Can a random oracle change which TFNP problems are strongly hard-on-average? I've been thinking about the following question at

various times
since I saw this question on Cryptography.

Question

Let $R$ be a TFNP relation.  Can a random oracle help P/poly

to break $R$ with non-negligible probability?  More formally,
$
\newcommand{\Pr}{\operatorname{Pr}}
\newcommand{\E}{\operatorname{\mathbb{E}}}
\newcommand{\O}{\mathcal{O}}
\newcommand{\Good}{\mathsf{Good}}
$

Does

  for all P/poly algorithms $A$,
  $\Pr_x [R(x, A(x))]$ is negligible

necessarily imply that

  for almost all oracles $\O$,
  for all P/poly oracle-algorithms $A$,
  $\Pr_x [R(x, A^\O(x))]$ is negligible

?

Alternative formulation

The relevant set of oracles is $G_{\delta\sigma}$ (thus measurable), so by taking contrapositive and applying Kolmogorov's zero-one law,
the following formulation is equivalent to the original one.

Does

  for almost all oracles $\O$,
  there exists a P/poly oracle-algorithm $A$ such that
  $\Pr_x [R(x,A^\O(x))]$ is not negligible

necessarily imply that

  there exists a P/poly algorithm $A$ such that
  $\Pr_x [R(x,A(x))]$ is not negligible

?

The uniform case

Here's a proof for the uniform version:

There are only countably-many PPT oracle-algorithms,
so by countable additivity of the null [ideal][8],
there is a PPT algorithm $A$ such that
for a non-null set of oracles $\O$,

$\Pr_x [R(x,A^\O(x))]$ is non-negligible.
Let $B$ be such an oracle-algorithm.

Similarly, let $c$ be a positive integer such that
for a non-null set of oracles $\O$,

$\Pr_x[R(x,B^\O(x))]$
is infinitely-often at least $n^{-c}$,
where $n$ is the length of the input.

By the contrapositive of Borel-Cantelli,
$\sum_{n=0}^{\infty} \Pr_{\O} \left[
n^{-c} \leq \Pr_{x\in\{0,1\}^n}[R(x,B^\O(x))]
\right]$ is infinite.

By the comparison test, infinitely often
$\Pr_{\O} \left[
n^{-c} \leq \Pr_{x\in \{0,1\}^n}[R(x,B^\O(x))
\right] \geq n^{-2}$.

Let $S$ be the PPT algorithm which [simulates the oracle][12] and
runs $B$ with that simulated-oracle.

Fix $n$ and
let $\Good$ be the set of oracles $\O$ such that
$n^{-c} \leq \Pr_{x\in\{0,1\}^n} [R(x,B^\O(x))]$.

If $\Good$ is not null then
$$\begin{matrix}
\Pr_{\O} [\O\in \Good] \cdot n^{-c}
\\ = \\
\Pr_{\O} [\O\in \Good] \cdot \E_{\O}[n^{-c}]
\\ \leq \\
\Pr_{\O} [\O\in \Good] \cdot \E_{\O} \left[
\Pr_{x\in \{0,1\}^n} [R(x,B^\O(x))] \mid \O \in \Good
\right]
\\ = \\
\E_{\O}\left[
\Pr_{x\in \{0,1\}^n} [\O \in \Good \text{ and } R(x,B^\O(x))]
\right]
\\ \leq \\
\E_{\O}\left[
\Pr_{x\in \{0,1\}^n} [R(x,B^\O(x))]
\right]
\\ = \\
\Pr_{\O, x\in\{0,1\}^n} [R(x,B^\O(x))]
\\ = \\
\Pr_{x\in \{0,1\}^n, \O} [R(x,B^\O(x))]
\\ = \\
\E_{x\in \{0,1\}^n} \left[ \Pr_{\O}[R(x,B^\O(x))] \right]
\\ = \\
\E_{x\in \{0,1\}^n} \left[ \Pr[R(x,S(x))] \right]
\\ = \\
\Pr_{x\in \{0,1\}^n} [R(x,S(x))]
\end{matrix}$$
.

Since $\Pr_{\O} [\O\in \Good] \geq n^{-2}$ infinitely often,
$\Pr_x[R(x,S(x))]$ is not negligible.

Therefore the uniform version holds.  The proof critically uses the fact that
there

are only countably many PPT oracle-algorithms.  This idea does not work in the

non-uniform case, since as
there are continuum-many P/poly oracle-algorithms.

No to my title, and Yes to my question's body.  This in fact generalizes immediately

  to every polynomial-length game that does not use the adversaries' code.

Note that I will be using $C$ for the adversaries, rather than $A$,

so as to match up with Theorem 2's notation.

Assume that for almost all oracles $\mathcal{O}$, there exists a P/poly

oracle-algorithm $C$ such that $\operatorname{Pr}_x\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$ is non-negligible.

For almost all oracles $\mathcal{O}$, there exists a positive integer d such that

there exists a sequence of circuits of size at most d+nd such that

$\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$ is infinitely-often greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^d\hspace{-0.02 in}\right)$.

By countable additivity, there exists a positive integer d such that for a non-null set of oracles $\mathcal{O}$, there exists a sequence of circuits of size at most d+nd such that

$\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$ is infinitely-often greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^d\hspace{-0.02 in}\right)$.

Let j be such a d, and let z be the (not-necessarily-efficient) oracle-algorithm which

takes n as input and outputs the lexicographically least oracle-circuit of size at most j+n$^{\hspace{.03 in}j}$

that maximizes $\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$.    By the contrapositive of Borel-Cantelli, $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^2\hspace{-0.02 in}\right) \: < \: \operatorname{Prob}_{\mathcal{O}}\hspace{-0.05 in}\bigg[\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.03 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right) < \operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(\hspace{-0.04 in}x,\hspace{-0.04 in}\left(z^{\mathcal{O}}\right)^{\hspace{-0.04 in}\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.05 in}\right)\hspace{-0.02 in}\right]\hspace{-0.06 in}\bigg] \;\;\;$ for infinitely many n.

For such n,

$1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; = \; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}\left(\hspace{-0.02 in}n^2\hspace{-0.02 in}\right)\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right) \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^2\hspace{-0.02 in}\right)\hspace{-0.03 in}\right) \cdot \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right) \; < \; \operatorname{Prob}_{\mathcal{O}\hspace{.02 in},\hspace{.04 in}x\in \{0,1\}^n}\hspace{-0.06 in}\left[R\hspace{-0.04 in}\left(\hspace{-0.04 in}x,\hspace{-0.04 in}\left(z^{\mathcal{O}}\right)^{\hspace{-0.04 in}\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.05 in}\right)\hspace{-0.02 in}\right]$

.
Let $A$ be the oracle-algorithm that takes 2 inputs, one of which is $n$, and does as follows:

Choose a random n-bit string $x$.  Attempt to

[parse the other input as an oracle-circuit and run that oracle-circuit on the n-bit string].

If that succeeds and the oracle-circuit's output $y$ satisfies R(x,y), then output 1, else output 0.

(Note that $A$ is not just the adversary.)

For infinitely many n, $\;\;\; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; < \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \:\:\:\:$.

Let p be as in Theorem 2, and set $\;\;\; f \: = \: 2\hspace{-0.04 in}\cdot \hspace{-0.04 in}p\hspace{-0.04 in}\cdot \hspace{-0.04 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\cdot \hspace{-0.04 in}n^{(2+j)\cdot 2} \:\:\:\:$.

By Theorem 2, there exists an oracle-function $\mathcal{S}$ such that with $\mathcal{P}$ as in that theorem,

if $\;\;\; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; < \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$ then

$1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right) \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)-\left(\hspace{-0.04 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)\hspace{-0.04 in}\right) \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)\hspace{-0.04 in}-\hspace{-0.04 in}\sqrt{1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{(2+j)\cdot 2}\right)\hspace{-0.04 in}\right)}$

$= \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)\hspace{-0.04 in}-\hspace{-0.04 in}\sqrt{\left(p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right)\hspace{-0.06 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}2\hspace{-0.06 in}\cdot \hspace{-0.04 in}p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.06 in} \cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{(2+j)\cdot 2}\right)\hspace{-0.04 in}\right)} \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)\hspace{-0.04 in}-\hspace{-0.04 in}\sqrt{\left(p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right)\hspace{-0.06 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.04 in}f\right)}$

$< \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right]-\hspace{-0.04 in}\sqrt{\left(p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right)\hspace{-0.06 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.04 in}f\right)} \; \leq \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{P}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$.

For n such that $\;\;\; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; < \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$:

In particular, there exists $\big[$an oracle-circuit $C$ of size at most j+n$^{\hspace{.03 in}j}\big]$ and

$\big[$an assignment of length at most f$\big]$ such that with that input and presampling,

$A$'s probability of outputting $1$ is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$.

Oracle-circuits of size at most j+n$^{\hspace{.03 in}j}$ can be represented with poly(n) bits, so for p is bounded

above by a polynomial in n, which means f is also bounded above by a polynomial in n.

By construction of $A$, that means there are oracle-circuits of size at most j+n$^{\hspace{.03 in}j}$ and a

polynomial-length assignment such that when run with that presampling, the circuits' probability of finding a solution is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$.  Since such circuits cannot make queries longer than j+n$^{\hspace{.03 in}j}$ bits, presampled inputs longer than that can be ignored, so such presampling can be efficiently-and-perfectly simulated with a random oracle and poly(n) hard-coded bits.  That means there are polynomial-size oracle circuits such that with a standard random oracle, the circuits' probability of finding a solution is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$.  Such a random oracle can in turn be efficiently-and-perfectly simulated with just ordinary random bits, so there are polynomial-size probabilistic non-oracle circuits whose probability of finding a solution is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$.  In turn, by hard-coding optical randomness, there are polynomial-size deterministic (non-oracle) circuits whose probability (over the choice of x) of finding a solution is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$.

As shown earlier in this answer, there are infinitely many n such that $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; < \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$, $\;\;\;$ so there is a polynomial such that

the sequence whose n-th entry is the lexicographically least

[circuit C of size bounded above by that polynomial] which maximizes $\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.04 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$

is a P/poly algorithm whose probability (over the choice of x) of finding a solution is non-negligible.

Therefore the implication's in my question's body always hold.

To get the same implication for other polynomial-length games, just

change this proof's $A$ to make it have the input oracle-circuits play the game.


Does "Productive function" mean just that in ME O'Neill, The Genuine Sieve of Eratosthenes? M.E. O'Neill in the Epilogue of "The Genuine Sieve of Eratosthenes" (preprint http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf DOI 10.1017/S0956796808007004) quotes Richard Bird that "union is defined in the way it is in order to be a productive function."

Is that the technical term referring to productive sets and creative sets, or is it just a manner of speaking?

The function union is defined there in the following Haskell code:

primes = 2:([3..] `minus` composites)
  where
    composites = union [multiples p | p <- primes]

multiples n = map (n*) [n..]

(x:xs) `minus` (y:ys) | x< y = x:(xs `minus` (y:ys))
                      | x==y = xs `minus` ys
                      | x> y = (x:xs) `minus` ys

union = foldr merge []
  where
    merge (x:xs) ys = x:merge' xs ys

    merge' (x:xs) (y:ys) | x< y = x:merge' xs (y:ys)
                         | x==y = x:merge' xs ys
                         | x> y = y:merge' (x:xs) ys

I haven't learned about productive sets. If it's helpful for understanding this point, I will.

Productive here just means that it isn't stuck.

An unorthodox (seemingly impredicative ) formulation of the sieve of Eratosthenes is

      S = {n : n ∈ N, n > 1} \ ⋃p ∈ S { p q :  q ∈ N, q ≥ p }

The following code is stuck, reflecting the above definition more or less verbatim:

primes = gaps 2 $ foldr (\p r-> union [p*p, p*p+p..] r) [] primes

union (x:xs) (y:ys) = case compare x y of            -- ~= sort ( (x:xs) ++ (y:ys) )
                        LT -> x : union  xs (y:ys)
                        EQ -> x : union  xs    ys
                        GT -> y : union (x:xs) ys

gaps c (x:xs) | c < x     = c : gaps (c+1) (x:xs)    -- ~= [c,c+2..] \\ (x:xs)
              | otherwise =     gaps (c+1) xs        --    when null((x:xs)\\[c,c+2..])

because primes list isn't primed with any initial data, so we get unbounded recursion. Asking take 10 primes produces no output (GHCi actually closes).

The following is also stuck (or blows up, whatever you prefer to call it):

primes = (2:) . gaps 3 . foldr (\p r-> union [p*p, p*p+p..] r) [] $ primes

because each union demands to know the head of further results on its right, to produce its results. Asking take 10 primes produces [2, and then no output (GHCi will actually close itself on this "racing to the bottom" ).

But this

primes = (2:) . gaps 3 . foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) [] $ primes

works fine, because now getting the head of the further results doesn't trigger the next union call right away.

On SO you ask how one could come up with such definition.

You could start with Turner's sieve,

primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y<- xs, rem y x /= 0]

then turn it into an optimal trial division sieve, by postponing the filters creation to the right moment,

primes = 2 : sieve primes [3..]
sieve (p:ps) xs | (h,t) <- span(<p*p)xs = h ++ sieve ps [y | y<- t, rem y p /= 0]

then make it a kind of the sieve of Eratosthenes,

primes = 2 : sieve primes [3..]
sieve (p:ps) xs | (h,t) <- span(<p*p)xs = h ++ sieve ps (minus t [p*p, p*p+p ..])

minus (x:xs) (y:ys) = case compare x y of
                        LT -> x : minus  xs (y:ys)
                        EQ ->     minus  xs    ys
                        GT ->     minus (x:xs) ys

The last step is to realize that (...(((xs-a)-b)-c)-...) == xs - (a+(b+(c+(...)))). (And the next step, that (a+(b+(c+(...)))) == a + ( (b+c) + ( ((d+e)+(f+g)) + ( ... ))).)

(or, it could "dawn on" you).

(edit:) one more way is to tweak your SO code actually. :) with just some minor tweaks it becomes the very nice

primesA :: [Integer]
primesA = 2 : 3 : sieve 5 [9, 15 ..]

sieve p cs@(c : t)
   | p == c    =     sieve (p + 2) t
   | otherwise = p : sieve (p + 2) (union cs [p*p, p*p+2*p ..])

(though not properly postponed at all) which is finally fixed with

primesA = [2,3,5] ++ sieve 7 (foldr (\p r-> p*p : union [p*p+2*p, p*p+4*p ..] r)
                                    [] $ tail primesA)

sieve p cs@(c : t)
   | p == c    =     sieve (p + 2) t
   | otherwise = p : sieve (p + 2) cs

as can be seen, your sieve is what I called gaps above.


Is there an oracle such that SAT is not infinitely often in sub-exponential time? Define $io$-$SUBEXP$ to be the class of languages $L$ such that there is a language $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ and for infinitely many $n$, $L$ and $L'$ agree on all instances of length $n$. (That is, this is the class of languages which can be "solved infinitely often, in subexponential time".)

Is there an oracle $A$ such that $NP^A \not\subset io$-$SUBEXP^A$? If we equip SAT with the oracle $A$ in the usual way, can we say that $SAT^A$ is not in this class?

