Most Popular
1500 questions
19
votes
3 answers
Models of computation strictly between classical and quantum in terms of query complexity
It is well known quantum computers are strictly more powerful than their classical counterparts in terms of query complexity.
Are there other models (natural or artificial) that are strictly between the quantum and classical in terms of query…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
19
votes
2 answers
How many tautologies are there?
Given $m, n, k$, how many of $k$-DNFs with $n$ variables and $m$ clauses are tautology? (or how many $k$-CNFs are unsatisfiable?)
Anonymous
- 4,041
- 19
- 43
19
votes
1 answer
Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?
I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically:
Problem. For a given system of $m$ linear equations in $n$ unknowns modulo $k$, do there exist any…
Niel de Beaudrap
- 8,821
- 31
- 70
19
votes
3 answers
CFG parsing using $o(n^2)$ space
There are a multitude of algorithms that can parse a context-free grammar in $O(n^3)$ time. Using matrix multiplication, one can even go asymptotically faster than that.
However, all algorithms for parsing arbitrary CFGs I know have a worst-case…
Alex ten Brink
- 4,680
- 25
- 48
19
votes
1 answer
A topological space related to SAT: is it compact?
The Satisfiability problem is, of course, a fundamental problem in theoretical CS. I was playing with one version of the problem with infinitely many variables. $\newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}}$
Basic Setup. Let…
Srivatsan Narayanan
- 531
- 2
- 9
19
votes
1 answer
Rapidly mixing Markov chains on 3-colorings of a cycle
The Glauber dynamics is a Markov chain on the colorings of a graph in which at each step one attempts to recolor a randomly chosen vertex with a random color. It does not mix for the 3-colorings of a 5-cycle: there are 30 3-colorings, but only 15 of…
David Eppstein
- 50,990
- 3
- 170
- 278
19
votes
2 answers
A data structure for minimum dot product queries
Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of the following format: given $x \in \mathbb{R}^n$…
ilyaraz
- 1,569
- 18
- 33
19
votes
5 answers
Where can you find job postings for faculty positions in CS theory?
What are the best resources for finding job postings for faculty positions in CS theory? Is there one website or mailing list in particular that is fairly comprehensive? I currently have the impression that one has to use a variety of resources to…
James King
- 2,613
- 18
- 25
19
votes
1 answer
Most efficient way to convert an $\text{AC}^0$ circuit to a circuit (of any depth) with gate fanout 1
EDIT (Aug 22, 2011):
I am further simplifying the question and putting a bounty on the question. Perhaps this simpler question will have an easy answer. I'm also going to strikethrough all the parts of the original question that are no longer…
Robin Kothari
- 13,617
- 2
- 60
- 116
19
votes
1 answer
Construction of graphs where every pair of vertices have an unique common neighbor
Let $G$ be a simple graph on $n$ vertices $(n > 3)$ with no vertex of degree $n − 1$. Suppose that for any two vertices of $G$, there is a unique vertex adjacent to both of them. It is an exercise from A Course in Combinatorics, van Lint and Wilson,…
Neeldhara
- 599
- 2
- 15
19
votes
3 answers
Trade off between time and query complexity
Working directly with time complexity or circuit lower bounds is scary. Hence, we develop tools like query complexity (or decision-tree complexity) to get a handle on lower bounds. Since each query takes at least one unit step, and computations…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
19
votes
2 answers
Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?
In their paper (p. 503) Garey and Johnson remark:
... there could exist an NP-complete problem which is neither NP-complete in the strong sense nor solvable by a pseudo-polynomial time algorithm ...
Does anyone know some candidate problems with…
Oleksandr Bondarenko
- 4,215
- 1
- 25
- 46
19
votes
2 answers
MIP with efficient provers
It is well-known that the set of languages having two-prover interactive proof systems, in which the verifier runs in polynomial-time (MIP), is NEXP. But are there bounds known on the power of such interactive proofs when the provers are restricted…
Thomas
- 445
- 2
- 7
19
votes
3 answers
What algorithms are known for computing Craig interpolants?
Is there any survey of algorithms for computing interpolants? What about papers on only one algorithm? The case I'm most interested in is $A=\lnot p\land q$ and $C=q$, plus the constraint that the interpolant is as small as possible. (I know of…
Radu GRIGore
- 4,796
- 30
- 69
19
votes
4 answers
How are side effects handled in semantics?
In Anthony Aaby's "Introduction to Programming Languages" section on Semantics, he makes the following observation:
Much of the work in the semantics of
programming languages is motivated by
the problems encountered in trying to
construct and…
Shane
- 2,233
- 3
- 26
- 25