Balls and Bins analysis in the $m \gg n$ regime: gaps Suppose we are throwing $m$ balls into $n$ bins, where $m \gg n$. Let $X_i$ be the number of balls ending up in bin $i$, $X_\max$ be the heaviest bin, $X_\min$ be the lightest bin, and $X_{\mathrm{sec-max}}$ be the second heaviest bin. Roughly speaking, $X_i - X_j \sim N(0,2m/n)$, and so we expect $|X_i - X_j| = \Theta(\sqrt{m/n})$ for any two fixed $i,j$. Using a union bound, we expect $X_{\max} - X_{\min} = O(\sqrt{m\log n/n})$; presumably, we can get a matching lower bound by considering $n/2$ pairs of disjoint bins. This (not completely formal) argument leads us to expect that the gap between $X_{\max}$ and $X_{\min}$ is $\Theta(\sqrt{m\log n/n})$ with high probability.

I am interested in the gap between $X_\max$ and $X_{\mathrm{sec-max}}$. The argument outlined above shows that $X_\max - X_{\mathrm{sec-max}} = O(\sqrt{m\log n/n})$ with high probability, but the $\sqrt{\log n}$ factor seems extraneous. Is anything known about the distribution of $X_\max - X_{\mathrm{sec-max}}$?

More generally, suppose that each ball is associated with a non-negative score for each bin, and we are interested in the total score of each bin after throwing $m$ balls. The usual scenario corresponds to scores of the form $(0,\ldots,0,1,0,\ldots,0)$. Suppose that the probability distribution of the scores is invariant under permutation of the bins (in the usual scenario, this corresponds to the fact that all bins are equiprobable). Given the distribution of the scores, we can use the method of the first paragraph to get a good bound on $X_{\max} - X_{\min}$. The bound will contain a factor of $\sqrt{\log n}$ that comes from a union bound (via the tail probabilities of a normal variable). Can this factor be reduced if we're interested in bounding $X_{\max} - X_{\mathrm{sec-max}}$?

Answer: $\Theta\left(\sqrt{\frac{m}{n\log n}}\right)$.

Applying a multidimensional version of the Central Limit Theorem, we get that the vector $(X_1,\dots, X_n)$ has asymptotically multivariate Gaussian distribution with
$$\mathrm{Var}[X_i] = m\left(\frac{1}{n} - \frac{1}{n^2}\right),$$
and
$$\mathrm{Cov}(X_i, X_j) = -m/n^2.$$
We will assume below that $X$ is a Gaussian vector (and not only approximately a Gaussian vector). Let us add a Gaussian random variable $Z$ with variance $m/n^2$ to all $X_i$ ($Z$ is independent from all $X_i$). That is, let
$$
\begin{pmatrix}
Y_1\\Y_2\\ \vdots\\Y_n
\end{pmatrix}
=
\begin{pmatrix}
X_1+Z\\X_2+Z\\ \vdots\\X_n +Z
\end{pmatrix}.
$$
We get a Gaussian vector $(Y_1, \dots, Y_n)$. Now each $Y_i$ has variance $m/n$:
$$\mathrm{Var}[Y_i] = \mathrm{Var}[X_i] + \underbrace{2\mathrm{Cov}(X_i,Z)}_{=\, 0}+\mathrm{Var}[Z] = m/n,$$
and all $Y_i$ are independent:
$$\mathrm{Cov}(Y_i, Y_j) = \mathrm{Cov}(X_i, X_j) + \underbrace{\mathrm{Cov}(X_i,Z) + \mathrm{Cov}(X_j,Z)}_{=\, 0} +\mathrm{Cov}(Z, Z) = 0.$$

Note that $Y_i - Y_j = X_i - X_j$. Thus our original problem is equivalent to the problem of finding $Y_{\mathrm{max}} - Y_{\mathrm{sec-max}}$. Let us first for simplicity analyze the case when all $Y_i$ have variance $1$.

  Problem. We are given $n$ independent Gaussian r.v. $\gamma_1,\dots, \gamma_n$ with mean $\mu$ and variance $1$. Estimate the expectation of $\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}$.

Answer: $\Theta\left(\frac{1}{\sqrt{\log n}}\right)$.

Informal Proof.
Here is an informal solution to this problem (it's not hard to make it formal).
Since the answer does not depend on the mean, we assume that $\mu = 0$. Let $\bar\Phi(t) = \Pr[\gamma > t]$, where $\gamma\sim{\cal N}(0,1)$. We have (for moderately large $t$),
$$\bar\Phi(t)\approx \frac{1}{\sqrt{2\pi}t} e^{-\frac{1}{2}t^2}.$$

Note that

$\Phi(\gamma_i)$ are uniformly and independently distributed on $[0,1]$,
$\Phi(\gamma_{\mathrm{max}})$ is the smallest among $\Phi(\gamma_i)$,
$\Phi(\gamma_{\mathrm{sec-max})}$ is the second smallest among $\Phi(\gamma_i)$.

Thus $\Phi(\gamma_{\mathrm{max}})$ is close to $1/n$ and $\Phi(\gamma_{\mathrm{max}})$ is close to $2/n$ (there is no concentration but if we don't care about constants these estimates are good enough; in fact, they are even pretty good if we care about constants — but that needs a justification). Using the formula for $\bar\Phi(t)$, we get that
$$
2\approx \bar\Phi(\gamma_{\mathrm{sec-max}})\left/\bar\Phi(\gamma_{\mathrm{max}})\right. \approx e^{\frac{1}{2}\left(\gamma_{\mathrm{max}}^2 - \gamma_{\mathrm{sec-max}}^2\right)}.
$$

Thus $\gamma_{\mathrm{max}}^2 - \gamma_{\mathrm{sec-max}}^2$ is $\Theta(1)$ w.h.p. Note that $\gamma_{\mathrm{max}}\approx \gamma_{\mathrm{sec-max}} = \Theta(\sqrt{\log n})$. We have,
$$\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}\approx \frac{\Theta(1)}{\gamma_{\mathrm{max}} + \gamma_{\mathrm{sec-max}}} \approx \frac{\Theta(1)}{\sqrt{\log n}}.$$

QED

We get that
\begin{align}
\mathbb{E}[{X_{\mathrm{max}} - X_{\mathrm{sec-max}}}] &= \mathbb{E}[{Y_{\mathrm{max}} - Y_{\mathrm{sec-max}}}] \\
&= \sqrt{\mathrm{Var}[Y_i]} \times\mathbb{E}[{\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}}] = \Theta\left(\sqrt{\frac{m}{n\log n}}\right).
\end{align}

  The same argument goes through when we have arbitrary scores. It shows that
  $$\mathbb{E}[X_{\mathrm{max}}- X_{\mathrm{sec-max}}] = c\, \left. \mathbb{E}[X_{\mathrm{max}}- X_{\mathrm{min}}]\right/\log n.$$


Complexity reductions to Hamiltonian Path? I am looking for a NP-hardness reduction from an arbitrary problem to the Hamiltonian Path problem such that the reduced no-instances of Hamiltonian path are "far" from having a Hamiltonian path.

Do you know such a reduction? Or does there exist a list of reductions to Hamiltonian Path somewhere?

For undirected graphs, you can build a graph $G$ for every constant $0<c<1$ from an $n$-variate CNF SAT instance $I$ such that

$G$ has $N=\operatorname{poly}(n)$ vertices
If $I$ is satisfiable, then $G$ has a Hamiltonian cycle
If $I$ is not satisfiable, then $G$ has no path of length $N-N^c$.

Karger Motwani Ramkumar 1997

For directed graphs, you can build a graph $G$ for every constant $0<c<1$ from an $n$-variate CNF SAT instance $I$ such that

$G$ has $N=\operatorname{poly}(n)$ vertices
If $I$ is satisfiable, then $G$ has a Hamiltonian cycle
If $I$ is not satisfiable, then $G$ has no path of length $N^{1-c}$.

Björklund Husfeldt Khanna 2004


For which problems in P is it easier to verify the result than to find it? For (search versions) of NP-complete problems, verifying a solution is clearly easier than finding it, since the verification can be done in polynomial time, while finding a witness takes (probably) exponential time.

In P, however, the solution can also be found in polynomial time, so it does not seem obvious when is the verification  faster than finding the solution.  In fact, different problems seem to behave differently from this point of view. Some examples:

3SUM: given $n$ input numbers, find 3 among them that sum to 0. As far as I know, the fastest known algorithm runs in  $O(n^{2-o(1)})$ time, and this order is conjectured optimal. On the other hand, the verification of a solution is much faster, since all we need to do is just to check that the 3 found numbers indeed sum to 0.
All-Pairs Shortest Paths:  given a graph with edge weights, compute its shortest path distance matrix. Once such a matrix is given, can it  be checked faster that it is indeed the correct distance matrix, than re-computing it? My guess is that the answer is perhaps yes, but it is certainly less obvious than for 3SUM.
Linear Programming. If a claimed optimal solution is given, checking it is  easier than re-computing it, when auxiliary information is also given (an optimal dual solution). On the other hand, if only the primal solution is available, it is not clear if one can check it faster, than actually solving the LP.

Question: what is known about this subject? That is, when is it easier to verify a solution for a problem in P, than finding the solution?

it is known that given a graph G and a tree T, it can be verified in linear time that T is a minimum spanning tree of G. But we don't yet have a deterministic linear time algorithm to compute the MST. Of course the gap is tiny (1 vs $\alpha(n)$), but it's still there :))


Mathematical analysis and computational complexity? computational complexity involves large amounts of Combinatorics and number theory, some ingridiences from stochastics, and an emerging amount of algebra.

However, being a analysist, I wonder whether there are applications of analysis into this field, or maybe ideas inspired by analysis. All I know which slightly corresponds to this is the Fourier transform on Finite groups.

Can you help me?

Flajolet and Sedgewick published the book "Analytic Combinatorics" http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html.  I don't know much about that topic, but people in the field use tools from complex analysis.  So far, their applications seem more on analysis of algorithms, not on computational complexity, as far as I see.


Can it be determined if language L lies in NP? Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?

No.  First, by Rice's Theorem, this is a property of TMs that depends only on the language they compute, so it cannot be computable.

But, more than that, it is known that the index set of $NP$ (that is, the set of TMs that compute languages in $NP$) is $\Sigma^0_3$-complete ($\Sigma^0_3$ in the arithmetic hierarchy of computability, not the polynomial hierarchy).

Questions like this were first investigated by Hajek.  For more, see e.g. this article by Ken Regan.

A few more great nuggets from Hajek's paper:

The index set of $P$ is $\Sigma^0_3$-complete.
$\{i : P^{L(M_i)} \neq NP^{L(M_i)}\}$ is $\Pi^0_2$-complete
There is a total Turing machine (halts on all inputs) $M_i$ such that $P^{L_i} = NP^{L_i}$ but the statement "$P^{L_i} = NP^{L_i}$" is independent (where $L_i = L(M_i)$).  Similarly for relativizations where $P \neq NP$.


Proof that sparsest cut is NP-hard Everywhere that I read about the sparsest cut problem, it only says that the problem is known to be NP-hard. Where can I find a proof of this? Which known NP-hard problem reduces to the sparsest cut problem?

