Cover Image

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Li, Zeyong
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Hierarchies within TFNP: building blocks and collapses
by: Ghentiyala, Surendra, et al.
Published: (2025)

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

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

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

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)

Hardness Amplification for (Sparse) LPN
by: Aggarwal, Divesh, et al.
Published: (2026)

Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
by: de Rezende, Susanna F., et al.
Published: (2024)

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
by: Bortolotti, Alex, et al.
Published: (2025)

Uniformity within Parameterized Circuit Classes
by: Hegeman, Steef, et al.
Published: (2025)

Optimal Lower Bounds for Symmetric Modular Circuits
by: Pago, Benedikt
Published: (2026)

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Identity Testing for Circuits with Exponentiation Gates
by: Li, Jiatu, et al.
Published: (2025)

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$
by: Chen, Lijie, et al.
Published: (2024)

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

When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
by: Li, Chenyang, et al.
Published: (2025)

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

A Simple Constructive Bound on Circuit Size Change Under Truth Table Perturbation
by: Krinkin, Kirill
Published: (2026)

Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
by: Jacot, Arthur
Published: (2025)

Exponential lower bound via exponential sums
by: Bhattacharjee, Somnath, et al.
Published: (2026)

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
by: Kahanamoku-Meyer, Gregory D., et al.
Published: (2024)

An Exponential Separation between Deterministic CDCL and DPLL Solvers
by: Samar, Sahil, et al.
Published: (2026)

Arithmetic Circuits with Division
by: Sacher, Silas Cato
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)

Maximum Matching and Related Problems in Catalytic Logspace
by: Chakraborty, Srijan, et al.
Published: (2026)

Min-Max Optimization Requires Exponentially Many Queries
by: Bernasconi, Martino, et al.
Published: (2026)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

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

Exponential Separation Between Powers of Regular and General Resolution Over Parities
by: Bhattacharya, Sreejata Kishor, et al.
Published: (2024)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
by: Buhrman, Harry, et al.
Published: (2025)

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

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

Lower bounds for planar Arithmetic Circuits
by: Ramya, C., et al.
Published: (2025)

Circuits and Backdoors: Five Shades of the SETH
by: Lampis, Michael
Published: (2024)

Nearest Neighbor Complexity and Boolean Circuits
by: DiCicco, Mason, et al.
Published: (2024)

Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
by: Aivasiliotis, Panagiotis, et al.
Published: (2025)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
by: Rajakumar, Joel, et al.
Published: (2024)

A Quadratic Lower Bound for Noncommutative Circuits
by: Shastri, Pratik
Published: (2026)