Can we fast generate perfectly uniformly mod 3 or solve NP problem? To be honest, I don't know that much about how random number are generated (comments are welcome!) but let's assume the following theoretical model:
We can get integers uniformly random from $[1,2^n]$ and our goal is to output an integer uniformly random from [1,3].

A simple solution whose expected running time is polynomial is the following. Discard $2^n$ (and possibly also $2^n-1$) from $[1,2^n]$ so that the number of remaining integers is divisible by $3$ so we can take $\bmod 3$ of the generated integer.
If we get a discarded number, we generate another number, until we get a non-discarded one.

But what if we want to terminate surely in polynomial time?
Because of divisibility issues, the problem becomes unsolvable.
However, I wonder if we can solve the following.

  Suppose we can generate integers uniformly random from $[1,2^n]$ and we are given a computationally hard problem.
  Our goal is to output an integer uniformly random from [1,3] or solve the hard problem.

Here the hard problem can be factoring an integer, solving a SAT instance or anything similar.
For example, we can decode a one-way permutation $f$ as follows, if we are given some $f(x)$ (and supposing $n$ is even):
If for our random string $f(r)<f(x)$, then take $f(r) \bmod 3$, if $f(r)>f(x)$, then take $f(r)-1\bmod 3$.
Finally, if $f(r)=f(x)$, then we are done, as $r=x$.
(If $n$ is odd, then something similar works, just we also have to check if $f(r+1)=f(x)$ and subtract $2$ if $f(r)>f(x)$.)

Summary of answers.
Emil Jeřábek has shown that unless we can generate perfectly uniformly, we can solve any single-valued search problem from TFNP, and also from PPA-3.
On the other hand, daniello has shown that we cannot solve NP-complete problems the above way, unless NP=co-NP.

I will use numbers starting from $0$ rather than $1$, as I find it much more natural.
Here are two classes of problems we can solve in this way:

Functions in TFNP (i.e., single-valued total NP search problems)
(This generalizes the example with one-way permutations. It includes as a special case decision problems from $\mathrm{UP\cap coUP}$.)
The setup is that we have a polynomial-time predicate $R(x,y)$, and a polynomial $p(n)$ such that for every $x$ of length $n$, there exists a unique $y$ of length $m=p(n)$ such that $R(x,y)$ holds. The computational task is, given $x$, find $y$.
Now, I will assume wlog that $m$ is even, so that $2^m\equiv 1\pmod3$. The algorithm is to generate a uniformly random $y\in[0,2^m)$, and output

$y$ (as a solution of the search problem) if $R(x,y)$;

$y-y'$ (as a random element of $\{0,1,2\}$) if $y-y'\in\{1,2\}$, and $R(x,y')$;

$y\bmod3$ (as a random element of $\{0,1,2\}$) if no $y'\in\{y,y-1,y-2\}$ solves $R(x,y')$.

If there were no solution of the search problem, the $2^m$ random choices would give $1$ and $2$ $(2^m-1)/3$ times, and $0$ $(2^m+2)/3$ times (one more). However, if $y$ solves the search problem, we tinkered with the elements $y,y+1,y+2$ (which hit all three residue classes) so that they only produce residues $1$ and $2$, which evens out the advantage of $0$. (I am assuming here wlog that $y<2^m-2$.)

PPA-$3$ search problems
A convenient way to define PPA-$3$ is as NP search problems many-one reducible to the following kind of problems. We have a fixed polynomial-time function $f(x,y)$, and a polynomial $p(n)$, such that for any input $x$ of length $n$, the induced mapping $f_x(y)=f(x,y)$ restricted to inputs $y$ of length $m=p(n)$ is a function $f_x\colon[0,2^m)\to[0,2^m)$ satisfying $f_x(f_x(f_x(y)))=y$ for every $y$. The task is, given $x$, find a fixpoint $y$ of $f_x$: $f_x(y)=y$.
We can solve this in the way in the question as follows: given $x$ of length $n$, we generate a random $y$ of length $m=p(n)$, and output

$y$ if it is a fixpoint of $f_x$;

otherwise, $y$, $f_x(y)$, and $f_x(f_x(y))$ are distinct elements. We can label them as $\{y,f_x(y),f_x(f_x(y))\}=\{y_0,y_1,y_2\}$ with $y_0<y_1<y_2$, and output $i\in\{0,1,2\}$ such that $y=y_i$.

It is clear from the definitions that this gives a uniform distribution on $\{0,1,2\}$, as the non-fixpoint $y$'s come in triples.

Let me show for the record the equivalence of the problem above with Papadimitriou’s complete problem for PPA-$3$, as this class is mostly neglected in the literature. The problem is mentioned in Buss, Johnson: “Propositional proofs and reductions between NP search problems”, but they do not state the equivalence. For PPA, a similar problem (LONELY) is given in Beame, Cook, Edmonds, Impagliazzo, and Pitassi: “The relative complexity of NP search problems”. There is nothing special about $3$, the argument below works mutatis mutandis for any odd prime.

Proposition: The following NP search problems are poly-time many-one reducible to each other:

Given a circuit representing a bipartite undirected graph $(A\cup B,E)$, and a vertex $u\in A\cup B$ whose degree is not divisible by $3$, find another such vertex.

Given a circuit representing a directed graph $(V,E)$, and a vertex $u\in V$ whose degree balance (i.e., out-degree minus in-degree) is not divisible by $3$, find another such vertex.

Given a circuit computing a function $f\colon[0,2^n)\to[0,2^n)$ such that $f^3=\mathrm{id}$, find a fixpoint of $f$.

Proof:
$1\le_p2$ is obvious, as it suffices to direct the edges from left to right.
$2\le_p1$: First, let us construct a weighted bipartite graph. Let $A$ and $B$ be copies of $V$: $A=\{x^A:x\in V\}$, $B=\{x^B:x\in V\}$. For each original edge $x\to y$, we put in an edge $\{x^A,y^B\}$ of weight $1$, and an edge $\{x^B,y^A\}$ of weight $-1$. This makes $\deg(x^A)=-\deg(x^B)$ equal to the degree balance of $x$ in the original graph. If $u$ is the given vertex of balance $b\not\equiv0\pmod3$, we add an extra edge $\{u^A,u^B\}$ of weight $b$, so that $\deg(u^A)=2b\not\equiv0\pmod3$, and $\deg(u^B)=0$. $u^A$ will be our chosen vertex.
In order to make the graph a plain unweighted undirected graph, we first reduce all weights modulo $3$, and drop all edges of weight $0$. This leaves only edges of weights $1$ and $2$. The latter can be replaced with suitable gadgets. For example, instead of a weight-$2$ edge $\{x^A,y^B\}$, we include new vertices $w_i^A$, $z_i^B$ for $i=0,\dots,3$, with edges $\{x^A,y^B\}$, $\{x^A,z^B_i\}$, $\{w^A_i,y^B\}$, $\{w^A_i,z^B_i\}$, $\{w^A_i,z^B_{(i+1)\bmod4}\}$: this makes $\deg(w_i^A)=\deg(z_i^B)=3$, and contributes $5\equiv2\pmod3$ to $x^A$ and $y^B$.
$3\le_p2$: Let me assume for simplicity $n$ is even so that $2^n\equiv1\pmod3$. We construct a directed graph on $V=[0,2^n)$ as follows:

We include edges $3x+1\to3x$ and $3x+2\to3x$ for each $x<2^n/3-1$.

If $x_0<x_1<x_2$ is a non-fixpoint orbit of $f$, we include edges $x_0\to x_1$ and $x_0\to x_2$.

The chosen vertex will be $u=2^n-1$. The first clause contributes balance $1$ or $-2\equiv1\pmod3$ to each vertex $\ne u$. Likewise, the second clause contributes balance $-1$ or $2\equiv-1\pmod3$ to vertices that are not fixpoints. Thus, assuming $u$ is not already a fixpoint, it is indeed unbalanced modulo $3$, and any other vertex unbalanced modulo $3$ is a fixpoint of $f$.
$1\le_p3$: We may assume that $A=B=[0,2^n)$ with $n$ even, and the given vertex $u\in A$ has degree $\equiv2\pmod3$.
We can efficiently label edges incident with a vertex $y\in B$ as $(y,j)$, where $j<\deg(y)$. In this way, $E$ becomes a subset of $[0,2^n)\times[0,2^n)$, which we identify with $[0,2^{2n})$. We define a function $f$ on $[0,2^n)\times[0,2^n)$ as follows.

On the complement of $E$: for each $y\in B$, and $j$ such that $\deg(y)\le 3j<2^n-1$, we make $f(y,3j)=(y,3j+1)$, $f(y,3j+1)=(y,3j+2)$, $f(y,3j+2)=(y,3j)$. Also, $f(3i,2^n-1)=(3i+1,2^n-1)$, $f(3i+1,2^n-1)=(3i+2,2^n-1)$, $f(3i+2,2^n-1)=(3i,2^n-1)$ for $3i<2^n-1$. This leaves out the point $(2^n-1,2^n-1)$, and $3-(\deg(y)\bmod 3)$ points $(y,i)$ for each $y\in B$ whose degree is not divisible by $3$.

On $E$: for each $x\in A$, we fix an efficient enumeration of its incident edges $(y_0,j_0),\dots,(y_{d-1},j_{d-1})$, where $d=\deg(x)$. We put $f(y_{3i},j_{3i})=(y_{3i+1},j_{3i+1})$, $f(y_{3i+1},j_{3i+1})=(y_{3i+2},j_{3i+2})$, $f(y_{3i+2},j_{3i+2})=(y_{3i},j_{3i})$ for $i<\lfloor d/3\rfloor$. This leaves out $\deg(x)\bmod3$ points for each vertex $x\in A$ whose degree is not divisible by $3$.

Since $\deg(u)\equiv2\pmod3$, two of its incident edges were left out; we make them into yet another $f$ cycle using $(2^n-1,2^n-1)$ as the third point. The remaining points are left as fixpoints of $f$. By construction, any of them will give rise to a solution of (1).


What is a "level-r pseudo expectation functional"? In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction that expectation of a square of a function is guaranteed to be zero only when the function is a polynomial of degree $\leq \frac{r}{2}$

Is the above right?
So the polynomials on which one would take the "level-r pseudo expectation functional" are what are to be called "level-r fictitious random variable" ?
Conventionally in optimization questions one would say something like "maximize $P_0$ given that $P_i^2=0$ for $i =1,2,..,m$" but the ``r-round SOS SDP relaxation" of this same question would be to choose a "level-r pseudo expectation functional" say $\tilde{E}$ and say "maximize $\tilde{E}[P_0]$ given that $\tilde{E}[P_i^2]=0$ for $i =1,2,..,m$ for $deg(P_i) \leq \frac{r}{2}$"

Is the above right?
And if so then how is a specific $\tilde{E}$ chosen to do the relaxation?

The degree $r$ pseudo-expectation operator operates on polynomials of at most degree $r$. Since the pseudo-expectation operator is positive semidefinite, we're guaranteed that the square of a polynomial (or sum of squares of polynomials) always has nonnegative pseudo-expectation.

Also, if we have a system of polynomial equations $\{p_i = 0\}$ of degree at most $r/2$, then we can construct the pseudo-expectation operator to be such that the pseudo-expectation $\tilde{\mathbb{E}}[p_i q] = 0$ for all polynomials $q$ of sufficiently small degree.

