Can every distribution producible by a probabilistic PSpace machine be produced by a PSpace machine with only polynomially many random bits? Let $M$ be a probabilistic Turing machine with a unary input $n$ whose
space is bounded by a polynomial in $n$ and
its output is a distribution $D$ over binary strings.
Note that the number of random bits that $M$ can use can be exponential in $n$.

Can $D$ be "approximated" by
a probabilistic polynomial space-bounded Turing machine
which uses only a polynomial number of random bits?

More formally,

  Let $M$ be a TM with space bound $s$.
  Is there a probabilistic Turing machine $N$ using poly(s) space and random bits with the following property:
  $$\forall k<s \ \left(Pr[M = x] > 2^{-k} \implies
Pr[N = x] > 2^{-k - O(\log s)} \right)$$

Yes.

I took the four screenshots  0,1,2,3  of this answer in case is doesn't render correctly.

Alexey did not specify that the outputs are bounded-length (that was edited in by Kaveh),

so I do not assume that.    Note that  L $\subseteq$ NL $\subseteq$ NC2 $\subseteq$ DSPACE$\hspace{-0.02 in}\left(\hspace{-0.04 in}O\hspace{-0.05 in}\left(\hspace{-0.04 in}(\hspace{.02 in}\log(n)\hspace{-0.03 in})^2\right)\hspace{-0.03 in}\right)$ .

In this answer, "strings" without further clarification may continue infinitely to the right.

The part of this answer between here and the at-symbol applies

to all probabilistic automata with at most $C$ configurations;

even those with, for example, irrational transition probabilities.

Consider any positive integer $j$. $\;\;\;$ Since probabilities are non-negative and add to one,

there are less than $j$ $x$s such that $\: 1/j < \operatorname{Pr}[\text{Automaton outputs }x] \;$. $\;\;\;$ Consider any such $x$.

For strings $s$, say a configuration is bad for $s$ if the probability of the automaton outputting $s$

from the configuration is at most $1/j$, and good for $s$ otherwise. $\:$ Say a configuration

is good if the configuration is good for at least one suffix of $x$, and bad otherwise.

$\operatorname{Pr}[\text{Automaton outputs }x \;\; | \;\; \text{Automaton reaches a bad configuration}]$
$\leq$
$1/j \: < \: \operatorname{Pr}[\text{Automaton outputs }x] \;\;\;$,

so it's possible for the automaton to output $x$ without reaching any bad configuration.

Probabilities are non-negative and add to one, so any given configuration is good

for less than $j$ strings. $\;\;\;$ The automaton has at most $C$ configurations, so there are

less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$ strings for which there exists a configuration which is good for the string.

Since it's possible for the automaton to output $x$ while remaining in

good configurations, $x$ has less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$ distinct non-empty suffixes.

Thus, either $x$'s length is less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$ or $\big[x$ is eventually-periodic and the length

of [the pre-periodic part concatenated with the initial period] is less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \hspace{.02 in}\big]$.

Regard the former case as having period zero, so both of those cases are

covered by "pre-periodic part and initial period, each with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \:$".

Now, choose a family $H$ of hash functions with short output and domain equal to

$\big[$the set of strings with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j \hspace{.02 in}\big]$, $\:$ such that for all distinct equal-length

