:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Arteche, Noel, Khaniki, Erfan, Pich, Ján, Santhanam, Rahul
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2405.02232
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Proof Analysis Problem
by: Arteche, Noel, et al.
Published: (2025)

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

Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard
by: Arteche, Noel, et al.
Published: (2024)

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

Constructive Separations and Their Consequences
by: Chen, Lijie, et al.
Published: (2022)

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

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

Fine-Grained Complexity via Quantum Natural Proofs
by: Chen, Yanlin, et al.
Published: (2025)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Proof Complexity of Linear Logics
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2026)

Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)

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

Improved Bounds on the Space Complexity of Circuit Evaluation
by: Shalunov, Yakov
Published: (2025)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

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

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
by: Chen, Lijie, et al.
Published: (2025)

On the Incompressibility of Truth With Application to Circuit Complexity
by: Tonon, Luke
Published: (2025)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
by: de Rezende, Susanna F., et al.
Published: (2026)

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

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

Barriers to Complexity-Theoretic Proofs that "AGI" Using Machine Learning is Impossible
by: Guerzhoy, Michael
Published: (2024)

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

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

The Complexity of Computing KKT Solutions of Quadratic Programs
by: Fearnley, John, et al.
Published: (2023)

The Computational Complexity of Circuit Discovery for Inner Interpretability
by: Adolfi, Federico, et al.
Published: (2024)

Circuit Complexity Bounds for Visual Autoregressive Model
by: Ke, Yekun, et al.
Published: (2025)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
by: Atserias, Albert, et al.
Published: (2024)

The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
by: Chen, Yifang, et al.
Published: (2024)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
by: Garg, Abhibhav, et al.
Published: (2025)

Quantum Interactive Oracle Proofs
by: Sun, Baocheng, et al.
Published: (2026)

Wasserstein Complexity of Quantum Circuits
by: Li, Lu, et al.
Published: (2022)

Structure in Communication Complexity and Constant-Cost Complexity Classes
by: Hatami, Hamed, et al.
Published: (2024)

Polynomial-Time Pseudodeterministic Construction of Primes
by: Chen, Lijie, et al.
Published: (2023)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
by: Cao, Yang, et al.
Published: (2025)

Truth Predicate of Inductive Definitions and Logical Complexity of Infinite-Descent Proofs
by: Ito, Sohei, et al.
Published: (2026)

On the Constant-Depth Circuit Complexity of Generating Quasigroups
by: Collins, Nathaniel A., et al.
Published: (2024)

Interactive Proofs For Distribution Testing With Conditional Oracles
by: Biswas, Ari, et al.
Published: (2025)

From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting
by: Hecher, Markus, et al.
Published: (2025)

Circuit Complexity Bounds for RoPE-based Transformer Architecture
by: Chen, Bo, et al.
Published: (2024)

The Complexity of Sparse Win-Lose Bimatrix Games
by: Batziou, Eleni, et al.
Published: (2026)