Citation showing minors are topological minors for subcubic graphs If $G$ is a graph with maximum degree 3 and is a minor of $H$, then $G$ is a topological minor of $H$.

Wikipedia cites this result from Diestel's "Graph Theory". It's listed as Prop 1.7.4 in the latest version of the book. The book lacks proof or citation.

Are the whereabouts known for an (original) proof of this?

Furthermore, is there a reference proving that if $G$ is a path or a subdivision of a claw and is a minor of $H$ then $G$ is a subgraph of $H$? It's mentioned here briefly but lacks reference.

If $G$ is a graph with maximum degree 3 and is a minor of $H$, then $G$ is a topological minor of $H$.

Since $G$ is a minor of $H$, $G$ can be obtained from $H$ by deleting edges, isolated vertices and performing edge contractions. It's also easy to show that we can insist that the subgraph operations are done first, i.e., we can first perform all the edge and vertex deletions and then perform all the edge contractions. Moreover, let us restrict the definition of "edge contraction" to disallow contracting edges where one of the vertices has degree 1. Contracting such an edge is the same as deleting it, so this will not change the definition of graph minors.

Let $H'$ be the graph obtained from $H$ by performing all the edge/vertex deletions first. $H'$ still contains $G$ as a minor. If we show that $H'$ contains $G$ as a topological minor then we're done, since the definition of topological minor also allows edge/vertex deletions.

Since $G$ can be obtained from $H'$ by edge contraction only, $H'$ and all intermediate graphs must have maximum degree 3 since there is no way to decrease the maximum degree of a graph by performing an edge contraction. (This would have been possible if we had allowed the contraction of edges incident on a vertex of degree 1.)

So consider any step in the conversion of $H'$ to $G$. The only types of edges we can contract are those with both degree-2 vertices or one degree-2 vertex and one degree-3 vertex. (All other combinations don't work. For example, edges with two degree-3 vertices will give rise to a vertex of degree 4 when contracted.)

And now we're done, since if $H_1$ is obtained from $H_2$ by contracting an edge with two degree-2 vertices, then $H_2$ can be obtained from $H_1$ by performing edge subdivision on that edge. Similarly for an edge with one degree-3 vertex and one degree-2 vertex. Thus $H'$ can be obtained from $G$ by performing edge subdivisions only, which means $G$ is a topological minor of $H'$ and thus $H$.

  If $G$ is a path or a subdivision of a claw and is a minor of $H$ then $G$ is a subgraph of $H$

This is easy to show once we have the previous result. Since paths and subdivisions of claws have maximum degree 3, if $G$ is a minor of $H$ it is also a topological minor of $H$. This means there is a subgraph of $H$ that can be obtained from $G$ by only performing edge subdivisions. Now it's easy to show by induction that every edge subdivision of a path or subdivision of a claw leads to a graph which contains the original as a subgraph. For example, subdividing a path of length k leads to a path of length k+1, which contains the path of length k as a subgraph. Similarly for subdivisions of a claw.

We also needed this result for a paper once, so we included a short proof in our paper. You can find the result in Quantum query complexity of minor-closed graph properties. It's mentioned on page 13. However, this fact is hidden away in the proof of something else and isn't stated explicitly as a theorem.

What's also interesting is that there is a converse to this theorem:

  The only graphs $G$ for which containing $G$ as a minor is equivalent to containing $G$ as a subgraph are those in which each connected component is a path or a subdivision of a claw.


Does this game terminate? Consider the following card game (known in Italy as "Cavacamicia," which may be translated as "stripshirt"):

Two players randomly split in two decks a standard deck of cards.  Each player gets one deck.

The players alternate placing down in a stack the next card from their deck.

If a player (A) places down a special card, i.e. a I, II, or III, the other player (B) has to place down consecutively the corresponding number of cards.

If in doing so B places down a special card, the action reverses, and so on; otherwise, if B places down the corresponding number of cards but no special card, A collects all the cards that were put down and adds them to their deck.  A then restarts the game by placing down a card.

The first player to run out of cards loses the game.

Note: The outcome of the game depends exclusively on the initial partition of the deck.  (Which may make this game look a bit pointless ;-)

Question: Does this game always terminate? What if we generalize this game and give any two sequences of cards to each player?

Regarding Beggar-My-Neighbour

Paulhus (1, p.164) wrote in 1999:

  If $C$ is a full deck of cards, does ${D_{2}}^{'}(C)$ have a cycle? We
  leave  this question unanswered except to say that we have been unable
  to find one in
  3.2 billion randomly chosen deals.

But Conway et al. (2, p.892) wrote in 2006:

  Strip-Jack-Naked, or Beggar-My-Neighbour **1

  Another problem that took almost 47 years to solve concerns this old
  children’s game. Each of the two players starts with about half of the
  cards  (held face-down), which they alternately turn over onto a
  face-upwards “stack”  on the table, until one of them (who's now “the
  commander”) first deals one of  the “commanding cards” (Jack, Queen,
  King, or Ace).

  After one of these has been dealt, the other player (now “the
  responder”) turns  over cards continuously until EITHER. **2 a new
  commanding card appears (when  the players change roles **3) or
  respectively 1, 2, 3, or 4 non-commanding cards  have been turned
  over. In the latter case, the commander turns over the stack  and
  ajoins it to the bottom of his hand. The responder then starts the
  formation  of a new stack by turning over his next card, and play
  continues as before.

  A player who acquires all the cards is the winner and in real games,
  it seems  that someone always does win. The interesting mathematical
  question, posed by  one of us many years ago, was “is it really true
  that the game always ends?”  Marc Paulhus has recently found the
  answer to be “no!”. About 1 in 150,000 games  (played with the usual
  52 cards) goes on forever.

  We are fairly confident that no one person has played the game
  anything like  that number of times, so the chance (with random
  shuffling) of experiencing a  non-terminating game in a lifetime’s
  play must be very small indeed.

  Just as surely, however, the total number of times this game has been
  played by  the World’s **4 children must be significantly larger than
  150,000, so many of  them will have been theoretically non-terminating
  ones. We imagine, though, that  in practice most of them actually did
  terminate because someone made a mistake.

Unfortunately I was not able to found in (2) any reference to the discovery of Paulhus... I would love to see a sequence of cards that gives a non-terminating game in order to say that the problem is solved.

In 2013, Lakshtanov and Aleksenko (3) wrote:

  For card games of the Beggar-My-Neighbor type, we prove finiteness of
  the mathematical expectation of the game duration under the conditions
  that a player to play the first card is chosen randomly and that cards
  in a pile are shuffled before being placed to the deck. The result is
  also valid for general-type modifications of the game rules. In other
  words, we show that the graph of the Markov chain for the
  Beggar-My-Neighbor game is absorbing; i.e., from any vertex there is
  at least one path leading to the end of the game.

but their rules are not the ones I followed when I played the game when I was a child ;-)

To the best of my knowledge the longest Beggar-my-Neighbour game was found in 2014 by William Rucklidge with 7960 cards:

1: -J------Q------AAA-----QQ-
2: K----JA-----------KQ-K-JJK

Regarding Cavacamicia

I usually played it with a 40 cards deck, simulations with an half deck (only 20 cards) gives 16 non terminating games on a total of 3.448.400 games.

Bibliography

(1)
PAULHUS, Marc M. Beggar my neighbour. American Mathematical Monthly, 1999, 162-165.
http://www.jstor.org/stable/2589054

(2)
BERLEKAMP, Elwyn R.; CONWAY, John H.; GUY, Richard K. Winning Ways for Your Mathematical Plays, Volume 4. AMC, 2003, 10: 12.
http://www.maa.org/publications/maa-reviews/winning-ways-for-your-mathematical-plays-volume-4

(3)
LAKSHTANOV, Evgenii Leonidovich; ALEKSENKO, Alena Il'inichna. Finiteness in the Beggar-My-Neighbor card game. Problems of Information Transmission, 2013, 49.2: 163-166.
http://dx.doi.org/10.1134/S0032946013020051


Is DNF-Equivalence Problem $\mathsf{NP\mbox{-Hard}}$? I have the following Equivalent DNF problem:

Input:Two DNF formulas, $F_1$ and $F_2$,with variables $a_1,a_2,...a_n.$

Output: $1$ if $F_1$ and $F_2$ are equivalent, $0$ otherwise.

$F_1$ and $F_2$ are equivalent if for all $(a_1,a_2,...a_n)∈\{0,1\}^n,F_1(a_1,a_2,...a_n)= F_2(a_1,a_2,...a_n).$

Is the DNF-Equivalence problem polynomial or in $\mathsf{NP\mbox{-Hard}}$? If in $P$, how do we find an efficient algorithm and determine its complexity. How do we prove it if it's $\mathsf{NP\mbox{-Hard}}$.

A special case of DNF equivalence is DNF tautology: Given a DNF formula $F$, is it satisfied for all assignments? This can be seen by setting $F_1 = F$ and $F_2$ to be a trivial tautology. CNF non-satisfiability is co-NP-complete. Negating the input formula turns a CNF formula into a DNF formula and vice versa and non-satisfiability into tautology. Thus, DNF tautology is co-NP-complete.


How to compute K and n? [Item-based Collaborative Filtering] I'm currently studying this item-based collaborative filtering algorithm on this thesis that I've researched and I've formulated the algorithm below based on it. I have no problem on steps 1 to 3 but in step 4 it says there: Set the threshold value n.
How can I determine the value of n? Is there a formula for getting the value of it? I already checked it out but there's nothing there.
And also in Step 5: Select the K most similar products in M. The same question, how can I compute the value of K?

  Retrieve all the item rated by an active user and put it to Q.
  Isolate the users who have rated both the target item (i) and the items rated by the active user in Q, get the item and put it in R.
  (co-rated items)
  Calculate the item similarities using the Pearson Correlation Coefficient with all the  items (j) in R.
  Set the threshold value n, If the similarity of i and j is greater or equal to n, (sim(i,j) >= n),  Then include it in M.
  Select the K most similar products in M.
  Take the weighted average of the users rating on these similar items K.

My guess is that these are free parameters of the algorithm that you must set somehow.  For instance, you might evaluate different choices of these parameters on a set of training data to see which performs the best.  You could also use cross-validation or other techniques to evaluate different settings of these parameters.

Note that p.46 of the thesis says "This threshold value is based on the predicted ratings that are achieved after running the item-based collaborative filtering algorithm."  That sounds consistent with my interpretation above.

In general, I would recommend reading the original, published, peer-reviewed research papers on algorithms for this problem.  I would expect them to generally be of relatively high quality, and to be more likely to explain the algorithm and methodology in full (or cite a source that does).


Max-weight connected subgraph problem in planar graphs The maximum-weight connected subgraph problem is as follows:

Input: a graph $G=(V,E)$ and a weight $w_i$ (possibly negative) for each vertex $i \in V$.
Output: a maximum-weight subset $S$ of vertices such that $G[S]$ is connected.

This problem is NP-hard. David S. Johnson mentions on pg. 149 of this column that the problem remains hard in planar graphs of maximum degree three with all weights either $+1$ or $-1$.
I cannot find the cited paper --  A. Vergis, manuscript (1983)
Any ideas as to where to find the paper? Or what the reduction was?

In the "The NP-Completeness Column: An Ongoing Guide" number 14, Johnson writes "... Vergis [49]. Transformation from STEINER TREE IN GRAPHS [ND12]...". I don't have access to the Vergis' paper, however a possible reduction can be the following.

Steiner Tree (ST) in graphs problem

