Intuitively, why is the complementary slackness condition true? What's an intuitive proof that shows that the conditions of complementary slackness are indeed true:

If $x^*_j > 0$ then the $j$-th constraint in the dual is binding.
If the $j$-th constraint in the dual is not binding, then $x^*_j = 0$

And similarly for the dual variables $y^*_i$ and constraints in the Primal. Where $x^*$ and $y^*$ are the optimal solutions to the Primal and Dual respectively.

What's an intuitive proof as to why this is the case? Staring at the equations makes sense algebraically, but I wish to understand it at a more visceral level.

As you have noted, complementary slackness follows immediately from strong duality, i.e., equality of the primal and dual objective functions at an optimum.
Complementarity slackness can be thought of as a combinatorial optimality condition, where a zero duality gap (equality of the primal and dual objective functions) can be thought of as a numerical optimality condition.

In order to understand what complementary slackness means, the concept of dual variables as "shadow prices" is useful. The dual variable associated with a primal constraint is called the constraint's shadow price because it can be thought of as how much the objective function would increase if the constraint was relaxed (meaning e.g. the right hand side of a $\le$ constraint was increased).

Complementary slackness says that at an optimal solution, if a shadow price (dual variable) is positive, meaning that the objective function could be increased if the corresponding primal constraint was relaxed, then this primal constraint must be tight. If not, the primal objective function value could be improved (by changing the primal variables in order to make this non-binding primal constraint binding).


Is graph connectivity definable in existential MSO with vertices and edges? Can $\exists$MSO$_2$ express graph connectivity?

Monadic SO (MSO) is the fragment of second-order logic in which the second-order quantifiers range over relations of arity 1 only.
$\exists$MSO is the fragment of MSO in which only non-negated existential second-order quantification is allowed.

MSO over graphs (sometimes denoted MSO$_1$) has as its universe vertices only.
In contrast, the variant MSO$_2$ has as its universe vertices as well as edges.

It is well-known that MSO$_2$ is more expressive than MSO$_1$; for instance, the former can express the existence of a Hamiltonian cycle (see Libkin's Elements of Finite Model Theory, Exercise 7.4), while the latter cannot (Libkin's proof of Corollary 7.24 is a neat pumping argument due to Makowsky).

It is also standard that $\exists$MSO$_1$ cannot express graph connectivity.  One proof is via Hanf locality due to Fagin, Stockmeyer, and Vardi (Information and Computation 1995).  This paper states: "we consider it possible that connectivity is not in monadic NP, even in the presence of arbitrary built-in relations of arbitrary degree"; the edge relation has arity 2 so they are conjecturing that the answer to my question is negative (monadic NP is the same as $\exists$MSO).
(Removed last clause as per comment of Emil Jeřábek.)

More recently, Courcelle and Engelfriet's textbook on MSO mentions that it is possible to express "$X$ is a set of edges forming a directed path from $s$ to $t$" in MSO$_2$.  However, their formula uses universal quantification.  It is not immediately obvious whether this is necessary, at least for the concept of connectivity of an undirected graph.

You can express that $s$ is connected to $t\ne s$ in $G=(V,E)$ by the $\exists\mathrm{MSO}_2$ formula

  “there exists $E'\subseteq E$ such that in the graph $(V,E')$, $s$ and $t$ have degree $1$, and all other vertices have degree $0$ or $2$.”

Note that the formula after the initial $\exists E'$ quantifier is first-order.

A graph of degree $\le2$ is a disjoint union of lines and cycles; since end-points of lines are exactly the vertices of degree $1$, the only way to satisfy the formula is that $E'$ consists of a line connecting $s$ to $t$, and possibly some disjoint cycles.

Likewise, directed connectivity can also be defined by an $\exists\mathrm{MSO}_2$ formula (we replace “degree $2$” with “in-degree and out-degree $1$”, and similarly for the end-points).


Other norms for Lattice reduction techniques (LLL, PSLQ)? LLL and other lattice reduction techniques (such as PSLQ) try to find a short basis vector relative to the 2-norm, i.e. for a given basis that has $ \varepsilon $ as its shortest vector, $ \varepsilon \in Z^n $, find a short vector s.t. $ b \in Z^n, ||b||_2 < ||c^n \varepsilon||_2 $.

Has there been any work done to find short vectors based on other, potentially higher, norms?  Is this a meaningful question?

Following the specific reference provided by Steve Huntsman in his MO answer leads to the paper

Oded Regev and Ricky Rosen. Lattice problems and norm embeddings, STOC 2006.  doi: 10.1145/1132516.1132581 (full preprint version)

This paper presents randomized reductions from the approximation versions of lattice problems in the $\ell_2$ norm to any norm $\ell_p$ where $1 \le p \le \infty$.  The reductions don't quite preserve the approximation ratio, but the loss can be bounded by a factor of $(1+\epsilon)$.  So the $\ell_2$ norm yields in some sense the "easiest" versions of lattice problems.  It is enough to prove hardness of approximation using the $\ell_2$ norm, and hardness of approximation for any other $\ell_p$ norm follows with only a $(1+\epsilon)$ larger approximation factor.

Regev and Rosen then go on to use this to strengthen some existing hardness results.

On the other hand, Chris Peikert showed that lattice problems posed using $\ell_p$ norms are not substantially harder than problems posed in the $\ell_2$ norm.

Chris Peikert, Limits on the hardness of lattice problems in $\ell_p$ norms, Computational Complexity 17 300–351, 2008.  doi: 10.1007/s00037-008-0251-3 (full preprint version)

So yes, the question is sensible, and it has also essentially been answered.

(Thanks to @user834 for the preprint links.)


Complexity of computing the discrete Fourier transform? What is the complexity (on the standard integer RAM) of computing the standard discrete Fourier transform of a vector of $n$ integers?

The classical algorithm for fast Fourier transforms, inappropriately[1] attributed to Cooley and Tukey, is usually described as running in $O(n \log n)$ time.  But most of the arithmetic operations executed in this algorithm start with complex $n$th roots of unity, which are (for most $n$) irrational, so exact evaluation in constant time is not reasonable.  The same issue arises with the naive $O(n^2)$-time algorithm (multiplying by a Vandermonde matrix of complex roots of unity).

It's not even clear how to represent the output of the DFT exactly (in any useful form).  In other words, it's not clear that computing DFTs is actually possible!

So suppose we only need $b$ bits of precision in each output value.  What's the complexity of computing the discrete Fourier transform, as a function of $n$ and $b$?  (For concreteness, feel free to assume $n$ is a power of $2$.)

Or does every instance of "FFT" in the literature actually mean "fast number-theoretic transform"?[2]

See my related questions on the complexity of Gaussian elimination and Euclidean shortest paths.

[1] It should really be called (some prefix of) the Gauss-Runge-König-Yates-Stumpf-Danielson-Lánczos-Cooley-Tukey algorithm.

[2] And if so, why do most textbooks describe only the complex-number algorithm?

This answer is a variant of the analysis of the first algorithm
("Methode A") by Schönhage and Strassen for multiplication of long integers.

Assume we want to compute an FFT of length $K = 2^k$.
Scale your input such that all values are smaller than 1.
Let us first assume that we compute with $m$-bit fixed point arithmetic
($m$ bits after the binary point). Let $\delta = 2^{1/2 -m}$ be the
("complex") unit of least position. Let $\omega =  \exp(2\pi i/K)$.

1) One can compute approximations $\omega_j'$ such that
$|\omega_j' - \omega^j| \le (2k-1)\delta$ for all $0 \le j \le K-1$.
This can be done in time $O(K M(m))$ where $M(m)$ is the time needed
to multiply $m$-bit numbers. (see Knuth Vol. 2, 3rd ed., page 309).

If standard integer RAM means logarithmic cost, then $M(m) = O(m \log m)$.
If standard integer RAM means word RAM, then $M(m) = O(m)$. (Schönhage and Strassen show in "Methode A" how to reduce in linear time the multiplication of $m$-bit numbers to $m$ multiplication of $O(\log m)$ bit numbers. The latter can be done at unit costs.)

2) The classical Cooley-Tukey FFT computes operations of the form
$a = b + \omega^j c$. We use $m$-bit fixed point arithmetic,
these opertions become $a' = truncate(b' + \omega_j' c')$.
If we know $b'$ and $c'$ up to an error of $\epsilon$, we get $a'$ up to an error of $2\epsilon + 2k\delta$.

3) Using induction, it is easy to see that we get the final result
with error $(2^k - 1) \cdot 2k\delta$. To get precision $b$ in the end,
$m \ge k + \log k + b + O(1)$.

4) Thus the final running time is $O(K k M(k+b))$.

This should also work with floating point numbers: 1) can still be done with fixed point arithmetic, 2) is also true for floating point numbers.

In fixed point arithmetic, I think, it can even be done faster.
First we reduce the computation of the FFT to the multiplication of
polynomials using Bluestein's trick.
The length of the coefficients needed to get the desired precision
should be $O(k + b)$.
Then we reduce the multiplication of polynomials to the multiplication
of long integers. (Append the coefficients to a long number and separate them by blocks of zero of length $O(k+b)$.) The length of the integers is $O(K(k+b))$.


For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$? The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows:

Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$.
Question: Does there exist $k$-pairwise vertex-disjoint paths $P_1,\ldots,P_k$, such that $P_i$ goes from $s_i$ to $t_i$?

The problem, for general $k$, is known to be NP-complete even for planar graphs of max degree 3.
That said, $2$-$\text{DPP}$ admits a nearly linear algorithm for general undirected graphs.
Is there anything known for any higher value of $k$ (assuming fixed $k$ value)? What about $k=3$?

For undirected graph problem admits a FPT algorithm for any fixed $k$. Robertson and Seymour, Graph Minor XIII. Their algorithm runs in time $2^{2^{2^{2^{O(k)}}}} P(n)$ which means for $k = O(\log\log\log\log n)$ is polynomial. But it's not known whether there is better bound for $k$ or not. In special cases like undirected planar case and recently bounded genus case, running time improved.

For directed graph it's NP-Complete even case of 2-disjoint path problem. But in planar graphs is FPT by result of Marx et al., in graphs of bounded genus is at least in XP (not known whether is FPT or not), in directed acyclic graphs is $W[1]$-hard by result of Slivkins, for tournaments is NP-complete (not known if is FPT or even XP, edge disjoint version admits XP algorithm by result of Seymour et al).


Pseudo-polynomial time algorithms Consider the following algorithm:

Given a natural number as input, say $N$, the algorithm runs a loop (in which the algorithm does $O(1)$ time operations) $N$ times. Now, by definition of time complexity, we want to measure the running time as a function of input size, so the complexity of this algorithm is $O(N)=O(2^{\lg N})$.  I have always felt a little uneasy that this simple algorithm is actually has an exponential running time.

More examples of such problems include integer factorization, knapsack (and a lot of other related papers Google throws up) which all have a running time that is pseudo-polynomial in the size of the input(also called as weakly NP-complete problems). Is there any survey/book that treats these problems in detail? Are there any interesting aspects of these problems (as in, they have some properties that characterize them distinctly from strongly NP-complete problems) that are well-known?

