On Super Strong ETH

DOI10.1613/jair.1.11859OpenAlexW3128463714MaRDI QIDQ5856463

Nikhil Vyas, R. Ryan Williams

Publication date: 26 March 2021

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1613/jair.1.11859

zbMATH Keywords

satisfiabilityconstraint satisfactionmathematical foundations

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites Work

• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• NP is as easy as detecting unique solutions
• On super strong ETH
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Generating hard satisfiability problems
• Proof of the Satisfiability Conjecture for Large k
• The Time Complexity of Constraint Satisfaction
• An improved exponential-time algorithm for k -SAT
• Relations between average case complexity and approximation complexity
• Solving random satisfiable 3CNF formulas in expected polynomial time
• The Complexity of Satisfiability of Small Depth Circuits
• Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
• Bridging between 0/1 and linear programming via random walks
• A Better Algorithm for Random k-SAT
• 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On Super Strong ETH