elements $x_0$ and $y$ of their domain, if  $y\neq x$  then $\;\;\; \operatorname{Pr}_{h\leftarrow H'}[h(\hspace{.03 in}y) = h(x_0)] \: \leq \: 1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in}) \:\:\:\:$.

Let $x_0$ and $x_1$ be the pre-periodic part and initial period respectively of $x$.

For all strings $y_0$ and $y_1$ whose lengths are at most the lengths of $x_0$ and $x_1$ respectively,

$\operatorname{Pr}_{h\leftarrow H}\hspace{-0.06 in}\big[\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$

$\text{and } \: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle \neq \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h(\hspace{.03 in}y_0),h(\hspace{.03 in}y_1)\rangle = \langle h(x_0),h(x_1)\rangle\big]$
$\leq$
$\operatorname{Pr}_{h\leftarrow H}[\langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle \neq \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h(\hspace{.03 in}y_0),h(\hspace{.03 in}y_1)\rangle = \langle h(x_0),h(x_1)\rangle]$
$\leq$
$1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$

.   Since doing so will correspond to taking a weighted average, that will still apply when

$y_0$ and $y_1$ are chosen from a distribution independently of $h$.  In particular, it will still apply when

$\langle \hspace{.03 in}y_0,\hspace{-0.03 in}y_1\rangle \:$ is chosen according to the automaton's outputs so that $y_0$ is the first up-to-length($x_0$)

bits of the output and $y_1$ is the next up-to-length($x_1$) bits of the output.  Since the random

choice of $h$ from $H$ also corresponds to a weighted average, there is an $h$ from $H$ such that

$\operatorname{Pr}_{\langle \hspace{.02 in}y_0,\hspace{.02 in}y_1\hspace{-0.02 in}\rangle \leftarrow \text{Automaton}}\hspace{-0.05 in}\big[\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$

$\text{and } \: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle \neq \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h(\hspace{.03 in}y_0),h(\hspace{.03 in}y_1)\rangle = \langle h(x_0),h(x_1)\rangle\big]$
$\leq$
$1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$

.   Let $h_0$ be such an $h$.

$1/j \: < \: \operatorname{Pr}[\text{Automaton outputs } x] \;\; \leq \;\; \operatorname{Pr}_{\langle \hspace{.02 in}y_0,\hspace{.02 in}y_1\hspace{-0.02 in}\rangle \leftarrow \text{Automaton}}[\langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle = \langle x_0,\hspace{-0.02 in}x_1\rangle]$
$=$
$\operatorname{Pr}_{\langle \hspace{.02 in}y_0,\hspace{.02 in}y_1\hspace{-0.02 in}\rangle \leftarrow \text{Automaton}}\hspace{-0.05 in}\big[\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$

$\text{and } \: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle = \langle x_0,\hspace{-0.03 in}x_1\rangle \: \text{ and } \: \langle h_0(\hspace{.03 in}y_0),h_0(\hspace{.03 in}y_1)\rangle = \langle h_0(x_0),h_0(x_1)\rangle\big]$

,   so the probability of $\: \langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle = \langle x_0,\hspace{-0.03 in}x_1\rangle \:$ conditioned on

$\langle \operatorname{length}(\hspace{.03 in}y_0),\operatorname{length}(\hspace{.03 in}y_1)\rangle = \langle \operatorname{length}(x_0),\operatorname{length}(x_1)\rangle$

$\text{and } \; \langle h_0(\hspace{.03 in}y_0),h_0(\hspace{.03 in}y_1)\rangle = \langle h_0(x_0),h_0(x_1)\rangle$

is greater than $2/3$.  In particular, for each element $i$ of

$\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\operatorname{length}(x_0)\hspace{-0.03 in}+\hspace{-0.03 in}\operatorname{length}(x_1)\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$, conditioned on the same event,

$2/3$$<$
$\operatorname{Prob}[\text{Automaton gives more than } i \text{ bits of output and}$

$\text{the }i\text{-th bit of the output equals the }i\text{-th bit of } x_0$||$x_1]$

.     Multiplying the number of states by  $4\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j$  lets the automata track $i$ and

for hard-coded $i_0$ from $\{0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\operatorname{length}(x_0)\hspace{-0.03 in}+\hspace{-0.03 in}\operatorname{length}(x_1)\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$, record the $i_0$-th output.

Now, for efficiency's sake, we must turn back to the hash family $H$.  Let $p$ be the

smallest prime that is not less than  $2\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j^{\hspace{.02 in}2}$ ,  and then use wikipedia's string hashing method.

For input length of at most one block, collisions are simply impossible.    Otherwise,

$\text{maximum_collision_probability} \leq \text{degree}\hspace{.02 in}/p \; = \; ((\text{number_of_blocks})\hspace{-0.04 in}-\hspace{-0.05 in}1)/p \; \leq \; (\lceil (\text{input_length})/(\text{block_size})\rceil\hspace{-0.04 in}-\hspace{-0.05 in}1)/p \; \leq \; (\lceil (\text{input_length})/1\rceil \hspace{-0.04 in}-\hspace{-0.04 in}1)/p \; = \;$

$(\lceil \text{input_length}\rceil \hspace{-0.04 in}-\hspace{-0.05 in}1)/p \; < \; (\text{input_length})/p < (C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j)/p \leq (C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j)/(2\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j^{\hspace{.02 in}2}) \; = \; 1/(2\hspace{-0.04 in}\cdot \hspace{-0.04 in}j)$

.     Thus wikipedia' string hashing method has small enough collision probability for this answer.

By Bertrand's postulate, $p$ will be less than  $4\hspace{-0.04 in}\cdot \hspace{-0.04 in}C\hspace{-0.04 in}\cdot \hspace{-0.04 in}j^{\hspace{.02 in}2}$ ,  so for $j$ given in unary, logspace can find $p$

by trial division and do the arithmetic operations mod $p$.    In particular, NC2 can do the same.  Observe that wikipedia's string hashing method takes the input as a stream, so

(for $j$ given in unary) NC2 can find a deterministic finite automata for each hash in the $p$ family.

Thus, by a product construction, NC2 can get automata which will use any given

hash in the $p$ family to test both parts of the underlying automata's output -

If the underlying automaton would halt without having produced output or finish a part

not matching the target hash values, then the resulting automaton will enter a reject state;

if the underlying automaton gives enough output without either of those happening,

then the resulting automaton goes to Finalize0 or Finalize1,

determined by the value of the bit the underlying automaton was recording.

By the conditional probability I went over earlier, there is an $h_0$ is the $p$ family such that,

when that's done with $\operatorname{length}(x_0)$ and $\operatorname{length}(x_1)$ and $h_0(x_0)$ and $h_0(x_1)$, for each element $i_0$$\{0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\operatorname{length}(x_0)\hspace{-0.03 in}+\hspace{-0.03 in}\operatorname{length}(x_1)\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$, the probability of the resulting automaton finalizing the $i_0$-th bit of  $x_0$||$x_1$  is more than twice its probability of finalizing the other bit.    Clearly, for each such automaton, there is at most one pair  $\langle \hspace{.02 in}y_0,\hspace{-0.03 in}y_1\rangle$  of $\big[$strings with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j\big]$ satisfying the previous sentence's condition.    Furthermore, the $p$ family and its outputs

are given by integers mod $p$ and the lengths are restricted to being less than  $C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j$ ,

so for $j$ in unary, NC2 can output a list of all such automata.
@
Now, assume that all probabilistic transitions are coin-flips, i.e.,

equal probability of going to each of 2 possible next-states:

There are only polynomially many possibilities for the workspace's contents, so the automata's sizes are polynomial.    Each transition probability is in {0,1/2,1}, so by Lemma 6.1, (for $j$ given

in unary) NC2 can determine whether there is a pair of $\big[$strings with length less than $\: C\hspace{-0.04 in}\cdot \hspace{-0.03 in}j\big]$ satisfying the condition in the paragraph just-before the at-symbol, and if so, find that pair.

There's almost certainly a simpler method, but as a brute-force for determining whether-or-not

the strings represented by such pairs are equal, NC2 can build the deterministic finite automata from those representations which give one output per step, construct their product, and check

whether-or-not that product automata reaches a state from which [exactly one halts or they

give different outputs].  Thus NC2 can (for $j$ given in unary) output a list of pairs such that

[each string which the Turing machine has probability greater than $1/j$ of outputting]

is the eventually-periodic string encoded in the obvious way by exactly one of the pairs in the list.

Now it's time to show that NC2 can find the probabilities of those strings being outputted.

We start by dealing with no-further-output scenarios.  Non-deterministic logspace can check whether-or-not there is a sequence of random bits which will cause further output from a given configuration, so NC2 can replace entering those configurations with entering the halt state.

The remaining configurations all have some way of giving output.  Since loops can be removed from any such way, it must be that for each non-halt configuration, there's a way to give output with at most number_of_configurations transitions.  Since non-zero transition probabilities are at least 1/2, one will have that for each non-halt configuration, the probability of giving output from there in

at most most number_of_configurations transitions is at least 1/(2^(number_of_configurations)).

That remains the case as long as it stays in configurations which weren't replaced with halt,

so for all positive integers t, the probability of it doing so for t steps without giving output

is at most (1-(1/(2^(number_of_configurations))))^(floor(t/(number_of_configurations)))

That goes to zero as t goes to infinity, so for each time and configuration-at-that-time, the probability of [giving no further output but not halting] is zero.  By countable additivity, the previous sentence remains true when "for each time and configuration-at-that-time," is removed, so the probability of [the total output being finite without the automata ever entering its halt state] is 0.

For infinite eventually-periodic strings, apply the previous paragraph, then further modify

the automaton to have it track its output's location in    the pre-periodic part  /  the period  ,

as applicable, and halt if it would output something other than the eventually-periodic

string's next bit.        The only other way for it to not output the whole eventually-periodic string

is its output being finite, so by the previous paragraph, the probability of it outputting the

eventually-periodic string is one minus the probability of it reaching the halt configuration.

For finite strings, apply 2 paragraphs ago then further modify the automaton

to track [the amount of output it has given, up to the string's length, inclusive],

enter an accept state if has outputted the whole string and would halt (for a reason other than

the following part of this sentence), and halt if it [hasn't finished outputting the string and

would output something other than the next bit] or would output more than the string.

By two paragraphs ago, its probability of outputting the string without entering the accept state is zero, so its probability of outputting the string equals its probability of entering the accept state.

By Lemma 6.1, given $j$ in unary, NC2 can compute those probabilities.  NC2 can also

compare those probabilities to $1/j$, so can strip out the pairs with probability at most $1/j$.

In summary, given $j$ in unary and an automaton whose probabilistic transitions

are coin-flips, NC2 can output a list of triples  $\langle \text{prob},\hspace{-0.02 in}x_0,\hspace{-0.02 in}x_1\rangle$  such that

the pairs formed by taking the right two entries from distinct triples

represent distinct eventually-periodic strings
and
for each such eventually-periodic string, the left entry of its triple

is the probability of the automaton outputting that string
and
each of those probabilities is greater than $1/j$
and
for each string x, if the probability of the automaton outputting $x$ is greater than $1/j$ then

$x$ is eventually-periodic and represented by the right two entries of one of the triples

.  (In light of this paper, I suspect Lemma 6.1 can be improved to put its problem in TC1.

If so, then TC1 can also do everything relevant to this answer that NC2 can do.)

Applying that to the OP's problem:

NC2 can round the probabilities down to fractions with denominator $j$ and remove the denominators.  Since $j$ is in unary, logspace can reduce mod $j$, and thus sample "as close to uniformly as possible" from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,j\hspace{-0.04 in}-\hspace{-0.04 in}2,j\hspace{-0.04 in}-\hspace{-0.05 in}1\}$.     Note that  $2\hspace{-0.05 in}\cdot \hspace{-0.05 in}\lceil \log_2(\hspace{.05 in}j)\rceil$  random bits are enough to make the error less than $1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$.    For the same reason, logspace can use the list of [triples with integer left entries] and the element from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,j\hspace{-0.04 in}-\hspace{-0.04 in}2,j\hspace{-0.04 in}-\hspace{-0.05 in}1\}$ to add the integers, stopping if/when the sum exceeds the element, and then [if that happened then output the eventually-periodic string indicated by the most recent triple's other two elements, else output $\bot$].

Thus NC2 can do those things after it computes the list, so DSPACE$\hspace{-0.02 in}\left(\hspace{-0.04 in}O\hspace{-0.05 in}\left(\hspace{-0.04 in}(\hspace{.02 in}\log(n)\hspace{-0.03 in})^2\right)\hspace{-0.03 in}\right)$

can also do the same things.    That means DSPACE$\hspace{-0.02 in}\left(\hspace{-0.04 in}O\hspace{-0.05 in}\left(\hspace{-0.04 in}(\hspace{.02 in}\log(n)\hspace{-0.03 in})^2\right)\hspace{-0.03 in}\right)$ can use

at most  $2\hspace{-0.05 in}\cdot \hspace{-0.05 in}\lceil \log_2(\hspace{.05 in}j)\rceil$  random bits to sample from a distribution such that, other than $\bot$,

the probabilities for each output are less than $3/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$ away from the original probabilities, and whenever the latter is greater than $1/j$, the resulting probability will be greater than $1/(2\hspace{-0.05 in}\cdot \hspace{-0.04 in}j\hspace{.02 in})$.

Now, plugging in  $j = 2^k$  and [using just $k$ random bits] and $\big[$using the actual input machine's structure as a Turing machine to simulate reading from a $\left(\hspace{-0.04 in}O(S)\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^S\right)$-state automata whose probabilistic transitions are all coin-flips$\big]$ gives a  $O\hspace{-0.04 in}\left(\hspace{-0.03 in}(S\hspace{-0.04 in}+\hspace{-0.04 in}k)^{\hspace{.02 in}2}\hspace{-0.03 in}\right)\hspace{-0.02 in}$-space algorithm that uses $2\hspace{-0.05 in}\cdot \hspace{-0.04 in}k$ random bits to sample from a distribution such that, other than $\bot$, the probabilities for each output are less than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}2^k\hspace{-0.04 in}\right)$ away from the original probabilities, and whenever the latter is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}2^k\hspace{-0.04 in}\right)$, the resulting probability will be at least $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}2^k\hspace{-0.04 in}\right)$.    (Since $2^k$ is a power of two,

$k$ random bits is enough to choose the element from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,j\hspace{-0.04 in}-\hspace{-0.04 in}2,j\hspace{-0.04 in}-\hspace{-0.05 in}1\}$ perfectly uniformly.)

That achieves what you're after.


A clear and rigorous explanation of critical pairs and the Knuth-Bendix completion algorithm? I'm looking for an explanation of critical pairs and the Knuth-Bendix completion algorithm that is at once rigorous and of high pedagogical value, i.e. clear, detailed, containing illustrative examples preferably with drawings, and reasonably self-contained. It can be inside a book, an article, lecture notes, website, whatever. Possible languages: English, French, German.

The two obvious references are:

Chapter 7 of Term Rewriting and All That, notable for its pedagogy and accessible examples

Chapter 7 of Term Rewriting Systems, notable for its completeness and attention to detail, though a bit dated at this point I guess.

Note that neither refers to completion as "Knuth-Bendix" completion in the index, since the science of completion has come a long way since it was first introduced. This survey by Dershowitz and Jouannaud might be a bit more historical.
It might help to understand what your needs are, since the field is vast, and somewhat technical. Are you trying to use a completion algorithm? Implement it? Adapt it to a specific setting?


Deciding whether an interval contains a prime number What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the interval and $\sim$ hides poly-logarithmic factors in the starting point of the interval; can we do better (in terms of $L$ alone)?

Disclaimer: I'm not an expert in number theory.

Short answer: If you're willing to assume "reasonable number-theoretic conjectures", then we can tell whether there is a prime in the interval $[n, n+\Delta]$ in time $\mathrm{polylog}(n)$. If you're not willing to make such an assumption, then there is a beautiful algorithm due to Odlyzko that achieves $n^{1/2 + o(1)}$, and I believe that this is the best known.

Very helpful link with lots of great information about a closely related problem: PolyMath project on deterministic algorithms for finding primes.

Long answer:

This is a difficult problem, an active area of research, and seems to be intimately connected to the difficult question of bounding gaps between the primes. Your problem is morally very similar to the problem of finding a prime between $n$ and $2n$ deterministically, which was recently the subject of a PolyMath project. (If you want to really dive into these questions, that link is a great place to start.) In particular, our best algorithms for both problems are essentially the same.

In both cases, the best algorithm depends heavily on the size of gaps between the prime. In particular, if $f(n)$ is such that there is always a prime between $n$ and $n + f(n)$ (and $f(n)$ can be computed efficiently), then we can always find a prime in time $\mathrm{polylog}(n) \cdot f(n)$ as follows. To determine whether there is a prime between $n$ and $n + \Delta$, first check if $\Delta \geq f(n)$. If so, output yes. Otherwise, just iterate through the integers between $n$ and $n + \Delta$ and test each for primality and answer yes if you find a prime and no otherwise. (This can be done deterministically, which is why deterministically finding a prime between $n$ and $2n$ is so closely related to determining whether there is a prime in a certain interval.)

If the primes behave like we think they do, then this is the end of the story (up to $\mathrm{polylog}(n)$ factors). In particular, we expect to be able to take $f(n) = O(\log^2 n)$. This is known as Cramér's conjecture after Harald Cramér, and proving it seems very far out of reach at the moment. But, as far as I know, it is widely believed. (One arrives at this conjecture, e.g., from the heuristic that the primes behave like the random set of integers obtained by including each integer $n \geq 3$ independently at random with probability $1/\log n$.)

There are many conjectures that imply the much much weaker bound $f(n) \leq O(\sqrt{n})$, such as Legendre's conjecture. (I'm not aware of any conjectures that are known to imply an intermediate bound, though I imagine that they exist.) And, the Riemann hypothesis is known to imply the similar bound $f(n) \leq O(\sqrt{n} \log n)$. So, if you assume these conjectures, you essentially match Odlyzko's algorithm (up a factor of $n^{o(1)}$) with a much simpler algorithm.

I believe that the best unconditional bound right now is $\widetilde{O}(n^{0.525})$ due to Baker, Harman, and Pintz. So, if you assume nothing, then Odlyzko's algorithm beats the obvious algorithm by roughly a factor of $n^{0.025}$.


Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly? I was reading a paper of Buhrman and Homer “Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy”.

