research
∙
03/30/2021
A note about claw function with a small range
In the claw detection problem we are given two functions f:D→ R and g:D→...
share
research
∙
03/09/2021
Several Separations Based on a Partial Boolean Function
We show a partial Boolean function f together with an input x∈ f^-1(*) s...
research
∙
02/16/2021
Unambiguous DNFs and Alon-Saks-Seymour
We exhibit an unambiguous k-DNF formula that requires CNF width Ω̃(k^2),...
research
∙
07/06/2020
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
We study the quantum query complexity of two problems. First, we consi...
research
∙
11/28/2019
Quantum Lower Bounds for 2D-Grid and Dyck Language
We show quantum lower bounds for two problems. First, we consider the pr...
research
∙
07/13/2018