Buchumschlag

Sketching approximability of all finite CSPs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chou, Chi-Ning, Golovnev, Alexander, Sudan, Madhu, Velusamy, Santhoshini
Format:	Preprint
Veröffentlicht:	2021
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Linear Space Streaming Lower Bounds for Approximating CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

Sketching approximations and LP approximations for finite CSPs are related
von: Singer, Noah G., et al.
Veröffentlicht: (2025)

Streaming approximation resistance of every ordering CSP
von: Singer, Noah G., et al.
Veröffentlicht: (2021)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Algebra in Algorithmic Coding Theory
von: Sudan, Madhu
Veröffentlicht: (2025)

Low-Degree Testing Over Grids
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2023)

Improved PIR Schemes using Matching Vectors and Derivatives
von: Ghasemi, Fatemeh, et al.
Veröffentlicht: (2024)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
von: Błasiok, Jarosław, et al.
Veröffentlicht: (2026)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2025)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
von: Singer, Noah G.
Veröffentlicht: (2025)

Local Correction of Linear Functions over the Boolean Cube
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2024)

Low Degree Local Correction Over the Boolean Cube
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable k-CSPs: V
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

Ideals, Macaulay Bases, and PCPs
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2025)

On Approximability of Satisfiable $k$-CSPs: VI
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable k-CSPs: IV
von: Bhangale, Amey, et al.
Veröffentlicht: (2023)

Communication with Imperfectly Shared Randomness
von: Canonne, Clément L., et al.
Veröffentlicht: (2014)

CSPs with Few Alien Constraints
von: Jonsson, Peter, et al.
Veröffentlicht: (2024)

Approximation algorithms for noncommutative CSPs
von: Culf, Eric, et al.
Veröffentlicht: (2023)

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
von: Velusamy, Santhoshini
Veröffentlicht: (2025)

Hilbert Functions and Low-Degree Randomness Extractors
von: Golovnev, Alexander, et al.
Veröffentlicht: (2024)

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

Online Orthogonal Vectors Revisited
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2026)

Satisfiability of commutative vs. non-commutative CSPs
von: Bulatov, Andrei A., et al.
Veröffentlicht: (2024)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

Existence and nonexistence of commutativity gadgets for entangled CSPs
von: Culf, Eric, et al.
Veröffentlicht: (2025)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
von: Saxena, Raghuvansh R., et al.
Veröffentlicht: (2024)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
von: Fei, Yumou
Veröffentlicht: (2025)

Restricted CSPs and F-free Digraph Algorithmics
von: Guzmán-Pro, Santiago, et al.
Veröffentlicht: (2025)

Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2025)

An order out of nowhere: a new algorithm for infinite-domain CSPs
von: Mottet, Antoine, et al.
Veröffentlicht: (2023)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
von: Jonsson, Peter, et al.
Veröffentlicht: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2026)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
von: Fritsch, Timo, et al.
Veröffentlicht: (2026)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
von: Kim, Eun Jung, et al.
Veröffentlicht: (2022)