New answers tagged reference-request
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
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
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
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 ...
- 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
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 ...
- 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