13
votes
Accepted
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
This CSP is known to be SETH-hard. More precisely, assuming SETH, for any constant $\varepsilon > 0$ there is no $d^{(1-\varepsilon)n}$-time algorithm for solving this CSP with domain size $d$.
...
- 4,788
8
votes
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
To give an alternative (slightly older) reference to the one proposed in another answer, the result "If the SETH is true, then $n$-variable CSP over alphabets of size $d$ cannot be solved in time ...
- 3,416
8
votes
Do we currently know a polynomial-size Frege proof for Tseitin formulas?
Tseitin tautologies are unsatisfiable systems of linear equations over $\mathbb F_2$, and as such they can be refuted just by summing all the equations together (possibly after reconstructing the ...
- 16.9k
8
votes
Accepted
Do we currently know a polynomial-size Frege proof for Tseitin formulas?
Section 6 of the following paper has a sketch:
Alasdair Urquhart. Hard examples for resolution. Journal of the ACM,
34(1):209–219, 1987. DOI: https://doi.org/10.1145/7531.8928
- 286
2
votes
What are the recent TCS books whose drafts are available online?
A bit awkward as it's my own, but the draft of my monograph on distribution testing, "Topics and Techniques in Distribution Testing: A Biased but Representative Sample" (Now Publishers, FnT ...
1
vote
Accepted
Learning arithmetic series
An arithmetic series is defined by the 1st term $t_1$ and the difference between terms $d$. If you stipulate that $\max(|t_1|,d)\le M$ then you have a finite hypothesis space and hence a finite ...
- 10.3k
1
vote
What are the recent TCS books whose drafts are available online?
The following book is about Database Theory, a small subarea of TCS at the border to Data Management:
Principles of Databases by Marcelo Arenas, Pablo Barcelo, Leonid Libkin, Wim Martens, and Andreas ...
Only top scored, non community-wiki answers of a minimum length are eligible