DROPS

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

DOI: 10.4230/LIPIcs.ITCS.2025.17

Random Restrictions of Bounded Low Degree Polynomials Are Juntas

Authors: Sreejata Kishor Bhattacharya

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

We study the effects of random restrictions on low degree functions that are bounded on every point of the Boolean cube. Our main result shows that, with high probability, the restricted function can be approximated by a junta of arity that is just polynomial in the original degree. More precisely, let f: {± 1}ⁿ → [0,1] be a degree d polynomial (d ≥ 2) and let ρ denote a random restriction with survival probability O(log(d)/d). Then, with probability at least 1-d^{-Ω(1)}, there exists a function g: {± 1}ⁿ → [0,1] depending on at most d^O(1) coordinates such that ||f_{ρ}-g||_2^2 ≤ d^{-1-Ω(1)}. Our result has the following consequence for the well known, outstanding conjecture of Aaronson and Ambainis. The Aaronson-Ambainis conjecture was formulated to show that the acceptance probability of a quantum query algorithm can be well approximated almost everywhere by a classical query algorithm with a polynomial blow-up: it speculates that a polynomal f: {± 1}ⁿ → [0,1] with degree d has a coordinate with influence ≥ poly(1/d, Var[f]). Our result shows that this is true for a non-negligible fraction of random restrictions of f assuming Var[f] is not too low. Our work combines the ideas of Dinur, Friedgut, Kindler and O'Donnell [Dinur et al., 2006] with an approximation theoretic result, first reported in the recent work of Filmus, Hatami, Keller and Lifshitz [Yuval Filmus and Hamed Hatami, 2014].

Cite as

Sreejata Kishor Bhattacharya. Random Restrictions of Bounded Low Degree Polynomials Are Juntas. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhattacharya:LIPIcs.ITCS.2025.17,
  author =	{Bhattacharya, Sreejata Kishor},
  title =	{{Random Restrictions of Bounded Low Degree Polynomials Are Juntas}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.17},
  URN =		{urn:nbn:de:0030-drops-226459},
  doi =		{10.4230/LIPIcs.ITCS.2025.17},
  annote =	{Keywords: Analysis of Boolean Functions, Quantum Query Algorithms}
}

Document

DOI: 10.4230/LIPIcs.CCC.2024.23

Exponential Separation Between Powers of Regular and General Resolution over Parities

Authors: Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, and Pavel Dvořák

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract

Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities is an outstanding problem that has received a lot of attention after its introduction by Itsykson and Sokolov [Dmitry Itsykson and Dmitry Sokolov, 2014]. Very recently, Efremenko, Garlík and Itsykson [Klim Efremenko et al., 2023] proved the first exponential lower bounds on the size of ResLin proofs that were additionally restricted to be bottom-regular. We show that there are formulas for which such regular ResLin proofs of unsatisfiability continue to have exponential size even though there exist short proofs of their unsatisfiability in ordinary, non-regular resolution. This is the first super-polynomial separation between the power of general ResLin and that of regular ResLin for any natural notion of regularity. Our argument, while building upon the work of Efremenko et al. [Klim Efremenko et al., 2023], uses additional ideas from the literature on lifting theorems.

Cite as

Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, and Pavel Dvořák. Exponential Separation Between Powers of Regular and General Resolution over Parities. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 23:1-23:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.CCC.2024.23,
  author =	{Bhattacharya, Sreejata Kishor and Chattopadhyay, Arkadev and Dvo\v{r}\'{a}k, Pavel},
  title =	{{Exponential Separation Between Powers of Regular and General Resolution over Parities}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{23:1--23:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.23},
  URN =		{urn:nbn:de:0030-drops-204191},
  doi =		{10.4230/LIPIcs.CCC.2024.23},
  annote =	{Keywords: Proof Complexity, Regular Reslin, Branching Programs, Lifting}
}

Search Results

Documents authored by Bhattacharya, Sreejata Kishor

Quantum-Classical Equivalence for And-Functions

Abstract

Cite as

Random Restrictions of Bounded Low Degree Polynomials Are Juntas

Abstract

Cite as

Exponential Separation Between Powers of Regular and General Resolution over Parities

Abstract

Cite as

Thanks for your feedback!

Could not send message