On the bottom of page 2 they remark that the results of Kannan imply that $NEXPTIME^{NP}$ does not have polynomial size circuits. I know that in the exponential time hierarchy, $NEXPTIME^{NP}$ is just $\Sigma_2EXP$, and I also know that Kannan's result is that $\forall c\mbox{   }\exists L\in\Sigma_2P$ such that $L \not\in Size(n^c)$. Of course, Kannan's theorem is NOT saying $\Sigma_2P \not\subset P/poly$ (in order for that to be the case we would need to show that $\exists L\in\Sigma_2P$ such that $\forall c$, $L \not\in Size(n^c)$. However, I don't see how Kannan's result implies that $NEXPTIME^{NP} \not\subset P/poly$?

This version of the answer incorporates feedback from Emil Jeřábek.
As far as I can see, the main twist is that there is a language in $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ of exponential circuit complexity. In particular, fix a binary encoding of boolean circuits and define $L$ as the language defined by

$L_n$ is not decided by any circuit of size $2^{n/2}$, and
any language $L'_n \subseteq \{0,1\}^n$ which precedes $L_n$ lexicographically is decided by some circuit $C$ of size at most $2^{n/2}$,

where the notation $L_n$ means the slice $L_n = L \cap \{0,1\}^n$.
To do this in exponential time with a $\Sigma_2^\mathsf{P}$ oracle, you can use binary search over subsets of $\{0,1\}^n$ (think of them as $2^n$ bit integers) to find the first such set which has circuit complexity $> 2^{n/2}$. You just keep the current guess of $L_n$, and use the oracle to test if there exists a $L'_n \prec_{\text{lex}} L_n$ of circuit complexity at least $2^{n/2}$. Since this gives a machine in $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ which writes down the whole slice $L_n$, clearly we can also decide membership in $L_n$, and, therefore, in $L$.
This is very much as in Kannan's argument, but scaled up and streamlined to use the exponential time. Then you should be able to use a scaled-up version of the Karp-Lipton theorem to show that if $\mathsf{NEXP} \subseteq \mathsf{P/poly}$, then $\mathsf{EXP}^{\Sigma^\mathsf{P}_2} \subseteq \mathsf{NEXP}^{\mathsf{NP}}$, and you can carry out the case analysis in Kannan's proof.


How to find the first $k$ points of high enough level using a priority search tree? In reading Chan's paper,
Closest Point Problems Simplified on a RAM,
the following came up as a sub-problem:

Given a set $P$ of points in the plane, and a query point $q$, find the first $k$ points (ordered by $x$-coordinate) which dominate $q$.

Chan asserts that this query can be answered in $O(\log n + k)$ time using a priority search tree, but doesn't give details, and the details are not clear to me. The traditional query for a priority search tree is a 3-sided range query, but this query is different because we are given a 2-sided range (an upper-right quadrant) and a maximum number of points to report. We should report the $k$ "leftmost" points in the 2-sided range.

The tree is binary and has depth $O(\log(n))$ and the properties that:

for any non-root node $v$, the y-coordinate of $v$ is larger than that of its parent.
for any node $v$, all descendants in the left subtree have x-coordinate smaller than $v$, and all descendants in the right subtree have x-coordinate larger than $v$.

This means that your solution set from which you choose $k$ elements is actually a subtree one side (in the left/right sense) of what remains when a path is deleted, and can be traversed with DFS in $(\log(n)+k)$ time.  Note that the priority search tree may require dummy points at which you root subtrees to keep the depth low.

This paper may give some clarification: http://people.scs.carleton.ca/~michiel/MinMaxPST.pdf


How to use induction without Fixpoint definition in Coq? I want to verify a program written in C. I am using Jessie to translate the (pre/post)conditions of the program to Coq. In Coq I will make a proof. Sometimes I need recursive definitions.

Unfortunately Jessie generates no fixpoint definitions and unfortunately I must use these generated definitions to verify a program.

For example the power function:

Require Export ZArith.
Open Scope Z_scope.

  (*Generated by Jessie from my C program*)
Definition pow : Z->Z->Z.
Admitted.

Definition eq_int_bool : Z -> Z -> bool.
Admitted.

Lemma eq_int_bool_axiom :
  (forall (x:Z), (forall (y:Z), ((eq_int_bool x y) = true <-> x = y))).
Admitted.

Lemma _jc_axiom_sum :
    forall (b:Z),
    forall (e:Z), (pow b e) =
    if (eq_int_bool e 0) then (1)
    else (b * pow b (e-1)).
Admitted.

How can I use the inductive tactics provided in Coq, if I want to prove some features? What can I do in this situation to prove the features? Is it even possible to perform some “complicated” proofs with this sort of definition?
In my Coq proofs I can use all I want, including fixpoint definitions.

You have an equational specification of the power function. You can prove that it's equivalent to some recursively defined function, in that it has the same values whenever the two functions are passed equal arguments. This is called extensional equality of the two functions.

There is a Zpower function in the standard library, defined recursively:

Fixpoint iter_pos (n:positive) (A:Type) (f:A -> A) (x:A) {struct n} : A :=
  match n with
    | xH => f x
    | xO n' => iter_pos n' A f (iter_pos n' A f x)
    | xI n' => f (iter_pos n' A f (iter_pos n' A f x))
  end.
Definition Zpower_pos (z:Z) (n:positive) := iter_pos n Z (fun x:Z => z * x) 1.
Definition Zpower (x y:Z) :=
    match y with
      | Zpos p => Zpower_pos x p
      | Z0 => 1
      | Zneg p => 0
    end.

Here's a quick-and-dirty proof that your function is equal to Zpower for nonnegative exponents.

Lemma neq_int_bool : forall x y, eq_int_bool x y = false <-> x <> y.
Proof.
  intros.
  pose (A := eq_int_bool_axiom x y); clearbody A.
  split; intros.
  intro E; apply <- A in E. assert (false = true); solve [eauto with bool].
  case_eq (eq_int_bool x y); intro E.
  apply -> A in E. elimtype False. solve [auto with bool].
  reflexivity.
Qed.

Lemma pow_x_0 : forall b, pow b 0 = 1.
Proof.
  intros; rewrite _jc_axiom_sum.
  replace (eq_int_bool 0 0) with true. reflexivity.
  symmetry. apply <- eq_int_bool_axiom. reflexivity.
Qed.

Lemma pow_nat_is_power :
  forall b n, pow b (Z_of_nat n) = Zpower b (Z_of_nat n).
Proof.
  induction n; simpl.
  apply pow_x_0.
  rewrite _jc_axiom_sum.
  replace (eq_int_bool (Zpos (P_of_succ_nat n)) 0) with false.
  replace (Zpos (P_of_succ_nat n) - 1) with (Z_of_nat n).
  rewrite IHn; clear IHn.
  rewrite Zpower_pos_nat. rewrite nat_of_P_o_P_of_succ_nat_eq_succ.
  replace (S n) with (1 + n)%nat. 2: solve [auto with arith].
  rewrite Zpower_nat_is_exp.
  unfold Zpower_nat at 1; simpl.
  replace (b * 1) with b. 2: solve [auto with zarith]. f_equal.
  destruct n; simpl.
  reflexivity.
  rewrite Zpower_pos_nat. rewrite nat_of_P_o_P_of_succ_nat_eq_succ. reflexivity.
  rewrite Zpos_P_of_succ_nat. solve [auto with zarith].
  symmetry. apply <- neq_int_bool. intro; discriminate.
Qed.

What about negative exponents? Your function is underspecified; you may want to try to coerce a more precise specification out of Jessie. One possibility is that pow b e = 0 whenever e < 0, which would make pow extensionally equal to Zpower. But it's also possible that pow 1 e = 1 whenever e < 0.

You can also prove properties of the function independently of the function's definition. For example, you can use induction on the arguments to prove interesting properties like

Lemma pow_plus :
  forall b n1 n2,
    pow b (Z_of_nat n1 + Z_of_nat n2) =
    pow b (Z_of_nat n1) * pow b (Z_of_nat n2).
Proof.
  induction n2.
  (*same techniques as above*)
Qed.


Binary search on coin heads probability Let $f:[0,1] \to [0,1]$ be a smooth, monotonically increasing function.  I want to find the smallest $x$ such that $f(x) \ge 1/2$.

If I had a way to compute $f(x)$ given $x$, I could simply use binary search on $x$.  However, I don't have a way to compute $f(x)$.  Instead, I have a black box that, on input $x$, flips a biased coin and outputs 1 with probability $f(x)$ and 0 with probability $1-f(x)$.  I can invoke the black box as many times as I want.

I'm looking for a query-efficient strategy to approximate $x^* = \min \{x : f(x) \ge 1/2\}$.  Is there an efficient algorithm?  I would be happy with strategies where we assume a fixed upper bound on $f'(x)$.

Informally, we can summarize the problem as: I have a coin whose heads probability depends in some unknown but monotonic way on a parameter; how can I choose the minimum value of that parameter to ensure the coin is biased in my favor?

A naive approach is to estimate $f(x)$ for any $x$ by invoking the black box $k$ times on the same input $x$, then use binary search with this estimator.  However, I suspect this makes more queries than necessary.  Intuitively, it makes many queries in regimes where $|x-1/2|$ is large, and the estimator for $f(x)$ doesn't use information from the black box on queries $x'$ that are near to $x$.

I suspect something like the following might be better, for some constant $1/2 < \alpha < 1$:

Set $x := 1/2$ and $d := \alpha$.
Repeat some fixed number of times:

Query the black box on $x$.  If it returns 1, set $x := x + d$, otherwise set $x := x - d$.
Clip $x$ to the range $[0,1]$.  Set $d := \alpha d$.

However I'm not sure how to set $\alpha$ or how to analyze this approach.  (Note that if $\alpha=1/2$ and the black box returned whether or not $f(x)\ge 1/2$, this strategy would devolve to binary search.)

Is there a good way to choose $\alpha$?  Or, is there a better strategy?

This is addressed in the following paper of Karp and Kleinberg:

  Karp, Richard M.; Kleinberg, Robert. Noisy binary search and its applications. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 881--890, ACM, New York, 2007.

You can find a copy on Kleinberg's website.


Max-clique in line graph of hypergraph Suppose we have a multigraph (later, a multihypergraph). An edge-clique is a set of edges which all pairwise intersect (have at least one common vertex). Then any edge-clique $C$ in a multigraph always falls into one of two categories:

A star: there is a vertex such that every edge of $C$ contains it
A triangle: there are three vertices such that every edge of $C$ goes between two of them

This leads to an easy $O(n^3)$-time algorithm to compute the largest edge-clique.

I am pretty sure one can show more generally, that for every $r$, in multihypergraphs with maximum edge size $r$, you can prove a certain structure theorem for hyperedge-cliques, and get a polynomial time algorithm to find the maximum clique.

Is there anything related to this result known? Also, the algorithm I have in mind is extremely high degree polynomial; it would be nice to get something with running time $n^{\mathrm{poly}(r)}$ or better.

I found this interesting since the maximum edge-clique is a lower bound on the edge-chromatic number (a.k.a chromatic index).

Edit: In the cross-post, the reference about kernels leads to a $2^{2^{\mathrm{exp}(r)}}n^{\mathrm{exp}(r)}$-time algorithm: guess the kernel and guess the restriction of the clique to the kernel.

Every graph G is a line graph of some hypergraph, for instance the one that has the edges of G as its vertices and the sets of edges neighboring each vertex of G as its hyperedges. Therefore, finding cliques in line graphs of hypergraphs can be no easier than finding cliques in arbitrary graphs.

Of course with your limitation of edge size $r$, one can only do this starting from a graph $G$ with degree $r$, and max clique in bounded degree graphs is not so hard, so this doesn't rule out the $n^{poly(r)}$ algorithm you're hoping for.


Density of Ramsey Graphs Suppose we have a graph $G$ with $n$ vertices that contains neither a clique of size $3 \log(n)$ nor an independent set of size $3 \log(n)$ (for example $G(n,0.5)$ satisfies this property with with high probability). Is it true that the number of edges of $G$ is at least $n^2/100$, i.e., it cannot be too sparse?

More generally, I would like to know whether such graphs have some kind of pseudo-random properties.

The answer to your question is yes. It is a result of Erdős and Szemerédi from 1972. We know a little, but non-zero about pseudo-random properties of Ramsey graphs. For example, we know that many different kinds of induced subgraphs appear in such a graph. See, for example, a paper by Alon–Balogh–Kostochka–Samotij and references therein.


Understanding proof of Theorem 3.3 in Karp's "Probabilistic Recurrence Relations" Background: In Karp's paper on Probabilistic Recurrence Relations, he develops tail-bounds for random variables satisfying the following recurrence:

$$ T(x) = a(x) + T(h(x)) $$

where $T(x)$ is a random-variable that can be thought of as the cost or run-time of some randomized algorithm when run on an instance of size $x$. Here, $a$ is some deterministic "toll" cost involved in processing the instance prior to a recursive call, and $h(x)$ is a real-valued random-variable in the range [0, x], which gives the size of the instance in the recursive call of $T$.

Assuming the expectation of $h(x)$ is bounded by some function $m(x)$, Karp then considers the deterministic recurrence relation:

$$ u(x) = a(x) + u(m(x)) $$

He then derives various tail-bounds on $T$ in terms of $m$, $a$, and $u$.

Question: My question is about one of the steps in the proof of Theorem 3.3 of the paper. The exact statement of the result is not needed to understand the step I'm stuck on. In this theorem, $a$ and $m$ are assumed to be continuous, there is some $d$ such that $a(x) = 0$ on the interval $[0, d]$, $a$ is strictly increasing on $[d, \infty)$, and $m(x)/x$ is assumed to be non-decreasing.

Karp then defines $K_r(x) = \mathrm{Prob}[T(x) > r]$. He notes that $K_r(x) = E[K_{r - a(x)}(h(x))]$. His goal is to bound $K_r(x)$ by some quantity. To do so, he starts by defining a sequence of functions $K_r^i$ indexed by natural number $i$ as: $K_r^0(x) = 1$ for $r \leq 0$ and $K_r^0(x) = 0$ for $r > 0$; and inductively, $K_r^{i+1}(x) = E[K_{r-a(x)}^i(h(x))]$. He then says that $K_r(x) \leq \sup_{i} K_r^i(x)$, and proceeds to bound each of the $K_r^i$, thus deriving a bound on the supremum and in turn $K_r$.

However, I do not understand why $K_r(x) \leq \sup_{i} K_r^i(x)$. This step is stated without elaboration, so I'm guessing I'm missing something obvious. I see that the $K_r^i$ are defined recursively in terms of the same recurrence about expectation that $K_r$ satisfies, and the supremum of the $K_r^i$ should be a fixed-point of this recurrence, sort of like the construction in Kleene's fixed-point theorem. But that would seem to give a least fixed point, which would justify the opposite inequality: $\sup K_r^i(x) \leq K_r(x)$. I think I see a way to make the argument go through if $\{a(x) | a(x) > 0\}$ is bounded below by some $\epsilon > 0$, but that contradicts the continuity assumption on $a$. Banach's fixed-point theorem would give a unique fixed point, which would do, but I do not see a sense in which this is a contraction.

Other references: this result is mentioned in Chapter 4 of Dubhashi and Panconesi's textbook on Concentration of Measure, but the proof is not included. Chaudhuri and Dubhashi's paper "Probabilistic Recurrence Relations Revisited" proves a similar result but the proof technique is different, so it does not help me understand this argument.

In some cases the recurrence for $T$ does not determine it uniquely. We take the following interpretation of $T$, which gives the minimum $T$ consistent with the recurrence.

Repeatedly substitute $T(x) = a(x) + T(h(x))$ to expand $T(x)$ as the (random) sum
$$
T(x) = a(x) + a(h(x)) + a(h(h(x))) + \cdots = \sum_{j=1}^\infty a_j
$$
where $a_i = a(h^{(i-1)}(x))$,
in which $h^{(0)}(x) = x$ and and $h^{(i+1)}(x) = h(h^{(i)}(x))$.

lemma. With this definition of $T$,
we have $K_r(x) \le \sup_i K^i_r(x)$.

Proof.
Inspecting the definitions of $K^i_r$ and $K_r$, we have
$$
K_r(x) = \Pr[\textstyle\sum_{j=0}^\infty a_j > r]
~~\mbox{and}~~
K^i_r(x) = \Pr[\textstyle\sum_{j=0}^{i-1} a_j \ge r].
$$
To prove the lemma, we will show something slightly stronger, namely
$$
\Pr[\textstyle\sum_{j=0}^\infty a_j > r] ~~=~ \sup_i \Pr[\textstyle\sum_{j=0}^{i-1} a_j > r].
$$
Define random variable $T = \min\{i : \sum_{j=0}^{i-1} a_j > r\}$ to be the first step at which the sum of terms exceeds $r$ (with $T=\infty$ if that never happens).
Rewriting the desired equation in this notation, we want to show
$$
\textstyle \Pr[T < \infty] ~=~ \sup_i \Pr[T \le i].
$$
But that equation follows from basic definitions as follows:
$$
\Pr[T < \infty]
= \sum_{j=0}^\infty \Pr[T = j]
= \lim_{i\rightarrow\infty} \sum_{j=0}^i \Pr[T=j]
= \lim_{i\rightarrow\infty} \Pr[T \le i]
= \sup_i \Pr[T \le i ].$$
QED


What are CS blogs for puzzles/games? I am looking for blogs which contains recent progress on puzzles/games (Algebraic and Combinatorial) etc. like Soduko, latin square etc. I come across a list on TCS What CS blogs should everyone read?, but it does not seem to contain the type of blogs I am looking for. I am looking for blogs that contains content related to the complexity and algorithmic question of games/puzzles.

I have tried to try to search on the internet. I have got a few resources like FUN conference etc., that helps to some extent.

Are there any blogs or webpage which can serve the purpose I have given below?

What I am from them

Brief idea of the puzzle
Current status of the puzzle
Current open/interesting question on puzzle

http://www.cseblog.com/
CMU - The Puzzle Toad
Tanya Khovanova’s Math Blog

And the links therein.


Classes and types in object-oriented languages In typical object-oriented programming languages like Java, classes are used as types.  On the other hand, type-theoretic approaches to object-oriented languages treat interfaces as types.

Are there any theoretical frameworks that formalize the use of classes as types?

Core calculi for Java typically take the classes-as-types approach.  Two well-known examples are Featherweight Java and Classic Java.


How to design a secret sharing scheme for matrix-like positioned participants How to design a secret sharing scheme where when participants are positioned as a matrix, the minimum group people who can reconstruct the secret are the ones that are in same row or in same column?

For an m x n matrix, you can simply create m+n independent sharings (using any n-out-of-n or m-out-of-m secret sharing scheme, such as the XOR scheme), one for each row and for each column.

Each participant will get tow shares, one for his row and one for his column. His total share size is 2s, where s is the length of the secret. Since you can't get share size less than s, this simple scheme is within a factor of 2 of the optimum.


Halting problem, uncomputable sets: common mathematical proof? It is known that with a countable set of algorithms (characterised by a Gödel number), we cannot compute (build a binary algorithm which checks belonging) all subsets of N.

A proof could be summarized as: if we could, then the set of all subsets of N would be countable (we could associate to each subset the Gödel number of the algorithm which computes it). As this is false, it proves the result.

This is a proof I like as it shows that the problem is equivalent to the subsets of N not being countable.

Now I'd like to prove that the halting problem is not solvable using only this same result (uncountability of N subsets), because I guess those are very close problem. Is it possible to prove it this way ?

The halting theorem, Cantor's theorem (the non-isomorphism of a set and its powerset), and Goedel's incompleteness theorem are all instances of the Lawvere fixed point theorem, which says that for any cartesian closed category, if there is an epimorphic map $e : A \to (A \Rightarrow B)$ then every $f : B \to B$ has a fixed point.

Lawvere, F. William. Diagonal Arguments and Cartesian Closed Categories. Lecture Notes in Mathematics, 92 (1969), 134-145.

For a nice introduction to these ideas, see this blog post of Andrej Bauer.


A lottery that you can be convinced that it is fair (Sorry if this is well known.) I would like to give some item to one of $k$ agents, so that agent $j$ will get the item with probability $p_i$. Is there a cryptographic (or other) tool so that every agent (and even every observer) will be able to be convinced that the random drawing was indeed fair?

If I am understanding the problem correctly, it would seem to amount to public flipping a $k$-sided coin. There seem to be lots of ways to do this if you assume bit commitment. One example would be having each party generate a random integer between 0 and $k-1$, using bit commitment to publicly commit to that bit string. Then once each agent has committed, they all publicly reveal their secret integer. The winning agent is then the one indexed by the sum of the integers modulo $k$. If even one agent is honest, then the flip must be random.

Of course one problem with this is that it requires bit commitment. Information theoretic schemes for bit commitment are impossible for both classical and quantum computing (though Adrian Kent recently proposed a scheme exploiting relativity). However, secure bit commitment can be achieved with computational assumptions.


research papers for undergraduate students The papers presented at conferences like SODA, FOCS are hard to understand for undergraduates. Also a lot of background knowledge is assumed for understanding such papers. Are there any conferences/resources/websites where I can find interesting research paper readable by undergrads.

thanks

It's not true that all science papers have to be very complicated and rough for undergraduates. When I was still really fresh in CS I found a lot of science papers that helped me understand many problems. Try to look for something interesting for you on http://paperity.org/. I found many interesting journals and papers. I think this is currently the most useful aggregator on web


Maximum rows to partially distinguish all the columns This is a problem I met in my work. I thought about it for about two weeks, no result. I don't know whether it has been studied before by others?

Problem Description: Given an $m\times n$ matrix $M$ with entries valued 0 or 1. Let $r_i$ denote the $i^{th}$ row,
$c_i$ denote the $i^{th}$ column and $t_{ij}$ denote the entry in the $i^{th}$ row and $j^{th}$ column. Find a $k \times n$ submatrix $A$ of $M$, such that in $A$
\begin{equation}
\forall_{r_i}{ \exists_{c_a,c_b}{ \forall_{r_j \ne r_i}{\left(  t_{ia} \ne t_{ib} \land t_{ja} = t_{jb} \right) } } }.
\end{equation}
$k$ is the parameter

The selected rows satisfy the following condition: For each row $r_i$, there exist two columns $c_a, c_b$, such that entries of the two columns at row $i$ are different, and at the remaining rows are the same.

Could someone give me any reference for it, if it has been studied before ? Thank you very much.

At first, I thought it was a special case of Minimum Test Set problem, however, it turns out not.

This is not an answer, only an extended comment on a possible transformation of the problem (hope it is correct :-).

Each row can be "mapped" to a $n \times (n-1) / 2$ "extended" row. Each element of the extended row represents a pair of elements in the original row and is set to 1 if the two elements are different, set to 0 if the two elements are the same.

For example:

row_i = 10011
        ^1100   (*)
         ^011
          ^11
           ^0

extended_row_i = 1100 011 11 0

(*) note that in building the extended row, when the current bit (marked with ^)
is 0, the remaining bits are just copied and when the current bit is 1 the
remaining bits are inverted

We can extend each row and obtain an "extended" matrix. For example the matrix:

10011
01101
00011

Becomes:

1100 011 11 0
1101 010 10 1
0011 011 11 0

And the original problem reduces to find a submatrix of the "extended" matrix with exactly one 1 in each column.


Is the concept of the Turing Machine derived from automata? I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"?

I didn't know the answer of course, but I'm curious to find out. The Turing Machine is basically a slightly more sophisticated version of a Push-Down Automata. From that I would assume that the Turing Machine was derived from automata, however I have no definitive proof or explanation. I might just be plain wrong... perhaps they were developed in isolation.

Please! Free this mind from everlasting tangents of entanglement.

Neither!

The best way to see this independence is to read the original papers.

Turing's 1936 paper introducing Turing machines does not refer to any simpler type of (abstract) finite automaton.
McCulloch and Pitts' 1943 paper introducing "nerve-nets", the precursors of modern-day finite-state machines, proposed them as simplified models of neural activity, not computation per se.

For an interesting early perspective, see the 1953 survey by Claude Shannon, which has an entire section on Turing machines, but says nothing about finite automata as we would recognize them today (even though he cites Kleene's 1951 report).

Modern finite automata arguably start with a 1956 paper of Kleene, originally published as a RAND technical report in 1951, which defined regular expressions.  Kleene was certainly aware of Turing's results, having published similar results himself (in the language of primitive recursive functions) at almost the same time.  Nevertheless, Kleene's only reference to  Turing is an explanation that Turing machines are not finite automata, because of their unbounded tapes.  It's of course possible that Kleene's thinking was influenced by Turing's abstraction, but Kleene's definitions appear (to me) to be independent.

In the 1956 survey volume edited by Shannon and McCarthy, in which both Kleene's paper on regular experssions and Moore's paper on finite-state transducers were finally published, finite automata and Turing machines were discussed side by side, but almost completely independently.  Moore also cites Turing, but only in a footnote stating that Turing machines aren't finite automata.

(A recent paper of Kline recounts the rather stormy history of this volume and the associated Dartmouth conference, sometimes called the "birthplace of AI".)

(An even earlier version of neural nets is found in Turing's work on "type B machines", as reprinted in the book "The essential Turing", from about 1937 I think.  It seems likely that many people were playing with the idea at the time, as even today many CS undergrads think they have "invented" it at some point in their studies before discovering its history.)


Fast approximation of (vertex) clique cover I'm looking for a fast algorithm to find a clique cover on an undirected unweighted graph.

I'm not looking for an optimal solution (ie minimal number of cliques). Obviously I'm also not looking for a maximal solution (ie 1 clique per edge on an edge cover).

Any pointer towards a nice algorithm?

You can use a fast (e.g. greedy) max clique algorithm to find cliques one after another. That is, find a maximal clique, remove it from the graph, and repeat until the graph is empty. If fact, I just coded this in C++ for some project that I'm working on now. I can share the code if you'd like it (it accepts DIMACS files).


Languages and their operations: determining equivalence I'm currently taking a subject on theoretical computer science. This is not a homework question.

I'm having trouble figuring out to show the equivalence or disprove the equivalence. Consider any two languages $A$ and $B$. Is the following statement true or false?

$A^* \cup B^* = (A \cup B)^*$

Honestly, I use the above example mainly to ensure my question is less subjective. However I'm more concerned about the generalised approach to determining whether languages are equivalent (or subsets of each other and such) when operated on by various operators (kleene star, union, intersection, difference, concatenation). If I know that they are not equivalent I can basically just start bruteforcing for counter-examples, however I can't really think of any structured and consistent approach to answering questions such as the above.

Thanks.

Nope. Let $A = \{a\}$, $B= \{b\}$. Then $A^* = \{\epsilon,a,aa,
\ldots\}$ and similarly for $B$. So, $A^*\cup B^*$ contains strings of repeated "a" or repeated "b". But $(A\cup B)^*$ contains strings like $ab$, which you can't get from $A^*$ or $B^*$.

I'd suggest looking at a book like Sipser for a good coverage of languages like these and how to prove properties like equivalence. In particular, he has a great number of exercises to work through. Good luck!


Are there any propositional proof systems which are not Cook-Reckhow proof systems? An abstract proof system is a polynomial time function $f$ whose
  range is equal to the set of tautologies. If $\tau$ is a tautology, then an $f$-proof of $\tau$ is any value $\pi$ such that $f(\pi) = \tau$.

Is there an example of a propositional  proof system which doesn't satisfy this definition?

Natural examples of propositional proof systems that do not fall under this definition are algebraic proof systems where the lines in the proof are arbitrary polynomials (not necessarily fully expanded). To verify the correctness of such proofs, among other things one has to test the identity of polynomials, which is not known to be possible in deterministic polynomial time.

Cf. the paper "Algebraic propositional proof systems" by Toni Pitassi, in  DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 31, Descriptive Complexity and Finite Models, Immerman and Kolaitis (Eds.), pp. 215-244, 1996.


Request for references on multicommodity flow-cut results This is a somewhat subjective question. I am interested in studying the literature on multicommodity flow-cut results, especially the 'positive' results which show that flow is a good approximation to cut (say, within a factor that is constant or polylogarithmic in the number of flows). Examples are:

1) Flow polytope (also called demand polytope) for multicommodity flow in undirected graphs is within O(log k) of cut as shown in

F. Leighton and S. Rao,“An approximate max-flow min-cut theoremfor uniform multicommodity flow problems with applications to approximation algorithms,” in Proc. of 28th Annual Symposium on Foundations of Computer Science, (Los Alamitos, California), 1988.

N. Linial, E. London, and Y. Rabinovich, “The geometry of graphs and some of its algorithmic applications,” Combinatorica, vol. 15, no. 2, pp. 215–245, 1995.

2) Demand polytope of multicommodity flow in directed graphs with symmetric demands is within O(log^2 k) of cut as shown in

P. Klein, S. Plotkin, S. Rao, and E. Tardos, “Bounds on the max-flow min-cut ratio for directed multicommodity flows,” J. Algorithms, no. 22, pp. 241–269, 1997.

3) Max sum-rate in groupcast is within a factor 2 of the multicut. (I don't know a reference for this result. Could someone help me with this? Thanks.)

I would like to know more such positive results affirming flow being close to cut assuming certain structure of the problem (such as undirectedness of graph or symmetric demands, as in above). It would be great if you can give me a one-line summary of the result(s) and a reference of the paper. Thanks.

I can recommend my recent paper http://arxiv.org/abs/1110.6832 on multicommodity flows and cuts in polymatroidal networks; we generalize several known results in standard graphs. Although we do not give a nice table summary we discuss many of the known cases. Some of the results that are not discussed in the paper but are of relevance are those for planar undirected graphs and some special cases. These include the result of
Satish Rao on $O(\sqrt{\log n})$ bound on flow-cut gap and tight bound of $2$ for series-parallel graphs by Chakrabarti-Jaffe-Lee-Vincent and some others. James Lee has several papers on flows and cuts on these graphs and any relatively recent one will discuss the existing literature.


How to publish a paper? Being a software engineer for the most part of my life I have absolutley no idea how to start with publishing an "academic" kind of paper. During my latest research I've found an interesting algorithm for the task I've been solving (related to some calculations on financial markets). It's not some great result but I think it can be interesting for people doing the similar tasks and I'd like to publish it.

I'm of course familar with a style of research papers since I use them extensivly at my job (thanks to Google Scholar and all the good people out there) and I'm able to google for free manuals on academic writing style and how to use LaTeX and I have a lot of friends mathematicians who will check my paper and help to make it look ok.

But I have absolutely no idea what to do next! I don't belong to any academic institution or recognizable research entity, I work in a small local company, which will be happy to have its name on some paper published but this name will say nothing to anybody. I don't know anybody who is doing research in this area, I mean I've never communicated with anybody.

How can I found the right place to send paper to? Do I need some sort of recommendation or review and how and where can I try to get them? What are my steps?.. I realize that all these are absolutely obvious things for you if you are a professional sceintist but I have no idea where to start :)

First, you should write up your result so it's comprehensible as you can make it, and send it to a journal. If your write-up looks like it is a real research paper, your paper should be sent out for review and possible publication. How to choose a journal? Look for other papers which are on roughly the same subject matter and around the same quality as yours, and see where they got published.

Don't publish in a fourth-tier journal; if you do, it will never be read; these seem to exist only for the purpose of increasing the number of researcher's publications, and are not subscribed to by many academic libraries. To make sure you're not choosing one of these, check the online databases of a few good academic libraries, and make sure most of them subscribe to the journal you have picked.


Relationship between contracts and dependent typing I've been reading some articles on dependent types and programming contracts. From the majority of what I've read, it seems that contracts are dynamically checked constraints and dependent types are statically checked.

There have been some papers that have made me think that it's possible to have contracts that are partially statically checked:

Hybrid Type Checking (C. Flanagan - 2006)
Unifying Hybrid Types and Contracts (J. Gronski, C. Flanagan - 2007)

With this, there seems to be a significant amount of overlap and my categorisation of contracts vs dependent types starts to disappear.

Is there something deeper in either concepts that I'm missing? Or are these really just fuzzy categories of representing the same underlying concept?

On a practical level, contracts are assertions. They let you check (quantifier-free) properties of individual executions of a program. The key idea at the heart of contract checking is the idea of blame -- basically, you want to know who is at fault for a contract violation. This can either be an implementation (which does not compute the value it promised) or the caller (who passed a function the wrong sort of value).

The key insight is that you can track blame using the same machinery as embedding-projection pairs in the inverse limit construction of domain theory. Basically, you switch from working with assertions to working with pairs of assertions, one of which blames the program context and the other of which blames the program. Then this lets you wrap higher-order functions with contracts, because you can model the contravariance of the function space by swapping the pair of assertions. (See Nick Benton's paper "Undoing Dynamic Typing", for example.)

Dependent types are types. Types specify rules for asserting whether or not certain programs are acceptable or not. As a result, they do not include things like the notion of blame, since their function is to prevent ill-behaved programs from existing in the first place. There is nothing to blamed since only well-formed programs are even grammatical utterances. Pragmatically, this means that it is very easy to use dependent types to speak of properties of terms with quantifiers (eg., that a function works for all inputs).

These two views are not the same, but they are related. Basically, the point is that with contracts, we  start with a universal domain of values, and use contracts to cut things down. But when we use types, we try to specify smaller domains of values (with a desired property) up front. So we can connect the two via type-directed families of relations (ie logical relations). For example, see Ahmed, Findler, Siek and Wadler's recent "Blame for All", or Reynolds' "The Meaning of Types: from Intrinsic to Extrinsic Semantics".


Exact algorithms for non-convex quadratic programming This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form

minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}$ subject to $\mathbf{x} \in [0,1]^n$.

If $A$ was positive semi-definite, then everything would be nice and convex and easy, and we could solve the problem in polynomial time.

On the other hand, if we had the integrality constraint $\mathbf{x} \in \{0,1\}^n$, we could easily solve the problem in time $O(2^n \cdot \mathrm{poly}(n))$ by brute force. For the purposes of this question, this is reasonably fast.

But what about the non-convex continuous case? What is the fastest known algorithm for general box-QPs?

For example, can we solve these in moderately exponential time, e.g., $O(3^n \cdot \mathrm{poly}(n))$, or is the worst-case complexity of the best known algorithms something much worse?

Background: I have some fairly small box-QPs that I would actually like to solve, and I was a bit surprised to see how poorly some commercial software packages perform, even for very small values of $n$. I started to wonder if there is a TCS explanation for this observation.

An optimal solution lies on some face.  So, we can go through all the faces of the cube, and find all stationary points on each of the faces.

Here is a more concrete procedure.  A face of the cube can be characterized by two disjoint index sets $I_0$ and $I_1$.  For $i \in I_0$, we fix $x_i = 0$, and for $i \in I_1$ we fix $x_i = 1$.  Let $\tilde{x}$ consist of the remaining unfixed entries of $x$.  This fixing turns the objective function into the following form:

$$
\tilde{x}^{\top} \tilde{A} \tilde{x} + \tilde{c}^{\top} \tilde{x} + d,
$$

with appropriate $\tilde{A}$ and $\tilde{c}$, and some constant $d$, and we want to find the stationary points of this function under the condition that $0 < \tilde{x} < 1$.

To this end, we take the differentiation of the objective function to obtain

$$
\frac{1}{2} \tilde{A} \tilde{x} + \tilde{c} = 0.
$$

Solving this system of linear equations gives you the stationary points, the candidates for optimal solutions.  We go through all of them, check the condition, and choose one with the minimum objective value.

The overall time complexity is something like $O(3^n \text{poly}(n))$ since the number of faces of the $n$-cube is $3^n$ and a system of linear equations can be solved in polynomial time.  The space complexity is polynomial in $n$.


Treewidth of two complete binary trees joined at their leaves Let $T$ be a complete binary trees on $n$ nodes. Let $G'$ be the graph that consists of two disjoint copies of $T$. For a leaf $x \in T$, let $x_1, x_2$ be the two copies of it in $G'$. Then, let $G$ be the graph obtained from $G'$ where for every leaf $x$, an edge between $x_1, x_2$ is introduced.

I am interested in the treewidth of $G$. I conjecture that it is $O(\log(n))$ (start at the root of one copy of a tree, then first visit the left subtree and recurse until the root node of the other tree is reached, we always need to keep track of a path of length at most $\log(n)$). First, is this correct? Second, how can I prove a LB on the treewidth of this graph?

Thanks in advance.

Indeed, this graph has treewidth 2. It's a well-known result in phylogenetics where the leaves are labelled. See Bryant, David, and Jens Lagergren. "Compatibility of unrooted phylogenetic trees is FPT." Theoretical Computer Science 351.3 (2006): 296-302. The graph structure they use unifies leaves with the same label (rather than putting an edge between them), but their graph can be obtained from yours by suppressing degree-2 vertices, and this does not impact upon the treewidth.


"Tiny" Graph Isomorphism While thinking about the complexity of testing isomorphism of asymmetric graphs (see my related question on cstheory), a complementary question came to my mind.

Suppose that we have a polynomial time Turing machine $M$ that on input $1^n$ generates a graph $G_{M,n}$ with $n$ nodes.

We can define the problem $\Pi_M$:

  ("Tiny" GI): Given a graph $G=(V,E)$, is $G$ isomorphic to $G_{M,|V|}$?

In other words we must compare a given graph with a "reference" graph of the same size generated by a fixed polynomial time Turing machine $M$.

  For all polynomial time Turing machines $M$, we have $\Pi_M \in NP$, and for many of them we have $\Pi_M \in P$.
  But is it true for all $M$? Is the problem known?

At first glance, I thought that every $\Pi_M$ should be much easier than $GI$, because for every $n$ there is only one "reference" graph of that size and perhaps the symmetries/asymmetries of the graphs generated by $M$ can be exploited and an efficient ad-hoc isomorphism tester can be built ... but it's not true: $M$ can contain some sort of polynomial timed Universal Turing machine that uses the (unary) input $1^n$ to generate completely different (in the structure) reference graphs as $n$ increases.

[This is more of a few extended comments than an answer.]

1) If $GI \notin \mathsf{P}$, then there is no fixed-polynomial bound on the time complexity of all $\Pi_{M}$, even for $M$ that only take time, say, $n^3$: If for all time-$n^3$ $M$, $\Pi_{M} \in \mathsf{DTIME}(n^k)$, then the following is a poly-time algorithm for GI. On input $(G, H)$, construct a Turing machine $M_{G}$ with a clock which ensures that $M_{G}$ never runs for more than $n^3$ steps on inputs of size $n$, and such that $M_{G}(1^{|V(G)|}) = G$, and then solve $\Pi_{M_G}(H)$ in time $O(n^k)$.

2) Since for any $M$, $\Pi_{M}$ is no harder than GI, one might think that the best result along the lines of "$\Pi_M$ seems not to be in $\mathsf{P}$" one could hope for is a GI-completeness result. However, it seems unlikely to me that any one $\Pi_M$ would be GI-complete, for at least the following reasons:

