Spectral Lower Bounds for Local Search

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Brânzei, Simina, Recker, Nicholas J.
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Tarski Lower Bounds from Multi-Dimensional Herringbones
von: Brânzei, Simina, et al.
Veröffentlicht: (2025)

A note on quantum lower bounds for local search via congestion and expansion
von: Brânzei, Simina, et al.
Veröffentlicht: (2024)

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
von: Brânzei, Simina, et al.
Veröffentlicht: (2024)

The Query Complexity of Local Search and Brouwer in Rounds
von: Brânzei, Simina, et al.
Veröffentlicht: (2020)

The Query Complexity of Local Search in Rounds on General Graphs
von: Brânzei, Simina, et al.
Veröffentlicht: (2026)

Computing Envy-Free up to Any Good (EFX) Allocations via Local Search
von: Brânzei, Simina
Veröffentlicht: (2025)

Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians
von: Kocurek, Nicholas
Veröffentlicht: (2025)

Local Enumeration and Majority Lower Bounds
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2024)

Tit-for-Tat Dynamics and Market Volatility
von: Brânzei, Simina
Veröffentlicht: (2019)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
von: Basu, Arpon, et al.
Veröffentlicht: (2024)

Lower Bounds for Approximate Sign Rank
von: Bindua, Riju, et al.
Veröffentlicht: (2026)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
von: Kothari, Pravesh K., et al.
Veröffentlicht: (2024)

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
von: Block, Alexander R., et al.
Veröffentlicht: (2026)

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
von: Blocki, Jeremiah, et al.
Veröffentlicht: (2021)

A Quadratic Lower Bound for Noncommutative Circuits
von: Shastri, Pratik
Veröffentlicht: (2026)

IPS Lower Bounds for Formulas and Sum of ROABPs
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2025)

Lower Bounds for Set-Multilinear Branching Programs
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2023)

Lower Bounds from Succinct Hitting Sets
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2023)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
von: Byramji, Farzan, et al.
Veröffentlicht: (2025)

Tight Lower Bounds for Block-Structured Integer Programs
von: Hunkenschröder, Christoph, et al.
Veröffentlicht: (2024)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
von: Carmosino, Marco, et al.
Veröffentlicht: (2026)

Top-Down Lower Bounds for Depth-Four Circuits
von: Göös, Mika, et al.
Veröffentlicht: (2023)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2025)

Lower Bounds for Subset Sum in Resolution with Modular Counting
von: Part, Fedor
Veröffentlicht: (2022)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
von: Gryaznov, Svyatoslav, et al.
Veröffentlicht: (2024)

Lower Bounds for Conjunctive Query Evaluation
von: Mengel, Stefan
Veröffentlicht: (2025)

A Lower Bound on Conservative Elementary Object Systems Coverability
von: Di Cosmo, Francesco, et al.
Veröffentlicht: (2025)

Lower Bounds against the Ideal Proof System in Finite Fields
von: Elbaz, Tal, et al.
Veröffentlicht: (2025)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2026)

Query Lower Bounds for Correlation Clustering under Memory Constraints
von: Garg, Sumegha, et al.
Veröffentlicht: (2026)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
von: Alhamdan, Yousef M.
Veröffentlicht: (2025)

Separations above TFNP from Sherali-Adams Lower Bounds
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

Dueling over Multiple Pieces of Dessert
von: Brânzei, Simina, et al.
Veröffentlicht: (2026)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
von: Ostonov, Azimkhon, et al.
Veröffentlicht: (2024)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
von: Raz, Ran
Veröffentlicht: (2026)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
von: Alman, Josh, et al.
Veröffentlicht: (2025)

A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture
von: Biswas, Aniruddha, et al.
Veröffentlicht: (2022)

Improved Lower Bounds for QAC0
von: Joshi, Malvika Raj, et al.
Veröffentlicht: (2025)

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
von: Mao, Xinyu, et al.
Veröffentlicht: (2024)

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
von: Gupta, Rishav, et al.
Veröffentlicht: (2026)