On the Approximability of Boolean Max-$k$-CSP

Ainesh Bakshi

REVIEW 3 major objections 4 minor 151 references

On the Approximability of Boolean Max-$k$-CSP

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For every fixed k >= 10, a randomized polynomial-time algorithm approximates any Boolean Max-k-CSP instance within k/2^k, up to an arbitrarily small loss.

desk verdict A clean and significant improvement for Boolean Max-k-CSP, but the main result rests on an unproved lemma from a concurrent preprint. read the letter →

arxiv 2608.05331 v1 pith:YGSSWWFG submitted 2026-08-05 cs.CC cs.DS

Ainesh Bakshi This is my paper · ORCID

classification cs.CCcs.DS MSC 68Q1768Q2590C2260E1560G15

keywords Max-k-CSPapproximationalgorithmssemidefiniteprogrammingGaussianroundingorthantprobabilitiescomparisoninequalityUniqueGamesConjecture

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes a randomized polynomial-time algorithm achieving an approximation ratio of k/2^k for every Boolean Max-k-CSP with fixed arity k >= 10, up to any desired additive epsilon. The previous best guarantee was 0.626612 k/2^k, so this closes the gap to the k/2^k scale. The algorithm rounds the standard Makarychev-Makarychev SDP with a noisy Gaussian hyperplane, mixing a common Gaussian signal with independent noise. The proof reduces clause satisfaction to a lower bound on Gaussian orthant probabilities, obtained from a new comparison inequality that amplifies the orthant probability when the covariance has a strong all-ones component. Combined with the UGC-based hardness upper bound, the result makes the limiting approximation constant exactly 1.

What carries the argument

The Gaussian orthant amplification inequality (Theorem 4.1) states that for a centered Gaussian vector X with correlation matrix R, Pr[X >= 0] >= $2^{{-m}}$ exp((m - 1^T $R^{{-1}}$ 1)/pi). It converts a lower bound on the common all-ones component of the covariance into an exponential lift of the positive-orthant probability above $2^{{-m}}$. The proof derives this inequality from a centered Gaussian product inequality (Lemma 4.2) by exponentially tilting half-line indicators and choosing the test point b = $\sqrt$(2/pi) 1; the corollary rank-one version handles covariance matrices that dominate eta J. This mechanism is what lets the noisy rounding, with noise fraction delta = pi/k, recover the missing factor k instead of leaving a 1+o(1) loss.

What would settle it

Fix k = 10 and take a covariance matrix R = eta J + (1 - eta) I for eta in {1/10, 1/2, 9/10}; numerically compute Pr[X >= 0] for X ~ N(0, R) with high-accuracy quadrature or Monte Carlo and compare it with $2^{{-k}}$ exp((k - 1/eta)/pi). Any value below the bound refutes the orthant amplification inequality. More directly, a single bounded log-concave function with zero Gaussian first moment whose correlated expectation is smaller than its independent expectation would refute Lemma 4.2 and hence the main theorem.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: for every fixed integer k >= 10 and every epsilon > 0, there is a randomized algorithm that, given any Boolean Max-k-CSP instance I on n variables with m constraints, outputs an assignment x satisfying E[val_I(x)] >= (k/2^k - epsilon) OPT(I), running in poly(n,m,k, log(1/epsilon)) time. In exact arithmetic the rounding achieves the full factor k/2^k, with the epsilon arising only from finite-precision implementation. The analysis is clausewise: for every conjunction C with SDP value q = ||z_C||^2, the noisy Gaussian rounding satisfies C with probability at least (k/2^k) q; summing over clauses yields the global ratio. This resolves the conjecture that the approximation-ratio constant c_k tends to 1, and shows that the SDP from [MM12] admits a rounding with no (1+o(1)) loss.

Load-bearing premise

The argument hinges on an imported lemma asserting that, for bounded one-hump functions with zero average under the standard Gaussian, replacing independent Gaussians by any correlated Gaussian can only increase the expected product; this lemma is used as a black box and not proved here.

Editorial extensions

If this is right

For every fixed k >= 10, Boolean Max-k-CSP admits a randomized polynomial-time (k/2^k - epsilon)-approximation, and in exact arithmetic the factor is exactly k/2^k.
The approximation-ratio constant c_k satisfies lim_{k -> infinity} c_k = 1, so the k/2^k scale is optimal up to lower-order terms, assuming the Unique Games Conjecture.
The same SDP relaxation used in [MM12] is shown to be roundable to k/2^k, so no (1+o(1)) loss is necessary for that relaxation.
The algorithm runs in time polynomial in n, m, k, and log(1/epsilon), so the additive loss can be made exponentially small in 1/epsilon at modest computational cost.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The orthant amplification inequality is a standalone statement about Gaussian measure; it likely applies to other rounding problems where the covariance has a rank-one lower bound, such as Max-Cut-type or graph-coloring SDPs, though the paper does not explore these.
The k >= 10 restriction may be an artifact of the proof rather than a fundamental barrier; numerically testing the inequality for small arities could reveal whether the bound extends to k >= 3.
Because the main theorem depends on an imported lemma not proved in the paper, a machine-checked proof or a counterexample search for Lemma 4.2 would settle the conditional nature of the result.
The finite-precision analysis suggests that only O(log(1/epsilon)) bits of precision are needed for implementation, so the algorithm could plausibly be run at large k; this is a testable engineering prediction.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Konstantin, here's my take on Bakshi's Max-k-CSP paper. The headline: it proves a k/2^k approximation for Boolean Max-k-CSP, improving the previous 0.626612 k/2^k, provided the Centered Gaussian Product Inequality (Lemma 4.2) from Mulgund's concurrent preprint holds. That lemma is the load-bearing wall.

