Skip to main content
15 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,908
14 votes
Accepted

Structural Complexity Theory References

I don't think there really are canonical references for this stuff (roughly: advanced modern structural complexity theory), but here are some references. This list is partially geared towards my ...
Joshua Grochow's user avatar
14 votes
Accepted

Complexity of NFA cofiniteness

Lemma 1. Determining whether a given NFA is cofinite is PSPACE-hard. Proof. The proof is by an easy reduction from the PSPACE-complete problem of determining whether a given NFA is universal. The ...
Neal Young's user avatar
  • 10.8k
12 votes

What are pertinent references to cite on Scott domains?

I asked Dana Scott who kindly responded. I am relaying his answer: I think the paper “A type-theoretical alternative to ISWIM, CUCH, OWHY” answers the questions and gives the context of the discovery....
Andrej Bauer's user avatar
  • 29.2k
11 votes

What are examples of recent relatively simple 'toolbox algorithms'?

Suffix arrays, with linear time construction. There are various algorithms, they're relatively approachable, and applications are plenty. SA-IS dates to 2009. Soft heaps, they're not that complex, and ...
user555045's user avatar
11 votes

What are examples of recent relatively simple 'toolbox algorithms'?

More attention has been given recently to sketching and streaming data structures, such as Bloom Filters, Count Min Sketch, HyperLogLog. Related, and also gaining popularity, are linear-algebra-based ...
usul's user avatar
  • 7,615
10 votes

What are examples of recent relatively simple 'toolbox algorithms'?

Quantum algorithms would fit this, if one has time to introduce the model -- specifically, Grover search and possibly Shor's algorithm.
usul's user avatar
  • 7,615
9 votes
Accepted

How many numbers are needed such that the possible subset sums cover $\{1, \frac{1}{2}, \frac{1}{3},\dots, \frac{1}{2^m}\}$?

The problem itself was studied in this paper and was proved to be $\mathsf{NP}$-complete given the target set $T$ as the input. For this specific instance $T=\{1,1/2,1/3,\ldots,1/n\}$, we can show ...
Wei Zhan's user avatar
  • 903
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
8 votes

What are examples of recent relatively simple 'toolbox algorithms'?

You could look at the multiplicative weights update method. Specific instances of this technique have been known since the 1950s, but it's only been recognized as a very useful general algorithmic ...
Peter Shor 's user avatar
8 votes

General collection with the current state of complexity bounds of well-known unsolved problems?

For job scheduling problems, there is this complexity wiki. I am not sure if it is actively being updated.
Inuyasha Yagami's user avatar
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
8 votes

What are pertinent references to cite on Scott domains?

First papers Scott (1993), A type-theoretical alternative to ISWIM, CUCH, OWHY. This 1969 manuscript was later published in TCS. The title is a bit odd but it seems to hide the very first written ...
8 votes

Complexity of NFA cofiniteness

Since the other answer makes it sound as if it were not obvious, let me point out that the problem is computable in PSPACE. First, we observe: Lemma. For any NFA $A$ with $n$ states, the following ...
Emil Jeřábek's user avatar
7 votes

NP-complete problems where the inputs are prime numbers

There are no known NP-complete problems whose input would consist of primes (or, say, $k$-tuples of primes, or even more complicated structures as long as they contain at least one prime of length $\...
Emil Jeřábek's user avatar
7 votes
Accepted

Approaches to fast matrix multiplication and their limits

Their phrase in that paper "All work on matrix multiplication since 1986" is...an oversimplification. While it's true that what they cite are all the papers that have improved the state of ...
Joshua Grochow's user avatar
6 votes

What are examples of recent relatively simple 'toolbox algorithms'?

Perhaps Markov Chain Monte Carlo. Like most other answers, it can be traced farther back, but rose to much more prominence since the mid-90s. In general, Markov chains and (random) walks on graphs are ...
usul's user avatar
  • 7,615
6 votes

What are examples of recent relatively simple 'toolbox algorithms'?

I think we could include submodular optimization. Many common optimization problems can be framed as maximizing or minimizing submodular functions subject to natural constraints. Examples include max ...
usul's user avatar
  • 7,615
6 votes
Accepted

What is the probability a random language in $\mathsf{PSPACE}$ is in $\mathsf{P}$?

As pointed out by Emil, and I think maybe the OP already knew based on the last sentence of the OQ, there isn't actually a uniform distribution on a countable set. However, Jack Lutz developed the ...
Joshua Grochow's user avatar
5 votes

What are examples of recent relatively simple 'toolbox algorithms'?

I guess it depends on what constitutes "too advanced from a math point of view." It is natural that modern algorithmic ideas will involve more modern mathematics. The theory of Linear ...
NaturalLogZ's user avatar
5 votes
Accepted

Horn clause on cnf

Yes, any unsatisfiable Horn CNF has a tree-like resolution refutation with a linear number of clauses. Consider the standard poly-time Horn-SAT algorithm, which works as follows. First, set all ...
Emil Jeřábek's user avatar
5 votes

The empty tree-word for regular tree languages

I believe this is one of the many cases where it becomes clear that labelling nodes is a bad choice, and we should be labelling edges instead. In the edge-labelled framework, the empty tree is simply ...
Denis's user avatar
  • 8,903
4 votes

What are examples of recent relatively simple 'toolbox algorithms'?

Montgomery's ladder and a whole host of other algorithms developed to mitigate side-channel attacks only appeared in the 1980-1990s. They're conceptually quite simple to understand, and the rationale ...
Raphael Treccani-Chinelli's user avatar
4 votes

General collection with the current state of complexity bounds of well-known unsolved problems?

For fixed-parameter tractability, there is this wiki: http://fpt.wikidot.com/fpt-races/ (seems to be updated only until ~10 years ago.) The problem with most such resources is that it takes a lot of ...
Hermann Gruber's user avatar
4 votes
Accepted

Tree decompositions with unique witness for each edge

I'm afraid the answer to both of your questions is no. Consider a graph $(V_n, E_n)$ with $V_n = \{1,...,n+2\}$ and $E = \{\{i,i+1\} | 1 \leq i \leq n+1\} \cup \{\{i,i+2\} \mid 1 \leq i \leq n\}$. ...
Corto's user avatar
  • 136
4 votes
Accepted

Computational complexity of the elementary theory of finite fields

By Proposition 13 in Benedikt and Hrushovski, the theory of finite fields has nonelementary complexity (it is harder than $k$-times iterated exponential time for all constants $k$). Apparently, the ...
Emil Jeřábek's user avatar
3 votes

Structural Complexity Theory References

Joshua Grochow gave a very detailed list in his answer. I would like to mention a few sources that present more introductory/intermediate material, although these may not be useful for OP (hopefully, ...
Cyriac Antony's user avatar
3 votes
Accepted

Finding deepest intersection

I have always seen this referred to as the depth of an arrangement of boxes (or rectangles in the planar case). Often the algorithms having to do with this depth look somewhat like algorithms for Klee'...
Tassle's user avatar
  • 881
3 votes

Complexity results for Lower-Elementary Recursive Functions?

Since lower elementary functions are computable in time $2^{O(n)}$ (and space $O(n)$), the set of corresponding decision problems is unlikely to include NP, or even just $\mathrm{NTIME}(n^{1+\epsilon})...
Emil Jeřábek's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible