:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Bortolotti, Alex, Mastrolilli, Monaldo, Palomba, Marilena, Vargas, Luis Felipe
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2509.06928
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Degree Automatability of Sum-of-Squares Proofs
by: Bortolotti, Alex, et al.
Published: (2025)

Computational complexity of sum-of-squares bounds for copositive programs
by: Palomba, Marilena, et al.
Published: (2025)

Ideal Membership Problem for Boolean Minority and Dual Discriminator
by: Bharathi, Arpitha P., et al.
Published: (2024)

Symmetric Proofs in the Ideal Proof System
by: Dawar, Anuj, et al.
Published: (2025)

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

Sum of Squares Circuits
by: Loconte, Lorenzo, et al.
Published: (2024)

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

Does Subset Sum Admit Short Proofs?
by: Włodarczyk, Michał
Published: (2024)

Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
by: Ren, Hanlin, et al.
Published: (2025)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
by: Hitchcock, John M.
Published: (2026)

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

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
by: Li, Zeyong
Published: (2023)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

Sum-of-Squares & Gaussian Processes I: Certification
by: Sandhu, Juspreet Singh, et al.
Published: (2024)

PosSLP and Sum of Squares
by: Bläser, Markus, et al.
Published: (2024)

New Direct Sum Tests
by: Westover, Alek, et al.
Published: (2024)

Simulating Time With Square-Root Space
by: Williams, R. Ryan
Published: (2025)

The Algebraic Cost of a Boolean Sum
by: Orzel, Ian, et al.
Published: (2025)

The Round Complexity of Proofs in the Bounded Quantum Storage Model
by: Grilo, Alex B., et al.
Published: (2024)

Distribution-Free Proofs of Proximity
by: Aaronson, Hugo, et al.
Published: (2023)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

On the Existence of Algebraic Natural Proofs
by: Chatterjee, Prerona, et al.
Published: (2020)

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

Geometry Of The Subset Sum Problem -- Part I
by: Bollepalli, Srinivas Balaji
Published: (2025)

Symmetric Distributions from Shallow Circuits
by: Kane, Daniel M., et al.
Published: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
by: Dawar, Anuj, et al.
Published: (2025)

Locally Sampleable Uniform Symmetric Distributions
by: Kane, Daniel M., et al.
Published: (2024)

Proof Systems Based on Structured Circuits
by: Micun, Matthäus, et al.
Published: (2026)

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

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

Computing the Elementary Symmetric Polynomials in Positive Characteristics
by: Orzel, Ian
Published: (2025)

On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
by: Agarwal, Sanyam, et al.
Published: (2026)

Computational Complexity and Integer Programming Formulation of the Oredango Puzzle
by: Takahata, Takuma, et al.
Published: (2025)

Recursive Jump Operators and Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Hard CNF Instances for Ideal Proof Systems
by: Hakoniemi, Tuomas, et al.
Published: (2026)

A Strong Direct Sum Theorem for Distributional Query Complexity
by: Blanc, Guy, et al.
Published: (2024)

Constant Bit-size Transformers Are Turing Complete
by: Li, Qian, et al.
Published: (2025)

Proof Complexity and Feasible Interpolation
by: Tabatabai, Amirhossein Akbar
Published: (2025)

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Optimal Proof Systems for Complex Sets are Hard to Find
by: Egidy, Fabian, et al.
Published: (2024)