# Tag Info

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$. ...

### 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 ...

### 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 ...
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

### 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 ...
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