Why do we need formal semantics for predicate logic? Consider this question solved. I will not pick a best answer as all of them have contributed to my understanding of the topic.

Im unsure what benefit we have by formally defining the semantics of predicate logic. But I do see value in having a formal proof calculus. My point is that we would not need formal semantics to justify the inference rules of proof calculi.

We could define a calculus that mimicks the "laws of thought", i.e. the rules of inference that have been used by mathematicians for hundreds of years to proof their theorems. Such a calculus already exists: natural deduction. Then we would define this calculus to be sound and complete.

This can be justified by realising that the formal semantics of predicate logic is just a model. The appropriateness of the model can only be justified intuitively. Thus, by showing that natural deduction is sound and complete with reference to the formal semantics does not make natural deduction more "true". It would be just as good if we would directly justify the rules of natural deduction intuitively. The detour using formal semantics gives us nothing.

Then, having defined natural deduction to be sound and complete, we could show the soundness and completeness of other calculi by showing that the proofs they produce can be translated to natural deduction and vice versa.

Are my reflections above correct?
Why is it important to prove the soundness and completeness of proof calculi by reference to formal semantics?

A minor comment, and a more serious answer.

First, it doesn't make sense to declare a natural deduction system complete by fiat. Natural deduction is interesting precisely because it has a natural internal notion of consistency and/or completeness -- namely, cut-elimination. This is a fantastic theorem, and IMO fully justifies attempts to give purely proof-theoretic semantics (and by the CH correspondence, it likewise justifies the use of operational methods in programming language semantics). But this is interesting precisely because it offers a more refined notion of getting the logic right than consistency. Taking the proof theoretic road means you'll have to do more work, but in exchange you get stronger results.

However, it happens that sometimes the logic per se takes a secondary role. We may begin with a (family of) models, and then look for ways of talking syntactically about them, using a logic. The soundness and completeness of a logic with respect to a family of models indicates that the logic really does capture everything both interesting and true you can say about the class of models. A concrete example of when models are more interesting than the logical theories occurs in program analysis and model checking. There, the usual thing to do is to take your model to be the execution of a program, and the logic to be some fragment of temporal logic. The propositions you can say in these languages are (deliberately) not terribly exciting -- e.g., null pointer dereferences never occur -- but it's the fact that it applies to actual program runs that gives it interest.


Problem of graph bi-partition (related to graph isomorphism) I am considering the following problem:

  Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$
  Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to $H_1$, and $G[V\backslash V_1]$ is isomorphic to $H_2$?

It is clearly at least as hard as Graph Isomorphism (take the empty graph for $H_2$), and in NP (certificate: $V_1$ and the isomorphisms). Intuitively, it should be easier than subgraph isomorphism, since here we know what the "complement" looks like.

I have several questions regarding this:

Has it been studied / does it have a name?
If yes, is it NP-hard?
If still yes, has it been studied on restricted graph classes?

Your problem is NP-complete. Two-colorable perfect matching (which is NP-complete even when restricted to cubic planar graphs) is reducible to your problem. Take $H_1$ and $H_2$ to be perfect matchings each of $|V|/2$ nodes. Then your problem is to find 2-coloring of $V$ such that each color class induces a perfect matching.


Does using Normal Order Evaluation instead of Normal Order Reduction lose the Normalization theorem? Normal Order Reduction (NOR)
reduce the leftmost, outermost redex.

Normal Order Evaluation (NOE)
reduce the leftmost, outermost redex, but not within the body of abstractions.

So (λw. (λx.x) z) is in normal form under NOE, but not under NOR.

Does using NOE instead of NOR weaken the Normalization property?

The Normalization property states that if there is a normal form under beta-reduction, that NOR will find it.
Edit:
Sorry, it's the Curry/Feys Theorem that says that NOR always finds a normal form if it exists.

NOE reduction strategy (as you define it) won't find the $\beta$-normal form of a term. For example, the normal form of $\lambda x.((\lambda y.y)x)$ is $\lambda x.x$
but NOE won't find it, because it won't reduce the inner redex $(\lambda y.y)x$ which is under the outer $\lambda$-abstraction. So it's not a normalizing reduction strategy.

However, in a typed functional language with data types like Int, if you know that some expression is of such a type, you know that it cannot be a function, so it's enough to restrict reductions to so-called Weak Head Normal Form (which is close to NOE), and it simplifies many things. See also:

http://www.haskell.org/haskellwiki/Weak_head_normal_form
https://en.wikibooks.org/wiki/Haskell/Graph_reduction#Weak_Head_Normal_Form
https://stackoverflow.com/questions/6872898/haskell-what-is-weak-head-normal-form


What is the complexity class most closely associated with what the human mind can accomplish quickly? This question is something I've wondered about for a while.

When people describe the P vs. NP problem, they often compare the class NP to creativity.  They note that composing a Mozart-quality symphony (analogous to an NP task) seems much harder than verifying that an already-composed symphony is Mozart-quality (which is analogous to a P task).

But is NP really the "creativity class?"  Aren't there plenty of other candidates?  There's an old saying:  "A poem is never finished, only abandoned."  I'm no poet, but to me, this is reminiscent of the idea of something for which there is no definite right answer that can be verified quickly...it reminds me more of coNP and problems such as TAUTOLOGY than NP or SAT.  I guess what I'm getting at is that it's easy to verify when a poem is "wrong" and needs to be improved, but difficult to verify when a poem is "correct" or "finished."

Indeed, NP reminds me more of logic and left-brained thinking than creativity.  Proofs, engineering problems, Sudoku puzzles, and other stereotypically "left-brained problems" are more NP and easy to verify from a quality standpoint than than poetry or music.

So, my question is:  Which complexity class most precisely captures the totality of what human beings can accomplish with their minds?  I've always wondered idly (and without any scientific evidence to support my speculation) if perhaps the left-brain isn't an approximate SAT-solver, and the right-brain isn't an approximate TAUTOLOGY-solver.  Perhaps the mind is set up to solve PH problems...or perhaps it can even solve PSPACE problems.

I've offered my thoughts above; I'm curious as to whether anyone can offer any better insights into this.  To state my question succinctly:  I am asking which complexity class should be associated with what the human mind can accomplish, and for evidence or an argument supporting your viewpoint.  Or, if my qusetion is ill-posed and it doesn't make sense to compare humans and complexity classes, why is this the case?

Thanks.

Update:  I've left everything but the title intact above, but here's the question that I really meant to ask:  Which complexity class is associated with what the human mind can accomplish quickly?  What is "polynomial human time," if you will?  Obviously, a human can simulate a Turing machine given infinite time and resources.

I suspect that the answer is either PH or PSPACE, but I can't really articulate an intelligent, coherent argument for why this is the case.

Note also:  I am mainly interested in what humans can approximate or "do most of the time."  Obviously, no human can solve hard instances of SAT.  If the mind is an approximate X-solver, and X is complete for class C, that's important.

I don't claim this is a complete answer, but here are some thoughts that are hopefully along the lines of what you're looking for.

NP roughly corresponds to "puzzles" (viz. the NP-completeness of Sudoku, Minesweeper, Free Cell, etc., when these puzzles are suitably generalized to allow $n \to \infty$). PSPACE corresponds to "2-player games" (viz. the PSPACE-completeness of chess, go, etc.). This is not news.

People generally seem to do alright with finite instances of NP-complete puzzles, and yet find them non-trivial enough to be entertaining. The finite instances of PSPACE-complete games that we play are considered some of the more difficult intellectual tasks of this type. This at least suggests that PSPACE is "hitting the upper limits" of our abilities. (Yet our opponents in these PSPACE-complete games are generally other people. Even when the  opponents are computers, the computers aren't perfect opponents. This heads towards the question of the power of interactive proofs when the players are computationally limited. There is also the technicality that some generalizations of these games are EXP-complete instead of PSPACE-complete.)

To an extent, the problem sizes that arise in actual puzzles/games have been calibrated to our abilities. 4x4 Sudoku would be too easy, hence boring. 16x16 Sudoku would take too much time (not more than the lifetime of the universe, but more than people are generally willing to sit to solve a Sudoku puzzle). 9x9 seems to be the "Goldilocks" size for people solving Sudoku. Similarly, playing Free Cell with a deck of 4 suits of 13 cards each and 4 free cells seems to be about the right difficulty to be solvable yet challenging for most people. (On the other hand, one of the smartest people I know is able to solve Free Cell games as though she were just counting natural numbers "1,2,3,4,...") Similarly for the size of Go and Chess boards.

Have you ever tried to compute a 6x6 permanent by hand?

I suppose the point is that if you take natural problems in classes significantly above PSPACE (or EXP), then the only finite instances that people are capable of solving seem to be so small as to be un-interesting. Part of the reason "natural" is necessary here is that one can take a natural problem, then "unnaturally" modify all instances of size $< 10^{10}$ so that for all instances a human would ever try the problem becomes totally intractible, regardless of its asymptotic complexity.

Conversely, for problems in EXP, any problem size below the "heel of the exponential" has a chance of being solvable by most people in reasonable amounts of time.

As to the rest of PH, there aren't many (any?) natural games people play with a fixed number of rounds. This is also somehow related to the fact that we don't know of many natural problems complete for levels of PH above the third.

As mentioned by Serge, FPT has a role to play here, but (I think) mostly in the fact that some problems naturally have more than one "input size" associated with them.


A "simple" language outside $CFL \cup coCFL$? I am looking for a language L with the following properties:

L should not be context-free.
L's complement should not be context-free. (Everything you see in textbooks as prime examples of non-context-free languages seem to fail this second requirement.)
L shouldn't be too hard, For example, I know that undecidable languages fit the first two requirements, but what I want is a simpler language which can be recognized by a slightly "improved" automaton model, e.g. a probabilistic pushdown automaton.

How about $L:=\{a^{n^2}\mid n\in\mathbb{N}\}$? It is easy to see that $L$ and its complement are not regular, and hence (as we are dealing with a unary alphabet) not context-free.


Justifying simplifying assumption about message distributions for perfectly secret encryption? I am currently reviewing my way through Katz and Lindell's Intro to Modern Cryptography, and have found the following question early in the book (exercise 2.6) surprisingly difficult to answer cleanly:

  Say encryption scheme (Gen,Enc,Dec) satisﬁes Deﬁnition 2.1 for all distributions over
  $\mathcal{M}$ that assign non-zero probability to each $m\in \mathcal{M}$ (as per the simplifying convention used in this
  chapter). Show that the scheme satisﬁes the definition for all distributions over $\mathcal{M}$ (i.e. including those
  that assign zero probability to some messages in $\mathcal{M}$). Conclude that the scheme is also perfectly secret
  for any message space $\mathcal{M}' \subset \mathcal{M}$

Where $\mathcal{M}$ is the message space the encryption scheme is defined over, and def 2.1 is

  An encryption scheme (Gen,Enc,Dec) over a message space $\mathcal{M}$ is perfectly secret if for
  every probability distribution over $\mathcal{M}$, every message $m \in \mathcal{M}$, and every ciphertext $c \in \mathcal{C}$ for which
  $\Pr[C = c] > 0$ :
  $\Pr[M = m \mid C = c] = Pr[M = m]$

Maybe I am just missing something really basic, does anyone have a simple solution?

My initial crack at a solution is the following, please let me know what you think

Fix an encryption scheme (Gen, Enc, Dec) satisfying definiton 2.1 for all distributions over
$\mathcal{M}$ that assign non-zero probability to each $m\in
\mathcal{M}$. Fix a distribution $p_{\mathcal{M}}$ over $\mathcal{M}$
for which $\exists m \in \mathcal{M}$ such that $p_{\mathcal{M}}(m) = 0$. Let $N$ denote the set of all such $m$. To avoid triviality, assume $\exists$ at least 2 messages $m_0, m_1 \in \mathcal{M}$ such that $p_{\mathcal{M}}(m_0) > 0$ and $p_{\mathcal{M}}(m_1) > 0$.

Now, we let $p^* = p_{\mathcal{M}}(m_0)$, and create an "altered"
distribution as follows. Let $p'_{\mathcal{M}}(m) =
p_{\mathcal{M}}(m)$ for all $m \in \mathcal{M} \setminus (N \cup
\{m_0\})$, and let $p'_{\mathcal{M}}(m) = \frac{p(m_0)}{| N \; \cup \;
  \{m_0\} |}$ (that is, the altered distribution is the same as the
original, except it distributes the probability $p_{\mathcal{M}}(m_0)$
evenly amongst $m_0$ and all the messages in $N$). For notational
convenience, let $N' :=  N \; \cup \;
  \{m_0\} $.

