Pith. sign in

REVIEW 5 minor 76 references

Random ordering CSPs can be strongly refuted in polynomial time once the number of clauses exceeds roughly n to the power d/2 over epsilon squared, where d is the predicate's coordinate degree.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-13 03:12 UTC pith:Z6LUBAQF

load-bearing objection Solid first treatment of strong refutation for random ordering CSPs, with a clean Kikuchi adaptation and a properly conditional matching lower bound.

arxiv 2607.09410 v1 pith:Z6LUBAQF submitted 2026-07-10 cs.DS cs.CC

Strong Refutation of Random Ordering CSPs

Xifan Yu This is my paper
classification cs.DS cs.CC MSC 68Q2568Q1768W2005C80
keywords ordering CSPstrong refutationKikuchi methodcoordinate degreelow-degree algorithmsrandom CSPsspectral algorithmsaverage-case complexity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper starts the study of strong refutation for random ordering constraint satisfaction problems: given a random collection of local ordering constraints on n variables, efficiently certify that no global ordering satisfies much more than a random assignment would. It proves that a polynomial-time algorithm achieves an epsilon-refutation once the expected number of clauses is at least about n^{d/2}/epsilon squared, with d equal to the coordinate degree of the predicate. Using the Kikuchi method after a rank decomposition that handles the non-product domain of permutations, the work also supplies a smooth three-way tradeoff among running time, clause density, and refutation strength. A matching lower bound against low-coordinate-degree algorithms, conditional on a generalized low-degree conjecture, indicates that the tradeoff is nearly optimal. The result extends the well-studied theory of CSP refutation to ordering CSPs that arise in ranking, scheduling, and acyclic-subgraph problems.

Core claim

For any non-trivial ordering predicate P of coordinate degree d there is a polynomial-time epsilon-refutation algorithm for a p-random k-OCSP once the expected number of clauses satisfies m greater than or equal to tilde-Omega of n to the d/2 over epsilon squared; more generally a Kikuchi-matrix algorithm of level ell runs in time n to the O(ell) and refutes above a density that interpolates smoothly between that spectral threshold and denser regimes.

What carries the argument

The Kikuchi matrix built from a centered occurrence-count tensor after a parity-encoding rank decomposition that expresses every canonical ordering predicate as a linear combination of rank-1 tensors over plus-or-minus-1 vectors; spectral-norm bounds on these matrices certify that no assignment (and therefore no ordering) can exceed the average value by more than epsilon.

Load-bearing premise

The matching computational lower bound rests on the conjecture that bounded advantage for low-coordinate-degree functions already rules out any algorithm running in time exponential in the degree over a polylog factor.

What would settle it

Exhibit either a polynomial-time epsilon-refutation algorithm that succeeds at clause density o of n to the d/2 over epsilon squared for some fixed predicate of coordinate degree d, or a low-coordinate-degree test that strongly separates the quiet-planted distribution from the null below that density.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Polynomial-time strong refutation becomes available for random maximum-acyclic-subgraph and higher-order rank-aggregation instances once the edge or hyperedge density crosses the coordinate-degree threshold.
  • The three-way tradeoff supplies sub-exponential algorithms that still refute below the pure spectral density, exactly as in classical CSP refutation.
  • Any future unconditional hardness for ordering-CSP refutation must either break the low-coordinate-degree barrier or exploit structure outside the quiet-planting construction used here.
  • The bucketing reduction shows that constant-epsilon refutation of ordering CSPs is essentially no harder than ordinary CSP refutation over a constant-size alphabet.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same rank-decomposition-plus-Kikuchi pipeline should apply, with only cosmetic changes, to other non-product domains such as partial orders or tournament graphs.
  • If the generalized low-degree conjecture is later restricted to a narrower class of 'nice' planted distributions, the quiet planting used here will remain inside that class because it is permutation-invariant and product-conditional.
  • Coordinate degree, rather than arity, is likely the right complexity parameter for any average-case ordering problem whose value function admits an Efron-Stein expansion.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper initiates the study of strong refutation for random ordering CSPs (OCSPs). For a non-trivial ordering predicate P of coordinate degree d, it proves a polynomial-time ε-refutation algorithm for p-random k-OCSP once the expected number of clauses satisfies m ≥ Õ(n^{d/2}/ε^{2}). A smooth three-way tradeoff among running time n^{O(ℓ)}, clause density, and refutation strength is obtained via the Kikuchi method (Theorem 3.1); a black-box bucketing reduction removes the extra polylog factors when ε is constant (Theorem 3.3). Matching computational lower bounds against algorithms of running time exp(O(D/polylog n)) are shown under the Generalized Low Degree Conjecture (Theorem 3.5), via a quiet-planting reduction to a hypothesis-testing problem whose low-coordinate-degree advantage is bounded below the same density threshold.

