Image de couverture de livre

Sparse juntas on the biased hypercube

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Dinur, Irit, Filmus, Yuval, Harsha, Prahladh
Format:	Preprint
Publié:	2017
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

Boolean functions on high-dimensional expanders
par: Dikstein, Yotam, et autres
Publié: (2018)

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)

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)

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

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

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

Corners in Quasirandom Groups via Sparse Mixing
par: Jaber, Michael, et autres
Publié: (2024)

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

An unconditional lower bound for the active-set method on the hypercube
par: Disser, Yann, et autres
Publié: (2025)

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)

Coboundary and cosystolic expansion without dependence on dimension or degree
par: Dikstein, Yotam, 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)

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

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

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

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
par: Gribanov, Dmitry, et autres
Publié: (2022)

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)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
par: Hsieh, Jun-Ting, et autres
Publié: (2024)

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
par: Notarantonio, Hadrien, et autres
Publié: (2023)

An Invariance Principle for the Multi-slice, with Applications
par: Braverman, Mark, et autres
Publié: (2021)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
par: Baril, Ambroise, et autres
Publié: (2024)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
par: Grüne, Christoph
Publié: (2022)

Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
par: Hodur, Nadzieja, et autres
Publié: (2025)

A Subexponential Reduction from Product Partition to Subset Sum
par: Costandin, Marius
Publié: (2024)