New answers tagged

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 ...
Michael Lampis's user avatar
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$. ...
Huck Bennett's user avatar
  • 4,788
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 ...
Aryeh's user avatar
  • 10.3k
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 ...
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 ...
Emil Jeřábek's user avatar
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
Emre Yolcu's user avatar
0 votes

Representation of binary strings by graphs and hypergraphs

I assume you mean that you want to represent a set of binary strings with a graph or hypergraph (since you mention a binary tree which I think is a set of binary strings - a unique string for every ...
JimN's user avatar
  • 1,276
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 ...

Top 50 recent answers are included