On Super Strong ETH
From MaRDI portal
Publication:5856463
DOI10.1613/jair.1.11859OpenAlexW3128463714MaRDI QIDQ5856463
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
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