I could not find any proof in Vazirani's book - Approximation Algorithms, which presents the Leighton Rao algorithm, or the book "Computers and Intractability" - which summarizes many NP-complete problems. I could not find it by searching (with obvious search strings) on Google.  There is one paper by Chawla et al, which assumes Khot's UGC conjecture and proves the hardness of approximating the sparsest cut. I was hoping to see a proof that does not assume any conjecture.

The proof should just reduce a known NP-hard problem to sparsest cut.

Thank you,

Arpita Korwar.

[Moved from comment]

The paper "Sparsest cuts and bottlenecks in graphs" by David W. Matula, Farhad Shahrokhi gives a reduction from max-cut problem. Max-cut's proof of hardness can be found in Garey Johnson.


Random Cerny Conjecture For simplicity, all DFAs will be using the binary alphabet $\{0,1\}$. Let $M$ be a synchronizable DFA. We let $p(M,n)$ be the probability that a random $x\in \{0,1\}^n$ will synchronize $M$.
We define $P(k,n)$ to be the minimum of $p(M,n)$ taken over all DFAs $M$ having $k$ states. I want to know asymptotic bounds for $f$ such that $P(k,f(k)) \to 1$ exponentially fast (so there is  $c <1$ such that $P(k,f(k))>1-c^k$ asymptotically). I know how to prove that $f(k) = k^42^{k^2}$ suffices. For any two states in a DFA, there will exist a string with length at most $k^2$ which synchs the two states, thus the probality that $k^2 2^{k^2}$ random bits will not synchronize a new pair of states is at most $1/e$. The rest quickly follows.
Can this upper bound be improved? What kind of lower bounds are possible?

I think this problem has little to do with Cerny's conjecture. There the problem is to find a word that works for every pair of states. Here it is enough to show that the word will work whp. for any pair of states.
An exponential lower bound on $f$ can be given as follows.
Take a DFA whose states are $v_1,\ldots,v_k$ and the transition function is such that reading a 1 we go ahead by one until we reach the end, i.e., $\delta_1(v_i)=v_{i+1}$ for $i<k$, while $\delta_1(v_k)=v_k$, but if we read a 0 before the end we have to start all over again, i.e., $\delta_0(v_i)=v_1$ for $i<k$, while $\delta_0(v_k)=v_k$.
If the initial states are $v_1$ and $v_k$, then the question is how fast we reach the terminal state in this simple Markov-chain; in expectation this is about $k2^k$.


Why is CNF used for SAT and not DNF? I don't quite understand why almost all SAT solvers use CNF instead of DNF. It seems to me that solving SAT is easier using DNF. After all, you just have to scan through the set of implicants and check whether one of them contains not both a variable and its negation. For CNF, there's no simple procedure like this.

