Imagen de Portada

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Chukhin, Nikolai, Kulikov, Alexander S., Mihajlin, Ivan
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Improved Space Bounds for Subset Sum
por: Belova, Tatiana, et al.
Publicado: (2024)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
por: Chukhin, Nikolai, et al.
Publicado: (2024)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
por: Meir, Or
Publicado: (2023)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
por: Gryaznov, Svyatoslav, et al.
Publicado: (2024)

Strong XOR Lemma for Information Complexity
por: Sawettamalya, Pachara, et al.
Publicado: (2024)

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

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
por: Byramji, Farzan, et al.
Publicado: (2025)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
por: Gurumukhani, Mohit, et al.
Publicado: (2026)

One-Way Communication Complexity of Partial XOR Functions
por: Podolskii, Vladimir V., et al.
Publicado: (2023)

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
por: Bhattacharya, Sreejata Kishor, et al.
Publicado: (2025)

An XOR Lemma for Deterministic Communication Complexity
por: Iyer, Siddharth, et al.
Publicado: (2024)

Simple Circuit Extensions for XOR in PTIME
por: Carmosino, Marco, et al.
Publicado: (2025)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
por: Wang, Qisheng, et al.
Publicado: (2024)

XOR Lemmas for Communication via Marginal Information
por: Iyer, Siddharth, et al.
Publicado: (2023)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
por: Lu, Jiaqi, et al.
Publicado: (2025)

Refuting approaches to the log-rank conjecture for XOR functions
por: Hatami, Hamed, et al.
Publicado: (2023)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
por: Dinur, Itai, et al.
Publicado: (2021)

Local Enumeration and Majority Lower Bounds
por: Gurumukhani, Mohit, et al.
Publicado: (2024)

Spectral Lower Bounds for Local Search
por: Brânzei, Simina, et al.
Publicado: (2024)

Lower Bounds for Approximate Sign Rank
por: Bindua, Riju, et al.
Publicado: (2026)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
por: Kothari, Pravesh K., et al.
Publicado: (2024)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
por: Błasiok, Jarosław, et al.
Publicado: (2026)

A Quadratic Lower Bound for Noncommutative Circuits
por: Shastri, Pratik
Publicado: (2026)

IPS Lower Bounds for Formulas and Sum of ROABPs
por: Chatterjee, Prerona, et al.
Publicado: (2025)

Lower Bounds for Set-Multilinear Branching Programs
por: Chatterjee, Prerona, et al.
Publicado: (2023)

Lower Bounds from Succinct Hitting Sets
por: Chatterjee, Prerona, et al.
Publicado: (2023)

Parallel Repetition for $3$-Player XOR Games
por: Bhangale, Amey, et al.
Publicado: (2024)

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

Convergent Gate Elimination and Constructive Circuit Lower Bounds
por: Carmosino, Marco, et al.
Publicado: (2026)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
por: Gajulapalli, Karthik, et al.
Publicado: (2025)

Lower Bounds for Subset Sum in Resolution with Modular Counting
por: Part, Fedor
Publicado: (2022)

Lower Bounds for Conjunctive Query Evaluation
por: Mengel, Stefan
Publicado: (2025)

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
por: Li, Rupert, et al.
Publicado: (2025)

A Lower Bound on Conservative Elementary Object Systems Coverability
por: Di Cosmo, Francesco, et al.
Publicado: (2025)

Lower Bounds against the Ideal Proof System in Finite Fields
por: Elbaz, Tal, et al.
Publicado: (2025)

Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians
por: Kocurek, Nicholas
Publicado: (2025)

Query Lower Bounds for Correlation Clustering under Memory Constraints
por: Garg, Sumegha, et al.
Publicado: (2026)

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

Separations above TFNP from Sherali-Adams Lower Bounds
por: Fleming, Noah, et al.
Publicado: (2026)

Strongly Refuting Random CSP without Literals
por: Chan, Siu On, et al.
Publicado: (2026)