All the GI completeness results I know of are for rather large classes of graphs, rather than having a single graph of each size. Even if you drop the efficiency requirement entirely, I do not know of any list of graphs $G_1, G_2, \dotsc$ such that $|V(G_n)| = n$ (or even $poly(n)$) such that testing isomorphism to $G_n$ is GI-complete.
On a related note, most (all?) GI-completeness results are not merely many-one reductions, but have the following form: there is a function $f$ such that given an instance $(G,H)$ of GI, $(f(G), f(H))$ is instance of the other GI-complete problem. (These are just poly-time morphisms of equivalence relations, or what Fortnow and I called "kernel reductions.) We can easily show unconditionally that there is no such reduction from GI to any $\Pi_M$ (even if you modify the definition to allow $M$ to output multiple graphs). Hint: Get a contradiction by showing that any such $f$ must have its image completely contained in $\{G_{M,n}\}_{n \geq 0}$.

3) Even though one could construct $M$ based on a universal TM as suggested in the question, perhaps one can still construct an efficient tester, just not efficiently. That is, maybe for each $M$, $\Pi_{M}$ is in $\mathsf{P/poly}$?


A course for learning algebraic complexity I want to learn about algebraic algorithms and complexity thoery. In particular, I am interested in PIT.

Is there a set of lecture notes, books, papers and surveys for students who have read standard textbook about theory like Sipser's book or the Arora-Barak's complexity textbook.

The set of references will includes recent advanced results.

The massive tome of Burgisser-Clausen-Shokrollahi is the standard reference for algebraic complexity theory (and I'm not really sure there are others from the complexity point of view, though there are definitely others about algebraic algorithms), but doesn't do much of PIT.

The surveys of Chen-Kayal-Wigderson (freely available from Wigderon's webpage) and Shpilka-Yehudayoff (freely available from Shpilka's webpage) cover much more of the recent results on lower bounds and derandomizing PIT for small algebraic circuit classes.

Agrawal's 2006 ICM address gives a good overview of the permanent versus determinant problem, and despite being 8 years old is still fairly up to date. (I think the only more recent lower bound is Landsberg-Manivel-Ressayre, which gets the same lower bound but for approximative determinantal complexity instead of just determinantal complexity.)


Knapsack problem with dependent weight and profits among the items I'm working on a problem that may be reduced to the following variant of multiple knapsack problem:
Each knapsack has its own valuation function; an item brings different profit and weight to a specific knapsack. Also, the profit and weight of an item depend on the profit and weight that has been assigned to the knapsack.
For example, suppose two items $a$ and $b$ have profit $p_{ai}$ and $p_{bi}$ and weight $w_{ai}$ and $w_{bi}$ in the $i^{th}$knapsack. If the item $a$ is selected to the knapsack $i$, everything goes well. However, if both items are presented to knapsack $i$, the combined profit of $a$ and $b$ is not $p_{ai} + p_{bi}$ and instead be little smaller than that. The total weight of $a$ and $b$ is also larger than $w_{ai} + w_{bi}$. Though, we can know the value of each combination, it takes expensive computation overheads. This relationship is not limited between two items, but holds among all items, which means if a knapsack is assigned three items $a$, $b$ and $c$, its profit is not $p_{ai} + p_{bi} + p_{ci}$ or $Value({a, b}) + Value({a, c}) + Value({b, c})$ and its weight is not $w_{ai}+w_{bi} + w_{ci}$. As usual, we always want to maximize the total profit. Though, it seems like a variant of quadratic knapsack problem, the overhead to compute the additional profit for all subsets is too costly.
My question is, has there work been done on this variant of (multiple)knapsack problem? Are there any papers that I can read to better understand it? I am not very familiar with the literature of knapsack problems and have tried to search for this but still gets little useful.

Hi that sounds quite a lot like the multiobjective Knapsack Problem to me. It has undergone some research for example by the bio-inspired computation community, see for example here:
https://etheses.bham.ac.uk/id/eprint/7532/2/Joshi17PhD.pdf


How to introduce recursion to Simply Typed Lambda Calculus while at the same time keeping strong normalisation? Suppose you have a version of the STLC with one base type, similar to:

 data Tree = Branch Tree Tree | Leaf

Now, suppose you want to add recursion to that language, while still guaranteeing termination. Someone suggested a "Recur" primitive, which can only be applied at sub-expressions of pattern matches, making the following legal:

id (Tree a b) = Tree (id a) (id b)
id Leaf = Leaf

This is obviously terminating, so that sounds like a good idea. Now, mind that function:

foo (Tree (Tree a b) c) = foo (Tree a c)
foo (Tree a b) = Tree (foo a) (foo b)
foo Leaf = Leaf

Now this function is obviously terminating, but it includes a recursion that is not applied directly to a sub expression of a pattern match, namely, foo (Tree a c), so you can't express it on the suggested system. My question is: is there a more general way to introduce recursion that will still guarantee termination without making some valid cases illegal?

Which of the following are you asking: are there ways of
enriching the simply-typed $\lambda$-calculus with
mechanisms (presumably by restricting the available forms of
recursion) such that

exactly the terminating programs are typable?
more terminating programs are encodable than with the simple
    restriction you are describing in your question?

The answer to (1), as pointed out by Toxaris, is: if you want
type-checking to be decidable, then no. This follows directly
from the uncomputability of the halting problem. The answer
to (2) is positive, and Dave Clarke's answer gives an
example. Indeed there are countless ways of doing so, some
ad-hoc: e.g. if you have a particular (terminating) program $M$
of type $\alpha$ you want to add to the simply-typed
$\lambda$-calculus, you simply add a rule $\Gamma \vdash M :
\alpha$ to your typing system. For a more interesting and
principled way you could look at Barendregt's $\lambda$-cube,
which presents three orthogonal axes of extending the
simply-typed $\lambda$-calculus, all of which make the
simply-typed $\lambda$-calculus strictly more expressive
without losing normalisation. Relatedly, you can look at
induction principles, which are related closely to recursion. Note that this is an active area
of research because the more expressive you make your typing system,
the harder it becomes to prove that the calculus indeed only
types normalising programs.

Note that the problem is usually not to find a fragment of total functions
that we can use to program our terminating programs in. The total
fragments of lambda-calculus given by more expressive parts of the
$\lambda$-cube (e.g. $F_{\omega}$ or the calculus of constructions)
are very expressive. The problem is usually that it is
often inconvenient to encode a terminating program in such a
fragment. R. Harper gives the example of the $gcd$ function computing
the greatest common divisor:
$$
\begin{align*}
\textit{gcd}(m,0) & = m \\
\textit{gcd}(0,n) & = n \\
\textit{gcd}(m,n) & = \textit{gcd}(m-n,n) \quad \text{if}\ m>n \\
\textit{gcd}(m,n) & = \textit{gcd}(m,n-m) \quad \text{if}\ m<n
\end{align*}
$$

It is easy to see that this function terminates, but expressing it
using simple recursion schemes is no fun. Most programs we care
about in daily programming life are terminating for simple reasons and can typically
be encoded using relatively simple recursion schemes (e.g. primitive recursion).
That's why it was a major insight of Ackermann's and Sudan's that primitive
recursion is not enough.
For this reason  powerful recursion schemes
(including the unrestricted recursion of most programming languages)
are typically a convenient device to make programming   simpler, rather
than necessary for expressivity. Note that in the presence of higher-order functions,
primitive recursion is quite powerful, and enables us to encode e.g. the Ackermann function:

$$
\begin{array}{lcl}
   \textit{Ackermann} \ 0 & = & \lambda x. x+1 \\
   \textit{Ackermann} \ ( m+1 ) & = & \textit{Iter}\ ( \textit{Ackermann}\ m ) \\
   \textit{Iter}\ f\ 0 & = & f\ 1 \\
   \textit{Iter}\ f\ ( n+1 ) & = & f\ ( \textit{Iter}\ f\ n )
\end{array}
$$

BTW, the simply-typed $\lambda$-calculus with primitive recursion is also known as Gödel's System T and its expressivity has been studied in great detail and is well understood: we can define exactly the recursive function whose totality can be
proved in first-order logic, starting from the usual axioms for the elementary data
types, eg the Peano axioms for natural numbers.

In this context, you may find the paper Total Functional Programming by DA Turner interesting.

Non-typing work on termination. There's also a lot of ongoing work, both theoretical and implementation oriented, on termination analysis that's
not using (compositional) typing systems, but static analysis
techniques. An example is Microsoft's T2 termination prover.


Closure of unambiguous context-free languages under pre- and postfix. Let $L$ be a context-free language. Define $ppc(L)$ to be the pre- and postfix closure of $L$, in other words, $ppc(L)$ contains all of $L$'s prefixes and postfixes, and hence $L$ itself. My question: if $L$ is context-free and has a non-ambiguous grammar, is the same true for $ppc(L)$?

I believe that this kind of basic question would already have been resolved in the heyday of language theory, but I could not find a suitable reference.

The set $\mathit{ppc}(L)$ is certainly context-free, but I think it can be inherently ambiguous: consider
$$L=\{a^mb^mc^nd\mid m,n\geq 0\}\cup\{da^mb^nc^n\mid m,n\geq 0\}\;,$$ then $\mathit{ppc}(L)$ includes the classical inherently ambiguous language $$L'=\{a^mb^mc^n\mid m,n\geq 0\}\cup\{a^mb^nc^n\mid m,n\geq 0\}\;,$$ and one can prove $\mathit{ppc}(L)$ is also inherently ambiguous by the usual argument (apply Ogden's Lemma to both $a^{n+n!}b^nc^n$ and $a^nb^nc^{n+n!}$ to deduce the existence of two distinct trees for $a^{n+n!}b^{n+n!}c^{n+n!}$).