Now,
$p'_{\mathcal{M}}$ is a distribution in which all messages have
non-zero probability, so (Gen, Enc, Dec) is perfectly secret with
respect to this distribution. That is, Gen and Enc define a distribution
over the set of ciphertexts $\mathcal{C}$ such that:

$$p'(M = m \mid C = c) = \frac{p'(M=m, C = c)}{p'(C = c)} = p'(M = m)$$

for all $m \in \mathcal{M}, c \in \mathcal{C}$. (Here $p'$ denotes the
joint probability over messages and ciphertexts determined by the
distribution $p'_{\mathcal{M}}$ over $\mathcal{M}$, the distribution
over keys generated by Gen, and the randomness of Enc). Then, I claim, (Gen,
Enc, Dec) must be perfectly secret with respect to the original
distribution, $p_{\mathcal{M}}$ over $\mathcal{M}$.

Claim 1: For all $m \not \in  N'$, and for all $c \in \mathcal{C}$:
 $$p'(M=m, C=c) = p(M=m,
  C=c)$$
(where $p'$ is as before and $p$ denotes the
joint probability over messages and ciphertexts determined by the
distribution $p_{\mathcal{M}}$ over $\mathcal{M}$, the distribution
over keys generated by Gen, and the randomness of Enc). The reason
this holds is that Gen and Enc act independently of the
  distribution over $\mathcal{M}$. Since $p'_{\mathcal{M}}(m) =
  p_{\mathcal{M}}(m) \forall m \not \in  N'$, the claim follows.

Claim 2: For all $c \in \mathcal{C}$:
$$p(M=m_0, C=c) = \sum_{m \in N'} p'(M=m, C=c) $$
First, we note that for any $c\in \mathcal{C}$ and for any $m \in
\mathcal{M} \setminus N'$, $p(C=c \mid M= m) = p'(C = c \mid M = m)$,
since the randomness of Gen and Enc are completely independent of the
distribution over $\mathcal{M}$, and so the message-conditional
probability of any particular ciphertext is equal. Then, fix $c\in \mathcal{C}$
$$
\begin{align*}
p(M=m_0, C = c) &= p(C=c \mid M=m_0)p(M=m_0) \\
&= p'(C = c \mid M = m_0)p(M = m_0), \text{ by the above discussion} \\
&= p'(C=c)p(M= m_0), \text{ since (Gen, Enc, Dec) is perfectly secret
  for } p'_{\mathcal{M}} \\