Significance. The work cleanly extends the mature theory of random CSP refutation (spectral algorithms, Kikuchi matrices, low-degree hardness) to the non-product domain of orderings. The key technical contributions—an Efron–Stein decomposition of ordering predicates into canonical predicates (Prop. 4.2–4.5), a parity-encoding rank decomposition that rewrites the canonical predicate as a linear combination of rank-1 tensors over {±1}^n (Lem. 4.7–4.10), and a careful transfer of Kikuchi spectral-norm bounds from CdX26—are self-contained and of independent interest. The resulting three-way tradeoff is essentially optimal under a standard average-case hardness assumption, and the paper correctly flags the known limitations of that assumption (Rem. 5.4). The results therefore constitute a solid, well-executed first step that should be of lasting value to the average-case complexity and approximation-algorithms communities.

minor comments (5)
  1. The abstract and introduction use “Õ” and “Ω̃” interchangeably for the same polylog-hiding notation; a single consistent convention would improve readability.
  2. In Definition 4.9 the centered occurrence tensor F is written with a slightly different centering term than the corresponding tensor in CdX26; while Remark 4.17 correctly notes that the difference is only a constant factor for fixed k, an explicit sentence equating the two normalizations would prevent confusion for readers who consult both papers.
  3. Lemma 4.8 bounds ∑|C_Γ| ≤ L^{t-1}. The subsequent applications (e.g., the even-t case of the proof of Theorem 3.1) absorb this factor into the polylog; a short remark that the bound is tight up to constants would be helpful.
  4. The statement of Conjecture 5.3 is labelled “informal”; given that the hardness theorem rests on it, a pointer to the precise formalization in Hop18 or Kun25 would make the dependence clearer.
  5. A few typographical slips appear: “occurence” (Def. 4.9), “Erdős-Rényi” inconsistently accented, and an occasional missing space after punctuation. None affect correctness.

Circularity Check

0 steps flagged

No significant circularity; thresholds follow from independent spectral reductions and an external conditional conjecture.

full rationale

The paper's central algorithmic claims (Theorems 3.1 and 3.3) are obtained by a transparent, self-contained chain: Efron–Stein decomposition of an arbitrary ordering predicate into a linear combination of canonical predicates (Proposition 4.2 and 4.5), a parity-encoding rank decomposition that rewrites each canonical predicate as a sum of rank-1 tensors over {±1}^n (Lemmas 4.7–4.10), and standard Kikuchi spectral-norm / Frobenius-norm bounds imported from the external reference CdX26 (Theorems 4.16–4.18). None of these steps defines a quantity in terms of the target density, fits a free parameter to data, or relies on a self-citation for a uniqueness or existence claim. The matching lower bound (Theorem 3.5) is explicitly conditional on the Generalized Low Degree Conjecture (Conjecture 5.3), which is treated as an external heuristic; the paper itself flags (Remark 5.4) that a related version is already false, so the hardness statement is correctly presented as conditional evidence rather than a derived theorem. No fitted inputs, self-referential normalizations, or load-bearing self-citations appear. The derivation is therefore free of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 2 invented entities