Instance: an undirected graph $G = (V,E)$, a subset of the vertices $R \subseteq V$, called terminal nodes; a non-negative integer $k$

Question: is there a subtree of $G$ that includes all the vertices of $R$ (a spanning tree for $R$) and that contains at most $k$ edges?

The problem remains NPC even for planar graphs (M. Garey and D. Johnson. The rectilinear Steiner tree problem is NP-complete).

Given an instance of planar ST, for now suppose that you can assign arbitrary weights to nodes. If $|R|=p$ and $|E|=q$ , you can assign weight $q+1$ to the nodes of $R$ and you can add a middle node to every edge of $E$ and assign weight $-1$ to it. Assign weight $0$ to the remaining nodes in $V \setminus R$. The original graph $G$ has a spanning tree for $R$ with at most $k$ edges if and only if in the transformed graph you can find a subgraph of target weight greater or equal to $W = p(q+1) - k$.

Informally to reach the $p(q+1)$ quantity you must include all the nodes of $R$ in the subgraph, and you must include at most $k$ middle nodes (corresponding to the edges of $G$) that have negative weight -1 to keep them connected.

You can reduce the the max degree of the whole graph to three in this way: if $D = \max\{deg(u_i) \mid u_i \in V\}$ just transform each node $u_i$ to a circular chain of $D$ nodes (and adjust the value of $p$ accordingly). Connect the inbound edges to distinct nodes of the chain (that will have degree 3).

And if you want to use only weights $+1,-1$ then you must:(A) assign $+1$ to all the nodes of the circular chains corresponding to nodes in $V\setminus R$,(B) transform every middle node to a linear chain of nodes of weight $-1$ and length $l_E = |V\setminus R|+1$, and(C) further expand the circular chains (with weight +1) corresponding to the nodes of $R$ to at least length $l_R = l_E( |E| + 1)$; and set target weight $W =pl_R - kl_E$.
Informally, the expanded chains and the new target make the $+1$ weights of the nodes corresponding to $V \setminus R$ (point A) irrelevant.


Weird claim of graphclasses about complexity of domination EDIT this got 'fixed' on graphclasses, as per answers/comments, so you might not reproduce it, unless you have their earlier database, which is publicly available via sage - http://sagemath.org.

Likely this is technical error in graphclasses or in me.

Appears to me graphclasses claims P=NP.

In Domination perfect
we have $\gamma(G)=i(G)$ which implies the complexity of Dominating Set
 (DS) and Independent Dominating Set (IDS) is the same in subclasses of
domination perfect.

In line graphs
we have DS NP-complete and IDS Polynomial.

According to the java application of graphclasses, line graphs
are domination perfect, one of the reasons is they are claw-free.

Appears to me this implies P=NP.

  What is wrong?

Screenshot:

Answering vb le question about polynomial IDS on line.

Clicking details recursively, we get: Polynomial on claw-free
and the claim without reference on claw-free:

  Polynomial On domination perfect graphs, the Independent set and Independent domininating set problems are equivalent.

The culprit is the claim that Weighted-IDS is polynomial on claw-free graphs, because the independent set problem is and for domination perfect graphs, IDS is equivalent to IS. But for domination perfect graphs, IDS is not equivalent to IS, but to dominating set. So the statement should be: IDS is NPC on line graphs, because domination is.


Can we prove weak normalization for System F by induction on a transfinite ordinal Weak normalization for the simple typed lambda calculus can be proved (Turing) by induction on $\omega^2$. An extended lambda calculus with recursors on natural numbers (Gentzen) has a weak normalization strategy by induction on $\epsilon_0$.

What about System F (or weaker)? Is there a weak normalization proof in this style? If not, can it be done at all?

