Cover Image

On Approximability of Satisfiable k-CSPs: IV

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhangale, Amey, Khot, Subhash, Minzer, Dor
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Approximability of Satisfiable $k$-CSPs: VI
by: Bhangale, Amey, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
by: Bhangale, Amey, et al.
Published: (2024)

On Approximability of Satisfiable k-CSPs: V
by: Bhangale, Amey, et al.
Published: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
by: Bhangale, Amey, et al.
Published: (2024)

Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$
by: Bhangale, Amey, et al.
Published: (2023)

An Invariance Principle for the Multi-slice, with Applications
by: Braverman, Mark, et al.
Published: (2021)

Parallel Repetition for $3$-Player XOR Games
by: Bhangale, Amey, et al.
Published: (2024)

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

The Lens of Abelian Embeddings
by: Minzer, Dor
Published: (2026)

Constant Degree Direct Product Testers with Small Soundness
by: Bafna, Mitali, et al.
Published: (2024)

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

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
by: S., Karthik C., et al.
Published: (2021)

A Distance Amplification Lemma for Monotonicity
by: Minzer, Dor
Published: (2025)

Optimal Inapproximability of Generalized Linear Equations over a Finite Group
by: Bhangale, Amey, et al.
Published: (2026)

Characterizing Direct Product Testing via Coboundary Expansion
by: Bafna, Mitali, et al.
Published: (2023)

Restricted CSPs and F-free Digraph Algorithmics
by: Guzmán-Pro, Santiago, et al.
Published: (2025)

Biased Linearity Testing in the 1% Regime
by: Khot, Subhash, et al.
Published: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

Quasi-Linear Size PCPs with Small Soundness from HDX
by: Bafna, Mitali, et al.
Published: (2024)

Improved Round-by-round Soundness IOPs via Reed-Muller Codes
by: Minzer, Dor, et al.
Published: (2025)

Satisfiability of commutative vs. non-commutative CSPs
by: Bulatov, Andrei A., et al.
Published: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

$C_{2k+1}$-coloring of bounded-diameter graphs
by: Piecyk, Marta
Published: (2024)

Approximately counting maximal independent set is equivalent to #SAT
by: Zhang, Hao, et al.
Published: (2024)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
by: Han, Zicheng, et al.
Published: (2026)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
by: Gur, Tom, et al.
Published: (2025)

Approximation algorithms for noncommutative CSPs
by: Culf, Eric, et al.
Published: (2023)

Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
by: Hodur, Nadzieja, et al.
Published: (2025)

Deriving differential approximation results for $k\,$CSPs from combinatorial designs
by: Culus, Jean-François, et al.
Published: (2024)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
by: Dinur, Itai, et al.
Published: (2021)

Atropos-k is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

Approximate cycle double cover
by: Ghanbari, Babak, et al.
Published: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

On the satisfiability of random $3$-SAT formulas with $k$-wise independent clauses
by: Caragiannis, Ioannis, et al.
Published: (2024)

Product Mixing in Compact Lie Groups
by: Ellis, David, et al.
Published: (2024)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)