I think this somehow “uneasy feeling” comes from the fact that human beings consider natural numbers only with a semantic—if I see 2001, e.g., I immediately think of 9/11 or Stanley Kubrick or something, that is, you interpret the number. In terms of inputs for an algorithm, however, it is merely a string of characters, and could just as well be such nonsense as ¨*^! or anything. What we as algorithm analyzers care about is only the length of the string, and absolutely not what it contains or represents. You really have to get this into your mind because otherwise you could e.g. say that $PRIMES$ is obviously in $\mathsf{P}$ as you can just try to divide a number $x$ by all numbers between 1 and $x,$ and this algorithm has obviously polynomial runtime. I hope you see the pitfall.


Solvability of matrix filling Matrix $A$ has dimension $n \times n(n-1)$. We want to fill $A$ using integers between $1$ and $n$, inclusive.

Requirements:

Each column of $A$ is a permutation of $1, \dots, n$.
Any submatrix formed by two rows of $A$ cannot have identical columns.

Question:

Is it possible to fill the matrix satisfying the requirements?

Relation to cryptography:

Each row number corresponds to a plaintext. Each column corresponds to a key. Since a key defines an injection, each column must be a permutation. The second requirement is for perfect secrecy for two messages.

This is a partial solution.  Such a matrix exists if n is a prime power.

Let F be the finite field of order n.  We construct an n×n(n−1) matrix whose rows are labeled by F, whose columns are labeled by (F∖{0})×F, and whose entries are in F as follows: the i-th row of the column labeled (a, b) is given by ai+b.  In words, each column corresponds to a degree-one polynomial in F.  Then each column contains each element of F exactly once, and no two columns have equal entries in more than one row because the values of two distinct degree-one polynomials can coincide at at most one point.

(If you want a matrix whose entries are in {1,…,n} instead of in F, replace the elements of F with {1,…,n} arbitrarily.)


Natural notion for computational hardness When I teach students concepts like intractable problems and efficient algorithms in discrete structures or data structures and algorithms, it is difficult for students to intuitively grasp somewhat artificial concepts of asymptotic time complexity and polynomial growth rates. Artificial $NP$-complete problems were known before the discovery of Cook's first natural $NP$-complete problem, which sparked huge interest in the field. Under some acceptable definition of natural:

  What is the most natural way to express the computational hardness of natural problems to students who encounter the subject for the first time?

EDIT: Motivated by Marc's answer, it would be more natural to find how hard is the self reducibility of clique problem. For instance, How hard is it to reduce an instance of clique of input size $(1+ \epsilon)n$ to an instance of size $n$ using Turing reduction?.

Just what makes growth rates such as O(n²) artificial — just the fact that it isn't one specific monotonic function? Or is it the fact that it's a family of functions in itself, and not just some simple number which comes from something obvious about the problem?

At the very least, your students should be able to grasp the purpose, and in a sense the meaning, of asymptotic notation by observing how the tediousness of performing arithmetic scales with the size of the numbers — that it gets more tedious for larger numbers, and that adding two n-bit numbers is less tediuous than multiplying them. Hopefully they should percieve a difference! If they can, then you have got them where you want them. Point out that the difference is smaller when you have smaller numbers: obviously the difference is one which grows with instance size. Point out to them the nested iterations in the multiplication algorithm. And now you have motivated caring about the difference between O(n²) time and O(n) time. Get them to do matrix computations next to give them a taste of O(n³), and point out the nested iterations there. They should get the idea after that.

I would say that exponential-time versus poly-time often amounts to "searching through a combinatorial explosion versus performing a bounded number of nested iterations", which is about as natural a distinction as possible between approaches to solving problems (e.g. in computer programming). But you cannot motivate complexity of problems of any sort, to people who do not themselves spend time solving problems and so who have no taste for the idea that certain ways of solving things (or solving different kinds of problems) take different amounts of work, and that differences between algorithms come from some place. You can't convince someone of these things unless they can have enough "empathy" for the computer to viscerally feel the extra work that is being done in one algorithm, versus another; to be aware of the layers of computing or of searching which it is doing, to actually hope that the problem has enough structure to narrow the solution space beyond just nested loops. They must be able to appreciate the existentially Sisyphian futility of trying to solve instances of SAT just by looking forlornly for a solution brute-force. This sort of perspective comes from solving problems oneself, and being self-aware of what one is doing; and I think it is perfectly natural to ask how much the tediousness of the task (i.e. how many computations you are doing) scales with the size of the problem.

If your students can't grasp this, tell them that the "difficulty" of adding numbers by high-school techniques is rated as 1; that of multiplying numbers is rated as 2; that sorting an unordered list has a rating between 1 and 1.000001 if you do it in the right way; and that there are no techniques for solving SAT whose rating is less than infinity; and move on from there — because you're not likely to do much better than this pedagogically without inventing a novel complexity measure, or obtaining more engaged students.


Extensionality of lambda calculus models I'm translating a book on LISP and naturally it touches some elements of $\lambda$-calculus. So, a notion of extensionality is mentioned there alongside some models of $\lambda$-calculus, namely: $\mathcal{P}_\omega$ and $D^\infty$ (yes, with the infinity at the top). And it is said that $\mathcal{P}_\omega$ is extensional while $D^\infty$ is not.

But... I was looking through the Barendregt's Lambda Calculus, It's Syntax and Semantics, and (hopefully, correctly) read there exactly the opposite: $\mathcal{P}_\omega$ is not extensional, $D_\infty$ is.

Does anybody know about that strange model $D^\infty$? Could it be just the same model as $D_\infty$, but erroneously written? Am I right about the extensionality of the models?

Thanks.

I presume that by extensionality you mean the law
$$(\forall x . f x = g x) \implies f = g.$$
If this is what you mean then the graph model $\mathcal{P}\omega$ is not extensional, while Dana Scott's $D_\infty$ is (I presume $D^\infty$ is Dana Scott's model of the $\beta\xi\eta\lambda$-calculus).

To see this, recall that $\mathcal{P}\omega$ is an algebraic lattice with the property that its space of continuous maps $[\mathcal{P}\omega \to \mathcal{P}\omega]$ is a proper retract of $\mathcal{P}\omega$, i.e., there are continuous maps
$$\Lambda : \mathcal{P}\omega \to [\mathcal{P}\omega \to \mathcal{P}\omega]$$
and
$$\Gamma : [\mathcal{P}\omega \to \mathcal{P}\omega] \to \mathcal{P}\omega$$
such that $\Lambda \circ \Gamma = \mathrm{id}$ but $\Gamma \circ \Lambda \neq \mathrm{id}$. Given $u, v \in \mathcal{P}\omega$, the application $u v$ is interpreted as $\Lambda(u)(v)$. Now take $u$ and $u'$ such that $u \neq u'$ but $\Lambda(u) = \Lambda(v)$ (these exist because $\Gamma \circ \Lambda \neq \mathrm{id}$). Then for all $v$ we have $u v = u v'$ yet $u \neq u'$. Extensionality is violated.

In contrast, $[D_\infty \to D_\infty]$ is isomorphic to $D_\infty$, i.e., there are continuous maps
$$\Lambda : D_\infty \to [D_\infty \to D_\infty]$$
and
$$\Gamma : [D_\infty \to D_\infty] \to D_\infty$$ which are inverses of each other. So consider any $u, u' \in D_\infty$ and suppose that $u v = u' v$ for all $v \in D_\infty$. This means that $\Lambda(u)(v) = \Lambda(u')(v)$ for all $v \in D_\infty$, hence $\Lambda(u) = \Lambda(u')$ and so $u = \Gamma(\Lambda(u)) = \Gamma(\Lambda(u')) = u'$. Extensionality is established.

We see that extensionality is a consequence of $\Gamma \circ \Lambda = \mathrm{id}$. What is the other equation $\Lambda \circ \Gamma = \mathrm{id}$ good for? For this we have to remember how $\lambda$-abstraction is interpreted:
$$\lambda X. u(X) = \Gamma (v \mapsto u(v))$$
In words, an expression $u(X)$ with a variable $X$ may be interpreted as a map which takes $v$ to $u(v)$. Then the $\lambda$-abstraction $\lambda X . u(X)$ is interpreted as the $\Gamma$-image of that function. Now from $\Lambda \circ \Gamma = \mathrm{id}$ we get
$$(\lambda X . u(X)) w = \Lambda (\Gamma (v \mapsto u(v))) (w) = (v \mapsto u(v))(w) = u(w)$$
which is just $\beta$-reduction.


Hardness of quantum circuit equivalence? Given two poly-sized quantum circuits $C_1$ and $C_2$ on $n$ qubits with a universal gate set generated by some finite set of one and two qubit gates. I'm thinking of the gates $\langle H, T, CNOT\rangle$, but other universal gate sets should work as well. Notice that $C_1$ and $C_2$ each correspond to a $2^n \times 2^n$ unitary matrix, $U_1$ and $U_2$, respectively. How hard is it to determine if $U_1 == U_2$, given the circuits $C_1$ and $C_2$?

Clearly the problem is in coQMA since if $U_1$ and $U_2$ are different there exists an input state $r$ such that $C_1(r)$ not equal to $C_2(r)$ which can be checked with a quantum computer. Has this problem been studied? Is it complete for this class? Is this class known as something else in the literature, since I cannot find much about it?

The problem isn't clearly in coQMA. If $U_1$ and $U_2$ are different, and you're given a state on which they act differently, it is not necessary that a polynomial-time quantum computer can check that the output states are different.

In fact, it is easy to show that if these two quantum states are different, but exponentially close in trace norm, then no polynomial-time quantum algorithm can distinguish the two. This is analogous to how no polynomial-time classical algorithm can distinguish two probability distributions that are exponentially close.

On the other hand, if we're promised that $U_1$ and $U_2$ are not too close when they are not equal, then the problem is in coQMA.

The complexity of either variant is known. In the exact case, this problem is complete for coNQP, which is the same as the class $C_=P$.

  Yu Tanaka, EXACT NON-IDENTITY CHECK IS NQP-COMPLETE. International Journal of Quantum Information 08:05, 807-819 http://arxiv.org/abs/0903.0675.

In the other case where we're promised that they're not too close when unequal, the problem is indeed coQMA-complete.

  D. Janzing, P. Wocjan, and T. Beth, Non-identity check is QMA-complete, International Journal
  of Quantum Information, 3(3), pp. 463–473, 2005; http://www.worldscientific.com/doi/abs/10.1142/S0219749905001067

(Note that the problem is equivalent to checking if $U_1U^\dagger_2$ is the identity matrix, which is called the identity check problem.)


Sampling from Multivariate Gaussian with Graph Laplacian (inverse) Covariance We know from e.g. Koutis-Miller-Peng (based on work of Spielman & Teng), that we can very quickly solve linear systems $A x = b$ for matrices $A$ that are the graph Laplacian matrix for some sparse graph with non-negative edge weights.

Now (first question) consider using one of these graph Laplacian matrices $A$ as the covariance or (second question) inverse covariance matrix of a zero-mean multivariate normal distribution $\mathcal{N}(\boldsymbol{0}, A)$, or $\mathcal{N}(\boldsymbol{0}, A^{-1})$.  For each of these cases, I have two questions:

A. How efficiently can we draw a sample from this distribution?  (Typically to draw a sample, we compute the Cholesky decomposition $A = LL^T$, draw a standard normal $y \sim \mathcal{N}(\boldsymbol{0}, I)$, then compute a sample as $x = L^{-1} y$).

B. How efficiently can we compute the determinant of $A$?

Note that both of these could be solved easily given a Cholesky decomposition, but I don't immediately see how to extract $L$ more efficiently than just by using a standard sparse Cholesky algorithm, which wouldn't use the techniques presented in the above-referenced works, and which would have cubic complexity for sparse-but-high-treewidth graphs.

There are two separate issues here.

How to use efficient solvers for $Ax=b$ in order to apply $A^{1/2}b$.
How to compute the determinant.

The short answers are 1) use rational matrix function approximations, and 2) you don't, but you don't need to anyways. I address both of these issues below.

