8 Search Results for "Lifshitz, Noam"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.2
Oracle Separations for the Quantum-Classical Polynomial Hierarchy

Authors: Avantika Agarwal and Shalev Ben{-}David

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum verifier. Our main result is that QCPH is infinite relative to a random oracle (previously, this was not even known relative to any oracle). We further prove that higher levels of PH are not contained in lower levels of QCPH relative to a random oracle; this is a strengthening of the somewhat recent result that PH is infinite relative to a random oracle (Rossman, Servedio, and Tan 2016). The oracle separation requires lower bounding a certain type of low-depth alternating circuit with some quantum gates. To establish this, we give a new switching lemma for quantum algorithms which may be of independent interest. Our lemma says that for any d, if we apply a random restriction to a function f with quantum query complexity Q(f) ≤ n^{1/3}, the restricted function becomes exponentially close (in terms of d) to a depth-d decision tree. Our switching lemma works even in a "worst-case" sense, in that only the indices to be restricted are random; the values they are restricted to are chosen adversarially. Moreover, the switching lemma also works for polynomial degree in place of quantum query complexity.
Cite as

Avantika Agarwal and Shalev Ben-David. Oracle Separations for the Quantum-Classical Polynomial Hierarchy. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ITCS.2026.2,
  author =	{Agarwal, Avantika and Ben\{-\}David, Shalev},
  title =	{{Oracle Separations for the Quantum-Classical Polynomial Hierarchy}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{2:1--2:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.2},
  URN =		{urn:nbn:de:0030-drops-252893},
  doi =		{10.4230/LIPIcs.ITCS.2026.2},
  annote =	{Keywords: Switching Lemma, Polynomial Hierarchy, Approximate Degree, Random Oracles, Query Complexity, Quantum Computing}
}
Document
DOI: 10.4230/LIPIcs.ITP.2025.9
Algebra Is Half the Battle: Verifying Presentations of Graded Unipotent Chevalley Groups

Authors: Eric Wang, Arohee Bhoja, Cayden Codel, and Noah G. Singer

Published in: LIPIcs, Volume 352, 16th International Conference on Interactive Theorem Proving (ITP 2025)

Abstract
Graded unipotent Chevalley groups are an important family of groups on matrices with polynomial entries over a finite field. Using the Lean theorem prover, we verify that three such groups, namely, the A₃- and the two B₃-type groups, satisfy a useful group-theoretic condition. Specifically, these groups are defined by a set of equations called Steinberg relations, and we prove that a certain canonical "smaller" set of Steinberg relations suffices to derive the rest. Our work is motivated by an application for building topologically-interesting objects called higher-dimensional expanders (HDXs). In the past decade, HDXs have formed the basis for many new results in theoretical computer science, such as in quantum error correction and in property testing. Yet despite the increasing prevalence of HDXs, only two methods of constructing them are known. One such method builds an HDX from groups that satisfy the aforementioned property, and the Chevalley groups we use are (essentially) the only ones currently known to satisfy it.
Cite as

