:: Library Catalog

Buchumschlag

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Gupta, Shreya, Huang, Boyang, Impagliazzo, Russell
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	https://arxiv.org/abs/2411.18137
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
von: Byramji, Farzan, et al.
Veröffentlicht: (2025)

High Rate Efficient Local List Decoding from HDX
von: Dikstein, Yotam, et al.
Veröffentlicht: (2026)

Subquadratic Algorithms and Hardness for Attention with Any Temperature
von: Gupta, Shreya, et al.
Veröffentlicht: (2025)

Replicability in High Dimensional Statistics
von: Hopkins, Max, et al.
Veröffentlicht: (2024)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
von: Aaronson, Scott, et al.
Veröffentlicht: (2023)

Submodular Maximization under Supermodular Constraint: Greedy Guarantees
von: Srivastava, Ajitesh, et al.
Veröffentlicht: (2026)

Improved Bounds for Coin Flipping, Leader Election, and Random Selection
von: Chattopadhyay, Eshan, et al.
Veröffentlicht: (2025)

On Computability of Computable Problems
von: Khaliq, Asad
Veröffentlicht: (2023)

The Stochastic Arrival Problem
von: Webster, Thomas
Veröffentlicht: (2022)

On the Hardness of the Drone Delivery Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2025)

Continuous Defensive Domination Problems
von: Grüne, Christoph, et al.
Veröffentlicht: (2026)

Parameterized Complexity of the Star Decomposition Problem
von: Hajebi, Sahab, et al.
Veröffentlicht: (2024)

On the Exact Matching Problem in Dense Graphs
von: Maalouly, Nicolas El, et al.
Veröffentlicht: (2024)

Complexity Theory for Quantum Promise Problems
von: Chia, Nai-Hui, et al.
Veröffentlicht: (2024)

On the Complexity of Problems on Tree-structured Graphs
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2022)

Reductions Between Code Equivalence Problems
von: Cheraghchi, Mahdi, et al.
Veröffentlicht: (2025)

Total Search Problems in $\mathsf{ZPP}$
von: Fleming, Noah, et al.
Veröffentlicht: (2025)

The 2-Attractor Problem is NP-Complete
von: Fuchs, Janosch, et al.
Veröffentlicht: (2023)

Inverse Intersections for Boolean Satisfiability Problems
von: Homer, Paul W.
Veröffentlicht: (2025)

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
von: Gupta, Rishav, et al.
Veröffentlicht: (2026)

On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
von: Agarwal, Sanyam, et al.
Veröffentlicht: (2026)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
von: Bennett, Huck, et al.
Veröffentlicht: (2022)

No Complete Problem for Constant-Cost Randomized Communication
von: Fang, Yuting, et al.
Veröffentlicht: (2024)

P-time Algorithms for Typical #EO Problems
von: Meng, Boning, et al.
Veröffentlicht: (2024)

Trading Determinism for Time: The k-Reach Problem
von: Bhadra, Ronak, et al.
Veröffentlicht: (2024)

The Line Traveling Salesman and Repairman Problem with Collaboration
von: Golak, Julian, et al.
Veröffentlicht: (2025)

Maximum Matching and Related Problems in Catalytic Logspace
von: Chakraborty, Srijan, et al.
Veröffentlicht: (2026)

Strong Inapproximability for a Promise Rank Problem
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2026)

Explaining the Ubiquity of Phase Transitions in Decision Problems
von: Jackson, Andrew
Veröffentlicht: (2025)

An Efficient Algorithm for Solving the 2-MAXSAT Problem
von: Chen, Yangjun
Veröffentlicht: (2023)

Geometry Of The Subset Sum Problem -- Part I
von: Bollepalli, Srinivas Balaji
Veröffentlicht: (2025)

Parameterised Holant Problems
von: Aivasiliotis, Panagiotis, et al.
Veröffentlicht: (2024)

Complexity Thresholds for the Constrained Colored Token Swapping Problem
von: Bilò, Davide, et al.
Veröffentlicht: (2026)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
von: Bai, Tian, et al.
Veröffentlicht: (2026)

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

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
von: Lichter, Moritz, et al.
Veröffentlicht: (2024)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
von: Yung, Kingsley
Veröffentlicht: (2024)

Partial Minimum Branching Program Size Problem is ETH-hard
von: Glinskih, Ludmila, et al.
Veröffentlicht: (2024)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
von: Fu, Cheng-Hao, et al.
Veröffentlicht: (2025)