(I'm asking separate questions here, because we have to be careful with infinitely-often time classes: just because you have a reduction from problem $B$ to problem $C$ and $C$ is solvable infinitely often, you may not actually get that $B$ is solvable infinitely often without further assumptions on the reduction: what if your reduction from $B$ "misses" the input lengths that you can solve $C$ on?)

You can just take the oracle A s.t. NP$^A$=EXP$^A$ since EXP is not in i.o.-subexp. For SAT$^A$ it depends on the encoding, for example if the only valid SAT instances have even length then it is easy to solve SAT on odd-length strings. But if you use a language like $L=\{\phi 01^*\ |\ \phi\in SAT^A\}$ then you should be fine.


Converting a Bernoulli to a Gaussian It is not hard to see that, given one sample from a univariate unit-variance Gaussian $X\sim \mathcal{N}(\mu,1)$ with unknown $\mu$ s.t. $0<|\mu|\leq 1$, one can simulate one draw from a
"Bernoulli" random variable $Y\in\{-1,1\}$ with $|\mathbb{E}[Y]| = \Theta(|\mu|)$. (Basically, just take $Y=\operatorname{sign}(X)$.)
Is it possible to do the converse (even allowing extra randomness, independent of the sample)? That is:

Given one realization of some random variable $Y\in\{-1,1\}$ with (unknown) $\mathbb{E}[Y] = \mu$, output $X\sim \mathcal{N}(\nu,1)$ s.t. $|\nu| = \Theta(|\mu|)$.

I conjecture that to be impossible (I have some mild contrived evidence), but I don't really see how one would go about proving that.

Suppose you had such a randomized procedure that takes a value in $\{-1,1\}$ and outputs a real number. Let $P$ and $Q$ be the output distribution on input $+1$ and $-1$ respectively.
Consider the extreme case of $\mu = +1$. In this case $Y = +1$ for sure, and you are outputting a sample from $P$, which means that $P$ should be an $\mathcal{N}(\nu, 1)$ distribution for some $\nu$ with $|\nu|$ being $\Omega(1)$. Similarly, the other extreme of $\mu=-1$ tells us that $Q$ is a $\mathcal{N}(\nu', 1)$ distribution for some $\nu'$ with $|\nu'|$ being $\Omega(1)$.
But now, for $\mu=0$, you are outputting the uniform mixture of two normals, which cannot be a normal distribution unless $\nu=\nu'$. In the latter case, you get $\mathcal{N}(\nu, 1)$ for some $\nu$ bounded away from zero.
Thus you cannot satisfy this requirement simultaneously for $\mu\in \{-1, 0, 1\}$.


Is ALogTime != PH hard to prove (and unknown)? Lance Fortnow recently claimed that proving L != NP should be easier than proving P != NP:

  Separate NP from Logarithmic space. I gave four approaches in a pre-blog 2001 survey on diagonalization (Section 3) though none have panned out. Should be much easier than separating P from NP.

Section 3 in the linked survey claims that there are no meaningful oracle collapse results:

  While the P != NP question remains quite formidable, the L != NP question seems much more tractable. We have no reason to think this question is difficult. The lack of good relativization models for space means we have no meaningful oracle model where L and NP collapse. Also since L is a uniform class, the Razborov-Rudich [RR97] limitations do not apply.

A question about known relativization barriers to L != NP on this site got an answer pointing out that the PSPACE-complete problem TQBF can be used as oracle to get such a collapse. An objection about whether this was a meaningful oracle model seems to be answered too.

But even if I would understand why "we have no meaningful oracle model where L and NP collapse" should be considered to be a correct statement, I would still have my doubts whether proving L != NP is any more feasible than proving P != NP. If proving L != NP should really be easier than proving P != NP, then proving ALogTime != PH should definitively be within reach. (The survey article hints at the possibility to separate $\Sigma_2^p$ from $L$.) I guess ALogTime != PH is still open, and I would like to know whether there are good reasons to expect that it will be hard to prove.

Not sure why Fortnow says there's "no meaningful model where $L$ and $NP$ collapse"... it seems to me that QBF should make them collapse, under the usual Ruzzo-Simon-Tompa oracle model (and the link you included agrees). Note this oracle model also has its quirks: we have $L = NL$ if and only if $L^A = NL^A$ for every oracle $A$, so any oracle witnessing a separation would imply the unrelativized separation.

ALogTime = LOGTIME-Uniform $NC1$. So yes, $ALogTime = NP$ is open. There is a relativized notion of uniform $NC1$, and you can collapse $NP$ and $NC1$ under that notion. See Theorem 6 in http://link.springer.com/article/10.1007/BF01692056.
(A caveat: technically speaking, that paper considers LOGSPACE-uniform NC1, but I believe some reasonable version of that oracle construction should work in the LOGTIME-uniform setting.)

Beyond that, I know of no particular reason to believe it is "hard to prove" other than the observation that many people have tried and none have succeeded yet.


What are bounded-treewidth circuits good for? One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output of a gate having $a$ as input (or vice-versa); connect wires $a$ and $b$ whenever they are used as inputs to the same gate. Edit: one can equivalently define the treewidth of the circuit as that of the graph representing it; if we use associativity to rewite all AND and OR gates to have fan-in at most two, the treewidth according to either definition is the same up to a factor $3$.

There is at least one problem that is known to be untractable in general but tractable on Boolean circuits of bounded treewidth: given a probability for each of the input wires to be set to 0 or 1 (independently from the others), compute the probability that a certain output gate is 0 or 1. This is generally #P-hard by a reduction from e.g. #2SAT, but it can be solved in PTIME on circuits whose treewidth is assumed to be less than a constant, using the junction tree algorithm.

My question is to know whether there are other problems, beyond probabilistic computation, that are known to be intractable in general but tractable for bounded-treewidth circuts, or whose complexity can be described as a function of the circuit size and also of its treewidth. My question is not specific to the Boolean case; I am also interested in arithmetic circuits over other semirings. Do you see any such problems?

We now understand that for any fixed bound $k \in \mathbb{N}$ on the treewidth, we can convert any Boolean circuit of treewidth less than $k$ to a so-called d-SDNNF circuit, in linear time and with the dependency on $k$ being singly exponential.

The so-called d-SDNNFs are circuits satisfying conditions on the use of negation (only at the leaves), determinism (the inputs to OR-gates are mutually exclusive), decomposability (the inputs to AND-gates depend on disjoint sets of variables), and stucturedness (the AND-gates split the variables in some fixed way throughout the circuit, as described by a v-tree). This class has been studied in knowledge compilation and is known to enjoy tractable SAT and tractable model counting (recapturing probabilistic evaluation and counting), but other problems have been studied for this class such as enumeration, quantification, etc.

So one way to use bounds on the treewidth of a circuit is to convert it to this d-SDNNF class which has more explicit properties in terms of the circuit semantics, and for which there are several known results on the tractability of various tasks.


Phonology and lambda calculus I wonder whether there is any relationship between lambda calculus and phonology (study of phonemes). Specifically, how one would use the concepts of lambda calculus (typed or untyped) in the study of phonology of a particular natural language, like English, German, or Finnish? It would be much appreciated, if you could mention some introductory texts, papers, books, etc. about this.

This is just a long comment (too many words to fit in a comment box).
Gérard Huet is, among other things, an expert in $\lambda$-calculus who worked worked a lot on the computational processing of Sanskrit, including its phonological aspects.  I remember him once giving a talk in Marseilles entitled Des Lambdas et des Aums ("Lambdas and Oms") but unfortunately I do not recall whether he made any explicit connection between the two (it was a very informal talk in honor of Per Martin-Löf, who was to receive a doctorate honoris causa from the University of Aix-Marseille 2 a few days later.  All this was nearly 16 years ago).
I browsed a bit his web page (linked above), there's a lot of material on the computational analysis of Sanskrit (including phonetics) but none of it seems to mention the $\lambda$-calculus (there's some OCaml programming at best).  Since, as I said, Huet knows the $\lambda$-calculus extremely well, my guess is that had he seen any connection between the latter and Sanskrit phonology, he would have stressed it.  But certainly the best is just to ask him directly!  I'm sure he'll be glad to tell you.
PS: perhaps a little bit of motivation/background to your question wouldn't hurt.  Why do you think there should be any relationship between $\lambda$-calculus and phonology?  I guess I can vaguely understand the motivation behind a computational approach to phonology, but why the $\lambda$-calculus?


Hadwiger number under matching contraction Given a graph $G$ with Hadwiger number $h(G)$ and a matching $M$ of $G$. Let $G/M$ be the simple graph obtained by contracting $M$. I am looking for a lower bound on the Hadwiger number of $G/M$ as a function of $h(G)$, say: $$h(G/M) \geq \Omega(\log h(G))$$ (or something like that), or a counter example to show that there is no such bound. Does anybody have any pointer on this?

I think the right bound is: $$h(G/M) = \Omega(h(G))$$
but I am unable to prove (or disprove) it. This is based on two observations: contracting a matching of $K_h$ resulting in $K_{h/2}$ and the similar situation holds for treewidth parameter: contracting a matching of a treewidth $k$ graph resulting in a graph of treewidth at least $k/2$ (though treewidth is loosely connected to Hadwiger number).

From Wikipedia: Hadwiger number $h(G)$ is the largest number $k$ for which the complete graph $K_k$ is a minor of $G$.

There is no such function - here is an example where $h(G)$ is arbitrarily large while $h(G/M) \leq 4$. Make $G$ by taking two copies of an $n \times n$ grid and making every vertex of one grid adjacent to the corresponding vertex of the other grid.

$G$ contains a clique of size $n$ as a minor (i.e $h(G) \geq n$). In particular the $i$'th vertex of the clique is obtained by contracting the $i$'th row of the first grid and the $i$'th column of the second grid and then contracting these two vertices together.

Let $M$ be the matching that connects each vertex of the first grid with its copy in the second grid. $G/M$ is an $n \times n$ grid, so $G/M$ is planar and hence $h(G/M) \leq 4$.


Why is the first step in the Lovasz-Vempala convex volume algorithm correct? I've been reading about convex volume estimation, and have found the paper "Simulated Annealing in Convex Bodies and an $O^{*}(n^4)$ Volume Algorithm" by Lovasz and Vempala, which can be read here.

The algorithm provided relies the standard multi-phase monte-carlo technique of producing a series of values, the first of which is easy to compute, the remainder estimatable by random variables, and then combining each of these variables in some way to produce an estimate of the volume. This particular technique involves extruding an $n$-dimensional shape into an $n+1$-dimensional pencil, and estimating the volume of that pencil. The pencil is defined as the intersection of a cylinder over the convex body and a cone. Let $K$ be the convex body, and

$$
C = \{{\bf x} \in \mathbb{R}^{n+1} | x_0 > 0, \; \sum^n_{i=1}x_i^2 \leqslant x_0^2\}
$$
The pencil, $K'$, is defined:
$$
K' = ([0,2D] \times K) \cap C
$$

By assumption, $K$ contains the unit ball, so the set of points in $K'$ with $x_0<1$ is exactly the $n+1$-dimensional hypercone with height $1$ and whose base is the $n$-ball of radius $1$. This cone is referred to as $C_B$. We also denote by $\pi_n$ the volume of the unit n-ball. The estimates of the volume of the pencil are provided using the following function:

$$
Z(a) = \int_{K'} e^{-ax_0} d{\bf x}
$$

For a sufficiently small value of $a$, $Z(a)$ can be shown to be a good estimate for the volume of $K'$. For $a \geqslant 2n$, it is claimed that $Z(a)$ is close to the above integral taken over the entire cone $C$. We know that $K' \subseteq C$ from its definition, hence

$$
Z(a) = \int_{K'} e^{-ax_0} d{\bf x} \leqslant \int_{C} e^{-ax_0} d{\bf x} = \int_0^\infty e^{-at}t^n \pi_n dt = n! \pi_n a^{-(n+1)}
$$

We know also that $C_B \subseteq K'$, hence

$$
Z(a) \geqslant \int_{C_B} e^{-ax_0} d{\bf x} = \int_0^1 e^{-at}t^n \pi_n dt
$$

At this point, I can no longer follow the paper's reasoning. It is stated that

$$
\int_0^1 e^{-at}t^n \pi_n dt > (1-\varepsilon) \int_0^\infty e^{-at}t^n \pi_n dt
$$

No bounds are specified on $\varepsilon$. Indeed, our estimation algorithm should be able to take an arbitrarily small value of $\varepsilon$. The integrand, hovever, is non-negative across its domain of integration, so it must be the case that

$$
\int_0^1 e^{-at}t^n \pi_n dt \leqslant \int_0^\infty e^{-at}t^n \pi_n dt
$$

Surely, then, the inequality in $\varepsilon$ would only hold for a sufficiently large value of $\varepsilon$, rather than for an arbitrarily small one. Further, stating that $a\geqslant 2n$ gives no information about a relationship between $\varepsilon$ and $a$. How is it even possible to reach the conclusion from the premise in this case? Further still, an independent talk on the algorithm found here suggests instead that the inequality only holds for $a>6n$, rather than $a>2n$. The paper states that this is true by standard computation, so I do feel that I must be missing something here, but I cannot tell what.

I've emailed both of the authors at the email addresses I can find for them, and haven't received any response from them, so hopefully someone from here can help.

It is also unclear to me what $\epsilon$ means in that line of the paper.
The approximation error for $Z(a_0)$ is never mentioned again;
my interpretation is that the authors are saying the error is so small it can
be ignored.

The bound I get is:
$$ \tag{*} Z(a_0)=Z(2n) \geq (1-(2/e)^n \mathrm{poly}(n)) \int_0^\infty e^{-2nt} t^n \pi_n dt.$$

So the approximation should be ok for $n > 100 \log \epsilon^{-1}$ and large $n$.
I don't know if it is necessary to use a different analysis or algorithm
to get Theorem 1.1 as stated for the regime where
$\epsilon$ is exponentially small compared to $n$.

To show (*), I claim the stronger statement that
$\int_1^\infty e^{-at}t^n dt \leq e^{-a}/n$
for all $a\geq 2n$ - this can be shown by induction on $n$.
Using Stirling's approximation on $\int_0^\infty e^{-2nt}t^n dt=n!(2n)^{-(n+1)}$,
$$ \frac{\int_1^\infty e^{-2nt}t^n dt}
{\int_0^\infty e^{-2nt}t^n dt}
\leq \frac{e^{-2n}(2n)^n}{n^n e^{-n}} \mathrm{poly}(n)
= (2/e)^n \mathrm{poly}(n).
$$


Is there a tool for finding Nash equilibria in parametric games? There are a few tools, either online or offline, that could solve (find equilibrium) in a game explicitly given as a real-valued matrix.

Such tools are Game Theory Explorer and Gambit.

However, as far as I know, these can not be used for finding equilibrium in a game with parameters.

For example, consider a two player game symmetric game, parametrized by some $x\in[0,1]$, which is given by the following payoff matrix for the row player (and $A^t(x)$ for the column player):
$$A(x)=
 \left( \begin{array}{ccc}
\frac{x}{2} & x \\
1-x & \frac{1-x}{2} \\
\end{array} \right) $$

Each equilibrium in this game can be represented as $<p_a,p_b>\in[0,1]^2$ where $p_a$ is the probability of the first player playing the first strategy and $p_b$ is the probability the second player plays the first strategy.

Analytically we can find all the equilibriums for this game

$$EQ(x)=
\begin{cases}
\{<1,1>\}&\mbox{if } x>\frac{2}{3}\\
\{<3x-1,3x-1>,<1,0>,<0,1>\}&\mbox{if } \frac{1}{3}\leq x\leq\frac{2}{3}\\
\{<0,0>\}& \mbox{else}
\end{cases}
$$

I'm looking for a solver which is able to understand inputs like $A(x)$ and produce $EQ(x)$.

  Is there a tool which solves parametric games?

Is there a tool which solves parametric games?

Not that I am aware of (I am a co-author of GTE and help with Gambit).

The best suggestion I have if you don't find such a tool (and I doubt one exists) is to do a parameter sweep and solve a bunch of individual instantiations and see what the resulting sets of equilibria say about $EQ()$. Gambit is very tightly integrated with python, so you can easily define your game as a python function with the parameters as arguments and solve a set of instances via a parameter sweep.


Find the remainder of a large fixed polynomial when divided by a small unknown polynomial Assume we operate in a finite field. We are given a large fixed polynomial p(x) (of, say, degree 1000) over this field. This polynomial is known beforehand and we are allowed to do computation using a lot of resources in the "initial phase." These results may be stored in reasonably small look-up tables.

At the end of the "initial phase", we will be given a small unknown polynomial q(x) (of, say, degree 5 or less).

Is there a fast way to compute p(x) mod q(x) given that we are allowed to do some complicated calculations in the "initial phase"? One obvious way is to calculate p(x) mod q(x) for all possible values of q(x). Is there a better way to do this?

The following algorithms works well if the underlying field has a very small order $s$.

Suppose we know $q$ is irreducible, of a fixed degree $d$. Then, mod $q$, we know $x^{s^d} = x$ holds. Hence it suffices to pre-compute $p(x) \mod x^{s^d} - x$.

In general, $q(x)$ may decompose into a product of irreducible polynomials $q = q_1 \dots q_r$. In this case, a similar argument applies to computing $p$ modulo each $q_1, \dots, q_r$ separately, and then piecing the results together. So we really need to compute $p(x) \mod x^{s^{d'}} - x$ for each $d' \leq d$.


Is there any task where classical computers outperform quantum computers? Everybody knows that there are whole classes of problems which quantum computers are able to solve much faster (i.e. with fewer instructions) than classical computers.

Is there any problem for which the reverse is true?

If you're asking whether a quantum computer can compute any function that a classical computer can compute without using many more elementary computational steps, then the answer is yes: a quantum computer can perform any reversible classical computation, and if you keep the input around, any classical computation can be made reversible at a cost of multiplying the number of steps by a small constant factor.

If you're asking whether a quantum computer can compute any function that a classical computer can without using many more resources, the answer is much less clear. The construction that lets you make a $T$-step computation reversible using $O(T)$ steps also takes $O(T)$ space (i.e., memory cells). You can achieve a smaller blow-up in space at the cost of a superlinear number of steps. See Time/Space Trade-Offs for Reversible Computation by Charles H. Bennett.

For an actual physical quantum computer, it's very likely that you might also be able to make it faithfully simulate a classical computer by letting it lose coherence, but in this case it's no longer really working as a quantum computer, and if you try to use a quantum computer that is operating this way as a subroutine in a quantum computation, it might not work properly.


Proof that the theory of rationals is convex In Example 10.12 of the book The calculus of computation by Bradley and Manna, it is said

The theory of rationals is convex, as it is convex in a geometric sense.

How does the geometric sense of convex relate to theories being convex?
It further gives a proof by contradiction but I am unclear on what the assumptions are, what is being contradicted and how.

The theory of rationals TQ is convex, as it is convex in a geometric sense ... Each equality ui = vi of the disjunction G of is geometrically convex, but G itself is not. Consider, for example, H : x=y ∨ x=z. Let SH be the set of points satisfying H. The point (x,y,z) = (0,0,1) is included in SH , as is the point (1,0,1). However, the average of the two points, (12, 0,1) (choosing λ = 1/2), is not in SH. Indeed, choose any two points (u, u,v1) and (w,v2,w) from Sx=y and Sx=z, respectively, such that neither is in their intersection Sx=y=z (i.e., v1= u and v2= w). Then for any λ ∈ (0,1), the point
(λu +(1−λ)w, λu+(1−λ)v2, λv1 +(1−λ)w)
is neither in Sx=y nor in Sx=z. Suppose, then, that F ⇒ G : ni=1 ui = vi, but for no i ∈ {1,...,n} does F ⇒ui=vi. Then it must be the case that there are two points s1 and s2 of SF in separate subsets Sui=vi, Suj=vj, i= j, of SG. By the argument above, the points on the line segment between s1 and s2 are not in SG and thus not in SF. Then F is not geometrically convex, a contradiction. Thus, TQ is convex.

UPDATE:
Context from the same book:

If a conjunctive formula in a convex theory implies a disjunction of equalities between variables, then it actually implies a single equality. Formally, consider a quantifier-free conjunctive Σ-formula F and a disjunction n
G: conjunction_over_i_to_n ( ui = vi ),
for variables ui and vi.
Theory T is convex if for every such F and G, if n
F ⇒ disjunction_over_i_to_n (ui = vi)
then,
F ⇒ ui=vi for some i∈{1,...,n} .
If F implies G, then F actually implies one of the disjuncts of G.

Cross-posted from SO: https://stackoverflow.com/q/38814285/1494559 (as it lies in the intersection of the fields)

The key idea here is that for any conjunction of equations $F\equiv u_1=v_1\wedge\ldots\wedge u_k=v_k$, the set $S_F$ is convex in the geometric sense, i.e. for any two points $p,q\in S_F$, all points between $p$ and $q$ are also in $S_F$.

Now suppose that $F\Rightarrow G$, where $G$ is a disjunction of equations $x_1=y_1\vee\ldots\vee x_n=y_n$ (note that the variables $u_i,v_i,x_i,y_i$ are not assumed to be pairwise distinct). Without loss of generality, we may assume that $G$ is minimal in the sense that for each $i$, there is a point $p_i$ in $S_F$ which satisfies $x_i=y_i$, but not $x_j=y_j$ for any $j\neq i$. Any equation for which this is not the case can simply be removed from $G$ to obtain a smaller disjunction $G'$ which still satisfies $F\Rightarrow G'$. We will show that for such a minimal $G$, $n\le 1$.

Suppose not, i.e. $n>1$. Then the line segment $l$ between (say) $p_1$ and $p_2$ is contained in $S_F$ due to (geometric) convexity. Since $p_1$ and $p_2$ cannot be the same due to their definition, $l$ has infinitely many points. Therefore there must be some $i$ such that $l\cap S_{x_i=y_i}$ has infinitely many points, and so $l\subseteq S_{x_i=y_i}$; in particular, $p_1\in S_{x_i=y_i}$, implying $i=1$, and $p_2\in S_{x_i=y_i}$, implying $i=2$ for a contradiction.


Problems with no known quantum advantage I was wondering what the list of current natural computational problems is for which there is no known complexity advantage in using a quantum computer.

To start things off, I think computation of the edit distance is one for which the fastest known quantum algorithm seems to be the fastest known classical one. More tentatively, I would also suggest sorting as another problem for which there is no known quantum speedup (compared to the fastest known unit-cost word RAM algorithm).

Although I don't want to set a hard restriction, I am particularly interested in problems in NP and/or problems with no known efficient classical solution.

Following a suggestion of Juan Bermejo Vega  here is some further clarification.  I am interested in problems in NP for which there is currently no known big $O$ time complexity advantage at all if you use a quantum computer.

I am not focusing on cases where we can prove there can't be an advantage nor am I focusing on exponential speedups (i.e. polynomial would also be fine).  So far it seems the only two examples are the ones in my question which seems very surprising if it is really true.

This is not in NP, but comparison-based sorting. The $\Omega(n \log n)$ lower bound is information theoretic.


Dividing users with certain files into 2 equal groups I am framing a particular combinatorial question using users and files for better understanding.

Let there be a universe of files $F$ = $\{f_1, f_2,\ldots,f_n\}$ and $2k$ users $\{u_1, u_2,\ldots, u_{2k}\}$. Each user $u_i$ has a set of files denoted by $F(u_i) \subseteq F$.

Can the users be divided (whenever possible) into two equal sized group $G_1$ and $G_2$ in polynomial time in $n$, such that   $\mathcal{F}(G_1) = \bigcup_{u_i \in G_1} F(u_i)$ and similarly let
$\mathcal{F}(G_2) = \bigcup_{u_j \in G_2} F(u_j)$ satisfy the following conditions:

$$\mathcal{F}(G_1)\not\subset \mathcal{F}(G_2) \text{ and } \mathcal{F}(G_2)\not\subset \mathcal{F}(G_1), $$
where $\not \subset$ means "not a strict subset".

EDIT 1: The algorithm must to be polynomial time in $k$ and $n$.

Thanks in advance.

The problem is NP-complete. The reduction is from the Set cover problem. Let one user has all the files $F$. Then our only hope is to achieve $\mathcal{F}(G_2)= \mathcal{F}(G_1)$. So the question is, from given $2k-1$ sets, are there $k$ that cover the ground set? This easily reduces to the decision version of the Set cover problem after adding a few dummy users/files.

My old answer, which gives a polytime algorithm if we do not allow $\mathcal{F}(G_2)= \mathcal{F}(G_1)$:
Yes, you can check this in P. Your condition is equivalent to that there is an $f_i$ and $f_j$ such that $f_i\in \mathcal{F}(G_1)\setminus \mathcal{F}(G_2)$ and $f_j\in \mathcal{F}(G_2)\setminus \mathcal{F}(G_1)$. So all you have to do is for each pair, $f_i, f_j$, you check whether you can divide the users appropriately. This can be done if no user has both files and at most $k$ users have any of the files. The total running time is $O(n^2k)$ (if the info is stored appropriately) which can be easily improved.


About a random walk with constant spectral gap The existence of a graph with certain strange-looking properties will imply a counterexample to something I am playing with. I'm stuck on figuring out whether such a graph can exist and so I thought I'd post it here as question.

Specifically, for any integer $n$, is it always possible to construct an undirected graph on $n$ nodes such that:

(i) the simple random walk on it has constant spectral gap?

(ii) there exist two vertices $i,j$ such that the stationary distribution at both of them is lower bounded by a constant and the hitting time from $i$ to $j$ is at least linear in $n$?

More formally, the question is as follows. Given an undirected graph $G$, the simple random walk is the Markov chain which  transitions to a uniformly random out-neighbor at each step. Let $P$ be its probability transition matrix and $\pi$ be its stationary distribution, i.e, $\pi^T P = \pi^T$.

Do there exist positive constants $\alpha, \beta, c$ such that:

i) For each $n$, there exists an undirected graph on $n$ vertices for which the corresponding matrix $P$ satisfies $\lambda_2(P) \leq 1-\alpha$.

ii) In the same graph, there exist nodes $i,j$ such that $\pi_i \geq \beta$, $\pi_j \geq \beta$ and the hitting time from $i$ to $j$ is at least $cn$?

I suspect that this is not possible.

No.

First we have the standard bound for how close the distribution is to stationary after $t$ steps. Letting $v$ be the initial distribution, we have (I write my matrices on the left)
$||(P^tv)_i-(P^t\pi)_i||\le ||P^tv-P^t\pi||_1\le \sqrt n ||P^t(v-\pi)||_2\le \sqrt n \lambda_2^n\sqrt n=n\lambda_2^t$ which is $\le \epsilon$ for $t=\log_{1/\lambda_2}(n/\epsilon)$.

Assume (i) and (ii) hold. So starting from $i$ (or any probability distribution), there is a $\ge \beta - \epsilon$ chance that it hits $j$ on the $\log_{1/\lambda_2}(n/\epsilon)=O_{\lambda_2,\epsilon}(\log n)$th step. If it hasn't hit, there is another $\beta - \epsilon$ chance it will hit in the next so many steps. The expected hitting time is at most $\sum_{m=1}^{\infty}(1-\beta+\epsilon)^{m-1}(\beta-\epsilon) mO_{\lambda_2,\epsilon}(\log n)=O_{\lambda_2,\epsilon,\beta}(\log n)$.


Would an NP-complete public key cryptosystem imply NP=co-NP? Would the existence of an NP-complete (or co-NP-complete) public key signature cryptosystem imply that NP = co-NP?  My specialty is definitely not theoretical computer science, so this is somewhat of a mystery to me.

Any useful cryptosystem has to be in NP or co-NP.  Using digital signatures as an example, you obviously need signature verification to be in P.  Similarly, key generation needs to be in P, or good luck generating keys.

To say that a signature system is an NP-complete problem would really mean that the decision problem of determining whether the signature for an arbitrary message is less than some integer is NP-hard.  That definition would imply that deriving whether the private key is less than some integer is also NP-hard.  For both these problems, the certificate is the full answer, which shows membership in NP (and NP-complete).

But then the complement to these two problems, determining whether their full answer is not less than some number, is a simple reduction to the "less than" version.  Does this mean that the existence of such an NP-complete signature system implies NP = co-NP?

My argument above is highly informal.  For example, checking whether an alleged private key in fact matches a given public key may not be straightforward and possibly not in P.  (It is definitely in BPP, though: try signing random messages.)  Also, many public-key signature systems may have multiple valid signatures (DSA, ECDSA) or multiple matching private keys (RSA).  These things throw wrenches into the works.

Your argument is correct about the FACTORING problem, but it does not automatically generalize to all public-key cryptosystems.

Here's an excerpt from an exercise by Dominique Unruh, showing formally that if FACTORING is NP-complete, then NP = coNP.

If you are interested in research on the relationship between crypto and NP-completeness, I suggest reading Pass's paper Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on NP-hardness.


What are the simplest turing-complete systems? Lambda Calculus is very simple. Are there even simpler turing-complete systems? Which is the simplest of them all?

The Rule 110 cellular automaton (often simply Rule 110) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect it is similar to Game of Life. Rule 110 is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.

Another simple example is a Bitwise Cyclic Tag System:

The "program" is a sequence of instructions $0, 01, 11$ (i.e. $C = p_{n} p_{n-1} ... p_2 p_1; \; p_i \in (0|01|11)^+$)
; the "data" is a binary string (i.e. $w \in \{0,1\}^+$).

If $p_1$ is the "current instruction" and the data is $w = a_1 a_2 ... a_m$; you can put the program and the data side by side ($p_{n}...p_2 p_1 \leftrightarrow a_1 a_2 ...a_m$), and the "execution" of $p_1$ is:

if $a_1 = 1$ and $p_1 = x1$ then append $x$ to $w$
delete $a_1$ from $w$
rotate $C$ ($p_1$ is moved to the left of $C$ and $p_2$ becomes the current instruction)

The universality can be proved by simulating the more general cyclic-tag system.


Quantum analogues of SPACE complexity classes We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in complexity theory there was much success with these classes such as the space-hierarchy theorem and the creating on important classes like $\textbf{L}$ and $\textbf{PSPACE}$. Is there analogous definitions for quantum computation? Or is there some obvious reason why the quantum analogous would not be interesting?

It seems like it would be important to have a class like $\textbf{QL}$ --- a quantum version of $\textbf{L}$: require a logarithmic number of qubits (or maybe a quantum TM uses logarithmic space).

You might want to check  Space-Bounded Quantum Complexity, by John Watrous.

There you have the result that for any $s=\Omega(\log n)$, a Quantum Turing Machine running in space $s$ can be simulated by a probabilistic Turing Machine with unbounded error running in space $O(s)$. You also have that any Quantum Turing Machine running in space $s$ can be simulated in $NC^2(2^s) \subseteq DSPACE(s^2) \cap DTIME(2^{O(s)})$


Is there a concept of "Lego complete"? If not, does it make sense to develop one? We know the concept of Turing Completeness. These days when I play lego with my kids. I realised that Lego is kinda like programming language: we can build a lot of things with a fairly small set of Lego shapes.
This makes me wonder, is there a math/computing theory similar to Turing Completeness for Lego: given a set of lego shapes, can we prove that, these lego shapes could generate all possible objects we can think of.
Obviously this idea sounds a bit silly. If this question is not suitable for this site, please help to point me to the right forum. Thanks!

A piece of Lego can be seen as a Polyomino: a plane geometric figure formed by joining one or more equal squares edge to edge.

In Tiling the Plane with a Fixed Number of Polyominoes [2009], Nicolas Ollinger proved that 5 polyominoes are enough to simulate any set of Wang tiles (the shapes of the polyominoes are quite complex and clearly depends on the set of Wang tiles to be simulated). And it is undecidable if a set of Wang tiles can tile the plane (see the link provided by domotorp in his comment).
So it is undecidable given a set of 5 "Lego pieces" (unlimited quantity of each) you can place them (theoretically) on an infinite Lego base and completely cover it (cover the plane).
In other words given a Turing machine, there is a set of 5 lego pieces such that you can cover the whole plane with them if and only if the Turing machine doesn't halt.
But even if you have only 3x1 Lego pieces, and a target object to recreate with them, it can be very hard to find the solution; indeed it is an NP-complete problem as proved in Danièle Beauquier, Maurice Nivat, Eric Rémila, Mike Robson; Tiling Figures of the Plane with Two Bars (1995).


Lower Bounds on Running time of Graph Algorithms Are there any non-trivial lower bounds on the running time of graph algorithms in RAM/PRAM/
models of computation ? I am not looking for the NP-Hardness results here.

Following is a result that I could find [see ref L92]:

3-Coloring of an n-cycle requires $\Omega(\log^*{n})$ time.

I was curious to know whether there has been any progress/work in the direction of getting
lower bounds for problems like: Shortest Paths(with/without negative weights), Mincut,
s-t Maximum flows, Maximum (cardinality/weighted) matching. Any references related to
this are very much appreciated and helpful.

Reference

[ L92 ] N. Linial, Locality in distributed graph algorithms, SIAM Journal on Com-
puting, 1992, 21(1), pp. 193-201

EDIT: As suggested by Robin Kothari in the comments, I am making the question more directed.

In the PRAM model without bit operations, fairly strong lower bounds are known. For example, in this model, one cannot solve min-cut in $O(\sqrt{n})$ time on $2^{O(\sqrt{n})}$ processors [1].

Despite being a restricted model, it is strong enough to compute the determinant efficiently, and includes most standard algorithms for poly-time combinatorial optimization problems. See here, here, or the original paper for more details.

[1] Mulmuley, K. Lower Bounds in a Parallel Model without Bit Operations. SIAM J. Comput., 28(4), 1460–1509, 1999. (from author's webpage without paywall)


What information can a program give about the Kolmogorov Complexity of its accepting Language Suppose we have a program(algorithm) that solves some decision problem $(\Sigma,L)$.

Given the program, can we always say something about the Kolmogorov complexity of the words in $L$ ?

Let's assume we use TMs to describe the Kolmogorov Complexity of words over $\{0,1\}$. Since we can encode any string over a finite alphabet as binary string we don't lose generality.

Using Gödel Numbering we can encode every TM $M$ as a string over $\{0,1\}$. If there is an input $x$ such that $M$ outputs $w$ on input $x$, in symbols $<M,x>=w$, then the length of this description of $w$ is the length of the concatenated binary string of $M$ and $x$, in symbols $|M \circ x|$.

Now, due to your request we have a TM $M$ that decides our language $L$. That implies that $M$ halts on every input(a semi-decision algorithm would be sufficient as well but the following algorithm would be slightly more cumbersome). With $M$ we can construct a TM $M'$ which enumerates $L$. That means $M'$ on some input $n$, which we will interpret as a natural number but 0, does the following:

counter := 0
for all x in {0,1}^*
    if x in L then counter++
    if counter = n then break
return x

To decide $x$ in $L$ we use $M$. Additionally, I'd consider it useful that the sequence of all binary strings should be traversed in ascending order w.r.t length(for assessing the quality of our upper boundary later on).

Now, let for all words $w \in L$ be $f(w)$ the natural number such that $<M',f(w)> = w$. Then we can state an upper bound for the KC of any word $w$ in $L$ as

$K(w) \leq |M' \circ bin(f(w))|$

with $bin(x)$ being the binary representation we also use to pass $f(w)$ as input to $M'$. Extra: the quality of our upper bound for the larger words in $L$ can be estimated by comparing the growth rate of $|w|$ to $log_2(f(w))$.


Confusing (to me) statement from "Type Classes in Haskell" I'm reading up on type classes, and started looking at the paper Type Classes in Haskell.

In Section 2.2 - Superclasses, the authors use the following example:

class (Eq a) => Ord a where
   (<)  :: a -> a -> Bool
   (<=) :: a -> a -> Bool

Then, they proceed to state that "This declares that type a belongs to class Ord if there are operations (<) and (<=) of the appropriate type and if a belongs to class Eq. Thus, if (<) is defined on some type, then (==) must be defined on that type as well."

The second sentence does not make any sense to me; why would a type that defines (<) have to define (==) if it is not declared to be an instance of either Ord or Eq?

Simple answer: When the above class definition is in scope, you simply cannot bind (<) or (<=) except as part of an instance declaration for Ord.


Complexity of type inference in the simply typed lambda calculus A similar question was answered here:
Is simply typed lambda calculus equivalent to primitive recursive functions
What I conclude from the answers is that the complexity is that of the extended polynomials, but this refers to what can be computed in the STLC, not of type checking expressions in the STLC.
This link provides an algorithm for type-checking. It is claimed that
type checking is linear time in an answer to this question: Complexity of type-checking in relation to complexity of normalization
Also, a survey of algorithms that do type inference for STLC, using unification occurs here, but no complexity result is given.

Type inference for simply typed lambda calculus is complete for polynomial time, as elegantly explained in section 1 of Harry Mairson's Linear lambda calculus and PTIME-completeness.
To be a bit more precise, here "type inference" is taken to mean the problem of computing the principal simple type of an untyped lambda term. This is strictly speaking a functional problem ("Given a term $t$, compute its principal type"), but Mairson shows that the corresponding decision problem ("Given a term $t$ and type $A$, is $A$ the principal type of $t$?") is PTIME-hard, by reduction from the circuit value problem.  This implies PTIME-completeness, since simple type inference can be performed efficiently using first-order unification.  Moreover, Mairson's encoding of the circuit value problem has the property that the terms representing boolean circuits are affine (variables used at most once), and in Section 2 of the paper he gives another encoding that produces linear terms (variables used exactly once).  So his proof implies PTIME-completeness of simple type inference even when restricted to affine/linear lambda terms.


On connecting combinatorial rectangles In communication complexity one important object is the combinatorial retangle. Given a $0-1$ square matrix $M$, do their exist permutations $\sigma,\pi$ such that $\sigma M\pi$ consists of only geometric rectangles? That is all the combinatorial rectangles are geometrically connected?

It's not possible.  Consider the following 3x3 boolean matrix:

1 1 0

1 0 1

0 1 1

For every pair of rows {r,r'} , there exists a column c such that {r,r'} X {c} is a combinatorial rectangle.  For any particular pair, we can permute the rows such that {r,r'} are adjacent.  However, since we have a combinatorial rectangle for all pairs of rows, it's not possible to permute the rows so that all such rectangles are geometrically connected simultaneously.


Is it enough for linear program constraints to be satisfied in expectation? In the paper Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching, while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the dual is feasible in expectation (see Lemma 3 on page 5). My question is:

  Is it enough for linear program constraints to be satisfied in expectation?

It is one thing to show that the expected value of the objective function is something. But if feasibility constraints are satisfied in expectation, there is no guarantee that it will be satisfied on a given run. Moreover, there are many such constraints. So what is the guarantee that ALL of them will be satisfied on a given run?

I think the difficulty is that this wording slightly misleading; as they state more clearly in the Introduction (1.2), "the expected values of the dual variables constitute a feasible dual solution."

For every fixed setting of the dual variables $X$, we obtain some primal solution of value $f(X)$ and a dual solution of value $\frac{e}{e-1}f(X)$. (The dual is infeasible in some of these cases, but that's fine.)

So the expected value of the primal over all runs of the algorithm is $E[f(X)]$. But $E[X]$ is a dual-feasible solution, so there exists a dual solution of value $\frac{e}{e-1}f(E[X])$. The key trick is that $f(X)$ is linear in the dual variables $X$: In fact, here the dual variables are $\alpha_i$ and $\beta_j$, and each matching of vertex $i$ to $j$ adds a total of $\left(\frac{e-1}{e}\right)(\alpha_i + \beta_j)$ to the primal objective. So $E[f(X)] = f(E[X])$ and the conclusion follows.

(As a side note, I feel that, as this point is one of the main focuses of their paper (according to the abstract), it would have been nicer if they had explained this point! It doesn't seem at all obvious to me, and I would like to find out when it's true more generally.)


Longest path from every vertex in a tournament I have a tournament (directed complete graph) with $V$ vertices. For every vertex I want to find the longest path starting in it (so the longest path starting in the first vertex, longest path starting in the second vertex etc.). In general, longest path problem is NP-complete, but this is a very special case so I guess there exist a polynomial (in terms of $V$) time algorithm.

This is really just an elaboration of Sasho Nikolov's comment, but the subsequent comment makes clear that it needs elaboration and this doesn't fit within a comment itself.

If you topologically order the strongly connected components of your tournament, then the longest path from any vertex $v$ contains all vertices of the component containing $v$ and all vertices of later components.

To see this, we need the known facts that

Each strongly connected component contains a Hamiltonian cycle.
Condensing the strongly connected components to a single vertex per component produces a directed acyclic graph, which must itself be a tournament.
Any acyclic tournament is totally ordered by the orientations of its edges, so the topological ordering of components is uniquely defined.

So, start from $v$, and follow the Hamiltonian cycle within its own component. Then, when the cycle would return to $v$, instead follow any edge to the next component in the total ordering of the components (there's an edge to that component because there's an edge to every vertex and because the edges connecting the current component to the next component are all oriented in the direction you want to go). Then continue the same way in each successive component.


Is there a formulation of Rice's Theorem that does not involve admissible (or Gödel) numberings? It is an easy task to devise an encoding for a computing formalism (such as  Turing Machines) that has a function with fixed encoding. That is, the encoding is a numbering $\psi : \mathbb{N} \rightarrow \textbf{P}^{(1)}$ where $\textbf{P}^{(1)}$ is the set of partial unary computable $\mathbb{N} \rightarrow \mathbb{N}$ functions. By a function with fixed encoding we mean a function $f$ that has exactly one $c$ such that $\psi (c) = f$. It is also simple to have such a numbering be realizable, that is, its codes can be decoded and executed by a universal computer, and furthermore it is possible to directly provide a code $u$ for a universal computer.

It seems we have all the ingredients to falsify Rice's Theorem; since there is only one code for $f$, deciding if a function belongs to $\{f\}$ is a simple matter of checking if the function's code is $c$. At this point we must stop and check the theorem's formal statement, in somewhere such as Wikipedia, where we find out that our numbering has to admissible. The proposed numbering is obviously not so; there is no computable function that could map exactly all standard codes for $f$ into exactly $c$.

But that does not mean $\psi$ is an undesirable numbering. On the contrary, i'd argue that having a numbering where a function is restricted to a special code could be a more pleasant evironment to program in, and while i've only spoken of fixing an encoding for a single function, it should be generalizable to finite amounts of functions, and there might even be infinite classes as well (but that's a question for another TCS.se post). It's also clear that most properties over $\textbf{P}^{(1)}$ are still undecidable even under $\psi$, which suggests a more general restatement of Rice's Theorem.

My question is: Are there generalizations of Rice's Theorem that account for realizable numberings, not just admissible ones?

tl;dr:

(1) While (a) there is a kind of Rice's Theorem for your example construction, (b) it seems to me unlikely that one holds for realizable numberings in general.

(2) Your particular construction of a code $\psi$ with a fixed encoding for some $f$ has lots of (provable) deficiences, and I think other numberings can only get worse from there, so I don't think it's a very good programming environment, though I suppose that's a matter of what you're willing to trade off in order to have that fixed encoding.

Elaboration:

(1a) Rice-type theorem for your example construction. Let $\psi$ be the encoding from the comments, namely $\psi_0$ is the all-zeros function, and $\psi_n = \varphi_b + \delta_a$ where $n = (a,b)$ under some fixed computable bijection $\mathbb{N} - \{0\} \to \mathbb{N}^2$, $\varphi$ is a standard (acceptable) numbering, and $\delta_a$ is the Kronecker delta function, which is $\delta_a(a) = 1$ and $\delta_a(a') = 0$ for all $a' \neq a$. Let $P^{(1)}_1$ denote the subset of $P^{(1)}$ consisting of functions that have at least one nonzero output value (note that these are precisely the functions $\psi_{(a,b)}$ such that $\varphi_b(a)$ halts). Then for any subset $\emptyset \neq S \subsetneq P^{(1)}_1$, the function
$$s(a,b)=1 \text{ iff } \psi_{(a,b)} \in S$$
is not computable. We mimic the proof of Rice's Theorem; suppose $s$ were computable. Let $(a_0,b_0)$ be such that $\psi_{(a_0,b_0)} \notin S$ and let $(a_1,b_1)$ be such that $\psi_{(a_1,b_1)} \in S$. Let $D(p)$ be the total computable function which proceeds as follows:

$D(0)=0$
$D(p)(n)$ = if $s(p)=1$ then $\psi_{(a_0,b_0)}(n)$, otherwise $\psi_{(a_1,b_1)}(n)$

Now, if $s$ is computable, then so is $D$, and furthermore, $D$ is in $P^{(2)}_1$, so there is some index $(a_d,b_d)$ for $D$. Then consider $D((a_d,b_d))$: if $s((a_d,b_d))=1$ then $D((a_d,b_d)) = \psi_{(a_0,b_0)} \notin S$, and if $s((a_d,b_d))=0$ then $D((a_d,b_d)) = \psi_{(a_1,b_1)} \in S$, so either way $s$ gets it wrong.

(1b) The above relied on the fact that although we don't have a total computable compiler from $\varphi$ to $\psi$, we at least had a partial one which covered a nontrivial set of functions. I wouldn't be surprised if you can cook up a realizable numbering where there's essentially no such partial compiler.

(2) Since a $\psi$-Rice's Theorem fails for $\{f\}$, $\psi$ also must not satisfy the S-m-n Theorem (currying). In particular, there is some $n$ such that $\psi_n(x,y) = \varphi_x(y)$ (i.e., a universal TM). But then there is no computable program transformation $t$ such that $\psi_{t(m,x)}(y) = \psi_m(x,y)$ for all $m,x,y$, for if there were, $t(n,x)$ would enable you to decide whether $\varphi_x = f$, which is undecidable by the usual Rice's Theorem. Currying is a pretty basic feature for a programming environment to lack. I think one can prove a similar thing not just for currying, but for infinitely many program transformations, probably whenever the transformation is not finitely different from the identity map and has $f$ in its image.


Can I bound the cardinality of a set if testing for membership in it is known to be NP-complete? I would like to have a bound on the cardinality of the set of unit disk graphs with $N$ vertices. It is known that checking whether a graph is a member of this set is NP-hard. Does this lead to any lower bound on the cardinality, assuming P $\neq$ NP?

For example, suppose there is an ordering on all graphs with $N$ vertices. Would NP-hardness then imply the cardinality exceeds $2^N$, in that otherwise you could test for membership in polynomial time by doing a binary search through the set? I think this would assume that you have somehow stored the set in memory... Is this allowed?

Defintion: A graph is a unit disk graph if each vertex can be associated with a unit disk in the plane, such that vertices are connected whenever their disks intersect.

Here is a reference on NP-hardness of membership testing for unit disk graphs:
http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf

Mahaney’s Theorem states that sparse NP-complete sets exist iff P=NP. Therefore, assuming $P \neq NP $ implies a super-polynomial lower bound on the number of instances of size $n$ in $NP$-complete sets, for infinitely many $n$. That is, if $P \neq NP$, then any $NP$-complete set must have some $\epsilon \gt 0$ such that for infinitely-many integers $n\ge 0$, the set contains
at least $2^{n^{\epsilon}}$ strings of  length $n$.

H. Buhrman and J. M. Hitchcock proved the lower bound ($2^{n^{\epsilon}}$) is tight, unless the polynomial hierarchy collapses.

[1] H. Buhrman and J. M. Hitchcock, NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly, In IEEE
Conference on Computational Complexity, pages 1–7, 2008

[2] Eric Allender, A Status Report on the P Versus NP Question, Advances in Computers, Volume 77, 2009, Pages 117-147


Breaking encrypted file store with a file? Let's say you have an encrypted file store of some kind such as an encrypted hard drive, ZIP file, etc.  You don't have the private key or password to this file store, so a brute-force attack is not a good option.

But what you DO have is a copy of a file -- a file that you know for certain is on that file store.

Does this help reduce the complexity of an attack? In other words, would I be able to crack the encryption in less time by knowing part of the contents of the encrypted file store?

(Forgive me if this is obvious, encryption is not my specialty.)

This is called the known-plaintext attack. Any cipher algorithm which is prone to this type of attack is considered very weak. Therefore, AFAIK, no present-day cipher (e.g. AES) has this weakness. Even DES needs 243 known plaintexts to be broken under linear cryptanalysis. (see this topic  on Wikipedia).

On the other hand, all hope is not lost. Weak ciphers or bad implementation of strong ciphers are still commonplace. One noticeable case is with the (old) implementations of ZIP. More info is available here:

http://www.elcomsoft.com/help/archpr/index.html?known_plaintext_attack_(zip).html


NP-hardness on Cayley graphs What is known about complexity of NP-hard problems on Cayley graphs?

Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input length is the size of the graph. Can we solve NP-complete problems on such graphs (maximum clique/max-cut) in polynomial time?

What about some special cases of groups? For example, $\mathbb{Z}_n$ (a.k.a. circulant graphs) or $\mathbb{Z}_2^{\log(n)}$. That is, the input to the problem is the set of generators (and $1^n$ to represent the size of the graph).

Because the input size (a description of the group and its generators) can be so much smaller than the graph itself, even standard polynomial-time graph optimization problems can become hard on Cayley graphs. For instance, shortest paths on circulant graphs (a special case of Cayley graphs) are NP-complete; see "On Routing in Circulant Graphs", Cai et al, COCOON 1999, doi:10.1007/3-540-48686-0_36

Of course that doesn't apply to the exact statement of the problem you give (where the group is given as a multiplication table, itself an object of size comparable to the Cayley graph) but it does indicate a need for some care.


$\mathbb{N}$ in intensional MLTT with judgmentally commutative $+$ and $\times$ Is there a way to implement natural numbers in intensional Martin-Löf type theory so that addition and multiplication is judgmentally commutative?

This is impossible.

Suppose that we have such a type $T$, with an implementation of addition $\mathit{add} : T \to T \to T$, which is judgementally commutative.
Because MLTT is strongly normalising, we know that we can put $\mathit{add}$ in $\beta$-normal, $\eta$-long form.
Now suppose that we have two variables $x, y$ of type $T$.
Now consider the terms $\mathit{add}\,x\,y$ and $\mathit{add}\,y\,x$.
Substituting $x$ and $y$ for the formal parameters of $\mathit{add}$ will not create any new $\beta$-reducible expressions, because $x$ and $y$ are neutral terms.
Now, $\eta$-expand the occurences of $x$ and $y$ as demanded by the definition of $T$.
Now, the resulting terms will be identical except that we've permuted the occurences of $x$ and $y$.
Recall that judgemental equality for $\beta$-normal, $\eta$-long terms is just $\alpha$-equivalence.
Since we assumed $\mathit{add}\,x\,y$ and $\mathit{add}\,y\,x$ were assumed to be judgementally equal, this means that the normal forms for these two terms are $\alpha$-equivalent.
Since anywhere that $x$ occurs in the normal form for $\mathit{add}\,x\,y$, a $y$ occurs in the corresponding position of the normal form for $\mathit{add}\,y\,x$, the only way that these two terms can be $\alpha$-equivalent is if neither $x$ nor $y$ occurs in the term.
This means that $\mathit{add}\,x\,y$ and $\mathit{add}\,y\,x$ do not use their arguments!
As a result, we can conclude that $\mathit{add}\,1\,1$ and $\mathit{add}\,0\,0$ are also judgementally equal.
Therefore $T$ cannot be the natural numbers, since $2$ and $0$ must not be judgementally equal.


Complexity of finding Exact Size Cut-Sets in Bipartite Graphs I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part of the input). Note that this is different from the problems of MINCUT and MAXCUT which simply ask to find the minimum and maximum sized cutsets.

For general graphs, the MINCUT problem can be solved in polynomial time while the MAXCUT problem is NP-Hard. It follows that deciding if a cutset of a particular size exists in a general graph is also NP-Hard since we could use it to find the maximum sized cutset.

For bipartite graphs however, the MAXCUT problem is trivial -- all the edges in the graph constitute the MAXCUT. Moreover, if it helps, I think I can show that for bipartite graphs, the edge - complement of a cutset is also a cutset. That is if $E_c\subseteq E$ is a cutset of a bipartite graph $G=(U\cup V,E)$ then $E−E_c$ is also a cutset of $G$.

However, I have not been able to determine if deciding if a cutset of some size $k$ exists is in P or is NP-Complete or something else. If it is Np-Complete, is there a family of graphs for which it is in P? Any pointers will be helpful.

The problem of bipartite exact cuts is NP-Complete, as shown here by a reduction from exact cuts in general graphs.


What is special about $2^{32}/\phi$ in cryptography? In the Tiny Encryption Algorithm:

  Different multiples of a magic constant are used to prevent simple attacks based on the symmetry of the rounds. The magic constant, 2654435769 or 9E3779B916 is chosen to be $2^{32}/ \phi$, where ϕ is the golden ratio.

Which properties does $2^{32}/ \phi$ have that makes it useful in this context?

One reason that $\varphi$ makes a particularly useful 'magic number' in this context is that the multiples $n\varphi$ are guaranteed to be 'maximally far' from integers (this has to do with the lack of large terms in the continued fraction for $\varphi$), and thus the sequence $\{n\varphi\}$ (or more accurately, its initial segments) is more uniformly distributed mod 1 than the sequence $\{n\alpha\}$ for any other irrational $\alpha$.

To give an example: suppose we choose a magic constant $C_\pi = \lfloor {2^{32}/\pi}\rfloor = 1367130551$.  Then $(355C_\pi)\mod {2^{32}} = 41157$, an unexpectedly small result for such a small multiple of our magic constant.  By contrast, if we use the magic constant $C_\varphi = \lfloor {2^{32}/\varphi}\rfloor = 2654435769$, then the smallest $n$ for which $|(nC_\varphi)\mod {2^{32}}| \leq 2^{16}$ (abusing notation a bit) is $n=28657$.  In practice, this can conceivably lead to things like unexpectedly large correlations between the values $X_n$ and $X_{n+k}$ of a linear congruential random number generator for some smallish $k$; for the most part, though, it's folkloreish black magic, based more on the intuition that 'small multiples of this number being small mod $2^{32}$ will be bad' than on any specific theoretical results.


Set cover with budget on sets I am wondering if this is a studied variant of the Set Cover problem.

We are given a universe $X$, a collection of sets $S = \{S_1, ..., S_m\}$ and integers $c_i$.  We want to cover all elements in $X$ with sets $S'_i \subseteq S_i$ such that $|S'_i| \leq c_i$.  In other words we want to cover the elements with as few sets as possible but we are only allowed to use $c_i$ elements of each set.

The most similar variant I found is described in "Maximum Coverage Problem with Group Budget Constraints and Applications"

Thank you

Yes, this variant, and in fact a further generalization has been considered in the literature. See the paper below for the problem they call capacitated facility location.

J. Bar-Ilan, G. Kortsarz and D. Peleg,
Generalized submodular cover problems and applications,
Theoretical Computer Science, 250:179-200, 2001.


Known and described subclasses of Context-Free Grammars class I'm looking for various researches which consider specific subclasses of Context-Free Grammar class, i.e. some specific described cases, which differ from well-known:

deterministic/non-deterministic
ambiguous/unambiguous
regular/non-regular

As an example of such "non-standard" subclasses are Visibly pushdown grammar described here. Any additional examples will be much appreciated.

More specifically, I'm wondering, are any described subclasses which can help distinguish this two very similar cases?

$G_1$:

$S\rightarrow aD$, $S\rightarrow cD$

$D\rightarrow abc$, $D\rightarrow abDc$

$G_2$:

$S\rightarrow aD$, $S\rightarrow cD$

$D\rightarrow abc$, $D\rightarrow abDc$, $D\rightarrow aDb$, $D\rightarrow aDc$

It is clear that both of them are unambiguous non-determ. CFG, and $\mathcal{L}(G_1)\subset\mathcal{L}(G_2)$. But these are common properties, I'm looking for specific differences.

Density might be interesting concept for you. The density function is defined as
$$\delta_L(n) := |L\cap \Sigma^n|,$$

where $\Sigma^n$ denotes the set of all strings of length $n$ over $\Sigma$.

Your first language seems to have density values of only 0 and 1 while the second goes up to 3. So the first is 1-slender, the second is not following the terminology of  Lucian Ilie's work.


Confusion with the proof of constraints for a particular adiabatic quantum evolution [This might be related to one of my previous unanswered questions.]

This proof belongs to the paper, How to Make the Quantum Adiabatic Algorithm Fail by Edward Farhi, Jeffrey Goldstone, Sam Gutmann and Daniel Nagaj. It is the theorem 1 on page 3. The theorem is as follows.

  Let $H_P$ be diagonal in the $z$ basis with a ground state subspace of
  dimension $k$. Let

  $$ H(t) = \left(1 - \frac{t}{T} \right) E \left( \mathbb{I} -
> |s\rangle \langle s|  \right) + \left( \frac{t}{T} \right) H_P $$ .

  Let $P$ be the projector onto the ground state subspace of $H_P$ and
  let $b > 0$ be the success probability, that is, $b = \langle \Psi (T)
> | P | \Psi (T) \rangle $. Then

  $$ T \ge \frac{b}{E} \sqrt{\frac{N}{k}} - \frac{2 \sqrt{b}}{E} $$.

As the proof proceeds I can't really follow it completely.

For example, there are three equations at the bottom of page 3 which evaluates $S(t)s$. As per the paper $S(t)$ is the sum on $x$. But the expression looks to involve norms. I understand that there are more than one kind of norms. What kind of norm are we talking about here? Why? What is the physical significance of this quantity in this context?

The norms are the usual norms of a ket vector, i.e. $|||a\rangle||^2 = \langle a|a\rangle$.

What did we do on the bottom of page 3? It is really running the argument from the An Analog Analogue paper backwards.

Imagine we start from the state $|g_x\rangle$ (a particular ground state of the final Hamiltonian $H_{P}$, related to $|x\rangle$), and evolve backwards with an inverse algorithm. Similarly to AAA, we are looking at whether evolving backwards with no purpose (without knowledge of $x$) makes the evolution any different from evolving with a Hamiltonian that involves $x$. We show that for a successful algorithm, it is necessary that the quantity $S(0)$ must be large enough. However, running back in time from $T$ to $0$, this $S(t)$ doesn't change much, which allows us to show that $T$ must be large.


Foundational textbook(s) for Complexity and Computability on Real Numbers It would be extremely helpful if someone can suggest foundational textbooks on Recursive Analysis (Computability over Reals) which explains connections between Computability and the Topological properties of continuous sets. I could not find any, except "Recursive Analysis" by R.L. Goodstein but I dont have any feedback on that book. I would also like to ask for suggestions regarding a book on Complexity over Real Numbers which again deals with the connection between the complexity and the topology of a set. The only book I found on the net was "Complexity and Real Computation" by Lenore Blum et al but I am not sure if that is the book which I am looking for. Thanks in advance.

There are some good books -
 1. Computable Analysis - Pour-El and Richards (an older reference)
 2. Computable Analysis - Weihrauch

There's also the Blum-Shub-Smale Model, which is the model explored in "Complexity and Real Computation".

The complexity theory of computability of reals is explored in
 1. Computational Complexity of real functions  - Ker-I Ko

A regular conference which explores this area is "Computability and Complexity in Analysis", held annually.


How does the CHC Algorithm deal with child populations with lower fitness? I am basing my question on the pseudocode for the CHC Adaptive Search Algorithm by Eshelman given in this answer by deong:

delta = k/4               # k = chromosome length
while not done
    create new child population
    for i = 1 to n/2     # n = population size
        select p1, p2 from population without replacement
        if hamming_distance(p1, p2) > delta
            c1, c2 = HUX crossover(p1, p2)
            insert c1, c2 into child pop
        end if
    end for
    if child pop is empty
        delta = delta - 1
    else
        take best n individuals from union of parent and child populations as next population
    end if
    if delta < 0
        keep one copy of best individual in population
        generate n-1 new population members by flipping 35% of the bits of the best individual
        delta = k/4
    end if

How does this algorithm deal with situations where the child population has lower fitness than the parent population?

Consider a population of two parent with a large enough hamming distance to produce children. Now if both children have a lower fitness than their parents, doesn't the survivor selection ("take best n") select the same parents again, resulting in an infinite loop?

CHC never has a next generation's population with lower fitness than the current one due to the use of a truncation selection step. It combines the parents and offspring, sorts by fitness, and takes the best $n$ individuals. So if including any child would lower the fitness of the population, it would just select the parents as the next generation and the average fitness would stay the same.

In principle, you could indefinitely select the same two parents over and over, continually producing inferior offspring. But generally you're running CHC with a population size of 50 or more, so you don't expect to continually pair the same two parents. Also, it's technically an infinite loop anyway, as most GAs are. In practice you define some stopping condition based on evaluation count or wall clock time or whatever.


n-approximable functions I came across the following definition in a paper:

We can extend the notion of an $n$-c.e. [n-computably enumerable] set to a notion that measures the number of fluctuations of a function as folows: For every $n \geq 1$, call $f : N \rightarrow R$ n-approximable if there is a rational-valued computable approximation $\varphi$ such that $\lim_{k\rightarrow \infty} \varphi(x, k) = f(x)$ and such that for every $x$, the number of $k$’s such that $\varphi(x,k + 1) − \varphi(x,k) < 0$ is bounded by $n − 1$. That is, $n − 1$ is a bound on the number of fluctuations of the approximation.

Note that the $1$-approximable functions are precisely the lower semicomputable ($\Sigma_1^0$) ones (zero fluctuations). Also note that a set $A \subseteq \mathbb N$ is $n$-c.e. if and only if the characteristic function of A is n-approximable.

I have two questions.

Is this a commonly used principle? Google didn't give me any relevant results.
If I have an $n$-c.e. function $\varphi(x)$, with $\varphi(x,k)$ approximating it. Couldn't I just build a Turing machine $\varphi'(x, k')$ that dovetails the computation of $\varphi(x, k)$ until it sees two consecutive halting machines with $\varphi(x, k+1) < \varphi(x, k)$, stops the dovetailing, and outputs $\varphi(x, k+1+k')$ (ie. it computes $\varphi(\cdot, \cdot)$ but starting from k+1). Then, if $\varphi(x)$ is $n-c.e.$ (and not $n+1$-c.e.), it is also $n-1$-c.e., and by induction it is just approximable.

So the definition doesn't seem to make sense. Am I missing something?

This is a special case of what is called an $f$-c.e. set. A set $A$ is $f$-c.e. iff there is computable function $g$ such that

$\chi_A(x) = \lim_i g(x,i)$, and
$\forall x \ |\{s \mid g(x,i) \neq g(x,i+1) \}| \leq f(x)$.

If we consider $f(x)=n$ then we get the definition of $n$-c.e sets.

They don't need to be c.e. because c.e. is not closed under complement. Take two c.e. sets and take their difference. It is a $2$-c.e. set but it does not need to be a c.e. set.

Barry Cooper and colleges have been interested in these sets and the notion of computability in limit. You may want to check his "Definability in the Real Universe" article from "Computability In Context: Computation and Logic in the Real World".


Is Square DH hard in Bilinear Groups? Let $G$ be a group, $g ∈_R G, x ∈_R Z_q$, and  $e: G \times G \rightarrow G_T$ be a bilinear paring.

Then, given $g, g^x$, is it still hard to compute $g^{x^2}$?

1. In other words is Square Diffie-Hellman hard in Bilinear Groups?

I am trying to look for references that have used this problem or a reduction which proves this is hard.

[I am aware of a variant of this called the Flexible Square Diffie-Hellman  [Laguillaumie et al], which asks to compute $(h,h^x,h^{x^2})$ given $g^x$.]

2. What about the decisional version of the same problem?

This assumption has been used in cryptographic constructions.  Both the computational and decisions are generally believed hard by the provable security community, but I doubt a reduction to, e.g., DH will be found.  See http://homepage.ruhr-uni-bochum.de/Eike.Kiltz/papers/dh_full.pdf for discussion and references.


Confusion about reduction counting vertex covers to counting cycle covers This confuses me.

One easy case of counting is when the
decision problem is in $P$ and there are no solutions.

A lecture show that the problem of counting the number of perfect matchings in a bipartite graph (equivalently, counting the number of cycle covers in a directed graph) is $\#P$ -complete.

They give reduction from counting vertex covers of size $k$
to counting cycle covers in a digraph using gadgets.

Theorem 27.1 The number of good cycle covers in $H$ is $(k!)^2$ times the number of vertex covers of $G$ of size $k$.

Using gadget they leave only the "good" cycles.

My understanding of the lecture is that $G$ doesn't have
vertex cover of size $k$ iff the transformed digraph $G'$
doesn't have cycle cover. Checking if $G'$ has cycle cover
can be done in polynomial
time, implying $P=NP$ since we can transform the decision
problem to finding solution.

  What am I misunderstanding?

The permanent of the adjacency matrix of digraph
counts cycle covers and is $\#P$-complete.

The decision problem "Is the permanent of (0,1) matrix zero"
is in P since finding cycle cover is in $P$.

$P \ne NP$ implies there is no reduction of counting
$NP$-complete problems to counting $(0,1)$-permanent which maps $0 \mapsto 0$.

Edit Related MO question

Added

Markus Bläser points out that bad cycle are still "there",
but the sum of their weights vanishes.

Appears to me the weight of bad cycle in
a widget is zero.

From page 148 (11 of the pdf):

  The full adjacency matrix B with submatrices A corresponding to these
  four-node widgets counts 1 for each good cycle cover in H and 0 for each bad
  cycle cover

Another question:

  Wouldn't maximum weight cycle cover contain only the good cycles,
  corresponding to a $k$ vertex cover in the original graph?

In CC every vertex must be in exactly one cycle.

Looks like the misunderstanding is this:

In the final reduction to (0,1)-permanent they are using modular
arithmetic, which breaks my argument.

Let $A$ be the original matrix and $B$ the (0,1) matrix.

Working modulo $n$, it might happen $perm(A)=0$ and perm $perm(B)=mn$.

Though equality holds modulo $n$, $B$ have cycle covers.

Haven't found the flaw in the question about maximum weighted
cycle cover, which doesn't appear to be affected by the above.


How many ephemeral stacks are required to simulate a queue in worst-case $O(1)$ time? In "Real Time Queue Operations in Pure LISP" (ML implementation), Hood and Melville show an $O(1)$ worst-case simulation of a queue using 6 stacks and global rebuilding. Can a real-time queue be simulated with fewer stacks?

In "Simple and Efficient Purely Functional Queues and Deques", Okasaki shows an implementation using one stack and two lazy stacks.

Both Okasaki's and Hood & Melville's queues require purely functional stacks as building blocks, and both produce purely functional queues. If push and pop are destructive, can global rebuilding be used to simulate an ephemeral queue with 6 ephemeral stacks? Fewer?

Not sure I fully understand your question, but it seems related to Problem 1.3.49 from Sedgewicks Algorithm book.


Finding short and fat paths Motivation: In standard augmenting path maxflow algorithms, the inner loop requires finding paths from source to sink in a directed, weighted graph.  Theoretically, it is well-known that in order for the algorithm to even terminate when there are irrational edge capacities, we need to put restrictions on the paths that we find.  The Edmonds-Karp algorithm, for example, tells us to find shortest paths.

Empirically, it has been observed that we might also want to find fat (is there a better term for this?) paths.  For example, when using capacity scaling, we find shortest paths that can bear at least $\epsilon$ amount of flow.  There is no restriction on how long the path can be.  When we can no longer find any paths, we decrease $\epsilon$ and repeat.

I am interested in optimizing the choice of augmenting paths for a very specific application of max-flow, and I want to explore this tradeoff between short and fat paths.  (Note: it is not necessary for me to always solve the problem.  I am most interested in finding the largest lower bound on flow in the shortest amount of wall time.)

  Question: Is there a standard way to
  interpolate between the shortest path
  approach and the capacity-scaling
  approach?  That is, is there an
  algorithm for finding paths that are
  both short and fat, where ideally some
  parameter would control how much
  length in the path we are willing to
  trade off for fatness?  At the extremes, I'd like to be able to recover
  shortest paths on one end and capacity scaling-style paths on the other.

In the spirit of your comment about "pretty good but not necessarily optimal," I present the following idea with absolutely no guarantee of optimality!

For completeness, here is the pseudocode that you referred to (Remark: the algorithm linked assumes edge capacities are integers between 1 and C and that flow and residual capacity values are integral):

Scaling-Max-Flow(G, s, t, C) {
   foreach e ∈ E f(e) ← 0
   Δ ← smallest power of 2 greater than or equal to C
   G_f ← residual graph

   while (Δ ≥ 1) {
      G_f(Δ) ← Δ-residual graph
      while (there exists augmenting path P in G_f(Δ)) {
         f ← augment(f, C, P)
         update G_f(Δ)
      }
      Δ ← Δ / 2
   }
   return f
}

Observe that when $\epsilon$ = 1 ($\epsilon = \Delta$ in the psuedocode), you're just finding paths in shortest to longest order, and when $\epsilon$ is large, you're finding paths in (more or less) fattest to slimmest order. In fact, depending on the instance, the capacity-scaling algorithm finds paths in shortest to longest order within "buckets" of "enough flow."

Then, add another input parameter $0 \le \rho \le 1$ that represents how much you care about "fatness" vs "shortness." In order to ensure we're not massively affecting the runtime, we further require that $\rho$ is a rational number.

Then, each time $\epsilon$ is assigned a value, we additionally take the $\rho$-weighted arithmetic mean (I hope that's the correct term..) between 1 and its current value. That is,

$\epsilon \leftarrow (\rho)\epsilon + (1-\rho)$

For $\rho = 0$, we end up with a pure shortest path algorithm; for $\rho = 1$, we get a pure fattest path algorithm; and for $0 < \rho < 1$ we get something in between. In particular, for some middle value, $\epsilon$ will converge to $\le 1$ more quickly, so you'll get more shortest paths, and fewer fattest paths.


Natural candidate against the Isomorphism Conjecture? The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is that it implies $P\neq NP$. It was published in 1977, and a piece of supporting evidence was that all $NP$-complete problems known at the time were indeed p-isomorphic. In fact, they were all paddable, which is a nice, natural property, and implies p-isomorphism in a nontrivial way.

Since then, the trust in the conjecture deteriorated, because candidate $NP$-complete languages have been discovered that are not likely to be p-isomorphic to $SAT$, although the problem is still open. As far as I know, however, none of these candidates represent  natural problems; they are constructed via diagonalization for the purpose of disproving the   Isomorphism Conjecture.

Is it still true, after nearly four decades,  that all known natural $NP$-complete problems are p-isomorphic to $SAT$? Or, is there any conjectured natural candidate to the contrary?

I think the answer is yes, even today there is no known natural problem that is a candidate for violating the Isomorphism Conjecture.

The primary reason is that typically natural NP-complete problems are very easily seen to be paddable, which Berman and Hartmanis showed suffices to be isomorphic to SAT. For natural graph-related problems this typically involves adding extra vertices that are, e.g., disconnected from the graph, or connected in a very particular (but usually obvious) way. For the decision version of optimization problems, it typically involves adding new dummy variables with no constraints on them. And so on.


Missing Wikipedia articles Which missing TCS topics on Wikipedia would you most like there to be an article about?

They could be glaring omissions or just topics you think should really have an article.

One topic per answer please so that the most wanted ones can be voted up.

Update 5/2/2017: Shuchi Chawla is leading an effort to improve TCS coverage on wikipedia. I'm adding this update in the hopes that people will update their answers as appropriate, add more answers, and/or contribute to the effort!

Some missing topics from my collection of graph algorithms articles:

Dynamic graph algorithms
K shortest paths
Spanners and approximate shortest path data structures

Also, not so much missing topics, but a lot of the articles on topics covered by undergraduate algorithms classes kind of look like they were written by students in those classes. There's a deeper level of understanding missing, and they take a dogmatic point of view that reflects a single textbook rather than a synthesis of multiple sources. More expert help there could be useful.