Imagen de Portada

SDPs and Robust Satisfiability of Promise CSP

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Brakensiek, Joshua, Guruswami, Venkatesan, Sandeep, Sai
Formato:	Preprint
Publicado:	2022
Materias:	Data Structures and Algorithms Discrete Mathematics Logic in Computer Science
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Redundancy Is All You Need (for CSP Sparsification)
por: Brakensiek, Joshua, et al.
Publicado: (2024)

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

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

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

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

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

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

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

Color Refinement for Relational Structures
por: Scheidt, Benjamin, et al.
Publicado: (2024)

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

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

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

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

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

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

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

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

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

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

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

Graph classes through the lens of logic
por: Pilipczuk, Michał
Publicado: (2025)

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

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

Smaller Circuits for Bit Addition
por: Goncharov, Mikhail, et al.
Publicado: (2025)

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

From Width-Based Model Checking to Width-Based Automated Theorem Proving
por: Oliveira, Mateus de Oliveira, et al.
Publicado: (2022)

Twice-Ramanujan Sparsifiers
por: Batson, Joshua, et al.
Publicado: (2008)

Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
por: Dahan, Anatole, et al.
Publicado: (2026)

Placing Green Bridges Optimally for Robust Habitat Reconnection
por: Ellmies, Gero, et al.
Publicado: (2026)

On Tight Robust Coresets for $k$-Medians Clustering
por: Huang, Lingxiao, et al.
Publicado: (2025)

Algorithms and complexity for monitoring edge-geodetic sets in graphs
por: Foucaud, Florent, et al.
Publicado: (2024)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
por: Bandyapadhyay, Sayan, et al.
Publicado: (2024)

Non-Exclusive Notifications for Ride-Hailing at Lyft I: Single-Cycle Approximation Algorithms
por: Ekbatani, Farbod, et al.
Publicado: (2026)

Distortion of Metric Voting with Bounded Randomness
por: Cai, Ziyi, et al.
Publicado: (2026)

Monotone Randomized Apportionment
por: Correa, José, et al.
Publicado: (2024)

Some variations of the secretary problem
por: Agrawal, Sarthak, et al.
Publicado: (2026)

Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations
por: Bilò, Vittorio, et al.
Publicado: (2025)

Unbalanced Random Matching Markets with Partial Preferences
por: Potukuchi, Aditya, et al.
Publicado: (2024)

A Customized SAT-based Solver for Graph Coloring
por: Brand, Timo, et al.
Publicado: (2025)

Parameterized Complexity of Path Set Packing
por: Aravind, N. R., et al.
Publicado: (2022)