Image de couverture de livre

Local Enumeration and Majority Lower Bounds

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Gurumukhani, Mohit, Paturi, Ramamohan, Pudlák, Pavel, Saks, Michael, Talebanfard, Navid
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Local Enumeration: The Not-All-Equal Case
par: Gurumukhani, Mohit, et autres
Publié: (2025)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
par: Gurumukhani, Mohit, et autres
Publié: (2026)

Optimal Depth-Three Circuits for Inner Product
par: Gurumukhani, Mohit, et autres
Publié: (2026)

On Extremal Properties of k-CNF: Capturing Threshold Functions
par: Gurumukhani, Mohit, et autres
Publié: (2024)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
par: Gryaznov, Svyatoslav, et autres
Publié: (2024)

On the Existence of Seedless Condensers: Exploring the Terrain
par: Chattopadhyay, Eshan, et autres
Publié: (2023)

Extractors for Polynomial Sources over $\mathbb{F}_2$
par: Chattopadhyay, Eshan, et autres
Publié: (2023)

Improved Bounds for Coin Flipping, Leader Election, and Random Selection
par: Chattopadhyay, Eshan, et autres
Publié: (2025)

Spectral Lower Bounds for Local Search
par: Brânzei, Simina, et autres
Publié: (2024)

Condensing and Extracting Against Online Adversaries
par: Chattopadhyay, Eshan, et autres
Publié: (2024)

Two-Sided Lossless Expanders in the Unbalanced Setting
par: Chattopadhyay, Eshan, et autres
Publié: (2024)

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

Lower Bounds for Approximate Sign Rank
par: Bindua, Riju, et autres
Publié: (2026)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
par: Kothari, Pravesh K., et autres
Publié: (2024)

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
par: Block, Alexander R., et autres
Publié: (2026)

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
par: Blocki, Jeremiah, et autres
Publié: (2021)

A Quadratic Lower Bound for Noncommutative Circuits
par: Shastri, Pratik
Publié: (2026)

IPS Lower Bounds for Formulas and Sum of ROABPs
par: Chatterjee, Prerona, et autres
Publié: (2025)

Lower Bounds for Set-Multilinear Branching Programs
par: Chatterjee, Prerona, et autres
Publié: (2023)

Lower Bounds from Succinct Hitting Sets
par: Chatterjee, Prerona, et autres
Publié: (2023)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
par: Byramji, Farzan, et autres
Publié: (2025)

Tight Lower Bounds for Block-Structured Integer Programs
par: Hunkenschröder, Christoph, et autres
Publié: (2024)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
par: Carmosino, Marco, et autres
Publié: (2026)

Top-Down Lower Bounds for Depth-Four Circuits
par: Göös, Mika, et autres
Publié: (2023)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
par: Gajulapalli, Karthik, et autres
Publié: (2025)

Lower Bounds for Subset Sum in Resolution with Modular Counting
par: Part, Fedor
Publié: (2022)

Lower Bounds for Conjunctive Query Evaluation
par: Mengel, Stefan
Publié: (2025)

A Lower Bound on Conservative Elementary Object Systems Coverability
par: Di Cosmo, Francesco, et autres
Publié: (2025)

Lower Bounds against the Ideal Proof System in Finite Fields
par: Elbaz, Tal, et autres
Publié: (2025)

Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians
par: Kocurek, Nicholas
Publié: (2025)

Query Lower Bounds for Correlation Clustering under Memory Constraints
par: Garg, Sumegha, et autres
Publié: (2026)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
par: Alhamdan, Yousef M.
Publié: (2025)

Separations above TFNP from Sherali-Adams Lower Bounds
par: Fleming, Noah, et autres
Publié: (2026)

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
par: Kamath, Pritish, et autres
Publié: (2026)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
par: Amiri, Alireza, et autres
Publié: (2025)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
par: Ostonov, Azimkhon, et autres
Publié: (2024)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
par: Raz, Ran
Publié: (2026)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
par: Alman, Josh, et autres
Publié: (2025)

A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture
par: Biswas, Aniruddha, et autres
Publié: (2022)

From FPT Decision to FPT Enumeration
par: Creignou, Nadia, et autres
Publié: (2025)