&= p'(C=c) \sum_{m \in N'} p'(M = m) \\
&= p'(C=c) \sum_{m \in N'} p'(M = m \mid C = c) \\
&= \sum_{m \in N'} p'(M=m, C=c)
\end{align*}
$$

Thus, since
$$p(C = c) = \sum_{m \in \mathcal{M}} p(M=m, C=c) = \sum_{m
  \in \mathcal{M}} p'(M=m, C=c) = p'(C=c)$$
 we see that the
distribution over ciphertexts remains the same with respect to both distributions
over $\mathcal{M}$. Combined with Claim 1, we see that

$$
\begin{align}
p(M =m \mid C=c) &= \frac{p(M=m, C=c)}{p(C=c)} \\
&= \frac{p'(M=m, C=c)}{p'(C=c)} \\
&= p'(M=m \mid C=c) \\
&= p'(M=m) \\
&= p(M=m)
\end{align}
$$

for all $m \in \mathcal{M} \setminus N'$ and all $c \in
\mathcal{C}$. For $m \in N' \setminus \{m_0\}$,
$$p(M= m \mid C = c) =
0 = p(M=m)$$
.

What remains to be seen is that $p(M=m_0 \mid C =
c) = p(M =m_0)$. This is the case, since for all $c \in \mathcal{C}$
$$
\begin{align}
p(M=m_0 \mid C = c) &= \frac{p(M=m_0, C=c)}{p(C=c)} \\
&= \sum_{m \in N'} \frac{p'(M=m, C=c)}{p'(C=c)}, \text{ by Claim 2} \\
&= \sum_{m \in N'} p'(M=m \mid C=c) \\
&= \sum_{m \in N'} p'(M=m), \text{ since (Gen, Enc, Dec) is
  perfectly secret w.r.t }p'_{\mathcal{M}}\\
&= p(M=m_0), \text{ by definition of }p'_{\mathcal{M}}
\end{align}
$$
And so the claim is proven.


Density of distinct satisfying assignments for uniquely satisfiable formulas Motivated by the NP-completeness of Another-SAT problem, Another-3SAT={$(\phi, m)$: 3CNF formula $\phi$ has a satisfying assignment different from $m$ }, Let us consider a function from all uniquely satisfiable Horn 3SAT formulas on $n$ variables to binary strings of length $n$ (representing unique solutions). I'm interested in the density of the range of this function. A set is sparse if the number of strings in the set of length $n$ is bounded by a polynomial in $n$ otherwise it is dense.

What is the best known lower-bound for the asymptotic growth rate of the number of distinct satisfying assignments for uniquely satisfiable Horn 3SAT formulas on $n$ variables? Is this set dense?

EDIT: Thanks to Tsuyoshi,I realized that the original question had a mistake. So I changed the question to be about uniquely satisfiable Horn 3SAT.

If I understand your question correctly, you are asking for asymptotic growth of $f:\mathbb{N} \to \mathbb{N}$ such that $f(n)=k$ iff there are $k$ different 3-CNF formulas on $n$ variables such that each of them has a unique satisfying assignment. As Tsuyoshi Ito, points out you can construct a 3-SAT instance $\phi$ from a given Boolean string $x=b_{n-1},\dots,b_0$ such that $x$ is the only satisfying assignment of $\phi$. This follows from Cook-Levin, theorem as you can write description of T.M which accepts the input iff the input bit string $y$ is equal to $x$, and then using the Cook-Levin construction convert it into a 3-SAT formula where the variables would correspond to input bits. But size of $\phi$ can be polynomial in $n$ (I am not sure if Tsuyoshi Ito was referring to this construction). Also Valiant-Vazirani lemma which  sates that 3-SAT instance on $n$ variables can be reduced (using a randomized algorithm which succeeds on $\frac{1}{8n}$ fraction of random choices) to U-SAT, can be used to deduce that from a 3-SAT instance $\phi$ on $n$ variable we get at least $\frac{1}{8n}$ 3-SAT instances on $2n$ variables (Valiant-Vazirani lemma uses hash functions, and the number of variables it adds to the formula is $k \in [n]$, which denotes the logarithm of number of satisfying assignments of the old formula, and hence to make the formula obtained by the randomized algorithm in the reduction uniformly on $2n$ variables we'll add clauses involving dummy variables). Hence $f(2n)\geq \frac{1}{8n}2^{r(n}g(n)$ where $g(n)$ is the number of different 3-SAT instances and $r(n)$ is the randomness used by Valiant-Vazirani reduction..


Are the $\lambda_I$-Calculus and the $\lambda_K$-Calculus equivalent? I see here and there mention of the $\lambda_I$-Calculus (in which every variable must be used at least once) and the $\lambda_K$-Calculus (in which a variable can also be unused).  Are they equivalent?  Why has the latter kinda obscured the former?

EDIT

By equivalent, I mean they have the same expressive power, namely, being universal or Turing complete.

You've basically answered the question yourself.
$\lambda K$ is just another name for the standard, untyped lambda calculus.
$\lambda I$ is a strict subset of $\lambda K$.
$\lambda I$ doesn't allow terms where one abstracts over a variable but doesn't use it. So
$$K = \lambda xy.x \in \lambda K$$
but
$$ K \not\in \lambda I$$
Thanks to this restriction, $\lambda I$ has some interesting properties, in particular if $M$ has a normal form then so do all its sub-terms.
Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics contains some notes about $\lambda I$, namely:

... the $\lambda I$ calculus is sufficient to define all recursive functions  (since $K_1 := \lambda xy . yIIx$ satisfies $K_1xc_n = x$ for each of Church's numerals $c_n := \lambda fz . f^n z$ - it is also the case that for each finite set $n$ of nf's, we can find a "local $K$ for $n$" $K_n$ such that $K_nMN = M$ for each $N$ in $n$).
... The $\lambda I$ calculus corresponds to the combinatory logic with primitive combinators $I$, $B$, $C$, and $S$. ...


K-means with centres outside the data? Say we want to split a cube in $\mathbb{R}^{64}$ into 10 pieces.
NN, nearest-neighbor or Voronoi splits,
take 10 cluster centres $c_0, \ldots, c_9$ in the cube,
e.g. from K-means,
then classify a new data point $x$ by finding its nearest centre:
$$\text{NN}( x, c_0, \ldots, c_9 ) \equiv \text{argmin}_j\ \| x - c_j \| \text.$$

Kmeans centres are averages of data points, so fall near the data.
Could allowing centres outside the data give better splits ?
Is there a variant of Kmeans which converges e.g. to SVM weights,
viewed as points in the data space ?

As Suresh Venkat points out, "better" splitting,
better classification, is hard to define.

Since k-means minimizes the within-cluster sum of squares, the cluster centers will always be the mean of the points within that cluster. If you use a different criterion, you are basically using a different method than k-means.


Approximate counting problem capturing BQP In the black-box model, the problem of determining the output of a BPP machine $M(x,r)$ on input $x$ is the approximate counting problem of determining $E_r M(x,r)$ with additive error 1/3 (say).

Is there a similar problem for BQP? This comment by Ken Regan suggests such a problem

You can reduce a BPP question to approximating a single #P function, but with BQP what you get is the difference of two #P functions, call them $f$ and $g$. Approximating $f$ and $g$ separately does not help you approximate $f - g$ when $f - g$ is near zero!

BQP does give you a little help: When the answer to the BQP question on an input $x$ is yes, you get that $f(x) - g(x)$ is close to the square root of $2^m$, where the counting predicates defining $f$ and $g$ have m binary variables after you substitute for $x$. (There are no absolute-value bars; “magically” you always get $f(x) > g(x)$. Under common representations of quantum circuits for BQP, $m$ becomes the number of Hadamard gates.) When the answer is no, the difference is close to 0.

Can you precisely formulate such a problem as close as possible to BQP? I am hoping for something like: given black-box access to functions $f,g$ mapping $X$ to $Y$, with the promise that ..., estimate $f-g$ to within $\varepsilon$.

Emanuele: Unfortunately, we don't know of any black-box problem capturing BQP as simple as the one you mentioned capturing BPP.

Intuitively, this is because it's hard to talk about BQP without bringing in unitarity in one form or another.  The ability to sum both positive and negative numbers is what makes BQP more powerful than BPP, but then unitarity is what makes BQP less powerful than #P! :-)

Having said that, besides the Dawson et al. paper that Martin Schwarz linked to, you should definitely check out this and this by Janzing and Wocjan, which give "surprisingly classical-looking" promise problems that capture BQP.

Also, let S ⊆ {0,1}n, and consider a Boolean function f:S→{0,1}.  Then I have a conjecture from years ago which says that Q(f), the bounded-error quantum query complexity of f, is polynomially related to the minimum degree of a real polynomial p:Rn→R such that

(i) p(x)∈[0,1] for all x∈{0,1}n, and

(ii) |p(x)-f(x)| ≤ ε for all x∈S.

If this conjecture holds, then an "approximate counting problem capturing BQP" would simply be to approximate the value of a polylog(n)-degree polynomial p:Rn→R, at a specified point on the Boolean cube, given that p is bounded everywhere on the Boolean cube.  This might be about as close as one could get to an answer to your question.


Noether’s Normalization Lemma for finite fields My question is about theorems 4.1 and 4.2 in "Geometric Complexity Theory V".

The first theorem states that there exists an EXPSPACE algorithm for constructing h.s.o.p. for $\Delta[\text{det},m]$ (see definitions in the paper) on $\mathbb{C}$ (in fact on an arbitrary algebraically closed  field of characteristic zero).

The second provides a probabilistic poly-time Monte-Carlo algorithm for the same problem.

Can theses results be extended to an algebraic closure of a finite field?

As I understand, it is possible because Hilbert’s Nullstellensatz problem belongs to PSPACE in this case too. Heintz and Schnorr theorem also holds for fields of arbitrary characteristic...

I believe the answer is yes. The only part I haven't checked carefully is:

The argument in the middle of Theorem 4.2 using the complex topology, and the fact that the Zariski closure = complex closure for Zariski-constructible sets over $\mathbb{C}$. This part of the argument should be replaceable by the standard algebraic technique of using Laurent series, though as I said, I haven't checked this carefully.

In Theorems 4.1 and 4.2, it seems the only other place characteristic zero is really used is the $\mathsf{EXPH}$ part of Theorem 4.1 (assuming GRH). This uses Koiran's result that, assuming GRH, Hilbert's Nullstellensatz is in $\mathsf{PH}$. Koiran's result relies pretty heavily on characteristic zero (since it considers the solutions of the system of equations modulo many different primes $p$). This is not needed to get the $\mathsf{EXPSPACE}$ part of Theorem 4.1, however, only the $\mathsf{EXPH}$ part (assuming GRH).


What is the oldest open problem in TCS? This problem is inspired by this MO question, which I thought was very interesting.

  What is the oldest open problem in TCS?

Clearly this question needs some clarification.

First, what is TCS?  I think the existence of odd perfect numbers is not TCS. I would say that Hilbert's tenth problem is TCS. I think problems like "Can we construct X with a ruler and compass" are also TCS, since they are asking for an algorithm in a restricted model of computation. There may be no rigorous way to define what a TCS problem is, but use your judgment. Perhaps one test is "If this gets solved, would it most likely appear in STOC/FOCS? Would the researcher who solved it most likely be a theoretical computer scientist?"

Second, what is "oldest"? I mean oldest by date. The stated date should also be verifiable, but I don't think this should be too hard.

Third, what is an "open problem"? By "open problem", I mean a problem that was specifically considered open at some time. Perhaps it appeared at the end of a paper in the open problems section, or maybe there is evidence that some people worked on it and failed, or maybe there are incorrect proofs in the literature, which suggest that it has been studied. An example of something that doesn't fit this criteria: "The greeks studied objects X and Y. Z is clearly an intermediate object, surely they wondered if it can be constructed." If there's no literature on Z from that time period, then it is not an open problem from that time period.

Fourth, what do I mean by "problem"? I mean a specific "yes/no" question, and not something like "Characterize all the objects X with property Y", because such questions often do not have a satisfactory answer. Quite often there will be disagreement as to whether the question has been resolved. Let's not get into such questions here. If it is not a yes/no question, but it is clear that it is really open, that's fine too. (In case this isn't clear, by "problem" I mean a formally stated problem. Please do not convert some folk legend about gambling in the 16th century to a question about BPP and PSPACE.)

Lastly, since this is not a big-list question, please post an answer only if you think it is older than the answers already posted (or if you think the answers posted do not satisfy some other condition -- like they are not TCS, or they are not open). This isn't an indiscriminate collection of old open problems.

What is the computational complexity of integer multiplication?  Arguably, this question dates back at least to the the 'duplation and mediation' algorithm for integer multiplication described in the Rhind Mathematical Papyrus, which was written circa 1650 BC, but claims to be a copy of a significantly older document.

Admittedly, the Rhind papyrus did not explicitly consider the complexity of is algorithm.  So maybe a better answer is What is the complexity of solving systems of linear equations?  Research into efficient algorithms for solving linear systems dates back at least to Liu Hui's commentary, published in 263 AD, on The Nine Chapters on the Mathematical Art.  Specifically, Liu Hui  compares two variants of what is now recognized as Gaussian elimination, and counts the number of arithmetic operations used by each, with the explicit goal of finding the more efficient method.

Both of these questions are still targets of active research.


Prefix Dictionary Problem in External Memory I'm interested in an external memory data structure able to support the following operations on variable length binary sequences: (1) Insert such a sequence. (2) Given a query sequence, find the longest sequence previously inserted which is a prefix of the query sequence, provided one exists.

In particular, do we need $O(n)$ I/O's for an operation with a sequence of length $n$? (Say, by directly implementing a radix tree in external memory.) Or is there something nice, where we can get $O(n/B)$ I/O's?

You might store $\Theta(B)$ children in every node of a trie with alphabet size $\Theta(B)$ by treating your binary sequences as strings over an alphabet each letter of which takes $\Theta(\lg B)$ bits. This will waste space if your string set is sparse, but I think inserts and prefix searches require $(n/\lg B)$ I/Os in the worst case where $n$ is the length of the longest unique prefix (in the case of insert) or the length of the prefix searched for.

To find the longest sequence with a certain prefix, store with each child pointer the length of the longest descendant string.

If the number of strings you plan to store is $o(2^n)$, you might also be interested in the string B-tree. Insert takes $O(n/B + \log_B k)$ I/Os in the worst-case for a string of length $n$ in a tree containing $k$ strings. Prefix search takes $O((p + occ)/B + \log_B k)$ I/Os in the worst-case, where $p$ is the length of the prefix to search and $occ$ is the number of results of the search. These are both larger than your requested bound ($O(p/B)$ or $O(n/B)$ in this notation), and prefix search isn't exactly what you're looking for, it sounds like, but I think storing the longest descendant length will work in this case.


Finding simple fixed length paths in directed graphs Is there an efficient algorithm to enumerate unique simple fixed-length paths (of size $k$) in directed graphs? What would be its time complexity?

The color coding technique for deciding if a graph contains a $k$-path, presented for example in the book Parameterized Algorithms, can be turned into output-sensitive enumeration algorithm for such paths.

The algorithm works in iterations in which a random coloring of $k$ colors is assigned to the vertices of the graph, and then the paths with distinctly colored vertices are identified by dynamic programming.
In each iteration, compute by dynamic programming the function $P(S, u)$ denoting the number of paths that use the subset $S$ of colors and end in the vertex $u$. Then trace the positive values in this dynamic programming backwards to enumerate the paths. In this way the paths identified by this coloring can be enumerated in $O(2^km + Pm)$, where $P$ is the number of such paths and $m$ is the number of edges.

A path of length $k$ is identified with probability at least $e^{-k}$, so by the coupon collector analysis $O(e^k k \log n)$ iterations is enough to identify all (possibly $n^k$) paths with constant probability. A path of length $k$ is identified with probability at most $O(e^{-k} k)$, so the total expected time complexity of the algorithm is $O((2e)^k km \log n + P k^2 m \log n)$, where $P$ is the number of paths of length $k$.


Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone In Boyd & Vandenberghe's "Convex Optimization", question 2.31(d) asks to prove that the interior of the dual cone $K^*$ is equal to

(1)  $\text{int } K^* = \{ z \mid z^\top x > 0 $ for all $ x \in K \}.$

Recall that the dual cone of a cone K is the set:

$K^* = \{ y \mid y^\top \ge 0 $ for all $ x \in K \}.$

I've spent a solid chunk of time trying to prove this simple and seemingly evident statement about the interior of the dual cone but keep getting stuck on the problem of bounding the inner product of x with a perturbed version of z (details provided below).  Frustratingly, the proof in the book's answer key (available online) takes as given this very fact that that I am stuck on proving.

My work in proving statement (1) is given below.  I hope someone can show me the piece of mathematical technology I'm missing.  Thanks!

Question 2.31(d):

Let $K$ be a convex cone and $K^* = \{ y \mid y^\top x \ge 0 $ for all $ x \in K \}$ be its dual cone.

Let $S = \{ z \mid z^\top x > 0 $ for all $ x \in K \}.$   Show that $S = \text{int } K^*.$

Certainly $S \subseteq K^*.$  Now consider some arbitrary point $z_0 \in S$.  For all $x \in K$ we have $z_0^\top x > 0$.  It's clear that we need to find an $\epsilon$ such that for all $z' \in D(z_0, \epsilon)$,

$~~~~ z'^\top x > 0 $ for all $ x \in K.$

Unfortunately, I don't know how to show $z'^\top x > 0$ for $z' \in D(z_0, \epsilon)$ when $\epsilon$ is chosen sufficiently small.

I do know we can write $z'$ as $z_0 + \gamma u$ where $\|u\| = 1$ and $\gamma \in (0,\epsilon)$.  And I do know that

$~~~~ z_0^\top x - \gamma \|x\| ~\le~ z_0^\top x + \gamma u^\top x ~\le~ z_0^\top x + \gamma \|x\|$.

where $z_0^\top x > 0$ and $\gamma \|x\| \ge 0.$

However, I don't know how to show the critical piece, that

$~~~~ z_0^\top x - \gamma \|x\| > 0$

when $\epsilon$ is chosen sufficiently small since $x$ can range over $K$ and therefore $\|x\|$ can be arbitrarily large.

Frustratingly, the solution in B&V just takes it for granted that for sufficiently small $\epsilon$,

$~~~~ z_0^\top x + \gamma u^\top x > 0$.

I've looked online for some matrix perturbation theory results to apply but nothing I've found has been useful.

Any help is greatly appreciated,

Ted

Arnaud is correct.  The critical piece I was missing is that for any $z$, $z^\top x > 0 \iff z^\top x / \|x\| > 0.$

So pick $z \in S$. Let $x_0 = \text{arg inf } \{ z^\top x \mid x \in \text{cl}(K) \cap \{0\}, \|x\|=1 \}$
and let $c_{x_0} = z^\top x_0 > 0$.  We know $x_0$ exists because the set $\text{cl}(K)\cap \{x \mid \|x\| = 1 \}$ is closed and bounded.

Now let $\varepsilon = c_{x_0} / 2$ so that for any $z' = z + \gamma u$ where  $\|u\|=1$ and  $\gamma \in (0,\varepsilon)$, we have

$~~~~ z'^\top x_0 \ge c_{x_0} - \gamma > c_{x_0} / 2 > 0.$

Furthermore, for any other $x \in \text{cl}(K)\cap \{x \mid \|x\| = 1 \}$ we know

$~~~~ z'^\top x \ge z'^\top x_0 > 0.$

Therefore, for any $x \in \text{cl}(K) \backslash \{0\}$ we have

$~~~~ z'^\top x / \|x\| > 0$

which proves $z'^\top x > 0$ whenever $z' \in D(z,\varepsilon)$.


When can be used the "uncompute garbage" trick in quantum computing? As far as I have understood, "uncomputation" in quantum computing is a way to restore the working memory to its initial state, while keeping the result of the computation in another register. This trick is usually explained as follows:

  Assume you have a classical function $f : \{0,1\}^n \rightarrow \{0,1\}$. Then there exists a unitary $U_f$ that maps state $|x\rangle|0\rangle |0\rangle$ to $|x\rangle |g(x)\rangle |f(x)\rangle$, where $|g(x)\rangle$ is the state of the working space at the end of the computation. Moreover, $|x\rangle |g(x)\rangle |f(x)\rangle$ is a pure state (not a superposition). You can now add an extra register $|0\rangle$ in which the result $f(x)$ of the computation is CNOT at the end, i.e. we get $|x\rangle |g(x)\rangle |f(x)\rangle |f(x)\rangle$. Finally, apply $U_f^{-1}$ to the first three registers of this state so as to obtain $|x\rangle |0\rangle |0\rangle |f(x)\rangle$. The working memory has been cleaned.

I'm fine with this procedure. However, it seems to me that it works because $|x\rangle |g(x)\rangle |f(x)\rangle$ is a pure state. It would also be ok
for a superposition of pure states that all have the same register $|f(x)\rangle$ at the end (before we CNOT). But it doestn't work in the other cases. Consider for instance this circuit:

After the first Hadamard has been applied, $x_1$ contains the result of the computation (it is the same as $|f(x)\rangle$ previously, but now it is
a superposition). It is CNOT with the extra register $x_2$ and then another Hadamard is applied. The final state is $(|00\rangle+|01\rangle+|10\rangle-|11\rangle)/2$.
Obviously, the first qubit has not been restored to its initial state.

My first question is: am I right when I say that the uncomputation trick only works when the register that is copied is not in superposition? My second
question is about the following algorithm taken from this paper from Scott Aaronson:

$\mathcal{Q}_*$ is a quantum circuit that takes some witness $|z\rangle$ as input, and outputs $0$ or $1$. It can be thought as a circuit for QMA,
for which the real input $x$ has been fixed and we want to know if there exists a witness that is accepted with high probability (the idea of this
paper is to only try with pure states witnesses $|z\rangle$). In this context, I don't understand why the "uncompute garbage" step restores the memory.
I think that the register containing the output $b$ is CNOT in an extra register (which will be measured later), but since it's usually a
superposition of $|0\rangle$ and $|1\rangle$ I don't understand why the uncomputation would work.

I think I finally figured out what the answer was :) It seems that the "uncomputation trick" was first used for quantum computing in this paper: Strengths and Weaknesses of Quantum Computing (proof of Theorem 4.14). So basically I was right when I said that it only works for "exact" computation (i.e. the output register that contains $f(x)$ is not in superposition) but it can also be used when the error probability of the algorithm is low (in this case the uncomputation is not perfect, but the amplitude of the error term is low).

Let me explain how it works: we have a quantum algorithm $\mathcal{Q}$ that takes an input $|0\rangle |0\rangle$ and produces a state $|\phi\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle$ where $y$ is the working space and $b_y \in \{0,1\}$ is the output register (the result of the computation). If the computation is "exact" then all the $b_y$ are equal to a same value $b$, i.e. the state is $\sum_y \alpha_y |y\rangle |b\rangle$. We now add an extra register in which we CNOT the result: $\sum_y \alpha_y |y\rangle |b\rangle |b\rangle$. Finally, we can apply $\mathcal{Q}^{-1}$ on the first two registers so as to obtain $|0\rangle |0\rangle |b\rangle$. The uncomputation is exact.

Assume now that there is some error probability $\varepsilon$, i.e. the probability of correctly measuring $b$ is $\sum_{y : b_y = b} |\alpha_y|^2 = 1 - \varepsilon$. Let's add the extra register to CNOT the result and denote $|\phi\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle |b_y\rangle $ (in which some $b_y$ are different from $b$) and $|\phi'\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle |b\rangle$. If we apply $\mathcal{Q}^{-1}$ on the first two registers of $|\phi'\rangle$ we obtain $|0\rangle |0\rangle |b\rangle$ which is what we want. Unfortunately, we only know how to compute $|\phi\rangle$ (in which the last register is a superposition of $b$ and $1-b$). However, note that $\langle \phi | \phi' \rangle = \sum_{y : b_y = b} |\alpha_y|^2 = 1-\varepsilon$. Consequently, the inner product between $\mathcal{Q}^{-1} |\phi\rangle$ and $\mathcal{Q}^{-1} |\phi'\rangle = |0\rangle |0\rangle |b\rangle$ is also $1-\varepsilon$ (inner product is preserved by unitaries), which means that the amplitude of $|0\rangle |0\rangle |b\rangle$ in $\mathcal{Q}^{-1} |\phi\rangle$ is $1 - \varepsilon$. Thus, if $\varepsilon$ is small, then $\mathcal{Q}^{-1} |\phi\rangle$ is close to the correct uncomputed state $|0\rangle |0\rangle |b\rangle$. The uncomputation is almost exact.

I think this is the underlying reasoning in Aaronson's paper when he talks about "uncompute garbage". His circuit $\mathcal{Q}^{\star}$ has a very low error probability (due to an amplification step he performed before) and thus he does not care about the error part in the uncomputation.

There is also this paper: Quantum Entanglement and the Communication Complexity of the Inner Product Function (section 3) for another detailed use of uncomputation.


Limits of variants of Independent Set? Independent Set (IS) is the $\mathsf{NP}$-complete decision problem

Input: graph $G$ with $v=|V(G)|$, integer $k$
Question: is there an independent set $S \subseteq V(G)$ with at least $k$ vertices?

Similarly, we can define $f(v)$-bounded IS as the promise version of IS, where the promise is that $k \le f(v)$.
Note that the function parameter depends only on the number of vertices in the input graph.

It is straightforward to show that when $f(v) = v/c$ for some constant $c$, then $f(v)$-bounded IS remains $\mathsf{NP}$-hard.
This is because IS can be reduced to $f(v)$-bounded IS by blowing up the number of vertices by at most a factor of $c$.
Similarly, when $f(v)=v^{1/c}$ for some constant $c$, then $f(v)$-bounded IS is also still $\mathsf{NP}$-hard, by blowing up the number of vertices by a power of $c$.

On the other hand, when $k$ is a constant, then $k$-bounded IS can be decided in polynomial time by exhaustively checking each of the $\binom{v}{k} = \Theta(v^k)$ different $k$-subsets, in at most $O(v^{k+2})$ steps.

This suggests that there is a spectrum of hardness defined via functions restricting the largest independent set that is sought in any instance.
This is, in fact, the case: Bodirsky and Grohe 2008 (preprint) and Chen, Thurley, Weyer 2008 (preprint) established such results non-constructively via versions of Ladner's theorem, conditional on $\mathsf{P} \ne \mathsf{NP}$.

Keeping in mind that asymptotic behaviour does not induce a total order on functions,

  what is a "smallest" function $f(v)$ such that $f(v)$-bounded IS is $\mathsf{NP}$-hard?

In particular, is there some function $f(v)=o(v^{1/c})$ for every constant $c>0$ for which bounded IS is hard?
(I'd be happy with an argument that is conditional on a common hypothesis such as ETH or $W[1] \ne \mathsf{FPT}$.)

Note that while $f(v) = v^{1/\lg v} = 2$ yields a polynomial upper bound on time, the somewhat faster growing function $f(v)=v^{1/\lg\lg v}$ yields a bound for exhaustive search that is superpolynomial but subexponential.
It would therefore also be interesting to establish whether there is a function $f(v) = \omega(1)$ such that $f(v)$-bounded IS is still in $\mathsf{P}$.

Question 1: For a function $f(n)$ lets say that $f$ is sub-polynomial if $\forall \epsilon > 0, f(n) = O(n^\epsilon)$. The Exponential Time Hypothesis (ETH) states that 3-SAT needs $2^{\epsilon n}$ time for some $\epsilon > 0$. Let's postulate a much weaker version, ``Weak Exponential Time Hypothesis'' (WETH): There exists an $\epsilon > 0$ such that $3$-SAT requires $2^{\epsilon n^\epsilon}$ time.

Claim: If $f$-bounded Independent Set is NP-hard for any sub-polynomial function $f$ then the WETH fails.

Proof: Supose $f$-bounded Independent Set is NP-hard under Turing-reductions for some any sub-polynomial function $f$. Then there exists a constant $c$ and an $O(n^c)$ time algorithm for $3$-SAT with $n$-variables that makes at most $O(n^c)$ oracle calls to $f$-bounded Independent Set with at most $O(n^c)$ vertices.

From this algorithm we make an algorithm for $3$-SAT where the oracle calls to $f$-bounded Independent Set are replaced by the $O(|V(G)|^{k+2})$ time brute force algorithm. The running time of this algorithm is upper bounded by
$O((n^c) \cdot (n^c)^{f(n^c)+2}) = 2^{O(\log n \cdot f(n^c))}$. For any $\epsilon > 0$, pick $\delta = \epsilon / 2c$. Since $f$ is sub-polynomial we have that $f(n^c) = O((n^c)^\delta) = O(n^{\epsilon / 2})$. Therefore the running time of the algorithm is upper bounded by $2^{O(\log n \cdot n^{\epsilon / 2})} = 2^{O(n^{\epsilon})}$, contradicting the WETH.

Question 2: Let's say that $f$ computably tends to infinity if there exists a computable function $g : \mathbb{N} \rightarrow \mathbb{N}$ such that for every $c$ and every $n \geq g(c)$, $f(n) \geq c$.

Claim: If $f$-bounded Independent Set is in P for any function $f$ that computably tends to infinity, then FPT = W[1].

Proof: Assuming the existence of a polynomial time algorithm for $f$-bounded Independent Set we will give an FPT algorithm for Independent Set, proving FPT=W[1].

Given as input $G$ and $k$, set $n = |V(G)|$ and compute $g(k)$. Note that computing $g(k)$ takes time that is only a function of $k$. If $g(k) \leq n$ run the polynomial time algorithm for $f$-bounded Independent Set, this will output the correct answer because $k \leq f(n)$. If $g(k) > n$ then run the brute force $n^{k+2}$ algorithm, this takes time $g(k)^{k+2}$. In total the running time is bounded by $O(n^c + h(k))$ for some constant $c$ independent of $k$ and some function $h$.

Remark: Note that nothing here is specific to Independent Set. The first argument works for any problem with a $O(n^{k^c})$ time algorithm for some $c$, while the second argument works for any decidable problem.


Comparing Shannon-Fano and Shannon coding I am interested in a few algorithms for creating prefix codes:

Shannon coding: we take $l_i=\lceil -\log p_i\rceil$.
Shannon-Fano coding: list probabilities in decreasing order and then split them in half at each step to keep the probability on each side balanced. Then codes/lengths come from resulting binary tree.

My question is whether one of these algorithms always provides a better $L=\sum p_i l_i$? In a few examples I've done, Shannon-Fano seems better. Is this always true? Do you have any references or proofs? I realize these aren't the two best algorithms (Huffman coding is optimal). I'm just interested in comparing them.

Edit: Well, no interest so far? I guess this stuff isn't all that exciting, but I'd still like to know. Here's what I've come up with after some more google searching/playing around with numbers.

Practically, Shannon-Fano is often optimal for a small number of symbols with randomly generated probability distributions, or quite close to optimal for a larger number of symbols. I haven't found an example yet where Shannon-Fano is worse than Shannon coding.

In Shannon's original 1948 paper (p17) he gives a construction (equivalent to Shannon coding above) and claims that Fano's construction (Shannon-Fano above) is substantially equivalent, without any real proof. I haven't been able to find a copy of Fano's 1949 technical report to see whether it has any analysis.

Thomas and Cover's Elements of Information Theory says that Fano codes give $L \leq H +2$ and Shannon codes give $L \leq H+1$. However the reference they give for the Fano code analysis I think applies to alphabetical codes where you're not allowed to reorder the probabilities.

Stefan Moser's Information Theory Lecture Notes (pp 50-59) agree with my historical analysis above and purport to prove that for Fano codes we have $l_i \leq \lceil -\log p_i \rceil$ which would be sufficient to prove they are better than Shannon codes. However I don't follow the proof and I think I have a counterexample:

Take probabilities $(0.4, 0.26, 0.02, 0.02, 0.02, \ldots, 0.02)$ (we have 17 0.02's so that probabilities add to 1). Then Shannon coding has lengths $(2,2,6,6,6,\ldots,6)$ while Fano coding splits between 0.4 and 0.26 and then for the 0.6 probability on the right it splits between the second and third 0.02. Continuing on we see that 0.26 is encoded with a length of 3, larger than Shannon length. However, the average length is still less for Fano than for Shannon (according to my program implementing Fano coding).

So, am I doing something wrong? Can you see how to construct a probability distribution to make Shannon code perform better than Fano, or a way to prove it's not possible?

Unfortunately, I also don't have an exact answer. After an initially wrong statement in my lecture notes, currently I do not provide a good bound on the Fano code (version 3.1 of lecture notes). I do, however, have a proof that shows that the Fano codes has an expected average codeword length of less than H(U)/log(2) + 1 - 2p_{min}. Unfortunately, I only have the proof for the case of a binary code, not a general D-ary code. This is why I haven't included this yet into the lecture notes. But I'm still working on it and hope that I will eventually be able to fix it in my lecture notes.

Note, however, that my result does NOT compare Shannon codes with Fano codes. It only gives a general upper bound on the Fano codes. I think it is very difficult to compare the two codes directly. In particular, I do not understand the proof given above and I have my doubts that it can be made rigorous, particularly not for D>2.


What is known about the effectiveness of reliable computing? How well has the following problem been investigated in TCS?
(I apologize if the problem statement sounds vague!)

Given a Model of Computation MC (Turing Machine, Cellular Automata, Kolmogorov-Uspenskii Machine ... etc.) and a  Model of Noise that could affect the computation of MC, is there a way of recovering from the errors caused by this noise in an effective way? For instance, say some type of noise affects a Turing Machine M, could one devise a Turing Machine M' that simulates M without a major cost and is reliable (which means that M' is tolerant to this noise)?

It seems that some models of computations are better than others in doing this: Cellular Automata for instance.
Any results if the noise is replaced by an adversary model?

Sorry for the tag! I don't have enough reputation to put a suitable tag (reliable-computing, fault-tolerant-computing ... etc.)

While there are some techniques that can be applied to fault-tolerance for all models, how resistant a computational model is to fault tolerance depends on the model. For instance, Peter Gacs has done quite a bit of research with fault tolerance on cellular automata, and he shows that (with a lot of work) you can build fault-tolerant cellular automata.

Von Neumann proved that by using redundancy, you could build a reliable computer out of unreliable components using only logarithmic overhead.

For quantum computation, quantum circuits can be made fault tolerant with polylogarithmic overhead ($\log^c n$ overhead, where finding the correct value of $c$ is still open). Another open question for quantum computation is whether adiabatic quantum computation can be made fault tolerant in a physically reasonable manner (physically reasonable means it is possible that the method leads to a scalable adiabatic quantum computer; for example, you're not allowed to take the temperature to 0 as the size of the computation gets larger).


Lower Bound for the Parity Learning Problem What are known lower bounds for the time and query complexity of the problem of learning parities with an adaptive membership query oracle? To be clear the concept space $C$ is $\{x\in \{0,1\}^n \, \, | \, \,\sum_{i=1}^n x_i = k \}$, and the hypothesis space $\mathcal H$ is $\{0,1\}^n$. Given a bitstring of length $n$ as input, the adaptive membership query oracle returns 1 if the parity of the $k$ effective bits is odd and 0 otherwise.

The question is about recovering with membership queries for which it is well known that O( k log n) queries suffice (via BCH codes see Hoffmeister's paper or my COLT 2005 paper). In terms of lower bounds \Omega(k log n) trivially follows from counting the number of parities and using the fact that they are all completely uncorrelated (basic packing-based lower bound).


Applications of TCS to classical mathematics? We in TCS often use powerful results and ideas from classical mathematics (algebra, topology, analysis, geometry, etc.).

  What are some examples of when it has gone the other way around?

Here are some I know of (and also to give a flavor of the type of results I'm asking about):

Cubical foams (Guy Kindler, Ryan O'Donnell, Anup Rao, and Avi Wigderson: Spherical Cubes and Rounding in High Dimensions, FOCS 2008)
The Geometric Complexity Theory Program.  (Although this is technically an application of algebraic geometry and representation theory to TCS, they were led to introduce new quantum groups and new purely algebro-geometric and representation-theoretic ideas in their pursuit of P vs NP.)
Work on metric embeddings inspired by approximation algorithms and inapproximability results

I am in particular not looking for applications of TCS to logic (finite model theory, proof theory, etc.) unless they are particularly surprising -- the relationship between TCS and logic is too close and standard and historical for the purposes of this question.

Expanders were developed to a large extent in TCS and they have profound connections and applications to mathematics.


complexity of graph 2.5-coloring My question is inspired by this one.  I define 2.5-coloring to be the parameterized problem

Instance: an integer j and an n-vertex non-empty simple graph G

Parameter: integer k

Output: if there is a 3-coloring of G in which at least one of

the colors is used at most  min($\hspace{.03 in}$j,k)  times then YES else NO

.
Since j is part of the input and the only involvement of k is via   min($\hspace{.03 in}$j,k) ,  increasing k

cannot make 2.5-coloring easier.     Even for k=0, that problem is logspace-complete.

For k in nΩ(1), that problem is NP-hard by enlarging 3-coloring instances.

By applying Reingold's result to the bipartite double cover of the subgraph induced by the

non-guessed vertices, 2.5-coloring is in   GC ( max(k$\cdot \hspace{-0.02 in}\lceil \log_2(n)\hspace{-0.02 in}\rceil \hspace{-0.03 in}$,n) , DSPACE(O(log(n))) ) ,

since the verifier has two-way access to the alleged proof.

  Is anything else known about the complexity of 2.5-coloring?

In particular, I'd accept any non-trivial consequence of any answer to any of the following,

since I do not expect anyone to manage to outright answer any of them:

Is 2.5-coloring in  coNTIME$\left(\hspace{-0.02 in}n^{o(k)}\hspace{-0.04 in}\right)\hspace{-0.07 in}\big/\hspace{-0.04 in}$$n^{o(k)}$ ?     Is 2.5-coloring in rational-uniform ACC0?

Is 2.5-coloring with k in no(1) hard for rational-uniform TC0?

Is there a function g in ω(log) such that 2.5-coloring with k in no(1) is GC(g(n),AC0)-hard?

Is 2.5-coloring with k in no(1) hard for  GC ( k$\cdot$O(log(n)) , DSPACE(O(log(n))) ) ?

What about the "infinitely-often" versions of any of those questions,

i.e., for pairs k,n such that k is in no(1) and is arbitrarily large?

(I now realize that one of the questions I gave at the bottom of my OP is trivial,

and for another, a yes answer would have a simple unlikely consequence.

As I stated in my OP, 2.5-coloring is logspace-complete even with k=0,

so it certainly is hard for TC0, and if it's in ACC0 then  ACC0 = logspace .)

More interestingly, I recently learned about the odd cycle transversal problem.  By using Reingold's algorithm as I mentioned in my OP, odd cycle transversal is logspace-equivalent to 2.5-coloring.  Accordingly, this paper yields a significant amount of information

"about the complexity of 2.5-coloring", and this paper gives a faster algorithm for it.


How to show that a type in a system with dependent types is not inhabited (i.e. formula not provable)? For systems without dependent types, like Hindley-Milner type system, the types correspond to formulas of intuitionistic logic. There we know that its models are Heyting algebras, and in particular, to disprove a formula, we can restrict to one Heyting algebra where each formula is represented by an open subset of $\mathbb{R}$.

For example, if we want to show that $\forall\alpha.\alpha\lor(\alpha\rightarrow\bot)$ is not inhabited, we construct a mapping $\phi$ from formulas to open subsets of $\mathbb{R}$ by defining:
\begin{align}
\phi(\alpha) &= (-\infty, 0)
\end{align}
Then
\begin{align}
\phi(\alpha\rightarrow\bot) &= \mbox{int}( [0, \infty) ) \\ & = (0,\infty) \\
\phi(\alpha\lor(\alpha\rightarrow\bot)) &= (-\infty, 0) \cup (0,\infty) \\
  &= \mathbb{R} \setminus {0}.
\end{align}
This shows that the original formula cannot be provable, since we have a model where it's not true, or equivalently (by Curry-Howard isomorphism) the type cannot be inhabited.

Another possibility would be to use Kriepke frames.

Are there any similar methods for systems with dependent types? Like some generalization of Heyting algebras or Kripke frames?

Note: I'm not asking for a decision procedure, I know there cannot be any. I'm asking just for a mechanism that allows to witness unprovability of a formula - to convince someone that it's unprovable.

That a formula is not provable can essentially be done in two ways. With some luck we might be able to show within type theory that the formula implies one which is already known to be not provable. The other way is to find a model in which the formula is invalid, and this can be quite hard. For example, it took a very long time to find the groupoid model of dependent type theory, which was the first to invalidate uniqueness of identity proofs.

The question "what is a model of dependent type theory?" has a somewhat complicated answer. If you ignore certain properties of substitution, a model is a locally cartesian closed category, and that might be the simplest answer. If you want a "real" model, then there are several options, see the nLab page on categorical models of dependent type theory. In any case, the answer is always a bit complicated because dependent type theory is a fairly complex formal system.

If I were to suggest just one article on the subject, I would probably recommend the original paper by Robert Seely, "Locally cartesian closed categories and type theory". If I were to suggest another one, it would probably be one that explains what needs to be corrected in Seely's paper, e.g., Martin Hoffman's "On the Interpretation of Type Theory in Locally Cartesian Closed Categories".

A recent important advance in this area is the realization that homotopy-theoretic models are also models of dependent type theory, see homotopytypetheory.org references. This provides a wealth of possibilities, but one must now learn homotopy theory to get hands on the models.


Literature for restrictions that make NPC-Problems to P The boolean satisfiability problem is in $\mathcal{NPC}$. But if you only get Horn clauses, it is in $\mathcal{P}$.

I've already heard similar statements. Do you know a more general statement when problems in $\mathcal{NPC}$ get to problems in $\mathcal{P}$ because of restrictions?

If something like that does not exist, do you know literature where such restrictions are described?

While there are numerous individual examples of sharp thresholds (2-coloring vs 3-coloring is another one), probably the best structural result along the lines you're looking for is Schaefer's dichotomy theorem.

Roughly speaking, the theorem looks at very general classes of problems (called constraint satisfaction problems) and completely characterizes (merely in terms of the kind of input) when the problem is NP-complete and when it's in P.

I haven't read it, but the linked wikipedia page indicates a recent survey by Hubie Chen that presents this result in a more general framework.


Worst number of questions needed to learn a monotonic predicate over a poset Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by providing one node $x \in X$ and finding out if $P(x)$ holds or not. My goal is to determine exactly the set of nodes $x \in X$ such that $P(x)$ holds, using as few evaluations of $P$ as possible. (I can choose my queries depending on the answer of all previous queries, I am not required to plan all queries in advance.)

A strategy $S$ over $(X, \leq)$ is a function which tells me, as a function of the queries that I ran so far and their answers, which node to query, and which ensures that on any predicate $P$, by following the strategy, I will reach a state in which I know the value of $P$ on all nodes. The running time $r(S, P)$ of $S$ on a predicate $P$ is the number of queries required to know the value of $P$ on all nodes. The worst running time of $S$ is $wr(S) = \max_P r(S, P)$. An optimal strategy $S'$ is such that $wr(S') = \min_S wr(S)$.

My question is the following: given as input the poset $(X, \leq)$, how can I determine the worst running time of the optimal strategies?

[It is clear that for an empty poset $n$ queries will be needed (we need to ask about each single node), and that for a total order around $\lceil \log_2 n \rceil$ queries will be needed (doing a binary search to find the frontier). A more general result is the following information-theoretic lower bound: the number of possible choices for the predicate $P$ is the number $N_X$ of antichains of $(X, \leq)$ (because there is a one-to-one mapping between monotonic predicates and antichains interpreted as the maximal elements of $P$), so, since each query gives us one bit of information, we will need at least $\lceil \log_2 N_X \rceil$ queries, subsuming the two previous cases. Is this bound tight, or are them some posets whose structure is such that learning can require asymptotically more queries than the number of antichains?]

This is not a complete answer, but it's too long to be a comment.

I think I found an example for which the bound $\lceil \log_2 N_X \rceil$ is not tight.

Consider the following poset.  The ground set is $X=\{a_1, a_2, b_1, b_2\}$, and $a_i$ is smaller than $b_j$ for all $i,j\in\{1,2\}$. The other pairs are incomparable.  (The Hasse diagram is a $4$-cycle).

Let me identify the monotone properties with the upsets of the poset.  This poset has seven upsets: $\emptyset$, $\{b_1\}$, $\{b_2\}$, $\{b_1,b_2\}$, $\{a_1,b_1,b_2\}$, $\{a_2,b_1,b_2\}$, $\{a_1,a_2,b_1,b_2\}$, and this poset has seven antichains since the antichains are in one-to-one correspondence with the upsets.  So, $\lceil \log_2 N_X \rceil=\lceil \log_2 7 \rceil = 3$ for this poset.

Now, by adversary argument I'll show that any strategy needs at least four queries (so needs to query all elements).  Let's fix an arbitrary strategy.

If the strategy first queries $a_1$, then the adversary answers "$P(a_1)$ doesn't hold."  Then, we are left with five possibilities: $\emptyset$, $\{b_1\}$, $\{b_2\}$, $\{b_1,b_2\}$, $\{a_2,b_1,b_2\}$.  Thus, to determine which is the case, we need at least $\lceil \log_2 5\rceil = 3$ more queries.  In total, we need four queries.  The same argument applies if the first query is $a_2$.

If the strategy first queries $b_1$, then the adversary answers "$P(b_1)$ holds."  Then, we are left with five possibilities: $\{b_1\}$, $\{b_1,b_2\}$, $\{a_1,b_1,b_2\}$, $\{a_2,b_1,b_2\}$, $\{a_1,a_2,b_1,b_2\}$.  Therefore, we need at least three more queries as before.  In total, we need four queries.  The same argument applies when the first query is $b_2$.

If we take $k$ parallel copies of this poset, then it has $7^k$ antichains, and thus the proposed bound is $\lceil \log_2 7^k \rceil = 3k$. But, since each of the copies needs four queries, we need at least $4k$ queries.

Probably, there is a larger poset with larger gap.  But this argument can only improve the coefficient.

Here, the problem looks to be a situation where no query partitions the search space evenly.  In such a case, the adversary can force the larger half to remain.


Non-metric distances Could anybody suggest practically important distances that are significantly non-metric and are not Bregman divergences? For instance, they are non-symmetric and not equivalent to the Euclidean distance.

Thanks!

For a really thorough listing of various distances, metric or not, that are in use, I recommend Encyclopedia of Distances by Deza and Deza. (It is also available electronically from Springer.) For a really simple example of a family of non-metric distances, you can simply let $p$ be less than 1 for an $L_p$ distance, for example. For a family that is in heavy, actual use, you could look into various forms of weighted edit distance. There's also the cosine measure, Jeffrey divergence, partial Hausdorff distance, dynamic time warping distance, and domain-dependent distances such as the COSIMIR model, all discussed in Skopal's paper on indexing non-metric distances.


Enumerate all solutions of a SAT problem All the #SAT solvers I know, e.g RelSat, C2D, only return the number of satisfiable instances. But I want to know each of those instances?

Is there such a #SAT solver or how I should modify an available #SAT solver to do this?

Thank you.

You are looking for an ALL-SAT or all solutions SAT solver. This is a different problem from #SAT. You do not have to enumerate all solutions to count them.

I do not know of a tool that solves your problem because people add these algorithms on top of existing SAT solvers but rarely seem to release these extensions. Two papers that should help you in modifying a CDCL solver to implement ALL-SAT are below.

Memory Efficient All-Solutions SAT solver and its Application to Reachability, O. Grumberg, A. Schuster, A. Yadgar, FMCAD 2004

Here is a recent article posted on the arXiv.

Extending Modern SAT Solvers for Enumerating All Models, Said Jabbour, Lakhdar Sais, Yakoub Salhi, 2013

You could try contacting these authors for their implementation.


Planar graph via the intersection of fat thingies? There is a beautiful theorem of Koebe (see here) that states that any planar graph can be drawn as kissing graph of disks (very romantic...). (Putting it somewhat differently, any planar graph can be drawn as the intersection graph of disks.)

Koebe theorem is not very easy to prove. My question: Is there an easier version of this theorem where instead of disks one is allowed to use any fat convex shapes (convexity might be open to negotiations, but not fatness). Note, that every vertex can be a different shape.

Thanks...

Clarification: For a shape $X$, let $R(X)$ be the radius of the smallest enclosing ball of $X$, and let $r(X)$ let me the radius of the largest enclosed ball in $S$. The shape $S$ is $\alpha$-fat if $R(x) /r(x) \leq \alpha$. (This is not the only definition for fatness, BTW.)

You didn't say the fat objects had to be two-dimensional, did you? Felsner and Francis prove that it's always possible with axis-parallel cubes in 3d. But, the proof involves Schramm's generalizations of Koebe-Thurston-Andreev, so it's not exactly a simpler result. They also mention along the way that for four-connected maximal planar graphs it's possible to use parallel-sided equilateral triangles.


A search problem and no algorithm for it I would like to learn about the following search problem, in particular, which kind of algorithms exist for it.

Suppose we have a huge search space $S$. For each element $s \in S$, we have the weight function $w(s)$. We start at some element $s_0 \in S$ and want to find an element with very low $w$-value.

How can we traverse this search space? For each element $s_1 \in S$, there exists a set of keys $K_S$, and we have some function $a : S \times K_S \rightarrow S$, that computes a new element $s_2 = a(s_1,k)$ for some $k \in K_S$.

We can evaluate the weight of some element $s$ only once it is given. But computing the weight is expensive, and should be minimalized. In order to find a good choice how to traverse throughout this graph, we are given a heuristic $h(s)$, that is supposed to compute a "good" key.

We know for small changes of the key (say, in Hamming distance), the weight of $w(s)$ does not change to much.

Question: Is such a problem known in theoretical computer science, and does there exist theory for it? In particular I am looking for algorithms for problems like these, and conditions on the heuristic $h$ to provide a "good" heuristic.

The description is deliberately vague, in order to allow for wider range of answers. I think many search algorithms do not apply, because they are too generous with search space evaluation. Maybe the problem is even too ill-posed to be accessible to CST tools.

Thank you very much!

Your description is a bit vague, but the problem you describe seems very similar to the canonical problem defining the complexity class PLS (http://en.wikipedia.org/wiki/PLS_(complexity)). Problems in PLS can be described by an exponentially sized graph that you have access to using two polynomial time algorithms: one for evaluating the weight of a current vertex, and one for directing you to the neighbors of a current vertex. The goal is to find a local-minimum in the graph: any vertex such that none of its neighbors have lower weight.

Complete problems for this class include computing pure strategy Nash equilibria in congestion games (See e.g. here), and no polynomial time algorithms for such problems are known.


Removing all but a few cycles in a graph Let problem $S$ be defined as

  Given undirected graph $G$ and a set
  of cycles $C_1,C_2, \ldots, C_n$ in G,
  find minimum number of vertices that
  need to be deleted to remove all
  cycles in the graph G except the
  specified set.

Surely Problem $S$ is NP-hard, since finding minimum number of vertices required to remove all cycles in G (feedback vertex set) is NP-hard

My question is:

  Is it possible to Reduce Problem S to
  the feedback vertex set problem in an undirected
  or directed graph reduction such that if there exist a solution for problem S of size at most k in G iff there exist a feedback vertex set of size at most k in G'

ksoltys gives a reduction (answer below) from Problem S to feedback vertex set when we are not allowed to pick vertices from the forbidden cycles $C_1,C_2, \ldots, C_n$ .Suppose we are allowed to pick vertices from these forbidden cycle. Is there a reduction such that if there exist a solution for problem S of size at most k in G iff there exist a feedback vertex set of size at most k in G'

I think I have such a reduction for the case when we aren't allowed to break the given cycles. Let $C$ be the set of the vertices belonging to the selected cycles (wlog assume that $G[C]$ is connected), and let $D = V\setminus C$. We cannot remove any vertex from $C$. Let's collapse all the vertices from $C$ into one vertex $c_1$ (of course delete the created loops, but keep the double edges), and create $k$ copies of $c$, with the same neighborhood (so now we have a graph on $\{c_1, \dots, c_{k+1}\} \cup D$). We now search for a feedback vertex set. If I'm not mistaken, instance of feedback vertex set thus created has a solution of size $k$ iff our graph had a solution of size $k$ to our problem.

edit: Answer to Prabu's doubt from the comment

The vertices $v_1$ and $v_4$ would indeed collapse to a vertex $v$ (with all other vertices of the forbidden cycles), but the reduction creates $k+1$ copies of $v$ (let's call them $w_1, ..., w_{k+1}$). So the cycle $P$ is transformed into two families of cycles: $F_1 = \{(w_i, v_2, v_3, w_i): i \in [k+1]\}$ and $F_2 = \{(w_i, v_5, v_6, w_i): i \in [k+1]\}$. To break all the cycles from $F_1$, we would have to delete either all the vertices $w_i$ (but we can't, there's too many of them), or one of the vertices $\{v_2, v_3\}$. Same goes for $F_2$ - so altogether we delete exactly 2 vertices.

Let's now look at our original graph. We have two cycles here, one is $P$, and the other: $(v_1, v_2, v_3, v_4, c_1, c_2, ..., c_l, v_1)$, where $v_4, c_1, ..., c_l, v_1$ is some path from $v_4$ to $v_1$ using only the vertices from the forbidden cycles, which we cannot delete (we assumed that $G[C]$ is connected, if we want to get rid of this assumption, we would have to consider connected components of $C$ and collapse vertices from these components separately). To destroy both of this cycles we would also have to delete one vertex from $\{v_2, v_3\}$ and one from $\{v_5, v_6\}$ (you can easily see this when you draw this graph).

So the reduction did exactly what we wanted in this case.


Describing a grammar and associated parser In the process of writing a Turing machine simulator, I decided on a machine representation in ASCII that closely mirrors Turing's original machine tables. I am interested in the formal categorization of the grammar and the simplest type of parser required to implement it, and in a more formal description of same. The grammar is as follows:

<instruction> ::= <ident> "," <symbol> "," <operation> "," <ident> <EOL>
      <ident> ::= <char>
      <symbol ::= <char> | 'None'
  <operation> ::= <movement> | <write> <movement>
      <write> ::= 'P' <char> | 'E'
    <movement ::= 'R' | 'L'

An example Turing machine table written in this grammar is as follows:

b, None, P0R, c
c, None, R,   e
e, None, P1R, f
f, None, R,   b

It is clear to me that since this grammar is expressible in BNF, it must then be at most context-free, but is there a more accurate (more strict) categorization? The lack of left-recursion implies that it could be parsed with a recursive descent parser, but is there a simpler parser that would be capable of this grammar? How would one describe this grammar and its (simplest) associated parser?

if you don't count rembering the symbols of previous lines it's a regular language here's the regex as I see it (<char> is translated to [a-z])

[a-z]\s*,\s*([a-z]|None)\s*,\s*(R|L|P[a-z](R|L))\s*,\s*[a-z]\n

use capturing groups as necessary ;)


Is a theoretically secure key exchange possible? During a discussion I was wondering if it would be possible to design a theoretically secure key exchange.

In other words: If it is possible to design a key exchange (like Diffie–Hellman) where the communication could not be decrypted by an eavesdropper even if he had a computer with infinite speed and memory.

My question is:

Would this be possible and can this (yes or no) be proven mathematically?

EDIT

After having read some of the answers I want to improve my question a bit:

Is it possible that some sender is sending some information to a receiver over an (insecure) channel not having any common keys nor access to a common source of randomness (or similar) in a way that it is not theoretically possible to "decrypt" the actual information from data transferred over the channel?

After a week of thinking I think I found some proof:

A is some data of the sender (such as a public/private key pair)
B is some data of the receiver
Ds is the data sent by the "sender"
Dr is the data sent by the "receiver"
Fn are mathematical functions
M is the "cleartext message" to be encrypted
The data sent by the "receiver" depends on the data received from the "sender" and from the private data B: Dr = F1(B,Ds)
The data sent by the "sender" depends on the data received from the "receiver", private data and the message: Ds = F2(A,M,Dr)
"Theoretically security" would mean that two different messages M exist which can result in the same data of the set (Dr,Ds); otherwise an attacker could search for all sets (A,B,M) which lead to a given data of (Dr,Ds) - and would know the only possible value of M
Because of Ds = F2(A,M,Dr) this would mean that different values of the set (A,M) must exist that lead to the same Ds (when Dr is given)
This would mean that the receiver (not having any additional information about A but the information contained in Ds) would also not be able to decrypt the message

I'm not sure if this proof is correct.

Can anyone tell me if it is correct?

I believe you are talking about the existence of information-theoretically (unconditionally) secure key agreement schemes. You can prove that such schemes cannot be achieved with only authenticated channels from Alice to Bob and Bob to Alice.

Nevertheless, if Alice, Bob, and Eve are in possession of some sort of correlated randomness, then it may be possible to construct such a scheme.

One such example is when a satellite broadcasts several random bits, and Alice, Bob, and Eve receive the bits through different binary symmetric channels with certain error probabilities. One can prove that, in this case, information-theoretical key agreement is possible, even when Eve's error probability is much lower than Alice's and Bob's.

A classic paper on this topic is "Secret Key Agreement by Public Discussion from Common Information" by Ueli Maurer.


Applications of algebraic geometry in Boolean complexity Representing boolean functions by polynomials or rational functions either perfectly or approximately is an important topic while polynomials and rational functions is the body of algebraic geometry. Why is algebraic geometry not that applicable to this area of complexity theory? Or atleast what are some of the important papers in representing boolean functions that uses algebraic geometry?

In addition to the Geometric Complexity Theory Program already mentioned by Sasho Nikolov (see e.g. here, and - shameless self plug, but has tons of references on uses of AG in complexity - here), there's also:

Work on matrix multiplication (Strassen's work especially come to mind, as well as the more recent GCT-style work of Burgisser and Ikenmeyer, but also some other stuff in between)
Mulmuley's "P vs NC" result (this is a Boolean result - if you need convincing I'm happy to), which can be seen as building off of Ben-Or's sorting lower bound and others
Work on derandomizing polynomial identity testing (several papers of M. Agrawal come to mind). (Which, in retrospect, is deeply related to GCT.)
Coding theory (there's a whole "subfield" on AG codes)


Computational hardness for sampling a uniform matching A famous result of Jerrum, Sinclair, and Vigoda shows that there exists a polynomial-time algorithm which takes a bipartite graph $G$ and produces a random perfect matching $M$ of $G$ (assuming one exists), so that the distribution of $M$ is arbitrarily close to uniform in total variation distance. This is sufficient to give a randomized approximation scheme for the number of perfect matchings of $G$.

Since Valiant has shown that the permanent of a binary matrix is $\#\mathsf{P}$-hard, we do not expect to be able to compute the number of perfect matchings of a bipartite graph $G$ exactly. I suspect that generating a uniformly random perfect matching of $G$ is also hard, but I do not know of any complexity theory evidence for this. So my question is:

  Is there any evidence that sampling a uniformly random perfect matching $M$ of a bipartite graph $G$ is computationally hard?

The important bit that differentiates between this question and the JSV result is that the distribution of $M$ is required to be exactly uniform. Any computational hardness here would have to be conditional, because if we could compute the number of perfect matchings in any bipartite graph, then we could also sample a uniformly random matching.

More generally, how does one show conditional hardness for sampling problems?

Concerning your general question, I think the paper by Aaronson and Arkhipov [1] on boson sampling is a good example. They show that if there exists a classical poly-time algorithm that exactly (or at least "extremely accurate" as they state it) samples from a certain distribution, then the polynomial hierarchy collapses up to some level.

To prove the same thing for an approximate sampling algorithm, they must rely on some unproven conjectures.

[1] Aaronson, Scott, and Alex Arkhipov. "The computational complexity of linear optics." Proceedings of the forty-third annual ACM symposium on Theory of computing. ACM, 2011.


Is the primality problem with unary input NLOGSPACE-Hard? Consider the language $L=\{1^n : n \text{ is prime}\}$. Is this language NLOGSPACE-Hard?

The motivation for this question is that $L$ is a good candidate for reducing to other languages related to my automata research.

This language is in $\mathsf{LOGSPACE}$ via trial division. It is also known logarithmic space is neccessary ([1]). For a generalization to sparse sets, see bounded language complete for NSPACE(log n)?. For hardness in binary case, see Are the problems PRIMES, FACTORING known to be P-hard?.

[1] J. Hartmanis, L. Berman, On tape bounds for single letter alphabet language processing. Theoretical Computer Science vol. 3 http://www.sciencedirect.com/science/article/pii/0304397576900244


Offline multidimensional RMQ/RSQ in query model Problem: In the multidimensional range Max/Sum query problem (RMQ/RSQ)
  you are given a $d$-dimensional array
  with $n$ elements, and given a
  $d$-dimensional box, you wish to
  determine the max/sum of all elements
  in the range (if the elements are from
  semigroup, they have no inverses).

What is the state-of-art best algorithm for offline multidimensional RMQ/RSQ in query model (preprocessing of data allowed in offline, queries asked online)? Is there any gap between RMQ and RSQ in multidimensional case? What theoretical/practical interest does this problem have, if any?

I'm interested in it because looks like the best asymptotics for both RMQ and RSQ was achieved in this paper by Chazelle and Rosenberg in 1989, which was not cited a lot, though the problem looks very natural and interesting. By best asymptotics I mean $O(\alpha^d(m,n))$ query time, where $m$ is the amount of storage available per element, $d$ --- number of dimensions of the array, $\alpha$ --- inverse Ackerman function, $n$ --- number of entries in the array. I suspect that this is mainly because this paper is not very readable in the part where it describes the construction, so implementation of this approach is complicated. So a simpler description of a data structure with the same asymptotics is also very welcome.

So, you are interested in range queries in the "dense case" (an array) as opposed to the case most frequently studied in theory (arbitrary points in space).

The RMQ problem is easier than the semigroup sum problem, and no $\alpha$ is needed. The most recent result I know is: Hao Yuan, Mikhail J. Atallah: Data Structures for Range Minimum Queries in Multidimensional Arrays, SODA 2010

The semigroup sum problem is mainly of theoretical interest, in my opinion (what is a natural semigroup beyond max?). This explains why the Chazelle-Rosenberg paper does not have a lot of citations.


Integer factorization using polynomial whose roots are prime factors Let $n$ be a square-free positive integer, let $n=p_{1}p_{2}\ldots p_{k}$
be the prime factorization of $n$ into $k$ distinct primes $p_{i}$.
For such $n$, define $F_{n}(x)\triangleq\prod_{i=1}^{k}(x-p_{i})$.
That is, $F_{n}(x)\in\mathbb{Z}[x]$ is the monic polynomial whose
roots are distinct prime factors of $n$. If we know $F_{n}(x)$,
we can obviously factorize $n$ in polynomial time. Now suppose that
we are given some partial information on $F_{n}(x)$ instead of complete
$F_{n}(x)$. We would like to know

  What kind of partial information on $F_{n}(x)$ would allow factorization
  of $n$ in polynomial time?

For example, it was demonstrated in SUMS OF DIVISORS, PERFECT NUMBERS
AND FACTORING that knowing just the sum of absolute values of coefficients
of $F_{n}(x)$ is enough to factorize $n$. What other partial information
on $F_{n}(x)$ allows factorization of $n$ in polynomial time?

After seeing comments, I am adding for kind of "partial information" we should be looking for.  As pointed out by @joro, knowing $F_n(1)$ or $F_n(-1)$ allows factorization of $n$. First question is that, does knowing value of $F_n(x)$ at any non-zero integer allow factorization of $n$? Second question is that, does knowing only constant many coefficients of $F_n(x)$ allow factorization of $n$?

Knowing $F_n(1)$ or $F_n(-1)$ gives good randomized polynomial algorithm for the factorization of $n$.

We have $|F_n(1)|=\phi(n)$ and $|F_n(-1)|=\sigma(n)$ by definition.

$\phi(n)$ is Euler's totient function and $\sigma(n)$ is the sum of divisors function.

The paper you link to proves the case for $\sigma(n)$.

The same paper cites that the case for $\phi(n)$ is known
and is derandomized assuming ERH (p. 1).

I am pretty sure both algorithms will be quite fast in practice.


Lambda-Calculus terms that reduce to themselves In my continuing quest to try to learn lambda calculus, Hindley & Seldin's "Lambda-Calculus and Combinators an Introduction" mentions the following paper (by Bruce Lercher) which proves that the only reducible expression that is the same (modulo alpha conversion) to itself is: $(\lambda x.xx)(\lambda x.xx)$.

While I believe the result, I do not follow the argument at all.

It is quite short (less than one paragraph).  Any explanations would be most welcome.

Thanks,

Charlie

First, note that the result states that the only beta redex where the right-hand side is equal (modulo alpha-conversion) to the left-hand side is $(\lambda x. x x) (\lambda x. x x)$. There are other terms that reduce to themselves, having this redex in a context.

I can see how most of Lercher's proof work, though there are points where I can't get past without modifying the proof slightly. Suppose that $(\lambda x. A) B = [B/x] A$ (I use $=$ for alpha equivalence), and as per the variable convention suppose that $x$ does not occur free in $B$.

Count the number of $\lambda$'s in the left-hand side and the right-hand side. The reduction removes one from the redex, plus those of $B$, and adds as many as there are in $B$ times the number of occurrences of $x$ in $A$. In other words, if $L(M)$ is the number of $\lambda$'s in $M$ and $\#_x(M)$ is the number of free occurrences of $x$ in $M$ then $1 + L(B) = \#_x(A) \times L(B)$. The only solution to that Diophantine equation is $\#_x(A) = 2$ (and $L(B)=1$ but we won't use that fact).

I don't understand Lercher's argument for the paragraph above. He counts the number of $\lambda$'s and atomic terms; let's write this $\#(M)$. The equation is $\#(B) + 1 = \#_x(A) \times (\#(B) - 1)$, which has two solutions: $\#_x(A)=2, \#(B)=3$ and $\#_x(A)=3, \#(B)=2$. I don't see an obvious way to eliminate the second possibility.

Let us now apply the same reasoning to the number of subterms equal to $B$ on both sides. The reduction removes one near the top, and adds as many as there are substituted occurrences of $x$ in $A$, i.e. 2. Hence one more occurrence of $B$ must disappear; since the ones in $A$ remain (because $B$ contains no free $x$), the extra occurrence of $B$ on the left-hand side must be $\lambda x. A$.

I don't understand how Lercher deduces that $A$ does not have $B$ as a subterm, but this is not in fact relevant for the proof.

From the initial hypothesis, $[(\lambda x. A)/x] A$ is an application. This cannot be the case if $A = x$, therefore $A$ itself is an application $M N$, with $\lambda x.M N = [(\lambda x. M N)/x] M = [(\lambda x. M N)/x] N$. Since $M$ can't have itself as a subterm, $M$ cannot have the form $\lambda x.P$, so $M = x$. Similarly, $N = x$.

I prefer a proof with no counting arguments. Suppose that $(\lambda x. A) B = [B/x] A$.

If $A = x$ then we have $(\lambda x. A) B = B$, which is not possible since $B$ cannot be a subterm of itself. Thus, since the right-hand side of the hypothesis is equal to an application, $A$ must be an application $A_1 A_2$, and $\lambda x. A = [B/x] A_1$ and $B = [B/x] A_2$.

From the former equality, either $A_1 = x$ or $A_1 = \lambda x. [B/x] A$. In the second case, $A_1 = \lambda x. (\lambda x. A_1 A_2) B$, which is not possible since $A_1 cannot be a subterm of itself.

From the latter equality, either $A_2 = x$ or $A_2$ has no free $x$ (otherwise $B$ would be a subterm of itself). In the latter case, $A_2 = B$.

We have shown that $A = x x$. The right-hand side of the initial hypothesis is thus $B B$, and $B = \lambda x. A$ = $\lambda x. x x$.


Submitting other people's work to the arXiv This is a soft question aimed at establishing what people think is the professional best-practise for submitting unoriginal work on the arXiv.

There is a draft of an article [1] by Robert Szelepcsényi, at his webspace at the University of Chicago, apparently written more than a decade ago during his graduate studies. The work seems to be  correct, modulo some very minor errors, and contains a result that I would like to refer to, independently of what the University of Chicago intends to do with that webspace. It seems to be available only at that single location; and there doesn't seem to be any publicly available works which duplicate his results.

Partly for the sake of ensuring its correctness, I have taken it upon myself to write notes recapitulating the results and motivations of that draft, acknowledging that it is essentially a recapitulation of [1], and which hopefully smooths over some of the roughness present in the existing draft. I can certainly put these notes online on webspace of my own, but at present the arXiv seems to be the most responsible place to submit this draft for future reference.

Question.

Assuming correct attribution, and granted that these results are not widely available otherwise, is there any particular reason that I should not submit my draft of Szelepcsényi's results on the arXiv?

[1] Logspace MOD Classes with Composite Moduli (Preliminary Version) — Postscript File

This should be perfectly acceptable if it is framed as an exposition article. There is a long tradition of expository articles in mathematics (one example that comes to mind is Thurston's exposition of a method developed by Conway to determine if the plane can be tiled by a given shape, see here). Just make sure that the abstract and the introduction convey that all you're doing is to explain Szelepcsényi's proof.


Sorting using read-only stacks Consider the following setting:

we are given a stack $s$ which contains $n$ items.
we can use a constant $O(1)$ number of extra stacks.
we can apply the following operations on these stacks:

check if a stack is empty,
compare the top items of two stacks,
delete the top item in a stack,
print the top item in a stack,
copy the top item of a stack into another stack,
copy the content of one stack to another stack.

Note that these are the only operations that are permitted.
We cannot swap items and
we are not allowed to push any item onto any of the stacks
with the exception of copying the top item into a stack
(after which the previous content of the target stack is discarded and
it will only contain the copied item).

Here is an algorithm to sort the stacks with $O(n^2)$ comparisons:

last := empty
for i from 1 to n
  min := empty
  w := s
  while w is not empty
    if w.top > last and w.top < min
      min := w.top
    delete w.top
  print min
  last := min

Can we do better?

  Is there a program that prints the sorted list of the items in the stacks
  using only $O(n\log n)$ comparisons?

I think I can now demonstrate a nontrivial lower bound. The idea is to implement any such program with a family of comparison branching programs. The `read-only' assumption means that our family of branching programs uses little, i.e. $O(\log n)$, space. Then we apply the lower bound $ST=\Omega(n^2)$ proved by Borodin et al. in "A Time-Space Tradeoff for Sorting on non-oblivious Machines." This gives us a $n^2/\log n$ lower bound for the time.

In a bit more detail: We can dispense with operation 5 above. Loosely speaking, if we can already compare the heads of two lists and print the head of a list, then there is no need for us to isolate the head of a list on a particular register. Assuming this, we see that every register in the machine only ever stores a final substring of the input.

Suppose our register program has $\ell$ lines of code and $k$ registers, $X_1,\dots,X_k$.

Fix $n$. We construct the comparison branching program for strings of length $n$ as follows. Create a node for each tuple $(i,d_1,\dots,d_k)$ where $1\le i\le \ell$  and $0\le d_1 ,\dots, d_k \le n$. The idea is, computations in the register machine correspond to paths in the branching program, and we're at node $(i,d_1 ,\dots, d_k)$ if we're at line $i$ in the register machine and the length of the string stored in $X_i$ is $d_i$. Now, we have to define the directed edges of the branching program

If line $i$ is of the form

if $X_u<X_v$ then goto $i_1$ else goto $i_2$

then for all $d_1,\dots,d_k$, node $(i,d_1,\dots,d_k)$ is labelled by comparing the $d_u$-th and $d_v$-th element of input, and having the "true" edge go to $(i_1,d_1,\dots,d_k)$, and the "false" edge to $(i_2,d_1,\dots,d_k)$.

If line $i$ is of the form

$X_1 \leftarrow tail(X_2)$, goto line $i'$

then there is an arrow from any node $(i,d_1,\dots,d_k)$ to $(i',d_2-1,\dots,d_k)$.

If line $i$ is of the form

$print(head(X_u))$, goto line $i'$

then there is an arrow from any node $(i,d_1,\dots,d_k)$ to $(i',d_1,\dots,d_k)$ which is labelled by the $d_u$-th node of the input.

Hopefully these examples make it clear how I intend to construct my branching program. When all is said and done, this branching program has at most $\ell\cdot n^k$ nodes, so it has space $O(\log n)$


How do models of hypercomputation overcome the Halting Problem? Hypercomputation refers to models of computation that are not possible to simulate using Turing machines.  (Hypercomputers are not necessarily physically realisable!)  Some hypercomputers have access to a resource that allows the Halting Problem for standard Turing machines to be solved.  Call this a "superpower": a hypercomputer with a superpower can decide whether any standard Turing machine terminates.

  What kinds of "superpowers" do hypercomputers use?

Ed Blakey's thesis sets up a formal framework to classify some of the major kinds of resources used in hypercomputing, but it does not try to provide a comprehensive survey of superpowers.  I am not interested in a list of hypercomputers (there is a nice list in the Wikipedia article), but in understanding what "special sauce" each model uses, perhaps thought of as a unique kind of resource.

This question is inspired by How fundamental is undecidability?.  Also related is What would it mean to disprove Church-Turing thesis? which generated lots of interesting discussion, and Are there any models of computation currently being studied with the possibility of being more powerful than Turing Machines?.

In the paper On the power of multiplication in random access machines
 it has been proven by Hartmanis and Simon that, if we add unit cost multiplication instruction in a RAM (called MRAM) then for this model P = NP. In addition the languages decided in polynomial time in the MRAM model are exactly the languages in PSPACE.

As stated in the paper, this results shows that multiplication have the same complexity as addition iff P = PSPACE.

A more related result I have heard of, is that if we add a division instruction with infinite precision in a RAM then we can solve undecidable problems. However I could not find the paper that proves this result. If anyone is familiar with it please comment and I will update the answer.