Copertina

Classification of Non-redundancy of Boolean Predicates of Arity 4

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Brakensiek, Joshua, Guruswami, Venkatesan, Putterman, Aaron
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Multiplicative error set system sparsification: A simpler proof via chain length contraction
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

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

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
di: Alrabiah, Omar, et al.
Pubblicazione: (2024)

Punctured Low-Bias Codes Behave Like Random Linear Codes
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2021)

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

Maximal Recoverability: A Nexus of Coding Theory
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

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

Generic Reed-Solomon Codes Achieve List-decoding Capacity
di: Brakensiek, Joshua, et al.
Pubblicazione: (2022)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
di: Sharma, Amatya, et al.
Pubblicazione: (2026)

Hardness of Learning Boolean Functions from Label Proportions
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

Boolean functions on high-dimensional expanders
di: Dikstein, Yotam, et al.
Pubblicazione: (2018)

Query complexity of Boolean functions on the middle slice of the cube
di: Gerbner, Dániel, et al.
Pubblicazione: (2023)

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

New constructions of pseudorandom codes
di: Ghentiyala, Surendra, et al.
Pubblicazione: (2024)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
di: Goyal, Rohan, et al.
Pubblicazione: (2025)

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

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

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
di: Bhattiprolu, Vijay, et al.
Pubblicazione: (2025)

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2025)

VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
di: Chang, Fan, et al.
Pubblicazione: (2025)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
di: Bennett, Huck, et al.
Pubblicazione: (2022)

Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
di: Minevich, Igor, et al.
Pubblicazione: (2024)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
di: Li, Xin, et al.
Pubblicazione: (2024)

Scheduling Problems with Constrained Rejections
di: Davies, Sami, et al.
Pubblicazione: (2025)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2021)

Explicit Constant-Alphabet Subspace Design Codes
di: Goyal, Rohan, et al.
Pubblicazione: (2026)

Arity hierarchies for quantifiers closed under partial polymorphisms
di: Dawar, Anuj, et al.
Pubblicazione: (2025)

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

On the Mysteries of MAX NAE-SAT
di: Brakensiek, Joshua, et al.
Pubblicazione: (2020)

MAX BISECTION might be harder to approximate than MAX CUT
di: Brakensiek, Joshua, et al.
Pubblicazione: (2025)

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
di: Bhattiprolu, Vijay, et al.
Pubblicazione: (2024)

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

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

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

A Note on the Complexity of Directed Clique
di: Gutowski, Grzegorz, et al.
Pubblicazione: (2026)

Lions and Contamination: Trees and General Graphs
di: Kim, Dohoon, et al.
Pubblicazione: (2026)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
di: Grüne, Christoph, et al.
Pubblicazione: (2026)

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

King Chasing Problem in Chinese Chess is NP-hard
di: Li, Chao, et al.
Pubblicazione: (2026)