Image de couverture de livre

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Gajulapalli, Karthik, Li, Zeyong, Volkovich, Ilya
Format:	Preprint
Publié:	2025
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

Upper and Lower Bounds for the Linear Ordering Principle
par: Hirsch, Edward A., et autres
Publié: (2025)

Downward self-reducibility in the total function polynomial hierarchy
par: Gajulapalli, Karthik, et autres
Publié: (2025)

Hierarchies within TFNP: building blocks and collapses
par: Ghentiyala, Surendra, et autres
Publié: (2025)

Online Orthogonal Vectors Revisited
par: Gajulapalli, Karthik, et autres
Publié: (2026)

A Note on Avoid vs MCSP
par: Hirsch, Edward A., et autres
Publié: (2025)

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
par: Li, Zeyong
Publié: (2023)

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

The Complexity of Logarithmic Space Bounded Counting Classes
par: Vijayaraghavan, T. C.
Publié: (2025)

Hardness Amplification for (Sparse) LPN
par: Aggarwal, Divesh, et autres
Publié: (2026)

Oblivious Deletion Codes
par: Con, Roni, et autres
Publié: (2025)

A Hierarchy for Constant Communication Complexity
par: Ambainis, Andris, et autres
Publié: (2025)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
par: Conneryd, Jonas, et autres
Publié: (2025)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
par: Chen, Lijie, et autres
Publié: (2025)

Local Enumeration and Majority Lower Bounds
par: Gurumukhani, Mohit, et autres
Publié: (2024)

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

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

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

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

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

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

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)

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)

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

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)

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

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
par: Li, Shuangle, et autres
Publié: (2024)

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)

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

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

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

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

Structure in Communication Complexity and Constant-Cost Complexity Classes
par: Hatami, Hamed, et autres
Publié: (2024)

On Bounded Advice Classes
par: Marshall, Simon, et autres
Publié: (2024)

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
par: Li, Jiawei, et autres
Publié: (2024)