Copertina

Redundancy Is All You Need (for CSP Sparsification)

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Brakensiek, Joshua, Guruswami, Venkatesan
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Discrete Mathematics Information Theory Logic in Computer Science Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

SDPs and Robust Satisfiability of Promise CSP
di: Brakensiek, Joshua, et al.
Pubblicazione: (2022)

Tight Bounds for Sparsifying Random CSPs
di: Brakensiek, Joshua, et al.
Pubblicazione: (2025)

Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

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

Elementary first-order model checking for sparse graphs
di: Gajarský, Jakub, et al.
Pubblicazione: (2024)

On merge-models
di: Buffière, Hector, et al.
Pubblicazione: (2026)

CNFs and DNFs with Exactly $k$ Solutions
di: Chandran, L. Sunil, et al.
Pubblicazione: (2025)

Flipper games for monadically stable graph classes
di: Gajarský, Jakub, et al.
Pubblicazione: (2023)

Merge-width and First-Order Model Checking
di: Dreier, Jan, et al.
Pubblicazione: (2025)

Graph classes through the lens of logic
di: Pilipczuk, Michał
Pubblicazione: (2025)

Exponential Time Approximation for Coloring 3-Colorable Graphs
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

Palette Sparsification for Graphs with Sparse Neighborhoods
di: Dhawan, Abhishek
Pubblicazione: (2024)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
di: Lyon, Tim S., et al.
Pubblicazione: (2023)

Construction of orientable sequences in $O(1)$-amortized time per bit
di: Gabric, Daniel, et al.
Pubblicazione: (2024)

On constrained intersection representations of graphs and digraphs
di: Cicalese, Ferdinando, et al.
Pubblicazione: (2025)

Color Refinement for Relational Structures
di: Scheidt, Benjamin, et al.
Pubblicazione: (2024)

On classes of bounded tree rank, their interpretations, and efficient sparsification
di: Gajarský, Jakub, et al.
Pubblicazione: (2024)

Formal Primal-Dual Algorithm Analysis
di: Abdulaziz, Mohammad, et al.
Pubblicazione: (2026)

The Iteration Number of the Weisfeiler-Leman Algorithm
di: Grohe, Martin, et al.
Pubblicazione: (2023)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
di: Grohe, Martin, et al.
Pubblicazione: (2023)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
di: Koh, Zhuan Khye, et al.
Pubblicazione: (2021)

Solving Partial Dominating Set and Related Problems Using Twin-Width
di: Balabán, Jakub, et al.
Pubblicazione: (2025)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
di: Majewski, Konrad, et al.
Pubblicazione: (2021)

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

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
di: Bedert, Benjamin, et al.
Pubblicazione: (2025)

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
di: Bhattacharya, Sudatta, et al.
Pubblicazione: (2025)

A Method for Generating Connected Erdos-Renyi Random Graphs
di: Chinyaev, Boris
Pubblicazione: (2025)

Six Candidates Suffice to Win a Voter Majority
di: Charikar, Moses, et al.
Pubblicazione: (2024)

A Unified Model of Congestion Games with Priorities: Two-Sided Markets with Ties, Finite and Non-Affine Delay Functions, and Pure Nash Equilibria
di: Takazawa, Kenjiro
Pubblicazione: (2024)

The Popular Dimension of Matchings
di: Connor, Frank, et al.
Pubblicazione: (2025)

Approximately Dominating Sets in Elections
di: Charikar, Moses, et al.
Pubblicazione: (2025)

Stationary Online Contention Resolution Schemes
di: Aminian, Mohammad Reza, et al.
Pubblicazione: (2026)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
di: Černý, Marek, et al.
Pubblicazione: (2025)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
di: Černý, Marek
Pubblicazione: (2026)

Smaller Circuits for Bit Addition
di: Goncharov, Mikhail, et al.
Pubblicazione: (2025)

SAT Encoding of Partial Ordering Models for Graph Coloring Problems
di: Faber, Daniel, et al.
Pubblicazione: (2024)

Combinatorial Bernoulli Factories
di: Niazadeh, Rad, et al.
Pubblicazione: (2020)

Additive Sparsification of CSPs
di: Pelleg, Eden, et al.
Pubblicazione: (2021)

A Faster Isomorphism Test for Graphs of Small Degree
di: Grohe, Martin, et al.
Pubblicazione: (2018)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
di: Bencs, Ferenc, et al.
Pubblicazione: (2024)