Are there natural separations in the nondeterministic time hierarchy? The original Nondeterministic Time Hierarchy Theorem is due to Cook (the link is to S. Cook, A hierarchy for nondeterministic time complexity, JCSS 7 343–353, 1973).  The theorem states that for any real numbers $r_1$ and $r_2$, if $1 \le r_1 \lt r_2$ then NTIME($n^{r_1}$) is strictly contained in NTIME($n^{r_2}$).

One key part of the proof uses (an unspecified) diagonalization to construct a separating language from the elements of the smaller class.  Not only is this a nonconstructive argument, but languages obtained by diagonalization usually provide no insight other than the separation itself.

If we want to understand the structure of the NTIME hierarchy, the following question probably needs to be answered:

  Is there a natural language in NTIME($n^{k+1}$) but not in NTIME($n^k$)?

One candidate might be k-ISOLATED SAT, which requires finding a solution to a CNF formula with no other solutions within Hamming distance k.  However, proving the lower bound seems is tricky, as usual.  It is obvious that checking a Hamming k-ball is clear of potential solutions "should" require $\Omega(n^k)$ different assignments to be checked, but this is by no means easy to prove.  (Note: Ryan Williams points out this lower bound for $k$-ISOLATED SAT would actually prove P ≠ NP, so this problem does not seem to be the right candidate.)

