research
∙
08/04/2023
Linear isomorphism testing of Boolean functions with small approximate spectral norm
Two Boolean functions f, g : F_2^n →-1, 1 are called linearly isomorphic...
share
research
∙
08/04/2023
Randomized and quantum query complexities of finding a king in a tournament
A tournament is a complete directed graph. It is well known that every t...
research
∙
07/08/2023
On the Composition of Randomized Query Complexity and Approximate Degree
For any Boolean functions f and g, the question whether R(f∘ g) = Θ̃(R(f...
research
∙
03/23/2021
Separations between Combinatorial Measures for Transitive Functions
The role of symmetry in Boolean functions f:{0,1}^n →{0,1} has been exte...
research
∙
12/09/2020
Symmetry and Quantum Query-to-Communication Simulation
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean fun...
research
∙
12/03/2020
Tight Chang's-lemma-type bounds for Boolean functions
Chang's lemma (Duke Mathematical Journal, 2002) is a classical result wi...
research
∙
07/17/2020
Query Complexity of Global Minimum Cut
In this work, we resolve the query complexity of global minimum cut prob...
research
∙
06/24/2020
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
The disjointness problem - where Alice and Bob are given two subsets of ...
research
∙
09/23/2019
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean f...
research
∙
06/18/2019