:: Library Catalog

Image de couverture de livre

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Arteche, Noel, Khaniki, Erfan, Pich, Ján, Santhanam, Rahul
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity
Accès en ligne:	https://arxiv.org/abs/2405.02232
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

The Proof Analysis Problem
par: Arteche, Noel, et autres
Publié: (2025)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
par: Lu, Jiaqi, et autres
Publié: (2025)

Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard
par: Arteche, Noel, et autres
Publié: (2024)

Separations in Proof Complexity and TFNP
par: Göös, Mika, et autres
Publié: (2022)

Constructive Separations and Their Consequences
par: Chen, Lijie, et autres
Publié: (2022)

Proof Complexity and Feasible Interpolation
par: Tabatabai, Amirhossein Akbar
Publié: (2025)

Nearest Neighbor Complexity and Boolean Circuits
par: DiCicco, Mason, et autres
Publié: (2024)

Fine-Grained Complexity via Quantum Natural Proofs
par: Chen, Yanlin, et autres
Publié: (2025)

Monotone Circuit Complexity of Matching
par: Cavalar, Bruno, et autres
Publié: (2025)

Proof Complexity of Linear Logics
par: Tabatabai, Amirhossein Akbar, et autres
Publié: (2026)

Communication Complexity is NP-hard
par: Hirahara, Shuichi, et autres
Publié: (2025)

Optimal Proof Systems for Complex Sets are Hard to Find
par: Egidy, Fabian, et autres
Publié: (2024)

Improved Bounds on the Space Complexity of Circuit Evaluation
par: Shalunov, Yakov
Publié: (2025)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
par: Cavalar, Bruno P., et autres
Publié: (2025)

Proof Systems Based on Structured Circuits
par: Micun, Matthäus, et autres
Publié: (2026)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
par: Chen, Lijie, et autres
Publié: (2025)

On the Incompressibility of Truth With Application to Circuit Complexity
par: Tonon, Luke
Publié: (2025)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
par: de Rezende, Susanna F., et autres
Publié: (2026)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
par: Hitchcock, John M.
Publié: (2026)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
par: Chukhin, Nikolai, et autres
Publié: (2024)

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

Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
par: Ren, Hanlin, et autres
Publié: (2025)

The Round Complexity of Proofs in the Bounded Quantum Storage Model
par: Grilo, Alex B., et autres
Publié: (2024)

The Complexity of Computing KKT Solutions of Quadratic Programs
par: Fearnley, John, et autres
Publié: (2023)

The Computational Complexity of Circuit Discovery for Inner Interpretability
par: Adolfi, Federico, et autres
Publié: (2024)

Circuit Complexity Bounds for Visual Autoregressive Model
par: Ke, Yekun, et autres
Publié: (2025)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
par: Atserias, Albert, et autres
Publié: (2024)

The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
par: Chen, Yifang, et autres
Publié: (2024)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
par: Garg, Abhibhav, et autres
Publié: (2025)

Quantum Interactive Oracle Proofs
par: Sun, Baocheng, et autres
Publié: (2026)

Wasserstein Complexity of Quantum Circuits
par: Li, Lu, et autres
Publié: (2022)

Structure in Communication Complexity and Constant-Cost Complexity Classes
par: Hatami, Hamed, et autres
Publié: (2024)

Polynomial-Time Pseudodeterministic Construction of Primes
par: Chen, Lijie, et autres
Publié: (2023)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
par: Cao, Yang, et autres
Publié: (2025)

Truth Predicate of Inductive Definitions and Logical Complexity of Infinite-Descent Proofs
par: Ito, Sohei, et autres
Publié: (2026)

On the Constant-Depth Circuit Complexity of Generating Quasigroups
par: Collins, Nathaniel A., et autres
Publié: (2024)

Interactive Proofs For Distribution Testing With Conditional Oracles
par: Biswas, Ari, et autres
Publié: (2025)

From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting
par: Hecher, Markus, et autres
Publié: (2025)

Circuit Complexity Bounds for RoPE-based Transformer Architecture
par: Chen, Bo, et autres
Publié: (2024)

The Complexity of Sparse Win-Lose Bimatrix Games
par: Batziou, Eleni, et autres
Publié: (2026)