The intuition should be that if $\{p_i=0\}$ has a feasible solution, then $\mathbb{E}[ p_i(x) ] = 0$ where $x$ is a random feasible solution to $\{p_i = 0\}$ and $\mathbb{E}$ is the "actual" expectation operator.

But of course, it is not possible for us to directly sample this distribution. Instead we play a sort of game where we assume that we can evaluate various expectations of polynomials $\mathbb{E}[p]$ (that is, moments) of this distribution over feasible solutions, and 'combine' them together to get a feasible solution.

But of course, we don't really have those moments, either, because again it's too hard to sample the distribution. So we instead use the SoS algorithm to find a pseudo-distribution and pseudo-expectation operator that we can evaluate to get pseudo-moments $\tilde{\mathbb{E}}[p]$, and feed the pseudo-moments to the same 'combiner' algorithm as if they were actual moments, and sometimes we get an answer out that's actually not half bad.

Edit: It is better to consider the sum of squares SDP as optimizing a particular pseudo-expectation; for example, in Goemans-Williamson, we maximize $\tilde{\mathbb{E}}[ \langle x, Lx \rangle]$ where $L$ is the Laplacian and this corresponds to maximizing the value of our cut.


Calculate sum of reciprocal rank in arbitrary large graph For arbitrary graph of n node, can I approximate $\sum_{v\neq u}\frac{1}{Rank_u(v)^a\times Rank_v(u)^b}$ with $\sum_{v\neq u}\frac{1}{Rank_u(v)^{a+b}}$ or not when n is large enough? $a,b>0$, $Rank_u(v)=k$ if v is the $k$th nearest node to u. For example, $Rank_u(u)=1$, $Rank_u(u')=2$ where u' is the nearest node to u. Here approximation means something like $\Theta(n)$. Thanks a lot!

If I understand the requirements correctly, the answer is no. I will restate (what I understand to be) the problem:

We are dealing with graphs $(V,E,\delta)$ (undirected, though directed edges won't change the answer), equipped with a distance $\delta$ which generates a ranking $Rank_u$ for each node $u$. This means that there are no $u,v,w$ with $v\neq w$ and $d(u,v)=d(u,w)$; for any node $u$, $Rank_u$ is then the unique function $V\to\{1,...,|V|\}$ such that $Rank_u(v)<Rank_u(w)$ iff $d(u,v)<d(u,w)$.

I will concentrate on the case $a=b=1$, i.e. consider the sums

$s_1 := \sum_{v\neq u}\frac{1}{Rank_u(v)Rank_v(u)}$ and $s_2 := \sum_{v\neq u}\frac{1}{Rank_u(v)^2}$.

The question is whether $s_2$ can be used to approximate $s_1$. Note that for a graph with $n$ nodes, $s_2$ will always be equal to $n\sum_{i=2}^n\frac{1}{i^2}$, which is in $O(n)$, since $\sum_{i=2}^\infty\frac{1}{i^2}$ converges. It is enough to find a family $(V_n,E_n,\delta_n)$ of graphs with $|V_n|=n$ for which $s_1$ grows more quickly. Consider this example:

$(V_n,E_n)$ is the complete graph $K_n$ on $n$ nodes. The metric $\delta_n$ is given by $\delta_n(v_i,v_j) = 2^i+2^j$ for $i\neq j$ (and $0$ for $i=j$). The resulting ranking functions are

$Rank_{v_i}(v_j) = 1+j$ for $j<i$,
$Rank_{v_i}(v_i) = 1$,
$Rank_{v_i}(v_j) = j$ for $j>i$.

The first sum above then becomes

$s_1 = 2\sum_{i<j}\frac{1}{Rank_{v_i}(v_j)Rank_{v_j}(v_i)} = 2\sum_{i<j}\frac{1}{j(1+i)} = 2\sum_{j=2}^n(\frac{j-1}{j}\sum_{i=1}^{j-1}\frac{1}{i})$;

the summand is in $\Theta(\log j)$, and $s_1$ is in $\Theta(n\log n)$.


Oracle results on P vs BPP Let $A$ be any EXP complete problem. Then, $P^A = NP^A$.

Let $B$ be some oracle that takes into accounts the queries that $M$ (a TM in P) will make, and we can get $P^B \neq NP^B$.

Question: Do we have similar oracle results for P vs BPP?

I had a vague recollection that I knew an excellent reference for such oracle separations. I finally found it.

A great reference for oracle separations (for classes between P and PSPACE) is the following paper:

  Vereshchagin, N K (1994), "RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS", Russian Academy of Sciences. Izvestiya Mathematics 42 (2): 261

The paper shows (or gives a citation for) an oracle separation between almost every pair of classes that you might care about between P and PSPACE (e.g., it has classes like P, RP, BPP, UP, FewP, NP, MA, AM, other levels of PH, PH, IP, PSPACE, etc.).

For example, Theorem 8 shows an oracle problem in coRP that is not in NP. Since (relative to all oracles) coRP is in BPP and NP contains P, we get an oracle problem in BPP that is not in P.

As I mentioned in my comment, showing an oracle for which $\text{P}^A = \text{BPP}^A$ is easy. Let A be a EXP-complete language or a PSPACE-complete language.


Computing power sums I know some schemes to compute power sums (I mean $1^k + 2^k + ... + n^k$) (here I assume that every integer multiplication can be done in $O(1)$ time for simplicity): one using just fast algorithm for computing $n^k$ in $O(\lg k)$ and it's overall time is $O(n \lg k)$, the other, using Bernoulli numbers, can be implemented in $O(k^2)$. And the most complicated works in $O(n \lg \lg n + n \lg k / \lg n)$ - it uses somewhat like sieve of Eratosthenes. (Don't know if it's well-known, I came up with this by myself, so if it not well-known, I can explain how to do it)

Every of this 3 algorithms, but the first, has it's own pros and cons, for example for every $k = n^{O(1)}$ the last algorithm works in $O(n \lg \lg n)$ time, while first in runs $O(n \lg n)$ and second is even worse. When $k = o(\sqrt{n \lg \lg n})$ second algorithm performs better than others.

So my question is: if there exists some more efficient algorithms? (Like in previous problems, I am not merely interested in asymptotics in $n$, but in $k$ too)

Thank you very much!

Here's another approach, which I think runs in $O(k)$ time.

Define $S_k$ by

$$S_k = {1 \choose k} + {2 \choose k} + \dots + {n \choose k} = {n+1 \choose k+1}.$$

The right-hand-side can be computed in $O(k)$ time.

Similarly,

$$S_{k-1} = {1 \choose k-1} + {2 \choose k-1} + \dots + {n \choose k-1} = {n+1 \choose k},$$

and given the value of the previous sum $S_k$, we can compute this sum $S_{k-1}$ in $O(1)$ time (using the fact that ${n+1 \choose k} = {n+1 \choose k+1} \times {k+1 \over n-k+1}$).

In this way, we can compute all of the sums $S_k,\dots,S_2,S_1,S_0$ in $O(k)$ time.

Furthermore, we can find constants $c_0,\dots,c_k$ such that

$$x^k = c_k {x \choose k} + \dots + c_1 {x \choose 1} + c_0 {x \choose 0}$$

holds for all $x$.  It follows that

$$S = 1^k + 2^k + \dots + n^k = c_k S_k + \dots + c_1 S_1 + c_0 S_0,$$

which can be computed in $O(k)$ time.


Could a descriptive complexity version of Rice's theorem be used to separate AC0 and PSPACE? In this question, it was mentioned that there are descriptive complexity versions of Rice's theorem.  I found a proof of the following theorem:

  Given a complexity class C, nontrivial properties of languages in C cannot be computed in C

I had previously posted the proof I found, but because it was so long and because it was pointed out in the comments that this paper contains a proof of that theorem already, I removed it.  (If for some reason you are desperate to see my proof, please see the previous revisions of this question.)

My interest is in whether or not this theorem could be used to separate AC0 and PSPACE.  Here's the argument:

Consider the property P of the complexity class AC0 defined as follows:

P:  the property of being an FO query that accepts a particular fixed structure, namely the structure consisting of one element, no functions, no constants, and no relations

Clearly, by the theorem above, P is not decidable in AC0; it is a non-trivial property of FO queries.

However, a little examination should show that computing whether or not an FO query accepts such a simple structure can be decided as easily as TQBF; thus, P is decidable in PSPACE.

To ensure clarity on this point (that P is computable in PSPACE):  Note that the property we are interested in requires that the structure be FO.  So, we are trying to determine whether a FO query that is running on a single-element structure with no relations accepts.  Because there are no relations to deal with, it should be clear that the task of deciding such an FO query is equivalent to deciding an instance of TQBF; there are no relations, so the only challenge that remains is to evaluate whether or not the quantified boolean formula is true.  This is basically just TQBF, so P is computable in PSPACE.

Because P is computable in PSPACE but not AC0, we should be able to conclude that AC0 != PSPACE.  Is this reasoning correct, or have I made a mistake somewhere?  I'm particularly concerned about the preceding paragraph; I'll try to clarify and update the argument tomorrow after I get a chance to give a little more thought to the exposition.

I would accept as an answer an example of a FO query that, when computing on the one-element, relation-free structure I've described, clearly does not make sense as an instance of TQBF.  (I'm suggesting that there isn't one, so if you can show that there is one, that would be a counterexample.)

Thanks.

Deciding the nontrivial properties of (an indexing) sets in a complexity class is as difficult as computing the graph of the universal function for the class. Intuitively this means that the only way to decide a nontrivial property is to simulate the machines and wait for answers. It seems to me that the idea of using such a property will just give what is known by the hierarchy theorems. (See theorem 4.2 of D. Kozen, "Indexing of subrecursive classes", 1978 for details and the exact statement of the theorem.)

We can decide the $grU_{AC^0}$ (the graph of universal function for $AC^0$) in $PSpace$, the reason is simply that $AC^0 \subseteq L$ and we have a universal machine for languages in $L$ in $PSpace$, so it is easy to simulate the $AC^0$ machines (or the descriptive complexity equivalent of $AC^0$ which is $FO$ queries) in $PSpace$. This means that that we can decide the property you have stated in $PSpace$. Since it is a nontrivial property, it is not decidable in $AC^0$. So this argument separates $AC^0$ from $PSapce$.

But is this surprising? No, since we already know a simpler way of stating (essentially) the same argument: $AC^0 \subseteq L \subset PSpace$, the last proper inclusion is by the space hierarchy theorem.


In regards to the tautologies of a polynomially-bounded propositional proof system In the book 'Logical Foundations of Proof Complexity', co-authored by Stephen Cook, the following definition is given:

A proof-system $F$ is said to be polynomially-bounded if there is a polynomial p(n) such that for all tautologies $A$, there is a proof $X$ of $A$ in $F$ such that |x| $\leq$ p(|A|). Informally, a proof system is polynomially-bounded if every tautology has a short proof in F.

My question is in regards to what "all tautologies" means. Is it in regards to every tautology in $F$ or any tuatology in in any adequate proof system, which first needs to be converted to an equivalent formula in $F$?

For example, let's say we are dealing with 2 very different proof-systems, A and B. Let's just assume for the moment that B is polynomially-bounded. Then every tautology in B has a short proof.

My question is: Given a tautology in system A--denoted as $\phi$--, is it necessary that the conversion from $\phi$ in A to its equivalent formula $\phi'$ in B happens in polynomial-time?

Or is the only thing that is necessary for B to be considered a polynomially-bounded proof system this: that once $\phi$ is represented in the system B (regardless of how long this conversion takes place), then this formula has a short proof in B?

So if it was inefficient to convert $\phi$ to $\phi'$, yet $\phi'$ nonetheless still had a short proof in system B, is B still considered a polynomially-bounded proof system?

Your question is like asking what is the class of formulas for the problem SAT?
In the definition of SAT it is fixed to some fixed class,
say those based on $\{\lnot, \land, \lor\}$
but it doesn't really matter usually whether
we talk about formulas based on
$\{\lnot, \land, \lor\}$ or $\{\bot, \to \}$ or
any other complete set of Boolean connectives.
Therefore it is often not explicitly stated.
The reason is they can simulate each other with
at most polynomial increase in the size of formulas.
Therefore it is often not explicitly mentioned.
If we pick an unusual one then things might be completely different.
E.g. DNF-SAT is in P, but this does not mean SAT is in P.
Similarly CNF-TAUT is in P and therefore
if we define the concept of proof system for CNF-TAUT
it has polynomially bounded proof system.
But again this does not mean that
TAUT has polynomially bounded proof system.
The problem we are interested in is TAUT, not CNF-TAUT.
We want a polynomially bounded proof system for TAUT.

For the definition of proof system
we have to similarly fix the class of tautologies.
If we pick different classes we get different definitions.
TAUT being the dual to SAT
it is natural to take the dual of the formulas for SAT
(i.e. formulas based on connectives $\{\lnot, \land, \lor\}$).
It is also common to use DNF-TAUT as a dual to CNF-SAT
(there is a simple reduction from SAT to CNF-SAT
using new extension variables such that
the set of satisfying assignments of the original formula and resulting CNF
are P-isomorphic).
But as long as we can efficiently express DNF formulas
it usually does not matter what we use.
It can be linear equations, or any class of computational objects
as long as they can express DNFs with at most a polynomial increase in size.
If that is not the case then
the system is trivially not polynomially bounded as
it is not a proof system for TAUT (or DNF-TAUT).
The book does not deal with cases where
the class of formulas does not contain DNFs.

For the purpose of the book you can assume that the class of propositional formulas contains DNFs and every tautology means every DNF tautology.

  A proof system $Q$ is polynomially bounded if
  there is a polynomial $p$ such that
  for every DNF tautology $\varphi$
  there is a $Q$-proof $\pi$ such that
  $|\pi| \leq p(|\varphi|)$.

As you can see there is no mention of other proof systems.

If you want the more general definitions look at Reckhow's thesis.
Reckhow looks at the more general definition with different set of connectives
and classes of formulas.
He shows that any two Frege systems polynomially simulate each other
as long as we have a complete set of Boolean connectives.
I think the simplest way to explain it is as follows:

  If we have a complete set of connectives
  we can express in polynomial size the truth of formulas
  based on another finite set of Boolean connectives.

For more see the section in Reckhow's thesis
discussing polynomial simulation
between proof systems with different class of formulas.


Minimizing $L_2$ norm of a vector with two distinct entries Let $d\in\mathbb N$ and denote $V=\bigcup_{a,b\in\mathbb R}\{a,b\}^d$, the set of all vectors with two distinct values.
Given a vector $x\in \mathbb R^d$, I want to compute some $v^*\in V$ such that $\left\lVert x-v^*\right\rVert_2\le \left\lVert x-v\right\rVert_2$ for any $v\in V$.

What would be the fastest algorithm to compute $v^*$?

It seems possible to show that the problem is equivalent to finding a threshold $T\in\mathbb R$ such that $v^*_i=\begin{cases}a & \mbox{if $x_i<T$}\\b & \mbox{otherwise}\end{cases}$, where $a$ is the mean of all entries smaller than $T$ and $b$ is the mean of all entries larger than or equal to $T$.
This suggests a $O(d^2)$ time algorithm. Can we find the optimal $T$ faster?

I am also interested in an extension of the problem where we look at $V_4=\bigcup_{a,b,c,z\in\mathbb R}\{a,b,c,z\}^d$ instead of $V$. How fast can we find $v^*$ in this setting?

(This is probably a comment but I cannot comment)
This seems to be 1-dimensional $k$-means clustering for $k=2$ and $k=4$. Here is a reference that gives a $O(kn + n \log n)$ algorithm for 1-d $k$-means clustering: Grønlund, Larsen, Mathiasen, Nielsen, Schneider, Song, Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. It seems similar to the algorithm given in the comments.


How efficiently can circuits over sets of naturals be transformed to boolean circuits? I am interested in reducing a circuit over sets of naturals (see here for some basic notions about this type of circuits) to a boolean circuit computing the same output. A very basic circuit of this type is a circuit $C_s$ defined over a beginning subset of $\mathbb{N}$ (i.e., $\{0,...,n\}$) containing only $\{\cap,\cup\}$ gates. My question is how efficiently can a boolean circuit $C_b$ be constructed that computes the same output as $C_s$ and whether there exists a lower bound on the size of such a $C_b$.

The simplest way I can think of, in order to achieve the above, would be to represent a set $S$ by a binary array $\mathbf{s} = s_1,...,s_n$ of size $n$ where a 1 in position $i$ would signify that element $i \in S$. With this representation in mind, a union operation between sets $S,P$ can be implemented by $n$ OR gates by performing a point-wise OR for arrays $\mathbf{s}$ and $\mathbf{p}$. Likewise, intersection would be captured by point-wise AND. This approach would imply that $|C_b| \in O(n)$ and likewise for the reduction time (with a multiplicative factor of $|C_s|$).

Can someone point out whether this approach is optimal or whether there is a better way to achieve the above? More importantly, is there a known lower bound for transformation of circuits over sets of naturals to boolean circuits? My research is security-motivated and the problem is governed by a security parameter $\lambda$ such that $n \in O(2^{\lambda})$ hence my approach is infeasible as it yields exponential size $C_b$. (EDIT: Assume each set $S$ is of size only $O(poly(\lambda)$)

A simple conversion process for $\boldsymbol\cup\,$, $\boldsymbol\cap\,$, constants, and complements

Note that any integer-set circuit representing a set $S \subseteq \{0,1,\ldots,N-1\}$ can be represented by a boolean circuit which tests $x \mathbin{\in?} S$ for $0 \leqslant x < N$. If $N = 2^n$, this is a boolean circuit with $n$ inputs. We may construct such a circuit $C_n$ as follows.
$\def\GE#1{\mathrm{GE#1}}\def\PRIME={\mathrm{PRIME}}$

Using AND, OR, and NOT gates, we can very easily simulate equality of the input with a binary representation of any integer $0 \leqslant x < 2^n$ with a circuit of size $n$ and depth $\log (n)$.
Next, we may represent your input sets as also being constructed by $\cup$ circuits, constructed from singletons $\{x\}$ for $1 \leqslant x < N$. If $S_j$ has size $m_j \leqslant M$, this requires a circuit with a boolean tree structure, with $m-1$ union gates, having depth at most $\log(m)$.
Finally, we may represent unions and intersections of your sets $S_j$ by logical ANDs and ORs of membership in the input sets. This part of the circuit has the same size $s$ and depth $d$ as the depth of your integer-set-circuit.

We may then obtain a boolean circuit $C_n$ of depth at most $d + \log m + \log n$ and size at most $s + m + mn$. The complexity of building this circuit is essentially $O(s + m(\log m + n \log n))$, arising from doing the necessary construction of the binary trees for the gates representing each $S_j$ and $\{x\}$ for $x \in S_j$.

Note that the complexity does not increase at all if you allow logical complementation, which would represent in principle an infinitely large set including numbers larger than the input size; though to represent numbers which are $N$ or larger, we must use uniform circuit families $\{C_n\}$ rather than a single circuit $C_n$. The construction above will build these efficiently, however.

Remarks on the power of integer-set circuits with arithmetic

In the (extremely powerful!) model of arithmetic circuits including $+$ and $\times$ gates, this construction fails because the outputs to those gates implicitly involve existential quantifiers over satisfying inputs to subcircuits of arbitrary size. As your linked article notes, the Goldbach conjecture can be tested by evaluating $G(0)$, where $G$ is a (finite depth!) circuit,
$$ G :=\overline{\{0\} \times \Bigl(\bigl[ \{2\} \times \GE2 \bigr] \cap \bigl[\; \overline{\PRIME + \PRIME}\;\bigr]\Bigr)} \;, $$
where $\GE2 := \overline{\{0\} \cup \{1\}}$ tests whether an input is $\geqslant 2$, and $\PRIME := \GE2 \cap \bigl[\,\overline{\GE2 \times \GE2}\,\bigr]$ tests whether an input is prime. The enormous power of these circuits seem to me to come from combining negation (which allows you to obtain infinite sets from finite ones) with the $+$ and $\times$ gates (which allow existential quantification over all inputs to sub-circuits, as to whether there are accepted inputs whose sum or product is equal to the input integer). If you do not have additions or multiplications, those quantifications are absent, and the problem becomes much simpler — indeed, very close in flavour to a run-of-the-mill boolean circuit.


Generation of unlabeled acyclic digraphs I'm looking for an algorithm to efficiently generate all unlabeled acyclic digraphs of a given order.  (By "unlabeled" I mean that no two of the generated digraphs should be isomorphic.)
Thanks

Edit: removed the word "enumeration" from title; I made the original title "Enumeration/generation of unlabeled acyclic digraphs" in a misguided effort to increase the number of possible answers; I had conjectured, incorrectly, that enumeration algorithms could be easily adapted to generate all the enumerated digraphs; now I realize this conjecture is wrong, hence the edited title emphasizes that I'm interested in an algorithm for generating (and not just enumerating) unlabeled acyclic digraphs.

If you are looking for an implementation, Sage knows how to generate general digraphs up to isomorphism

sage: len(list(digraphs(4)))
218

You can then plug in a "test" method if you just want the acyclic ones :

sage: len(list(digraphs(4, property = lambda g:g.is_directed_acyclic())))
31

It returns 302 digraphs on 5 vertices, and 5984 on 6 vertices. But I am a bit scared to try larger values :-)

By the way, giving those values to the OEIS returns the expected sequence :

http://oeis.org/search?q=1,2,6,31,302,5984&language=english&go=Search

Which also happens to contain several references that may suit your taste :-)

Nathann


What is the name of this algorithm on direct acyclic graph? I am trying to linearize the history of a git branch for display purpose. I want commits to be collocated by branch instead of simply displaying commits in the order given by the time of commit.

In this graph problem, there is a start node and an final node and in between there is a direct acyclic graph (DAG). It looks like the following:

One possible solution is the following:

a0 a b d1 x2 x1 d2 d3 c3 c1 e c2 f z1 z2 z3 g h i j k

It walks the graph upward, consuming both branches of merge commmits. It moves to the next branch, when it meets a vertex that has several outgoings vertices - a source vertex like b and d1. A source vertices is added to the result list when all it children are already in the result list.

Here is a proof of concept implementation in scheme:

(define (linearize graph start)
  (let loop ((todos (list start))
             (out '()))
    (pk 'todos todos)
    (if (null? todos)
        out
        (let ((todo (car todos))
              (rest (cdr todos)))
          (let ((incomings (ref-incomings graph todo)))
            (case (length incomings)
              ((0) (loop '() (cons todo out)))
              ((1) (if (null? rest)
                       (loop (reverse incomings) (cons todo out))
                       (if (eq? (length (ref-outgoings graph (car incomings))) 1)
                           (loop (append incomings rest) (cons todo out))
                           (loop rest (cons todo out)))))
              (else (loop (append (reverse incomings) rest) (cons todo out)))))))))

What is the name of this algorithm?

Looks to me like some additional restrictions on a topological sort: https://en.m.wikipedia.org/wiki/Topological_sorting .
Also git already supports this operation for instance git rev-list --topo-order .


Understanding the definition of a "restriction of a resolution derivation" I am reading the paper An Introduction to Lower Bounds on Resolution Proof Systems. In its subsection 2.3 the author gives an inductive definition of the restriction of a resolution refutation $\pi$.
My preoccupation resides on the second line of the definition :

$C'_i=C'_{j_1} \vee C'_{j_2}$ if $C_{j_1} \vee y$ and $C_{j_2}\vee \bar{y}$ derive $C_i$ via the resolution rule for $j_1 < j_2 < i;$.

I wonder how this induction can be apply on $C'_{j_1}$ and $C'_{j_2}$ since $C_{j_1}$ and  $C_{j_2}$ are not in $\pi$ but instead $C_{j_1}\vee y$ and  $C_{j_2}\vee \bar{y}$.

Furthermore, in example 2.12 the author computes the restrictions  $\pi[x_1=0]$ and $\pi[x_2=1]$ of the refutation $\pi$ as if they were just a restrictions of sets of clauses i.e. by using $\pi[x=a]=\{C[x=a]; C \in \pi\}$ instead of the inductive definition.

Is there anything that I'm missing?

For the first point, it seems that $C_{j_1} := D_{j_1} \lor y$ and $C_{j_2} := D_{j_2} \lor \bar{y}$ are meant to be the clauses in $\pi$, instead of $C_{j_1} \lor y$ and $C_{j_2} \lor \bar{y}$. This may help in understanding such a definition. Furthermore, it seems that the resolution of $C'_{j_1}$ and $C'_{j_2}$ upon $y$ is taken, rather than $C'_{j_1} \lor C'_{j_2}$ (they are equivalent).
This view would explain, for example, the computation of $C_4[x=0]$: $C_1' = x_2 \lor \bar{x_3}$ and $C_2' = x_3$ are resolved upon $x_3$ to obtain $C_4' = x_2$.

For the second point: the computations are meant to produce the same output. In the paper, the final result without any computation is shown. Going through the recursive computation by pencil and paper shows how the rules are used.


Is there a relationship between relational algebra/calculus and category theory? I am aware of at least two different theoretical approaches for understanding relational databases: Codd's relational algebra/calculus, and category theory.

Is there any relationship between these two approaches? Are they in some sense equivalent? Is there any introductory work explaining how both of these frameworks explain relational databases?

Background:
A while ago I read David Spivak's Category Theory for Scientists which spent quite some time discussing how category theory could be applied to understand the theory of relational databases. However, having little personal experience about what relational databases are or why they are useful, at the time I did not fully appreciate the depths of insight found in the book.

However, recently I have been learning about SQL queries and two R packages for data manipulation: dplyr and data.table. SQL can apparently express much of the ideas of Codd's relational algebra/calculus/model, but not all. Moreover, the author of dplyr, Hadley Wickham, has stated explicitly that his philosophy underlying the package is based on Codd's work on relational algebra, and the basic commands of data.table map fairly well to commands in SQL and dplyr.

I also know that category theory influences a lot of programmers using functional programming languages like Haskell. However, I am not really aware of there being any use of functional programming for data manipulation or data science, besides Hadley Wickham's purrr package for R, the fact that Apache Spark is written in Scala, and technologies related to MapReduce.

All of this sort of suggests to me that there should be some sort of relationship between category theory and Codd's relational algebra/calculus, but I have never heard of anyone making such a connection explicit or explain how it underlies the design decisions in popular data manipulation and relational database technologies. So I also suspect I could be entirely wrong.

EDIT: Apparently David Spivak has worked on a "functorial query language (FQL)". This sounds like it might be an application of such a theoretical connection, provided it exists.

Note: I am not sure if "relational-structures" is the appropriate tag for discussion of relational databases or relational algebra/calculus. This Wikipedia article suggests they might be connected, but ultimately I don't know what the phrase "relational structure" means. Please feel free to re-tag.

Categorical approaches to query languages is a bit of a niche interest, but I think it's a very interesting niche!

Two of the key figures in this area are Peter Buneman and Torsten Grust. Obviously, they didn't do all the work, but if you start with their papers and trace out the citation graph, you'll get pretty good coverage of the area.

The central observation that they work from is that since a relation can be viewed as a set of tuples, the powerset functor can be interpreted as taking  a tuple type to the type of relations over that tuple. Then, the fact that the powerset functor forms a monad means that you can use ideas inspired by Philip Wadler's monad comprehension syntax to give a categorically-inspired calculus for queries with a rich equational theory.

Indeed, Buneman et al's query system Kleisli got its name from the fact that monads are sometimes called "Kleisli triples".

Grust's PhD thesis, Comprehending Queries, works this out these ideas in detail, including the use of monad morphisms to model aggregation operators (like sum and count). Grust and his group also built a system, Ferry, which studied how to integrate databases into programming languages.

One of the main issues in this work (and also in Kleisli, if memory serves), is that monadic query languages tend to be a bit more expressive than relational algebra -- they permit queries to handle sets of sets. Compiling this to SQL or relational algebra requires some care (for example, see Cheney et al's A practical theory of language-integrated query), but the basic issue has a very nice categorical formulation. Relational algebra only uses the monoidal structure of the powerset functor, i.e., the existence of a cartesian product natural transformation $(\bullet) : \mathcal{P}(X) \times \mathcal{P}(Y) \to \mathcal{P}(X \times Y)$; and monadic query languages also demand the join, $\mu : \mathcal{P}(\mathcal{P}(X)) \to  \mathcal{P}(X)$.

That's probably the primary stream of work on categorical approaches to query languages.

A new idea (which unfortunately hasn't gotten as much traction as I think it deserves) is David Spivak's work on using simplicial sets to model databases -- see Simplicial Databases. The central innovation is that the simplicial structure permits explicitly modelling the whole database schema including the relationships between tables (eg, the system of foreign keys), and this enables giving semantics to schema update operations.

Another deviation from standard query languages are restricted logic programming languages such as Datalog, which can be understood as relational algebra plus a fixed point operator. Fixed points permit expressing things like transitive closure queries, and so new databases like Datomic feature query languages based on Datalog. My PhD student, Michael Arntzenius, and I have studied the  semantics of Datalog, and come up with a functional analogue we call Datafun, which has a pretty categorical interpretation in terms of the categories of posets and semilattices.


Help needed on method to use for anomaly detection I think people here could guide me in solving a problem related to anomaly detection. The term anomaly here refers to some malware attack.

I could get information about the malware infection from more than one source. For example extracting value from two different data strututres and if the value is different it is certain that virus infection is there.

In order to remove the false positive cases, information is gathered from different data strutres or mechanisms. In that certain information are less trusted and certain information are more trusted.

I am looking for a mathematical method, that could easily handle this type of situations?

Update 1:

Its applied in Linux Kernel for detecting some kind of anomalies. But the problem is that if the kernel is affected you cant trust anyone. But "some" behavior can tell you that anomaly is there. But some others not

Update 2:

Current models mainly depends on archived copy of the system before infection and then compare it with the new state. I am looking for some other method like

(1) Certain variables cant be accessed by a normal module
(2) Information given by command should match
(3) Module code didn't have any jmp instructions often

In these (3) is allowed to some extent. But (1) is disallowed. The (2) should certainly match.

Hope now things are clear.

First of all, I warn that things aren't that simple. Up until now, researchers haven't came up with a perfect algorithm to do that (and I'm almost sure they never will!)

However, there are many competing approaches to do what you want. They compete in efficiency, false-positive rate, false-negative rate, and so on.

The model is as follows: Assume you have a number of algorithms (fuzzy, genetic, neural net, etc.) which process (possibly different) streams of data, and generate alerts if they find anomaly. You then have a stream of alerts, which must be correlated by another algorithm. Unsurprisingly, such algorithm is called alert correlation.

You can find hundreds of papers on this subject here. While this term is usually applied to IDS algorithms, there's nothing preventing you from applying it to antivirus algorithms.


Where is $MA$ more relevant than $\exists BPP$? (EDITED)
A previous version of this question asked about a complexity class I called $MA^*$, which has been recognized by users to be $\exists BPP$.
The difference between $MA$ and $\exists BPP$ is that in the latter class the probabilistic verifier decides a BPP language; while the probabilistic verifier in $MA$,  when $x\in L$, is required to accept with bounded error only for one certificate and can answer just randomly for all the others, thus violating the BPP promise.
What is the natural reason to allow this "strange" power to the class? E.g. an $MA$ language which is not (trivially) in $\exists BPP$ would answer the question. More generally, in which contexts the class $MA$ comes up naturally but $\exists BPP$ wouldn't (trivially) work?
P.S. For now, I'm answering me as follows. A set $C$ of certificates $x,c$ for $x \in L$ makes sense only in reference to a verification procedure for $(x,c)$. If the verifier is probabilistic, and we want bounded error, there could be some $x,c$ that aren't decided. For $x \notin L$, it remains defined that $(x,c) \notin C$, or soundness is compromised. But what should define $(x,c) \in C$ for $x \in L$, if not the verification procedure itself? So in this sense $MA$ is more natural than $\exists BPP$, because $MA$ doesn't assume $C$ before the verification procedure.

$\def\mr{\mathrm}$First, standard derandomization assumptions (the existence of a language in $\mr E$ that requires circuit size $2^{\Omega(n)}$) imply $\mr{promise\text-BPP=promise\text-P}$, hence
$$\mr{MA=\exists BPP=NP},$$
thus any difference between the two classes is likely just an artifact of our incomplete knowledge.
Having said that, there are several results in complexity theory involving $\mr{MA}$ that are not known to hold for $\exists\mr{BPP}$. In particular, there is a group of results of the form
$$\begin{align*}
\mr{PP\subseteq P/poly}&\implies\mr{PP=MA},\\
\mr{PSPACE\subseteq P/poly}&\implies\mr{PSPACE=MA},\\
\mr{EXP\subseteq P/poly}&\implies\mr{EXP=MA},\\
\mr{NEXP\subseteq P/poly}&\implies\mr{NEXP=MA}.
\end{align*}$$
(The first three results are due to Babai, Fortnow & Lund, the last one is due to Impagliazzo, Kabanets & Wigderson.)
If you allow me larger time bounds, an often quoted related result is that
$$\mr{MA\text-EXP\nsubseteq P/poly}$$
(here, $\mr{MA\text-EXP=MA\text-TIME}(2^{n^{O(1)}})$ is the exponential analogue of $\mr{MA}$). In fact, this result can be improved, nevertheless it is not known to be true for $\mr{NEXP^{BPP}}$ (which is the exponential analogue of $\exists\mr{BPP}=\mr{NP^{BPP}}$).


Type theory and computational complexity Is there a type system, which restricts the lambda terms to the terms which fall inside a complexity class? Like the typable terms in the theory are strictly inside the complexity class ? Or is it not possible at all?

I find the there are lot of studies on expressibility of the type theory, like provably terminating, extended polynomials etc.. But is there any way to restrict that to a complexity class?

The keywords you are looking for are "Implicit Computational Complexity". The field studies for instance variants of linear logic and the complexity bounds they can guarantee on the terms underlying the derivations.


Is the following language in RE? There's a computability theory exercise that had me stuck for a long time. I have the language

L={ M | there exists a reduction from HP to L(M) }

I managed to prove it's not in R with a reduction from HP, but I can't figure out if it's in RE (or rather, I suspect it must not be in RE but can't prove it).

I'm not necessarily looking for an actual solution, but a clear enough hint, since it did elude me for a while now.

EDIT: M is a Turing machine. L(M)={x | M accepts x}. HP is the Halting Problem. RE is the Recursively Enumerable class of languages.

One can solve this problem either by a direct proof or using an extended version of Rice's theorem (Theorem II.4.2 in Oddifredi's book Classical Recursion Theory I, where it is attributed to Myhill, Sheperdson, McNaughton and Shapiro). I'll start by the latter.

Rice's theorem says that given a property $P$ of languages:

either $P$ is trivial (i.e. either all languages satisfy $P$, or none does)
or the set $\mathcal{A}$ = {$M$ | $L(M)$ has the property $P$} is not computable

But here we want to know whether $\mathcal{A}$ can be recursively enumerable (the current trend is to say "computably enumerable" instead). This can happen: take for example: {$M$ | $M$ halts on at least 7 inputs}

The generalized version of Rice's theorem says the following. Given a property $P$ of languages, the set $\mathcal{A}$ = {$M$ | $L(M)$ has the property $P$} is computably enumerable if and only if there exists a computably enumerable set $F$ of finite sets of strings such that: $M \in L \Leftrightarrow (\exists u \text{ finite})~[u \in F  \text{  and  }  u \subseteq L(M)]$.

(Notice that it makes sense to talk about a computably enumerable set of finite sets of strings, as such objects can themselves be encoded by strings).

Here we have the set $\mathcal{A}$ = {$M$ | $HP$ reduces to $L(M)$}. Suppose $\mathcal{A}$ is finite. Then there exists a computably enumerable set $F$ as above. Now

If $F$ is non-empty and contains a finite set of strings $u$, then let $M_u$ be a Turing machine whose domain $L(M_u)$ is exactly $u$ (this is easy to build). Then by definition of $F$, $M_u \in \mathcal{A}$, but this means that $HP$ reduces to $L(M_u)=u$, which is a finite set (hence computable), a contradiction since $HP$ is not computable.
Or $F$ is empty, in which case $\mathcal{A}$ is also empty, but this is not the case as there does exist a machine $M_{HP}$ whose domain is exactly $HP$ (as $HP$ is computably enumerable).

We have a contradiction!

But if you don't like using too powerful theorems we can do this directly, via an adaptation of Yohay's proof. Let $\mathcal{A}$ = {$M$ | $HP$ reduces to $L(M)$}. If $\mathcal{A}$ were computably enumerable, it would reduce to the halting problem $HP$. To show that this is not the case, we will show that some set harder than $HP$ can be reduced to $\mathcal{A}$. We'll take the following: $INF$ = {$M$ | $L(M)$ is infinite}. The fact that $HP$ reduces to $INF$ but not vice-versa is standard (if you don't believe me, here is a nice and fairly easy exercise for you!).

Now we want to reduce $INF$ to $\mathcal{A}$. Let $M_{HP}$ be a fixed machine such that $L(M_{HP})=HP$. Let $M$ be any machine. Using $M$, construct the machine $M'$ which does the following.

For all input $x$, $M'$ counts the numbers of elements in $L(M)$. Whenever $n$ elements are found in $L(M)$, $M'$ runs the computation of $M_{HP}(x)$ during $n$ steps of computation. If this halts at any point, then $M'$ halts too, if not it waits to find more elements in $L(M)$ and repeats the process. There are two cases:

If $M \notin INF$, then calling $k$ the number of elements of $L(M)$, by construction $M'$ will only emulate $M_{HP}$ during $k$ steps of computation for any input. For large inputs (|x|>k), this will be insufficient as $k$ steps won't even be enough to read the input! Hence $M'$ will not halt for all inputs $x$ such that $|x|>k$, hence $L(M')$ is finite, and hence $L(M') \notin HP$
If $M \in INF$, then for any input $x$, $M'$ emulates $M_{HP}$ for infinitely many steps of computation, hence $L(M')=L(M_{HP})=HP$. And therefore $M' \in \mathcal{A}$.

We have proven $M \in INF \Leftrightarrow M' \in \mathcal{A}$, so $INF$ reduces to $\mathcal{A}$, which is what we wanted.


Example of logarithmic length witness being easier to verify than find An easy observation is that if a problem $A$ is decidable by a polynomial-time nondeterministic program using $O(\log n)$ nondeterministic bits (i.e., all witnesses are logarithmic in length), then $A \in \mathsf{P}$.

If one then asks the question, "Is it easier to verify a witness than to find one?" for such problems, and one considers all polynomial running times equivalent, then the answer is no, since one can find such witnesses in polynomial time by searching through all potential witnesses.

But what if we consider fine-grained distinctions between polynomial running times? I'm wondering if there is a concrete example of a natural problem in $\mathsf{P}$ that has logarithmic-length witnesses that are easier to verify than to find, where "easier" means a smaller polynomial running time.

For example, known algorithms for perfect matching in graphs take polynomial time, but more than $O(n)$ time on a graph with $n$ nodes. But given a set of $n/2$ pairs of nodes (a witness), it is easy to verify in time $O(n)$ that it is a matching. However, the matching itself requires at $\Omega(n)$ bits to encode.

Is there some natural problem that achieves a similar (apparent) speedup in verification versus finding, in which the witness has logarithmic length?

Consider the decision problem which decides whether a given binary input $x$ of length $n$ is a non-palindrome.
There is a pretty standard communication complexity proof that a single tape TM requires at least $\Omega(n^2)$ time to solve this problem.
On the other hand, we can also solve this problem using a nondeterministic algorithm with a $\log(n)$ length witness $i$: the algorithm accepts whenever the $i$th bit from the start of $x$ differs from the $i$th bit from the end of $x$. Identifying the $i$th bit from the start or end of a length $n$ bitstring can be accomplished in $O(n \log n)$ time on a single tape TM.


Is there a well-defined division operation on finite automata? Background:

Given two deterministic finite automata A and B, we form the product C by letting the states in C be the cartesian product of states in A and states in B. Then, we choose transitions, initial state, and final states so the language accepted by C is the intersection of the languages for A and B.

Questions:

(1) Can we "divide" C by B to find A? Is A even unique, up to isomorphism? We care about the state diagrams, not the languages here and below. Thus, we don't allow compressing the state diagrams to reduce the number of states.

(2) If A is unique, is there an efficient algorithm to find it?

(3) Does every deterministic finite automaton have a unique factorization into "primes". A prime here means an automaton that cannot be factored, that is, written as a product of 2 smaller automata.

Work with @MichaelWehar

Take a look at this MFCS 2013 paper, which studies compositionality in automata. Perhaps it will help.


$\ell_p$-norm preserving Turing machines Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine.

For people working in complexity theory going to quantum complexity a great introductory text is Fortnow's paper which link was posted by Joshua Grochow here. In that paper, the quantum Turing machine is presented as a generalized probabilistic Turing machine. Basically, the probabilistic machine have a state $s$ normalized under the $\ell_1$-norm, i.e. $\parallel s\parallel_1=1$. The time evolution of the machine is given by the application of a stochastic matrix $P$ such that $\parallel Ps\parallel_1=1$, i.e. $P$ preserves the $\ell_1$-norm. So the state at time $t$ is $P^ts$ (the notation may not be precise because the left or right multiplication of $P$ depends on if $s$ is a row or column vector or the rows or columns of $P$ are the subspaces preserving the norm). So in this sense the probabilistic Turing machine is a $\ell_1$-norm preserving machine denoted $M^{\ell_1}$.

Then a quantum Turing machine can be seen as having a state $s$ with $\parallel s\parallel_2=1$ and unitary matrix $P$ (that preserves $\ell_2$-norms) such that $P^ts$ is the state at time $t$ where $\parallel P^ts\parallel_2=1$. This is a $\ell_2$-norm preserving machine denoted $M^{\ell_2}$.

Let in general a $\ell_p$-norm preserving machine be denoted by $M^{\ell_p}$.

So my questions are:

(1) What's the power of $\ell_p$-norm preserving machines for finite $p$? More formally, can we prove that for any given $p$ and $q$, if $q>p$ then there exists a language $L$ and machine $M^{\ell_q}$ such that $M^{\ell_q}$ efficiently decides $L$ and there is no machine $M^{\ell_p}$ that efficiently decides $L$. For example, this could be a generalization of the question, is $NP \subseteq BQP$?.

(2) What about $p=\infty$? Here the maximum value of the components of the state vector is 1.

(3) These questions goes beyond unitarity so it is not expected to agree with quantum mechanics. In general, what happens with computation if you relax the unitarity restriction on operations? There are works about allowing non-linear operators (see Aaronson 2005).

(4) Maybe the most important, is it universal? I think this is clear, because for particular cases it is universal. But what happens with universality when $p=\infty$?

This is not a complete answer to the questions, but it is too long to write as a comment.  It expands my previous comment.

The question “What happens to computation if the axioms of quantum mechanics are modified a little?” is addressed in great detail by a fun paper [Aar04] by Scott Aaronson.  I believe that your questions are essentially answered in the first half of Section 2 of [Aar04].

Aaronson shows that if p>0 and p≠2, then a matrix which preserves the p-norm for all vectors is necessarily a generalized permutation matrix (a product of a permutation matrix and a diagonal matrix).  He states that the same holds in the case p=∞.  All these hold for both over ℝ and over ℂ.  Note that this includes the case of p=1: stochastic matrices preserve the 1-norm for nonnegative vectors but not for all vectors in general.

I guess that a probabilistic Turing machine generalized as in [For00] has a generalized permutation matrix as its global transition matrix only if it is a deterministic Turing machine, but I do not have a proof at hand.

Aaronson discusses also several other modifications of the axioms of quantum mechanics in the paper.  For example, if we change the rule of measurement (instead of the set of allowed gates) so that the outcome x occurs with probability |αx|p/∑y|αy|p, where αy is the amplitude of |y⟩, then this “quantum computer” can solve any problems in PP (including NP-complete problems) in polynomial time unless p=2 (Proposition 5).

References

[Aar04] Scott Aaronson.  Is quantum mechanics an island in theoryspace?  In Proceedings of the Växjö Conference “Quantum Theory: Reconsideration of Foundations,” 2004.  arXiv:quant-ph/0401062v2.

[For00] Lance Fortnow.  One complexity theorist’s view of quantum computing.  In Computing: the Australasian Theory Symposium (CATS 2000), pp. 58–72, Jan. 2000.  http://dx.doi.org/10.1016/S1571-0661(05)80330-5


Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation? The classical representations of the graph automorphism problem is Karp-reducible to the classical representation of the graph isomorphism problem. The sketch of proof for this can be written as follows based on the detailed proof given in Section 1.5 of The Graph Isomorphism Problem - Its Structural Complexity.

Prove that the graph automorphism problem is Turing-reducible to the graph isomorphism problem.
Prove that the graph automorphism problem has a polynomial time computable or-function.
Prove that the graph isomorphism problem has both polynomial time computable and- and or-functions.
Combining the previous results, it may be argued that the graph automorphism problem is Karp-reducible to the graph isomorphism problem.

My question is whether similar reduciblity can be inferred for the problems under hidden subgroup representations (HSP). Let me define those representations.

Graph isomorphism as a hidden subgroup problem

Let the $2 n$ vertex graph $\Gamma = \Gamma_1 \sqcup \Gamma_2$ be the disjoint union of the two graphs $\Gamma_1$ and $\Gamma_2$ such that $Aut \left(\Gamma_1\right) = Aut \left(\Gamma_2\right) = \left\{e\right\}$ (a limited version). A map $\varphi : S_{2n} \to \text{Mat}\left(\mathbb{C}, N \right)$ from the group $S_{2n}$ is said to have hidden subgroup structure if there exists a subgroup $H_\varphi$ of $S_{2n}$, called a hidden subgroup, an injection $\ell_\varphi : S_{2n}/H \to \text{Mat}\left(\mathbb{C}, N \right)$, called a hidden injection, such that the diagram

is a commutative diagram, where $S_{2n}/H_{\varphi}$ denotes the collection of right cosets of $H_\varphi$ in $S_{2n}$, and where $\nu : S_{2n}/H_\varphi$ is the natural map of $S_{2n}$ onto $S_{2n}/H_\varphi$. We refer to the group $S_{2n}$ as the ambient group and to the set $\text{Mat}\left(\mathbb{C}, N \right)$ as the target set.

The hidden subgroup version of the graph isomorphism problem is to determine a hidden subgroup $H$ of $S_{2n}$ with the promise that $H$ is either trivial or $|H| = 2$.

Graph automorphism as a hidden subgroup problem

For a graph $\Gamma$ with $n$ vertices, a map $\varphi : S_{n} \to \text{Mat}\left(\mathbb{C}, N \right)$ from the group $S_{n}$ is said to have hidden subgroup structure if there exists a subgroup $\text{Aut}\left(\Gamma\right)$ of $S_{n}$, called a hidden subgroup, an injection $\ell_\varphi : S_{n}/\text{Aut}\left(\Gamma\right) \to \text{Mat}\left(\mathbb{C}, N \right)$, called a hidden injection, such that for each $g \in \text{Aut}\left(\Gamma\right)$, $g \left(\Gamma\right) = \Gamma$ and, the diagram

is commutative, where $S_{n}/\text{Aut}\left(\Gamma\right)$ denotes the collection of right cosets of $\text{Aut}\left(\Gamma\right)$ in $S_{n}$, and where $\nu : S_{n}/\text{Aut}\left(\Gamma\right)$ is the natural map of $S_{n}$ onto $S_{n}/\text{Aut}\left(\Gamma\right)$. We refer to the group $S_{n}$ as the ambient group and to the set $\text{Mat}\left(\mathbb{C}, N \right)$ as the target set.

The hidden subgroup version of the graph automorphism problem is to determine a hidden subgroup $\text{Aut}\left(\Gamma\right)$ of $S_{n}$ with the promise that $\text{Aut}\left(\Gamma\right)$ is either of trivial or non-trivial order depending on the type of $\Gamma$.

My questions:

I think it can be trivially shown that the hidden subgroup representation of the graph automorphism problem is Turing-reducible to the graph isomorphism problem by giving two input graphs as the original graph and the candidate automorphism of the original graph.

If I am correct, the remaining question is whether there is a Karp-reduction for the hidden subgroup representation. If there is, how it can be shown.

I think your focus on the rigid case of GI limits you too much. Instead phrase (non-rigid) GI as an HSP in the same way, but now the goal is to determine the size of the hidden subgroup, or a generating set. The difference between the isomorphic and non-isomorphic cases will be a factor of 2 in the order of the hidden subgroup. If you phrase the problem as finding generators of the hidden subgroup, then the question is just whether any generator switches $\Gamma_1$ and $\Gamma_2$.

Now, an instance of "HSP-GA" corresponding to a graph $\Gamma$ is given by the function from $S_n \to M_n(\mathbb{C})$ defined by $f(\pi) = A(\pi(\Gamma))$ where $A(\cdot)$ denotes the adjacency matrix. In particular, $f(1) = A(\Gamma)$. Then apply the usual Karp reduction from GA to GI to get a pair of graphs $\Gamma_1, \Gamma_2$, and consider the HSP-GI instance, of the type described in the preceding paragraph, corresponding to the pair $\Gamma_1, \Gamma_2$ (that is, the disjoint union $\Gamma_1 \cup \Gamma_2$).


signature scheme without random oracles Suppose that we have an EU-CMA or sEU-CMA signature scheme without random oracles. My question is if messages to be signed are in the form H(m), where H is a hash function (doesn't belong to the signature parameters). Does this affect the security of the scheme?

EU-CMA: existentially unforgeable under chosen message attack.

sEU-CMA: Strongly EU-CMA.

See digital signature forgery for more info.

If the hash function is collision-resistant, it doesn't affect security.

Another way to put it: it affects security, in the sense that you are now reliant upon the security of the hash function to resist collisions.  But if it is infeasible to find collisions in the hash function, and if the underlying signature scheme is secure, then signing a hash of the message is also secure.


On $NP$ and $XP$ classes? On page 33 venn diagram in http://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf it is implied that $XP\subseteq NP$.
Below this there is a statement which says $XP\not = NP$ unless $P=NP$.

Is there a reference for proof for these two $XP$ statements?

On the first question:

First off, I do not think the statement $\mathsf{XP} \subseteq \mathsf{NP}$ is meant to be implied at that point. To explain what is meant, let me ask a question: What is the parameterized counterpart to $\mathsf{NP}$?

This question naturally arises when defining a notion of intractability of parameterized problems as classical intractabilty is thought to correspond with $\mathsf{NP}$-hardness. A first attempt yields $\mathsf{ParaNP}$, basically a nondeterministic $\mathsf{FPT}$, but a theorem states that if some parameterized problem $(L, \kappa)$ is $\mathsf{ParaNP}$-complete, then already a finite union of slices (the $k$th slice of $(L,\kappa)$ is the set of instances $x$ in $L$ of parameter $\kappa(x) = k$) is already $\mathsf{NP}$-complete and thus all the hardness is already exhibited by some parameter values. Conversely, it means that problems whose slices (for fixed $k$) are solvable in polynomial time are not $\mathsf{ParaNP}$-hard -- thus this class does not yield hardness results for problems like SAT (parameterized by the number of variables), $k$-Clique (parameterized by the size of the solutions) and many other problems which are believed not to be in $\mathsf{FPT}$.

Now, (uniform) $\mathsf{XP}$ deals exactly with this kind of problems whose slices are in $\mathsf{P}$, but the definition allows for very large running times if the parameters get large w.r.t. the input size and indeed, if we parameterize by the input length, we can use exponential time algorithms and as such, $\mathsf{XP}$ contains problems from $\mathsf{EXP}$ using some suitable parameterization, but not problems like $k$-Colorabilty parameterized by $k$.

So neither $\mathsf{ParaNP}$ nor $\mathsf{XP}$ are the class that we sought out to find and in this light, we can (sort of) understand that slide as an attempt to partition the landscape of $\mathsf{NP}$ problems and their parameterized versions into somewhat meaningful parameterized complexity classes (however, it suggests $\mathsf{XP} \subseteq \mathsf{ParaNP}$ which is not the case).

On the second question:

Arguably, one can interpret the statement $\mathsf{XP} = \mathsf{NP}$ to mean that "the class of unparameterized versions of the naturally parameterized problems in $\mathsf{XP}$ coincides with $\mathsf{NP}$" and since membership in $\mathsf{XP}$ means that the slices of a problem are in $\mathsf{P}$, we get that unless $\mathsf{P} = \mathsf{NP}$ there exist some problems in $\mathsf{NP}$ which are not in $\mathsf{XP}$ when using some parameterizations (like $k$-Colorability parameterized by $k$) and thus falsifying our interpretation of $\mathsf{XP} = \mathsf{NP}$.

This of course is a bit speculative, but given that one class is parameterized while the other is not together with the results we have seen, I have no better interpretation to give.

Sources:

M. Grohe, J. Flum: Parameterized Complexity Theory


Was the reduction in Shor's algorithm originally discovered by Shor? This is a "historical question" more than it is a research question, but was the classical reduction to order-finding in Shor's algorithm for factorization initially discovered by Peter Shor, or was it previously known?  Is there a paper that describes the reduction that pre-dates Shor, or is it simply a so-called "folk result?"  Or was it simply another breakthrough in the same paper?

I have to admit (surprising as it sounds) that I don't know really the answer. I either discovered or rediscovered this reduction myself.

I discovered the discrete log algorithm first, and the factoring algorithm second, so I knew from discrete log that periodicity was useful.  I knew that factoring was equivalent to finding two unequal numbers with equal squares (mod N) — this is the basis for the quadratic sieve algorithm. I had also seen the reduction of factoring to finding the Euler $\phi$ function, which is quite similar.

While I came up with the reduction of this question to order-finding, it's not hard, so I wouldn't be surprised if there was another paper describing this reduction that predates mine. However, I don't think this could be a widely known "folk result". Even if somebody had discovered it, before quantum computing why would anybody care about reducing factoring to the question of order-finding (provably exponential on a classical computer)?

EDIT: Note that order-finding is provably exponential only in an oracle setting; order finding modulo $N$ is equivalent to factoring $N$, and this had been proved earlier by Heather Woll, as the other answer points out.


Approximately sampling from convex polyhedrons with quantum computers Quantum computers are very good for sampling distributions that we don't know how to sample using classical computers. For example if $f$ is a Boolean function (from $\{-1,1\}^n$ to $\{-1,1\}$) that can be computed in polynomial time then with quantum computers we can efficiently sample according to the distribution described by the Fourier expansion of $f$. (We do not know how to do it with classical computers.)

  Can we use quantum computers to sample or approximately sample a random point  in a polyhedron described by a system of $n$ inequalities in $d$ variables?

Moving from the inequalities to the points looks to me somewhat similar to a "transform". Moreover, I would be happy to see a quantum algorithm even if you modify the distribution, e.g. consider product of Gaussian distribution described by the hyperplanes of the polyhedron or some other things.

A few remarks: Dyer, Frieze and Kannan found a famous classical polynomial time algorithm to approximately sample and approximately compute the volume of a polyhedron. The algorithm is based on random walks and rapid mixing. So we want to find a different quantum algorithm for the same purpose. (OK, we can hope that a quantum algorithm may lead also to things in this context we do not know to do classically. But to start, all we want is a different algorithm, this must be possible.)

Second, we don't even insist on approximately sampling the uniform distribution. We will be happy to approximately sample some other nice distribution which is roughly supported on our polyhedron. There is an argument by Santosh Vampala (and also by me in another context) leading from sampling to optimization: if you want to optimize $f(x)$ sample to find a point $y$ where $f(x)$ is typical. Add the constraint $\lbrace f(x) \ge f(y)\rbrace$ and repeat.

As the post acknowledges, the existence of a classical polynomial-time algorithm to estimate the volume of a convex polytope is a game-changer.  A quantum algorithm is much less likely to be interesting unless it is competitive with classical algorithms.   After all, without that criterion, any classical algorithm could simply be called a quantum algorithm instead.

That said, there is still room for a polynomial speed-up, and the main, known viewpoint for that type of speedup is a quantum walk, especially considering that the classical acceleration in this case is based on a good random walk.   (Indeed, any quantum algorithm can be viewed as a quantum walk, but for some algorithms this is not necessarily enlightening.)   Various papers in the QC literature have pointed out that the algorithms to estimate the volume of a convex polytope use random walks, and that there could be an acceleration from a quantum walk.  So, it appears that researchers know this suggestion, but that no one has tried to work out what polynomial acceleration you might get for this problem.   You might not get anything if the best classical algorithm has some sort of spoiler, such as a separate stage which is not a random walk with comparable running time.

Here is a collection of papers that all mention the basic idea in passing; again, Google Scholar seems to suggest that no one has gone further.

arXiv:quant-ph/0104137 - Quantum Walks on the Hypercube
arXiv:quant-ph/0205083 - Quantum random walks hit exponentially faster
arXiv:quant-ph/0301182 - Decoherence in Discrete quantum walks
arXiv:quant-ph/0304204 - Controlling discrete quantum walks: coins and intitial states
arXiv:quant-ph/0411065 - Quantum walk on a line with two entangled particles
arXiv:quant-ph/0504042 - Entanglement in coined quantum walks on regular graphs
arXiv:quant-ph/0609204 - Quantum speedup of classical mixing processes
arXiv:0804.4259 - Speed-up via quantum sampling
A random walk approach to quantum algorithms
Discrete quantum walk for solving nonlinear equations over finite fields

The other side of the classical algorithms to estimate the volume of a convex polytope is linear programming.   I don't know there has been any progress finding a quantum acceleration for that.  It seems difficult to avoid a stage of linear programming in order to put the convex polytope in a favorable position for sampling.


“Overflow” in Extended Euclidean Algorithm Sorry if I'm mistaken with the place to ask the question (maybe I should go to stackoverflow.com/mathoverflow.net?).

I wonder if there is a proof that when evaluating extended Euclidean algorithm the Bézout's coefficients (that is s and t in identity as + bt = gcd(a, b)) will not exceed some reasonable values (depending on a, b, I guess). In particular implementation on some general-purpose programming language I'm interested in overflow correctness of the program.

To be precise I can mention that I use Victor Shoup's description of the algorithm (4.2 in his book “A Computational Introduction to  Number Theory and Algebra” freely available from his homepage).

This is called the Bézout's identity/lemma (not to be confused with Bézout's theorem in algebraic geometry), which states:

  Lemma. For every integers $a,b \neq 0$, $\gcd(a,b) = ax + by$ for some integers $x,y$. Also, we may assume $|x| \leq |b|$ and $|y| \leq |a|$.

Proofs can be founded in standard algebra textbooks. Also you can prove it yourself by induction on the iterations of gcd process.

In general this is true in every Euclidean domain $R$ with a multiplicative Euclidean function $f$. In the case here when $R = \mathbf{Z}$, we have $f(x) = |x|$ which is multiplicative.


Limits to Parallel Computing I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject:

http://en.wikipedia.org/wiki/NC_%28complexity%29

The article contains the following sentence:

  It is unknown whether NC = P, but most
  researchers suspect this to be false,
  meaning that there are probably some
  tractable problems which are
  "inherently sequential" and cannot
  significantly be sped up by using
  parallelism

Does this sound reasonable? Are there known cases where a problem in P cannot be sped up using parallelism?

It is not even known whether NC = P, but P-complete problems seem to be inherently hard to parallelize.  These include Linear Programming and Horn-SAT.  (In contrast, problems in NC seem reasonably easy to parallelize.)

See question Problems between NC and P: How many have been resolved from this list? for reference material (including links to a classic textbook that is now available for free download), and further discussion about problems that are in P but not known to be parallelizable.

See question Generalized Ladner's Theorem for the structure of the complexity classes between NC and P.  Briefly, if they differ then there are infinitely many complexity classes strictly between NC and P.

See question NC = P consequences? for a nice demonstration by Ryan Williams that it is possible to amplify collapses in the hierarchy of complexity classes within P into perhaps more unlikely collapses like PSPACE = EXP.

It is worth pointing out that one consequence of Horn-SAT being P-complete, and the links above, is that it does not seem possible to parallelize general SQL queries in databases, unless we can also rewrite any large-scale computation to use only a reasonable amount of storage.  This is a puzzling discrepancy -- I think it is quite uncontroversial to state there are limits on compression, but I often see articles which seem built on the assumption that it is possible to parallelize any database query.


Length of a minimal DNF Boolean expression Consider an disjunctive normal form boolean expression on $n$ variables. What is the upper bound on the number of terms in a minimal equivalent DNF expression? That is, given an arbitrary DNF expression on $n$ variables, after eliminating redundant terms, what length is it guaranteed to be under (how many $\vee$'s)?

The answer is $2^{n-1}$.

To see that this is a lower bound consider the n variable parity function and observe that the unique (equivalent) DNF has $2^{n-1}$ clauses, none of which are resolvable.

To see that this is an upper bound, consider any DNF and the  full ordered decision tree for that DNF (i.e., tree where every leaf is at depth n and every path from the root to the leaf has all variables and in the same fixed order). Any two leafs which are siblings and which are both "true"  represent resolvable clauses in the full equivalent DNF. In this way one has at least has an equivalent clause-set of size at most $2^{n-1}$ by taking for every node at level n-1 either the DNF clause given by the only true leaf child of that node (if it has one true child) or the resolvent of the two clauses corresponding to its two children (if it has two true children). That is we have at most one clause for each node at this level in the tree, I.e., $2^{n-1}$.


Sensitivity of Graph Properties In [1], Turan shows that the sensitivity (called "critical complexity" in the paper) of a graph property is strictly greater than $\lfloor {1\over 4} m \rfloor$ where $m$ is the number of vertices in the graph. He goes on to conjecture that any non-trivial graph property has sensitivity $\geq m-1$. He mentions that this has been verified for $m \leq 5$. Has any progress been made on this conjecture?

Background

Let $x$ be a binary string in $\{0,1\}^n$. Define $x^i$ for $1 \leq i \leq n$ to be the string obtained from $x$ by flipping the $i^{th}$ bit. For a boolean function $f: \{0,1\}^n$ \to $\{0,1\}$, define the sensitivity of $f$ at $x$ as $s(f;x) := |\{i : f(x) \neq f(x^i) \}|$. Finally, define the sensitivity of $f$ as $s(f) := \mbox{max}_x\; s(f;x)$.

A graph property $\mathcal P$ is a collection graphs such that if $G \in \mathcal P$ and $G'$ is isomorphic to $G$ then $G' \in \mathcal P$. We can think of a graph property $\mathcal P$ as the union of properties $\mathcal P_m$ where $\mathcal P_m$ is the subset of $\mathcal P$ consisting of graphs with $m$ vertices. Further, we can conceive of a graph property $\mathcal P_m$ as a boolean function on $\{0,1\}^n$ where $n = {m \choose 2}$. We can encode a graph on $m$ vertices in a binary vector of length $n$; each entry in the vector corresponds to a pair of vertices and the entry is $1$ iff that edge is present in the graph. Thus, the sensitivity of a graph property is its sensitivity qua boolean function.

Turan, G., The critical complexity of graph properties, Information Processing Letters 18 (1984), 151-153.

The survey that Suresh pointed to brings up a paper by Wegener [1] that partially confirms the conjecture. It holds for all monotone graph properties and the inequality is tight (consider the property "Has no isolated vertices"). Any more recent results would be appreciated as well.

Wegener, L. The critical complexity of all (monotone) Boolean functions and monotone graph properties. Information and Control, 67:212-222, 1985.


Amortized Analysis - Potential Method I read about Potential Method when I was trying to understand some calculations.

I just can't understand how do you perform the calculation it self. How can you even define $O(n)-O(n)$ as it is used in the Wikipedia page? I just don't understand where is the calculation done.

Is there any good and simple example of this kind of analysis?

Shay

http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/15-amortize.pdf specifically for amortization, and http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/ generally


Nearly Optimal Sparse Walsh-Fourier Tranform In the recent paper: Nearly Optimal Sparse Fourier Transform[Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price], the authors show an $O(k \log n)$-time algorithm for the problem of computing the discrete Fourier transform of an $n$-dimensional signal that has at most $k$ non-zero Fourier coefficients.

Is there a similar result for the Walsh-Fourier transform (or is it possible to use the same algorithm for a multidimensional DFT of size $2^n$) ?

As the quoted paper itself summarizes in its introduction,

  The past two decades have witnessed significant advances in sublinear sparse Fourier algorithms. The first such algorithm (for the Hadamard transform)

(which is what you are looking for)

  appeared in KM91 (building on GL89). Since then, several sublinear sparse Fourier algorithms for complex inputs were discovered [Man92, GGI+02, AGS03, GMS05, Iwe10, Aka10, HIKP12].

Some of the quoted papers (e.g. Aka10) give similar results for Fourier transforms over all Abelian groups.


Berman-Hartmanis Isomorphism for NP$_{\mathbb{R}}$? Using the real-RAM/BSS model, we have the class NP$_{\mathbb{R}}$,   (where a BSS is the Blum-Shub-Smale model of a computer with operations over reals). We have NP$_{\mathbb{R}}$ complete problems. So, the question is
is there an analog of the Berman Hartmanis conjecture for the class NP$_{\mathbb{R}}$? Of course, the question posed here is dependent on the model - in other words, as the definition of NP$_\mathbb{R}$ uses the BSS model, do all of NP$_{\mathbb{R}}$-complete problems have the same structure using the BSS model(this approximates the Berman-Hartmanis conjecture for NP over reals)?

Depending on which version of $\mathsf{NP}_{\mathbb{R}}$ you use, yes or it's open. When one considers BSS machines that only use addition and subtaction, and only branch on equality, the answer is yes. If one includes branching on $<$, I believe it is still open, and the same if one allows multiplications. For details, see Cucker, Koiran, and Matamala "Complexity and dimension," Inform. Proc. Lett. 1997


Complexity of hex with random turn order. I've been thinking of a variant of hex, where instead of the two players making moves alternately, each turn a player picked at random makes a move. How hard is it to determine the chances for each player winning? This problem is obviously in PSPACE, but can't it to be NP-hard, much less PSPACE-complete. The difficulties come from how the randomness makes it impossible for a player to be forced into making a choice among options; if that player is lucky he gets enough moves two take both options, and if the player is unlucky the opponent gets enough moves to block both options. On the other hand, I can't think of any polynomial-time algorithms for this.

You might want to look at the paper "Random-Turn Hex and Other Selection Games," by Yuval Peres, Oded Schramm, Scott Sheffield, and David Wilson. From the introduction:

  "Random-Turn Hex is the same as
  ordinary Hex, except that instead of
  alternating turns, players toss a coin
  before each turn to decide who gets to
  place the next stone. Although
  ordinary Hex is famously difficult to
  analyze, the optimal strategy for
  Random-Turn Hex turns out to be very
  simple."

So indeed, your intuition was right: this will be in BPP (or maybe P).


What are the equational laws for zero types? Disclaimer: while I care about type theory, I don't consider myself an expert on type theory.

In the simply typed lambda calculus, the zero type has no constructors and a unique eliminator:

$$\frac{\Gamma \vdash M \colon 0}{\Gamma \vdash initial (M) \colon A}$$

From a denotational point of view, the equation
$initial (M_1) = initial(M_2)$ is obvious (when the types make sense).

However, from that perspective I can also deduce that, when $M,M' \colon 0$, then : $M = M'$. This deduction seems stronger, although a particular model that shows it eludes me.

(I have some proof-theoretic intuition though: it doesn't matter which contradiction you use to obtain an inhabitant, but there might be different contradiction proofs.)

So my questions are:

What are the standard equational laws for zero types?
Are any of them classified as $\eta$ or $\beta$ laws?

The standard equational rules for the empty type is, as you surmise, $\Gamma \vdash e = e' : 0$. Think of the standard set-theoretic model, where sets are interpreted by types: sum types are disjoint unions, and the empty type is the empty set. So any two functions $e,e' : \Gamma \to 0$ must also be equal, since they have a common graph (namely, the empty graph). .
The empty type has no $\beta$ rules, since there are no introduction forms for it. Its only equational rule is an $\eta$-rule. However, depending on how strictly you wish to interpret what an eta-rule is, you may wish break this down into an $\eta$ plus a commuting conversion. The strict $\eta$-rule is:

$$e = \mathrm{initial}(e)$$

The commuting coversion is:

$$C[\mathrm{initial}(e)] = \mathrm{initial}(e)$$

EDIT:

Here's why distributivity at the zero type implies the equality of all maps $A \to 0$.

To fix notation, let's write $!_A : 0 \to A$ to be the unique map from $0$ to $A$, and let's
write $e : A \to 0$ to be some map from $A$ to $0$.

Now, the distributivity condition says that there's an isomorphism $i : 0 \simeq A \times 0$.
Since initial objects are unique up to isomorphism, this means that $A \times 0$ is itself a
initial object. We can now use this to show that $A$ itself is an initial object.

Since $A \times 0$ is an initial object, we know the maps $\pi_1 : A
\times 0 \to A$ and $!_A \circ \pi_2$ are equal.

Now, to show that $A$ is an initial object, we need to show an
isomorphism between it and $0$.  Let's choose $e : A \to 0$ and $!_A :
0 \to A$ as the components of the isomorphism.  We want to show that
$e \circ !_A = id_0$ and $!_A \circ e = id_A$.

Showing that $e \circ !_A = id_0$ is immediate, since there is only
one map of type $0 \to 0$, and we know that there is always an
identity map.

To show the other direction, note
$$
\begin{array}{lcll}
  id_A & = & \pi_1 \circ (id_A, e) & \mbox{Product equations} \\
       & = & !_A \circ \pi_2 \circ (id_A, e) & \mbox{Since $A\times 0$ is initial} \\
       & = & !_A \circ e & \mbox{Product equations}
\end{array}
$$

Hence we have an isomorphism $A \simeq 0$, and so $A$ is an initial object. Therefore maps $A \to 0$ are unique, and so if you have $e,e' : A \to 0$, then $e = e'$.

EDIT 2: It turns out the situation is prettier than I originally thought. I learned from Ulrich Bucholz that it's obvious (in the mathematical sense of "retrospectively obvious") that every biCCC is distributive. $\newcommand{\Hom}{\mathrm{Hom}}$ Here's a cute little proof:

$$
\begin{array}{lcl}
   \Hom((A + B) \times C, (A + B) \times C)
   & \simeq & \Hom((A + B) \times C, (A + B) \times C) \\
   & \simeq & \Hom((A + B), C \to (A + B) \times C) \\
   & \simeq & \Hom(A , C \to (A + B) \times C) \times \Hom(B, C \to (A + B) \times C) \\
   & \simeq & \Hom(A \times C, (A + B) \times C) \times \Hom(B \times C, (A + B) \times C) \\
   & \simeq & \Hom((A \times C) + (B \times C), (A + B) \times C)
\end{array}
$$


MIP with efficient provers It is well-known that the set of languages having two-prover interactive proof systems, in which the verifier runs in polynomial-time (MIP), is NEXP. But are there bounds known on the power of such interactive proofs when the provers are restricted in power? E.g., what is the class of languages that admit two-prover interactive proofs with polynomial-time provers?

More precisely, let's say that on an input x I allow the provers arbitrary pre-computation time, but once the interaction with the verifier starts they are restricted to using polynomial space (including storing the results of any pre-computation), and polynomial time to compute their answers to the verifier's question. Let's also assume that these space and time bounds are a fixed polynomial in the length of the questions that will be sent by the verifier (instead of the length of x), in order to preclude a more trivial solution in which the verifier would somehow exhaust the prover's space bound by asking polynomially more questions.

Clearly, this is enough for NP. What about PSPACE? If there was only the space bound they could do it, but what with the time bound? Are there any interesting results in that direction?

I am also interested in other limitations that one might consider on the provers. One of those would be the amount of communication prover->verifier, which I think has been thoroughly studied in the context of PCPs. What are the other interesting constraints?

It sounds like this class would be exactly MA.  The witness could be the results of pre-processing (which is of polynomial size).  The probabilistic verification procedure would then be to simulate the protocol, including the multiple provers (who are polynomial-time given the results of pre-processing).

Russell Impagliazzo


Partial cover approximation We have a set of elements $E=\{e_1, e_2, \ldots, e_m\}$, and $n$ subsets of $E$: $S_1, S_2, \ldots, S_n$ The union of those subsets is $E$, and each subset $S_i$ has a non-negative weight $w_i$.

The standard set cover problem is to find set of $S_i$'s whose union is $E$ and whose total weight is the smallest possible.

In the partial cover variation of this problem, we are given a $p \in (0,1)$ and are asked to find a minimum total cost set of $S_i$'s whose union has at least $p|E|$ elements.That is, find and index set $I \subseteq \{1,\ldots,n\}$ such that $|\bigcup_{i \in I}S_i| \geq p|E| $ and this is the cheapest set of $S_i$'s which have this property.

Give a polynomial time algorithm which finds a set of $S_i$'s whose union has at least $p|E|$ elements and whose total cost is at most $c(p)OPT$ where $OPT$ is the optimal cost of the set cover problem and $c(p)$ is a constant that depends on $p$.

My initial thought was that you could solve the relaxed version of the set cover problem, and do a rounding of the variables, where you round a variable $x_i$ (being associated with set $S_i$) to $1$ if $x_i \geq 1-p$, and otherwise round it down. This means the cost will be multiplied by a factor of no more than $1/(1-p)$.

The problem with this is that an element may be in many sets $S_i$ and so it may be the case that no $x_i > 1-p$ for the constraint corresponding to this element.

Having discussed with other users, I believe the following answers the question.

To begin with let us recap the greedy algorithm for the set cover problem, in which we wish to cover all of $E$ as cheaply as possible. At each step, the algorithm adds the set $S_i$ for which $\frac{w_i}{|\hat{S}_i|}$ is lowest, where $\hat{S}_i$ is the subset of $S_i$ which has yet to be covered. It can be shown that this minimum is upper bounded by $\frac{OPT}{Z}$ where $OPT$ is the optimal weight for the (full) set cover problem and $Z$ is the number of elements not yet covered. From this, one can show a a total weight bounded by $H_{|E|} \approx \log |E|$.

However, if one were to stop the algorithm as soon as $p|E|$ elements were covered, then we would get the bound  $\approx \log \frac{1}{1-p}$, as per @SashoNikolov's comment.

We can get a $H_{p|E|}$ approximation for the partial set problem by modifying the greedy algorithm as follows: At each iteration, choose the $S_i$ which minimizes $\frac{w_i}{\min(|\hat{S}_i|, Z)}$ where $Z$ is the number of elements we still need to get to complete $p|E|$ elements. Now we can guaranteed that there is an $S_i$ for which the above is bounded by $OPT/Z$ (where now $OPT$ is the optimal for the partial set cover). To see this, suppose an optimal solution is the collection of sets $S_1=\{xx|...\}$ $S_2=\{xxx|...\}$, $S_3=\{xxx|......\}$. In this notation, the $x$ represents an already covered element, and after the $|$ are elements which are not covered. Let $a_1, a_2, a_3$ denote the number of such uncovered elements and suppose $a_1, a_2, a_3\leq Z$. Then
$$min \{\frac{w_1}{a_1}, \frac{w_2}{a_2}, \frac{w_3}{a_3}\}\leq \frac{w_1+w_2+w_3}{a_1+a_2+a_3}  = \frac{OPT}{a_1+a_2+a_3} \leq \frac{OPT}{Z}.$$

Of course, if any of the $a_i$'s is larger than $Z$ then it is replaced by $Z$ in the above inequalities and they hold.

The starting $Z$ is $Z_0=p|E|$, and a similar analysis as for the full set cover leads to a total weight bounded by $OPT \cdot H_{Z_0}$.


Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs Suppose I have a DAG, $G = (V, E)$ and we know that all nodes in the DAG have at most $A$ ancestors. Let $V' \subseteq V$ be a subset of vertices of $V$. Is there a way to obtain the set of all ancestors of every vertex in $V'$ in $O(|V'|A + m)$ time? In other words, I want sets $B_i$ consisting of all ancestors of $v_i \in V'$ for all $v_i$.
The trivial algorithm does this in $O(|V'|A^2)$ time (for very dense graphs) but I would like to do this in $O(|V'|A + m)$ time or even better $O(|V'|A + E(V', B(V')))$. (Here $E(V', B(V'))$ indicates time proportional to the induced subgraph consisting of $V'$ and all ancestors of vertices in $V'$.)
If we cannot do this, are there any known lower bounds for this runtime?

We can reduce Boolean matrix multiplication to this problem by a three level construction, where the edges from the first level to the second level are determined by the first matrix and the edges from the second level to the third level are determined by the second matrix, and we query with $V'$ equal to the first level.
This reduction for $n \times n$ matrix produces an instance with $|V'| = n$, $A = O(n)$, and $m = O(n^2)$, so an $O(|V'|A + m)$ time algorithm would imply an $O(n^2)$ time algorithm for Boolean matrix multiplication. While I don't think that this has been conjectured to be impossible, it would be a breakthrough result: Best algorithms for Boolean matrix multiplication have the same time complexity as general matrix multiplication, and no "combinatorial" algorithms with $O(n^{3-\epsilon})$ time complexity are known. (see e.g. the intro of [1] for references).
An algorithm with time complexity $O(|V|^\omega \log(|V|))$, where $2 \le \omega < 2.373$ is the matrix multiplication exponent can be given by computing the transitive closure of the DAG with matrix multiplication.
[1] https://acris.aalto.fi/ws/portalfiles/portal/40881045/1.9781611975482.31.pdf