Imagen de Portada

Strongly Refuting Random CSP without Literals

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Chan, Siu On, d'Orsi, Tommaso, Xu, Jeff
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

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

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

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

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

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

Proof complexity of Mal'tsev CSP
por: Gaysin, Azza
Publicado: (2025)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Quantum Advantage and CSP Complexity
por: Ciardo, Lorenzo
Publicado: (2024)

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

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

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

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

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

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

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

Queimaduras e suas cicatrizes
por: Leandra d’Orsi Metsavaht
Publicado: (2017)

The Randomness Deficiency Function and the Shift Operator
por: Epstein, Samuel
Publicado: (2023)