:: Library Catalog

Copertina

Salvato in:

Dettagli Bibliografici
Autori principali:	Arteche, Noel, Khaniki, Erfan, Pich, Ján, Santhanam, Rahul
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	https://arxiv.org/abs/2405.02232
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

The Proof Analysis Problem
di: Arteche, Noel, et al.
Pubblicazione: (2025)

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

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

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

Constructive Separations and Their Consequences
di: Chen, Lijie, et al.
Pubblicazione: (2022)

Proof Complexity and Feasible Interpolation
di: Tabatabai, Amirhossein Akbar
Pubblicazione: (2025)

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

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

Monotone Circuit Complexity of Matching
di: Cavalar, Bruno, et al.
Pubblicazione: (2025)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Quantum Interactive Oracle Proofs
di: Sun, Baocheng, et al.
Pubblicazione: (2026)

Wasserstein Complexity of Quantum Circuits
di: Li, Lu, et al.
Pubblicazione: (2022)

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

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

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

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

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

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

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

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

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