Note that the theorem holds unconditionally, regardless of unproved separations such as P vs. NP.  An affirmative answer to this question would therefore not resolve P vs. NP, unless it has additional properties like $k$-ISOLATED SAT above.  A natural separation of NTIME would perhaps help to illuminate part of the "difficult" behaviour of NP, the part which derives its difficulty from an infinite ascending sequence of hardness.

Since lower bounds are hard, I will accept as an answer natural languages for which we may have a good reason to believe a lower bound, even though there may not yet be a proof.  For instance, if this question had been about DTIME, then I would have accepted $f(k)$-CLIQUE, for a non-decreasing function $f(x) \in \Theta(x)$, as a natural language that probably provides the required separations, based on Razborov's and Rossman's circuit lower bounds and the $n^{1-\epsilon}$-inapproximability of CLIQUE.

(Edited to address Kaveh's comment and Ryan's answer.)

As far as I know, we don't know of such languages, or if we do, there is significant controversy about the "naturalness" of them. I know this isn't really a satisfying answer, but I can say:

(a) If you prove an $\Omega(n^k)$ time lower bound for k-ISOLATED SAT for every $k$, then you have actually proved $P \neq NP$.

(b) One way you might hope to show that k-ISOLATED SAT is one of these natural problems in $NTIME[n^{k+1}] - NTIME[n^k]$ is to show that k-ISOLATED SAT problem is hard (in the usual, formal sense of having efficient reductions) for $NTIME[n^k]$. In fact this is the only way we know how to prove such results. But k-ISOLATED SAT is probably not hard in this sense, there are some very unlikely consequences.

The main reason is that k-ISOLATED SAT instances are solvable in $\Sigma_2 TIME[n]$, independently of $k$. You can existentially guess the isolated assignment, then universally verify (for all $O(\log (\sum_{i=1}^k {n \choose i}))$ ways to flip up to $k$ bits in the assignment) that none of the other "local" assignments work.

