Buchumschlag

Scheme-Theoretic Approach to Computational Complexity. IV. A New Perspective on Hardness of Approximation

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Çivril, Ali
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Scheme-Theoretic Approach to Computational Complexity. III. SETH
von: Çivril, Ali
Veröffentlicht: (2023)

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
von: Çivril, Ali
Veröffentlicht: (2021)

Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$
von: Çivril, Ali
Veröffentlicht: (2021)

Near Optimal Hardness of Approximating $k$-CSP
von: Minzer, Dor, et al.
Veröffentlicht: (2025)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
von: Martinsson, Björn
Veröffentlicht: (2024)

Computational Complexity of Game Boy Games
von: Tirmazi, Hayder, et al.
Veröffentlicht: (2024)

When and Why is Persuasion Hard? A Computational Complexity Result
von: Wojtowicz, Zachary
Veröffentlicht: (2024)

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
von: Hair, Isaac M, et al.
Veröffentlicht: (2026)

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

On the Computational Hardness of Transformers
von: Saha, Barna, et al.
Veröffentlicht: (2026)

Hardness of Approximate Hylland-Zeckhauser Equilibria
von: Braverman, Mark, et al.
Veröffentlicht: (2026)

On Approximability of Satisfiable k-CSPs: IV
von: Bhangale, Amey, et al.
Veröffentlicht: (2023)

Improved Hardness-of-Approximation for Token Swapping
von: Hiken, Sam, et al.
Veröffentlicht: (2024)

Complexity-Theoretic Implications of Multicalibration
von: Casacuberta, Sílvia, et al.
Veröffentlicht: (2023)

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

New Techniques for Constructing Rare-Case Hard Functions
von: Nareddy, Tejas, et al.
Veröffentlicht: (2024)

Additive Models Explained: A Computational Complexity Approach
von: Bassan, Shahaf, et al.
Veröffentlicht: (2025)

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

Improved Hardness of Approximation for Geometric Bin Packing
von: Ray, Arka, et al.
Veröffentlicht: (2023)

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
von: Amir, Guy, et al.
Veröffentlicht: (2024)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

The Radical Solution and Computational Complexity
von: Zheng, Bojin, et al.
Veröffentlicht: (2024)

The Computational Complexity of Factored Graphs
von: Gupta, Shreya, et al.
Veröffentlicht: (2024)

Random Permutations in Computational Complexity
von: Hitchcock, John M., et al.
Veröffentlicht: (2025)

Topics in Theoretical Computer Science
von: Rode, Alexander Forrest
Veröffentlicht: (2025)

Local vs. Global Interpretability: A Computational Complexity Perspective
von: Bassan, Shahaf, et al.
Veröffentlicht: (2024)

Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
von: Gao, Ruiquan, et al.
Veröffentlicht: (2024)

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

Unifying Formal Explanations: A Complexity-Theoretic Perspective
von: Bassan, Shahaf, et al.
Veröffentlicht: (2026)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
von: Zheng, Bojin, et al.
Veröffentlicht: (2026)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
von: Przybyłek, Michał R., et al.
Veröffentlicht: (2026)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2020)

Computational Complexity of UAP Reverse Engineering: A Formal Analysis of Automaton Identification and Data Complexity
von: Daghbouche, Karim
Veröffentlicht: (2025)

SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
von: Hair, Isaac M., et al.
Veröffentlicht: (2025)

On Approximate Computation of Critical Points
von: Ahmadi, Amir Ali, et al.
Veröffentlicht: (2026)

Assembly Theory and its Relationship with Computational Complexity
von: Kempes, Christopher P., et al.
Veröffentlicht: (2024)

The Parameterized Complexity of Computing the Linear Vertex Arboricity
von: Erhardt, Alexander, et al.
Veröffentlicht: (2025)

An Overview of the Theory of Instances Computational Complexity
von: Jorge A. Ruiz-Vanoye
Veröffentlicht: (2011)

A Theoretical Computer Science Perspective on Free Will
von: Blum, Manuel, et al.
Veröffentlicht: (2022)

The Communication Complexity of Approximating Matrix Rank
von: Sherstov, Alexander A., et al.
Veröffentlicht: (2024)