4 papers
Quantum-Classical Equivalence for AND-Functions
Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay +2
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean funct…
On the Advantage of Adaptivity for Sampling with Cell Probes
Farzan Byramji, Daniel M. Kane, Jackson Morris +1
We construct an explicit distribution over that exhibits an essentially optimal separation between adaptive and non-adaptive cell-probe sampling. The distr…
Hard-to-Sample Distributions from Robust Extractors
Farzan Byramji, Daniel M. Kane, Jackson Morris +1
We provide a unified method for constructing explicit distributions which are difficult for restricted models of computation to generate. Our constructions are based on a new notio…
Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
Farzan Byramji, Russell Impagliazzo
We prove lower bounds for proofs of the bit pigeonhole principle (BPHP) and its generalizations in bounded-depth resolution over parities (Res). For weak BPHP with…