:: Library Catalog

Buchumschlag

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Arteche, Noel, Khaniki, Erfan, Pich, Ján, Santhanam, Rahul
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	https://arxiv.org/abs/2405.02232
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Proof Analysis Problem
von: Arteche, Noel, et al.
Veröffentlicht: (2025)

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

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

Separations in Proof Complexity and TFNP
von: Göös, Mika, et al.
Veröffentlicht: (2022)

Constructive Separations and Their Consequences
von: Chen, Lijie, et al.
Veröffentlicht: (2022)

Proof Complexity and Feasible Interpolation
von: Tabatabai, Amirhossein Akbar
Veröffentlicht: (2025)

Nearest Neighbor Complexity and Boolean Circuits
von: DiCicco, Mason, et al.
Veröffentlicht: (2024)

Fine-Grained Complexity via Quantum Natural Proofs
von: Chen, Yanlin, et al.
Veröffentlicht: (2025)

Monotone Circuit Complexity of Matching
von: Cavalar, Bruno, et al.
Veröffentlicht: (2025)

Proof Complexity of Linear Logics
von: Tabatabai, Amirhossein Akbar, et al.
Veröffentlicht: (2026)

Communication Complexity is NP-hard
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

Optimal Proof Systems for Complex Sets are Hard to Find
von: Egidy, Fabian, et al.
Veröffentlicht: (2024)

Improved Bounds on the Space Complexity of Circuit Evaluation
von: Shalunov, Yakov
Veröffentlicht: (2025)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
von: Cavalar, Bruno P., et al.
Veröffentlicht: (2025)

Proof Systems Based on Structured Circuits
von: Micun, Matthäus, et al.
Veröffentlicht: (2026)

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

On the Incompressibility of Truth With Application to Circuit Complexity
von: Tonon, Luke
Veröffentlicht: (2025)

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

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
von: Hitchcock, John M.
Veröffentlicht: (2026)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
von: Chukhin, Nikolai, et al.
Veröffentlicht: (2024)

Barriers to Complexity-Theoretic Proofs that "AGI" Using Machine Learning is Impossible
von: Guerzhoy, Michael
Veröffentlicht: (2024)

Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
von: Ren, Hanlin, et al.
Veröffentlicht: (2025)

The Round Complexity of Proofs in the Bounded Quantum Storage Model
von: Grilo, Alex B., et al.
Veröffentlicht: (2024)

The Complexity of Computing KKT Solutions of Quadratic Programs
von: Fearnley, John, et al.
Veröffentlicht: (2023)

The Computational Complexity of Circuit Discovery for Inner Interpretability
von: Adolfi, Federico, et al.
Veröffentlicht: (2024)

Circuit Complexity Bounds for Visual Autoregressive Model
von: Ke, Yekun, et al.
Veröffentlicht: (2025)

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

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

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
von: Garg, Abhibhav, et al.
Veröffentlicht: (2025)

Quantum Interactive Oracle Proofs
von: Sun, Baocheng, et al.
Veröffentlicht: (2026)

Wasserstein Complexity of Quantum Circuits
von: Li, Lu, et al.
Veröffentlicht: (2022)

Structure in Communication Complexity and Constant-Cost Complexity Classes
von: Hatami, Hamed, et al.
Veröffentlicht: (2024)

Polynomial-Time Pseudodeterministic Construction of Primes
von: Chen, Lijie, et al.
Veröffentlicht: (2023)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
von: Cao, Yang, et al.
Veröffentlicht: (2025)

Truth Predicate of Inductive Definitions and Logical Complexity of Infinite-Descent Proofs
von: Ito, Sohei, et al.
Veröffentlicht: (2026)

On the Constant-Depth Circuit Complexity of Generating Quasigroups
von: Collins, Nathaniel A., et al.
Veröffentlicht: (2024)

Interactive Proofs For Distribution Testing With Conditional Oracles
von: Biswas, Ari, et al.
Veröffentlicht: (2025)

From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting
von: Hecher, Markus, et al.
Veröffentlicht: (2025)

Circuit Complexity Bounds for RoPE-based Transformer Architecture
von: Chen, Bo, et al.
Veröffentlicht: (2024)

The Complexity of Sparse Win-Lose Bimatrix Games
von: Batziou, Eleni, et al.
Veröffentlicht: (2026)