Search Results

Documents authored by Byramji, Farzan

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.37
Hard-To-Sample Distributions from Robust Extractors

Authors: Farzan Byramji, Daniel M. Kane, Jackson Morris, and Anthony Ostuni

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
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 notion of robust extractors, which are extractors that remain sound even when a small number of points violate the min-entropy constraint. Using such objects, we show that for a broad range of sampling models (e.g., low-depth circuits, small-space sources, etc.), every output of the model has distance 1 - o(1) from our target distribution, qualitatively recovering essentially all previously known hardness results. Our work extends that of Viola (SICOMP '14), who developed an earlier unified framework based on traditional extractors to rule out sampling with very small error. As a further application of our technique, we leverage a recent extractor construction of Chattopadhyay, Goodman, and Gurumukhani (ITCS '24) to present the first explicit distribution with distance 1 - o(1) from the output of any low-degree 𝔽₂-polynomial source. We note that a similar bound was obtained concurrently and independently by Khodabandeh and Shinkar (ECCC '26). We also describe a potential avenue toward proving a similar hardness result for AC⁰[⊕] circuits.
Cite as

Farzan Byramji, Daniel M. Kane, Jackson Morris, and Anthony Ostuni. Hard-To-Sample Distributions from Robust Extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 37:1-37:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{byramji_et_al:LIPIcs.APPROX/RANDOM.2026.37,
  author =	{Byramji, Farzan and Kane, Daniel M. and Morris, Jackson and Ostuni, Anthony},
  title =	{{Hard-To-Sample Distributions from Robust Extractors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{37:1--37:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.37},
  URN =		{urn:nbn:de:0030-drops-277543},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.37},
  annote =	{Keywords: sampling, extractor, low-degree polynomials}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.66
On the Advantage of Adaptivity for Sampling with Cell Probes

Authors: Farzan Byramji, Daniel M. Kane, Jackson Morris, and Anthony Ostuni

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
We construct an explicit distribution 𝐃 over {0,1}^N that exhibits an essentially optimal separation between adaptive and non-adaptive cell-probe sampling. The distribution can be sampled exactly when each output bit is allowed two adaptive probes to an arbitrarily long sequence of independent uniform symbols from [N]. In contrast, any non-adaptive sampler requires Ω̃(N) non-adaptive cell probes to generate a distribution with total variation distance less than 1-o(1) from 𝐃. This provides a 2-vs-Ω̃(N) separation for sampling with adaptive versus non-adaptive cell probes, improving upon the 2-vs-Ω̃(log N) separation of Yu and Zhan (ITCS '24) and the (log N)^O(1)-vs-N^Ω(1) separation of Alekseev, Göös, Myasnikov, Riazanov, and Sokolov (STOC '26).
Cite as

Farzan Byramji, Daniel M. Kane, Jackson Morris, and Anthony Ostuni. On the Advantage of Adaptivity for Sampling with Cell Probes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 66:1-66:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{byramji_et_al:LIPIcs.APPROX/RANDOM.2026.66,
  author =	{Byramji, Farzan and Kane, Daniel M. and Morris, Jackson and Ostuni, Anthony},
  title =	{{On the Advantage of Adaptivity for Sampling with Cell Probes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{66:1--66:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.66},
  URN =		{urn:nbn:de:0030-drops-277839},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.66},
  annote =	{Keywords: sampling lower bound, cell probe model, adaptive sampling}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.23
Quantum-Classical Equivalence for And-Functions

Authors: Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, and Shachar Lovett

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for And-functions of the form F(x,y) = f(x₁ ∧ y₁, …, x_n ∧ y_n), when the outer function f is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all And-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function f, the bounded-error quantum and classical deterministic communication complexities of the function f∘And₂ are polynomially related, up to polylogarithmic factors in n. We prove this by showing that both are characterized - up to polynomial loss - by the logarithm of the De Morgan sparsity of f. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett [Arkadev Chattopadhyay et al., 2026] on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general And-functions.
Cite as

Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, and Shachar Lovett. Quantum-Classical Equivalence for And-Functions. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.CCC.2026.23,
  author =	{Bhattacharya, Sreejata Kishor and Byramji, Farzan and Chattopadhyay, Arkadev and Dahiya, Yogesh and Lovett, Shachar},
  title =	{{Quantum-Classical Equivalence for And-Functions}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{23:1--23:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.23},
  URN =		{urn:nbn:de:0030-drops-270656},
  doi =		{10.4230/LIPIcs.CCC.2026.23},
  annote =	{Keywords: Communication complexity, quantum communication complexity, De Morgan sparsity, approximate gamma two norm, And-functions}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.55
Lifting to Randomized Parity Decision Trees

Authors: Farzan Byramji and Russell Impagliazzo

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We prove a lifting theorem from randomized decision tree depth to randomized parity decision tree (PDT) size. We use the same property of the gadget, stifling, which was introduced by Chattopadhyay, Mande, Sanyal and Sherif [ITCS 23] to prove a lifting theorem for deterministic PDTs. Moreover, even the milder condition that the gadget has minimum parity certificate complexity at least 2 suffices for lifting to randomized PDT size. To improve the dependence on the gadget g in the lower bounds for composed functions, we consider a related problem g_* whose inputs are certificates of g. It is implicit in the work of Chattopadhyay et al. that for any function f, lower bounds for the *-depth of f_* give lower bounds for the PDT size of f. We make this connection explicit in the deterministic case and show that it also holds for randomized PDTs. We then combine this with composition theorems for *-depth, which follow by adapting known composition theorems for decision trees. As a corollary, we get tight lifting theorems when the gadget is Indexing, Inner Product or Disjointness.
Cite as

Farzan Byramji and Russell Impagliazzo. Lifting to Randomized Parity Decision Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 55:1-55:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{byramji_et_al:LIPIcs.APPROX/RANDOM.2025.55,
  author =	{Byramji, Farzan and Impagliazzo, Russell},
  title =	{{Lifting to Randomized Parity Decision Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{55:1--55:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.55},
  URN =		{urn:nbn:de:0030-drops-244213},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.55},
  annote =	{Keywords: Parity decision trees, composition}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact