Cover Image

Strongly Refuting Random CSP without Literals

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chan, Siu On, d'Orsi, Tommaso, Xu, Jeff
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Finding Randomly Planted Cliques in Arbitrary Graphs
by: Agrimonti, Francesco, et al.
Published: (2025)

Max-Cut with $ε$-Accurate Predictions
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
by: Guruswami, Venkatesan, et al.
Published: (2025)

Private graphon estimation via sum-of-squares
by: Chen, Hongjie, et al.
Published: (2024)

Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
by: Xu, Jeff
Published: (2024)

Refuting approaches to the log-rank conjecture for XOR functions
by: Hatami, Hamed, et al.
Published: (2023)

Refuting Perfect Matchings in Spectral Expanders is Hard
by: Biswas, Ari, et al.
Published: (2025)

Near Optimal Hardness of Approximating $k$-CSP
by: Minzer, Dor, et al.
Published: (2025)

Baby PIH: Parameterized Inapproximability of Min CSP
by: Guruswami, Venkatesan, et al.
Published: (2023)

Proof complexity of Mal'tsev CSP
by: Gaysin, Azza
Published: (2025)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
by: Mackenzie, Simon, et al.
Published: (2024)

Dichotomies for \#CSP on graphs that forbid a clique as a minor
by: Meng, Boning, et al.
Published: (2025)

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
by: Bhangale, Amey, et al.
Published: (2025)

Modular Counting CSP: Reductions and Algorithms
by: Kazeminia, Amirhossein, et al.
Published: (2025)

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
by: Guruswami, Venkatesan, et al.
Published: (2024)

The Richness of CSP Non-redundancy
by: Brakensiek, Joshua, et al.
Published: (2025)

Streaming approximation resistance of every ordering CSP
by: Singer, Noah G., et al.
Published: (2021)

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
by: Barto, Libor, et al.
Published: (2021)

On Purely Private Covariance Estimation
by: d'Orsi, Tommaso, et al.
Published: (2025)

Tight Differentially Private PCA via Matrix Coherence
by: d'Orsi, Tommaso, et al.
Published: (2025)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
by: Chukhin, Nikolai, et al.
Published: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
by: Zhuk, Dmitriy
Published: (2024)

Qualidade da atenção ao parto em maternidades do Rio de Janeiro
by: Eleonora d’Orsi
Published: (2005)

Trabalho, suporte social e lazer protegem idosos da perda funcional: estudo epidoso
by: Eleonora d'Orsi
Published: (2011)

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
by: Kátay, Tamás, et al.
Published: (2023)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

Classical Simulation of Quantum CSP Strategies
by: Banakh, Demian, et al.
Published: (2025)

Quantum Advantage and CSP Complexity
by: Ciardo, Lorenzo
Published: (2024)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
by: Kothari, Pravesh K., et al.
Published: (2025)

A Strong Direct Sum Theorem for Distributional Query Complexity
by: Blanc, Guy, et al.
Published: (2024)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
by: Riazanov, Artur, et al.
Published: (2025)

Random Permutations in Computational Complexity
by: Hitchcock, John M., et al.
Published: (2025)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2023)

Infiltrações intralesionais de 5-FU no tratamento de queloides, cicatrizes hipertróficas e contraturas
by: Leandra d'Orsi Metsavaht
Published: (2015)

Hidroquinona: vilã ou heroína?
by: Leandra d’Orsi Metsavaht
Published: (2017)

Queimaduras e suas cicatrizes
by: Leandra d’Orsi Metsavaht
Published: (2017)

The Randomness Deficiency Function and the Shift Operator
by: Epstein, Samuel
Published: (2023)