Matrix square root approximations

The idea here is to convert a rational function approximation for scalar functions into a rational function approximation for matrix functions.

We know that there exist rational functions that can approximate the square root function extremely well,
$$\sqrt{x} \approx r(x) := \frac{a_1}{x+b_1} + \frac{a_2}{x+b_2} + \dots + \frac{a_N}{x+b_N},$$
for positive $b_i$. Indeed, to get high accuracy on the interval $[m,M]$, you need $O(\log \frac{M}{m})$ terms in the series. To get the appropriate weights ($a_i$) and poles ($-b_i$), just look up rational function approximation online or in a book.

Now consider applying this rational function to your matrix:
$$r(A) = a_1(A + b_1 I)^{-1} + a_2(A + b_2 I)^{-1} + \dots + a_N(A + b_N I)^{-1}.$$

Owing to the symmetry of $A$, we have
\begin{align}
||A^{1/2} - r(A)||_2 &= ||U\left(\Sigma^{1/2} - r(\Sigma)\right)U^*||_2, \\
&= \max_i |\sqrt{\sigma_i} - r(\sigma_i)|
\end{align}
where $A = U \Sigma U^*$ is the singular value decomposition (SVD) of $A$. So, the quality of the rational matrix approximation is equivalent to the quality of the rational function approximation at the location of the eigenvalues.

Denoting the condition number of $A$ by $\kappa$, we can apply $A^{1/2}b$ to any desired tolerance by performing $O(\log \kappa)$ positively shifted graph Laplacian solutions of the form,
$$(A + bI)x=b.$$

These solutions can be done with your favorite graph Laplacian solver—I prefer multigrid type techniques, but the one in the paper you cite should be fine, too. The extra $bI$ only helps the convergence of the solver.

For an excellent paper discussing this, as well as more general complex analysis techniques that apply to nonsymmetric matrices, see Computing $A^α$, $\log(A)$, and related matrix functions by contour integrals, by Hale, Higham, and Trefethen (2008).

Determinant "computation"

The determinant is harder to compute. As far as I know, the best way is to compute the Schur decomposition $A = Q U Q^*$ using the QR algorithm, then read off the eigenvalues from the diagonal of the upper-triangular matrix $U$. This takes $O(n^3)$ time, where $n$ is the number of nodes in the graph.

However, calculating determinants is an inherently ill-conditioned problem, so if you ever read a paper that relies on computing determinants of a large matrix, you should be very skeptical of the method.

Luckily, you probably don't actually need the determinant. For example,

To draw samples from a single Gaussian distribution $N(0,A^{-1})$, the normalization constant is the same at all points so you never need to compute it.
If your Laplacian matrix $A = A_x$ represents the inverse covariance of a local Gaussian approximation at point $x$ to a non-Gaussian distribution, then the determinant does indeed change from point to point. However, in every effective sampling scheme I know (including Markov chain Monte Carlo, importance sampling, etc.) what you really need is the determinant ratio,
$$\det(A_{x_0}^{-1}A_{x_p}),$$
where $x_0$ is the current point, and $x_p$ is the proposed next sample.

We can view $A_{x_0}^{-1}A_{x_p}$ as a low-rank update to the identity,
$$A_{x_0}^{-1}A_{x_p} = I + Q D Q^*,$$
where the effective numerical rank, $r$, of the low-rank update is a local measure of how non-Gaussian the true distribution is; typically this is much lower than the full rank of the matrix. Indeed, if $r$ is large, then the true distribution is locally so non-Gaussian that one ought to question the whole strategy of trying to sample this distribution using local Gaussian approximations.

The low-rank factors $Q$ and $D$ can be found with randomized SVD or Lanczos by applying the matrix
$$A_{x_0}^{-1}A_{x_p} -I$$
to $O(r)$ different vectors, each application of which requires one graph Laplacian solution. Thus the overall work for getting these low rank factors is $O(r \max(n,E))$.

Knowing $D = \text{diag}(d_1,d_2,\dots,d_r)$, the determinant ratio is then
$$\det(A_{x_0}^{-1}A_{x_p}) = \det(I + Q D Q^*) = \exp\left(\sum_{i=1}^r \log d_i\right).$$

These low rank determinant ration calculation techniques can be found in A Stochastic Newton MCMC Method for Large-Scale Statistical Inverse Problems with Application to Seismic Inversion, by Martin, et al. (2012). In this paper it is applied to continuum problems, so the "graph" is a grid in 3D space and the graph Laplacian is the actual Laplacian matrix. However, all the techniques apply to general graph Laplacians. There are probably other papers applying this technique to general graphs by now (the extension is trivial and basically what I just wrote).


What kind of optimization problem is that? I am new here as a writer but I read this group from time to time.
I am thinking about the following problem.

Problem description:

Assume we have an area $A$ of size $1000 \times 1000$ cells.
One cell is addressed with $(x,y)$ pair, where $x$ and $y$ are positive integers.
We are given the set of points (locations) on area $A$, lets say we have $N$ locations. These locations are fixed and given as an input. In practice N is lower than 1000.
In each location we can build a sender station that sends some signal. Sender stations can have 4 levels: 0,1,2,3. Building a sender station with proper level costs: $c_0=0$, $c_1>0$, $c_2>c_1$ and $c_3>c_2$ respectively. Costs are equal for each location. Moreover costs are fixed and given as an input. Each sender station covers given circular area with signal. Radius are following: $r_0=0$, $r_1>0$, $r_2>r_1$, $r_3>r_2$. Radius is fixed and given as an input.

Question: What level of sender station should be build in each location in such a way, that: all locations are covered with signal and the total cost of building is minimized?

My question to that is: what kind of theoretical problem is that? Is there some easy transformation to some well known optimization problem?

This is not a homework from university, just my own riddle :)

As pointed out in the comments already, this is an instance of weighted geometric set cover. Here are some recent relevant references:
http://www.divms.uiowa.edu/~kvaradar/paps/weightedcover.pdf
See also the follow up work:
http://www.cs.uwaterloo.ca/~tmchan/cover_soda.pdf


Finding balls that contain a point Suppose you are given a collection of $n$ balls in $\mathbb{R}^d$, and you want to preprocess them in such a way that you can later query them to find all spheres which contain any test point.

What efficient solutions are known for this problem?

The trivial answer is to just do a linear scan over all the spheres, which takes no preprocessing time but requires an overhead of $O(n)$ per query.

In 1D you can solve the problem using an interval tree, giving $O(\log(n) + k)$ query time with $O(n \log(n))$ preprocessing and $O(n)$ space, but it isn't clear to me that this generalizes.

I suspect there should be some sort of reduction here, since I can't seem to find any discussion of this problem in the literature which leads to me to think that it is trivial (though I am probably searching for the wrong terms).

There is a reduction to metric range searching in hyperbolic geometry with the signature $(+++ ... -)$, but I don't know how to do hyperbolic range searching efficiently (so it isn't much help).

If this question turns out to be too easy, you can also consider the situation where the set of balls is dynamic.

Note that point location in an arrangement of balls (of different radii) is equivalent to point location in an arrangement of hyperplanes one dimension higher by using the usual paraboloid lifting map $(x_1, \ldots, x_d) \mapsto (x_1, \ldots, x_d, \sum_i x_i^2)$. If you call this lifting map $\Phi$, then it's easy to see that $p \in B$ if and only if $\Phi(p)$ is above $\Phi(B)$.

