research
∙
11/30/2022
Lifting to Parity Decision Trees Via Stifling
We show that the deterministic decision tree complexity of a (partial) f...
share
research
∙
09/14/2021
Monotone Complexity of Spanning Tree Polynomial Re-visited
We prove two results that shed new light on the monotone complexity of t...
research
∙
12/09/2020
Symmetry and Quantum Query-to-Communication Simulation
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean fun...
research
∙
09/06/2020
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
We give improved separations for the query complexity analogue of the lo...
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
∙
04/30/2019
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
Lifting theorems are theorems that relate the query complexity of a func...
research
∙
04/30/2019
Query-to-communication lifting for BPP using inner product
We prove a new query-to-communication lifting for randomized protocols, ...
research
∙
01/17/2019