Cover Image

Effective Guessing Has Unlikely Consequences

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Salamon, András Z., Wehar, Michael
Format:	Preprint
Published:	2021
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
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)

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

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

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

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)

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

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)

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

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

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

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

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)

Sketching approximability of all finite CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
by: Çivril, Ali
Published: (2021)

Separations between Combinatorial Measures for Transitive Functions
by: Chakraborty, Sourav, et al.
Published: (2021)

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

Variety Evasive Subspace Families
by: Guo, Zeyu
Published: (2021)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
by: S., Karthik C., et al.
Published: (2021)

Fourier growth of structured $\mathbb{F}_2$-polynomials and applications
by: Błasiok, Jarosław, et al.
Published: (2021)

Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond
by: van Iersel, Leo, et al.
Published: (2024)

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
by: Ketkov, Sergey S., et al.
Published: (2025)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
by: Carmosino, Marco, et al.
Published: (2026)

A note on Jerabek's paper "A simplified lower bound for implicational logic"
by: Gordeev, Lev, et al.
Published: (2026)

A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing
by: Kortsarz, Guy
Published: (2026)