What is genuinely new: the Gaussian orthant amplification inequality (Theorem 4.1) and the observation that a lossless clausewise bound follows by choosing delta = pi/k and applying the scalar logarithmic-mean inequality (Lemma 5.3). The reduction from clauses to orthant events is standard, but the covariance analysis is careful, and the proof of Lemma 5.3 is elementary and correct. I checked the key steps in Sections 3 and 5; they hang together. If the bound holds, it settles the Makarychev–Makarychev conjecture and matches UGC hardness up to a 1+1/k factor. That is a real step.

The soft spot is exactly what the stress-test flagged: Theorem 4.1's proof uses Lemma 4.2 as a black box, with no proof or independent verification. Lemma 4.2 is a strong statement about arbitrary bounded log-concave functions with zero Gaussian first moments, imported from an unreviewed preprint. If that lemma carries a hidden hypothesis or a flaw, the argument collapses. The paper does not dodge this—it cites Mulgund explicitly—but a published theorem that depends on an unreviewed concurrent result is fragile. I would want a referee to verify the lemma independently, or require the author to include a self-contained proof.

Everything else checks out. The SDP rounding, the noise interpolation, and the finite-precision discussion are standard. There are no fitted constants; delta = pi/k is principled. The AI disclosure is honest.

Who is this for? Any theorist working on CSP approximation or Gaussian comparison inequalities. The orthant amplification inequality itself could find other uses. I would hesitate to cite it in my own work until the Mulgund lemma is resolved, but the paper is worth discussing.

Bottom line: this deserves a serious referee. Send it out, but with a clear instruction to verify Lemma 4.2 or have the author prove it. If the lemma holds, this is a top-venue paper; if not, the main theorem needs a new proof.

Referee Report

3 major / 4 minor

Summary. The paper studies the approximation of Boolean Max-k-CSP. Its main theorem (Theorem 1.1) claims that for every fixed integer k >= 10 and every epsilon > 0 there is a polynomial-time randomized algorithm achieving expected value at least (k/2^k - epsilon) OPT(I) on any instance I. This would improve the previous 0.626612 k/2^k guarantee of Makarychev and Makarychev and resolve their conjecture that the constant tends to 1. The method combines the Makarychev-Makarychev SDP relaxation with a noisy Gaussian hyperplane rounding at noise level delta = pi/k, reducing each clause to a Gaussian orthant probability. The central technical ingredient is a Gaussian orthant amplification inequality (Theorem 4.1), proved via a centered Gaussian product inequality imported as Lemma 4.2 from the concurrent preprint [Mul26]. A short self-contained scalar inequality (Lemma 5.3) then converts the orthant bound into the clausewise guarantee (k/2^k) ||z_C||^2.

Significance. If the main theorem is correct, it is a substantial result: it matches the UGC-based hardness of De and Mossel up to a 1+o(1) factor, resolves the Makarychev-Makarychev conjecture c_k -> 1, and shows that the standard MM12 SDP admits a rounding achieving the k/2^k barrier. The paper is commendably clean in several respects: the reduction to Gaussian orthants is natural, the covariance computation R_C - eta J in Section 5 is correct, the scalar Lemma 5.3 is proved in detail, and no fitted constants appear in the argument. The main concern is not internal inconsistency but dependence: the load-bearing Lemma 4.2 is taken as a black box from an unreviewed concurrent preprint, so the validity of Theorem 1.1 is conditional on an external result that this manuscript does not itself establish or verify.

major comments (3)

[Section 4, Lemma 4.2 and Eq. (6)] The proof of Theorem 4.1, and hence Corollary 4.3 and Theorem 5.1, relies entirely on Lemma 4.2, quoted as [Mul26, Theorem 4.1]. This lemma is used exactly once, at inequality (6), for the truncated exponential functions f_i(x) = e^{a(b_i)x} 1{x <= b_i}. The paper gives no proof of the lemma, no verification of its hypotheses against [Mul26], and no independent check of the concurrent preprint. If the centered Gaussian product inequality requires additional hypotheses, or if it is false for some tuple of bounded log-concave functions with zero Gaussian first moment, then inequality (6) fails and with it the orthant amplification bound, the k/2^k clausewise bound, and Theorem 1.1. For a journal submission, this external dependency must be removed by including a complete proof of Lemma 4.2, or at minimum a fully stated and verified theorem with a proof in an appendix.
[Section 3, Eq. (2)] The warm-up argument that the paper says already resolves Open Problem 2 of [MM17] uses [Mul26, Theorem 2.1] as a second unproved black box. This warm-up is not needed for the main theorem, but the paper presents it as a result in its own right, so either the source theorem should be proved here or the claim should be clearly marked as conditional on [Mul26].
[Section 5, proof of Theorem 5.1] The final paragraph of the proof says that standard arguments for solving the SDP and implementing Gaussian rounding in finite precision give running time poly(n, m, k, log(1/epsilon)), but no details are supplied. Since Theorem 1.1 includes the -epsilon term and the stated running time, the paper should spell out how approximate SDP solutions and finite-precision Gaussian sampling affect the guarantee, at least to the level of a standard rounding analysis.

minor comments (4)

[Corollary 4.3, Eq. (10)] The exponent in Eq. (10) is printed as m - eta - 1, which is ambiguous; the proof and the subsequent use in Section 5 make clear that the intended quantity is m - eta^{-1}. Please correct the typesetting.
[Throughout] Several expressions such as k2/2k and 2^{-k} appear without superscript formatting in the extracted text; in a final version these should be typeset unambiguously as k^2/2^k and 2^{-k}.
[Introduction and Section 3] There are minor typographical errors (e.g., 'disinguish', 'comaprison', 'boolean' vs. 'Boolean') that should be corrected.
[Acknowledgements] The sentence 'All the conceptual contributions in this work are biological' appears to be a typo or leftover text; the intended meaning is unclear and should be revised.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is parameter-free and self-contained except for an external, disclosed lemma from Mulgund, whose correctness risk is not a circularity.

full rationale