The algorithmic results rest only on standard concentration inequalities and the spectral analysis of Kikuchi matrices already proved for Boolean CSPs. The hardness result additionally invokes the Generalized Low Degree Conjecture. No free parameters are fitted; the only new conceptual objects are the coordinate degree of an ordering predicate and the parity-encoding rank decomposition.

axioms (3)
  • domain assumption Generalized Low Degree Conjecture (Conjecture 5.3): bounded Adv_{≤D}(P,Q) implies no exp(O(D/polylog n))-time strong detection for “sufficiently nice” product-null hypothesis-testing problems.
    Invoked only for the lower bound (Theorem 3.5); the algorithmic upper bounds are unconditional.
  • standard math Matrix Bernstein and Bernstein concentration inequalities (Theorems 2.1–2.2).
    Used throughout the spectral-norm and value-concentration arguments.
  • standard math Efron-Stein decomposition orthogonality and coordinate-degree facts (Fact 2.1, Definition 2.11).
    Standard functional analysis on product spaces; applied to rewrite ordering predicates.
invented entities (2)
  • Coordinate degree D(P) of an ordering predicate independent evidence
    purpose: Determines the critical density n^{D(P)/2} for both algorithms and lower bounds.
    Defined via the highest non-zero Efron-Stein component of the lift of P to [0,1]^k; natural but first used systematically for OCSP refutation.
  • Parity-encoding rank decomposition of canonical ordering predicates (Lemma 4.7) independent evidence
    purpose: Expresses the non-product ordering indicator as a linear combination of rank-1 ±1 tensors so that Kikuchi matrices apply.
    New technical device; the paper notes it was found with ChatGPT assistance. Independent of the hardness conjecture.

pith-pipeline@v1.1.0-grok45 · 53473 in / 2661 out tokens · 32175 ms · 2026-07-13T03:12:43.116711+00:00 · methodology

0 comments
read the original abstract

In this work, we initiate the study of strongly refuting the satisfiability of random ordering constraint satisfaction problems. We show that there is a polynomial-time $\varepsilon$-refutation algorithm for random ordering CSP with predicate $P$ when the number of clauses is above the threshold $\tilde{\Omega}\left(n^{d/2}/\varepsilon^2\right)$, where $d$ is the coordinate degree of the predicate $P$. We further give a smooth three-way tradeoff between the running time, the clause density, and the refutation strength $\varepsilon$ using the Kikuchi method. Finally, we complement our algorithmic results with a computational lower bound based on the class of low coordinate degree algorithms, providing evidence that the established three-way tradeoff is near optimal.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

76 extracted references · 6 linked inside Pith

  1. [1]

    Public-key cryptography from different assumptions

    Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 171--180, 2010

    2010

  2. [2]

    A near-cubic lower bound for 3-query locally decodable codes from semirandom csp refutation

    Omar Alrabiah, Venkatesan Guruswami, Pravesh K Kothari, and Peter Manohar. A near-cubic lower bound for 3-query locally decodable codes from semirandom csp refutation. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1438--1448, 2023

    2023

  3. [3]

    How to refute a random csp

    Sarah R Allen, Ryan O'Donnell, and David Witmer. How to refute a random csp. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 689--708. IEEE, 2015

    2015

  4. [4]

    The threshold for random k-sat is 2k (ln 2-o (k))

    Dimitris Achlioptas and Yuval Peres. The threshold for random k-sat is 2k (ln 2-o (k)). In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages 223--231, 2003

    2003

  5. [5]

    Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs

    Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, and Alex Wein. Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs. In Conference on Learning Theory , pages 410--473. PMLR, 2021

    2021

  6. [7]

    Classifying the complexity of constraints using finite algebras

    Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. Classifying the complexity of constraints using finite algebras. SIAM journal on computing , 34(3):720--742, 2005

    2005

  7. [8]

    The complexity of temporal constraint satisfaction problems

    Manuel Bodirsky and Jan K \'a ra. The complexity of temporal constraint satisfaction problems. Journal of the ACM (JACM) , 57(2):1--41, 2010

    2010

  8. [10]

    A gap in average proof complexity

    Eli Ben-Sasson and Yonatan Bilu. A gap in average proof complexity. In Electronic Colloquium on Computational Complexity (ECCC) , volume 9, 2002

    2002

  9. [11]

    A dichotomy theorem for nonuniform csps

    Andrei A Bulatov. A dichotomy theorem for nonuniform csps. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 319--330. IEEE, 2017

    2017

  10. [13]

    From average case complexity to improper learning complexity

    Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. From average case complexity to improper learning complexity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages 441--448, 2014

    2014

  11. [14]

    Proof of the satisfiability conjecture for large k

    Jian Ding, Allan Sly, and Nike Sun. Proof of the satisfiability conjecture for large k. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages 59--68, 2015

    2015

  12. [16]

    Relations between average case complexity and approximation complexity

    Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages 534--543, 2002

    2002

  13. [17]

    Beating the random ordering is hard: Every ordering csp is approximation resistant

    Venkatesan Guruswami, Johan H stad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar. Beating the random ordering is hard: Every ordering csp is approximation resistant. SIAM Journal on Computing , 40(3):878--914, 2011

    2011

  14. [18]

    Algorithms and certificates for boolean csp refutation: smoothed is no harder than random

    Venkatesan Guruswami, Pravesh K Kothari, and Peter Manohar. Algorithms and certificates for boolean csp refutation: smoothed is no harder than random. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 678--689, 2022

    2022

  15. [19]

    On random ordering constraints

    Andreas Goerdt. On random ordering constraints. In International Computer Science Symposium in Russia , pages 105--116. Springer, 2009

    2009

  16. [20]

    Approximating bounded occurrence ordering csps

    Venkatesan Guruswami and Yuan Zhou. Approximating bounded occurrence ordering csps. In International Workshop on Approximation Algorithms for Combinatorial Optimization , pages 158--169. Springer, 2012

    2012

  17. [21]

    A simple and sharper proof of the hypergraph moore bound

    Jun-Ting Hsieh, Pravesh K Kothari, and Sidhanth Mohanty. A simple and sharper proof of the hypergraph moore bound. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2324--2344. SIAM, 2023

    2023

  18. [22]

    Statistical inference and the sum of squares method

    Samuel Hopkins. Statistical inference and the sum of squares method . Cornell University, 2018

    2018

  19. [23]

    On the complexity of k-sat

    Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences , 62(2):367--375, 2001

    2001

  20. [24]

    An exponential lower bound for linear 3-query locally correctable codes

    Pravesh K Kothari and Peter Manohar. An exponential lower bound for linear 3-query locally correctable codes. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 776--787, 2024

    2024

  21. [25]

    Exponential lower bounds for smooth 3-lccs and sharp bounds for designs

    Pravesh K Kothari and Peter Manohar. Exponential lower bounds for smooth 3-lccs and sharp bounds for designs. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1802--1845. IEEE, 2024

    2024

  22. [26]

    Sum of squares lower bounds for refuting any csp

    Pravesh K Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any csp. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 132--145, 2017

    2017

  23. [27]

    Statistical inference of a ranked community in a directed graph

    Dmitriy Kunisky, Daniel A Spielman, Alexander S Wein, and Xifan Yu. Statistical inference of a ranked community in a directed graph. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 2107--2117, 2025

    2025

  24. [28]

    Low coordinate degree algorithms i: Universality of computational thresholds for hypothesis testing

    Dmitriy Kunisky. Low coordinate degree algorithms i: Universality of computational thresholds for hypothesis testing. The Annals of Statistics , 53(2):774--801, 2025

    2025

  25. [29]

    Is planted coloring easier than planted clique? In The Thirty Sixth Annual Conference on Learning Theory , pages 5343--5372

    Pravesh Kothari, Santosh S Vempala, Alexander S Wein, and Jeff Xu. Is planted coloring easier than planted clique? In The Thirty Sixth Annual Conference on Learning Theory , pages 5343--5372. PMLR, 2023

    2023

  26. [30]

    Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio

    Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation) , pages 1--50. Springer, 2019

    2019

  27. [31]

    Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs

    Dmitriy Kunisky and Xifan Yu. Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1621--1633. IEEE, 2024

    2024

  28. [33]

    Approximation algorithms for satisfiable and nearly satisfiable ordering csps

    Yury Makarychev. Approximation algorithms for satisfiable and nearly satisfiable ordering csps. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages 1692--1703, 2026

    2026

  29. [34]

    Satisfiability of ordering csps above average is fixed-parameter tractable

    Konstantin Makarychev, Yury Makarychev, and Yuan Zhou. Satisfiability of ordering csps above average is fixed-parameter tractable. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 975--993. IEEE, 2015

    2015

  30. [35]

    Optimal algorithms and inapproximability results for every csp? In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 245--254, 2008

    Prasad Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 245--254, 2008

    2008

  31. [36]

    Strongly refuting random csps below the spectral threshold

    Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random csps below the spectral threshold. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 121--131, 2017

    2017

  32. [37]

    Streaming complexity of csps with randomly ordered constraints

    Raghuvansh R Saxena, Noah Singer, Madhu Sudan, and Santhoshini Velusamy. Streaming complexity of csps with randomly ordered constraints. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4083--4103. SIAM, 2023

    2023

  33. [39]

    The kikuchi hierarchy and tensor pca

    Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore. The kikuchi hierarchy and tensor pca. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1446--1468. IEEE, 2019

    2019

  34. [40]

    A proof of the csp dichotomy conjecture

    Dmitriy Zhuk. A proof of the csp dichotomy conjecture. Journal of the ACM (JACM) , 67(5):1--78, 2020

    2020

  35. [41]

    2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=

    Satisfiability of ordering CSPs above average is fixed-parameter tractable , author=. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=. 2015 , organization=

    2015

  36. [42]

    arXiv preprint arXiv:2604.27336 , year=

    Strongly Refuting Random CSP without Literals , author=. arXiv preprint arXiv:2604.27336 , year=

    Pith/arXiv arXiv

  37. [43]

    The Annals of Statistics , volume=

    Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing , author=. The Annals of Statistics , volume=. 2025 , publisher=

    2025

  38. [44]

    2014 , publisher=

    Analysis of boolean functions , author=. 2014 , publisher=

    2014

  39. [45]

    2018 , publisher=

    Statistical inference and the sum of squares method , author=. 2018 , publisher=

    2018

  40. [46]

    arXiv preprint arXiv:2505.17360 , year=

    The quasi-polynomial low-degree conjecture is false , author=. arXiv preprint arXiv:2505.17360 , year=

    Pith/arXiv arXiv

  41. [47]

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

    Strongly refuting random CSPs below the spectral threshold , author=. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  42. [48]

    2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    The Kikuchi hierarchy and tensor PCA , author=. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2019 , organization=

    2019

  43. [49]

    Conference on Learning Theory , pages=

    Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs , author=. Conference on Learning Theory , pages=. 2021 , organization=

    2021

  44. [50]

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

    A near-cubic lower bound for 3-query locally decodable codes from semirandom CSP refutation , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  45. [51]

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

    An exponential lower bound for linear 3-query locally correctable codes , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

  46. [52]

    2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Exponential lower bounds for smooth 3-lccs and sharp bounds for designs , author=. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2024 , organization=

    2024

  47. [53]

    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=

  48. [54]

    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 , organization=

    2023

  49. [55]

    2009 , publisher=

    Approximating np-hard problems efficient algorithms and their limits , author=. 2009 , publisher=

    2009

  50. [56]

    2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    A dichotomy theorem for nonuniform CSPs , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

    2017

  51. [57]

    Journal of the ACM (JACM) , volume=

    A proof of the CSP dichotomy conjecture , author=. Journal of the ACM (JACM) , volume=. 2020 , publisher=

    2020

  52. [58]

    SIAM journal on computing , volume=

    Classifying the complexity of constraints using finite algebras , author=. SIAM journal on computing , volume=. 2005 , publisher=

    2005

  53. [59]

    arXiv preprint arXiv:1210.1890 , year=

    Local search is better than random assignment for bounded occurrence ordering k-csps , author=. arXiv preprint arXiv:1210.1890 , year=

    Pith/arXiv arXiv

  54. [60]

    International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=

    Approximating bounded occurrence ordering CSPs , author=. International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=. 2012 , organization=

    2012

  55. [61]

    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=

  56. [62]

    Electronic Colloquium on Computational Complexity (ECCC) , volume=

    A gap in average proof complexity , author=. Electronic Colloquium on Computational Complexity (ECCC) , volume=

  57. [63]

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

    Relations between average case complexity and approximation complexity , author=. Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages=

  58. [64]

    Proceedings of the forty-second ACM symposium on Theory of computing , pages=

    Public-key cryptography from different assumptions , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=

  59. [65]

    Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages=

    The threshold for random k-sat is 2k (ln 2-o (k)) , author=. Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages=

  60. [66]

    Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

    From average case complexity to improper learning complexity , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

  61. [67]

    Journal of Computer and System Sciences , volume=

    On the complexity of k-SAT , author=. Journal of Computer and System Sciences , volume=. 2001 , publisher=

    2001

  62. [68]

    Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages=

    Proof of the satisfiability conjecture for large k , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages=

  63. [69]

    2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=

    How to refute a random CSP , author=. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=. 2015 , organization=

    2015

  64. [70]

    arXiv preprint arXiv:2204.10881 , year=

    A ihara-bass formula for non-boolean matrices and strong refutations of random csps , author=. arXiv preprint arXiv:2204.10881 , year=

    Pith/arXiv arXiv

  65. [71]

    SIAM Journal on Computing , volume=

    Beating the random ordering is hard: Every ordering CSP is approximation resistant , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  66. [72]

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

    Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs , author=. Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages=

  67. [73]

    Journal of the ACM (JACM) , volume=

    The complexity of temporal constraint satisfaction problems , author=. Journal of the ACM (JACM) , volume=. 2010 , publisher=

    2010

  68. [74]

    arXiv preprint arXiv:2105.01782 , year=

    Streaming approximation resistance of every ordering CSP , author=. arXiv preprint arXiv:2105.01782 , year=

    Pith/arXiv arXiv

  69. [75]

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

    Statistical inference of a ranked community in a directed graph , author=. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

  70. [76]

    International Computer Science Symposium in Russia , pages=

    On random ordering constraints , author=. International Computer Science Symposium in Russia , pages=. 2009 , organization=

    2009

  71. [77]

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

    Streaming complexity of CSPs with randomly ordered constraints , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  72. [78]

    arXiv preprint arXiv:0910.1191 , year=

    Sorting from noisy information , author=. arXiv preprint arXiv:0910.1191 , year=

    Pith/arXiv arXiv

  73. [79]

    The Thirty Sixth Annual Conference on Learning Theory , pages=

    Is planted coloring easier than planted clique? , author=. The Thirty Sixth Annual Conference on Learning Theory , pages=. 2023 , organization=

    2023

  74. [80]

    2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs , author=. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2024 , organization=

    2024

  75. [81]

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

    Sum of squares lower bounds for refuting any CSP , author=. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  76. [82]

    ISAAC Congress (International Society for Analysis, its Applications and Computation) , pages=

    Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio , author=. ISAAC Congress (International Society for Analysis, its Applications and Computation) , pages=. 2019 , organization=

    2019