Now you have the problem of point location in an arrangement of hyperplanes (note that once you have such a structure it's usually easy to annotate each cell with the list of hyperplanes it is above). That problem can be solved by a variety of methods: for example there's an algorithm by Meiser that runs in time $O(d^5 \log n)$ but requires $n^d$ space. It's not clear from the question which is more important: space or time...


Finding an injective mapping between two sets that maximizes a similarity function I have a practical application where I need to map elements from one set (A) to another (B).

Sets A and B can both have arbitrary numbers of elements
Elements from A and B need to be paired up so that every element can only be used once.
Elements can be left unpaired as well.
A similarity matrix can be calculated: how well any element from A maps to any element from B.
The goal is to find a mapping that maximizes the sum of these similarity scores.

Brute-forcing all the options gives factorial complexity which gets out of hand fast. However, for many examples a simple greedy approach seems to work fine - iteratively add the edge which has the maximum score in the similarity matrix, making sure that the restrictions still apply.

Is there any guarantee that this greedy approach will give me the maximized result? I haven't been able to come up with a good counter-example but that doesn't mean they don't exist.

The simplest counter-example is something like an "anti-multiplication table": for $A=B=\left\{1,2,\ldots,n\right\}$ let's define the cost function as $cost(a, b) = n^2 - ab$. The greedy algorithm will fail for $n \ge 2$.

The problem you are solving is called the assignment problem and it's well studied. It can be solved in polynomial time by the Hungarian algorithm, for example.


Find the optimal way to use combinations of summands to get the most sum with a limited number of summands I have a bit of a problem, I have a set of sums that add up to X, like so:

A: $i + j + k = X$

B: $t + z = X$

C: $z + z = X$

D: $j + j + k + k = X$

I have a limited number of summands so for example I have: 12 of $i$, 35 of $z$, 12 of $j$, and 18 of $k$, 21 of $t$.

What I need is an algorithm that will determine the best way to use those combinations so that I end up with the most complete sums of $X$

So in the example above using:

17 of combination $C$, 1 of combination $B$, and 12 of combination $A$, total 30 sums of $X$, 72 summands used

is worse then using:

21 of combination $B$, 7 of combination $C$, and 6 of combination $D$, total 34 sums of $X$, 80 summands used

EDIT:

To further explain:

using 21 of combination $B$ will "spend" 21 $t$ and 21 $z$ leaving us with: 12 of $i$, 14 of $z$, 12 of $j$, 18 of $k$, 0 of $t$

using 7 of combination $C$ will "spend" 14 of $z$ (because it uses 2 summands of $z$ to be achieved) leaving us with: 12 of $i$, 0 of $z$, 12 of $j$, 18 of $k$, 0 of $t$

using 6 of combination $D$ will spend 12 of $j$ and 12 of $k$ (because it uses both of them twice) leaving us with: 12 of $i$, 0 of $z$, 0 of $j$, 6 of $k$, 0 of $t$

we can no longer make combinations that will add up to $X$ thus the algorithm is concluded.

The problem is a generalization of the set packing problem (exercise: why?), and therefore it is NP-hard even to approximate in a very weak sense.  See Maximum Set Packing and Maximum Clique in the compendium.


Programming languages with canonical functions Are there any (functional?) programming languages where all functions have a canonical form? That is, any two functions that return the same values for all set of input is represented in the same way, e.g. if f(x) returned x + 1, and g(x) returned x + 2, then f(f(x)) and g(x) would generate indistinguishable executables when the program is compiled.

Perhaps more importantly, where/how might I find more information on canonical representation of programs (Googling "canonical representation programs" has been less than fruitful)? It seems like a natural question to ask, and I'm afraid that I just don't know the proper term for what I am looking for. I'm curious as to whether it is possible for such a language to be Turing complete, and if not, how expressive a programming language you can have, while still retaining such a property.

My background is rather limited, so I would prefer sources with fewer prerequisites, but references to more advanced sources may be cool too, as that way I'll know what I want to work towards.

The extent to which this is possible is actually a major open question in the theory of the lambda calculus. Here's a quick summary of what's known:

The simply-typed lambda calculus with unit, products, and function space does have a simple canonical forms property. Two terms are equal if and only if they have the same beta-normal, eta-long form. Computing these normal forms is also quite straightforward.
The addition of sum types greatly complicates matters. The equality problem is still decidable (the keyword to search for is "coproduct equality"), but the known algorithms work for extremely tricky reasons and to my knowledge there is no totally satisfying normal form theorem. Here are the four approaches I know of:

Neil Ghani, Beta-Eta Equality for Coproducts, TLCA 1995.
Vincent Balat, Roberto di Cosimo, Marcelo Fiore, Extensional normalisation and type-directed partial evaluation for typed lambda calculus with sums, POPL 2004.
Sam Lindley, Extensional Rewriting with Sums, TLCA 2007.
Arbob Ahmad, Daniel R. Licata, and Robert Harper, A Proof-Theoretic Decision Procedure for the Finitary Lambda-Calculus. WMM 2007.

The addition of unbounded types, such as natural numbers, makes the problem undecidable. Basically, you can now encode Hilbert's tenth problem.
The addition of recursion makes the problem undecidable, because having normal forms makes equality decidable, and that would let you solve the halting problem.


When can a convex function induce submodularity? Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which either  (1) $f' < c$ for some given constant $c$ or (2) $f'$ minimizes.

Is either of these questions for any class of $f$ known to be solvable in $poly(n)$ time?
For any class of $f$ is $f'$ known to become submodular?

Typically I am dealing with a $f(\vec{x}) = SpectralNorm ( A + \vec{x}.\vec{M} )$ where the matrices are $2n$ dimensional real symmetric matrices with entries in $\{0,1,-1 \}$ , $\vec{x} \in [-1,1]^n$ and the matrices in the coordinates of the vector (in matrix space) $\vec{M}$ being simultaneously diagonalizable. Any advice specific to this class would be most helpful.

The notion of sub-modularity you use is non-standard. Usually you consider set functions with domain $\lbrace 0, 1\rbrace^n$. But to answer your questions, the Lovász extension establishes the following relationship between sub-modularity and convexity:

A set-function $F$ is sub-modular if and only if its Lovász extension $f$ is convex. For a proof see Proposition 6 in [1]. To go a bit further, e.g. Proposition 2.3 in [2] establishes the fact the very set function can be written as a difference of two sub-modular function. Conversely, the Lovász extension of every set function is DC (difference of convex functions).

The converse is not true: Not every convex function restricted to  $\lbrace 0, 1\rbrace^n$ is sub-modular. Form your description I assume that you matrix is positive semi-definite. But it is not clear to me how you define the convex $f(x)$? With that information, you can start checking sub-modularity.

[1] https://hal.archives-ouvertes.fr/file/index/docid/535950/filename/submodular_tutorial.pdf
[2] http://www.ml.uni-saarland.de/Publications/HeinSetzer-BeyondSC%282011%29-Supplement.pdf


State of the art algorithms for community detection in graphs Is anyone aware of the must read papers to get knowledge of the most recent algorithms and method for community detection in graphs, especially those that represent social networks?

There's a recent paper [1] on dense subgraph (i.e. community) detection in the context of distributed computing.
In [1], each node of the graph represents an operating entity (i.e. runs an instance of a distributed algorithm) and each node can communicate with its neighboring nodes by sending messages. The graph itself can change (slowly) over time. Note that the connections in social networks evolve over time, so considering a dynamic graph seems like the right model.
By running a distributed algorithm, each node can locally determine whether it's part of a dense subgraph. You might want to consult the related work section of [1] to get pointers to other references.

[1] Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Amitabh Trehan: Dense Subgraphs on Dynamic Networks. DISC 2012: 151-165. Full paper available at http://arxiv.org/abs/1208.1454


Dependent C-style types with subtyping rule I'm looking for previous work regarding an extension of a C-style type system in which types may have constraints and have a defined subtyping rule. In particular, I'm interested in defining algebra-like rules for types on which an order relation exists.

I will use integers for the rest of the examples, but those could be swapped for any kind of object that defines a total order relation.

Right now, I have a system that allows me to define a type as being a pair $(T, \phi)$ where $T$ is a "basic" C-style type (not a pointer, for instance) and $\phi$ is a constraint expressed in a simple language that is basically an extension of propositional calculus. For example, $(\texttt{int}, (>30)\ \text{and}\ (<40))$ would represent the type of integers between 30 and 40. This is similar to what happens in Dependent types, but is significantly less expressive.

I also define a subtyping rule based on the Liskov substitution principle, that specifies that given two types $\mathcal{T}_1 := (T, \phi_1)$ and $\mathcal{T}_2 := (T, \phi_2)$, $\phi_1 \vdash \phi_2 \implies \mathcal{T}_1 <: \mathcal{T}_2$. For instance,
$$
(\texttt{int}, (>30)\ \text{and}\ (<40)) <: (\texttt{int}, (>0)\ \text{and}\ (<100))
$$

For my needs, I am not interested in equivalence or isomorphism between types, only subtyping. I believe that by such "reductions", this flavour of dependent typing can be proved to be decidable.

I've been searching for previous works regarding something similar to what I have right now, but most of the works seem to focus on higher-order lambda calculus. This thread lists various articles regarding such works.

I'm struggling understand what to look for, as I do not know how such a system could be described, because "dependent types" and "subtyping" are obviously very broad fields and lead me to very general papers, while I'd like to find something that is more specific and less expressive.

EDIT: To clarify, the "C-style type" enhanced by a formula is generally a numeric data type, but could be struct if the struct were to define an order relation. I'm not specifically looking for anything regarding arrays, but it would be a "nice to have".

I think the best setup here is Liquid Types, but compared to the original Liquid Types paper, you would want a much weaker language of constraints. Also, if you don't need type inference, it's even easier.

You'd still have to solve linear programs, though. Consider this function:

{int | (< 30) /\ (>= 10)} foo({int | (> 20)} bar, {int | (<= 70)} baz) {...}

and you do some arithmetic on bar and baz inside the function. Then, to type check the function, you'd have to make sure that this expression takes a value between 10 and 29, which means you'd still need to solve linear programming (treating all non-constant multiplication as atoms), which is NP-complete. However, it is known that linear programming can be polynomial if you fix the number of variables involved. What implications do this fact have on our system? I don't really know as I'm not an expert in this area.

But I suspect what you really want is some sort of symbolic execution or abstract interpretation. If your language is completely first-order and doesn't have pointers, both should be pretty easy, and would involve far less human work (i.e. type annotations).


Regular expressions of families of regular expressions I was reading about the Star Height Problem and noticed that Eggan's family of regular expressions follows a simple pattern which can be described by a regular expression. My question is: are there any interesting results about regular expressions which describe families of regular expressions? Can this process be continued further, so you have a regex describing a family of regexes each of which in turn describes a family of regexes?
Just a thought.

Regular languages are closed under union, concatenation and star, so regular expressions under regular expressions describes regular languages. So, regex, that describe regex, that describe regex still describe family of regular languages, and you can continue that process as long, as you want.

Here, by «describe» I mean that first, you have just regex, like $(aa|b)^+ = R_0$  and regex $(a|bb)^+ = R_1$, than you describe regex level 1 like $(R_0R^*_1R_0)$, this regex describe languages  $(aa|b)^+(aa|b)^+$, $(aa|b)^+(a|bb)^+(aa|b)^+$, $(aa|b)^+(a|bb)^+(a|bb)^+(aa|b)^+$, …  and so on.

In other terms regex under regex can be described using composition operation. Let $L$ be a regular language under alphabet $\Sigma$ and $|\Sigma| = n$. Consider regular languages $L_{\sigma_1}, L_{\sigma_2}, \ldots, L_{\sigma_n}$  under some alphabet $\Delta$. So, for each word $w$ from $L$ we substitute letter $w[i] = \sigma_j$ by corresponding language $L_{\sigma_j}$, so $w = w[1]w[2]\ldots w[k] \to L_{w[1]}L_{w[2]}\ldots L_{w[k]} $  and union of all such languages, forms language $comp(L,L_1,\ldots,L_n)$. So, level of regex under regex is just number of composition operations, that were used. And regular languages are closed under composition-operation.

But there are some interesting results obtained by technique that's very closed to the one, that  you describe. I mean the $\delta-$operation. $\delta(L)$ is a such language, that every word from $\delta(L)$ yields by such tree, that every path in that tree lies in $L$. To learn more about it see the paper .


Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$ I'd like to know (related to this other question) if lower bounds were known for the following testing problem: one is given query access to a sequence of non-negative numbers $a_n \geq \dots\geq a_1$ and $\varepsilon \in (0,1)$, with the promise that either $\sum_{k=1}^n a_k = 1$ or $\sum_{k=1}^n a_k \leq 1-\varepsilon$.

How many queries (lookups) are sufficient and necessary for an (adaptive) randomized algorithm to distinguish between the two cases, with probability at least $2/3$?

I have found a previous post that gives a logarithmic (in $n$) upper bound for the related problem of approximating the sum, and a roughly matching lower bound on that problem for deterministic algorithms; but couldn't find a result for the specific problem I am considering (in particular, randomized algorithms).

Edit: Following the answer below, I guess I should have been clearer: in the above (and particularly in the asymptotics for the lower bound), $n$ is the "main" quantity seen as going to infinity, while $\varepsilon$ is an (arbitrarily small) constant.

Here are the lower bounds I can show. I conjecture that for a fixed $\epsilon$, the right lower bound is $\Omega( \log n)$, but naturally I might be wrong.

I am going to use a decreasing sequence (just for convenience). The basic mechanism is breaking the sequence into $L$ blocks. In the $i$th block there are going to be $n_i$ elements (i.e., $\sum_i n_i = n$).

In the following, we want the algorithm to succeeds with probability $\geq 1-\delta$, for some parameter $\delta >0$.

First lower bound: $\displaystyle \Omega\left( \frac{1}{\epsilon} \log \frac{1}{\delta} \right)$.

The $i$th block has $n_i = 2^{i-1}$ elements, so $L = \lg n$. We set the value of all the elements in the $i$th block to be $(1+X_i)/(2n_iL)$, where $X_i$ is a variable that is either $0$ or $1$. Clearly, the total sum of this sequence is
$$
\alpha = \sum_{i=1}^L \frac{1+X_i}{2n_i L} = \frac{1}{2} + \frac{1}{2L}\left(\sum_{i=1}^L X_i \right).
$$
Imagine picking each $X_i$ with probability $\beta$ to be $1$ and $0$ otherwise.  To estimate $\alpha$, we need a reliable estimate of $\beta$. In particulate, we want to be able to distinguish the base $\beta = 1-4\epsilon$ and, say, $\beta=1$.

Now, imagine sampling $m$ of these random variables, and let $Z_1, \ldots, Z_m$ be the sampled variables.  Settings $Y = \sum_{i=1}^m (1-X_i)$ (note, that we are taking the sum of the complement variables), we have $\mu = E[Y] = (1-\beta) m$, and Chernoff inequality tells us that if $\beta =1-4\epsilon$, then $\mu = 4\epsilon m$, and the probability of failure is
$$
 P\left[ Y \leq 2\epsilon m \right] =  P\left[ Y \leq (1-1/2) \mu \right] \leq \exp \left( -\mu (1/2)^2 / 2 \right) = \exp \left( -\epsilon m / 2 \right).
$$
To make this quantity smaller than $\delta$, we need $\displaystyle m \geq \frac{2}{\epsilon} \ln \frac{1}{\delta}$.

The key observation is that the Chernoff inequality is tight (one has to be careful, because it is not correct for all parameters, but it is correct in this case), so you can not do better than that (up to constants).

Second lower bound: $\Omega( \log n / \log \log n)$.

Set the $i$th block size to be $n_i = L^i$, where $L = \Theta( \log n / \log \log n)$ is the number of blocks. An element in the $i$th block has value $\alpha_i = \Bigl(1/L\Bigr)/n_i$. So the total sum of the values in the sequence is $1$.

Now, we might decide to pick an arbitrary block, say the $j$th one, and set all values in its block to be $\alpha_{j-1} = L \alpha_j$ (instead of $\alpha_j$). This increases the contribution of the $j$th block from $1/L$ to $1$, and increase the total mass of the sequence to (almost) $2$.

Now, informally, any randomized algorithm must check the value in each one of the blocks. As such, it must read at least $L$ values of the sequence.

To make the above argument more formal, with probability $p=1/2$, give the original sequence of mass $1$ as the input (we refer to this as original input). Otherwise, randomly select the block that has the increased values (modified input). Clearly, if the randomized algorithm reads less than, say, $L/8$ entries, it has probability (roughly) $1/8$ to detect a modified input.  As such, the probability this algorithm fails, if it reads less than $L/8$ entries is at least
$$
 (1-p)(7/8) > 7/16 > 1/3.
$$

P.S.  I think by being more careful about the parameters, the first lower bound can be improved to $\Omega(1/\epsilon^2)$.


Shortest Path Algorithm for large graph but short paths I have a graph (say, about a million vertices) where the degree of every vertex is somewhat large (about 100 000). We want to find the shortest path between two vertices -- but we know the graph is such that there is a very small upper limit (say, 10) for the shortest path length. There are no edge weights (or consider them 1).

Edit: also, I probably need to run this several times on different pairs. What data structure could be used to speed this up?

Assuming that you’re using BFS — or, more likely, a bidirectional BFS — and that you have no guiding heuristic (for an A* search or the like), what you’d probably like to optimize is the time it takes to consider the neighbors of each newly discovered node. After all, if each node has 100 000 neighbors, but there are only about 1 000 000 nodes in total, most nodes will be irrelevant (i.e., already visited) really fast.

The “normal” approach would be to have, say, adjacency lists for every node, and some global set data structure (e.g., a hash) for determining whether you’ve already seen a given node. This would keep the “already visited” checks fast, but you’d have to wade through lots of irrelevant neighbors.

One alternative would be to do it the other way around. Keep a global structure (like a linked list) that lets you iterate over the remaining relevant nodes (and remove the ones you visit), and then have a lookup-table for every node instead. If the node you’re looking at in the global list is found in the local lookup-table, you add it to your queue and remove it from the global list. That way, the number of potential nodes you’d look at would (probably) decrease quite a bit.

This approach would only help after a while, though; at least in the first iteration, it would be better to iterate over the neighbors of a given node, and to look them up in a global look-up table. You can do both, however…

For the local tables, you could use some compact (possibly perfect) hash tables that would let you efficiently check for membership, as well as iterate over the neighbors in linear time. Or, if you’d like to keep things simple (probably a good idea in this case), just keep the neighbor IDs in a sorted array, and use bisection for lookup checks.

For the global list/table you need something more, however. You’d like the structure to do several things:

Let you look up membership efficiently;
Iterate over the members in linear time (as a function of the number of remaining members);
Remove members efficiently; and
Reset the table efficiently, for running multiple searches.

I’m sure there are several ways of dealing with this, but one I’ve come up with for my current research code lets you do 1., 3. and 4. in constant time with a really small memory overhead. The structure assumes that every member is represented by an integer $0\ldots n-1$, and that you have two tables of size $n$ that can accomodate such integers; let's call these $\pi$ and $\pi^{-1}$. You can then use these to represent a permutation of the members — as well as the inverse permutation. Basically, the inverse permutation $\pi^{-1}$ is simply an array of members (answering the question “Which member is in position $k$?”), while the permutation ($\pi$) gives you the location of any given member. In addition, you store the number of remanining members, $m$.

Initially, you need to fill these two arrays so that $\pi = \pi^{-1} = \langle 0, 1, 2, \ldots, n-1\rangle$, as well as set $m=n$. To reset it, though, you only need to set $m=n$ (constant time).

Adding and removing elements only requires you to swap the given member into the position just inside/outside the “cutoff point” given by $m$ (updating both $\pi$ and $\pi^{-1}$), and then to increment or decrement $m$, as needed.

To make best use of this setup, you would only have to compare $m$ to size of the neighbor array of the current node in your BFS. Iterate over whichever is smaller, and do the lookups in the other one.


Examples of Computer-Found Optimal Strategies in Games I am looking for examples in games such as Go, Chess, and Backgammon, where the believed-optimal move turned out to be suboptimal as a computer found better strategies.

The best known example is probably checkers (also known as draughts), which has been solved recently in 2007 (the game is a draw). Other examples are listed in the Wikipedia page on solved games; notable among them are connect four and nine men's morris. Additionally, several chess endgames have been solved.

This perhaps doesn't seem like an answer to your question, but if an expert (such as Marion Tinsley) loses to a computer program, then the computer must have found a "more optimal" move.


Example of where violation of strict positivity condition in inductive types leads to inconsistency Most dependent typed systems have a strict positivity conditions for inductive types. Does anybody know an example where violation of the condition leads to inconsistency in the system?

It is actually possible to relax strict positivity and remain consistent. For instance, it suffices to only have a positivity condition. That is, we can accept type definitions like

$$
  T \triangleq \mu\alpha. (\alpha \to 2) \to 2
$$

where recursive type variables occur to the left of an even number of arrows and retain consistency.

However, theories permitting this sort of inductive type do not have set-theoretic models -- you cannot interpret types as sets and terms as elements of sets. In this case, we are saying that $T$ is isomorphic to its double-powerset (i.e., $T \simeq \mathcal{P}(\mathcal{P}(T))$), and this violates Cantor's theorem.

Since dependent type theories are often used to formalize mathematics, their designers are usually hesitant to add principles which are not compatible with a set-theoretic semantics, even if they are consistent.

EDIT: I'm adding this edit in response to Andrej's question. The type $T$ is consistent if you add it to (say) Agda; there are no problems with it at all. We only have a problem if we combine non-strict positivity with excluded middle.

The intuition for why is safe is (IMO) best seen through the lens of parametricity. In System F, we can show using parametricity that for any definable functor $F$, the type $\mu F \triangleq \forall \alpha.\; (F\alpha \to \alpha) \to \alpha$ is indeed an inductive type.

Now, recall that a definable functor $F$ is a type operator $F : \ast \to \ast$, together with an operator
$$\mathrm{map} : \forall \alpha,\beta.\;(\alpha \to \beta) \to F\;\alpha \to F\;\beta$$
satisfying the functoriality conditions (i.e., $\mathrm{map}\;id = id$ and $\mathrm{map}\;f\;\circ \mathrm{map}\;g = \mathrm{map}\;(f \circ g$).

Now, we can define a type operator for the double powerset

$$C = \lambda \alpha.\; (\alpha \to 2) \to 2$$

and because $\alpha$ occurs only positively, we can also define a map operator for it:

$$
map_C = \lambda f : \alpha \to \beta, a' : (\alpha \to 2) \to 2, k : \beta \to 2.\; a' \;(\lambda a:\alpha.\; k\;(f\;a))
$$

So we know that $T = \mu C$ is a legitimate inductive type.


Looking for Literature Source for Following idea I am quite certain that I am not the first to entertain the idea that I am going to present.  However, it would be helpful if I can find any literature related to the idea.

The idea is to construct a Turing Machine M with the property that if P=NP then M will solve 3-SAT in polynomial time.  (The choice of 3-SAT is arbitrary.  It could be really any problem in NP).

Just to be clear, this is not a claim that P=NP.  In fact, I believe the opposite.  I merely state that if P=NP, then M will provide a polynomial-time solution.  If you are looking for an efficient solution, I should warn that this is far from efficient.

M is constructed as follows:
first, assume a canonical encoding for all Turing Machines, and apply a numbering to these machines.  So, there is a Turing Machine number 1, a number 2, etc.  The idea of a Universal Turing Machine that can read the format for a provided machine and then simulate that machine's running on separate input is pretty well known.  M will employ a Universal Turing Machine to construct and simulate each Turing Machine in turn.

It first simulates the running of Turing Machine 1 for a single step.
It then looks at the output of Turing Machine 1.
It the simulates the running of Turing Machine 1 for two steps and looks at output,
then proceeds to simulate Turing Machine 2 for 2 steps.
It continues and loops in this fashion, in turn running Turing Machine 1 for k steps then 2 for k steps ... then eventually machine k for k steps.

After each simulation run, it examines the output of the run.  If the output is an assignment of variables satisfying the 3-SAT problem instance, M halts in an accept state.  If on the other hand, the output is a proof-string in some verifiable proof-language with the proven result that the problem instance is not satisfiable, M halts in a reject state.  (For a proof-language, we could for example, use the Peano Axioms with Second-Order logic and the basic Hilbert-style logical axioms.  I leave it as an exercise for the reader to figure out that if P=NP, a valid proof-language exists and is polynomial-time verifiable).

I will claim here that M will solve 3-SAT in polynomial time if and only if P=NP.
Eventually, the algorithm will find some magical Turing Machine with number K, which just so happens to be an efficient solver for the 3-SAT problem, and is able to provide a proof of its results for either success or failure.  K will eventually be simulated running poly(strlen(input)) steps for some polynomial.  The polynomial for M is roughly the square of the polynomial for k in the largest factor, but with some terrible constants in the polynomial.

To reiterate my question here: I want to know if there is a literature source that employs this idea.  I am somewhat less interested in discussing the idea itself.

It seems that this idea is attributed to Levin (It is called optimal search). I believe this fact is well known. A similar algorithm is described in wikipedia for instance, although using the subset sum problem. In this article from scholarpedia you can find several references on the subject, including a pointer to the original algorithm and to some other optimal search algorithms.

Comment 1: Levin's optimal search guarantees that if $\varphi$ is a satisfiable instance then a solution will be found in polynomial time assuming $P=NP$. If
$\varphi$ is not satisfiable the algorithm may not terminate.

Comment 2: As Jaroslaw Blasiok pointed out in another answer, this algorithm does not decide Sat only assuming P=NP.


Higher order Quines - when do super Quines exist? The normal Quine - a program that prints its own code - is a special case of an n-Quine.

An n-Quine is a program that prints code for a different program that after n iterations of printing and running will yield its own source (it has a period of n, and it does not repeat during the first n-1 iterations).

A "super Quine" is a (n>1)-Quine that is shorter than all the shortest n-Quines with smaller n (including the shortest 1-Quine = normal Quine).

When are super Quines possible? It's easy enough to think of a language where they are. But it is hard to think of an example in any general purpose language.

What factor determines the presence or absence of super Quines in a language?

There's a good chance this question is independent of ZFC for most programming languages.  In particular, I'd expect it to be true of any language where the shortest Quine is longer than the Kolmogorov complexity decidability bound, the integer $n$ such that no string can be proven to have Kolmogorov complexity $> n$.  I don't know to prove this, since even if you could express a Quine by a shorter program it wouldn't be a Quine, but I would expect a similar result to apply.

However, if the above argument were true, the argument itself might also be unprovable in ZFC, since it would require showing that no Quines exist below the complexity bound.


Efficiently getting bits of N! ? Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?

i.e. Given $N = 2^\eta$, $M = 2^\mu$ (with $N$, $M \in \mathbb{Z}$), find bit $2^\mu$ of $(2^\eta)!$ in $O( p(\eta, \mu) )$.

Note: I have asked this on mathoverflow.net here and have not been getting any answers so I have cross-posted.

From the comment on the other site, Gene Kopp points out that one can efficiently compute the lower order bits by doing modular arithmetic and higher order bits using Stirling's approximation, so this question is really 'how efficiently can one compute the middle order bits?'.

Dick Lipton has a beautiful post from 2009 on the relationship between the factorial function and factoring. There's a lot there that is unrelated to this question, but one salient point is this theorem:

  If $n!$ can be computed by a
  straight-line arithmetic computation
  in $O(\log^{c} n)$ steps, then
  factoring has polynomial size
  circuits.

I suspect that this is evidence that your question, especially within the time bounds you mention, is going to be difficult to answer.


How to define eta-equivalence for F-omega types? There are (at least) two styles for defining a (declarative) equivalence judgement for a typed lambda calculus:

via a plain relation  $t_1 = t_2$,
via an indexed relation $\Gamma \vdash t_1 = t_2 : T$.

Barendregt [1] e.g. uses the simpler former style, while other sources often seem to be preferring the latter.

I have only seen the first style being used for the case of simple beta equivalence (as in Barendregt). Is it possible to use this style even in the presence of an eta-rule, esp considering that eta-expansion does not necessarily preserve well-formedness?

More specifically, I'm interested in the (simple?) case of eta-equivalence for F-omega types. Any pointers are welcome.

[1] H. Barendregt, Lambda Calculi With Types. In: Handbook of Logic in Computer Science, Vol 2. Oxford University Press 1992

The first approach is subsumed by the second, sort of (because the first approach is slightly broken).

One should never consider expressions with free variables without explicitly specifying a context in which they appear (this is a lesson one learns as soon as one wants to formalize $\forall$ and $\exists$ that are allowed to range over possibly empty types or sets).

In a single-sorted theory, equations without context $t_1 = t_2$ can always be equipped with a context $\Gamma \vdash t_1 = t_2 : S$ where $S$ is the single sort and $\Gamma = x_1 : S, \ldots, x_n : S$, with $x_i$ being the free variables in $t_1$ and $t_2$.

Leaving the context implicit like that is not quite right. For example, what if I want to write down an equation that involves $x_1$ and $x_2$ in a context which also mentions $x_3$? You might think that sort of thing is going to be useless, but it isn't, not if $x_3$ could come from an empty type.

Also, as soon as you think about categorical semantics you will see that it makes little sense to have bare equations without contexts.

So I would advise you to put your equations in contexts, and then use the shorter form as an abbreviation. One reference where everything is done explicitly in a context all the time is Bart Jacob's "Categorical Logic and Type Theory", Chapter 8 is about polymorphic type theory and might be of particular interest to you.


The average number of annual publications for CS postdocs What is the average number of publications (including conference proceedings), per year, for CS postdoctoral researchers in the US? What are the ways to find out or estimate this number?

The main motive behind this question is to understand where am I standing with my own performance and productivity.

Then you're asking the wrong question.  The right metric to examine isn't the number of publication, but rather your visibility and reputation (and ultimately impact) within the research community.  If the intellectual leaders of your target subcommunity are eager to write you good recommendation letters, it doesn't matter whether you publish one paper a year or ten.  Similarly, if the intellectual leaders in your target subcommunity are not eager to write you good recommendation letters, it doesn't matter whether you publish one paper a year or ten.


Distinguishability a set of permutations Given integers $d<n$, find the largest $k$ such that there exists a set of $k$ permutations $\sigma_1,\cdots,\sigma_k$ on $[n]$, such that any size-$d$ subset $T\subseteq [n]$ is ``distinguishable'' by the permutations.

Here we say that a set $T$ is NOT distinguishable by two permutation $\sigma,\sigma^*$ if we view both permutations as arrangements of $[n]$ into a sequence, and the restricted orders on $T\subseteq [n]$ in both arrangements are the same, otherwise it is distinguishable by $\sigma$ and $\sigma^*$. We say that a subset $T\subseteq [n]$ is distinguished by a collection of permutations if it is distinguishable by every pair of permutations in the collection.

Probably it is hard to express $k$ in terms of $n$ and $d$, so we shoot for asymptotic lower or upper bounds on $k$. Actually I am more interested in the case where $d$ is small (let's say $d=O(\sqrt{n})$). Any previous results or relevant ideas are appreciated.

Here are loose lower and upper bounds.

Fix $d \le n$ as in the post.  Let $k^*$ denote the largest possible value of $k$ meeting the conditions in the post.  We show that $k^* = \exp(\Theta(d\log d)$) for $d\ge 3\sqrt n$, but $k^* \le 2$ for $d\le n^{1/3}$.  I suspect the latter bound can be strengthened (e.g. shown for larger $d$).

Lemma 1. $d!/{n\choose d} \le k^* \le d!$

Proof. The upper bound $k^*\le d!$ holds simply because each chosen permutation induces a distinct permutation on the $d$-subset $\{1,\ldots,d\}$.  For the lower bound, say that two permutations of $[n]$ conflict if, for some $d$-subset $T$ of $[n]$, they induce the same relative order on $T$.  A given permutation $\sigma$ induces a relative order on $n\choose d$ such $d$-subsets.  Each $d$-subset $T$ and relative order on $T$ is induced by $n!/d!$ permutations of $[n]$.  It follows that any given permutation $\sigma$ conflicts with at most $c = {n\choose d} \times n!/d!$ other permutations.  So, any maximal set of pairwise non-conflicting permutations must have size at least $n! / c = d!/{n\choose d}$.  $\diamond$

Corollary 1. If $d\ge 3\sqrt n$, then $k^* = \exp(\Theta(d\log d))$.

Proof. By Lemma 1 and calculation from Stirling's approximation,
$$k^* \ge d!/{n\choose d} = \frac{d^{2d+1}\exp(d^2/2n - 2d+O(1))}{n^d} = \exp(\Omega(d\log d))$$ for $d\ge 3\sqrt n$.
For the upper bound, note $k^*\le d!= \exp(O(d\log d))$.  $~~~~\diamond$

Lemma 2. If $2\le d\le n^{1/3}$, then $k^* = 2$.

We give two proofs.

Proof 1.
Consider any $d$ with $2\le d\le n^{1/3}$.
To see that $k^*\ge 2$, note that (as Zihan noted in his comment) for $d\ge 2$ every $d$-subset is distinguishable by the identity permutation and its reverse.
To finish we show $k^*\le 2$.

Fix any three permutations $\sigma_1, \sigma_2, \sigma_3$. Assume WLOG that $\sigma_1$ is the identity permutation: $\sigma_1(k) = k$ for $k\in [n]$. We show that some $d$-subset of $[n]$ is not distinguishable by some pair of the three permutations.

If $\sigma_2$ has an increasing subsequence of length $d$, then that subsequence induces the same permutation on its $d$-subset $T$ that $\sigma_1$ does, so $T$ is indistinguishable by $\sigma_1$ and $\sigma_2$, and we are done.

Otherwise, by the Erdős–Szekeres Theorem, $\sigma_2$ has a decreasing subsequence of length $n/d \ge d^2$ on some subset, say $T'$, of $[n]$. On $T'$, $\sigma_1$ is increasing and $\sigma_2$ is decreasing.

Applying the theorem to $\sigma_3$ restricted to $T'$, $\sigma_3$ has either an increasing subsequence of length $\sqrt{d^2} = d$ on some $d$-subset $T''$ within $T'$, or a decreasing subsequence of that length on some $d$-subset $T''$ within $T'$.  In the first case, $\sigma_1$ and $\sigma_3$ don't distinguish $T''$.  In the second case, $\sigma_2$ and $\sigma_3$ don't distinguish $T''$.$~~\diamond$

Here's an alternate proof of Lemma 2, by adapting the proof of the Erdős–Szekeres Theorem, for those who are interested in the details.

Proof 2. Consider any $d$ with $2\le d\le n^{1/3}$.
To see that $k^*\ge 2$, note that (as Zihan noted in his comment) for $d\ge 2$ every $d$-subset is distinguishable by the identity permutation and its reverse.  To finish we show $k^*\le 2$.

Fix any three permutations $\sigma_1, \sigma_2, \sigma_3$. Assume WLOG that $\sigma_1$ is the identity permutation: $\sigma_1(k) = k$ for $k\in [n]$. Assume for contradiction that every $d$-subset $T$ of $[n]$ is distinguishable by each pair of these three permutations.

For each pair $i, j$ with $1\le i < j \le 3$, define $I_{ij}(k)$ to be the maximum size of any subset $T\subseteq [k]$ that contains $k$ such that the order imposed on $T$ by both $\sigma_i$ and $\sigma_j$ is monotonically increasing.  Define $D_{ij}(k)$ to be the maximum size of any subset $T\subseteq \{1,\ldots,k\}$ that contains $k$ such that the order imposed on $T$ by both $\sigma_i$ and $\sigma_j$ is monotonically decreasing.  Define 3-tuple
$$s(k) = \big(I_{12}(k),\,I_{13}(k),\,D_{23}(k)\big),$$
 and $S = \{s(k) : k\in[n]\}.$

Claim 1. For every $k,\ell$ with $1\le k<\ell \le n$, we have $s(k) \ne s(\ell)$.

Before we prove the claim, note that it implies the lemma as follows. The claim implies that $|S| = n$. Each of the three values in any 3-tuple $s(k)$ is in $[d-1]$ (because, for example, there is a subset of $[n]$ of size $I_{12}(k)$ that is not distinguishable by $\sigma_1$ and $\sigma_2$). So $S\subseteq [d-1]^3$, so $n = |S|\le(d-1)^3$, implying that $d>n^{1/3}$, contradicting that $d\le n^{1/3}$ and proving the lemma.

To prove the claim, consider any $k,\ell\in[n]$ with $k<\ell$. Consider the relative order that each of the three permutations induces on the pair $k, \ell$: for each $i\in[3]$, either $\sigma_i(k) < \sigma_i(\ell)$ or $\sigma_i(k) > \sigma_i(\ell)$.  Since $\sigma_1$ is the identity, $\sigma_1(k) < \sigma_1(\ell)$.

First consider the case that $\sigma_2(k) < \sigma_2(\ell)$. By definition of $I_{12}$, there is a subset $T$ of $[k]$ that contains $k$ such that $|T| = I_{12}(k)$ and $\sigma_1$ and $\sigma_2$ are monotonically increasing on $T$.  So $T' = T\cup\{\ell\}$ is a subset of $[\ell]$ that contains $\ell$ such that $|T'| = I_{12}(k)+1$ and $\sigma_1$ and $\sigma_2$ are monotonically increasing on $T'$.  It follows that $I_{12}(\ell) \ge |T'| > I_{12}(k)$.  It follows that $s(\ell) \ne s(k)$ in this case.

For the case when $\sigma_3(k) < \sigma_3(\ell)$, by the same argument $I_{13}(\ell) > I_{13}(k)$, so $s(\ell)\ne s(k)$ in that case.
In the remaining case, $\sigma_2(\ell) < \sigma_2(k)$ and $\sigma_3(\ell) < \sigma_3(k)$.  By a similar argument $D_{23}(\ell) > D_{23}(k)$.  So $s(\ell)\ne s(k)$ in all cases, proving the claim.  $\diamond$

EDIT: Comment on the tightness of the proof of Lemma 2. The proof of Lemma 2 shows the existence of a $d$-subset $T$ which is indistinguishable by two of the permutations and that has the following stronger property: the two permutations are both increasing or both decreasing over $T$.  Given this, I believe the bound of $\Theta(n^{1/3})$ on $d$ is best possible.  That is, I believe that for, say, $d\ge 2n^{1/3}$, choosing appropriate random permutations w.h.p. yields $\exp(\Theta(d\log d))$ permutations such that, for every pair $\sigma$ and $\sigma^*$ of the permutations, there is no $d$-subset $T$ on which $\sigma$ and $\sigma^*$ are both increasing, or both decreasing.  (The argument is similar to the proof of Lemma 1 above, with the additional observation that, for a random permutation, w.h.p. there are only about ${n\choose d}/d!$ $d$-subsets on which the permutation is increasing or decreasing.)

So, to strengthen the lemma, the proof would have to somehow consider indistinguishable subsets on which the two permutations are not monotonic.


Term that can distinguish beta-equivalent normal forms in the untyped lambda calculus I'm trying to work through two (non-assessed) class-work questions and am stuck on a question that seems similar to one I could do.

The first question was to prove that there does not exist a $\lambda$-term $f$ that, given two $\lambda$-terms $m$ and $n$, can determine whether or not they are $\beta$-equivalent — i.e. there is no $f$ such that $\lambda\beta \vdash f \ m \ n = \textbf{t}$ if $m \ =_\beta \ n$ and $\lambda\beta \vdash f \ m \ n = \textbf{f}$ if $m \ \neq_\beta \ n$. I think I have done this relatively easily by appealing to the Scott-Curry theorem.

I'm now stuck on proving the same but for $m, n$ being in normal form. If I try to use the Scott-Curry theorem, showing that the set $A = \{ x = m \mid x \mbox{ in normal form} \}$ is inseparable, so that no $g \equiv f \ m$ can exist, then I cannot show that $A$ is closed under $\beta$-equality, which we require to apply the Scott-Curry theorem. So I don't think this is the correct approach.

Could anyone give me some help on how to formally prove this? I've played around with contexts, Böhm's theorem, etc. I feel like the fact $m, n$ are not required to be closed is important?

Let's split it into two parts:

First let $m$ and $n$ be terms that have a normal form (but are not necessarily in normal form). Let
\begin{align*}
 \mathbf{A} &= \{x \;|\; x =_\beta m\} \\
 \mathbf{B} &= \{x \;|\; x \neq_\beta m \mbox{ and $x$ has a normal form }\}
\end{align*}
These sets are nonempty, disjoint and closed under $\beta$-equivalence, so
we can apply Scott-Curry theorem and conclude that they're inseparable. So there is no algorithm that can determine if two such terms $m$ and $n$ are equal or not.

For the second part: Intuitively, a lambda term cannot distinguish if its arguments are in normal form or not. Suppose we have $f$ that can determine if two terms in normal form $m$ and $n$ are equal or not. Now let $m'$ and $n'$ be terms that have a normal form. We can use a normalizing reduction strategy to reduce them to their normal forms (which is accomplished in a finite number of steps), apply $f$ and determine if they're equal or not, which contradict the previous part.


Strong seeded randomness extractors with low entropy loss I would like to implement a strong seeded randomness extractor for flat sources as a part of my project.

Most of the literature on seeded extractors is concentrated on minimizing seed length. However, low entropy loss is crucial for my construction. What are the known extractors with minimal entropy loss? How efficient is the extractor in practice?

Is there a lower bound on the entropy loss for strong seeded extractors?

Are there any implementations of extractors that I can use off the shelf?

I'm not sure if this is what you are looking for, but as I recall, there is a mathematical proof that AMLS (advanced multi-level strategy) is maximal. This document does not contain the proof, but an outline of it is on page 9: Coin Toss

As a practical example, I seed AMLS with timer output to update a hashed accumulator used for seeding a reference PRNG, whose output I then use for research. The output of the seed accumulator does very well on randomness tests on its own, but it is very slow.


Are there any counterintuitive results in theoretical computer science? Some math and logic paradoxes could be automatically applied to computers probably, but are there any paradoxes that were discovered in computer science itself?

By paradoxes I mean counter intuitive results that look like a contradiction.

I find the fact that network flow is polynomial time counter intuitive. It is seems much harder on first look than many NP-Hard problems. Or putting it differently, there are many results in CS where the running time to solve them is way better than what you would expect it to be.


Mathematical implications of complexity theory conjectures outside TCS Do you know interesting consequences of (standard) conjectures in complexity theory in other fields of mathematics (i.e. outside of theoretical computer science)?

I would prefer answers where:

the complexity theory conjecture is as general and standard as possible; I am ok with consequences of the hardness of specific problems too, but it would be nice if the problems are widely believed to be hard (or at least have been studied in more than a couple of papers)
the implication is a statement that is not known to be true unconditionally, or other known proofs are considerably more difficult
the more surprising the connection the better; in particular, the implication should not be a statement explicitly about algorithms

"If pigs could fly, horses would sing" type of connections are ok, too, as long as the flying pigs come from complexity theory, and the singing horses from some field of math outside of computer science.

This question is in some sense "the converse" of a question we had about surprising uses of mathematics in computer science. Dick Lipton had a blog post exactly along these lines: he writes about consequences of the conjecture that factoring has large circuit complexity. The consequences are that certain diophantine equations have no solutions, a kind of statement that can very hard to prove unconditionally. The post is based on work with Dan Boneh, but I cannot locate a paper.

EDIT: As Josh Grochow notes in the comments, his question about applications of TCS to classical math is closely related. My question is, on one hand, more permissive, because I do not insist on the "classical math" restriction. I think the more important difference is that I insist on a proven implication from a complexity conjecture to a statement in a field of math outside TCS. Most of the answers to Josh's question are not of this type, but instead give techniques and concepts useful in classical math that were developed or inspired by TCS. Nevertheless, at least one answer to Josh's question is a perfect answer to my question: Michael Freedman's paper which is motivated by a question identical to mine, and proves a theorem in knot theory, conditional on $\mathsf{P}^{\#P} \ne \mathsf{NP}$. He argues the theorem seems out of reach of current techniques in knot theory. By Toda's theorem, if $\mathsf{P}^{\#P} = \mathsf{NP}$ then the polynomial hierarchy collapses, so the assumption is quite plausible. I am interested in other similar results.

Here's another example from graph theory. The graph minor theorem tells us that, for every class $\mathcal{G}$ of undirected graphs that is closed under minors, there is a finite obstruction set $\mathcal{Obs(G)}$ such that a graph is in $\mathcal{G}$ if and only if it does not contain a graph in $\mathcal{Obs(G)}$ as a minor. However, the graph minor theorem is inherently nonconstructive and does not tell us anything about how big these obstruction sets are, i.e., how many graphs it contains for a particular choice of $\mathcal{G}$.

In Too Many Minor Order Obstructions, Michael J. Dinneen showed that under a plausible complexity-theoretic conjecture, the sizes of several of such obstruction sets can be shown to be large. For example, consider the parameterized class $\mathcal{G}_k$ of graphs of genus at most $k$. As $k$ increases, we can expect the obstruction sets $\mathcal{Obs}(\mathcal{G}_k)$ to become more and more complicated, but how much so? Dinneen showed that if the polynomial hierarchy does not collapse to its third level then there is no polynomial $p$ such that the number of obstructions in $\mathcal{Obs}(\mathcal{G}_k)$ is bounded by $p(k)$. Since the number of minor obstructions for having genus zero (i.e. being planar) is just two ($\mathcal{Obs}(\mathcal{G}_0) = \{K_5, K_{3,3}\}$), this superpolynomial growth is not immediately obvious (although I believe it can be proven unconditionally). The nice thing about Dinneen's result is that it applies to the sizes of obstruction sets corresponding to any parameterized set of minor ideals $\mathcal{G}_k$ for which deciding the smallest $k$ for which $G \in \mathcal{G}_k$ is NP-hard; in all of such parameterized minor ideals the obstruction set sizes must grow superpolynomially.


Optimal bounds for $k$-wise non-uniform random bits Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$.

  What is the smallest sample space (or, equivalent, how many true independent random bits are needed) to generate $n$ $k$-wise independent Bernoullis with parameter $p\stackrel{\rm def}{=}1/2^t$?

This is not the same as this (related) question, since I don't want to generate uniform marginals in $\{1,\dots,2^t\}$ (which would be one way to simulate the $1/2^t$-biased coins, but one that feels very wasteful).

Alon, Babai, and Itai gave a time bound of $O(n^{k/2})$ for the case $t=1$.  Karloff and Mansour [Theorem 3 of 2] showed that for $2^t = \frac{n}{k}$, a space of size $\Omega(n^k)$ was necessary.

  Is the general trade-off as a function of $t,n,k$ known?

In particular, a simple construction would give an upper bound of
$k(\log n + t)$ bits. However, and here my intuition may be completely off, I would expect it to decrease with $t$? For $k,n$ fixed, increasing $t$ leads to more biased bits, so less entropy overall.

I am not specifically looking for explicit constructions.

[1] Alon, Noga, László Babai, and Alon Itai. "A fast and simple randomized parallel algorithm for the maximal independent set problem." Journal of algorithms 7.4 (1986): 567-583.

[2] Karloff, Howard, and Yishay Mansour. "On construction ofk-wise independent random variables." Combinatorica 17.1 (1997): 91-107.

$$s = \Theta( k \cdot ( t + \log n ) )$$

As the question mentions, there is an upper bound of $s \le k\cdot\max\{t,\lceil \log_2 n \rceil\}$ bits for the seed length. Specifically, sample a random polynomial of degree $<k$ over a field of size $2^{\max\{t,\lceil \log_2 n \rceil\}}$, and evaluate it at $n$ points. This produces $k$-wise independent field elements which can easily be turned into bits with the appropriate bias.

There is also a trivial $s \ge k \cdot t$ lower bound: Just look at the first $k$ bits of the output. These will all be $1$ with probability $2^{-k \cdot t}$. Generating an event with precisely this probability requires a seed of $k\cdot t$ bits.

To characterize the required seed length up to constants, all that remains is to prove a lower bound of $s\ge \Omega(k \log n)$ bits in the setting of $t \le o(\log n)$. Assume for simplicity that $k$ is even.

Let $X$ denote the distribution in question and let $x$ be an arbitrary point in its support. We have $\Pr[X=x]\ge 2^{-s}$ where $s$ is the seed length. Thus an upper bound on $\Pr[X=x]$ entails a lower bound on the seed length.

Define $Y = \sum_{i=1}^n \mathbb{I}[X_i \ne x_i]$. Then $X=x \iff Y=0$ and $\mu:=\mathbb{E}[Y] \ge n \cdot 2^{-t}$. Thus, by Markov's inequality and a Bernstein moment bound (e.g., Eq. 10 in SSS06 or this answer), $$2^{-s} \le \Pr[X=x] \le \Pr[|Y-\mu|\ge \mu] \le \frac{\mathbb{E}[(Y-\mu)^k]}{\mu^k} \le \frac{O(k\mu)^{k/2}}{\mu^k} = O\left(\frac{k}{\mu}\right)^{k/2} \le O\left(\frac{k}{n \cdot 2^{-t}}\right)^{k/2}.$$
This rearranges to $s \ge \frac12 k \cdot \left( \log_2 n - t -\log_2 k - O(1) \right)$. If $t=o(\log n)$ and $k=n^{o(1)}$, this is the desired lower bound.

In summary,

  $$k \cdot \max\{t,\lceil \log_2 n \rceil\} \ge s \ge k \cdot \max\left\{t, \frac12 \cdot \left( \log_2 n - \log_2 k - t - O(1) \right) \right\}.$$

The only room for improvement on this bound is in the constants (or the regime where replacing $n$ with $n/k$ makes a difference). However, if we only need a distribution that approximates the requirements, then I believe we can achieve better seed length (depending on the nature of the allowed approximation).


What is a really good problem to get your hands dirty in computational-geometry? Computational geometry is an area I find pretty interesting, and I'd like to devote about a month or two to a project that will introduce me to this and help me learn key concepts.

What is a good way to approach this and what are the key concepts I should be sure I'm introduced too?

To mix Suresh V.'s and Dave C.'s suggestions, it might be fun to try to gain experimental evidence
on an unsolved problem by implementing the necessary algorithms.  For example, it is now known that the Delaunay triangulation is not a ($\pi$/2)-spanner
[Prosenjit Bose, Luc Devroye, Maarten Löffler, Jack Snoeyink, Vishal Verma: "The spanning ratio of the Delaunay triangulation is greater than $\pi$/2." CCCG 2009: 165-167.]
You could implement a Delaunay triangulation algorithm, and shortest paths, and try to
determine experimentally what the true spanning ratio might be.
Or, more challenging, try to compute the combinatorial complexity of the Voronoi diagram of lines in $\mathbb{R}^3$,
another unsolved problem (and in the list that Suresh mentions as Problem 3.)


Complexity of deciding whether a matrix is totally regular A matrix is called totally regular if all its square submatrices have full rank. Such matrices were used to construct superconcentrators. What is the complexity of deciding whether a given matrix is totally regular over the rationals? Over finite fields?

More general, call a matrix totally $k$-regular if all its square submatrices of size at most $k$ have full rank. Given a matrix and a parameter $k$, what is the complexity of deciding whether the matrix is totally $k$-regular?

The paper Vandermonde Matrices, NP-Completeness, and Transversal Subspaces [ps] by Alexander Chistov, Hervé Fournier, Leonid Gurvits and Pascal Koiran may be relevant to your question (though it does not answer it).

They prove the $\mathsf{NP}$-completeness of the following problem: Given an $n\times m$ matrix over $\mathbb Z$ ($n\le m$), decide whether there exists a $n\times n$ submatrix whose determinant vanishes.


Separating lists of words There is an open problem in formal languages known as the Separating Problem; which is briefly stated as given two distinct strings of length $n$, how large of a DFA is required to "separate" them, meaning accept one string but reject the other.
Here are some relevant papers 1, 2. (I have a few more but I don't have enough reputation to post them).
These all discuss the problem of separating two distinct strings. I am wondering if there been any work done in the area of separating lists of strings, meaning given two lists of strings, $A$ and $B$, what size DFA is required to accept every string in $A$ and reject every string in $B$. This problem is equivalent to regex golf.
There are some basic questions that I have been working on such as if one of the lists is of size $1$ or if all the strings are of different lengths.
I have been searching around but haven't found any papers that deal with this type of problem. Has there been any research done in this area?
Thanks in advance.

The question you are asking is known as the separation problem for languages: Given two languages $K$ and $L$, is there a third language $M$ (a separator) that separates them, i.e. $K \subseteq M$ and $M \cap L = \emptyset$.

You are interested in the restricted case where $K$ and $L$ are finite, and in the size of a DFA for $M$.

In a 2013 paper, authors indicate:

  Although the separation problem frequently occurs, it has however not been systematically
  studied, even in the restricted, yet still challenging case of regular languages.

They however mention several special cases that have been solved, and that most certainly encompass the finite case.

You may also want to look at Craig interpolant, a similar problem on logical formulae.
Interpolation is used for instance in SAT-based model-checking, in a setting which I think is closer to what you are looking for (especially regarding finiteness of the input). This paper should be a good starting point.


Near-Sort quicksort algorithm faster than O(nlgn) Here, we define a nearly-sorted array with k-sized error, as this:
Elements in the array may be in the wrong order, but only if they are not distanced by more than k indices.
For example:

1, 2, 3, 6, 5, 4, 7, 8, 9

The 6 and the 4 are in the wrong order, and they are 2 indices apart from one another.
The rest of the elements are in order, or of less than 2 indices apart.
So the above array is nearly-sorted with an error size 2.

The question is, how to "tweak" the simple and basic version of the QuickSort algorithm, to have it produce a nearly-sorted array instead of a fully-sorted array, given a certain k, and thereby making it faster than O(nlgn)?

I've been thinking about this for days now, and I can't seem to understand how "ignoring" some of the elements while sorting, in any way, can ever change the run-time complexity of the algorithm, where k is constant?

I could easily just stop the recursion if size < k instead of size < 2, which would indeed make it faster by a tiny bit, and will indeed have possible errors, but wouldn't it still be O(nlgn)?

Any help or direction will be appreciated!

You can't do it. Suppose you start with an array where everything is sorted to distance $k$. Then, you can use a modified QuickSort to sort this array in time $n \log k$.

  First, choose pivot elements every $k$ elements. Now, sort the array so everything is in place with respect to these elements. (You can do this in time $O(n)$ using a modified version of Quicksort. First, put everything to the left of the first pivot element on the correct side of this pivot element. This takes $O(k)$ time. Next, put everything between the first and second pivot elements on the correct side of the second pivot element. Repeat for the rest of the pivot elements, from left to right.) Finally, sort each of the sublists between the pivot elements.

This will take total time $O(n \log k)$. Now, if you could take an arbitrary array to a nearly-sorted array in time less than $o(n\log n - n \log k)$, we would sort in time $o(n \log n)$. We can't do this.

Thus, there is an $\Omega(n \log \frac{n}{k})$ time bound on near-sorting.


Resources to learn about the P vs. NP problem I was recently reminded about the $\mathsf{P}$ vs. $\mathsf{NP}$ problem as explained by Stephen A. Cook on Clay Mathematics Institute.

It has piqued my interest and I would like to learn more about it. The first step would be gaining a deeper understanding of the problem and an understanding of the area in general.

Can you recommend any books or other resources where I can learn more about the problem?

It's good to see a fellow undergrad in pursue of this great problem, with such an enthusiasm. Allow me to offer you a piece of advice from my own experiences.

$ P \neq NP $ is a very interesting problem. The implications of the answer are immense, especially in the case that the two classes are equal. The reward is great in many levels, from the altruistic scientific one to the materialistic money award. That leads many young people that encounter the problem in trying to solve it, with no or limited knowledge about it.

Perhaps most theory students go through that phase. You will have an idea and think it is right, but it is almost certain that you are wrong. Some people never get through that phase and embarrass themselves by being too stubborn to admit their errors.

In FOCS 2010, Rahul Santhanam compared the $ P \neq NP $ question to a mythical monster. It would take many sacrifices and courage to even try to defeat this monster. After all, it may be the most difficult problem ever. To have a fighting chance, you will have to study a lot about this problem and complexity in general. You'll never know what the "monster's weakness" will be.

So my advice is this: Take your time in knowing the problem. Every time you figure out a solution, assume you are wrong somehow and try to find the problem with it. That way you'll learn much.

As for references, I would recommend Sipser's book as well. After finishing it, I would recommend "Computational Complexity:A modern approach" by Arora and Barak, a more complexity-oriented book, that requires a good understanding of the concept of computation.


Queueing Theory: How to estimate steady-state queue length for single queue, N servers? I have a real-life situation that can be solved using Queueing Theory.
This should be easy for someone in the field.  Any pointers would be appreciated.

Scenario:
There is a single Queue and N Servers.
When a server becomes free, the Task at the front of the queue gets serviced.
The mean service time is T seconds.
The mean inter-Task arrival time is K * T (where K > 1)
(assume Poisson or Gaussian distributions, whichever is easier to analyze.)

Question:
At steady state, what is the length of the queue?  (in terms of N, K).

Related Question:
What is the expected delay for a Task to be completed?

Here is the real-life situation I am trying to model:
I have an Apache web server with 25 worker processes.
At steady-state there are 125 requests in the queue.
I want to have a theoretical basis to help me optimize resources
and understand quantitatively how adding more worker processes
affects the queue length and delay.

I know the single queue, single server, Poisson distribution is well analyzed.
I don't know the more general solution for N servers.

thanks in advance,

You need to apply Little's law:

  The long-term average number of customers in a stable queue L is equal to the long-term average arrival rate, λ, multiplied by the long-term average time a customer spends in the queue, W; or expressed algebraically: L = λW.

The beauty of this law is that it does not depend on the distribution of arrivals or the service time (whether it is Markovian or not, etc.). More technically, and in Kendall's notation, it is true for the general GI/G/m queues.

We now assume that service time follows an exponential distribution (with parameter μ), and the arrivals follow a Poisson distribution (with parameter λ). In addition, we assume there's only one server. That is, our queue is modeled as M/M/1.

Using Little's Law, it can be shown (see formula (6.15) on page 247 of this book) that:

$W = \frac{\lambda/\mu^2}{1-\lambda/\mu}$

Note that the book uses different notations than here. It also states the formula holds for M/G/1-PS and M/G/1-LCFS queues.

Using Little's Law, we have $L = {\lambda^2 \over \mu^2-\lambda\mu}$.

In your case, λ = 1/(KT), and μ = 1/T. Hence L = 1/K(K-1).

PS: Little's Law has 3 variants. It can be applied to the whole system, to the queue itself, or to the service center. See pages 259-260 of this book for more info.

Edit: The case for M/M/c queues is much trickier. Here, you need to apply Erlang C formula.

To derive the following formulas, you can take a look at Section 5.2.3 of this book.

Let $a := \lambda/\mu$ and $\rho := a/c$, where c denote the number of servers. Then Erlang C formula, $C[c,a]$ is obtained by:

$C[c,a] = \frac{a^c}{c!} / ((1-\rho)\sum\limits_{n=0}^{c-1}\frac{a^n}{n!}+\frac{a^c}{c!})$

Now we have: $L = \rho C[c,a] / (1- \rho)$.

As a sanity check, note that for $c=1$ we derive the previous answer: $L = {\lambda^2 \over \mu^2-\lambda\mu}$.