:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Salamon, András Z., Wehar, Michael
Format:	Preprint
Published:	2021
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2111.02138
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Constructive Separations and Their Consequences
by: Chen, Lijie, et al.
Published: (2022)

Value Iteration with Guessing for Markov Chains and Markov Decision Processes
by: Chatterjee, Krishnendu, et al.
Published: (2025)

Certificate Games and Consequences for the Classical Adversary Bound
by: Chakraborty, Sourav, et al.
Published: (2022)

Exponential Separation Criteria for Quantum Iterative Power Algorithms
by: Czégel, András, et al.
Published: (2025)

Has quantum advantage been achieved?
by: Hangleiter, Dominik
Published: (2026)

Unlikely intersections of codimension one foliations
by: Barbosa, Gabriel Santos, et al.
Published: (2025)

Circuits and Formulas for Datalog over Semirings
by: Fan, Austen Z., et al.
Published: (2025)

Effective Versions of Strong Measure Zero
by: Rayman, Matthew
Published: (2025)

An origami Universal Turing Machine design
by: Assis, Michael
Published: (2024)

Circuits and Backdoors: Five Shades of the SETH
by: Lampis, Michael
Published: (2024)

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
by: Chavrimootoo, Michael C.
Published: (2024)

Multiparty Communication Complexity of Collision Finding
by: Beame, Paul, et al.
Published: (2024)

d-QBF with Few Existential Variables Revisited
by: Grigorjew, Andreas, et al.
Published: (2026)

Filtrations associated with singularities
by: Némethi, András, et al.
Published: (2024)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
by: Chavrimootoo, Michael C., et al.
Published: (2026)

New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality
by: Nagy, Tomáš, et al.
Published: (2025)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
by: DeJesse, Nicholas, et al.
Published: (2025)

Local Enumeration and Majority Lower Bounds
by: Gurumukhani, Mohit, et al.
Published: (2024)

A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
by: Le, Tran Duy Anh, et al.
Published: (2024)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
by: Gurumukhani, Mohit, et al.
Published: (2026)

Assembly Theory and its Relationship with Computational Complexity
by: Kempes, Christopher P., et al.
Published: (2024)

Corners in Quasirandom Groups via Sparse Mixing
by: Jaber, Michael, et al.
Published: (2024)

Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
by: Bozga, Marius, et al.
Published: (2026)

Unconditional Time and Space Complexity Lower Bounds for Intersection Non-Emptiness
by: Wehar, Michael
Published: (2025)

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

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

The Complexity of Local Stoquastic Hamiltonians on 2D Lattices
by: Waite, Gabriel, et al.
Published: (2025)

An Overview of the Theory of Instances Computational Complexity
by: Jorge A. Ruiz-Vanoye
Published: (2011)

Complexity of Scheduling Charging in the Smart Grid
by: de Weerdt, Mathijs, et al.
Published: (2017)

Expected Complexity of Persistence Barcode Computation via Matrix Reduction
by: Giunti, Barbara, et al.
Published: (2021)

The complexity of knapsack problems in wreath products
by: Figelius, Michael, et al.
Published: (2020)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
by: Amiri, Alireza, et al.
Published: (2025)

Bosonic Quantum Computational Complexity
by: Chabaud, Ulysse, et al.
Published: (2024)

Minimum Stable Cut and Treewidth
by: Lampis, Michael
Published: (2021)

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)

The Primal Pathwidth SETH
by: Lampis, Michael
Published: (2024)

A Reply to "On Salum's Algorithm for X3SAT"
by: Salum, Latif
Published: (2021)

Depth lower bounds in Stabbing Planes for combinatorial principles
by: Dantchev, Stefan, et al.
Published: (2021)

Efficient algorithms for collecting the statistics of large-scale IP address data
by: Liu, Hui, et al.
Published: (2021)

The PCP-like Theorem for Sub-linear Time Inapproximability
by: Ma, Hengzhao, et al.
Published: (2021)