The textbook reduction from SAT to 3SAT, due to Karp, transforms an arbitrary boolean formula $\Phi$ into an “equivalent” CNF boolean formula $\Phi'$ of polynomial size, such that $\Phi$ is satisfiable if and only if $\Phi'$ is satisfiable.  (Strictly speaking, these two formulas are not equivalent, because $\Phi'$ has additional variables, but the value of $\Phi'$ doesn't actually depend on those new variables.)

No similar reduction from arbitrary boolean formulas into DNF formulas is known; all known transformations increase the size of the formula exponentially.  Moreover, unless P=NP, no such reduction is possible!


Lipschitz composable compressor Def. We call $C: \mathbb R^d \to \mathbb R^d$ a $\delta$-compressor (or contractor) if for all $x$
$$\|C(x) - x\|^2 \le (1 - \delta) \|x\|^2$$
Intuitively, $C(x)$ is not too far from $x$. Note that $\delta$ can be pretty small, e.g. $\frac 1d$.
Def. For a fixed $n$ we say that function $f$ is $\alpha$-composable if there exist functions $g$ and $h$ such that for any $x_1, \ldots, x_n$ we can represent each of $f(x_1 + \ldots + x_n)$, $g(x_1), \ldots, g(x_n)$ using $\alpha$ bits and
$$f(x_1 + \ldots + x_n) = h(g(x_1), \ldots, g(x_n))$$
Intuitively, we have $n$ machines, we send $g(x_i)$ from each machine to the coordinator which computes the answer and sends it back to the machine. Moreover, for each machine (except of the coordinator) the total communication is $O(\alpha)$. The definition above was my attempt to capture this intuition, so it's possible that it's not the best one.
For $\alpha$-composability, we may also allow a polylogarithmic number of rounds to compute the answer. I.e. for $k  = polylog$ of all parameters we can have functions $h_1, g_1, \ldots, h_k, g_k$, so that in $j$-th round $g_j(x_i, h_0, \ldots, h_{j-1})$ are sent to coordinator, $h_j$ are sent back to the machines and $h_k$ must compute $f(x_1 + \ldots + x_n)$.
In both definitions, functions can be randomized. In this case, the properties must hold in expectation. All $g$ are allowed to share randomness in any way.
For example, "Communication-efficient distributed SGD with Sketching
" describes a $\tilde O(k)$-composable $\frac kd$-compressor. The main idea is to use count sketch to find heavy hitters.
Question: Does there exist a function with the following properties:

It is a $\frac cd$-compressor for some constant $c$.
It is $\tilde O(1)$-composable ($\tilde O(1)$ means polylogarithmic on all parameters)
It is Lipschitz, i.e. for some constant $L$ we have $\|C(x) - C(y)\| \le L \|x - y\|$ for all $x, y$. For randomized function, we only need Lipschitz property with respect to $x$, i.e. $\|C(x, \theta) - C(y, \theta)\| \le L \|x - y\|$ for all $x,y,\theta$, where $\theta$ is a randomness-controlling parameter and in the inequality above it's the same for $x$ and $y$.

Some weaker results (e.g. good $\frac 1 {\sqrt d}$-compressors) are also appreciated.
My thoughts: It shouldn't be possible even when we weaken $\alpha$-composability requirement to the following: "For all $x$, $f(x)$ can be stored using $\alpha$ bits". Intuitively, I expect that any such compressor must be of a heavy hitter type, and such compressors are not Lipschitz.
The composability definition essentially restricts possible solutions to linear sketches, and count sketch seems to be the only feasible solution, but, unfortunately, a corresponding compressor is not Lipschitz. However, if we allow multiple communication rounds, it's not that clear anymore.
Any ideas how to approach this are appreciated. I suspect we should leverage some communication complexity technique, but I don't know which one.

It turns out that there is a simple answer: $O(k)$-composable $\frac kd$ compressor (in expectation) just returns $k$ random coordinates. The proof is trivial and can be found in Stich et al., "Sparsified SGD with Memory", Section A.1


What do people mean by capabilities and capacities? Someone made a casual remark to me about the terminology of capabilities and capacities, in the context of threads, processors and runtime systems, particularly their theoretical modelling.

For example, in Haskell, an OS thread that is started to schedule work for a single logical processor (hardware thread) is called a capability. Where does this terminology come from? I'm not sure what it really means.

The person who made the casual remark thought that there is also the related concept of capacities, but neither of us are sure.

Anyone know about this? Or have any references for me?

A comment in capability.h says

// The Task currently holding this Capability.  This task has
// exclusive access to the contents of this Capability (apart from
// returning_tasks_hd/returning_tasks_tl).

This looks to be an access control mechanism.

In the security literature, the word capability is used to refer to a way of controlling access.  The dominant usage is as a reference to an object that encapsulates authority such that denying access to the object denies access to that authority but there are others as explained at "Capability Myths Demolished"

  We know of no security mechanisms outside  of the
  object-capability model that have described themselves
  using the word capability except for “POSIX
  capabilities”, “Netscape capabilities”, and “split
  capabilities” [14]. POSIX capabilities are not generally
  described as “capability-based security”. The
  “Netscape capabilities” extensions to Java were fairly
  short-lived and have not been presented in the research
  literature as a capability system. Moreover, both
  “POSIX capabilities” and “Netscape capabilities” have
  never been presented as security mechanisms that can
  stand on their own, instead only serving as an extension
  to existing security systems. The split capabilities
  model is explicitly presented in contrast to the pure
  capability model [14].

The Haskell usage is not an object-capability model.  The pointer from a task to a capability would have to go the other way, and probably be proxied through a revokable wrapper to qualify as a capability in the sense explained above.


Tree width of a particular graph What is the tree-width of the graph $G = (V_1 \cup V_2 \cup \dotsb V_n, E)$ where  the connected components of an induced subgraph of any neighboring set of vertices (i.e. $G[V_i \cup V_j], i = j - 1$) are complete bipartite graphs? Here is an example.

It is clear the entire graph $G$ is bipartite, and showing the tree-width of bipartite graphs is $\mathcal{NP}$-Hard in general, but I was curious if this added enough structure to the problem to make it tractable. For instance, we can easily find the largest bipartite clique just by finding a vertex with maximum degree, then finding its neighbors (and their predecessors).

The problem is still NP-complete. Here's a reduction from the Treewidth problem on general graphs. Recall that for a graph G of treewidth at least two, the treewidth is not affected when subdividing an edge by a degree-2 vertex (i.e. replacing an edge $\{u,v\}$ by a new vertex $x$ and edges $\{u,x\}$, $\{x,v\}$ ).

Given an input graph $G$ on $n$ vertices, assume without loss of generality that it has treewidth at least two (otherwise we can solve the problem and output an equivalent constant-sized instance). Number the vertices of G from $1$ to $n$, in some arbitrary order. Now assign vertex $v_i$ to set $S_{2i}$, and observe that trivially, each set $S_i$ induces an independent set in the graph; we will maintain this during the following process. As long as the graph has an edge $\{u,v\}$ between two vertices which are not in adjacent sets, say an edge between a vertex in $S_i$ and one in $S_j$ for $i < j$ and $j-i > 1$, subdivide the edge, placing the newly created degree-2 vertex in set $S_{i+1}$. Since this subdivider vertex is placed between the endpoints of the subdivided edge, it decreases the difference between the indices of the sets that its neighbors are in, and therefore each edge of the original graph is subdivided no more than $n$ times. So  this process terminates after a polynomial number of steps. The resulting graph $G'$ was made from G by repeatedly subdividing edges, so its treewidth equals that of G. Let us verify that the resulting sets satisfy that all connected components of $G'[S_i \cup S_{i+1}]$ are bicliques. One of the indices $i, i+1$ is odd. By construction, the set for this odd index contains only degree-2 vertices which were added to subdivide an edge. Since the subdivider vertex was placed "in the gap between its two neighbors", each degree-2 vertex has one neighbor in the previous set, and one neighbor in the next set. So the set out of $S_i, s_{i+1}$ with odd index has only vertices which have degree one in the graph $G'[S_i \cup S_{i+1}]$, which shows that the graph is a disjoint union of stars which are bicliques. So the graph G' has treewidth equal to G, size polynomial in that of G, and can be constructed in polynomial time. Since treewidth is NP-complete, so is the restriction to your special graph class.


Monotonicity in data flow analysis I am studying program analysis and synthesis, I was reading a presentation
about some data flow analysis.

I can't seem to understand why $$\bigcap_{s'\in\text{pred (s)}}\text{Out}(s')$$
and $$\operatorname{Gen}(s)\cup(\operatorname{In}(s)\setminus \operatorname{Kill}(s))$$ is monotone, as claimed in
slide 22.

I don't even understand exactly what is the function that is claimed to be monotone.
Can anyone please help ? any help is greatly appreciated!

*This was cross-posted on Math.SE a couple of days ago

You need to identify the lattices involved in each case.

Let $(\wp(S),\subseteq)$ be the lattice of all subsets of a set $S$ ordered by subset inclusion. A function $f:\wp(S) \to \wp(S)$ is monotone if for every pair of sets $x$ and $y$, if $x \subseteq y$ it also holds that $f(x) \subseteq f(y)$. The definition applies more generally to functions $f: L \to M$ between partially ordered sets $L$ and $M$.

Let $Stmt$ be the set of statements occurring in a program and let $(\wp(Stmt),\subseteq)$ be the lattice of subsets of statements ordered by subset inclusion. Let us assume for simplicity that a statement in $Stmt$ is either an assignment $x:= e$ or a Boolean expression $b$ (representing the entry of a conditional or head of a loop).

A control flow graph has the form $G = (Stmt,E)$ where $E$ is an edge relation over statements. The following definitions are extremely standard:

$succ: \wp(Stmt) \to \wp(Stmt)$ maps a set of statements to their successors.

$succ(X) = \{ y \in Stmt | \text{ there exists } x \text{ in } X \text{ such that } (x,y) \text{ is in } E\}$

$pred: \wp(Stmt) \to \wp(Stmt)$ maps a set of statements to their predecessors.

$pred(X) = \{ y \in Stmt | \text{ there exists } x \text{ in } X \text{ such that } (y,x) \text{ is in } E\}$

It is a standard exercise to show that these are monotone functions.

Consider the set $Exp$ of all arithmetic and Boolean expressions occurring in a program. The structure $(\wp(Exp),\subseteq)$ is a lattice with the subset inclusion order.

For the available expressions analysis, we can define two functions $Gen$ and $Kill$ in two steps as follows.

First define $Gen: Stmt \to \wp(Exp)$ as a function that maps a statement to the set of expressions generated by that statement. We can define $Gen$ inductively and lift it to sets as follows.

$Gen(x := e) = \{e\}$ and  $Gen(b) = \{b\}$

The lifted function $Gen: \wp(Stmt) \to \wp(Exp)$  is obtained in a standard manner by taking the union of $Gen$ sets for every statement in a given set.

$$ Gen(S) = \bigcup_{s \in S} Gen(s) $$

You can now ask whether this function is monotone.

A note about the slides

The slides you are studying do not contain sufficient information to deduce everything I have said here from first principles and I doubt they are meant to be read that way. I would consult the lecture notes or the section on data flow analysis in a  standard compilers textbook for a thorough treatment with complete definitions.


Sum From A List Of Numbers (Algorithm) I came upon a problem and have been trying to find a method more efficient then brute force, but I came up with nothing; and I am not even sure how to approach it...

You have a list of numbers and a target number all of which are positive and can have decimals. You must add the numbers in the list to get as close as possible to the target value without overshooting. Each number in the list can be used any number of times including not at all. The solution is the closest number that uses the least total numbers. To be clear, the least total numbers only applies when there are two identically close solutions.

It isn't very hard to make a program that checks every possible combination, but is there a way to make it more efficient?

The problem is NP-Complete even for integer values. You can look up the "knapsack problem" to see why.

A pseudo-polynomial algorithm exists if you can map your N values to integers (if the number of decimal places are bounded by some constant)


Exhibits for a Museum of Computing All of the computer-related museums and exhibits I'm aware of seem to only cover the history of computing machinery, but nothing on topics of computer science.

You are involved in the creation of a new Museum of Computing, chartered to educate, entertain, and inspire the general public in a wide variety of computing/computer science/communication/mathematics topics.  Though history and celebrity can be part of the exhibits, this is not a history museum.  Instead, visitors learn about timeless concepts that enable computing, from the hardware layer on up.  Budget is not specified but ideas should be durable and practical for high volumes of visitors in permanent installations, with minimal staffing/disposable materials similar to the world's best science centers.

What exhibits would you include?

Scott Aaronson addresses this particular question on his blog Shtetl-Optimized when considering the timeline of Computer Science. The relevant posts in chronological order:

Timeline of Computer Science

Top 150 computer science events to be decided once and for all

CS timeline voting: the results are in!

Most of the events in his list would make good exhibits, although it might be difficult to figure out how to present some of them physically.


Quantum approximation algorithms It is generally considered unlikely that quantum computers will be able to solve NP-complete problems efficiently. In the classical case one approach to tackle such problems is to use approximation algorithms. Has there been any research on approximation algorithms using quantum computing where quantumness gives significant speedup over classical approximation methods?

By "significant" I mean not necessarily exponential, but greater than for corresponding exact algorithms. In other words, I'm interested if relaxing the requirement that our algorithm yields the exact solution gives a significant advantage to quantum algorithms.

A comment upgraded to partial answer:

There is quite some work these days on a conjectured (or not) quantum version of the PCP theorem: see for example this blog post by Scott Aaronson
http://www.scottaaronson.com/blog/?p=139
or this answer by Peter Shor on MathOverflow
https://mathoverflow.net/questions/45106/quantum-pcp-theorem/45167#45167

Concerning quantum approximation alpgorithms, you can look at this reference "Approximation algorithms for QMA-complete problems"
http://arxiv.org/abs/1101.3884


Langton's ant highway conjecture and undecidability I was recently reading about Langton's ant and the related conjecture which states that for every initial configuration, the ant eventually starts building a 'highway'.

I also read that it has been shown that Langton's ant can be used to simulate any boolean circuit thus the ant is capable of universal computation.

But I am confused by those two facts because if the conjecture is true, then every computation performed by the ant will eventually end up to a highway which is easily detectable thus making any problem related to Langton's ant decidable. But how can this be true if Langton's ant is computationaly equivalent to a Turing machine for which there exist many undecidable problems?

I also read this paper and it specifically says in section 1.2: "If the conjecture is true, then any problem associated to the ant, whose input is an initial configuration with finite support, is decidable" whereas in section 1.3 it states: "There are undecidable problems associated to the behavior of the ant."

I suspect that my confusion on the matter has something to do with the finiteness/infiniteness of the input since in section 4 of the previous paper it says that Langton's ant universality is "a rather weak notion of universality (which requires an infinite - but finitely described - configuration)" which I'm not entirely sure I understand.

So my question is what's wrong with the above reasoning which suggests that the highway conjecture should be false (otherwise there would be no undecidable problems)?

From the comment: the undecidable questions are related to initial configurations with infinite support, whereas the conjecture refers to the behaviour of the ant when starting from a configuration with finite support (all but a finite number of cells are in the same initial state). If the conjecture is true then there are no undecidable problems starting from a finite support: just stop when the ant starts building the highway towards empty space.


Construction of graph embeddings with non-intersecting edges I have a bipartite graph whose genus $g$ I know. I have a genus $g$ real surface(a $g$-holed donut). I want to construct a graph embedding on the surface so that I have no intersecting edges. Has this problem been studied before?

That is given a genus $g$ bipartite graph, provide an explicit algorithm that can embed the graph in a non-intersecting manner on to a real surface with $g$ handles.

Is there any notion of equivalence of embeddings of graphs on surfaces? If so, given a genus $g$ graph, in how many non-equivalent ways can one do the embedding?

There is a "simpler" algorithm to check embeddability of graphs in surfaces of genus g.
See this paper.

Having a bipartite graph does not help. From any graph we can obtain a bipartite version by subdividing each edge once. The embeddability of the new graph and the original one is the same.


Is it conceivable at all that the standard model of physics can outperform a quantum computer in any sense? The Standard Model of physics (the mathematical model which predicts the Higg's boson) is, as far as I understand, our most complete model of the universe. That is to say, it is the best description of the mathematical game to be played to make predictions on the outcome of  experiments performed in our Universe.

As I understand it, quantum physics, used to create models of quantum computation (as used, for example, in the construction of Shor's algorithm) is a mathematical game contained within the Standard Model. Thus, in this sense the Standard Model is a generalization of quantum physics.

Is it at all conceivable that the Standard Model can allow for the construction of more general Standard Model computers? Or is there an obvious reason why quantum physics extracts all the benefit modern physics brings over classical models of computation and thus computer scientists should only reason according to quantum physics? Has any fundamental work been done on this? Is my question even well posed? Supposing that a Standard Model of physics computer could be a well-posed mathematical object more general than quantum computers, is there any reason at all to think that there could be any use to reasoning about that? Has there been any work done related to this question?

More informally, you might think of this question as something of the form "could we make a 'Higg's Boson' computer?" a rather natural justification for research in particle physics. Note that I know very little of the Standard Model (but a good deal about quantum physics) so this question might be ill posed, and if so, knowing that would be a clarification of my understanding.

If quantum computers can simulate in polynomial time the Standard Model, which is a quite complicated quantum field theory, then probably the Standard Model does not provide any extra computational power beyond BQP. Simulating quantum field theories with a quantum computer is not an easy task, but a start has been made by this paper by Jordan, Lee, and Preskill, which shows how to simulate in polynomial time a much simpler quantum field theory than the Standard Model.


Largest rectangle not touching any rock in a square field Following this mathematical question, I am interested in the algorithmic question:

  Given $n$ points in the unit square,
  find the largest area of an axis-parallel rectangle in the unit square
  that does not contain any of the given points in its interior.

What is known about this problem?

There is an $O(n \log^2 n)$ time algorithm. [Aggarwal and Suri 87]
It seems to be the state of the art.


Step-indexing: Where to begin? I am about to begin a verification project (for MIPS)  with my professor (I am a senior undergraduate) and have been told that the soundness proof for the program logic we need will probably involve step-indexing. I have read the Very Modal Model paper by Appel et al. and after a short tutorial by my prof, I think I have a basic understanding of step-indexing. However it has been kind of slow going. Especially when the $\mu$ operator and contravariance come up.

I would like to ask for either the original papers where step-indexing was introduced (from what I understand it traces back to the 50-60s? but am having trouble finding them) or if someone can point out a tutorial, that would also be great.

Amal Ahmed's very readable thesis dissertation could be a nice start.


Density of semantics in syntax Let $L$ be a programming language, and $\cong$ a notion of equality of $L$-programs (in general $\cong$ will be undecidable).  Let $syntax(n)$ be the number  of $L$-programs of size $n$ (for some reasonable notion of program  size), and $semantics(n)$ denotes the number of $\cong$-equivalence  classes of $L$-programs of size $n$. Now define
$$  density(n) = semantics(n)\ /\ syntax(n)$$
So $density(n)$ tells us how many really distinct programs we can
write of size $n$. What is known about the limit:
$$   \lim_{n \rightarrow \infty} density(n)?$$
I conjecture that $\lim_{n \rightarrow \infty} density(n) = 0$ for
reasonable choices of $L$ and $\cong$, since the larger programs are
allowed to be, the more room for redundancies like $M+N \cong N+M$.
Question. What is related work this direction?

In terms of related work, Marek Zaionc and collaborators have been studying similar kinds of questions for some time.  The following paper includes many results:

René David, Katarzyna Grygiel, Jakub Kozic, Christophe Raffalli, Guillaume Theyssier, Marek Zaionc.  Asymptotically almost all λ-terms are strongly normalizing.  Logical Methods in Computer Science, Volume 9, Issue 1 (February 15, 2013). arXiv

The result stated in the title is not exactly the same as the one you are asking about, but related: they prove that the asymptotic density of strongly normalizing terms among all terms of $\lambda$-calculus is 1.  Surprisingly, they also prove that the asymptotic density of strongly normalizing SKI combinator terms among all SKI combinator terms is 0.
As suggested by Gabriel Scherer's response, the specific formulation of density you are asking about is related to the density of normal terms among all terms, or in other words the probability that a uniformly random term of a given size is already normalized.  For subsystems of $\lambda$-calculus the probability that a term is normal typically decreases exponentially with size, and I believe it should be a small step from there to proving that the asymptotic density you are interested in is 0.  Certainly this is true for linear $\lambda$-terms: since normalization cannot increase the size of a term, the number of equivalence classes of terms of size $n$ is at most $n$ times the number of normal terms of size $n$, hence the ratio of equivalence classes to terms is asymptotically 0.


On the size of P4-transversals of graphs A subset $T$ of vertices of a graph $G$ is called a $P_4$-transversal if $T$ intersects every $P_4$ of $G$. In the context of this question, we consider $P_4$ as an induced path on 4 vertices.

Conjecture :
Given a graph $G$ of $n$ vertices, the minimal $P_4$-transversal of G is of at most $\frac{n}{2}$ vertices.

We consider gneral simple graphs here. However, any results of subclasses of simple graphs are welcome.

Thoughts:
$P_4$-transversal can be seen as a special case of hitting set of sets of size 4. However, for general hitting set of 4-sets (i.e., 4-uniform hypergraph) on $n$ vertices, the minimum hitting set can be as large as $n-3$.

The original version of this question guessed the upperbound of the size of $P_4$-transversal as $\frac{n}{3}$. Thanks to the comments from R B and Jim Nastos, we have an example on 16 vertices and whose minimal transverval has 7 vertices.

Introduction and why I am interested in $P_4$-transversal of graphs.

Study of $P_4$-transversal is a part of study of $P_4$-structures of graphs, which plays an important role in the "Strong Perfect Graph Theorem". $P_4$-transversal of perfect graphs and chordal graphs were studied in perfect graph and chordal graph.

$P_4$ is a path of 4 vertices. A $P4$-free graphs is called a cograph, which is the minimal family of graphs generated from $K_1$ and complementation and disjoint union. Therefore, $P_4$ structures seems to be an interesting and important property of graphs.

Let H be any graph on N vertices and requires T vertices in a P4-transversal (so its ratio is T/N).
Construct G like in the previous examples: G is a P4 but substitute an H in for each vertex. Then the total number of vertices of G is n = 4N and the transversal size is N + 3T.

This gives a ratio of (N+3T)/4N = (1/4) + (3/4)T/N

So, the last example I gave in the comment of Peng Zhang's answer used H = $P_4$ with T/N = 1/4 and the ratio was 1/4 + 3/16 = 7/16.

Now use that 7/16 graph in for H and construct G. This uses 64 vertices, and the transversal size is 16 + 3(7) = 37. We get a ratio of (1/4) + (3/4)(7/16) = 16/64 + 21/64 = 37/64 which is already over 50%.

This seems correct to me (in that I don't see what is wrong with it) but it is troublesome, because repeating this process will get to a fixed point x = (1/4) + (3/4)x , which is x=1.0 (?)

Thoughts...?


Discharged hypotheses in ->Introduction I have a question about page 9 in Proofs and Types.

The given $\rightarrow$Introduction rule says that $A \rightarrow B$ can be deduced from $B$ if the deduction of $B$ contains an arbitrary number of $A$s (0 or more).  How can this be true if there are zero $A$s in the deduction of $B$?

Dave Clarke's answer basically says it all: this is the standard convention in classical and constructive mathematics.  Nonetheless, your objection is the source of a century-old subdiscipline of philosophical logic called "relevance logic", which can be seen as rejecting the axiom p → (q → p) -- or in terms of natural deduction, rejecting precisely this ability to use a hypothesis zero times, or equivalently in terms of sequent calculus, rejecting the structural rule of weakening. Reconsidering other structural rules/axioms leads more generally to substructural logics, which have found applications in linguistics and theoretical computer science.  (One important example, linear logic, is mentioned in the appendix to Proofs and Types.)


Internal Regret in Online Convex Optimization Zinkevich's "online convex optimization" ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) generalizes "regret minimization" learning algorithms from a linear settings to a convex setting and gives good "external regret".  Is there a similar generalization for internal regret?  (I'm not totally sure even what exactly that would mean.)

Try "No-regret learning in convex games" by Gordon, Greenwald and Marks http://portal.acm.org/citation.cfm?id=1390202 . Its abstract sounds like it probably answers your question, or at least anyone answering that question would cite or be cited by that paper.


M-clique covers in complete graphs Let us consider a complete weighted graph, with $NM$ nodes.
Our objective is to find, among all possible combinations of $N$ disjoint $M$-cliques (each clique consisting of $M$ nodes), the configuration that maximizes/minimizes the sum of the $N$ $M$-cliques weights.
Here the weight of a $M$-clique is the sum of the edge weights between all the $M$ nodes composing the clique.

It sounds like a classical mathematical problem, but I have been spending hours without finding anything.
The special case where $M=2$ consists of a maximal weighted matching problem in a complete graph and can be solved using Edmonds Matching Algorithm, but I can't find anything for $M>2$.

Is there an efficient algorithm for this problem?

This problem is NP-hard.  As proof, the maximal clique problem (or rather the decision variant find-a-K-clique) can be reduced to this problem as follows.

Start with a problem on a graph with N vertices where we wish to find a clique of size K.  The set containing these original vertices we'll call S. Add a clique (we'll call it C) of size (N - K)*K which is joined to every vertex in S.  Additionally, adjoin one more vertex V which is joined only to the vertices in S (not the ones in C).

Now we have an instance of your problem (never mind the edge weights) where we want to divide the resulting graph up into N - K + 1 cliques of size K+1.  I claim that there is a solution to this problem if and only if there is a clique of size K in the original graph.

only-if follows from the fact that V must belong to some clique of size K+1 which is only the case if there are K vertices which form a clique in S.

Furthermore, there will be enough leftover nodes in C that every S-vertex not in the solution clique can be assigned to a separate set of K vertices from C.  So once we've managed to find a clique for V, finding the other N-K (K+1)-cliques is always possible (and indeed trivial).

So taking "efficient" to mean "polynomial time", then the answer to your question is "no", or more precisely, "only if P = NP"


Site with collection of exercises in TCS? Is there a website with a large collection of exercises for theoretical computer science, sorted by topics? I know that many exercises can be found in different textbooks, I'm looking for an online database, preferably with hints/solutions included.

100 exercises in the theory of automata and formal languages

https://algomuse.net/
It's a kind of competition but problems are from research papers.

Here http://www.openproblemgarden.org/
Some problems have hints.

https://a3nm.net/work/research/questions/#other-lists-of-open-problems

In this book, each chapter have some exercise:
https://files.boazbarak.org/introtcs/lnotes_book.pdf


Survey on Quantum error correction Are there any standard recent survey articles on quantum error correction (and may be including fault Tolerant computing)? The most standard ones that many people refer to are this and this. Both of them being relatively old, are missing some standard things such as Surface codes, codes comng from homology or LDPC codes. I am looking for survey paper giving indication of currently where do we stand.

Try these:
Quantum Error Correction by Todd Brun
Quantum Error Correction: An Introductory Guide by Joschka Roffe
For surface codes, Dan Browne's lecture notes might help.


How do you decide when you have enough research results to write a paper and to which journal you submit the paper In some research area in CS we got some very interesting results. Now we are thinking about publishing them. In the group we are, the philosophy is to publish inmediately small things in conference papers, which is ok but not the best. Now I am thinking about collecting more of these "small things" and publish in a JCR paper, impact factor more than 2. My question here is how would you decide when you have enough material to prepare a decent paper in a JCR journal? And furthermore, once you think this is ok, how would you decide to which journal you submit the paper to?

PS: JCR refers to Journal Citation Reports, an extensive list that collects info about the most representative and relevant journals in all scientific areas along with their impact factors, so they are usually refereed and no conference papers there

JCR is part of the ISI Science Citation Index family of databases, which is not especially reliable in its measurement of computer science impact. See for instance this report from Informatics Europe which specifically warns against using ISI databases to measure the impact of computer scientists.

In any case, if you want your papers to get attention from other computer scientists, publication in selective conferences is still the way to go. We can argue whether it should be, but that's what it is. Some conferences (e.g. SIGGRAPH) count as a journal directly (their proceedings are published as a special issue of a journal), others (e.g. FOCS/STOC/SODA) expect their authors to later turn the same material into an expanded and more polished journal paper, but the conference is to a large extent how to signal other researchers that your work is worth paying attention to. If you're not familiar with the conferences in the area, choosing one sponsored by ACM or IEEE over one that isn't is a good rule of thumb, as is choosing one that calls itself a "symposium" over one that calls itself a "workshop".

However, that doesn't mean that you have to partition your work into least publishable units as you describe your coworkers doing, and it also doesn't mean that saving up multiple small results into a single paper is a good way of making your papers stronger. It's certainly possible to publish papers like that but to my mind the better ones are often the ones that have a single strong main result, perhaps with additional results on the side not to strengthen the paper but rather to provide more complete coverage of its subject.


Ordering of a DAG minimizing some definition of cost Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the cost of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i
\mid \exists k>i: (v_j,v_k)\in A\}|$.
The problem is: given a DAG, find a topological ordering with minimum cost.

In other words, for each $i$, I consider that a vertex that appeared before $i$ is pending if it still has one or more out-neighbours that did not appear yet, and I want to minimize the maximum number of pending vertices at any time.

It looks like some graph measures (say treewidth, etc.), but I didn't manage to find this in the literature. Has it been studied before?

I'd say it's almost-certainly NP-hard (although I don't have a proof)... would there be any approximation algorithm, or at least some smart heuristic?

Edit: for a little bit of context. This came up while I was trying to program a tool solving a completely unrelated string problem. To make things short: the graph models my input, and I need to compute a set of strings $\mathcal S(v)$ for each node $v$. To compute each $\mathcal S(v)$, I need to know $\mathcal S(u)$ for each node $u$ with an arc $u\rightarrow v$. In the end I'm only interested in $\mathcal S(v)$ for the targets of the graph. Now I want to improve the memory needs: the sets $\mathcal S$ are huge, so I want to keep only a minimum number of them in memory at any time: they correspond to the "pending vertices" defined above.

This problem is NP-complete, as the following reduces to it:
https://cstheory.stackexchange.com/a/1936/419

The sketch of the reduction is as follows.
From a set of tasks $T$ with $n$ tasks and some costs (not to be confused with your cost function!), we will make a DAG that has $N$ indegree 0 vertices (sources), and $N$ outdegree 0 vertices (sinks), where $N$ is some big ($poly(n)$ size) number to be specified later.
The DAG will also have an indegree $N$ vertex that has to come right after the sinks, and, similarly, an outdegree $N$ vertex that has to come right before the sources.
For each task, we have a vertex that must be between the indegree $N$ vertex and the outdegree $N$ vertex by adding an edges from and to them, respectively.
This achieves that the task-vertices are not mixed with the sources and sinks.

Finally, for every task $t$ with a positive cost $c(t)$ we add $nc(t)$ edges from some sources, and for every task $t$ with a negative cost $c(t)$ we add $nc(t)$ edges to some sinks.
This achieves that the edges between the tasks won't matter, only the costs will determine the thickness cost that you've defined.

I don't know anything about approximation and heuristics.


Random walk and mean hitting time in a simple undirected graph Let $G=(V,E)$ be a simple undirected graph on $n$ vertices and $m$ edges.

I'm trying to determine the expected running time of Wilson's algorithm for generating a random spanning tree of $G$. There, it is shown to be $O(\tau)$, where $\tau$ is the mean hitting time: $$\tau = \sum_{v \in V} \pi(v) \cdot H(u, v), $$ where:

$\pi$ is the stationary distribution $\pi(v)=\frac{d(v)}{2m}$,
$u$ is an arbitrary vertex, and
$H(u,v)$ is the hitting time (AKA access time), i.e., the expected number of steps
before vertex $v$ is visited, starting from vertex $u$.

What is the general upper bound for the mean hitting time? And what is the worst case graph $G$ that maximizes mean hitting time?

To make my question clear, I don't require calculations or a detailed proof (although they may be useful to other people encountering this question in the future). For me personally, a citation would be sufficient.

The paper mentions another algorithm by Broder that works in expected cover time (first time when all vertices have been visited). Then it is said, that mean hitting time is always less than cover time. However it only gives an asymptotic bound of $\Theta(n)$ for most graphs (i.e., expander graphs) to contrast it with $\Theta(n \log n)$ by Broder for most graphs (with a somewhat more inclusive definition of most).

It does give an example of a graph where mean hitting time is $\Theta(n^2)$ and cover time is $\Theta(n^3)$. While this is known to be the worst case for the latter, he does not specifically say anything about the worst case of the former. This would mean that the worst case for Wilson's algorithm may fall anywhere between $O(n^2)$ and $O(n^3)$.

There are two publicly available implementations of Wilson's algorithm that I'm aware of. One is in the Boost Graph Library, while second is in graph-tool. Documentation of the former does not mention running time, while the latter states:

  The typical running time for random graphs is $O(n \log n)$.

Which does not answer the question, and actually seems to be inconsistent with Wilson's paper. But I report this just in case, to save time of anybody with the same idea of consulting implementation documentation.

I had initially hoped that the worst case might be attained by a graph constructed by attaching a path to a clique, due to Lovász, where the hitting time can be as high as $\Omega(n^3)$. However, the probability of this event is about $\frac{1}{n}$ when picking vertices from stationary distribution. Consequently yielding an $O(n^2)$ bound for the mean hitting time in this graph.

A paper by Brightwell and Winkler shows that a subset of lollipop graphs maximizes the expected hitting time, reaching $4n^3/27$. Graph by Lovász is also a lollipop graph, but in this case the clique size is $\frac{2}{3} n$, rather than half. However, care must be taken not to confuse expected hitting time with mean hitting time. This result, like the previous one, refers to expected hitting time for two specific vertices chosen beforehand.

I have decided to ask David Wilson himself, soon thereafter got a reply:

  For undirected graphs on $n$ vertices, the worst case mean hitting time is $\Theta(n^3)$. The example is the barbell graph, which consists of two cliques of size $n/3$ connected by a path of length $n/3$. I don’t know what the worst constant is. The [Brightwell-Winkler] paper looks at (expected) hitting times $H(x,y)$ started at $x$ and ending at $y$.  The mean hitting time is the average of $H(x,y)$ for fixed $x$ and random choices of $y$ from the stationary distribution of a random walk.  It’s a nice fact that this doesn’t depend on $x$. I learned about hitting times from the Aldous-Fill book, which is unfinished but on the web.

There is even a proof of this fact in the abovementioned book, which goes like this:

To construct a graph on $n=2n_1+n_2$ vertices, start with two complete graphs on $n_1$ vertices. Distinguish vertices $v_l \neq v_L$ in one graph ("the left bell") and vertices $v_R \neq v_r$ in the other graph ("the right bell"). Then connect the graphs via a path $v_L - w_1 - \cdots w_{n_2} - v_R $.

Then it is informally argued that it takes mean time about $n_1$ to hit $v_L$ and from there, there's chance $\frac{1}{n_1}$ to hit $w_1$, so it takes mean time about $n_1^2$ to hit $w_1$. From $w_1$ there is chance about $\frac{1}{n_2}$ to hit the right bell before returning into the left bell, so it takes mean time about $n_1^2 n_2$ to enter the right bell.

Setting $n_1 = n_2 = n/3$ gives us mean time $O(n^3)$.

Admittedly, I'm lost at the point they state:

  From $w_1$ there is chance about $\frac{1}{n_2}$ to hit the right bell before returning into the left bell.

But to ease my mind, I ran a simulation of random walks on barbell graphs constructed this way, between vertices picked from the stationary distribution. Indeed, the mean hitting time fitted very nicely to a curve $\frac{(n+1)^3}{54}$.

However, comments on the informal proof are still welcome.


Books/Lecture Notes on Parametrized Complexity I would like to learn about Parametrized Complexity (both on the algorithmic side and on the hardness side). What books/lecture notes can I read on this subject?

A good place to start is "Parameterized Complexity Theory" by Jörg Flum and Martin Grohe, published by Springer.


Can we construct a k-wise independent permutation on [n] using only constant time and space? Let $k>0$ be a fixed constant.
Given an integer $n$, we want to construct a permutation $\sigma \in S_n$ such that:

The construction uses constant time and space (i.e. preprocessing takes constant time and space). We can use randomization.

Given $i\in[n]$, $\sigma(i)$ can be computed in constant time and space.

The permutation $\sigma$ is $k$-wise independent,
i.e., for all $i_1, \ldots, i_k$,
the random variables $\sigma(i_1), \ldots, \sigma(i_k)$ are independent and
uniformly distributed over $[n]$.

The only thing I currently know uses logarithmic space and polynomial computation time per value of $\sigma(i)$ using pseudo-random generators.

Background
I needed something like the above for some recent work, and
I ended up using something weaker:
I allowed repeated entries and verified that all the numbers that I needed
were covered (i.e., a mess).
Specifically, I got a $k$-wise independent sequence
that can be computed in $O(1)$ time and
using constant space.
It would be nice to have something simpler, or just know what is known.
Assumptions
I am assuming the unit-cost RAM model. Every word in memory/register is of size $O(\log n)$, and every basic arithmetic operation takes $O(1)$ time. I am willing to assume any reasonable cryptographic assumption (one way function, discrete log, etc).
Current thingy
As suggested by Kaveh, here is the "easy" hack that I currently have (this is quite standard): Let $\sigma(x) = \sum_{i=0}^{k+2} a_i x^i \bmod p$ be a polynomial over a prime $p$ (think about $p$ as being $n$). Here, each $a_i$ is uniformly and randomly sampled from $[p]$. It is easy to see that $\sigma(1), \sigma(2), \ldots, \sigma(n)$ is a sequence that has repetitions, but it is $k$-wise independent, and roughly $n(1-1/e)$ of the numbers of $[n]$ appear in this sequence. Note, however, that since numbers repeat in this sequence, it is not a permutation.

If you are willing to use cryptographic techniques and rely upon cryptographic assumptions and to accept a computational notion of $k$-wise independence, it's posible that format-preserving encryption (FPE) might be helpful.  Let me sketch a few different constructions of this sort.

(By "computational notion of $k$-wise independence", I mean that no adversary with a reasonable running time can distinguish $\sigma$ from a $k$-wise independent permutation, except with negligible advantage.  These schemes won't be information-theoretically $k$-wise independent, but they'll be "essentially as good as $k$-wise independent", assuming all of the computation in sight is computationally bounded.)

A practical scheme, for smaller $n$

In particular, use a FPE construction to build a block cipher (pseudorandom permutation, PRP) with the signature $\sigma_k : [n] \to [n]$.  For values of $n$ that are smaller than $2^{128}$, probably the best scheme is to use a Feistel construction with a fixed number of rounds (say, 10) and a round function that is a PRF derived from AES.   The running time to evaluate $\sigma_k(i)$ for a single value of $i$ will be $O(1)$ AES invocations.  Each AES invocation runs in constant time.

Finally, note that any pseudorandom permutation is automatically $k$-wise independent.  In particular, the Luby-Rackoff theorem guarantees that with at least 3 rounds, you get (approximate) $k$-wise independence if $k \ll n^{1/4}$, assuming AES is secure.  With more rounds, it's likely that there will be a stronger result, but the theorems are harder to prove and become more technical, though it's widely believed that a constant number of rounds should suffice to get extremely high security (and thus essentially perfect $k$-wise independence for all reasonable values of $k$).

Generalizing this to larger $n$

When $n$ is larger, things get weirder, because the unit-cost RAM model implicitly allows up to $O(\lg n)$ parallelism for free.  It's not clear to me what the cost of PRPs should be in this model (constant? increasing with $n$? I don't know).

A third possible construction

Let $m$ be a RSA modulus that is a bit larger than $2n$.  Define $G$ to be the subgroup of $(\mathbb{Z}/m\mathbb{Z})^*$ containing the elements whose Jacobi symbol is $+1$.  Define $\pi : G \to G$ by

$$\pi(x) = x^3 \bmod m.$$

Next, define $\sigma$ by

$$\sigma(i) = g(\pi(f(i)),$$

where $f,g$ are random bijective 2-independent hash functions.

I suspect this construction has a chance of being (approximately) $k$-wise independent, under a RSA-like assumption.  I have no proof, just an intuition.  The main known regularity of $\pi$ is that it is multiplicatively homomorphic: $\pi(xy) = \pi(x) \pi(y)$.  I do not know of any other relevant regularities, even $k$-wise dependence.  Applying a 2-independent hash before and after $\pi$ provably eliminates this regularity: if $\pi$ is $k$-wise independence except for multiplicative homomorphicity, then the 2-wise independent hashes seem like they should provide full $k$-wise independence.  But this is super-sketchy and light-years from a proof of $k$-wise independence.

Note that you'll need to use format-preserving encryption techniques (e.g., the cycling technique) to ensure that $f,g$ work on $G$ rather than on $(\mathbb{Z}/m\mathbb{Z})$.  This scheme should have $O(1)$ (expected) running time to evaluate $\sigma(i)$ at a given input $i$, with suitable choice of $f,g$.

Also, in some sense this candidate construction is abusing the unit-cost RAM model by relying upon the ability to operate on $\lg n$-bit numbers in $O(1)$ time, for large values of $n$, which isn't really reasonable in practice.  (This last construction won't be secure for small values of $n$, so this last approach fundamentally relies upon the large-$n$ regime for it to have a chance of working... exactly the regime where the unit-cost RAM model is most dubious.)

I freely admit that this one is quite a stretch, but I mention it in case it triggers some inspiration for a better solution.

For instance, it might be possible to replace $G$ by a suitable elliptic curve group, so that we have $\pi(x) = e x$ over $G$ (recall that elliptic curve groups usually use additive notation rather than multiplicative notation).  The good thing about this is that it is not totally unreasonable to conjecture that, if the elliptic curve group $G$ is chosen right, $G$ will behave like a "black-box group", which I think might effectively imply that $\pi$ will be $k$-wise independent "except for effects implied by multiplicative homomorphism".  I don't have a complete construction ready to propose (the missing piece is how to choose $G$ and how to construct $f,g$ and how to prove $k$-wise independence from this), but it might be possible to put the pieces together somehow.


What is the meaning of 'uniform' in Blum's paper "On the Size of Machines" In Blum's "On the Size of Machines" he uses the word 'uniform' in several places.
For instance, in Theorem 1, he writes

Let $f$ be any recursive function. Then there exists $i,j\in \mathbb{N}$, both uniform in $f$,$g$ such that...

What does the word 'uniform' mean in this context?
In addition, is there a reference that defines what it means when one says a variable is uniform in a function?
Blum's paper is available at this link.

In this context, uniformity usually means that there exists an algorithm/Turing machine computing the thing that is being called uniform. That is, in this case, that there is a Turing machine that will compute $i,j$ from (Turing machines for) $f,g$.
More formally (in the context of the paper), it means:
There is a Turing machine $B$ such that, for any total Turing machines $F,G$, where $G$ has infinite range, $B(F,G)=(i,j)$ such that...


What kind of answer does TCS want to the question "Why do neural networks work so well?" My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to machine learning, stumbled across statements such as "No one understands why neural networks work well," which I found interesting.

My question, essentially, is what kinds of answers do researchers want?  Here's what I've found in my brief search on the topic:

The algorithms implementing simple neural networks are pretty
straightforward.
The process of SGD is well-understood mathematically, as is the statistical theory.
The universal approximation theorem is powerful and proven.
There's a nice recent paper https://arxiv.org/abs/1608.08225 which essentially gives the answer that universal approximation is much
more than we actually need in practice because we can make strong
simplifying assumptions about the functions we are trying to model
with the neural network.

In the aforementioned paper, they state (paraphrasing) "GOFAI algorithms are fully understood analytically, but many ANN algorithms are only heuristically understood." Convergence theorems for the implemented algorithms are an example of analytic understanding that it seems we DO have about neural networks, so a statement at this level of generality doesn't tell me much about what's known vs. unknown or what would be considered "an answer."

The authors do suggest in the conclusion that questions such as effective bounds on the size of the neural network needed to approximate a given polynomial are open and interesting. What are other examples of mathematically specific analytical questions that would need to be answered to say that we "understand" neural networks? Are there questions that may be answered in more pure mathematical language?

(I am specifically thinking of methods in representation theory due to the use of physics in this paper --- and, selfishly, because it is my field of study. However, I can also imagine areas such as combinatorics/graph theory, algebraic geometry, and topology providing viable tools.)

There are a bunch of "no free lunch" theorems in machine learning, roughly stating that there can be no one master learning algorithm that performs uniformly better than all other algorithms (see, e.g., here http://www.no-free-lunch.org/ ). Sure enough, deep learning can be "broken" without much difficulty:
http://www.evolvingai.org/fooling

Hence, to be provably effective, a learner needs inductive bias --- i.e., some prior assumptions about the data. Examples of inductive bias include assumptions of data sparsity, or low dimensionality, or that the distribution factorizes nicely, or has a large margin, etc. Various successful learning algorithms exploit these assumptions to prove generalization guarantees. For example, (linear) SVM works well when the data is well-separated in space; otherwise -- not so much.

I think the main challenge with deep learning is to understand what its inductive bias is. In other words, it is to prove theorems of the type: If the training data satisfies these assumptions, then I can guarantee something about the generalization performance. (Otherwise, all bets are off.)

Update (Sep-2019): In the two years since my posted answer, there has been a great deal of progress in understanding the inductive bias implicit in various DL and related algorithms. One of the key insights is that the actual optimization algorithm being used is important, since uniform convergence cannot explain why a massively over-parametrized system such as a large ANN manages to learn at all. It turns out that the various optimization methods (such as SGD) are implicitly regularizing with respect to various norms (such as $\ell_2$). See this excellent lecture for other examples and much more:
https://www.youtube.com/watch?v=zK84N6ST9sM


0-partition number vs partition number Denote by $\chi_0(f)$ the minimum number of 0 monochromatic rectangles needed to cover the 0-inputs of $f$, and by $\chi(f)$ the minimum number of monochromatic rectangles needed to cover the all inputs of $f$ (both 0 and 1). It is known that

$$\log \chi(f) \leq D(f) \leq (\log \chi_0(f))^2.$$

The last inequality follows from the famous clique vs independent set upper bound. Is there an $f$ that witnesses such a quadratic separation between $\log \chi(f)$ and $\log \chi_0(f)$?

A quadratic separation between $\log\chi_0$ and $\log\chi_1$ is proved in a paper by Göös, Jayram, Pitassi and Watson, see the ECCC report.

In Theorem 2 they construct a function $F$ with small $\log\chi_1(F)$, and they say "In fact, we prove Theorem 2 by showing that (the negation of) the function $F$ has high approximate nonnegative rank". Observe that $\log\chi_0(F)$ is at least the nonnegative rank of the negation of $F$.


Tight VC bound for agnostic learning The following result is supposedly known. However, the proofs I am able to find all prove a weaker result with an extra log factor. Where can I find the proof of the tight bound?

  Theorem. Let $\mathcal{H}$ be a class of functions $h : \mathcal{X} \to \{-1,+1\}$ with VC dimension $d<\infty$. Let $\mathcal{D}$ be a distribution on $\mathcal{X} \times \{-1,1\}$ and let $(X_1,Y_1), \cdots, (X_n,Y_n)$ be independent samples from $\mathcal{D}$. Let $\varepsilon,\delta>0$.

  If $n \geq O\left(\frac{d+\log(1/\delta)}{\varepsilon^2}\right)$, then $$\mathbb{P}\left[\forall h \in \mathcal{H} ~~\left|\frac{1}{n} \sum_{i=1}^n h(X_i) \cdot Y_i - \underset{(X_*,Y_*) \leftarrow \mathcal{D}}{\mathbb{E}}[h(X_*) \cdot Y_*]\right|\le\varepsilon\right] \ge 1-\delta.$$

The (well-known) connection to agnostic learning is as follows. $\mathcal{H}$ is a class of "hypotheses" and $\mathcal{D}$ is some unknown ground truth distribution on attributes $X \in \mathcal{X}$ and labels $Y \in \{-1,+1\}$. You see $n$ samples from $\mathcal{D}$ and want to be sure that any hypothesis that labels the sample well (i.e. $\frac{1}{n} \sum_{i=1}^n h(X_i) \cdot Y_i$ is large) also labels the ground truth well (i.e. $\underset{(X_*,Y_*) \leftarrow \mathcal{D}}{\mathbb{E}}[h(X_*) \cdot Y_*]$ is also large). The above theorem says that if $n \geq O\left(\frac{\mathsf{VCdim}(\mathcal{H})+\log(1/\delta)}{\varepsilon^2}\right)$ then with probability $\ge 1-\delta$, for all hypotheses the error on the sample and the error on the distribution are within $\varepsilon$.

The proofs that I can find relating VC dimension to uniform convergence all include an extra log factor. That is, they prove a bound of $n \geq O\left(\frac{\mathsf{VCdim}(\mathcal{H}) \cdot \log(\mathsf{VCdim}(\mathcal{H})/\varepsilon)+\log(1/\delta)}{\varepsilon^2}\right)$. This is achieved by applying the Perles-Sauer-Shelah lemma and a clever union bound. For the simple case where $\mathsf{VCdim}(\mathcal{H})=\log|\mathcal{H}|$, this just follows from Hoeffding's inequality and a union bound.

Unfortunately, I haven't been able to find a proof of the tight and general result, despite looking for several hours. Surely someone can point me to the right source!

This was proven in

  M. Talagrand. Sharper bounds for Gaussian and empirical processes. The Annals of Probability, pages 28–76, 1994.

This is mentioned in e.g. this paper (Section 1.1.2), which does a pretty good job (in my opinion) of summarizing the landscape.


Variation on partial Set Cover with penalties I'm looking at the following problem, which I'm hoping is perhaps a known variant of the Set Cover problem:

Input: We're given a universe $U$ and two disjoint subsets $A$ and $B$ such that $A \cup B=U$. We're also given a collection $C$ of $k$ sets $S_1,S_2,\ldots,S_k$ where $S_i \subseteq U$ for all $i=1\ldots k$. The sets $S_1,S_2,\ldots,S_k$ may or may not be disjoint, and the union of all $S_i$ may or may not equal the universe.

Solution form: A collection $C' \subseteq C$.

Objective function: Maximize $\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right| - \left|\left(\bigcup\limits_{c \in C'} c\right) \cap B\right|$

In English, the objective function rewards solutions that cover a large number of elements in $A$ and penalizes those that cover a large number of elements in $B$. The best solution would be one that covers $A$ fully and does not cover $B$ at all. The worst solution covers $B$ fully and does not cover $A$ at all. The cardinality of $C'$ is not important.

Example: Universe $U=\left\{1,2,3,4,5\right\}$. Susbsets $A=\left\{1,3,4,5\right\}$ and $B=\left\{2\right\}$. Sets $S_1=\left\{1,2,3,5\right\}$, $S_2=\left\{1,4\right\}$ and $S_3=\left\{2,5\right\}$. Here the best solution is to take $S_1$ and $S_2$, which gives a measure value of $3$.

It's relatively trivial to adapt the classical greedy heuristic to get an approximate solution. My questions are 1) is this problem studied in any literature, and 2) do you think it would be possible to prove an approximation ratio for the greedy heuristic on it?

I had a look at A compendium of NP optimization problems and questions like this one, but haven't been able to find anything similar yet.

This answers question (2):

The greedy heuristic for Set Cover / Maximum Coverage always picks the set which contains the maximal number of uncovered elements.

Assuming your modification for the heuristic is picking the set which greedily increases the solution profit, you might end up in a lousy approximation ratio.

Consider the following example:
$$A = \{a_1,a_2,\ldots a_{k}\}, B=\{b_1,b_2,\ldots b_k\}$$
$$C = \{C_1\} \cup C_2$$
$$C_1= A\cup B \setminus\{b_1\}$$
$$ C_2 = \{\{a_{i},b_1\}|i\in[k]\}$$

The greedy heuristic will output $C'=\{C_1\}$, so the profit is $1$, while the optimal solution is $C_2$ which gives profit $k-1$.


Complexity class of sensitivity Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function.

Let $[n]=\{1,2,\dots,n\}$.

If $i\in[n]$, let $\Bbb 1_i$ be length $n$ vector with all $0$s except $1$ at $i$th position.

If $B\subseteq [n]$, then $\Bbb 1_B$ be the length $n$ vector with $1$s only in positions marked by $B$.

If  $i\in[n]$ and $x\in\{0,1\}^n$, let $x^i=x\oplus\Bbb 1_i$ where $\oplus$ is $XOR$ operation.

If  $B\subseteq [n]$ and $x\in\{0,1\}^n$, let $x^{B}=x\oplus\Bbb 1_B$ where $\oplus$ is $XOR$ operation.

Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$

Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$

Block Sensitivity of $f$ at input $x$, $BS_x(f)$ is maximum $r$ such that there is a set of disjoint subsets $\{B_i\}_{i=1}^r$($\forall i\neq j$, $B_i\cap B_j=\emptyset$) such that  $$\forall j\mbox{, }f(x)\neq f(x^{B_j})$$

Block Sensitivity of $f$ is $$BS(f)=\max_xBS_x(f)$$

Given $f$ in $n$-variables, would it be reasonable to ask the complexity class of deciding $S(f)>c$ and $BS(f)>c$ for a fixed $c>0$? I understand that describing a Boolean function takes $2^n$ bits fully.

Does computing $BS(f)$ also take $O(2^{n+\epsilon})$ time as in answers below?

[An alternative answer for $BS(f)$]

There is a paper related to this problem.

Scott Aaronson: Algorithms for Boolean Function Query Properties.
SIAM J. Comput. 32(5): 1140-1157 (2003)

The paper gives an $O(N^{\log_2 5} \log N)$ algorithm for computing $BS(f)$ if $f$ is given by
a truth table of size $N=2^n$. Thus, even if $c$ is not fixed, deciding $BS(f) > c$
is in P.


Is getting post-doc difficult in theoretical computer science with few published papers? I am a Ph.D student ( expected to graduate in few months ) works in computational mathematics. In my PhD, I have published just couple of research papers. I am willing to go for a post-doc( US, Europe, Australia ), but not sure that I will get one or not as I have not published anything in the top conference, but still want to take a chance. I have heard from my seniors that getting a post-doc is very difficulty especially in theoretical computer science as there are very few jobs. I am also hesitant to write emails to the top researcher in my field. I can get a faculty job in my local area but that will be a teaching job ( mostly ) and right now I am not that much interested in teaching. I know that if I would have research papers in top conferences then my chances of getting a post-doc would have high.

Question :  Is getting pos-doc difficult in theoretical computer science with few published papers?

I voted to close the question but I see that it's getting upvotes and being "favorited" so perhaps a point that seems obvious to me bears being stated explicitly. So, not to put too fine a point on it: Not all postdocs are equally competitive. What is a postdoc, after all? It's a paid academic position, non tenure track, usually for a fixed time (1-3 years), possibly involving teaching. Usually, any faculty member or department with funding available can offer a postdoc position. But not all positions are created equal, and some are definitely more competitive and prestigious than others. So the strength of your CV will definitely have a major role in determining what kind of a position you'll be offered. Note that publications (especially their quantity rather than quality) are important but not all-decisive. A few very strong publications is certainly preferred to many weak ones -- at least when I'm hiring! Also the letters of recommendation matter a great deal.


Things that imply BQP Derandomization I am aware that it is generally believed that P = BPP, but BQP != P (since factoring is in BQP, and factoring seems hard.)

For BPP, we have the hardness vs randomness result: which states that circuit lower bounds for EXP imply derandomization results for BPP.

Even though I do not expect BQP to be simulatable in sub-exponential time, I am curious if there are any implication results along the lines of "If pigs can whistle, than donkeys can fly."

Formally, I'm asking if there exists provable statements of the form:

If [XYZ] then BQP can be simulated in sub-exponential time.

Ideally, [XYZ] would be about the hardness of certain problems against certain complexity classes. However, any XYZ not of the form "BQP can be simulated in sub-exponential time" would be interesting.

Thanks!

Interesting!  I don't know of any nontrivial result of that kind -- neither one that says "if [XYZ] then BPP=BQP", nor one that says "if [XYZ] then BQP ⊆ BPTIME(2o(n))."  The closest I can think of is a result of Terhal and DiVincenzo, who showed that if constant-depth quantum sampling can be efficiently classically simulated then BQP ⊆ AM.  (Later work, by Bremner-Jozsa-Shepherd and myself and Arkhipov, shows that the same assumption would even imply P#P = BPPNP.)  Combining that with some assumption that gave AM ⊆ BPTIME(2o(n)) would then yield what you wanted.


Other types of uniformity for circuits (incl. by small modifications) I've seen poly-time and logspace uniformity for circuit families, typically defined as the existence of a poly-time/logspace Turing machine "generator" that outputs the correctly sized circuit $C_n$ on input $n$. These restrictions upper bound the power of circuit families by requiring that they are computationally generated.

I was wondering what happens when you change the generator model. Here are two (vague) questions:

  Are there other useful types of uniformity for circuit families?
  Are there interesting "generators" besides time/space bounded TMs? For example, consider families that progress from $C_i$ to $C_{i+1}$ by "small" modifications of the circuit. Can these be broad and have interesting complexity properties?

The idea in #2 is far too inclusive, since it allows things like simple recursive definitions. I am more interested in severe restrictions on the range of possible families by limiting the types of modifications.

When you want to define (fully) uniform versions of circuit classes, log-space or poly-time uniformity is only sensible for classes of circuits whose power exceeds log-space or poly-time, respectively. This means that poly-time uniformity is next to useless, and log-space uniformity is good for classes like P, NC, $\mathrm{NC}^{k+1}$, $\mathrm{AC}^k$ for $k\ge1$, but not, say, for $\mathrm{NC}^1$.

The standard notion of uniformity for small complexity classes is DLOGTIME-uniformity, where furthermore one has to be careful what exact kind of description of the circuit is asked to be computable in DLOGTIME: in cases where it matters (e.g., $\mathrm{NC}^1$), one needs to use the extended connection language (cf. Ruzzo) of the circuit. This is known as $U_E$-uniformity.


SERF-reducibility and subexponential algorithms I have a question concerning the SERF-reducibility of Impagliazzo, Paturi and Zane and subexponential algorithms. The definition of SERF-reducibility gives the following:

  If $P_1$ is SERF-reducible to $P_2$ and there $O(2^{\varepsilon n})$ algorithm for $P_2$ for each $\varepsilon > 0$, then there is $O(2^{\varepsilon n})$ algorithm for $P_1$ for each $\varepsilon > 0$. (Hardness parameter for both problems is denoted by $n$.)

Some sources seem to imply that the following also holds:

  If $P_1$ is SERF-reducible to $P_2$ and there $O(2^{o(n)})$ algorithm for $A_2$, then there is $O(2^{o(n)})$ algorithm for $P_1$.

My question is, does this latter claim actually hold and if it does, is there a write-up of the proof somewhere?

As a background, I've been trying to understand the area around the Exponential Time Hypothesis. IPZ define subexponential problems as ones that have $O(2^{\varepsilon n})$ algorithm for each $\varepsilon > 0$, but this apparently is not sufficient in the light of the current knowledge to imply the existence of a subexponential algorithm for the problem. The same gap seems to be present in the SERF reducibility, but I am partially expecting that I am missing something here...

EDIT: As pointed out by Ryan in the comments, a problem may have a nonuniform algorithm with running time $O(2^{\epsilon n})$ for any constant $\epsilon > 0$ (the algorithm has access to $\epsilon$) but no uniform $2^{o(n)}$ time algorithm.

As a SERF reduction is a family of Turing reductions, one for each $\epsilon>0$, I conclude that they can only be used to obtain $O(2^{\epsilon n})$ time algorithms from $O(2^{\epsilon n})$ or $2^{o(n)}$ time algorithms.

The following Theorem is proved by Chen et al. [2009].

Theorem 2.4. Let $f(k)$ be a nondecreasing and unbounded function, and let $Q$ be a parameterized problem. Then the following statements are equivalent:
(1) $Q$ can be solved in time $O(2^{\delta f(k)}p(n))$ for any constant $\delta > 0$, where $p$ is a polynomial;
(2) $Q$ can be solved in time $2^{o(f(k))} q(n)$, where $q$ is a polynomial.

Taking $f(k)=n$ we obtain that a problem has a $O(2^{\epsilon n})$ time algorithm for every $\epsilon>0$ if and only if it has a $2^{o(n)}$ time algorithm.

It is mentioned in the paper by Chen et al. that this equivalence had been intuitively used before but that it was causing some confusion among researchers.


Why are regular languages called "regular"? Why are regular languages (and from that regular expressions) called "regular"? There is lot of regularity also in context-free languages other types of languages.

I suppose that, in the beginning, the adjective "regular" has been used to differentiate that type of languages from other "non-regular" or somehow abnormal languages. If so, what where these other types, and what was their non-regularity?

A quick check of the sources reveals that Chomsky called the levels of his hierarchy just “type 0, type 1, type 2, type 3”. He mentions in a footnote that his type 3 corresponds to “regular events” of Kleene. Kleene wrote there: We shall presently describe a class of events which we will call "regular events." (We would welcome any suggestions as to a more descriptive term.)

It would thus appear that the term is a historical accident, and in any case has no bearing on the relation of regular languages to context-free languages.


External Regret and Nash Equilibrium There is a well known fact that we can use the existence of external regret minimization algorithms to prove the minimax theorem of two-player zero-sum games.

The proof can be found in the survey Learning, Regret minimization, and Equilibria A. Blum and Y. Mansour.

Immediately arises question whether can we use external regret minimization to find mixed Nash equilibrium in finite non-zero two-player game, in other words does zero external regret leads to find mixed Nash equilibrium, in per round sense.

Intuitively it doesn't seem so, I am not sure that we can get external regret equals zero in general case, but there are polynomial time algorithm for good approximation (see the above paper), on the other hand approximation of Nash equilibrium seems like more difficult task.

I would appreciate if someone could help to answer the question.

No, no-regret dynamics do not converge to Nash equilibrium in general games, and its not hard to think of examples.

On the other hand, no regret dynamics do always converge to coarse correlated equilibrium in any game, and no-internal regret dynamics always converge to the set of correlated equilibria.

They are also known to converge to Nash equilibrium in several special cases of n-player games: for example, separable zero sum games, congestion games, and a few others.

In general, there are no efficient learning dynamics that converge to Nash equilibrium though. Not only is computing a Nash equilibrium PPAD hard, but even ignoring computation, for any "decoupled learning dynamics" (among which no regret dynamics are a special case) must exchange exponential communication before finding a Nash equilibrium in general games.


Weighted Min-Cut in bounded-genus graphs What is the status of the following decision problem ?

Input : A graph $G=(V,E)$ embedded in a torus (or more generally a surface of genus $g$), a weight function $w:E \rightarrow \{-1,1\}$

Output : Is there a cut $C\subseteq E$ with negative weight ?

Recall that $C$ is a cut in $G$ if the graph $G\setminus C$ is disconnected.

This problem can be solved in polynomial time in planar graphs. Indeed, there exists a negative cut if and only if there exists a negative cycle in the dual graph. The existance of such a cycle can be decided using Bellman-Ford algorithm.

Unfortunately, a cycle in the dual of a higher genus graph may not correspond to a cut in the primal graph, so that a generalisation of this algorithm seems difficult.

For graphs embedded on a surface of genus g with bounded weights $w:E \rightarrow \mathbb{Z}$, you can solve MAX-CUT in time $4^g poly(n)$ using an algorithm of Gallucio, Loebl and Vondrák. Applying it to your instance after taking the opposite weights and looking whether the result is positive seems to solve your problem.


Ramification of An Impredicative Type Theory Most type theories that I'm aware of are predicative by which I mean that

Void : Prop
Void = (x : Prop) -> x

isn't well-typed in most theorem provers as this pi type belongs to the same universe as Prop and it isn't the case that Prop : Prop. This makes them predicative and disallows impredicative definitions like the above. However, an awful lot of "blackboard languages" such as System F or CoC are in fact impredicative. In fact, this impredicativity is vital to defining most of the constructs not included primitively in the language.

My question is why would one wish to give up impredicativity given it's power in defining logical constructs? I've heard a couple people remark that impredicativity screws up "computation" or "induction" but I'm having trouble finding a concrete explanation.

I'm going to elaborate my comments into an answer. The origins of predicative type theory are almost as old as type theory itself, since one of Russel's motivations was to ban "circular" definitions which were identified as part of the source of the XIXth century inconsistencies and paradoxes. Thierry Coquand gives an enlightened overview here. In this theory, predicates over a "level" or type, belong to the types of the "next" level, where there is an infinite (countable) number of levels.

While Russel's predicative hierarchy was (apparently) sufficient to dismiss the known paradoxes, it turned out to be very difficult to use as a foundational system. In particular, defining even something as simple as the real number system was extremely difficult, and so Russel postulated an axiom, the Axiom of Reducibility which postulated that all levels were "reduced" to one. Needless to say, this was not a satisfactory development.

However, contrary to the "harmful" impredicative statements (like unrestricted comprehension), this axiom did not seem to introduce any inconsistencies. The subsequent formulations of foundational theories (simple type theory, Zermelo's theory of sets) accepted them wholesale, making families of predicates (quantifying over possibly the whole universe of sets), predicates at the same level.

Circa 1971, Martin-Löf introduced dependent type theory in which both this principle and the further axiom Type : Type hold. This system turned out to be inconsistent for subtle reasons: the naive Russel paradox can not be played out (in a straightforward manner), but a clever encoding nevertheless allows a contradiction to be found. This prompted a crisis of faith similar to that of Russel, resulting in the predicative type theory with universes we know and love.

There is a way to repair the theory to allow "innocent" impredicativity a la Zermelo set theory, resulting in type theories like the Calculus of Constructions, but the damage was done, and the "Swedish school" of type theory tends to reject impredicativity.

Several points:

What does this have to do with intuitionistic mathematics? The answer is not much. At the turn of the XXth century, mathematicians tended to conflate the use of circular/impredicative principles with non-constructive reasoning (the intuition being that impredicative reasoning seems to assume a pre-existing mathematical universe, as does uses of the excluded middle). However, there are perfectly intuitionistic impredicative theories (like IZF). People interested in intuitionism still tend to be interested in predicativism for some reason (I'm guilty of this, of course).
What can you do in predicative mathematics? As Martin points out in his answer, Hermann Weyl (not to be confused with Andre Weil) started a program which tried to explore the expressive power of predicative systems, taking as starting point that predicative systems were of expressive strength between Peano Arithmetic and Second Order Arithmetic, which is pretty much agreed to be impredicative by most standards (and is comparable to System F on the type theory side). The program was later dubbed "reverse mathematics" as it tried to classify the strength of known mathematical theorems in terms of the axioms required to prove them (the reverse of the usual approach). The wikipedia page give a good overview; the program was quite successful, in that most of XIXth century mathematics can easily be accommodated in very weak systems. It is still an open question whether this program can scale to more recent results in, say, higher category theory (the suspicion is that the answer is "yes, with great effort").


Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs Given a graph, $G = (V, E)$, I want to find an optimal $r$-domination for $G$. That is, I want a subset $S$ of $V$ such that all vertices in $G$ are at a distance of at most $r$ from some vertex in $S$, while minimizing the size of $S$.

From what I have checked so far, I got the following: There is this related problem of finding a $(k,r)$-center in a graph which is a subset $S$ of size at most $k$ such that all the vertices in the graph are at a distance of atmost $r$ from some vertex in $S$(here both $|S| \leq k$ and $r$ are parts of the input) for which Demaine et al. have a FPT algorithm for planar graphs. Otherwise the problem is $W[2]$-hard for even $r = 1$.

Is anything known about the exact complexity of $r$-domination problem for bounded tree width graphs or even just trees? (Is $r$-domination MSO definable? the usual $k$-dominating set problem is MSO definable -- which then would allow one to use Courcelle's theorem to conclude that there is a linear time algorithm for the problem). Are there any conditional hardness results known regarding this problem?

An (optimal) $r$-domination for $G$ is an (optimal) domination for the $r$th power $G^r$ and vice versa
($G^r$ is obtained from $G$ by adding new edges between distinct vertices of distance at most $r$).

The following facts are well known: (1) All powers of a strongly chordal graph are strongly chordal
(A. Lubiw, Master thesis; see also Dahlhaus & Duchet, On strongly chordal graphs,
Ars Combin. 24 B (1987) 23-30), and (2) Domination is solvable in linear time for strongly chordal graphs
(M. Farber. Domination, independent domination and duality in strongly chordal graphs,
Discrete Appl. Math., 7 (1984) 115–130). Hence $r$-domination is solvable in polynomial time for
strongly chordal graphs, in particular for trees ($r$ fixed or not).

Gurski & Wanke proved in this paper
that the clique-width of $G^r$ is at most $2\cdot (r+1)^{\text{tw}(G)+1}−2$, where $\text{tw}(G)$ is the tree-width
of $G$. Thus, for fixed $r$, the $r$th powers of bounded tree-width graphs have bounded clique-width.
Hence, for fixed $r$, $r$-domination is solvable in polynomial time for bounded tree-width graphs
(by Courcelle's theorem).


Electrical engineering student interested in Theoretical computer science I am sophomore studying electrical engineering and I have immense interest in pure mathematics and theoretical computer science. I have studied abstract algebra ,real analysis and little bit of topology and discrete math too. I am also an enthusiastic coder .

What is the 'roadmap' for an engineer interested in theoretical computer science and the best books for an undergrad student , which I should study in order to go ahead in this field ?

Theoretical computer science has many dimensions. One of them is the study of programming languages (in
a general sense). Here is a path into this field.

An introductory textbook on logic like Dirk van Dalen's "Logic and
Structure". There are plenty of other good books on the subject, but
I recommend one that that talks a little bit about proof theory and intuitionistic
logic as both are at the heart of programming language theory's use of logic.
Followed by an implementation oriented book like John Harrison's
amazing "Handbook of Practical Logic and Automated Reasoning".
After finishing this book you could start coding, for example
SAT-solvers, a highly interesting field, merging theory and
practise. It's competitive too: http://www.satcompetition.org/
In parallel you can read an introductory text book on the theory of
programming languages.  Alas there is nothing really up-to-date,
reflecting the last 25 years of progress, but Glynn Winskel's "The
Formal Semantics of Programming Languages" might not be the worst
place to start.
Some, but not all parts of programming language research is
enamoured with category theory. The usefulness of category theory
for programming languages is fiercely debated. But since you've
already mastered abstract algebra, you should be able to pick up
category theory without too much pain. You could start with
"Category Theory" by Steve Awodey, or "Abstract and Concrete
Categories" by Adamek et al. The categorical viewpoint on a lot of
things can be quite mind-blowing.

You would be well-qualified to dive into more specialised subfields of programming language research with this background.

None of the above would be very useful for the algorithms / complexity
track of theoretical computer science.


Minimum offset while measuring TSP paths I have Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.

I am trying to solve TSP with brute algorithm, and I want to know how to calculate the smallest possible difference between the paths that I find during the run.

Edit:
I want to know this, to proper round my distances. May be I can use integers, may be I need floats, or maybe I need 1,000,000 floating point number. When I am comparing two distances and I coming to the conclusion that they are equal I want to be 100% sure they are.

Edit 2 Another interesting example for the possibilities is: If you are taking a graph that all the weights are 1 or 2. The minimum offset will be exactly 1.

It is an open problem to lower bound the difference between two distinct Euclidean TSP tours by an inverse polynomial in the input size. Such a lower bound would show that Euclidean TSP is an NP optimizaition problem, which is not known.

Let us assume that a Euclidean TSP instance is given by a collection of points in $(\mathbb{Z} \cap [-N, N])^2$ (i.e. points with integer coordinates bounded in absolute value by $N$). It is not known how to decide the following problem in polynomial time: given two tours $T_1$, $T_2$ over the same set of points, is the cost $c(T_1)$ of $T_1$ less than the cost $c(T_2)$ of $T_2$. To solve this problem it is sufficient to upper bound $-\log |c(T_1) - c(T_2)|$ by a polynomial in n and $\log N$, which is equivalent to your question.

The even more basic problem of deciding if $\sum_{i = 1}^n{\sqrt{a_i}} < \sum_{i = 1}^n{\sqrt{b_i}}$, for $a_i, b_i \in \mathbb{Z} \cap [1, N]$ (i.e. positive integers bounded by $N$) in time polynomial in $n$ and $\log N$ is also open, see http://cs.smith.edu/~orourke/TOPP/P33.html.

If all distances between points are rational, i.e. $\|v_i - v_j\| = a_{i,j}/b_{i,j}$ for integers $a_{ij}$, $b_{i,j}$, then
$$
|c(T_1) - c(T_2)| >= \frac{1}{\text{LCM}(\{b_{i,j}\}_{i, j \in [n]})},
$$
where LCM is the least common multiple function.


Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$? A number of geometric problems are easy when considered in $R^1$, but are NP-complete in $R^d$ for $d\geq2$ (including one of my favourite problems, unit disk cover).

Does anyone know of a problem which is polytime solvable for $R^1$ and $R^2$, but NP-complete for $R^d,d\geq3$?

More generally, do problems exist which are NP-complete for $R^k$ but polytime solvable for $R^{k-1}$, where $k\geq3$?

It's not quite what you ask, because the 3d version is even harder than NP-complete, but: Finding a shortest path between two points among polygonal obstacles in the plane is in polynomial time (most simply, construct the visibility graph of the two terminals and the polygon vertices and apply Dijkstra; there is also a more complicated O(n log n) algorithm due to Hershberger and Suri, SIAM J. Comput. 1999) but finding a shortest path among polyhedral obstacles in 3d is PSPACE-complete (Canny and Reif, FOCS 1987).