Eric Wang, Arohee Bhoja, Cayden Codel, and Noah G. Singer. Algebra Is Half the Battle: Verifying Presentations of Graded Unipotent Chevalley Groups. In 16th International Conference on Interactive Theorem Proving (ITP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 352, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ITP.2025.9,
  author =	{Wang, Eric and Bhoja, Arohee and Codel, Cayden and Singer, Noah G.},
  title =	{{Algebra Is Half the Battle: Verifying Presentations of Graded Unipotent Chevalley Groups}},
  booktitle =	{16th International Conference on Interactive Theorem Proving (ITP 2025)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-396-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{352},
  editor =	{Forster, Yannick and Keller, Chantal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2025.9},
  URN =		{urn:nbn:de:0030-drops-246071},
  doi =		{10.4230/LIPIcs.ITP.2025.9},
  annote =	{Keywords: Group presentations, term rewriting, metaprogramming, proof automation, the Lean theorem prover}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.34
Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan

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

Abstract
We consider random walks on "balanced multislices" of any "grid" that respects the "symmetries" of the grid, and show that a broad class of such walks are good spectral expanders. (A grid is a set of points of the form 𝒮ⁿ for finite 𝒮, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in 𝒮. A walk respects symmetries if the probability of going from u = (u_1,…,u_n) to v = (v_1,…,v_n) is invariant under simultaneous permutations of the coordinates of u and v.) Our main theorem shows that, under some technical conditions, every such walk where a single step leads to an almost 𝒪(1)-wise independent distribution on the next state, conditioned on the previous state, satisfies a non-trivially small singular value bound. We give two applications of our theorem to error-correcting codes: (1) We give an analog of the Ore-DeMillo-Lipton-Schwartz-Zippel lemma for polynomials, and junta-sums, over balanced multislices. (2) We also give a local list-correction algorithm for d-junta-sums mapping an arbitrary grid 𝒮ⁿ to an Abelian group, correcting from a near-optimal (1/|𝒮|^d - ε) fraction of errors for every ε > 0, where a d-junta-sum is a sum of (arbitrarily many) d-juntas (and a d-junta is a function that depends on only d of the n variables). Our proofs are obtained by exploring the representation theory of the symmetric group and merging it with some careful spectral analysis.
Cite as

Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan. Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 34:1-34:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amireddy_et_al:LIPIcs.APPROX/RANDOM.2025.34,
  author =	{Amireddy, Prashanth and Behera, Amik Raj and Srinivasan, Srikanth and Sudan, Madhu},
  title =	{{Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{34:1--34:12},
  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.34},
  URN =		{urn:nbn:de:0030-drops-244004},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.34},
  annote =	{Keywords: Markov Chains, Random Walk, Multislices, Representation Theory of Symmetric Group, Local Correction, Low-degree Polynomials, Polynomial Distance Lemma}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.7
Sparser Abelian High Dimensional Expanders

Authors: Yotam Dikstein, Siqi Liu, and Avi Wigderson

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
The focus of this paper is the development of new elementary techniques for the construction and analysis of high dimensional expanders. Specifically, we present two new explicit constructions of Cayley high dimensional expanders (HDXs) over the abelian group 𝔽₂ⁿ. Our expansion proofs use only linear algebra and combinatorial arguments. The first construction gives local spectral HDXs of any constant dimension and subpolynomial degree exp(n^ε) for every ε > 0, improving on a construction by Golowich [Golowich, 2023] which achieves ε = 1/2. [Golowich, 2023] derives these HDXs by sparsifying the complete Grassmann poset of subspaces. The novelty in our construction is the ability to sparsify any expanding Grassmann posets, leading to iterated sparsification and much smaller degrees. The sparse Grassmannian (which is of independent interest in the theory of HDXs) serves as the generating set of the Cayley graph. Our second construction gives a 2-dimensional HDX of any polynomial degree exp(ε n) for any constant ε > 0, which is simultaneously a spectral expander and a coboundary expander. To the best of our knowledge, this is the first such non-trivial construction. We name it the Johnson complex, as it is derived from the classical Johnson scheme, whose vertices serve as the generating set of this Cayley graph. This construction may be viewed as a derandomization of the recent random geometric complexes of [Liu et al., 2023]. Establishing coboundary expansion through Gromov’s "cone method" and the associated isoperimetric inequalities is the most intricate aspect of this construction. While these two constructions are quite different, we show that they both share a common structure, resembling the intersection patterns of vectors in the Hadamard code. We propose a general framework of such "Hadamard-like" constructions in the hope that it will yield new HDXs.
Cite as

Yotam Dikstein, Siqi Liu, and Avi Wigderson. Sparser Abelian High Dimensional Expanders. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 7:1-7:98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dikstein_et_al:LIPIcs.CCC.2025.7,
  author =	{Dikstein, Yotam and Liu, Siqi and Wigderson, Avi},
  title =	{{Sparser Abelian High Dimensional Expanders}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{7:1--7:98},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.7},
  URN =		{urn:nbn:de:0030-drops-237013},
  doi =		{10.4230/LIPIcs.CCC.2025.7},
  annote =	{Keywords: Local spectral expander, coboundary expander, Grassmannian expander}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.10
Biased Linearity Testing in the 1% Regime

Authors: Subhash Khot and Kunal Mittal

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We study linearity testing over the p-biased hypercube ({0,1}ⁿ, μ_p^{⊗n}) in the 1% regime. For a distribution ν supported over {x ∈ {0,1}^k:∑_{i=1}^k x_i = 0 (mod 2)}, with marginal distribution μ_p in each coordinate, the corresponding k-query linearity test Lin(ν) proceeds as follows: Given query access to a function f:{0,1}ⁿ → {-1,1}, sample (x_1,… ,x_k)∼ ν^{⊗n}, query f on x_1,… ,x_k, and accept if and only if ∏_{i ∈ [k]} f(x_i) = 1. Building on the work of Bhangale, Khot, and Minzer (STOC '23), we show, for 0 < p ≤ 1/2, that if k ≥ 1+1/p, then there exists a distribution ν such that the test Lin(ν) works in the 1% regime; that is, any function f:{0,1}ⁿ → {-1,1} passing the test Lin(ν) with probability ≥ 1/2+ε, for some constant ε > 0, satisfies Pr_{x∼μ_p^{⊗n}}[f(x) = g(x)] ≥ 1/2+δ, for some linear function g, and a constant δ = δ(ε) > 0. Conversely, we show that if k < 1+1/p, then no such test Lin(ν) works in the 1% regime. Our key observation is that the linearity test Lin(ν) works if and only if the distribution ν satisfies a certain pairwise independence property.
Cite as

Subhash Khot and Kunal Mittal. Biased Linearity Testing in the 1% Regime. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khot_et_al:LIPIcs.CCC.2025.10,
  author =	{Khot, Subhash and Mittal, Kunal},
  title =	{{Biased Linearity Testing in the 1\% Regime}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{10:1--10:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.10},
  URN =		{urn:nbn:de:0030-drops-237046},
  doi =		{10.4230/LIPIcs.CCC.2025.10},
  annote =	{Keywords: Linearity test, 1\% regime, p-biased}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.11
A Near-Optimal Polynomial Distance Lemma over Boolean Slices

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that n-variate non-zero polynomial functions of degree d over a field 𝔽, are non-zero over any "grid" (points of the form Sⁿ for finite subset S ⊆ 𝔽) with probability at least max{|S|^{-d/(|S|-1)},1-d/|S|} over the choice of random point from the grid. In particular, over the Boolean cube (S = {0,1} ⊆ 𝔽), the lemma asserts non-zero polynomials are non-zero with probability at least 2^{-d}. In this work we extend the ODLSZ lemma optimally (up to lower-order terms) to "Boolean slices" i.e., points of Hamming weight exactly k. We show that non-zero polynomials on the slice are non-zero with probability (t/n)^{d}(1 - o_{n}(1)) where t = min{k,n-k} for every d ≤ k ≤ (n-d). As with the ODLSZ lemma, our results extend to polynomials over Abelian groups. This bound is tight upto the error term as evidenced by multilinear monomials of degree d, and it is also the case that some corrective term is necessary. A particularly interesting case is the "balanced slice" (k = n/2) where our lemma asserts that non-zero polynomials are non-zero with roughly the same probability on the slice as on the whole cube. The behaviour of low-degree polynomials over Boolean slices has received much attention in recent years. However, the problem of proving a tight version of the ODLSZ lemma does not seem to have been considered before, except for a recent work of Amireddy, Behera, Paraashar, Srinivasan and Sudan (SODA 2025), who established a sub-optimal bound of approximately ((k/n)⋅ (1-(k/n)))^d using a proof similar to that of the standard ODLSZ lemma. While the statement of our result mimics that of the ODLSZ lemma, our proof is significantly more intricate and involves spectral reasoning which is employed to show that a natural way of embedding a copy of the Boolean cube inside a balanced Boolean slice is a good sampler.
Cite as

Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan. A Near-Optimal Polynomial Distance Lemma over Boolean Slices. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amireddy_et_al:LIPIcs.ICALP.2025.11,
  author =	{Amireddy, Prashanth and Behera, Amik Raj and Srinivasan, Srikanth and Sudan, Madhu},
  title =	{{A Near-Optimal Polynomial Distance Lemma over Boolean Slices}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.11},
  URN =		{urn:nbn:de:0030-drops-233881},
  doi =		{10.4230/LIPIcs.ICALP.2025.11},
  annote =	{Keywords: Low-degree polynomials, Boolean slices, Schwartz-Zippel Lemma}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.9
Quantum Merlin-Arthur and Proofs Without Relative Phase

Authors: Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We study a variant of QMA where quantum proofs have no relative phase (i.e. non-negative amplitudes, up to a global phase). If only completeness is modified, this class is equal to QMA [Grilo et al., 2014]; but if both completeness and soundness are modified, the class (named QMA+ by Jeronimo and Wu [Jeronimo and Wu, 2023]) can be much more powerful. We show that QMA+ with some constant gap is equal to NEXP, yet QMA+ with some other constant gap is equal to QMA. One interpretation is that Merlin’s ability to "deceive" originates from relative phase at least as much as from entanglement, since QMA(2) ⊆ NEXP.
Cite as

Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. Quantum Merlin-Arthur and Proofs Without Relative Phase. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bassirian_et_al:LIPIcs.ITCS.2024.9,
  author =	{Bassirian, Roozbeh and Fefferman, Bill and Marwaha, Kunal},
  title =	{{Quantum Merlin-Arthur and Proofs Without Relative Phase}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.9},
  URN =		{urn:nbn:de:0030-drops-195370},
  doi =		{10.4230/LIPIcs.ITCS.2024.9},
  annote =	{Keywords: quantum complexity, QMA(2), PCPs}
}
Document
Extended Abstract
DOI: 10.4230/LIPIcs.ITCS.2021.87
Complexity Measures on the Symmetric Group and Beyond (Extended Abstract)

Authors: Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, and Marc Vinyals

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decision tree complexity, sensitivity, block sensitivity, and a few others. We show that these complexity measures are polynomially related for the symmetric group and for many other domains. To show that all measures but sensitivity are polynomially related, we generalize classical arguments of Nisan and others. To add sensitivity to the mix, we reduce to Huang’s sensitivity theorem using "pseudo-characters", which witness the degree of a function. Using similar ideas, we extend the characterization of Boolean degree 1 functions on the symmetric group due to Ellis, Friedgut and Pilpel to the perfect matching scheme. As another application of our ideas, we simplify the characterization of maximum-size t-intersecting families in the symmetric group and the perfect matching scheme.
Cite as

Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, and Marc Vinyals. Complexity Measures on the Symmetric Group and Beyond (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 87:1-87:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dafni_et_al:LIPIcs.ITCS.2021.87,
  author =	{Dafni, Neta and Filmus, Yuval and Lifshitz, Noam and Lindzey, Nathan and Vinyals, Marc},
  title =	{{Complexity Measures on the Symmetric Group and Beyond}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{87:1--87:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.87},
  URN =		{urn:nbn:de:0030-drops-136267},
  doi =		{10.4230/LIPIcs.ITCS.2021.87},
  annote =	{Keywords: Computational Complexity Theory, Analysis of Boolean Functions, Complexity Measures, Extremal Combinatorics}
}
  • Refine by Type
  • 8 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2024
  • 1 2021

  • Refine by Author
  • 2 Amireddy, Prashanth
  • 2 Behera, Amik Raj
  • 2 Srinivasan, Srikanth
  • 2 Sudan, Madhu
  • 1 Agarwal, Avantika
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Computational complexity and cryptography
  • 2 Theory of computation → Quantum complexity theory
  • 1 Computing methodologies → Symbolic and algebraic manipulation
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Spectra of graphs
  • Show More...

  • Refine by Keyword
  • 1 1% regime
  • 1 Analysis of Boolean Functions
  • 1 Approximate Degree
  • 1 Boolean slices
  • 1 Complexity Measures
  • Show More...

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