In a very silly way, weak normalization for any reasonable system can be proved by induction on a constructive ordinal, provided of course that weak normalization holds. Indeed, the statement that System F has weak normalization is formalizable in arithmetic as a $\Pi^0_2$ sentence, and as such is provable (since it's true) by transfinite induction along a non-natural constructive ordinal-notation of height $\omega^2$. (See this question on the mathematics stack exchange for how this ordering could work.)

However, as jbapple mentions, we don't know of a "natural" ordinal notation that works. We don't even know how to define "natural", but the one above isn't natural (since to see that it's well-founded we'd have to know weak normalization of System F to begin with), whereas the standard ones for $\varepsilon_0$, $\Gamma_0$, and various larger ones using ideas from large cardinal axioms, are natural.

Hopefully one day someone will come up with an ordinal notation for second order arithmetic that everyone will agree is natural, and then that could be used in an honest way to prove weak normalization for System F.


Maximum Crossing number of topological graph The crossing number of a graph $G$ is defined as the least number of crossings introduced when $G$ is drawn as a topological graph in the plane.

Is there anything known about the maximum number of crossings which can be introduced by drawing $G$ as a topological graph in the plane?

As Vinicius Santos has already said, this doesn't make sense without further restrictions (you can make any single edge cross itself as many times as you like). But a well-studied variant of this arises if you only allow each pair of edges to cross at most once, and not at all if they share an endpoint. Then, the graph drawings in which every possible crossing exists are called thrackles, and it's a longstanding open problem to characterize them.


Difference between self-information and entropy I get a bit confused about different definitions of entropy and/or self-information.

Entropy?

$$ H(X) = - \sum_{x \in X} P_X(x) \cdot \log{\left(P_X(x)\right)} $$

Self-information?

$$ I(x) = - \log{P_X(x)} $$
$$ I(X) = - \sum_{x \in X} \log{\left(P_X(x)\right)} $$

When do I use which formulate to calculate what? Generally, I am interested in the average information content of a text. Here I would calculate the frequency of each word, the probability, sum up the negative logarithm of this probability and average it by the number of words.

What am I missing here?

The entropy refers to a set of symbols (a text in your case, or the set of words in a language). The self-information refers to a symbol in a set (a word in your case).

The information content of a text depends on how common the words in the text are wrt the global usage of those words.

E.g. "Next saturday morning" should have less self-information (as a named entity) than "Large Hadron Collider", each of the words should have less self information (except for large, maybe). However the entropy may be higher in the first case, there are not many Large Hadron "things".

Maybe Markov chains or some model that is better suited for probability in natural language would give you better (more significant and useful) results.


Parallel Pebble Game on a Line In the pebble game on a line there are N+1 nodes labelled 0 through N. The game starts with a pebble on node 0. If there is a pebble on node i, you can add or remove a pebble from node i+1. The goal is to place a pebble on node N, without placing many pebbles on the board at the same time and without taking too many steps.

The naive solution is to place a pebble on 1, then 2, then 3, and so forth. This is optimal in terms of the number of steps. It's not optimal in the maximum number of pebbles on the board at the same time: during the last step there are N pebbles on the board (not counting the one on 0).

A strategy that places fewer pebbles on the board at the same time is in this paper. They reach node N without exceeding $\Theta(\lg N)$ pebbles at a time, but at the cost of increasing the number of steps to $\Theta(n^{\lg_2 3})$. They toggle whether there's a pebble at position $N$ without leaving any other pebbles around by recursively toggling $N/2$, using that as a starting point to toggle $N$ with another recursive step, then toggling $N/2$ with a third half-sized recursive step to clear it.

I'm interested in the tradeoff between the maximum number of pebbles and the number of steps, under the assumption that pebble additions and removals can be done in parallel. By "parallel" I mean that each step can add or remove as many pebbles as desired, as long as each individual addition/removal is allowed and doesn't interact with the other moves being made. Specifically, if $A$ is the set of nodes we want to add or remove pebbles from, and $P$ is the set of nodes that had a pebble at the start of the step, then we can do all those additions and removals in a single step as long as $\{a-1 | a \in A \} \subseteq P - A$.

For example, consider the strategy that places a pebble at $i$ on step $i$, but marks the pebbles that are multiples of $\sqrt{N}$ as "checkpoints" and removes the highest-index pebble behind a pebbled checkpoint whenever possible. This strategy still reaches node N after $N$ steps, like the naive strategy, but reduces the maximum number of pebbles from $N$ to $2 \sqrt{N}$.

Are there parrallel-line-pebbling strategies that finish in $N$ steps with even lower asymptotic max-pebble complexity? What if we're willing to allow $O(N \lg N)$ steps? What are the "interesting" points, where the tradeoff between max-pebble and time is particularly good?

EDITS: Added Lemmas 2 and 3.

Here's a partial answer:  You can reach position $N$

in $N$ moves using space $N^{O(\epsilon(N))}$, where $\epsilon(N) = 1/\sqrt{\log N}$.  (Lemma 1)
in $N^{1+\delta}$ moves using space $O(\log N)$ (for any constant $\delta>0$) (Lemma 2).

Also, we sketch a lower bound (Lemma 3): for a certain class of so-called well-behaved solutions, Lemma 1 is tight (up to constant factors in the exponent), and no such solution using poly-log space can reach position $N$ in time $O(N\,\text{polylog}\, N)$.

Lemma 1. For all $n$, it is possible to reach position $n$ in $n$ moves using space $$\exp(O(\sqrt{\log n}))~=~n^{O(1/\sqrt{\log n})}$$

Proof. The scheme is recursive, as shown in the figure below. We use the following notation:

$k$ is the number of levels in the recursion
$P(k)$ is the solution formed (with $k$ levels of recursion).
$N(k)$ is the maximum position reached by $P(k)$ (at time $N(k)$).
$S(k)$ is the space used by $P(k)$.
$L(k)$ is the number of layers used by $P(k)$, as illustrated below:

In the picture, time proceeds from top to bottom. The solution $P(k)$ does not stop at time $N(k)$, instead (for use in the recursion) it continues until time $2\,N(k)$, exactly reversing its moves, so as to return to a single pebble at time $2\,N(k)$.

The solid vertical lines partition the $L(k)$ layers of $P(k)$.  In the picture, $L(k)$ is five, so $P(k)$ consists of 5 layers.   Each of the $L(k)$ layers of $P(k)$ (except the rightmost) has two sub-problems, one at the top of the layer and one at the bottom, connected by a solid vertical line (representing a pebble that exists for that duration).  In the picture, there are five layers, so there are nine subproblems.  Generally, $P(k)$ is composed of $2\,L(k)-1$ subproblems. Each subproblem of $P(k)$ has solution $P(k-1)$.

The crucial observation for bounding the space is that, at any time, only two layers have "active" subproblems.  The rest contribute just one pebble each thus we have

$S(k) \le L(k) + 2\,S(k-1)$, and
$N(k) = L(k) \cdot N(k-1)$

Now, we choose $L(k)$ to fully determine $P(k)$.  I'm not sure if this choice is optimal, but it seems close: take $L(k) = 2^k$. Then the above recurrences give

$S(k) \le k\cdot 2^k$, and
$N(k) = 2^{k(k+1)/2}$

So, solving for $n=N(k)$,
we have $k \approx \sqrt {2 \log n}$
and $S(k) \approx \sqrt {2 \log n}\, 2^{\sqrt {2 \log n}} = \exp(O(\sqrt{\log n}))$.

This takes care of all positions $n$ in the set $\{N(k) : k\in\{1,2,\ldots\}\}$.  For arbitrary $n$, trim the bottom of the solution $P(k)$ for the smallest $k$ with $N(k)\ge n$.  The desired bound holds because $S(k) / S(k-1) = O(1)$.  QED

Lemma 2. For any $\delta>0$, for all $n$, it is possible to reach position $n$ in $n^{1+\delta}$ moves using space $O(\delta 2^{1/\delta}\log n).$

Proof. Modify the construction from the proof of Lemma 1 to delay starting each subproblem until the previous subproblem has finished, as shown below:

Let $T(k)$ denote the time for the modified solution $P(k)$ to finish. Now at each time step, only one layer has a subproblem that contributes more than one pebble, so

$S(k) \le L(k) + S(k-1)$,
$N(k) = L(k) \cdot N(k-1)$,
$T(k) = (2\,L(k)-1)\cdot T(k-1) \le 2\,L(k)\cdot T(k-1) \le 2^k N(k)$.

Choosing $L(k) = 2^{1/\delta}$, we get

$S(k) \le k 2^{1/\delta}$,
$N(k) = 2^{k/\delta}$,
$T(k) \le 2^k N(k)$.

Solving for $S = S(k)$ and $T=T(k)$ in terms of $n=N(k)$, we have $k=\delta \log n$, and

$S \le \delta 2^{1/\delta} \log n$, and
$T \le n^{1+\delta}$.

This takes care of all positions $n$ in the set $\{N(k) : k\in\{1,2,\ldots\}\}$.  For arbitrary $n$, trim the bottom of the solution $P(k)$ for the smallest $k$ with $N(k)\ge n$.  The desired bound holds because $S(k) / S(k-1) = O(1)$.  QED

The solutions in the proofs of Lemmas 1 and 2 are well-behaved, in that, for sufficiently large $n$, for each solution $P(n)$ that reaches position $n$ there is a position $k\le n/2$ such that only one pebble is ever placed at position $k$, and the solution decomposes into a (well-behaved) solution $P(N-k)$ for positions $k+1,k+2,\ldots,n$ and two (well-behaved) solutions $P(k)$, each for positions $1,2,\ldots,k$, connected by the pebble at position $k$.  With an appropriate definition of well-behaved, let $V(n)$ denote the minimum pebble volume (the sum over time of the number of pebbles at each time) for any well-behaved solution. The definition implies that for sufficiently large $n$, for $\delta=1>0$,
$$V(n) \ge \min_{k<n} V(n-k) + \max(n/2, (1+\delta) V(k)).$$

I conjecture that for every sufficiently large $n$ there is a well-behaved solution that minimizes pebble volume.  Maybe somebody can prove it?  (Or just that some near-optimal solution satisfies the recurrence...)

Recall that $\epsilon(n) = 1/\sqrt{\log n}$.

Lemma 3. For any constant $\delta>0$, the above recurrence implies $V(n) \ge  n^{1+\Omega(\epsilon(n))}$.

Before we sketch the proof of the lemma, note that it implies that any well-behaved solution that reaches position $n$ in $t$ steps has to take space at least $n^{1+\Omega(\epsilon(n))}/t$ at some step.  This yields corollaries such as:

Lemma 1 is tight up to constant factors in the exponent (for well-behaved solutions).
No well-behaved solution can reach position $n$ in $n\,\text{polylog}\, n$ time steps using space $\text{polylog}\, n$.  (Using here that $n^{\Omega(\epsilon(n))} = \exp(\Omega(\sqrt{\log n})) \not\subseteq \,\text{polylog}\, n$.)

Proof sketch.  We show $2 V(n) \ge f(n)$ where $f(n) = n^{1+c\epsilon(n)}$ for some sufficiently small constant $c.$  We assume WLOG that $n$ is arbitrarily large, because by taking $c>0$ small enough, we can ensure $2 V(n) \ge f(n)$ for any finite set of $n$ (using here that $V(n)\ge n$, say).

The lemma will follow inductively from the recurrence as long as, for all sufficiently large $n$, we have $f(n) \le \min_{k<n} f(n-k) + \max(n, 2 f(k))$, that is, $f(n) - f(n-k) \le \max(n, (1+\delta) f(k))$ for $k<n.$

Since $f$ is convex, we have $f(n) - f(n-k) \le k f'(n)$.  So it suffices if $k f'(n) \le \max(n, (1+\delta) f(k)).$

By a short calculation (using $f(n)/n = e^{c\sqrt{\log n}}$ and $f'(n)=(f(n)/n)(1+c/(2\sqrt{\log n})),$ and using a change of variables $x = \sqrt{\log k}$ and $y=\sqrt{\log n}$), this inequality is equivalent to the following:
for all sufficiently large $y$ and $x\le y$, $e^{cy}(1+c/(2y)) \le \max(e^{y^2 - x^2}, (1+\delta) e^{cx})$.  Since $1+z\le e^z$, and $e^z\le 1+2z$ for $z\le 1$, it suffices to show
$e^{cy + c/(2y)} \le \max(e^{y^2 - x^2}, e^{2\delta+cx}),$ that is,
$$cy + c/(2y) \le \max(y^2 - x^2, 2\delta+cx).$$

If $y \le x + 0.1\delta/c$, then $cy+c/(2y) \le cx + 0.2\delta$ (for large $y$) and we are done, so assume $y\ge x + 0.1\delta/c$.  Then $y^2-x^2 \ge 0.1y\delta/c$ (for large $y$), so it suffices to show
$$cy + c/(2y) \le 0.1 y\delta/c.$$
This holds for sufficiently small $c$ and large $y.$  QED


Streaming algorithms suitable for undergrad course I am looking for interesting streaming algorithms that would be suitable for presentation in an undergraduate algorithms course.

Good choices should probably satisfy the following requirements:

Solve a problem that is useful in practice or easy to motivate, or alternatively, illustrate techniques that are beautiful or useful.
Be suitable for presentation in an undergraduate algorithms course.  This means the algorithm and analysis can't be too complex.  Also they shouldn't require too much heavy probability theory to analyze (sadly, this rules out many beautiful algorithms).

What would be a good candidate?

One beautiful algorithm is the deterministic algorithm to find an element that occurs with frequency at least 50% (if any such element exists), using $O(1)$ space; or its generalization, find all items that occur with frequency at least $1/k$, using $O(k)$ space.  Are there any others that would be an excellent choice for an undergraduate course?

In addition to the Heavy Hitters problem you've mentioned (which has quite a few algorithms: batch-decrement, space-saving, etc.), I'd consider presenting the following:

Reservoir sampling - maintain a sample of $k$ elements, uniformly sampled from the set of items which appeared in the stream so far, in $O(k)$ space.
Approximate bit counting on a sliding window - given a bit-stream, answer queries approximating the number of $1$'s in the last $N$ bits, and do so using $O(\log N)$ space.
Sampling from a sliding window (at any point, give a sample of $k$ elements uniformly chosen from the last $N$ elements of a stream).
Exact item counting - answer queries of the form "how many times did $x$ appear in the stream" such that the answer will be correct w.h.p. using only sublinear space (modern data structures are quite complex, but Count–min sketch seems to fit undergrad course).


Terminology for games with incomplete information and no prior beliefs Can anyone please tell me what is the term used for games with incomplete information and there are no prior beliefs about other players' private information.

For example, let $ v_i(a_i,\theta_i) $ be the utility function of the player $ i $ and $ a_i $ be decided for each player some how. $ \theta_i $ be the private information for player $ i $. Player $ i $ has no belief (no knowledge of probability distribution) about others' private information except that it is a real number. Few authors call such games to be pre-Bayesian games. But there seems to be no standard. It would be great if any one can let me know this. Thanks!

Uncertainty in the absence of a prior distribution is sometimes called Knightian Uncertainty in economics. There are a couple of recent papers studying how to deal with knightian uncertainty in mechanism design. See for example:

The Knightian Truthfulness of Classical Mechanisms

Knightian Auctions


Finding the Length of the shortest Accepting path of a NDTM Let $M$ be a NDTM (non deterministic Turing machine) which decides a certain NP-complete language, say SAT.

$M$ computes any instance $I$ of the NP-complete problem in at most $p(n)$ non deterministic steps ($p$ in a polynomial function, $n$ is the input size). The length of a computation path can be measured as the "rank" of the non deterministic step where $M$ halts. Let call $rank_M(I)$  the rank of the shortest accepting path ($rank_M(I)$ is $p(n)+1$ if $M$ rejects $I$).

Is this problem NP-complete : Given a boolean expression $I$, is it true that $rank_M(I)=k$ ? ($k$ is polynomially bounded in $n$)

Edit --- $rank_M(I)$ has been modified : it defines now the shortest accepting path (instead of just the rank of the step where $M$ halts).

Thank you.

Your problem is $\mathsf{NP}$-complete, and you can find a proof for instance here (I gave a sketch in comments).

A remark: If you consider $\{\langle M,x,t\rangle : M$ halts on $x$ in $t$ steps $\}$, then you can only show it is $\mathsf{NP}$-hard. But as you mention that you consider $t$ polynomially bounded (in the sizes of $M$ and $x$, I guess), then your problem belongs to $\mathsf{NP}$.


Is there a polynomial-time algorithm to solve graph isomorphism for Delaunay graphs of (finite) hexagonal tessellations? Given a finite plane, I have a hexagonal tessellation of that plane with a fixed-size regular hexagon. I then compute the Delaunay graph G for the tessellation. Given such a graph G, I delete specific sets of nodes in that graph to yield multiple subgraphs of G. I need to determine if these subgraphs are isomorphic (to each other).

Does there exist a polynomial-time algorithm to do so?

I know that there is no know poly-time algorithm for solving graph isomorphism in the general case. But I am not sure if it is still the case for such specific Delaunay graphs.

I guess all those subgraphs will be planer graphs. And I think that there is efficient algorithm for isomorphism of planer graphs.
ref: Linear time algorithm for isomorphism of planar graphs by     J. E. Hopcroft
J. K. Wong
NOTE: I am not an expert and might not be making any sense.


Does ${\bf AC^0PAD} = {\bf PPAD}$? What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem?

Recently giving faster algorithms for Circuit satisfiability for small circuits turned out to be important, so I wonder what happens to rectricted versions of ${\bf PPAD}$.

$\def\ac{\mathrm{AC}^0}$Yes, $\ac\mathrm{PAD}=\mathrm{PPAD}$. (Here and below, I’m assuming $\ac$ is defined as a uniform class. Of course, with nonuniform $\ac$ we’d just get $\mathrm{PPAD/poly}$.)

The basic idea is quite simple: $\ac$ can do one step of a Turing machine computation, hence we can simulate one polynomial-time computable edge by a polynomially long line of $\ac$-computable edges. By a further extension of the idea, one could simulate edges computable in poly time with a PPAD oracle, that is, PPAD is closed under Turing reducibility; this argument is given in Buss and Johnson.

There are many equivalent definition of PPAD in the literature that differ in various details, hence let me fix one here for definiteness. An NP search problem $S$ is in PPAD if there is a polynomial $p(n)$, and polynomial-time functions $f(x,u)$, $g(x,u)$, and $h(x,u)$ with the following properties. For each input $x$ of length $n$, $f$ and $g$ represent a directed graph $G_x=(V_x,E_x)$ without self-loops where $V_x=\{0,1\}^{p(n)}$, and every node has in-degree and out-degree at most $1$. The representation is such that if $(u,v)\in E_x$, then $f(x,u)=v$ and $g(x,v)=u$; if $u$ has out-degree $0$, $f(x,u)=u$; and if $u$ has in-degree $0$, $g(x,u)=u$.

The node $0^{p(n)}\in V_x$ is a source (i.e., it has in-degree $0$ and out-degree $1$). If $u\in V_x$ is any source or sink (in-degree $1$, out-degree $0$) other than $0^{p(n)}$, then $h(x,u)$ is a solution to $S(x)$.

We can define $\ac\mathrm{PAD}$ similarly, except we require $f,g,h$ to be in $\mathrm{FAC}^0$.

I will ignore $h$ in the construction for simplicity. (It is not hard to show that one can take it to be a projection, hence $\ac$-computable.)

So, consider a PPAD problem $S$ defined by $f$ and $g$, and fix Turing machines computing $f$ and $g$ in time $q(n)$. For any $x$, we define a directed graph $G'_x=(V'_x,E'_x)$ whose vertices are sequences of the following form:

$(0,u,c_1,\dots,c_k)$, where $u\in V_x$, $0\le k\le q(n)$, and $c_1,\dots,c_k$ are the first $k$ configurations in the computation of $f(x,u)$.
$(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_k)$, where $u,v\in V_x$, $0\le k\le q(n)$, $f(x,u)=v$, $c_1,\dots,c_{q(n)}$ is the full computation of $f(x,u)$, and $d_1,\dots,d_k$ are the first $k$ steps in the computation of $g(x,v)$.
$(1,v,d_1,\dots,d_k)$, where $0^{p(n)}\ne v\in V_x$, $0\le k\le q(n)$, and $d_1,\dots,d_k$ are the first $k$ configurations in the computation of $g(x,v)$.
$(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_k)$, where $u,v\in V_x$, $v\ne0^{p(n)}$, $0\le k\le q(n)$, $g(x,v)=u$, $d_1,\dots,d_{q(n)}$ is the computation of $g(x,v)$, and $c_1,\dots,c_k$ are the first $k$ steps in the computation of $f(x,u)$.

$E'_x$ consists of the edges in $V'_x\times V'_x$ of the following kinds:

$(0,u,c_1,\dots,c_k)\to(0,u,c_1,\dots,c_{k+1})$
$(0,u,c_1,\dots,c_{q(n)})\to(0,u,c_1,\dots,c_{q(n)},v)$
$(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_k)\to(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_{k+1})$
$(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_{q(n)})\to(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_{q(n)})$ if $f(u)=v$ and $g(v)=u$ (i.e., either $(u,v)\in E_x$, or $u=v$ is an isolated vertex)
$(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_{k+1})\to(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_k)$
$(1,v,d_1,\dots,d_{q(n)},u)\to(1,v,d_1,\dots,d_{q(n)})$
$(1,v,d_1,\dots,d_{k+1})\to(1,v,d_1,\dots,d_k)$
$(1,u)\to(0,u)$

Formally, let $r(n)$ be a polynomial bounding the lengths of binary representations of all the sequences above (such that we can extend or shorten sequences, and extract their elements with $\ac$-functions); we actually put $V'_x=\{0,1\}^{r(n)}$, and we let all vertices except the above-mentioned sequences to be isolated.

It is easy to see that the functions $f'$, $g'$ representing $G'_x$ are $\ac$-computable: in particular, we can test in $\ac$ whether $c_1,\dots,c_k$ is a valid partial computation of $f(x,u)$, we can compute $c_{k+1}$ from $c_k$, and we can extract the value of $f(x,u)$ from $c_{q(n)}$.

The sinks in $G'_x$ are nodes of the form $(0,u,c_1,\dots,c_{q(n)},u,d_1,\dots,d_{q(n)})$ where $u$ is a sink in $G_x$. Likewise, sources are $(1,v,d_1,\dots,d_{q(n)},v,c_1,\dots,c_{q(n)})$ where $v$ is a source in $G_x$, except that in the special case $v=0^{p(n)}$, we have pruned the line early and the corresponding source in $G'_x$ is just $(0,0^{p(n)})$. We can assume the encoding of sequences is done in such a way that $(0,0^{p(n)})=0^{r(n)}$.

Thus, $f'$ and $g'$ define an $\ac\mathrm{PAD}$ problem $S'$, and we can extract a solution to $S(x)$ from a solution to $S'(x)$ by an $\ac$-function $h'$ which outputs the second component of a sequence.


Factoriality testing algorithms and their efficiency How efficiently can we decide that a number $P$ is the result of the factorial of another number $N$ (i.e. $P = N!$)? Notice that $P$ and $N$ are both integers and we are only given $P$.

Notice that the input size is $n = \lceil \log_2 P \rceil$. The problem can be solved in time near linear in $n$, i.e. in time $n \log^{O(1)} n = (\log P)(\log \log P)^{O(1)}$.

The trick is to do binary search on the integers in $[1, 2\log_2 P]$ in order to find the largest $N$ such that $N! \leq P$: call this number $N(P) = \max\{N: N! \leq P\}$. If $N(P) = P$, the answer is 'yes', otherwise it is 'no'.

Let us first show that $N(P) \leq 2\log_2 P$ for $P \geq 4$ (for smaller $P$ you can use a lookup table). This follows because for every $N$, $N! \geq (N/2)^{N/2}$, and therefore
$$
\log_2 P \geq \frac{N}{2}\log_2 \frac{N}{2} \geq \frac{N}{2}.
$$

The complexity is $T(2\log_2 P) \cdot O(\log \log P)$, whete $T(N!)$ is the complexity of computing $N!$. This is because the binary search performs $O(\log \log P)$ steps, and at each step computes $N!$ for some $N \leq 2\log_2 P$. The work by Borwein, referenced in Chad's answer, gives a near-linear in $N$ bound on $T(N)$.


Is it sometimes better to not publish at all? I hope this is not a politically incorrect question to ask, but for a PhD student who usually publishes at CCC/ITCS/ICALP (and occasionally at FOCS/STOC), could it be harmful (career-wise) to publish less significant works in less prestigious conferences (e.g. MFCS, FCT, STACS, IPL)? Could it be better to just leave such papers laying at ECCC/arXiv?

I was just referred to this question by graduate students that, in my opinion, were far too influenced by the answers. So let me start with two generic advises.

To the aspiring scientist: Don't assign too much weight to any answer on such matters, and don't assume that a small and highly non-random sample represents the common views among senior (or non-senior) people in the community. In general, think for yourself!
See http://www.wisdom.weizmann.ac.il/~oded/advice.html for more details...
To the senior scientist: Be careful about what you say, since it may be misinterpreted in harmful ways and/or have more impact than what you intend and/or perceive.

Re the discussion itself, I think that the idea that credits are non-monotone is not only utterly non-intuitive but also utterly wrong, and I am talking as a person who sat on numerous committees that took various career decisions. A person who has $X$ fundamental contributions, $Y$ important contributions, and $Z+1$ nice/legitimate contribution is ranked higher than one who has $(X,Y,Z)$, regardless of the numerical values of $X,Y,Z$ and assuming that quality captured by the $(X,Y,Z)$ triples is exactly the same. Trade-offs between different types is a different question, ditto re how much credit does each increase give...

In other words, for any set of works $S$ and any additional work $a$,
the credit of $S \cup \{a\}$ is (strictly) bigger than to $S$ [i.e., strict monotonicity].

In my opinion, people who claim the opposite just assume that a larger number $Z$ implies a decrease in what the value of $X$ (or $Y$) could have been. But this assumption may be wrong and more importantly is irrelevant to the comparison at hand. That is, if you compare a case of $(X,Y,Z)$ to one of $(X,Y,Z+1)$, you must rule that the second person (called B) was able to meet the performance of the first (called A) although B also did another work of 3rd type; so B is clearly better. Indeed, you may think that B could have done better investing more energy in Type 1 (which is not always true - see below), but that's a comparison against an imaginary B, not against A. (And when you have a case of $(X,Y,Z)$ against $(X,Y,Z+10)$, the same holds is stronger terms.)

In addition, I think there is also a confusion between the works and the publications. If a work already exists in writing, and assuming that it has its merits, then it can only be advantageous to publish it in a adequate venue, where by adequate I mean one that is intended for works of this profile (wrt quality and scope - publication in a too prestigious conference may actually hurt, since it may generate some annoyance and even bad opinions re the author). But if one still has to develop a work from an initial idea (or "only" write it - which always involves some more research...), then one may consider the trade-off between the amount of time required versus the importance of the work.

Finally, as I hinted above, it is not clear that one is better off aiming all the time at Type 1 (i.e., fundamental work). Firstly, this is infeasible and thus problematic/harmful. Secondly, and more importantly, one is always better off following the inherent logic of his/her own interests and ideas/feelings, and aiming to do as well as possible. See more in the aforementioned webpage.

Oded Goldreich


Proper PAC learning VC dimension bounds It is well known that for a concept class $\mathcal{C}$ with VC dimension $d$, it suffices to obtain $O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$ labelled examples to PAC learn $\mathcal{C}$. It is not clear to me if the PAC learning algorithm (which uses these many samples) is proper or improper? In the textbooks of Kearns and Vazirani as well as Anthony and Biggs it seems like the PAC learning algorithm is improper (i.e., the output hypothesis does not lie in $\mathcal{C}$)

Could someone clarify if a similar upper bound holds for the proper PAC learning setting as well?  If so, could you give me a reference where this is explicitly mentioned and also contains a self-contained proof?
Recently Hanneke improved this bound by getting rid of the $\log(1/\varepsilon)$ factor. Could someone clarify if the $\log(1/\varepsilon)$ is known to be removable for the Proper PAC learning setting? Or is it an open question still?

My thanks to Aryeh for bringing this question to my attention.

As others have mentioned, the answer to (1) is Yes, and the
simple method of Empirical Risk Minimization in $\mathcal{C}$ achieves
the $O((d/\varepsilon)\log(1/\varepsilon))$ sample complexity (see Vapnik and Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler, and Warmuth, 1989).

As for (2), it is in fact known that there exist spaces $\mathcal{C}$
where no proper learning algorithm achieves better than $\Omega((d/\varepsilon)\log(1/\varepsilon))$ sample complexity, and hence proper learning cannot achieve the optimal $O(d/\varepsilon)$ sample complexity. To my knowledge, this fact has never actually been published, but is rooted in a related argument of Daniely and Shalev-Shwartz (COLT 2014) (originally formulated for a different, but related, question in multiclass learning).

Consider the simple case $d=1$, and put the space $\mathcal{X}$ as $\{1,2,...,1/\varepsilon\}$, and $\mathcal{C}$ is singletons $f_z(x) := \mathbb{I}[x = z], z \in \mathcal{X}$: that is, each classifier in $\mathcal{C}$ classifies exactly one point from $\mathcal{X}$ as $1$ and the others as $0$. For the lower bound, take the target function as a random singleton $f_{x^*}$, where $x^{*} \sim {\rm Uniform}(\mathcal{X})$, and $P$, the marginal distribution of $X$, is uniform on $\mathcal{X}\setminus\{x^*\}$.  Now the learner never sees any examples labeled $1$,
but it must choose a point $z$ to guess is labeled $1$ (importantly, the
``all zero'' function is not in $\mathcal{C}$, so any proper learner must guess some $z$), and until it has seen every point in $\mathcal{X}\setminus\{x^*\}$ it has at least $1/2$ chance of guessing wrong (i.e., the posterior probability of its $f_z$ having $z \neq x^*$ is at least $1/2$).  The coupon collector argument implies it would require $\Omega((1/\varepsilon)\log(1/\varepsilon))$ samples to see every point in $\mathcal{X} \setminus \{x^*\}$. So this proves a lower bound of $\Omega((1/\varepsilon)\log(1/\varepsilon))$ for all proper learners.

For general $d>1$, we take $\mathcal{X}$ as $\{1,2,...,d/(4\varepsilon)\}$, take $\mathcal{C}$ as classifiers $\mathbb{I}_{A}$ for sets $A \subset \mathcal{X}$ of size exactly $d$, choose the target function at random from $\mathcal{C}$, and take $P$ again as uniform on just the points the target function classifies $0$ (so the learner never sees a point labeled $1$). Then a generalization of the coupon-collector argument implies we need $\Omega((d/\varepsilon)\log(1/\varepsilon))$ samples to see at least $|\mathcal{X}| - 2d$ distinct points from $\mathcal{X}$, and without seeing this many distinct points any proper learner has at least $1/3$ chance of getting greater than $d/4$ of its guess $A$ of $d$ points wrong in its chosen hypothesis $h_{A}$, meaning its error rate is greater than $\varepsilon$.  So in this case, there is no proper learner with sample complexity smaller than $\Omega((d/\varepsilon)\log(1/\varepsilon))$, which means no proper learner achieves the optimal sample complexity $O(d/\varepsilon)$.

Note that the result is quite specific to the space $\mathcal{C}$ constructed. There do exist spaces $\mathcal{C}$ where proper learners can achieve the $O(d/\varepsilon)$ optimal sample complexity, and indeed even the exact full expression $O((d/\varepsilon)+(1/\varepsilon)\log(1/\delta))$ from (Hanneke, 2016a). Some upper and lower bounds for general ERM learners have been developed in (Hanneke, 2016b), quantified in terms of properties of the space $\mathcal{C}$, as well as discussing some more specialized cases where specific proper learners can sometimes achieve the optimal sample complexity.

References:

Vapnik and Chervonenkis (1974). Theory of Pattern Recognition. Nauka, Moscow, 1974.

Blumer, Ehrenfeucht, Haussler, and Warmuth (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the Association for Computing Machinery, 36(4):
929–965.

Daniely and Shalev-Shwartz (2014). Optimal Learners for Multiclass Problems. In Proceedings of the 27th Conference on Learning Theory.

Hanneke (2016a). The Optimal Sample Complexity of PAC Learning. Journal of Machine Learning Research, Vol. 17 (38), pp. 1-15.

Hanneke (2016b). Refined Error Bounds for Several Learning Algorithms. Journal of Machine Learning Research, Vol. 17 (135), pp. 1-55.


Solve multiple instances of SAT with a 2-approximating #SAT query Assume we have some oracle $A$ such that when given as input a Boolean formula $\phi$, it outputs a 2-approximation to the number of satisfying assignments of $\phi$. If we are given multiple SAT instances $\phi_1,\ldots, \phi_m$ (where $m$ is a small constant such as 10, 5, or even 2), using only one query to $A$, how could I show in polynomial time which formulas are satisfiable?

Note that $\phi$ is unsatisfiable if and only if $A$ outputs 0 on input $\phi$.

Here's a sketch argument for constant $m$. I'll use $Z(\cdot)$ to denote the operator that takes a formula to its number of satisfying assignments. Let $T$ be a parameter to be determined later. You can easily construct formulae $\phi'_i$ with $Z(\phi'_i)=1+2^{2^iT}Z(\phi_i)$ for each $1\leq i\leq m$. Let $\phi$ be the conjunction $\phi'_1\wedge\cdots\wedge \phi'_m$ (renaming the variable sets to be disjoint if necessary). Then $Z(\phi)=\prod_{i=1}^m(1+2^{2^iT}Z(\phi_i))$, so $\frac 1 T \log_2 Z(\phi)$ is roughly the sum of $2^i$ over all $i$ such that $\phi_i$ is satisfiable. I believe the error term is $O(n/T)$ for fixed $m$ where $n$ is the total number of variables, so taking $T$ to be a sufficiently large $T$ polynomial in $n$, you can recover which $\phi_i$ are satisfiable from a $2$-approximation to $Z(\phi)$.


Impacts of quantum computing on Theoretical Computer Science Using quantum computers we can do calculations very fast.

However from a layman's view, I want to know the impact of quantum computers have on Theoretical computer science.

One major impact is that quantum computing gave us a polynomial time algorithm to solve the integer factoring problem which is not known to be efficiently solvable on classic computers. This partially motivated the development of public key cryptography that does not depend on the hardness of factoring problem.

Efficient quantum algorithm for an NP-complete problem would have the greatest impact on TCS since it would give us insights into the fundamental differences between the computational power of classical and quantum algorithms (assuming classic deterministic algorithms can not solve NP-complete problems in polynomial time) .


Are resource savings for the evaluation of $k$ dependent instances in parallel possible? Let $\phi(x_1,\dots,x_n)$ be a CNF. It is satisfiable if $\exists X=(x_1,\dots,x_n): \phi(X)=1$. Assume $\phi$ has a unique satisfying assignment. Then, by allowing only black-box queries to $\phi$, essentially $\Theta(2^n)$ queries will be required to find the satisfying $X$, i.e. to solve this NP-complete problem.

Now let us construct a circuit $C(X) = \bigvee_{\sigma_i \in S_n} \phi(\sigma_i(X))$, where $\bigvee$ is over all $n!$ many permutations $\sigma_i$ in the symmetric group $S_n$ of of $n$ elements. Thus, if evaluated in the trivial black-box way, $C(X)$ requires exponential time. But let us ignore this problem for a moment.

$C(X)$ has the nice property, that $C(X)$ has $n!$ satisfying assignment, if $\phi(x)$ has a unique one, and $C(X)$ remains unsatisfiable if $\phi(x)$ is. Essentially inputs to $C(X)$ are equivalent up to the number of $1$'s in the input. Thus testing $n+1$ different assignments with $0 \dots n$ bits set suffices to decide satisfiability of $\phi(x)$.

Let us now come back to the resources required to evaluate $C(X)$. Essentially $C(X)$ is solving $n!$ instances of the same problem (CNF evaluation) in parallel. There are (strong) direct product theorems which essentially say that solving $k$ independent instances of the same problem in parallel require essentially $k$ times the resources of solving a single instance (with non-neglible probability). But, crucially, the $n!$ instances of CNF evaluation we are solving are not indepent. We can walk over all permutations from one $\sigma_i$ to another $\sigma_j$ which differ only in the mapping of two variables. Thus, many clauses in $\phi(\sigma_i(X))$ and $\phi(\sigma_j(X))$ refer to the same variables and will evaluate to the same value. Thus evaluation of (large?) sets of clauses may be shared and reused while evaluating $\phi(\sigma_i(X))$ for various $i$.

The question I have is: are there any results on the resources required for dependent evaluation of $k$ instances of a problem (like direct product theorems, but maybe with contrary conclusion)? What impossibility result would an approach like the above run into as it implies a (novel?) approach for solving $NP$-complete problems? Would assuming $P \neq NP$ already imply a lower-bound on the dependent evaluation problem of $k$-instances, i.e. a generalization of direct product theorems?

EDIT: The problem appears to be a special case of the OR(SAT)-problem where one is given a set of SAT-instances $\psi_1, \dots, \psi_t$ and is aked to decide $\psi = \bigvee_{i=1}^t \psi_t$. The related instance compression problem asks for a reduction of $\psi$ to a much smaller instance $\psi'$. See this paper by Drucker for details and (references to) negative results on the problem. Thus, the minimized circuit $C'(X)$ in the answer below is an exponentially compressed instance of an OR(SAT)-problem, where the $\psi_i$ are equivalent to a single CNF $\phi$ up to relabeling of the input variables and the complete set of all possible relablings.

Assume $C'(X)$ is a logically equivalent but minimized version of $C(X)$. Then $C'(X) \notin  SIZE(poly(X))$, unless the polynomial hierarchy collapses.

To see this, assume $C'(X) \in SIZE(poly(X))$, i.e. $C'(X) \in P/poly$. As noted in the original post, this would imply $NP \in P/poly$, but then the claim follows from Karp-Lipton.

Thus, even the existence of a poly-sized circuit equvialent to $C(X)$ is unlikely. Or, in turn, a generalization of direct product theorems to the dependent case appears plausible under complexity theoretic assumptions.


Optimal evaluation of polynomials / rational functions A common way to compute the value a polynomial is to write it in Horner form. However, this isn't always the fastest way to evaluate it. Setting aside concerns of numerical precision, take the poynomial:

$$P(x) = \sum_{k=0}^n \binom{n}{k} x^k$$

with $n$ known. One technique would be to precompute the coefficients and evaluate the polynomial using the Horner form. However that will take time linear in $n$, whereas we might observe that

$$P(x) = (x+1)^n$$

which can be evaluated in $\mathcal{O}(\log n)$ multiplications.

In general, identifying patterns inside a polynomial that lend themselves to simplification can speed up evaluation. This is not always obvious

For instance $75938+99169x+45123x^2-805x^3-10745x^4-5523x^5-1309x^6-127x^7$ can also be written as $(x+5)^7-(2x+3)^7$.

Things become even more complicated once multiple variables are introduced, or when we generalize to rational functions.

Clearly there exists an algorithm to find the most efficient computation of a given expression in terms of arithmetic operations and variable assignments: iterate through all possible computations in order of their number of operations, decide if they are equivalent to the target equation and if so stop.

This of course is cost prohibitive. Is there a known efficient algorithm to solve this problem, or at least to approximate it?

In Knuth Vol II Theorem E on page 494 he presents an algorithm that can evaluate a polynomial using $\frac{n}{2} + 2$ multiplications. The theoretical minimum is $\frac{n}{2}$, assuming generic polynomials. The algorithm requires factoring polynomials. There is another algorithm from Rabin & Winograd that only requires division, but runs in $\frac{n}{2} + \log n$.

Your question is about automatically identifying special structure that can be exploited to optimize further, which these algorithms do not do.

Square-free factorization can be used to efficiently find repeated terms like $p(x)\cdot (q(x))^7$. It won't find your sum example.

If $n$ is not too big, it might actually be feasible to iterate through all circuits with $\frac{n}{2} + 1$ multiplication gates and arbitrary addition/subtraction gates. Reduce them symbolically to coefficient form and try to solve the resulting set of polynomial equations. I guess this last step would the hardest.


Bounding the gap between quantum and deterministic query complexity Although exponential separations between bounded-error quantum query complexity ($Q(f)$) and deterministic query complexity ($D(f)$) or bounded-error randomized query complexity ($R(f)$) are known, they only apply to certain partial functions. If the partial functions have some special structures then they are also polynomially related with $D(f) = O(Q(f)^9))$. However, I am mostly concerned about total functions.

In a classic paper it was shown that $D(f)$ is bounded by $O(Q(f)^6)$ for total functions, $O(Q(f)^4)$ for monotone total functions, and $O(Q(f)^2)$ for symmetric total functions. However, no greater than quadratic separations are known for these sort of functions (this separation is achieved by $OR$ for example). As far as I understand, most people conjecture that for total functions we have $D(f) = O(Q(f)^2)$. Under what conditions has this conjecture been proven (apart from symmetric functions)? What is the best current bounds on decision-tree complexity in terms of quantum query complexity for total functions?

As far as I know, the general bounds you state are essentially the best known. Changing the model slightly, Midrijanis has shown the bound that $D(f) = O(Q_E(f))^3$, where $Q_E(f)$ is the exact quantum query complexity of $f$; there are also tighter bounds known in terms of one-sided error (see Section 6 of this paper).

In terms of more specific, but still general, classes of functions, there is a paper of Barnum and Saks which shows that all read-once functions on $n$ variables have quantum query complexity $\Omega(\sqrt{n})$.

Although this progress has been limited, there has been considerable progress in lower bounding the quantum query complexity of specific functions; see this review for details (or e.g. the more recent paper of Reichardt, which proves that the most general version of the ''adversary'' bound characterises quantum query complexity).


0-1 Linear Programming: computing the Optimal Formulation Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in \{0,1\}$ and $k \in \mathbb{R}$.

Clearly, $c$ has the effect of splitting $\{0,1\}^n$ in two subsets $S_c$ and $S_{\lnot c}$. $S_c$ contains all and only those points satisfying $c$, whereas $S_{\lnot c}$ contains all and only those points falsifying $c$.

Assume that $|S_c| \geq n$. Now, let $O$ be a subset of $S_c$ such that all the following three statements hold:

$O$ contains exactly $n$ points.
Such $n$ points are linearly independent.
Such $n$ points are those at minimum distance from the hyperplane represented by $c$. More precisely, let $d( x, c )$ be the distance of a point $x \in \{0,1\}^n$ from the hyperplane $c$. Then, $\forall B \subseteq S_c$ such that $B$ satisfies 1 and 2 it is the case that $\sum_{x \in B} d(x, c) \geq \sum_{x \in O} d(x, c)$. In other words $O$ is, among all the subsets of $S_c$ satisfying both conditions 1 and 2, the one that minimizes the sum of the distances of its points from the hyperplane $c$.

  Questions

  Given $c$, is it possible to compute $O$ efficiently?
  Which is the best known algorithm to compute it?

$\ $

Example with $n = 3$

$S_{\lnot c} = \{ ( 1, 0, 1 ) \}$, $O = \{ ( 0, 0, 1 ), ( 1, 1, 1 ), ( 1, 0, 0 ) \}$.

$\ $

Update 05/12/2012

  Motivation

  The motivation is that using $O$ it should be possible to determine the optimal constraint $c^*$, as it should be the hyperplane defined by the $n$ points in $O$.

  The optimal constraint $c^*$ is the one that leads to the optimal polytope $P^*$.

  The optimal polytope $P^*$ is the one whose vertices are all and only the integer vertices of the initial polytope $P$ (an integer vertex is a vertex whose coordinates are all integer).

The process can be iterated for each constraint $c$ of a 0-1 $LP$ instance $I$, each time substituting $c$ with its corresponding optimal constraint $c^*$. At the end, this will lead to the optimal polytope $P^*$ of $I$. Then, since the vertices of $P^*$ are all and only the integer vertices of the initial polytope $P$ of $I$, any algorithm for $LP$ can be used to compute the optimal integer solution. I know that being able to compute $P^*$ efficiently would imply $P = NP$, however the following additional question still stands:

  Additional Question

  Is there any previous work along these lines? Did anyone already investigated the task of computing, given a polytope $P$, its corresponding optimal polytope $P^*$? Which is the best known algorithm to do that?

This seems to be NP-hard to do exactly, by reduction from subset sum. Suppose we had an efficient procedure to compute $O$. Given positive integers $v_1,\dots,v_n$ encoded in binary, we wish to test whether there is a subset summing to $s$. Preprocess by throwing out any integers larger than $s$.

Call the procedure to obtain a small set $O$ of points satisfying $v_1x_1+\dots+v_1x_n\leq s$, satisfying your minimality conditions (the preprocessing ensures $|S_c|\geq n$). This set will certainly contain a point on the hyperplane $v_1x_1+\dots+v_1x_n= s$ if there is one.


How to format author information in research papers? Is there any standard style for adding author information in research papers? I see different papers use different styles. Some have affiliation and contact address only. Some have affiliation, email, contact address in full. Some include designation also. So what is the best style one should follow? I am preparing a paper for a Springer Conference.

I think you should keep in mind how people are going to use this information and for what purpose.

You use it to advertise yourself and your identity. You hope that little by little, people learn to recognise your name and know what kind of work you do.
Other researchers will use the information to find more information about you and your work. If they find a relevant paper written by you, they might want to find your home page and see if you have done more recent research on the same topic. Or they might want to contact you and ask more about your work.
Various organisations will use it to construct bibliography databases (DBLP, ACM Portal, MathSciNet, etc.) and to come up with all kinds of statistics (how many papers were published by university X). The editors of the bibliography databases typically want to figure out which papers are written by the same person (far from trivial, as the names are not unique).

Some advice based on the above use cases:

Please try to include your full name. Do not abbreviate your first name. Use the same version of your name in all research papers, and use the same version on your home page. For example, if you decide to use middle initials, do it consistently.
An email address might be a good idea (at least if you are not worried about spam email). Not that I would ever send email blindly to an address that I see in a paper, but googling for the email address might be much faster than googling for your name if you happen to have lots of namesakes.
Affiliations (the names of the universities, departments, institutes, and/or companies) are a must to keep your employers happy... They also help with disambiguation if you happen to have lots of namesakes. (Unfortunately people change universities often or have double-affiliations, and this will also create some confusion in the bibliography databases.)

I have no idea who would ever use your full postal address for anything nowadays – if they need it, they can google for up-to-date information. However, it might be nice to include the town and country, especially if your university does not happen to be named after (a well-known) city.


Parametrized complexity of the 2-Long Paths Problem Consider the following problem:

  Let $G=(V,E)$ be a graph, $s,t\in V$ vertices and $k\in\mathbb N$ an integer parameter. The 2-Long Paths Problems asks whether there exist two disjoint paths from $s$ to $t$, each of length $\ge k$.

Is there an FPT time algorithm for the above problem?

The problem of a single long path is known to be FPT, and so is deciding whether there exists two paths of length exactly $k$ from $s$ to $t$.

What happen if we combine both?

Your problem is fixed-parameter tractable, which follows from the heavy machinery of Robertson & Seymour. Your problem can be stated in terms of rooted minors. A graph $H$ with designated root vertices $s$ and $t$ is a rooted minor of a graph $G$ with roots $s$ and $t$, iff there is a function $f \colon V(H) \to 2^{V(G)}$ which assigns to each vertex of $H$ a subset of vertices in $G$, called a branch set, such that the following holds:

For each $v \in V(H)$ the branch set $f(v) \subseteq V(G)$ induced a connected subgraph of $G$, and
The sets $f(v)$ and $f(u)$ are disjoint for $u \neq v$, and
For each edge $e = \{u,v\} \in E(H)$, there is an edge of $G$ between the branch set $f(u)$ and the branch set $f(v)$, and
The branch set of $s \in V(H)$ contains the $s$-vertex in $G$, and the branch set of $t \in V(H)$ contains the $t$-vertex in $G$.

Now consider the rooted graph $H$ with roots $s$ and $t$, connected by two vertex-disjoint paths of length $k$. (So $H$ is a cycle of length $2k$ with the root vertices at distance $k$ along the cycle.) You can show that $G$ has two vertex-disjoint $st$ paths of length at least $k$ if and only if the graph $G$ with roots $s$ and $t$ has $H$ as a rooted minor. Testing rooted minors is fixed-parameter tractable parameterized by the size of $H$, which follows from Graph Minors XIII. So your problem is FPT.

(If you are not familiar with graph minors, you might want to first absorb the fact that a graph has a cycle of length at least $k$ iff it contains the $k$-vertex cycle graph as a minor.)


Why is finding the ground state of a Hamiltonian in QMA? Why is finding the ground stte of a Hamiltonian in QMA?

It's in QMA to figure out if a hamiltonian has any energy eigenvalue within a certain window range which is at least inverse polynomial in size. But what if the energy gap for the ground state is inverse exponentially small? Then why is specifying the ground state in QMA? It takes an exponential time to measure energy up to inverse exponential accuracy, right? So, Arthur needs more than polynomial time to verify, right?

There needs to be a gap between the eigenvalue of the groundspace and the first excited state that is inverse-polynomial in the system size, and indeed such a promise is required for the QMA-complete Local Hamiltonian problem. Please refer to the formal definition of the Local Hamiltonian problem and the QMA-completness proof, e.g. Definition 10 and Theorem 1 in Nagaj's thesis. If the gap is inverse-exponentially small, then the promise is not satisfied by that local Hamiltonian instance and the QMA-completness proof does not apply since a key assumption is not satisfied.


What are examples of how non-uniformity can be useful? I'm curious about ways in which you have seen non-uniformity be useful in computation. One way is randomness, as in $BPP \subseteq P/poly$, and another is look-up tables which are used to show that all languages have non-uniform circuits.

In particular, I'm interested in ways that objects known to exist via the probabilistic method and other non-constructive (or not-constructive-enough) proof methods can be leveraged using non-uniformity. I'd prefer the examples to be natural, not contrived. To be clear, a circuit for a contrived problem could be something like: given some language $L \in P$, I create a polynomial size circuit by computing some really hard function $f(|x|)$ using my advice and asking whether $f(|x|)^{n/|f(|x|)|} \oplus x \in L$.

An example I like is the argument that $\mathrm{NE\subseteq coNE}/(n+1)$ by counting strings in the language (see e.g. https://blog.computationalcomplexity.org/2004/01/little-theorem.html).


Trying to understand a paper on ksvd algorithm (dictionary learning) by Elad, et al Trying to understand a paper titled KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation by M.Elad, et al;
my take of section IV.C. detailed description of KSVD, is that we have an objectiove function which we wish to minimize with respect to two variables, D (which is called the dictionary) and X (the coefficient matrix.
$$\min_{X,D} \{||Y-DX||_F^2\} \quad \textrm{  subject to} \quad \forall i, ||x_i||\leq T_0$$
One method of doing this is to divide it to two stages, sparse coding and dictionary update. In the sparse coding stage, we assume D is fixed and solve the above problem w.r.t X using a pursuit algorithm. Then we must update the dictionary to better fit our data using the coefficient matrix from previous stage.  In the update stage, we keep both X and D fixed and only one column of D and its corresponding row in X remains in question. After simplifying the objective function and decomposing the multiplication DX to the sum of k rank-1 matrices, one might suggest to use svd. But that would ruin the sparsity of X, so wee need to set constraints. At this point, the authors define some variables and use them for setting constraints. The problem is, I don't understand what is meant by this statement:

examples that use the atom $d_k$,i.e. those where $x_T^{k} (i)$ is
nonzero.

Any clarifications would be appreciated.

By examples that use the atom $d_k$,i.e. those where $x_T^{k} (i)$ is nonzero, the authors are referring to the nonzero elements of the coefficient matrix $X$ because only nonzero elements play a role in multiplying two matrices. Since we seek to have a sparse representation, we only pay attention to the nonzero elements of $X$ and keep the zero elements intact.


examples of use of permanents It is known that if calculating permanent is easy, then solving hard problems in NP is easy. Is there a transparent example regarding application of say finding independent set or find chromatic number of a graph through the permanent?

Here is a hint for your question in the comment to the question.  The independence number of a graph can be computed by a polynomial-time oracle Turing machine which calls the #P oracle just once.  That is, the independence number is in class FP#P[1].

For a graph G on n vertices, let gk(G) be the number of independent sets of size k in G.  Note that 0≤gk(G)<2n.  Let

$$f(G)=\sum_{k=0}^n 2^{nk}g_k(G).$$

I leave the rest of the proof as exercise.

Show that function f is in #P.
Show that the independence number of G can be computed from two integers n and f(G) in time polynomial in n, and conclude that the independence number can be computed in FP#P[1].
(If this is not clear from item 2,) conclude that the independence number can be computed by a polynomial-time oracle Turing machine which calls the oracle for the permanent just once.

The same idea works also for the chromatic number.


FL with polynomial number of log-space "reductions" still in FL? Suppose that $f: X \rightarrow X$ is computable in log-space. Given an input $x \in X$ where $x$ is encoded within $n$ bits, is $f^n(x)$ computable in log-space?

The answer is no unless L=P (and obviously yes if L=P).  To see this, fix a deterministic Turing machine (DTM) M which solves a P-complete problem in polynomial time, and consider a function f which maps a configuration of M to the configuration in the next time step.  Function f is just the simulation of one step in the DTM and can be computed in logarithmic space.  If you iterate this function t times, you can compute the configuration after t steps, and therefore you can decide whether DTM M accepts on a given input string within t steps.  If you can do this in logarithmic space, you have solved the P-complete problem in logarithmic space, and therefore L=P.


What's the correlation between treewidth and instance hardness for random 3-SAT? This recent paper from FOCS2013, Strong Backdoors to Bounded Treewidth SAT by Gaspers and Szeider talks about the link between the treewidth of the SAT clause graph and instance hardness.

  For random 3-SAT, i.e. 3-SAT instances chosen at random, what is the correlation between treewidth of the clause graph and instance hardness?

"Instance hardness" can be taken as "hard for a typical SAT solver", i.e. running time.

I am looking for either theoretical or empirical style answers or references. To my knowledge, there do not seem to be empirical studies on this. I am aware there are somewhat different ways to build SAT clause graphs, but this question is not focused on the distinction.

Maybe a natural closely related question is how treewidth of the clause graph relates to the 3-SAT phase transition.

Not really an answer but the closest references I am aware of. There are results available for branch-width. Also, there is at least one empirical study of treewidth of industrial instances.

Discovering treewidth, H. Bodlaender, 2005. Gives algorithms to compute bounds on treewidth.
Treewidth in Industrial SAT Benchmarks, R. Mateescu, 2011. Uses variations of above algorithms to estimate treewidth of SAT2009 competition benchmarks.
Algorithms and complexity results for #SAT and Bayesian inference, F. Bacchus S. Dalmao, T. Pitassi, 2003. Relates branch-width to complexity of #SAT, 2003.
Satisfiability, branch-width and tseitin tautologies, Alekhnovich, Razborov, 2002.


Introduction to spectral graph theory What are the basic references? Are there any good, high-level surveys of SGT and its applications to CS in general and machine learning more specifically?

Two sources: The Fan Chung book on spectral graph theory  and Dan Spielman's notes on the same.


Impagliazzo and Wigderson's famous P=BPP paper I'm reading Impagliazzo and Wigderson's famous $\mathsf P=\mathsf{BPP}$ paper in 1997.  Since I'm new to this field and the paper is a concise conference version, I have difficulty following their proofs.  In particular, some of their new theorems lack proofs.  To my best knowledge there hasn't been a journal version published.

I'm looking for resources from which I can learn their result, preferably those with formal proofs.  I'd be very grateful if you could tell me about such resources.

Check Chapter 7 of Salil Vadhan's monograph. Corollary 7.64 is Impagliazzo and Wigderson's result.


Concurrent algorithm for strongly connected components (SCCs) Is anybody aware of a concurrent version of Tarjan's SCCs algorithm, Kosaraju's algorithm or any other fast, O(|V| + |E|) algorithm for finding SCCs? Neither of those algorithms seem to be very hard to multithread, but I'd be happy for somebody else to have done this job. What I'm trying to handle here is an 8 GB directed graph, which I keep in RAM using a big AWS instance, and I'd like to make a good use of all 16 cores.

This answer might come late, but there's a work by Gavin Lowe: "Concurrent Depth-First Search Algorithms", Proceedings of TACAS 2014, p. 202--216, Volume 8413 of LNCS, Springer that has descriptions for parallel algorithms for computing strongly connected components, lasso-shaped paths and finding nodes that are part of a cycle.


Dynamic transitive closure with immediate new reachability facts The typical definition of dynamic transitive closure (or reachability) uses two types of queries: the first one is an update (edge deletion/insertion) and the second one is a reachability query. Thus, most works on time complexity provide separated estimations on update operation and reachability query evaluation. But what about the case when one wants to get new reachability facts immediately on the update? So, we have only update queries, and as a result of each edge insertion we want to get all new reachable pairs (for edge deletion --- all pairs that became unreachable, for example). Are there any results on the theoretical time complexity of such a case?

Most research regarding time complexity of dynamic reachability looks at an index structure which is updated and then queried.  It would be useful to know why you want an immediate query?  The link studies this idea from a descriptive complexity approach although time complexities aren't given for the queries.
https://arxiv.org/pdf/1512.05511.pdf


Algorithm to find s-t min paths in a weighted graph Given a directed graph with $n$ vertices with non-negative edge weights, I would like to find first $n^2$, $s$-$t$ minpaths with minimum sum of non-negative weights. By using Dijkstras shortest path algorithm I found out the first minpath. In order to get next minpath I have replaced edges in first minpath with infinity. By following this procedure I am missing out many minpaths whose sum of weights are much smaller than what I am getting by following above procedure.

Can some one suggest me a good procedure to list first $n^2$ minpaths.

Thank you.

Try searching for "k shortest paths". There are different answers depending on whether your graph is directed or undirected, whether you allow repeated vertices in your paths, etc.


If SAT is in PCP, for some constant q, then P = NP I have seen this statement before, but I haven't really seen a proof of it:

If $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, for some constant $q$, then $P = NP$.

Now, if $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, then SAT reduces to $GAP-q-CSP[1,2^{-q}]$. So to show $P = NP$, how do we show then that $GAP-q-CSP[1,2^{-q}]$ is in $P$?

Given a CSP where all constraints have arity at most $q$ we want to distinguish between the case where everything is satisfiable and the case where at most $1/2^q$ fraction of the constraints are satisfiable, in polynomial time. Here is how this can be done.

First, all predicates used in the CSP must have at least one satisfying assignment (otherwise we know that the instance is not perfectly satisfiable and we are done). If a used predicate has two or more satisfying assignments, then, if we take a random assignment for all variables some constraint is satisfied with probability at least $2/2^q>1/2^q$. Since all other constraints are satisfied with probability at least $1/2^q$, by linearity of expectations there exists an assignment that satisfies strictly more than $1/2^q$ fraction of the constraints and we are done in this case.

Finally, suppose that all predicates used have exactly one satisfying assignment. Then the CSP is an instance of DNF-SAT, which can be decided in polynomial time (we only need to check if any two constraints have a conflict).


Size of Formulas with no negative sign for Matrix Permanent What is the best lower bound for algebraic formulas for Permanent of a matrix given that the formulas have no negative sign? Is there an exponential lower bound known for such formulas and what would be a good reference on the topic?

Snir has proved a tight lower bound on the size of monotone formulas representing the permanent of an $n\times n$ matrix. The lower bound is $2^{2n - 0.25\log^2 n}$, and he notes that a formula of size $2^{2n - 0.25\log^2 n + O(\log n)}$ exists (Theorem 3.1. and comment after the proof).

The survey by Shpilka, and Yehudayoff is a good resource. Also, a lower bound of $2^{\Omega(n)}$ on the size of monotone circuits for the permanent is known as well (proved by Jerrum and Snir)


Approximate sum of a sorted list Recently,  I worked on the problem for computing the approximate sum of a list of sorted nonnegative numbers. For any fixed $\epsilon>0$,  an $O(\log n)$ time approximation scheme has been derived such that it gives an $(1+\epsilon)$-approximation for the sum. The paper is posted at http://arxiv.org/abs/1112.0520, which has not been finalized.

I have been looking for existing works for this problem, but I only got a few remotely related papers,  and cited them.  Was this problem studied before?   If someone knows any existing researches about this problem, please let me know. I will appreciate the help, and update the citations accordingly. If the results are old, the paper will be dumped into a garbage can.

This problem is solved in the following paper, where more general problems are mostly addressed: http://valis.cs.uiuc.edu/~sariel/papers/06/integrate/ .


Are there any implementations for zero-knowledge proofs of NP-complete problems? It's been known for a long time that any claim in NP has a zero-knowledge proof for it. Has anybody actually implemented a zero-knowledge proof system for a NP-complete language? Using a search engine, the most relevant thing I could find is this:

www.usenix.org/event/sec10/tech/full_papers/Meiklejohn.pdf

I'm not exactly sure what the scope of ZKPDL, but it looks like it's a combination of many special-purpose zero-knowledge protocols, and that it is not intended to NP-complete. It might turn out to be NP-complete with clauses like "x in [0,1]" and "x*y=z" allowing a reduction from SAT to the languages described there. However, the reduction doesn't seem natural or efficient.

The reason I'm asking this is that I'm currently working on an implementation of a NP-complete zero-knowledge protocol and I want to know what the prior work is.

The answer is yes, check the following paper:

SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
Eli Ben-Sasson and Alessandro Chiesa and Daniel Genkin and Eran Tromer and Madars Virza
http://eprint.iacr.org/2013/507
(also published at Crypto 2013)


Relation between edit distances over different alphabets Assume we have two strings $S_1$ and $S_2$ of lengths $cn$ and $cm$ bits resepctively for some $c\in\Bbb N$.

Assume that the Levenshtein distance (minimum number of single-character edits (i.e. insertions, deletions or substitutions)) between $S_1$ and $S_2$ over binary alphabet is $L(2)$.

For any $b$ such that $b>1$ and $b|c$ consider the strings $S_1$ and $S_2$ over alphabet $\{0,1,\dots,2^b-1\}$. Assume the Levenshtein distance between $S_1$ and $S_2$ over $b$-ary alphabet is $L(2^b)$.

Is there any relation between $L(2)$ and $L(2^b)$ in general?

Can we say anything for LCS (minimum number of insertions or deletions) distance as well?

Obviously, $L(2^b) \leq L(2)$.

The Levenshtein distance is at most the length of the longest string, so $L(2^b) \leq \max(cn,cm) / b$ whereas $L(2) \leq \max(cn,cm)$.

You cannot avoid $L(2^b)(S_1,S_2) = L(2)(S_1,S_2)$ when $L(2)(S_1,S_2) \leq \max(cn,cm) / b$:
consider for instance $b = c = 2$, $S_1 = 0^{2n}$ and $S_2 = (01)^{p} (00)^{n-p}$.

When $L(2)(S_1,S_2) > \max(cn,cm) / b$, you cannot avoid $L(2^b)(S_1,S_2) = \max(cn,cm) / b$.
Consider for instance $b = c = 2$, $S_1 = 0^{2n}$ and $S_2 = 1^{2n}$.


Algebraic formulation for packing problem My question is regarding the algebraic formulation for packing problems in graphs.

Taking an example, suppose I am interested in the problem of finding if there is a packing of k edge disjoint triangles in a given input (undirected) graph. I am aware of techniques that approach this problem combinatorially. Is there a way to frame this problem algebraically?

Also, in context of graph theory, are algebraic methods less powerful when compared to combinatorial methods? Or is there any particular intuition that governs which approach is more effective in certain problems?

I apologize if my question sounds too general. The purpose of this question is to try and form an understanding of algebraic vs combinatorial methods in the context of graph theory.

It is possible to prove the fixed-parameter tractability of various graph-theoretical problems (e.g., finding a path of length k or finding k disjoint triangles) using algebraic techniques by reducing the problem to questions about certain polynomials. See for example the following very readable paper by Ryan Williams:

http://arxiv.org/abs/0807.3026v3

and some other related papers:

http://www.cs.cmu.edu/~jkoutis/papers/MultilinearDetection.pdf

http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.24

http://arxiv.org/abs/0912.2371

About your meta question: as the formulation of graph-theoretical problems is usually "combinatorial," it is not surprising to me that most of the natural approaches are "combinatorial" rather than "algebraic." The "algebraic" approaches work only if the problem has some unexpected connection with algebra, which is probably quite rare for natural "combinatorial" problems. In the above-mentioned papers, such a connection is discovered, allowing us to solve the problem using algebraic techniques. Interestingly, for these problems the algebraic algorithms are faster (have better bounds) than the combinatorial ones.


On complexity of linear programming with quadratic equality/inequality constraints? Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ many quadratic (not necessarily convex constraints)

equality constraints in $P$?
inequality constraints in $P$?

  Can $k=\Omega(poly(n))$ hold in both cases? At least can $k>0$ hold at least for $1.$?

A famous result by Motzkin and Straus expresses the $k$-clique problem as the maximization of a quadratic function subject to a system of linear constraints.  In particular, they prove:

  Let $G$ be a graph with vertices $1,\ldots,n$ and edge set $E$.
  Then $G$ contains a $k$-clique,
  if and only if there exist real numbers $x_1,\ldots,x_n$
  that satisfy the quadratic constraint
  $$\sum_{(i,j)\in E}x_ix_j \ge \frac12\left(1-\frac1k\right)$$
  together with the linear constraints $\sum_{i=1}^nx_i=1$
  and $x_1,\ldots,x_n\ge0$.

Since the $k$-clique problem is NP-hard, this implies that feasibility testing for a linear program plus a single quadratic inequality constraint is NP-hard.
If the graph $G$ contains a $k$-clique $C$, then for $i\in C$ we may set $x_i=1/k$ and for $i\notin C$ we may set $x_i=0$.
Note that the resulting point $x$ satisfies all constraints in the feasibility problem with equality.
This yields that also feasibility testing for a linear program plus a single quadratic equality constraint is NP-hard.

Reference:
T.S. Motzkin and E.G. Straus (1965), "Maxima for graphs and a new proof of a theorem of Turán." Canadian Journal of Mathematics 17, pp 533–540.


PCP Theorem - Alphabet Reduction Step What follows might seem stupid (and that probably reflects my poor understanding - so please bear with me)

I had a query on PCP theorem. We know that after the first three steps viz. Degree Reduction, Expanderization and Gap Amplification, we have a constraint graph $G$ with improved gap and huge alphabet size (like $\Sigma^{d^t}$). It is this problem that the alphabet reduction step addresses.

My question is that as outlined in Venkat Guruswami's lecture notes Introduction to Composition, it seems to me that the high level idea is to express the constraint $c_e$ over an edge $e$ as a Boolean constraint over boolean variables. This by itself achieves nothing and we also need to apply the PCP reduction ,$P_e$, on this edge. This "looks like" a recursive invocation of PCP and this is where I start getting a little worried. It seems as this recursive invocation would blow up the alphabet size again.

The authors have offered some explanation by observing that this recursion has a "base case" - namely - the "inner" PCP reduction applies only to constraints of constant size.

(By this I understand that the inner recursion gets invoked only when we are looking at constraints $c_e$ over a single edge which is a binary constraint, but still I have not yet come over the fear that somehow we still might blow up the alphabet size instead of shrinking it). To me, it still seems that a recursive repetition of Gap Amplification step will only make matters worse by blowing up the alphabet size unless we incorporate measures to handle the base case a little differently.

I hope my query  (as silly as it is) is probably clear. Please let me know what essential part am I missing (or have misunderstood).

You are asking about Dinur's proof of the PCP Theorem. The alphabet reduction step does use a PCP, but the PCP has very different parameters from the one you construct, and you don't necessarily have to use recursion to construct it. In particular, in Dinur's proof, because this inner PCP for the alphabet reduction is applied on constant sized input, we don't care if it has huge (say exponential or even more than that) blowup, which makes it comparatively easy to give a direct construction of a good enough PCP.

The entire proof including this stage is described in several places (see answer to this question), and so you may find a different description that you like better. In particular, in my complexity textbook with Sanjeev Arora this is covered in Chapters 11 and 22, we offer there two alternative ways to achieve the alphabet reduction step. One is using Hadamard-based PCP in the main text. But maybe the simplest self contained variant of it is the construction worked out in   Exercise 22.5. We also have a table, in Section 22.2.1, that shows exactly what very step of the proof does to the alphabet size (and other parameters such as soundness error, size and number of queries) and that may allay your concern.


Are there specific examples of integral polyhedra that are neither Totally Unimodular nor Total Dual Integral? It is well known that if a constraint matrix $A$ is total dual integral or totally unimodular, then this is a sufficient condition of integrality of the polyhedron defined by the system $Ax \leq \beta$ (provided that $\beta$ has integer entries). But it is not a necessary condition.

Thus my question is

  Are there natural examples (from combinatorial optimization) of integral polyhedra such that their underlying constraint matrix is neither TUM nor TDI?

I'm only going to talk about the constraint matrix part of the problem, I don't know much about the linear system (TDI) part.

Call a matrix $A$ good if $\{x|Ax\leq b,x\geq 0\}$ is a integral polytope for all integral $b$.
TUM is precisely the set of good integral matrices. This is a result by Hoffman and Kruskal. see this for how the theorem comes about and the original paper.

If we relax the requirement that $A$ is integral, then we get a larger class of matrices. Call a good matrix $A$ trivial, if it is a scaling of a TUM matrix (i.e. $A=\frac{1}{k}B$ for some TUM matrix $B$ and integer $k$).

Sadly, I don't know of any natural non-trivial good matrices.

But there is a characterization of good matrices. A matrix $A$ is $1$-regular if for all non-singular square submatrix $R$, $R^{-1}$ is integral. We have the following by Appa and Kotnyek.

  A rational matrix $A$ is good iff $A$ is $1$-regular.

Here is an example of a non-trivial good matrix.

$$\left(
\begin{array}{cc}
 \frac{1}{2} & -\frac{1}{2} \\
 -\frac{1}{2} & -\frac{1}{2} \\
\end{array}
\right)$$


Scott's stochastic lambda calculi Recently, Dana Scott proposed stochastic lambda calculus, an attempt to introduce probabilistic elements into (untyped) lambda calculus based on a semantics called graph model.  You can find his slides on line for example here and his paper in Journal of Applied
Logic, vol. 12 (2014).

However, by a quick search on the Web, I found similar previous research, for example, that for Hindley-Milner type system.  The way they introduce probabilistic semantics is similar to Scott's (in the former, they use monads while in the latter Scott uses continuation-passing style).

In which way is the Scott's work different from previous work available, in terms of theories themselves or their possible applications?

One apparent strength of his approach is that it allows higher-order functions (i.e. lambda terms) to be observable outcomes, which measure theory generally makes quite tricky. (The basic problem is that spaces of measurable functions generally have no Borel $\sigma$-algebra for which the application function - sometimes called "eval" - is measurable; see the intro to the paper Borel structures for function spaces.) Scott does this using a Gödel encoding from lambda terms to natural numbers, and working directly with the encoded terms. One weakness to this approach may be that the encoding could be difficult to extend with real numbers as program values. (Edit: This is not a weakness - see Andrej's comment below.)

Using CPS seems to be primarily for imposing a total order on computations, to impose a total order on access to the random source. The state monad should do just as well.

Scott's "random variables" seem to be the same as Park's "sampling functions" in his operational semantics. The technique of transforming standard-uniform values into values with any distribution is more widely known as inverse transform sampling.

I believe there's just one fundamental difference between Ramsey's and Scott's semantics. Ramsey's interprets programs as computations that build a measure on program outputs. Scott's assumes an existing uniform measure on inputs, and interprets programs as transformations of those inputs. (The output measure can in principle be computed using preimages.) Scott's is analogous to using the Random monad in Haskell.

In its overall approach, Scott's semantics seems most similar to the second half of my dissertation on probabilistic languages - except I stuck with first-order values instead of using a clever encoding, used infinite trees of random numbers instead of streams, and interpreted programs as arrow computations. (One of the arrows computes the transformation from the fixed probability space to program outputs; the others compute preimages and approximate preimages.) My dissertation's chapter 7 explains why I think interpreting programs as transformations of a fixed probability space is better than interpreting them as computations that build a measure. It basically comes down to "fixpoints of measures are way complicated, but we understand fixpoints of programs pretty well."


coNP certificate for Graph Isomorphism It is easy to see that graph isomorphism(GI) is in NP. It is a major open problem whether GI is in coNP. Are there any potential candidates of properties of graphs that can be used as coNP certificates of GI. Any conjectures that imply $GI \in coNP$ ? What are some implications of $GI \in coNP$ ?

If $GI$ is in $coNP$, then we would have the result: $GI$ is not $NP$-complete unless $NP=coNP=PH$.  (Currently known: $GI$ is not $NP$-complete unless $\Sigma_2 P = \Pi_2 P = PH$).

Since $GI$ is in $coAM$, obviously derandomizing $coAM$ (doi link) would put $GI \in coNP$, but I don't know of any candidate graph properties for putting $GI \in coNP$ otherwise. I look forward to more answers though!

Interestingly, in that paper they also show that Graph Non-Isomorphism has subexponential size proofs -- that is, $GI \in co NSUBEXP$ -- unless $PH = \Sigma_3 P$.  This is at least headed in the direction of showing conditionally that $GI \in coNP$.


Are all RegExp solvable in O(n)? I'm wondering if all features, that are often part of modern RegEx engines, are solvable in O(n). I'm talking about features like repeating patterns ([abc]+);\1 would match abc;abc but not abc;cba, lazy or not greedy repetition operators [ab]+?ba$ would match abba or aaaabbbbba but not ababa.
I know that things like anchors (^ and $), optional operator (a?), character classes ([abc], or [^abc]) and the plus operator can be reduced to nominal regex operations or are simple checks in the end.

Thanks to @emil's comment and this stackoverflow answer, I now know that POSIX extended regular expressions are solvable in O(n) but backreferences are at least NP-hard and maybe NP-complete.


Finding similar vectors in subquadratic time Let $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$ be a function which we refer to as the similarity function.
Examples of similarity function are
cosine distance, $l_2$ norm, Hamming distance, Jaccard similarity, etc.

Consider $n$ binary vectors of length $k$: $\vec{v} \in (\{0,1\}^k)^n$.

Our goal is to group vectors which are similar.
More formally,
we want to compute a similarity graph where
nodes are the vectors and
edges represent vectors which are similar ($d(v,u) \leq \epsilon$).

$n$ and $k$ are very large numbers, and
comparing two length $k$ vectors is expensive,
we cannot do all brute-force $O(n^2)$ operations.
We want to compute the similarity graph with significantly less operations.

Is this possible?
If not can we compute an approximation to the graph
which contains all edges in the similarity graph
plus possibly at most $O(1)$ other edges?

There may be a way to shoe horn the Johnson-Lindenstrauss theorem into this problem.  Essentially, J-L states that you can project high dimensional data into lower dimensional spaces in such a way that the pairwise distances are nearly preserved.  More practically, Achlioptas has a paper called Database-friendly random projections: Johnson-Lindenstrauss with binary coins that does this projection in a random way, which works pretty well in practice.

Now, certainly, your similarity function is not exactly the same as something that would fit into the J-L theorem.  However, it looks like a distance function and perhaps some of the theory above may help.