Image de couverture de livre

Boolean functions on high-dimensional expanders

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Dikstein, Yotam, Dinur, Irit, Filmus, Yuval, Harsha, Prahladh
Format:	Preprint
Publié:	2018
Sujets:	Computational Complexity Combinatorics
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Sparse juntas on the biased hypercube
par: Dinur, Irit, et autres
Publié: (2017)

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
par: Dikstein, Yotam, et autres
Publié: (2023)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
par: Dikstein, Yotam, et autres
Publié: (2024)

Coboundary and cosystolic expansion without dependence on dimension or degree
par: Dikstein, Yotam, et autres
Publié: (2023)

Swap cosystolic expansion
par: Dikstein, Yotam, et autres
Publié: (2023)

Chernoff Bounds and Reverse Hypercontractivity on HDX
par: Dikstein, Yotam, et autres
Publié: (2024)

Sparse High Dimensional Expanders via Local Lifts
par: Yaacov, Inbar Ben, et autres
Publié: (2024)

Sensitivity and Hamming graphs
par: Asensio, Sara, et autres
Publié: (2025)

An exposition of recent list-size bounds of FRS Codes
par: Garg, Abhibhav, et autres
Publié: (2025)

Query complexity of Boolean functions on the middle slice of the cube
par: Gerbner, Dániel, et autres
Publié: (2023)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
par: Dinur, Itai, et autres
Publié: (2021)

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
par: Dinur, Irit, et autres
Publié: (2024)

Tensor rank and dimension expanders
par: Dvir, Zeev
Publié: (2025)

Classification of Non-redundancy of Boolean Predicates of Arity 4
par: Brakensiek, Joshua, et autres
Publié: (2026)

Deterministic list decoding of Reed-Solomon codes
par: Chatterjee, Soham, et autres
Publié: (2025)

High Rate Efficient Local List Decoding from HDX
par: Dikstein, Yotam, et autres
Publié: (2026)

VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
par: Chang, Fan, et autres
Publié: (2025)

Classification aggregation: a quantitative impossibility theorem
par: Filmus, Yuval
Publié: (2026)

Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
par: Goyal, Rohan, et autres
Publié: (2025)

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
par: Goyal, Rohan, et autres
Publié: (2023)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
par: Gan, Luyining, et autres
Publié: (2023)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
par: Filmus, Yuval, et autres
Publié: (2020)

Algorithmizing the Multiplicity Schwartz-Zippel Lemma
par: Bhandari, Siddharth, et autres
Publié: (2021)

Aggregation of evaluations without unanimity
par: Filmus, Yuval
Publié: (2025)

A base change framework for tensor functions
par: Chen, Qiyuan
Publié: (2026)

Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes
par: Yang, Chao, et autres
Publié: (2024)

Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
par: Yang, Chao, et autres
Publié: (2024)

Low-Degree Polynomials Are Good Extractors
par: Alrabiah, Omar, et autres
Publié: (2024)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
par: Eagling-Vose, Tala, et autres
Publié: (2025)

Refuting Perfect Matchings in Spectral Expanders is Hard
par: Biswas, Ari, et autres
Publié: (2025)

A Note on the Complexity of Directed Clique
par: Gutowski, Grzegorz, et autres
Publié: (2026)

Direct Product Primality Testing of Graphs is GI-hard
par: Calderoni, Luca, et autres
Publié: (2020)

Monotone Circuit Complexity of Matching
par: Cavalar, Bruno, et autres
Publié: (2025)

Hunting a rabbit: complexity, approximability and some characterizations
par: Ben-Ameur, Walid, et autres
Publié: (2025)

On the Keevash-Knox-Mycroft Conjecture
par: Gan, Luyining, et autres
Publié: (2022)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
par: Borzechowski, Michaela, et autres
Publié: (2023)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
par: Basu, Arpon, et autres
Publié: (2024)

On Approximability of Satisfiable $k$-CSPs: VI
par: Bhangale, Amey, et autres
Publié: (2024)

Flat origami is Turing Complete
par: Hull, Thomas C., et autres
Publié: (2023)

On Approximability of Satisfiable $k$-CSPs: VII
par: Bhangale, Amey, et autres
Publié: (2024)