The paper's derivation chain is a standard SDP rounding analysis: reduce to weighted conjunctions, orient decision vectors toward the clause, express clause satisfaction as a Gaussian orthant probability, decompose the covariance as qJ + (1-q)G, add noise with δ = π/k, and apply the rank-one orthant amplification inequality followed by the scalar Lemma 5.3. No fitted constants appear: δ is a design choice, q is the SDP value, and the bound is proven for every instance rather than tuned to data. The only imported result is Lemma 4.2, the Centered Gaussian Product Inequality, cited from Mulgund's preprint [Mul26]. This is an external theorem by a different author, not a self-citation, and it does not by itself state the target k/2^k bound or the orthant amplification formula. Theorem 4.1 is derived from Lemma 4.2 through additional exponential tilting, a variational maximization, and an explicit test point, so the imported lemma is strictly more general than the derived result. The main vulnerability is that Lemma 4.2 is not proved or machine-checked in this paper, so if that lemma is false or has hidden hypotheses, the clausewise bound collapses. That is a correctness and verification risk, not circularity. There are no self-citations used as load-bearing premises, no imported uniqueness theorem from the author's own prior work, no renaming of a known result as a new one, and no ansatz smuggled in by citation. The paper is appropriately transparent about its external dependency. Therefore the circularity score is 0.

Assumptions & free parameters 1 free parameters · 1 assumptions · 0 invented entities

The central claim is a pure math/algorithmic statement. The only hand-chosen parameter is delta=pi/k; it is not fitted to data. The proof relies on one external lemma from Mulgund's preprint. No invented entities are introduced.

free parameters (1)

delta = pi/k
Algorithmic noise weight chosen by hand so that the exponent k s/(k+pi s) matches Lemma 5.3. Not fitted to data, but the proof's success depends on this exact value.

assumptions (1)

domain assumption Centered Gaussian product inequality (Lemma 4.2): for bounded log-concave functions f_i with positive Gaussian expectation and zero Gaussian first moment, E[prod_i f_i(X_i)] >= prod_i E[f_i(Z)] for any correlation matrix R.
Imported from [Mul26, Theorem 4.1] and used without proof in the proof of Theorem 4.1. The entire orthant amplification result depends on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the Approximability of Boolean Max-$k$-CSP." pith.science (2026). https://pith.science/paper/YGSSWWFG

@misc{pith2026260805331,
  author       = {Pith},
  title        = {Pith review of: On the Approximability of Boolean Max-$k$-CSP},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YGSSWWFG}},
  note         = {Machine review of arXiv:2608.05331}
}

abstract

Consider the problem of maximizing the number of satisfied constraints of an arbitrary boolean constraint satisfaction problem with arity $k$. We obtain a polynomial time algorithm that achieves a $(k/2^k)$-approximation, improving on the previous best guarantee of $0.626612\; k/2^k$, due to Makarychev and Makarychev (arXiv:1206.3603). Assuming the Unique Games Conjecture, De and Mossel (arXiv:1202.5258) showed that achieving an approximation ratio better than $(k+1)/2^k$ for odd $k$ and $(k+2)/2^k$ for even $k$, is NP-hard. The main technical ingredient is an extension of a recently established Gaussian comparison inequality, used to resolve the Weak Simplex Conjecture in coding theory (arXiv:2607.14087).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

151 extracted references · 23 canonical work pages

[1]

Physical Review A , volume=

Good quantum error-correcting codes exist , author=. Physical Review A , volume=. 1996 , publisher=

1996
[2]

Proceedings of the Royal Society of London

Multiple-particle interference and quantum error correction , author=. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences , volume=. 1996 , publisher=

1996
[3]

2011 ieee 52nd annual symposium on foundations of computer science , pages=

Rounding semidefinite programming hierarchies via global correlation , author=. 2011 ieee 52nd annual symposium on foundations of computer science , pages=. 2011 , organization=

2011
[5]

2002 , PAGES =

Lang, Serge , TITLE =. 2002 , PAGES =. doi:10.1007/978-1-4613-0041-0 , URL =

doi:10.1007/978-1-4613-0041-0 2002
[6]

Hamiltonian Sparsification and Gap-Simulation , booktitle =

Dorit Aharonov and Leo Zhou , editor =. Hamiltonian Sparsification and Gap-Simulation , booktitle =. 2019 , url =. doi:10.4230/LIPIcs.ITCS.2019.2 , timestamp =

doi:10.4230/lipics.itcs.2019.2 2019
[7]

doi:10.22331/q-2019-09-30-189 , url =

The complexity of simulating local measurements on quantum systems , author =. doi:10.22331/q-2019-09-30-189 , url =

doi:10.22331/q-2019-09-30-189 2019
[8]

Annales Henri Poincar

Translationally Invariant Universal Quantum Hamiltonians in 1D , author=. Annales Henri Poincar. 2020 , volume=

2020
[9]

