:: Library Catalog

Imagen de Portada

Guardado en:

Detalles Bibliográficos
Autores principales:	Di Cosmo, Francesco, Mal, Soumodev, Prince, Tephilla
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity
Acceso en línea:	https://arxiv.org/abs/2504.03591
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Nets-within-Nets through the Lens of Data Nets
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)

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

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

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

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

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

Bounded Model Checking for Unbounded Client Server Systems
por: Phawade, Ramchandra, et al.
Publicado: (2022)

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Improved Lower Bounds for QAC0
por: Joshi, Malvika Raj, et al.
Publicado: (2025)

Lower Bounds for Convexity Testing
por: Chen, Xi, et al.
Publicado: (2024)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
por: Alman, Josh, et al.
Publicado: (2025)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
por: Raz, Ran
Publicado: (2026)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
por: Ostonov, Azimkhon, et al.
Publicado: (2024)

Optimal Lower Bounds for Symmetric Modular Circuits
por: Pago, Benedikt
Publicado: (2026)

Multiquadratic Sum-of-Squares Lower Bounds Imply VNC$^1$ $\neq$ VNP
por: Rossman, Benjamin, et al.
Publicado: (2025)

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

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
por: Gupta, Rishav, et al.
Publicado: (2026)

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
por: Mao, Xinyu, et al.
Publicado: (2024)

Sensitivity Lower Bounds for Approximaiton Algorithms
por: Fleming, Noah, et al.
Publicado: (2024)

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
por: Tang, Runshi, et al.
Publicado: (2026)

Improved Circuit Lower Bounds and Quantum-Classical Separations
por: Grewal, Sabee, et al.
Publicado: (2024)

Lower Bounds for Unitary Property Testing with Proofs and Advice
por: Weggemans, Jordi
Publicado: (2024)