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...
share
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/16/2022
Tight Lower Bounds for Approximate Exact k-Center in ℝ^d
In the discrete k-center problem, we are given a metric space (P,) where...
research
∙
07/11/2021
Karchmer-Wigderson Games for Hazard-free Computation
We present a Karchmer-Wigderson game to study the complexity of hazard-f...
research
∙
05/31/2021
Approximate polymorphisms
For a function g{0,1}^m→{0,1}, a function f{0,1}^n→{0,1} is called a g-p...
research
∙
06/18/2020
On the complexity of detecting hazards
Detecting and eliminating logic hazards in Boolean circuits is a fundame...
research
∙
03/10/2020
Algebraic Branching Programs, Border Complexity, and Tangent Spaces
Nisan showed in 1991 that the width of a smallest noncommutative single-...
research
∙
03/27/2019
Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions
The Fourier-Entropy Influence (FEI) Conjecture states that for any Boole...
research
∙
01/17/2019
Lower Bounds for Linear Decision Lists
We demonstrate a lower bound technique for linear decision lists, which ...
research
∙
09/26/2018
Improved bounds on Fourier entropy and Min-entropy
Given a Boolean function f:{-1,1}^n→{-1,1}, the Fourier distribution ass...
research
∙
12/05/2017