48th International Colloquium on Automata, Languages, and Programming (

Ojas Parekh and Kevin Thompson , title =. 48th International Colloquium on Automata, Languages, and Programming (. 2021 , url =

2021

Show all 151 references

[10]

15th Conference on the Theory of Quantum Computation, Communication and Cryptography (

Anurag Anshu and David Gosset and Karen Morenz , title =. 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (. 2020 , url =. doi:10.4230/LIPIcs.TQC.2020.7 , eprint =

2020 doi
[11]

Quantum Inf

Itai Arad , title =. Quantum Inf. Comput. , volume =. 2011 , url =. doi:10.26421/QIC11.11-12-10 , timestamp =

2011 doi
[12]

Hastings , title =

Matthew B. Hastings , title =. 48th International Colloquium on Automata, Languages, and Programming,. 2021 , url =. doi:10.4230/LIPICS.ICALP.2021.102 , timestamp =

2021 doi
[13]

2013 , url =

Dorit Aharonov and Itai Arad and Thomas Vidick , title =. 2013 , url =. doi:10.1145/2491533.2491549 , timestamp =

2013
[14]

npj Quantum Information , volume=

Hamiltonian simulation in the low-energy subspace , author=. npj Quantum Information , volume=. 2021 , publisher=

2021
[15]

Quantum , volume=

Hamiltonian simulation for low-energy states with optimal time dependence , author=. Quantum , volume=. 2024 , publisher=

2024
[16]

arXiv preprint arXiv:2102.02991 , year=

Strongly universal Hamiltonian simulators , author=. arXiv preprint arXiv:2102.02991 , year=

arXiv
[17]

Reservoir-sampling algorithms of time complexity o (n (1+ log (

Li, Kim-Hung , journal=. Reservoir-sampling algorithms of time complexity o (n (1+ log (. 1994 , publisher=

1994
[18]

Physical Review A—Atomic, Molecular, and Optical Physics , volume=

Quantum-Merlin-Arthur--complete problems for stoquastic Hamiltonians and Markov matrices , author=. Physical Review A—Atomic, Molecular, and Optical Physics , volume=. 2010 , publisher=

2010
[19]

John Kallaugher and Ojas Parekh , title =. 63rd. 2022 , url =. doi:10.1109/FOCS54457.2022.00054 , timestamp =

2022
[20]

Uniform Expansion Bounds for Cayley Graphs of SL_2 (F_p ) , urldate =

Jean Bourgain and Alex Gamburd , journal =. Uniform Expansion Bounds for Cayley Graphs of SL_2 (F_p ) , urldate =
[21]

Gross , title =

Jonathan L. Gross , title =. Journal of Combinatorial Theory, Series B , volume =. 1977 , doi =

1977
[22]

Silva, Marcel Kenji de Carli and Harvey, Nicholas J. A. and Sato, Cristiane M. , title =. 2016 , url =. doi:10.1145/2746241 , timestamp =

2016 doi
[23]

Journal of Combinatorial Theory, Series A , volume =

Ervin Gergely , title =. Journal of Combinatorial Theory, Series A , volume =. 1974 , doi =

1974
[24]

1979 , institution=

New results on the independence number , author=. 1979 , institution=

1979
[25]

1981 , publisher=

A lower bound on the stability number of a simple graph , author=. 1981 , publisher=

1981
[26]

2015 , volume =

Foundations and Trends® in Machine Learning , title =. 2015 , volume =. doi:10.1561/2200000048 , issn =

2015 doi
[27]

1986 , isbn =

Chew, P , title =. 1986 , isbn =. doi:10.1145/10515.10534 , booktitle =

1986
[28]

Approximating s-t minimum cuts in \

Bencz\'. Approximating s-t minimum cuts in \. 1996 , isbn =. doi:10.1145/237814.237827 , booktitle =

1996
[29]

and Teng, Shang-Hua , title =

Spielman, Daniel A. and Teng, Shang-Hua , title =. SIAM Journal on Computing , volume =. 2011 , doi =

2011
[30]

and Srivastava, Nikhil , title =

Spielman, Daniel A. and Srivastava, Nikhil , title =. SIAM Journal on Computing , volume =. 2011 , doi =

2011
[31]

and Srivastava, Nikhil , title =

Batson, Joshua and Spielman, Daniel A. and Srivastava, Nikhil , title =. SIAM Review , volume =. 2014 , doi =

2014
[32]

Code sparsification and its applications , booktitle =

Khanna, Sanjeev and Putterman, Aaron and Sudan, Madhu , editor =. Code sparsification and its applications , booktitle =. 2024 , url =. doi:10.1137/1.9781611977912.185 , timestamp =

2024 doi
[33]

Annals of Mathematics , volume =

Assaf Naor and Robert Young , title =. Annals of Mathematics , volume =. 2018 , doi =

2018
[35]

and Meka, Raghu , title =

Kane, Daniel M. and Meka, Raghu , title =. 2013 , isbn =. doi:10.1145/2488608.2488610 , booktitle =

2013
[36]

2002 , issue_date =

Feige, Uriel and Schechtman, Gideon , title =. 2002 , issue_date =. doi:10.1002/rsa.10036 , journal =

2002 doi
[37]

2008 , note=

Feige, Uriel , title=. 2008 , note=

2008
[38]

2021 , month =

Luca Trevisan , title =. 2021 , month =

2021
[39]

2025 , archivePrefix=

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs , author=. 2025 , archivePrefix=

2025
[40]

Spielman , title =

Daniel A. Spielman , title =. 2019 , url =

2019
[41]

Nilli , abstract =

A. Nilli , abstract =. On the second eigenvalue of a graph , journal =. 1991 , issn =. doi:https://doi.org/10.1016/0012-365X(91)90112-F , url =

1991 doi
[42]

and Spielman, Daniel A

Marcus, Adam W. and Spielman, Daniel A. and Srivastava, Nikhil , TITLE =. Ann. of Math. (2) , FJOURNAL =. 2015 , NUMBER =

2015
[44]

An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification , booktitle =

Nikhil Srivastava and Luca Trevisan , editor =. An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification , booktitle =. 2018 , url =. doi:10.1137/1.9781611975031.85 , timestamp =

2018 doi
[45]

Electronic Journal of Combinatorics , volume =

Alexandr Polyanskii and Rinat Sadykov , title =. Electronic Journal of Combinatorics , volume =. 2024 , doi =

2024
[46]

2018 , archivePrefix=

Hyperbolic polynomials and the Kadison-Singer problem , author =. 2018 , archivePrefix=

2018
[47]

, booktitle=

Cohen, Michael B. , booktitle=. Ramanujan Graphs in Polynomial Time , year=
[48]

Journal für die reine und angewandte Mathematik (Crelles Journal) , doi =

Improved bounds in Weaver and Feichtinger conjectures , author =. Journal für die reine und angewandte Mathematik (Crelles Journal) , doi =. 2019 , lastchecked =

2019
[49]

Improved bounds in Weaver's KSr conjecture for high rank positive semidefinite matrices , journal =

Zhiqiang Xu and Zili Xu and Ziheng Zhu , keywords =. Improved bounds in Weaver's KSr conjecture for high rank positive semidefinite matrices , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.jfa.2023.109978 , url =

2023
[50]

, title =

Cohen, Michael B. , title =. 2016 , howpublished =

2016
[51]

2012 , URL =

Why is the minimum size of a generating set for a finite group at most _2 n ? , AUTHOR =. 2012 , URL =

2012
[52]

2024 , archivePrefix=

Selector form of Weaver's conjecture, Feichtinger's conjecture, and frame sparsification , author=. 2024 , archivePrefix=

2024
[53]

2024 , url =

Surya Teja Gavva and Peng Zhang , title =. 2024 , url =

2024
[54]

Proceedings of the London Mathematical Society , volume =

Alon, Noga and Bucić, Matija and Sauermann, Lisa and Zakharov, Dmitrii and Zamir, Or , title =. Proceedings of the London Mathematical Society , volume =. doi:https://doi.org/10.1112/plms.70044 , url =

doi
[55]

How Abelian is a Finite Group? , booktitle =

L\'aszl\'o Pyber , editor =. How Abelian is a Finite Group? , booktitle =. 1997 , pages =. doi:10.1007/978-3-642-60408-9_27 , isbn =

1997 doi
[56]

Information Theory

Ash, Robert. Information Theory
[57]

1994 , issn =

Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power q , journal =. 1994 , issn =. doi:https://doi.org/10.1006/jctb.1994.1054 , url =

1994
[58]

G. A. Margulis , title =. Problemy Peredachi Informacii , volume =. 1973 , mrnumber =

1973
[59]

Lubotzky and R

A. Lubotzky and R. Phillips and P. Sarnak , title =. Combinatorica , volume =. 1988 , mrnumber =

1988
[60]

Combinatorics, Probability and Computing , author=

Quasirandom Groups , volume=. Combinatorics, Probability and Computing , author=. 2008 , pages=. doi:10.1017/S0963548307008826 , number=

2008 doi
[62]

2025 , isbn =

Brakensiek, Joshua and Guruswami, Venkatesan , title =. 2025 , isbn =. doi:10.1145/3717823.3718212 , booktitle =

2025
[63]

Sparsifying Cayley Graphs on Every Group , booktitle =

Jun. Sparsifying Cayley Graphs on Every Group , booktitle =. 2026 , url =. doi:10.1137/1.9781611978971.215 , timestamp =

2026 doi
[64]

Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

A Simple and Sharper Proof of the Hypergraph Moore Bound , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , publisher=. doi:10.1137/1.9781611977554.ch89 , url=. 2207.10850 , archivePrefix=

2023 arXiv
[65]

Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=. 2022 , publisher=. doi:10.1145/3519935.3519955 , url=. 2109.04415 , archivePrefix=

2022
[66]

arXiv preprint arXiv:2311.00558 , year=

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes , author=. arXiv preprint arXiv:2311.00558 , year=. doi:10.48550/arXiv.2311.00558 , url=. 2311.00558 , archivePrefix=

doi arXiv
[68]

Liu and Aaron Sidford , editor =

Arun Jambulapati and Yang P. Liu and Aaron Sidford , editor =. Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification , booktitle =. 2023 , url =. doi:10.1145/3564246.3585136 , timestamp =

2023
[69]

Kothari and Yang P

Arpon Basu and Pravesh K. Kothari and Yang P. Liu and Raghu Meka , title =. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. doi:10.1137/1.9781611978971.216 , URL =

2026 doi
[70]

Karger , editor =

David R. Karger , editor =. Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm , booktitle =. 1993 , url =

1993
[71]

A Theory of Spectral

Sanjeev Khanna and Aaron Putterman and Madhu Sudan , editor =. A Theory of Spectral. 52nd International Colloquium on Automata, Languages, and Programming,. 2025 , url =. doi:10.4230/LIPIcs.ICALP.2025.107 , timestamp =

2025 doi
[72]

2017 , url =

Arnold Filtser and Robert Krauthgamer , title =. 2017 , url =. doi:10.1137/15M1046186 , timestamp =

2017 doi
[73]

On Fully Dynamic Graph Sparsifiers , booktitle =

Ittai Abraham and David Durfee and Ioannis Koutis and Sebastian Krinninger and Richard Peng , editor =. On Fully Dynamic Graph Sparsifiers , booktitle =. 2016 , url =. doi:10.1109/FOCS.2016.44 , timestamp =

2016 doi
[74]

Benson and Jon M

Nate Veldt and Austin R. Benson and Jon M. Kleinberg , title =. 2022 , url =. doi:10.1137/20m1321048 , timestamp =

2022 doi
[75]

Sketching Cuts in Graphs and Hypergraphs , booktitle =

Dmitry Kogan and Robert Krauthgamer , editor =. Sketching Cuts in Graphs and Hypergraphs , booktitle =. 2015 , url =. doi:10.1145/2688073.2688093 , timestamp =

2015
[76]

Spectral Sparsification of Hypergraphs , booktitle =

Tasuku Soma and Yuichi Yoshida , editor =. Spectral Sparsification of Hypergraphs , booktitle =. 2019 , url =. doi:10.1137/1.9781611975482.159 , timestamp =

2019 doi
[77]

Michael Kapralov and Robert Krauthgamer and Jakab Tardos and Yuichi Yoshida , title =. 62nd. 2021 , url =. doi:10.1109/FOCS52979.2021.00114 , timestamp =

2021
[78]

Towards tight bounds for spectral sparsification of hypergraphs , booktitle =

Michael Kapralov and Robert Krauthgamer and Jakab Tardos and Yuichi Yoshida , editor =. Towards tight bounds for spectral sparsification of hypergraphs , booktitle =. 2021 , url =. doi:10.1145/3406325.3451061 , timestamp =

2021
[79]

Sanjeev Khanna and Aaron Putterman and Madhu Sudan , title =. 65th. 2024 , url =. doi:10.1109/FOCS61266.2024.00105 , timestamp =

2024
[80]

Near-linear Size Hypergraph Cut Sparsifiers , booktitle =

Yu Chen and Sanjeev Khanna and Ansh Nagda , editor =. Near-linear Size Hypergraph Cut Sparsifiers , booktitle =. 2020 , url =. doi:10.1109/FOCS46700.2020.00015 , timestamp =

2020
[81]

CoRR , volume =

Joshua Brakensiek and Venkatesan Guruswami and Aaron Putterman , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2508.13345 , eprinttype =

2025 doi
[82]

Analyzing graph structure via linear measurements , booktitle =

Kook Jin Ahn and Sudipto Guha and Andrew McGregor , editor =. Analyzing graph structure via linear measurements , booktitle =. 2012 , url =. doi:10.1137/1.9781611973099.40 , timestamp =

2012 doi
[83]

Graph sketches: sparsification, spanners, and subgraphs , booktitle =

Kook Jin Ahn and Sudipto Guha and Andrew McGregor , editor =. Graph sketches: sparsification, spanners, and subgraphs , booktitle =. 2012 , url =. doi:10.1145/2213556.2213560 , timestamp =

2012
[84]

Sparsification of Directed Graphs via Cut Balance , booktitle =

Ruoxu Cen and Yu Cheng and Debmalya Panigrahi and Kevin Sun , editor =. Sparsification of Directed Graphs via Cut Balance , booktitle =. 2021 , url =. doi:10.4230/LIPIcs.ICALP.2021.45 , timestamp =

2021 doi
[85]

and Panigrahi, Debmalya , title =

Fung, Wai Shing and Hariharan, Ramesh and Harvey, Nicholas J.A. and Panigrahi, Debmalya , title =. Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing , pages =. 2011 , isbn =. doi:10.1145/1993636.1993647 , abstract =

2011
[86]

Sparsification of

Butti, Silvia and. Sparsification of. 2020 , month = jan, journal =

2020
[87]

On Redundancy in Constraint Satisfaction Problems , booktitle =

Cl. On Redundancy in Constraint Satisfaction Problems , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.CP.2022.11 , timestamp =

2022 doi
[88]

Joshua Brakensiek and Venkatesan Guruswami and Bart M. P. Jansen and Victor Lagerkvist and Magnus Wahlstr. The Richness of. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2507.07942 , eprinttype =

2025 doi
[89]

Chen, Hubie and Jansen, Bart M. P. and Pieterse, Astrid , year =. Best-. Algorithmica , volume =. doi:10.1007/s00453-019-00660-y , langid =

doi
[90]

Sparsification of

Lagerkvist, Victor and Wahlstr. Sparsification of. 2020 , month = jun, journal =. doi:10.1145/3389411 , langid =

2020 doi
[91]

Bessiere, Christian and Carbonnel, Cl. Chain. 2020 , month = apr, journal =. doi:10.1609/aaai.v34i02.5499 , copyright =

2020 doi
[92]

Constraint Acquisition via Partial Queries , booktitle =

Christian Bessiere and Remi Coletta and Emmanuel Hebrard and George Katsirelos and Nadjib Lazaar and Nina Narodytska and Claude. Constraint Acquisition via Partial Queries , booktitle =. 2013 , url =

2013
[93]

Optimal Lower Bounds for Sketching Graph Cuts , booktitle =

Charles Carlson and Alexandra Kolla and Nikhil Srivastava and Luca Trevisan , editor =. Optimal Lower Bounds for Sketching Graph Cuts , booktitle =. 2019 , url =. doi:10.1137/1.9781611975482.158 , timestamp =

2019 doi
[94]

Bart M. P. Jansen and Astrid Pieterse , title =. 2019 , url =. doi:10.1145/3349618 , timestamp =

2019 doi
[95]

Satisfiability

Dell, Holger and van Melkebeek, Dieter , year =. Satisfiability. J. ACM , volume =
[96]

Proceedings of the AAAI Conference on Artificial Intelligence , volume=

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=. 2026 , doi=

2026
[97]

2026 , archivePrefix=

Classification of Non-redundancy of Boolean Predicates of Arity 4 , author=. 2026 , archivePrefix=

2026
[98]

Whiston, Julius , TITLE =. J. Algebra , FJOURNAL =. 2000 , NUMBER =. doi:10.1006/jabr.2000.8399 , URL =

2000
[99]

Valued Constraint Satisfaction Problems: Hard and Easy Problems , booktitle =

Thomas Schiex and H. Valued Constraint Satisfaction Problems: Hard and Easy Problems , booktitle =. 1995 , url =

1995
[100]

1965 , publisher=

Analytic Functions of Several Complex Variables , author=. 1965 , publisher=

1965
[101]

Morampudi and Chris R

Or Sattath and Siddhardh C. Morampudi and Chris R. Laumann and Roderich Moessner , title =. Proceedings of the National Academy of Sciences , volume =. 2016 , doi =

2016
[102]

Communications in Mathematical Physics , volume=

Stability of frustration-free Hamiltonians , author=. Communications in Mathematical Physics , volume=. 2013 , publisher=

2013
[103]

Quantum Hamiltonian complexity and the detectability lemma , author=
[104]

Cross disciplinary advances in quantum computing , SERIES =

Bravyi, Sergey , TITLE =. Cross disciplinary advances in quantum computing , SERIES =. 2011 , ISBN =. doi:10.1090/conm/536/10552 , URL =

2011 doi
[105]

Niel de Beaudrap and Sevag Gharibian , editor =

J. Niel de Beaudrap and Sevag Gharibian , editor =. A Linear Time Algorithm for Quantum 2-SAT , booktitle =. 2016 , url =. doi:10.4230/LIPIcs.CCC.2016.27 , timestamp =

2016 doi
[106]

2016 , url =

David Gosset and Daniel Nagaj , title =. 2016 , url =. doi:10.1137/140957056 , timestamp =

2016 doi
[107]

Quantum Inf

Stephen Piddock and Ashley Montanaro , title =. Quantum Inf. Comput. , volume =. 2017 , url =. doi:10.26421/QIC17.7-8-6 , timestamp =

2017 doi
[108]

Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality , booktitle =

Yeongwoo Hwang and Joe Neeman and Ojas Parekh and Kevin Thompson and John Wright , editor =. Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality , booktitle =. 2023 , url =. doi:10.1137/1.9781611977554.ch48 , timestamp =

2023 doi
[109]

CoRR , volume =

Stephen Piddock , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2510.07995 , eprinttype =

2025 doi
[110]

Cubitt and Ashley Montanaro , title =

Toby S. Cubitt and Ashley Montanaro , title =. 2016 , url =. doi:10.1137/140998287 , timestamp =

2016 doi
[111]

Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut , booktitle =

Sevag Gharibian and Ojas Parekh , editor =. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut , booktitle =. 2019 , url =. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.31 , timestamp =

2019 doi
[112]

CoRR , volume =

Ojas Parekh and Kevin Thompson , title =. CoRR , volume =. 2022 , url =. doi:10.48550/arXiv.2206.08342 , eprinttype =. 2206.08342 , archivePrefix =

2022 doi
[113]

33rd International Symposium on Algorithms and Computation (

Eunou Lee , title =. 33rd International Symposium on Algorithms and Computation (. 2022 , url =

2022
[114]

Quantum , volume =

Robbie King , title =. Quantum , volume =. 2023 , url =. doi:10.22331/q-2023-11-09-1180 , eprinttype =. 2209.02589 , archivePrefix =

2023 arXiv
[115]

51st International Colloquium on Automata, Languages, and Programming (

Eunou Lee and Ojas Parekh , title =. 51st International Colloquium on Automata, Languages, and Programming (. 2024 , url =

2024
[116]

CoRR , volume =

Felix Huber and Kevin Thompson and Ojas Parekh and Sevag Gharibian , title =. CoRR , volume =. 2024 , url =. doi:10.48550/arXiv.2411.04120 , eprinttype =. 2411.04120 , archivePrefix =

2024 doi arXiv
[117]

CoRR , volume =

Zackary Jorquera and Alexandra Kolla and Steven Kordonowy and Juspreet Singh Sandhu and Stuart Wayland , title =. CoRR , volume =. 2024 , url =. doi:10.48550/arXiv.2410.15544 , eprinttype =. 2410.15544 , archivePrefix =

2024 doi arXiv
[118]

CoRR , volume =

Nathan Ju and Ansh Nagda , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2504.10712 , eprinttype =. 2504.10712 , archivePrefix =

2025 doi arXiv
[119]

CoRR , volume =

Sander Gribling and Lennart Sinjorgo and Renata Sotirov , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2504.11120 , eprinttype =. 2504.11120 , archivePrefix =

2025 doi arXiv
[120]

33rd Annual European Symposium on Algorithms (

Anuj Apte and Eunou Lee and Kunal Marwaha and Ojas Parekh and James Sud , title =. 33rd Annual European Symposium on Algorithms (. 2025 , url =

2025
[121]

CoRR , volume =

Anuj Apte and Eunou Lee and Kunal Marwaha and Ojas Parekh and Lennart Sinjorgo and James Sud , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2512.09896 , eprinttype =. 2512.09896 , archivePrefix =

2025 doi
[122]

ArXiv , year=

Conjectured Bounds for 2-Local Hamiltonians via Token Graphs , author=. ArXiv , year=
[123]

Brouwer and Willem H

Andries E. Brouwer and Willem H. Haemers , title =. 2012 , doi =

2012
[124]

Haemers and Ali Mohammadian and Behruz Tayfeh-Rezaie , title =

Willem H. Haemers and Ali Mohammadian and Behruz Tayfeh-Rezaie , title =. Linear Algebra and its Applications , volume =. 2010 , doi =

2010
[125]

arXiv preprint arXiv:2601.17575 , year=

An Approximate Version of Brouwer's Laplacian Conjecture , author=. arXiv preprint arXiv:2601.17575 , year=. doi:10.48550/arXiv.2601.17575 , url=. 2601.17575 , archivePrefix=

doi
[126]

and Morley, Thomas D

Anderson, Jr., William N. and Morley, Thomas D. , TITLE =. Linear and Multilinear Algebra , FJOURNAL =. 1985 , NUMBER =. doi:10.1080/03081088508817681 , URL =

1985 doi
[127]

2010 , note =

Godsil, Chris , title =. 2010 , note =

2010
[128]

An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube , volume=

Filmus, Yuval , year=. An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube , volume=. The Electronic Journal of Combinatorics , publisher=. doi:10.37236/4567 , number=

doi
[129]

2015 , isbn =

Meka, Raghu and Potechin, Aaron and Wigderson, Avi , title =. 2015 , isbn =. doi:10.1145/2746539.2746600 , booktitle =

2015
[130]

, title =

Grigoriev, D. , title =. computational complexity , year =. doi:10.1007/s00037-001-8192-0 , url =

doi
[131]

Czechoslovak Math

Fiedler, Miroslav , TITLE =. Czechoslovak Math. J. , FJOURNAL =. 1974 , PAGES =

1974
[132]

and Olkin, Ingram and Arnold, Barry C

Marshall, Albert W. and Olkin, Ingram and Arnold, Barry C. , TITLE =. 2011 , PAGES =. doi:10.1007/978-0-387-68276-1 , URL =

2011 doi
[133]

Gordon , title =

Robert D. Gordon , title =. The Annals of Mathematical Statistics , volume =. 1941 , doi =

1941
[134]

arXiv preprint arXiv:2607.14087 , year =

Abhijeet Mulgund , title =. arXiv preprint arXiv:2607.14087 , year =. 2607.14087 , archivePrefix =

arXiv
[135]

International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=

Approximation Algorithm for Non-boolean MAX k-CSP , author=. International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=. 2012 , organization=

2012
[136]

Algorithmica , volume=

Parallel approximation algorithms by positive linear programming , author=. Algorithmica , volume=. 1998 , publisher=

1998
[137]

2017 , organization=

Approximation algorithms for CSPs , author=. 2017 , organization=

2017
[138]

ACM Transactions on Algorithms (TALG) , volume=

Near-optimal algorithms for maximum constraint satisfaction problems , author=. ACM Transactions on Algorithms (TALG) , volume=. 2009 , publisher=

2009
[139]

Computational Complexity , volume=

Approximation resistant predicates from pairwise independence , author=. Computational Complexity , volume=. 2009 , publisher=

2009
[140]

Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing , pages=

Gowers uniformity, influence of variables, and PCPs , author=. Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing , pages=
[141]

ACM Transactions on Computation Theory (TOCT) , volume=

Explicit Optimal hardness via Gaussian stability results , author=. ACM Transactions on Computation Theory (TOCT) , volume=. 2013 , publisher=

2013
[142]

Journal of the ACM (JACM) , volume=

Approximation resistance from pairwise-independent subgroups , author=. Journal of the ACM (JACM) , volume=. 2016 , publisher=

2016
[143]

Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages=

On the power of unique 2-prover 1-round games , author=. Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages=
[144]

Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

Optimal algorithms and inapproximability results for every CSP? , author=. Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=
[145]

Journal of the ACM (JACM) , volume=

Proof verification and the hardness of approximation problems , author=. Journal of the ACM (JACM) , volume=. 1998 , publisher=

1998
[146]

Journal of the ACM (JACM) , volume=

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming , author=. Journal of the ACM (JACM) , volume=. 1995 , publisher=

1995
[147]

Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science , pages =

Boaz Barak and Prasad Raghavendra and David Steurer , title =. Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science , pages =. 2011 , doi =

2011
[148]

Proceedings of the 2020 ACM--SIAM Symposium on Discrete Algorithms , pages =

Vedat Levi Alev and Fernando Granha Jeronimo and Dylan Quintana and Shashank Srivastava and Madhur Tulsiani , title =. Proceedings of the 2020 ACM--SIAM Symposium on Discrete Algorithms , pages =. 2020 , doi =

2020
[149]

Proceedings of the 29th Conference on Learning Theory , series =

Andrej Risteski , title =. Proceedings of the 29th Conference on Learning Theory , series =. 2016 , url =

2016
[150]

Proceedings of the 51st Annual ACM Symposium on Theory of Computing , pages =

Vishesh Jain and Frederic Koehler and Andrej Risteski , title =. Proceedings of the 51st Annual ACM Symposium on Theory of Computing , pages =. 2019 , doi =

2019
[151]

Hopkins and Silvio Lattanzi , title =

Ainesh Bakshi and Vincent Cohen-Addad and Rajesh Jayaram and Samuel B. Hopkins and Silvio Lattanzi , title =. Proceedings of the 38th Conference on Learning Theory , series =. 2025 , url =

2025
[152]

Hopkins , title =

Prashanti Anderson and Ainesh Bakshi and Samuel B. Hopkins , title =. Proceedings of the 2026 Annual ACM--SIAM Symposium on Discrete Algorithms , pages =. 2026 , doi =

2026
[153]

Fernando G. S. L. Brand. Quantum de Finetti Theorems under Local Measurements with Applications , journal =. 2017 , doi =

2017
[154]

Fernando G. S. L. Brand. Product-State Approximations to Quantum States , journal =. 2016 , doi =

2016
[155]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages =

Ainesh Bakshi and John Bostanci and William Kretschmer and Zeph Landau and Jerry Li and Allen Liu and Ryan O'Donnell and Ewin Tang , title =. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages =. 2025 , doi =

2025
[156]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages =

Ainesh Bakshi and Allen Liu and Ankur Moitra and Ewin Tang , title =. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages =. 2024 , doi =

2024

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

Physical Review A , volume=

Good quantum error-correcting codes exist , author=. Physical Review A , volume=. 1996 , publisher=

1996

[2] [2]

Proceedings of the Royal Society of London

Multiple-particle interference and quantum error correction , author=. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences , volume=. 1996 , publisher=

1996

[3] [3]

2011 ieee 52nd annual symposium on foundations of computer science , pages=

Rounding semidefinite programming hierarchies via global correlation , author=. 2011 ieee 52nd annual symposium on foundations of computer science , pages=. 2011 , organization=

2011

[4] [5]

2002 , PAGES =

Lang, Serge , TITLE =. 2002 , PAGES =. doi:10.1007/978-1-4613-0041-0 , URL =

doi:10.1007/978-1-4613-0041-0 2002

[5] [6]

Hamiltonian Sparsification and Gap-Simulation , booktitle =

Dorit Aharonov and Leo Zhou , editor =. Hamiltonian Sparsification and Gap-Simulation , booktitle =. 2019 , url =. doi:10.4230/LIPIcs.ITCS.2019.2 , timestamp =

doi:10.4230/lipics.itcs.2019.2 2019

[6] [7]

doi:10.22331/q-2019-09-30-189 , url =

The complexity of simulating local measurements on quantum systems , author =. doi:10.22331/q-2019-09-30-189 , url =

doi:10.22331/q-2019-09-30-189 2019

[7] [8]

Annales Henri Poincar

Translationally Invariant Universal Quantum Hamiltonians in 1D , author=. Annales Henri Poincar. 2020 , volume=

2020

[8] [9]

48th International Colloquium on Automata, Languages, and Programming (

Ojas Parekh and Kevin Thompson , title =. 48th International Colloquium on Automata, Languages, and Programming (. 2021 , url =

2021