Here is the proof of part (a). Let ISOLATED SAT be the version of the problem with $k$ given as part of the input (in unary, say). Suppose we prove that ISOLATED SAT requires $\Omega(n^k)$ time for all $k$. If $P=NP$, then $\Sigma_2 TIME[n]$ is in $TIME[n^c]$ for some fixed $c$ (the proof uses an efficient version of Cook's theorem: if there is a SAT algorithm running in time $n^d$, then any $c > d^2$ suffices). But we proved that there is a language in $\Sigma_2 TIME[n]$ that is not in $TIME[n^k]$ for every $k$. This is a contradiction, so $P \neq NP$.

Here is the proof of part (b). If every $L \in NTIME[n^k]$ could be efficiently reduced to a k-ISOLATED SAT formula (e.g., all $n$ bit instances of $L$ get reduced to $k$-ISOLATED SAT formulas of at most $f(k) n^{c}$ size) then $NP=\bigcup_{k} NTIME[n^k] \subseteq \Sigma_2 TIME[n^{c+1}]$. This would immediately imply $coNP \neq NP$, but moreover it just looks very unlikely that all of $NP$ can be simulated so efficiently within the polynomial hierarchy.


Labels for terms in the lambda calculus In the lambda calculus, are there commonly accepted names for $x$ and $M$ when they appear in $\lambda x [M]$  ? Something along the lines of "binder" and "bindee"?

$x$ is a "bound variable" and $M$ is the "scope" in which it is bound.


Rademacher complexity beyond the agnostic setting The way I know of to bound generalization error by Rademacher complexity is Theorem 2.4 in this lecture notes, http://ttic.uchicago.edu/~tewari/lectures/lecture9.pdf. Here the quantity on the LHS that Rademacher complexity is trying to upperbound is given as, $L_{\phi}(\hat{f}_{\phi}^*)-\min_{f \in F} L_{\phi}(f)$ where $F$ is some "hypothesis class" of functions mapping $ f :X \rightarrow D$, $\phi : D \times Y \rightarrow [0,1]$ is the "loss function", "$\phi-$"loss of any function $g : X \rightarrow D$ is defined as, $L_\phi(g) = \mathbb{E}[\phi(f(x),y)]$ - where the expectation is taken over some distribution over the points $(x,y) \in X \times Y$ and $\hat{f}_{\phi}^*$ is what the ERM returns over some $m$ samples i.e $\hat{f}_{\phi}^* = \mathrm{argmin}_{f \in F} \frac{1}{m} \sum_{i=1}^m \phi(f(x_i),y_i)$.
The above setting is called ``agnostic" because at no point was it assumed that, $\exists$ any ground-truth labelling function $L \in F$ such that $y = L(x)$ but rather the class $F$ is to be seen to be trying to learn via empirical risk minimization a distribution, say ${\cal D}$, over $X \times Y$.
My question is 3 fold , is there any analogue of this Theorem $2.4$ when,
(a)
an existence of a $L$ is assumed with $L$ may or maynot be in $F$. (the later is I guess often called the ``realizable setting") (...I have seen some papers trying to bound generalization error of a specific algorithm in the realizable setting but I somehow dont see Rademacher complexity defined in those settings!..)
(b)
the loss function $\phi$ is not assumed to be bounded above but only assumed to be bounded below.
(c)
AND most importantly, say I have a class of labelling functions ${\cal L}$ mapping $X \rightarrow Y$ and I want to say the following, "Given a loss function $\phi$, irrespective of which member of ${\cal L}$ labels the data (maybe also irrespective of the distribution over $X$ used to measure $L_{\phi}$) the member of class $F$ obtained via ERM on the data, can never generalize well". Is there a version of Rademacher complexity which captures this?

(a) If you don't assume that you're "competing" against $f\in F$, you must make some assumption about the larger function class to which $f$ belongs -- otherwise, by standard no-free-lunch theorems, you will not be able to give any meaningful risk decay rates (which is what Rademacher complexities enable you to do). Alternatively, you could assume something about the distribution (trivial case: it has finite support). Then you can get distribution-dependent rates.

(b) For unbounded losses, you typically need additional assumptions such as convexity or tail decay. See, eg,
https://papers.nips.cc/paper/3894-smoothness-low-noise-and-fast-rates
and
http://proceedings.mlr.press/v32/kontorovicha14.html

(c) It looks like you're looking for a lower bound on the risk in terms of Rademacher complexity. Any such result would have to be distribution-dependent. Since Rademacher complexity is majorized by covering numbers (via Dudley's integral) and also minorized by these (Sudakov inequality), you could probably use the covering-number characterization of learnability:
https://www.sciencedirect.com/science/article/pii/030439759190026X


Does there exist the idea of "RP-complete", like NP-complete? NP-hardness and NP-completeness play an important role in complexity theory.
My question is, does there exist a language $L$ in RP
to which any language $M$ in RP can be reduced in polynomial time?
We can say that such a language $L$ is "RP-complete", if exists, but I cannot find any information about this idea. Can anyone tell me about it, please?

Yes: the concept of "X-complete under Y-reductions" exists for any complexity class X and any class Y of reductions.  However, there may or may not be any complete problems under this definition, depending on what X and Y are. For example, it is well-known that NP has complete problems under polynomial-time, logspace and even first-order reductions, but it does not have complete problems under linear-time reductions as this would violate the time hierarchy theorem.

As far as I can see, it is open whether there is a class of reductions under which RP has complete problems. The issue is that it is a so-called semantic class: it is defined by a non-computable set of Turing machines, namely polynomial-time randomized Turing machines with the undecidable requirement that, for every input, either every path rejects or at least half accept. See this question for more details on the issues surrounding complete problems for semantic classes.


Parallel sorting: introduction and state of research there seem to exist papers on parallel sorting, but I have not found a good introduction into this topic.

So, do you know a good summary or introduction into parallel sorting algorithms? In particular, I am looking for some good and handy examples that realize best lower bounds (e.g. like merge sort in the sequentiel case.), if available.

Parallel algorithms are very dependent on the computation model, and there are a lot of different parallel models. So, it is difficult to have a representative general introduction.

I teach parallel algorithms following the pattern I first saw in a similar course by my PhD advisor. I spend the first few lectures on sorting networks, covering Batcher's constructions, and AKS very briefly. Then I introduce a specific general-purpose parallel computation model (BSP suits me very well), and cover five or six textbook-type algorithmic problems, first recalling their sequential algorithms, and then discussing with students how to parallelize them efficiently.

Sorting is one of these problems. Its BSP solution is very elegant: parallel sorting by regular sampling (presented in the original paper by Shi and Schaeffer, and also Quinn's book "Parallel Computing"). It does realise the relevant lower bounds in computation, communication and, surprisingly, also synchronisation - by synchronising the whole computation only a constant number of times (whereas looking at mergesort and AKS, one would expect to have to synchronize O(log n) times). The optimality proof is non-trivial, yet simple enough to be presented in an undergraduate class in 20 minutes - so for me, it is indeed a very good and handy example to teach.

Another good example is Leighton's columnsort - I am not teaching it, but would be if I had a bit more time.


Law of excluded middle in MLTT Is it possible to add law of excluded middle to Martin-Löf type theory as an axiom? It seems to me, that it's possible to add it to Coq since Coq has a module for non-constructive reasoning. Also, it seems to be impossible to Agda since it leads to inconsistency. But can we add it to plain MLTT? And why it will/won't work?

Law of excluded middle does not make intuitionistic logic inconsistent; intuitionistic logic is in many regards a subset of classical logic (of course classical logic can't have proof objects and there are other diffrences). In Agda you can use the postulate keyword for such things. The following could be added to your postulates.

$LEM : \{A : Set\} \to A \lor \neg A$

I was doing some proofs out of a book on first order logic where I found it more useful to have double negation elimination than LEM.

$\neg\neg E : \{A : Set\} \to \neg\neg A \to A$

One of course implies the other so take your pick.

edit:
One of your previous questions gives some insight here as well. cody made mention of Agda being predicative. Martin Lof type theory is predicative (as well as Agda which is basically MLTT). Agda still has large elimination and adding LEM does not make the logic inconsistent. Martin Lof originally tried to base MLTT off of System-F but its impredicative nature kept getting in the way of such things. This is part of the reason why MLTT is predictive.


How to translate the axiom schema of induction by Curry-Howard? I'm trying to understand the Curry-Howard correspondence. I am comfortable with it for propositional logic, but get confused when $\forall, \exists$ quantifiers come in the picture.

The axiom schema of induction (in second-order logic) is  $\forall P. \left[(P(0) \implies \forall k\in \mathbb N. (P(k)\implies P(k+1)))\implies \forall n\in \mathbb N. P(n)\right]$.

To my understanding, via Curry-Howard every statement gets translated to a type. Proving a statement means showing that the type is inhabited. For example, +, = are dependent types taking two parameters of type nat; every $\forall k\in A$ gets translated into a dependent product $\prod_{k::A}$. So the axiom schema should become something like
$
\left[\prod_{P::?} \left((P\, 0) \rightarrow \left(\prod_{k::\mathbb N} (P \, k)\rightarrow P \, (+\, k\, 1) \right)\right)\right]\rightarrow \prod_{n::\mathbb N}(P \,n)
$

A difficulty arises when translating $\forall P$: what is the type of $P$? The problem is that, in order for the above to make sense, $(P\, k)$ is supposed to be a type for all $k::\mathbb N$ (so we are allowed to say $(P\, 0) \rightarrow \cdots$, for instance). So $P$ seems to me like a (dependent) type constructor taking a nat as parameter. But then we are taking a product over $P$, so we must be able to treat $P$ as an element of a type! The problem seems to boil down to, are type constructors themselves of some type? Can we write this statement without having to refer to such a type? Perhaps higher-order logic translates to higher-order type theory, but I do not know the latter. References would also be appreciated.

First a correction. The statement
$$\forall P \,.\, (P(0) \Rightarrow (\forall n . P(n) \Rightarrow P(S n)) \Rightarrow \forall m . P(m)),$$
is not the schema of induction, but rather induction written in second-order arithmetic.
To get the schema you need to avoid $\forall P$. This is done by saying that there are infinitely many axioms of the form
$$P(0) \Rightarrow (\forall n . P(n) \Rightarrow P(S n)) \Rightarrow \forall m . P(m),$$
one for each formula $P(x)$. That is, whereas in your axiom $P$ refers to arbitrary subsets of $\mathbb{N}$, in the schema it refers to sytnactic entities, namely formulas with parameter $x$. It is called a "schema" because it prescribes a shape from which infinitely many axioms may be generated by plugging in all possible syntactic entities $P$.

To answer your question, we just have to look at the Curry-Howard correspondence to see what a predicate $P(x)$ correspond to. The answer is type family or dependent type. Because you wrote your axiom in second-order arithmetic, it became unclear how to quantify over dependent types. This is possible by using universes, for instance Daimano in his answer used $\mathsf{Prop}$, the universe of propositions. However, under the pure Curry-Howard there is no $\mathsf{Prop}$, there are only types.

We have two options. If we translate the schema, then it is this: for every dependent type $$x : \mathbb{N} \vdash P(x) \, \mathsf{type}$$ we get the type
$$\textstyle P(0) \to (\prod_{n:\mathbb{N}} P(n) \to P(S n)) \to \prod_{m:\mathbb{N}} P(m)$$
If we translate the second-order formulation of induction, we need to use a type universe $\mathsf{Type}$, and then we get
$$\textstyle
\prod_{P : \mathbb{N} \to \mathsf{Type}}
P(0) \to (\prod_{n:\mathbb{N}} P(n) \to P(S n)) \to \prod_{m:\mathbb{N}} P(m)$$

What are these types inhabited by? In the case of schema, they are inhabited by primitive recursors $\mathsf{rec}_P$ which satisfy the equations
\begin{align*}
\mathsf{rec}_P \; z \; f \; 0 &= z \\
\mathsf{rec}_P \; z \; f \; (S n) &= f \; n \; (\mathsf{rec}_P \; z \; f \; n)
\end{align*}
Depending on the details of your formalism we may be able to drop the subscript $P$ on $\mathsf{rec}_P$, and just write $\mathsf{rec}$ -- but secretly there is a different $\mathsf{rec}$ for each $P$.

In the case of the second-order induction we would get a single primitive recursor $\mathsf{rec}$ satisfying
\begin{align*}
\mathsf{rec} \; P \; z \; f \; 0 &= z \\
\mathsf{rec} \; P \; z \; f \; (S n) &= f \; n \; (\mathsf{rec} \;P \; z \; f \; n)
\end{align*}

If I spoke to a Haskell programmer I would say that in the case of schema each $\mathsf{rec}$ was obtained from $P$ using a "deriving" clause, whereas in the second-order case there is a single polymorphic $\mathsf{rec}$.


Proofs obtained only through spectral graph theory I have an increasing interest in spectral graph theory, which I find fascinating, and I've started collecting a few documents that I have yet to read more thoroughly than what I so far have.

However, I'm curious about a statement that popped up in several sources (for instance over there), which says in essence that some results in graph theory have been proved using spectrum-based techniques only, and that so far, no proof that bypasses those techniques is known.

Unless I skipped that, I don't recall seeing such an example in the literature I've read so far. Do any of you know of examples of such results?


Finding minimum spanning 1-tree We are considering a connected weighted graph G. 1-tree is a tree with one extra edge added (so it contains exactly one cycle). The task is to find minimum spanning 1-tree of G.
I was thinking of first using any of well-known MST algorithms and then adding an edge of smallest weight to the MST (which is not in the MST). Will something like this work (I am having trouble proving it would)?

I'm not sure this is research level, but here's a sketch. Suppose this algorithm outputs a 1-tree and the actual cheapest 1-tree is some other 1T. Now, since you built your tree with Kruskal's algorithm, you know that the tree directly proceeding adding your last edge(the cycle-inducing edge) was minimal, and as such costs less than any subtree of the "true" cheapest 1-tree.

So, consider the subtree of the "true" 1-tree that is comprised of all edges save one edge in the cycle that your tree doesn't contain(it is easy to show that, unless their cycles are equal, this edge must exist)*. This tree is more expensive than yours. Moreover, since your tree is a tree, adding that edge from the "true" 1T would have made yours a 1-tree. So your final edge must be cheaper than that edge, or you would have chosen that edge. Thus, your 1-tree must be cheapest.

*If the cycles are the same, but the remaining subtrees are different, you are also done since yours was built using Kruskal's algorithm.


Consequences/existence of problems without any "optimal" algorithm Let $P$ be some kind of "problem" such as addition or graph coloring, that has an input size $n$. Let $S_P$ denote the set of algorithms $A_1, A_2, \dots$ which deterministically solve $P$. Based off this, let $S'_P$ denote the set of "optimal" algorithms that solve $P$, in other words:

$$S'_P :=  \{A_i ∈ S_P | \nexists A_j ∈ S_P  \textrm{ s.t.} \lim_{n \to \infty} \frac{O(A_i)}{O(A_j)} = 0 \}$$

Is there an example of a problem when $S_P$ is non-empty, but $S'_P = \emptyset$? Also, are there any significant implications concerning the existence/non-existence of such a problem?

Blum's speedup theorem, proved in 1967, shows that there is such a problem $P$ that has no optimal algorithm.

The problem $P$ doesn't look all that much like addition or graph coloring - it's defined in terms of sets of machines $Z_i$, the primitive recursive functions $\phi_i(n)$ computed by the $i$th machine, and "step-counting functions" $\Phi_i(n)$ (which count how many steps the $i$th machine took to execute its function), and involves search over the latter in order to achieve the desired properties :).

It's a good reminder that the space of algorithms is large and counterintuitive - especially when the inputs and outputs are themselves programs. But you're also not likely to see this sort of weirdness until your inputs are programs, either, and maybe not even then depending on what you're trying to do with them...

Reference:

Blum, Manuel. "A machine-independent theory of the complexity of recursive functions." Journal of the ACM (JACM) 14.2 (1967): 322-336.