Connections between the Erdos Discrepancy Problem and (Theoretical) CS? Recently there have been some new results on computer-based experimental study of the Erdos Discrepancy Problem (EDP) (via SAT solvers, cited below). This problem has been cited and studied by several (T)CS researchers. However the (possibly deep?) links to (T)CS are not so obvious.

  What are the link(s) of the EDP to (T)CS?

Here are some references that show interest of the (T)CS community in EDP:

SAT attack on EDP by Konev and Lisitsa, and reaction by Gowers; also, other connections to empirical/experimental TCS (e.g. SAT automated theorem proofs)
Intro to EDP and techniques on Lipton's blog
EDP and Differential Privacy on the Windows on Theory blog, by Talwar
EDP polymath project, with some contributions by computer scientists

There are many links between discrepancy theory and computer science, and Bernard Chazelle has beautifully surveyed some of them in his book. A number of links have been found more recently as well, for example Kunal's blog post talks about the connection to differential privacy from [MN] and [NTZ]. Another example is Larsen's idea of using discrepancy to prove update/query time lower bounds for dynamic data structures. Many of these links can be instantiated with homogeneous arithmetic progressions (HAPs). This would give:

upper bounds on the $\varepsilon$-samples for range spaces of HAPs
lower bounds on time required to update/query a dynamic data structure for HAP range counting
lower and upper bounds on the error required to privately answer HAP queries

However, there two things that you must realize with respect to these links. One is that it is not clear that range spaces of HAPs are very natural. When do you expect to have input that is a multiset of integers and want to answer how many elements of a HAP are in the input? I cannot think of a situation when this comes up, but maybe I am missing something.

Another thing that you must realize is that all these applications rely on the notion of hereditary discrepancy. This notion is more robust than discrepancy which makes it more tractable: there are stronger lower bounds available for it, it is approximable to within polylogarithmic factors, and it is approximately equal to the value of a convex optimization problem. The result Kunal talks about in the blog post (paper is here) and the construction by Alon and Kalai that Kalai wrote about in this blog post together essentially settle the hereditary discrepancy of HAPs. As Kunal explains, intuition for the lower bound on the hereditary discrepancy of HAPs came from the tight connection between hereditary discrepancy and differential privacy, together with prior results in differential privacy.

However EDP is about the discrepancy of HAPs. Discrepancy is much more brittle than hereditary discrepancy, and that makes it harder to lower bound. This also makes it less useful in applications than hereditary discrepapncy. And this is why EDP is still wide open while the hereditary discrepancy question is fairly well understood.

Let me finish with one approach to attack EDP that is inspired by computer science ideas. There is a way to relax discrepancy to a semidefinite program, see the survey by Bansal for details. The optimal value of the semidefinite program is lower bounded by the value of any feasible solution to its dual program. So one can attempt to prove EDP by exhibiting a family of dual solutions to this semidefinite relaxation of discrepancy, and showing that the value of the dual solutions goes to infinity. I see no reason why such an attack cannot work, in particular we do not know how to construct solutions to the semidefinite relaxation that have constant value for arbitrarily large instances. In fact a lot of the effort in polymath5 was centered around finding or ruling out dual solutions with particular structure.

The discrepancy of arbitrary arithmetic progressions is $\Theta(n^{1/4})$ in the worse case: the lower bound is known as Roth's 1/4 Theorem. Lovasz gives a proof of the theorem using semidefinite programming (although by arguing directly about the primal rather than by constructing dual solutions). For the proof, see Section 5.2. of his SDP survey.


Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems? Suppose P != NP.

We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there anything preventing the set of hard instances, from being arbitrarily small, so long as for any given instance size (n) there are only Poly(n) (or even constant) instances of size Poly(n) or smaller?

For any hard 3-SAT instance, we would have to add the set of all 3-SAT instances it reduces to via looping through the NP-Completeness reduction cycle, but I don't foresee this adding to the number of hard instances very much.

In this world, we could construct an algorithm that polynomially solves all NP complete problems, except an exceptional few.

Edit:
A softer variant of the question: even if we showed P!=NP, how could we know whether a given method to generate size n 3-SAT problems actually generated hard one with some requisite probability?  If there's no way to know from P!=NP alone, what is required to show that we can generate a hard NP-complete problem?

1) Depending on exactly what was meant, the conclusion in Kaveh's observation can be strengthened from $\mathsf{NP} \subseteq \mathsf{P/poly}$ to $\mathsf{P} = \mathsf{NP}$, essentially using Mahaney's Theorem. That is, if there is an algorithm which solves SAT and runs in time $\leq p(n)$ on all instances of length $n$ except for possibly $q(n)$ such instances, where $p$ and $q$ are both polynomials, then in fact $\mathsf{P} = \mathsf{NP}$. See, e.g. Meyer and Paterson and references therein, or Schoning's monograph "Complexity and Structure". So if this captures your notion of "hard instances" then there must be more than $poly(n)$ many hard instances for each $n$, assuming $\mathsf{P} \neq \mathsf{NP}$.

FYI, such algorithms are sometimes referred to as "apt" or "APT" algorithms, for "almost polynomial time" (not to be confused with the more modern complexity class $\mathsf{almostP}$, which happens to equal $\mathsf{BPP}$).

2) The above can be strengthened even further, as follows. Assume $\mathsf{P} \neq \mathsf{NP}$. Then the above says that for any algorithm solving SAT and any polynomial $p$, there is a set of instances of super-polynomial size on which the algorithm takes more than $p(n)$ time. But the set can depend on the algorithm.

The stronger result switches the quantifiers, and concludes: there is a super-polynomial size set H (for "hard") such that for any algorithm A solving SAT and any polynomial p, A takes more than $p(n)$ time on all but finitely many elements of H. Such an H is called a complexity core (the size assumption is not part of the definition of complexity core). The definition and existence of complexity cores was given by Lynch. The result I just quoted is proved by Orponen and Schoning.


Adding integers represented by their factorization is as hard as factoring? Reference request I'm looking for a reference for the following result:

  Adding two integers in the factored representation is as hard as factoring two integers in the usual binary representation.

(I'm pretty sure it's out there because this is something I had wondered at some point, and then was excited when I finally saw it in print.)

"Adding two integers in the factored representation" is the problem: given the prime factorizations of two numbers $x$ and $y$, output the prime factorization of $x+y$. Note that the naive algorithm for this problem uses factorization in the standard binary representation as a subroutine.

Update: Thanks Kaveh and Sadeq for the proofs. Obviously the more proofs the merrier, but I would also like to encourage more help in finding a reference, which as I said I'm fairly sure exists. I recall reading it in a paper with other interesting and not-often-discussed ideas in it, but I don't recall what those other ideas were or what the paper was about in general.

Assume that we can solve the problem (lets call it FactSum) in complexity class $C$ and $C$ is closed under $\log$-iteration (aka $\log$-bounded recursion)(e.g. if we can compute $x*y$ where $*$ is a binary function, we can computed $x_1*\ldots*x_{\log{n}}$) and contains $\mathsf{P}$ (this last condition can be made weaker). We show that factoring is in also in $C$.

Note that each number can be written as a sum of $\log n$ powers of $2$. Each of them are easy to factor.

Now given a number, write it as the sum of powers of it, then write each summand in the factoring representation, and then use the algorithm to sum them in the factoring representation. The result will be the factoring of the input number.

This shows that factoring is reducible to $\log$-iteration of your problem FactSum. Therefore factoring is in $\mathsf{P}^{\text{FactSum}}$ (and I think $\mathsf{P}$ can be replaced with  $\mathsf{NC^1}$ here).


Finding largest closest subsets Original question:

Base problem:
Let $A\subset \mathbb{N}$ be a finite set with elements $a_k$, ($k=1,...,L$). We compose subsets
$s_i$ ($i=1,...,N$) from $A$. Elements cannot be repeated within any sets, e.g. $|s_i \cap A| = |s_i|$, where
$|.|$ stands for set cardinality. The cardinalities of sets $s_i$ may differ. The problem is to find sets $s$
composed from $A$ so that

i) $|s_i \cap s| \ge p|s|$, for all $i=1,...,N$, where $p\in [0,1]$ is fixed.

ii) $|s|$ is maximal.

First variant:
Let $A\subset \mathbb{N}$ be a finite set with elements $a_k$, ($k=1,...,L$). We compose sets
$s_i$ ($i=1,...,N$) from $A$ so that $|s_i \cap A| = |s_i|$,
that is, an $s_i$ set contains different elements. We also compose sets
$c_j$ ($j=1,...,M$) from $A$ so that $|c_j \cap A| = |c_j|$,
that is, a subset $c_j$ contains different elements. The cardinalities of the sets $c_j$
may differ.
The problem is to find sets $s$ composed from $A$ so that

i) $|\{i : |s_i \cap s| \ge p|s|\}| \ge qN$, where $p,q\in [0,1]$ is fixed.

ii) $|\{j : |c_j \cap s| \ge p|s|\}| \le q'M$, where $p,q'\in [0,1]$ is fixed.

iii) $|s|$ is maximal.

Interpretation for better understanding:
The $a_k$ elements are different mutations that we can represent e.g. with different
natural numbers. We have samples for two populations,
$\{s_i\}$ are the diseased persons, $\{c_j\}$ are the average ones, and we know
that $q'*100\%$ is the presence of the disease on average. We want to find characteristic mutation patterns (sets $s$)
that are characteristic for the diseased (at least $q*100\%$) but less characteristic (only up to $q'*100\%$) for the average population.
We say that $s$ is characteristic if at least its $p*100\%$ portion appears in a diseased person.

We would need known theoretical results, complexity of the algorithm and algorithmic approaches for the search.

Question 2 (new constraint added):

Jukka Suomela has given a correct answer for the Base problem in the Original question. Regarding his answer and also since from practical point of view it is reasonable, an extra constraint can be added to the problem as:

In Base problem:

iii) $|s| < |s_i|$, for all $i=1,...,N$.

In First variant:

iv) $|s| < r|s_i|$, for all $i=1,...,N$, where $r\in [0,1]$ is fixed.

The questions regarding the problems remain the same.

Interpretation for better understanding of this new size constraint:
We can estimate the number of mutations for a person to be approx. 1 million (that is, $|s_i|,|c_i| \approx 10^6$), while disease-sepcific mutation patterns are expected to be much smaller (say $|s|\approx 50$, but we do not know). This is the reason for the size constraints for $s$ in the problem.

Let us consider your "base problem" and the special case of $p = 1/2$.

Assume that we are given a graph $G = (V,E)$ and a positive integer $k \le |V|$.

Construct an instance of your problem as follows:

Our "alphabet" is $A = V \cup \{ 0,1,\dotsc,k-1 \}$.
The sets $s_i$ are indexed with $i \in I = E \cup \{ \bot \}$.
For each $e = \{u,v\} \in E$ we have $s_e = \{ 1,2,\dotsc,k-1, u, v\}$.
We also define $s_\bot = \{ 0,1,\dotsc,k-1 \}$.

Observations:

There is a trivial solution $s$ of size $2k-2$: just take a subset $s \subseteq A$ with $\{1,2,\dotsc,k-1\} \in s$ and $|s| = 2k-2$. Clearly $|s \cap s_i| \ge k-1$ for all $i$.
There cannot be a solution of size $2k+1$ or larger: it would imply $|s \cap s_\bot| > k = |s_\bot|$, a contradiction.
If there is a solution $s$ of size $2k-1$, we can pad it with an arbitrary element to obtain a solution of size $2k$.

Hence the key question is whether there exists a solution $s$ of size $2k$.

Assume that we have a solution $s$ of size $2k$. Then $s_\bot = \{0,1,\dotsc,k-1\} \subseteq s$. Hence $s = \{0,1,\dotsc,k-1\} \cup X$, where $X \subseteq V$ and $|X| = k$. Moreover, if $e = \{u,v\} \in E$, we must have $|s \cap s_e| \ge k$, which implies $e \cap X \ne \emptyset$. That is, $X$ is a vertex cover of size $k$.
Conversely, if we have a vertex cover of size $k$, we can construct a solution of size $2k$.

Hence it is NP-hard to find an optimal $s$. The same idea can be used to show that the problem is hard for any $0 < p < 1$.

Edit: Now a natural question is whether there is an approximation algorithm – for example, can one always find a feasible solution $s$ that is within a constant factor of the largest feasible solution.

However, this does not seem to be the case. It seems that it is actually NP-hard to find any non-trivial solution (i.e., a solution $s \ne \emptyset$), at least for certain values of $p$. The construction is a bit messy, though, but I can try to work out the details if needed.

Anyhow, it seems that to get anything positive (with provable performance guarantees), you need to relax your constraints a bit.


What is a multicast graph? Martin Fowler in his blog post on "The LMAX Architecture" tried to describe the component called Disruptor as a multicast graph of queues

  At a crude level you can think of a Disruptor as a multicast graph of
  queues where producers put objects on it that are sent all the
  consumers for parallel consumption through separate downstream
  queues...

I'm having difficulties understanding the nature of a multicast graph

Here is a technical paper on the LMAX Architecture (I just followed a link found on the blog you linked here): http://disruptor.googlecode.com/files/Disruptor-1.0.pdf

An example of a multicast graph is on page 9 of the PDF. There are also examples of multicast graphs (compared to various other options) here: http://en.wikipedia.org/wiki/Multicast


Computational complexity of quantum optics In "Requirement for quantum computation", Bartlett and Sanders summarize some of the known results for continuous variable quantum computation in the following table:

MY question is three-fold:

Nine years later, can the last cell be filled in?
If a column is added with the title "Universal for BQP", how would the rest of the column look?
Can Aaronson and Arkhipov's 95 page masterpiece be summarized into a new row?

With respect to your third question, Aaronson and Arkhipov (A&A for brevity) use a construction of linear optical quantum computing very closely related to the KLM construction. In particular, they consider the case of $n$ identical non-interacting photons in a space of $\text{poly}(n) \ge m \ge n$ modes, starting in the initial state
$$
\left|1_n\right>=\left|1,\dots,1,\ 0,\dots,0\right>\quad (n\text{ 1s}).
$$
In addition, A&A allow beamsplitters and phaseshifters, which are enough to generate all $m\times m$ unitary operators on the space of modes (importantly, though, not on the full state space of the system). Measurement is performed by counting the number of photons in each mode, producing a tuple $(s_1, s_2, \dots, s_m)$ of occupation numbers such that $\sum_i s_i = n$ and $s_i \ge 0$ for each $i$. (Most of these definitions can be found in pages 18-20 of A&A.)

Thus, in the language of the table, the A&A BosonSampling model would likely best be described as "$n$ photons, linear optics and photon counting." While the classical efficiency of sampling from this model is, strictly speaking, unknown, the ability to classically sample from the A&A model would imply a collapse of the polynomial hierarchy. Since any collapse of PH is generally considered extremely unlikely, it's not at all a stretch to say that BosonSampling is very probably not efficiently and classically simulatable.

As for BQP-universality of the A&A model, while linear optics of non-interacting bosons alone is not known to be universal for BQP, the addition of post-selected measurement is enough to obtain full BQP universality, via the celebrated KLM theorem. The acceptance probability of the postselection in the KLM construction scales as $1/16^\Gamma$, where $\Gamma$ is the number of controlled-Z gates that appear in a given circuit. Whether that is enough to conclude that the postselected linear optics model of BQP is efficient or not is thus a matter of what one defines to be efficient, but it is universal.

Aaronson explores the postselected linear optics case more in his followup paper on the #P-hardness of the permanent. This result was earlier proved by Valiant, but Aaronson presents a novel proof based on the KLM theorem. As a side note, I find that this paper makes a very nice introduction to many of the concepts that A&A use in their BosonSampling masterpiece.


What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors? I am trying to find a distribution over $n$ random vectors, say $x_1,\ldots, x_n$, on the $k$-dimensional unit sphere (where $n > k$) that minimizes $\max_{i\neq j} \mathrm{Var}(x_i^T x_j)$ subject to the constraint $\mathbb{E}[x_i^Tx_j]=0$.

I tried some distributions and almost all them have variance $1/k$. For example, both the distribution in which each coordinate of each $x_i$ is independently and uniformly chosen from $\left\{-1/\sqrt{k}, 1/\sqrt{k}\right\}$ and the distribution in which each $x_i$ is an independent uniform vector on the $k$-dimensional unit sphere have variance $1/k$.

Is $1/k$ the minimum variance among all distributions?

I will present an equivalent but simpler-looking formulation of the problem, and show a lower bound of (n/k − 1) / (n−1).  I also show a connection to an open problem in quantum information.  [Edit in revision 3: In earlier revisions, I claimed that an exact characterization of the cases in which the lower bound shown below is attained is likely to be difficult because an analogous question in the complex case includes an open problem about SIC-POVMs in quantum information.  However, this connection to SIC-POVMs was incorrect.  For details, see the section “Incorrect connection to SIC-POVMs in quantum information” below.]

Equivalent formulation

First, as was already pointed out in daniello’s answer, note that Var(xiTxj) = E[(xiTxj)2] − E[xiTxj]2 = E[(xiTxj)2].  So in the rest of the answer, we forget about variance and instead minimize maxi≠jE[(xiTxj)2].

Next, once we decide our goal is to minimize maxi≠jE[(xiTxj)2], we can ignore the constraint that E[xiTxj] = 0.  This is because if we have random unit vectors x1, …, xn, then we can negate each of them independently with probability 1/2 to satisfy E[xiTxj] = 0 without changing the value of the objective function maxi≠jE[(xiTxj)2].

Moreover, changing the objective function from maxi≠jE[(xiTxj)2] to (1/(n(n−1)))∑i≠jE[(xiTxj)2] does not change the optimum value.  The latter is at most the former because the average is at most the maximum.  However, we can always make the values of E[(xiTxj)2] for different choices of (i, j) (i≠j) equal by permuting the n vectors x1, …, xn randomly.

So for any n and k, the optimum value of the problem in question is equal to the minimum of (1/(n(n−1)))∑i≠jE[(xiTxj)2] where x1, …, xn are random variables which take unit vectors in ℝk as values.

However, by linearity of expectation, this objective function is equal to the expected value E[(1/(n(n−1)))∑i≠j(xiTxj)2].  Because the minimum is at most the average, there is no need to consider probability distributions anymore.  That is, the optimum value of the problem above is equal to the optimum value of the following:

  Choose unit vectors x1, …, xn ∈ ℝk to minimize (1/(n(n−1)))∑i≠j(xiTxj)2.

Lower bound

Using this equivalent formulation, we will prove that the optimal value is at least (n/k − 1) / (n−1).

For 1≤i≤n, let Xi=xixiT be the rank-1 projector corresponding to the unit vector xi.  Then, it holds that (xiTxj)2 = Tr(XiXj).

Let Y = ∑iXi.  Then, it holds that ∑i≠jTr(XiXj) = ∑i,jTr(XiXj) − n = Tr(Y2) − n.

The Cauchy–Schwarz inequality implies that Tr(Y2) ≥ (Tr Y)2/k = n2/k, and therefore ∑i≠jTr(XiXj) = Tr(Y2) − n ≥ n2/k − n.  By dividing by n(n−1), we obtain that the objective value is at least (n/k − 1) / (n−1).

In particular, when n=k+1, daniello’s answer is within a factor of 2 from the optimal value.

When is this lower bound attainable?

Attaining this lower bound (n/k − 1) / (n−1) is equivalent to making Y=(n/k)I.  I do not know the exact characterization when it is attainable, but following sufficient conditions exist:

When n=k+1, it is attainable by considering k+1 unit vectors which form a regular k-simplex centered at the origin, improving from 2/(k(k+1)) in daniello’s answer to the optimal 1/k2.
When n is a multiple of k, it is clearly attainable by fixing an orthonormal basis of ℝk and assigning each of the basis vectors to n/k of v1, …, vn.
More generally than the last bullet point, if it is attainable with some choice of k and both n=n1 and n=n2, then it is also attainable for the same k and n=n1+n2.  In particular, it is attainable if n=ak+b where a and b are integers satisfying a≥b≥0.

Although I have not checked details, it seems that any spherical 2-design gives a solution attaining this lower bound.

Incorrect connection to SIC-POVMs in quantum information

In earlier revisions, I stated:

  I suspect that answering this completely is a difficult question.  The reason is that if we instead consider the complex vector space ℂk, this question is related to an open problem in quantum information.

But this relation was incorrect.  I will explain why.

  More precisely, consider the following problem:

    Choose unit vectors x1, …, xn ∈ ℂk to minimize (1/(n(n−1)))∑i≠j|xi*xj|2.

  The lower bound above equally holds in this complex version.   Consider the case where n=k2 in the complex version.  Then the lower bound is equal to 1/(k+1).

So far, it was correct.

  A set of k2 unit vectors x1, …, xk2 ∈ ℂk attaining the lower bound is called a SIC-POVM in dimension k,

This part was incorrect.  A SIC-POVM is a set of k2 unit vectors x1, …, xn ∈ ℂk for which |xi*xj|2 = 1/(k+1) for all i≠j.  Note that here the requirement must hold for all pairs i≠j, not just the average over all pairs i≠j.  In the “Equivalent formulation” section, we showed the equivalence between minimizing the maximum and minimizing the average, but this was possible because x1, …, xn were random variables taking unit vectors there.  Here x1, …, xn are just unit vectors, so we cannot use the same trick.


How to solve this generalization of binary search? Let $f:\{1,\ldots,n\}$ be a monotonically non-decreasing function.

Consider, for some unknown threshold $1\le T\le n$, a threshold function
$$g(x)= \begin{cases}
0&\text{x<T}\\
1&\text{otherwise}.
\end{cases}$$

Our goal is to find $T$ while minimizing the worst case cost, where computing $g(x)$ for any $x\in\{1,\ldots n\}$ has a cost of $f(x)$.
We assume that $f$ is known.

There are two straightforward approaches for this: a linear scan and a binary search.

It's not hard to see that each of them is good for different scenarios -- a linear scan works fine for $f(x)=2^{x}$ while a binary search is optimal for $f(x)=1$.

Since $f(n/2)$ may be much larger than $f(T)$, another approach is to use doubling and then binary search. The cost of this is bounded by $O(f(2T)\log T)$. This can be modified to
$$O(\epsilon^{-1} f(T)\log T +  f(T(1+\epsilon))\log (T\epsilon))$$
by doing the doubling using a $(1+\epsilon)$ factor.

  If this problem is known, What is the name of this problem?

  What is the optimal strategy here?

Obviously, it is possible to exhaustively compute the correct strategy. Can we compute it (or an approximation of it) faster? Is it possible to give an analytical formula for it?

I am aware that the problem is somewhat vague. Mainly, I am wondering if it is possible to analytically find an optimal solution (using the $f(i)$ values) and if not, if it is possible to compute a reasonable strategy given $f$ as an input.
You may also assume additional reasonable properties on $f$.

The optimal strategy can be found through dynamic programming in $O(n^3)$ time.  Let $A[i,j]$ denote the worst-case cost of the optimal strategy when $T$ is already known to be in $\{i,i+1,\dots,j\}$.  Then we have the recursive relation

$$A[i,k] = \min \{f(j) + \max(A[i,j], A[j+1,k]) : j=i,i+1,\dots,k-1\},$$

with the base case $A[i,i] = 0$.  You can use dynamic programming to fill out this array.  The assumption that $f$ is non-decreasing is not needed; this works whenever $f$ is any non-negative function.


Expressing Determinant as Permanent One major problem in TCS is the problem of expressing a permanent as a determinant. I was reading Agrawal's paper Determinant Versus Permanent and in one paragraph he claims the reverse problem is easy.

  It is easy to see that the determinant of a matrix $X$ can be expressed as the permanent of a related matrix $Xˆ$ whose entries are 0, 1, or $x_{i,j}$ s and which is of size $O(n)$ (set up entries of Xˆ such that det $Xˆ$ = det $X$ and the product corresponding to every permutation that has an even cycle is zero).

First of all, I don't think 0, 1, and $x_{i,j}$ variables are enough because we would be missing negative terms. But even if we allowed -1 and $-x_{i,j}$ variables as well, I don't see why the growth in size can be made linear. Could someone please explain the construction to me?

I think this may have been a typo in Agrawal's paper. The best I know is how to write an $n \times n$ determinant as a projection of an $O(n^3)$-sized permanent, by writing the determinant as an algebraic branching program (and I think this is currently the best known). See the comments on this answer.


Resources on Jablon's Protocol Are there any good resources (descriptions, explanations, examples) regarding Jablon's protocol for password authentication using multiple servers, aside from this paper?

I found the book Protocols for Authentication and Key Establishment very promising on the subject of authentication protocols. Specifically, it references two protocols by Jablon (see references 165 and 166 of the book).

You may also find more info in papers that cite Jablon's Protocol.


Hidden path in square grids I stumbled on an open problem posed by David Eppstein and I am interested in its complexity status. He conjectured that it is NP-complete.

Input: $n$ by $n$ matrix of 0’s and 1’s, sequence of $n^2$ 0’s and 1’s

Question:  Is there a path through adjacent matrix entries, covering each matrix entry exactly once, with values matching the given sequence?

  Did anyone prove that the problem is indeed hard?

I received an email last February from a Spanish undergraduate, Nil Mamano, with a proof that this problem is indeed NP-complete, by reduction from Hamiltonian path in grid graphs. I don't know that it has been published anywhere yet. The reduction replaces each vertex of the grid graph by a 2x2 block of 1's, and each edge, face, or missing vertex by a 2x2 block of 0's. The input sequence alternates between subsequences of four 1's and four 0's for as many times as is needed to cover all the vertices, then fills out the rest of the sequence with 0's. To match the input sequence, a path through the grid must align the subsequences of four 1's with the 2x2 blocks of 1's from the reduction, forming a Hamiltonian path; if such a path exists, it's always possible to do this in a way that allows the rest of the matrix to be covered by the remaining zeros at the end of the sequence.


Minimum number of real multiplications to multiply two quaternions Karatsuba multiplication of two complex numbers can be performed with just three real multiplications (instead of four) as follows:
$$(a+bi)(c+di) = (ac-bd) + i ((a+b)(c+d) - ac-bd)$$
We only need the products $ac$, $bd$ and $(a+b)(c+d)$. Does there exists a similar trick for quaternion multiplication? A naive multiplication would need $16$. This can probably be reduce to $9$ using the same trick as above (and taking into account that quaternion multiplication is non-commutative). My question is it known that $9$ is the lower bound? If not, does there exist an algorithm, which does quaternion multiplications in less than $9$ real multiplications?

de Groote showed that one could compute both $uv$ and $vu$ using only a total of 10 non-scalar multiplications.

Howell and Lafon, in a tech report (that I could not find a refereed version of and have not checked myself, but is probably correct) showed that one can do quaternion product with only 8 multiplications.

7 is certainly a lower bound, as noted in both of the above papers.

(While this was an interesting question and fun to look up, I found the answer in about 5 minutes of Googling. Google is your friend.)


Simple proof that splay trees have the dynamic finger property? Splay trees are conjectured to be dynamically optimal, and they're known to have a number of nice properties, including the dynamic finger property, which says that the amortized cost of an access in a splay tree is logarithmic in the magnitude of the rank difference between the queried key and the most-recently-queried key.

It seems like the first proof that splay trees have the dynamic finger property comes from a two-paper series by Cole et al ("On the Dynamic Finger Conjecture for Splay Trees I: Splay Sorting $\log n$-Block Sequences" and "On the Dynamic Finger Conjecture for Splay Trees II: The Proof.") These papers collectively are over eighty pages long and involve fairly complicated, technical proofs. They also seem to be the papers cited by future work in splay trees and related structures when referring to the dynamic finger property.

Has there been any follow-up work in this area that provides a simpler proof of the dynamic finger conjecture?

There has been a lot of further work more broadly on Splay trees and related data structures after the two papers that you mention, for example the 2019 paper of Levy and Tarjan [1].

However, there have been no alternative proofs or simplifications of the dynamic finger result of Cole et al. that you mention. (Any such attempt would be quite interesting to those working on these problems.)

There is, however, a 2016 paper by Iacono and Langerman [2] that proves a generalization of the dynamic finger property for a different data structure called Greedy BST, that matches many (all) known properties of Splay. The proof techniques here are easier and quite different from those in the Splay dynamic finger paper.

[1] https://doi.org/10.1137/1.9781611975482.80

[2] https://arxiv.org/abs/1810.01785


Using a probability distribution in the fooling set technique for communication complexity I'm reading through the communication complexity book of Kushilevitz and Nisan, and in the section about fooling sets I encountered this proposition:

  Let $\mu$ be a probability distribution of $X\times Y$. If any $f$-monochromatic rectange $R$ has measure $\mu(R) \leq \delta$, then $D(f) \geq \log_2 1/\delta$. [Prop. 1.24]

I understand the idea of a fooling set (find a set which takes the same function value everywhere, but mixing and matching $x$ and $y$ coordinates will change the function value). I understand that $\mu$ maps $X\times Y$ to $\mathbb{R}$, and that $\mu(X\times Y) = 1$. But I don't understand why we should be allowed to use a probability distribution at all. There's no randomness here, and even if their likelihoods of being chosen were not uniform, each pair $(x,y)$ should in theory be possible, and we need to take this into consideration because communication complexity deals with the worst-case.

I'm obviously missing something. Any help here would be appreciated.

(Also, the use of any in the proposition is ambiguous. I assume that it means "for all", but it could also possibly mean "there exists"...)

It is true that there is "no randomness" in the sense that the protocol is not randomized and is supposed to work on all inputs. However, that does not mean that we are not allowed to use probability distributions in the analysis of the algorithm.

This theorem says that when you wish to prove a lower bound, then for the purpose of the analysis, you can take whatever distribution $\mu$ you like, and the communication complexity would be at least $\log(1/\delta)$, where $\delta$ is the largest probability of a monochromatic rectangle.

If you do not like thinking about it in terms of probability, you can also think about it as a counting argument. Suppose you could prove that every monochromatic rectangle contains at most $t$ pairs. Then, this would imply that the communication complexity must be at least $\log\left(\frac{|X \times Y|}{t}\right)$ by simple counting.

Now, the foregoing argument is exactly equivalent to applying the theorem you stated with $\mu$ being the uniform distribution and $\delta$ being $\frac{t}{|X \times Y|}$. The theorem generalizes this argument to work with probability distributions other than the uniform.

In the case the distribution is not uniform, this is equivalent to augmenting the counting argument with weights. Suppose you assign each pair some weight such that

The total weight of $X \times Y$ is $W$.
Every monochromatic rectangle has weight at most $w$.

Then, clearly the communication complexity must be at least $\log(W/w)$ (since there must be at least $W/w$ monochromatic rectangles). The theorem you stated is just a different way to look at this argument.


How to determine if a labelled digraph contains a cycle with given labels? Suppose $G = (V, E)$ is a digraph of bounded degree. Suppose each edge in $E$ is labelled with a number from the set $X = \{1, ..., n\}$ and for each vertex $v \in V$ and each $x \in X$ there is at most 1 edge labelled $x$ connecting out of $v$, i.e. there is at most one edge labelled $x$ with tail $v$.

Let $w$ be a word made using elements of $X$ as letters. For a given vertex $v$, $w$ defines a path through G by following the correctly labelled edges (if they exist) starting at $v$. I would like to determine if a $w$ forms a cycle anywhere within G.

  Is there a more efficient way to determine if there is a $v \in V$ such that $w$ forms a cycle when started at $v$ than checking where the path $w$ terminates for every starting vertex?

The following suggestion may speed up your solution if you need to answer queries for many different words.

Define the set $U_i^w$ to be a set of pairs $(v, A)$ where $A \subseteq V$ and $v$ is reached by some vertex in $A$ after traversing the first $i$ labels of the word $w$.  Then to check if $w$ forms a cycle in the graph, loop through all $(v, A) \in U_{|w|}^w$ and if ever $v \in A$, then a cycle does exist.

Note that if the first $i$ elements of $w$ and $w'$ are the same, then $U_i^w = U_i^{w'}$.  Also, $U_0^w = \{(v, \{v \} ) | v \in V \} $.

As you process queries, dynamically construct a trie such that each node (including the inner nodes) stores $U_i^w$ for some $i$ and $w$.  This way, if $w$ and $w'$ have the same first $k$ elements and $w$ is processed before $w'$, then $U_k^{w'}$ can be quickly retrieved by traversing the first $k$ nodes of the trie.


How to determine whether a proof requires "higher-order reasoning techniques"? The question:

Suppose I have a specification of a problem consisting of axioms and a goal (i.e. the associated proof problem is whether the goal is satisfiable given all the axioms). Let us also assume that the problem does not contain any inconsistencies/contradictions among the axioms.
Is there a way to determine in advance (i.e. without first constructing a full proof) that proving the problem will require "higher-order reasoning"?

By "higher-order reasoning", I mean applying proof steps which require higher-order logic to be written down. A typical example for "higher-order reasoning" would be induction: Writing down an induction scheme in principle requires using higher-order logic.

Example:

One can specify the proof problem "Is addition on two natural numbers commutative?" using first-order logic (i.e. define natural number via constructors zero/succ along with standard axioms, together with axioms that recursively define a "plus" function). Proving this problem requires induction on the structure of either the first or the second argument of "plus" (depending on the exact definition of "plus"). Could I have known this before attempting to prove it, e.g. by analyzing the nature of the input problem...? (Of course, this is just a simple example for illustration purposes - in reality, this would be interesting for more difficult proof problems than commutativity of plus.)

Some more context:

In my research, I frequently try to apply automated first-order theorem provers like Vampire, eprover etc. to solve proof problems (or parts of proof problems), some of which may require higher-order reasoning. Often, provers require quite some time to come up with a proof (provided there is a proof which only requires first-order reasoning techniques). Of course, trying to apply a first-order theorem prover to a problem that requires higher-order reasoning typically results in a timeout.

Therefore, I have been wondering whether there are any methods/techniques which can tell me in advance whether a proof problem will require higher-order reasoning techniques (meaning "don't waste time trying to hand it to a first-order theorem prover") or not, at least maybe for particular input problems.

I looked in the literature for an answer to my question and asked some fellow researchers from the area of theorem proving about that - but so far, I didn't receive any good answers. My expectation would be that there is some research on that topic from people who try to combine interactive theorem proving and automated theorem proving (Coq community? Isabelle community (Sledgehammer)?) - but so far, I could not find anything.

I guess that in general, the problem I outlined here is undecidable (is it?). But maybe there are good answers for refined versions of the problem...?

Briefly, every theorem stated in first-order logic has a first-order proof.

In his book "An Introduction to Mathematical Logic and Type Theory", Peter B. Andrews develops both first-order logic and a system of higher-order logic Q0, which is generally considered to be the theory basis of modern higher-order provers. (See the introduction to the HOL logic for example.)

For Q0 and similar systems, Andrews shows that the higher-order logics he describes can be considered as conservative extensions of first-order logic and writes (second edition, p. 259) that, "In summary, every first-order theorem of type theory has a first-order proof."

Given your practical concerns though, I also quote the following paragraph:

"However, some theorems of first-order logic can be proved most efficiently by using concepts which can be expressed only in higher-order logic. Examples may be found in [Andrews and Bishop, 1996] and [Boolos, 1998, Chapter 25]. Statman proved [Statman, 1978, Proposition 6.3.5] that the minimal length of a proof in first-order logic of a wff of first-order logic may be extraordinarily longer than that the minimal length of a proof of the same wff in second-order logic. A related result by Godel [Godel, 1936] is that in general 'passing to the logic of the next higher order has the effect, not only of making provable certain propositions that were not provable before, but also of making it possible to shorten, by an extraordinary amount, infinitely many of the proofs already available'. A complete proof of this may be found in [Buss, 1994]."


$\mathsf{FP}^{\mathsf{NP}[\log n]}$ versus $\mathsf{FP}^{\mathsf{NP}||}$ I know that $\mathsf{P}^{\mathsf{NP}[\log n]}$ (logarithmically many calls to the NP oracle) is equivalent to $\mathsf{P}^{\mathsf{NP}||}$ (polynomial number of parallel queries to the NP oracle). I was wondering wether the "function" version of these classes are also equivalent, that is, whether

$$ \mathsf{FP}^{\mathsf{NP}[\log n]} = \mathsf{FP}^{\mathsf{NP}||}$$
If it is known to be true, a pointer would be really helpful.

This is an open problem, it implies $\mathsf{NP} = \mathsf{RP}$ among other things.
See the following paper:

Alan Selman. A Taxonomy of Complexity Classes of Functions. Journal of Computer and Systems Sciences 48 (1992), pp. 357-381.

You can get it here:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.7438&rep=rep1&type=pdf


Is there a way to detect search engine bias? Search engines are increasingly being relied on as information gatekeepers, yet the criteria used by search engines to rank results is opaque to users. How can users be sure their results aren't biased or tampered with in some way to benefit some interest at the expense of search result quality?

Governments routinely demand that search providers remove or lower the ranking of websites deemed politically undesirable. Businesses may pay providers to boost certain results over others to increase their revenues. Firewalls may meddle with results before they're transmitted back to users.

Even seemingly innocuous changes to ranking algorithms that might not on the surface appear to be biased, could actually be deviously designed to harm websites that share some common attribute (unrelated to actual quality).

Is it possible to detect search engine bias, by say monitoring results over a period of time and evaluating whether some "hidden variable" (perhaps a political affiliation) is a driving factor in the change in website rankings?

A sneaky provider may gradually over time lower the ranking of targeted websites (and perhaps random websites as well to distract users). What are the limits on how much bias a provider can introduce without detection? Or is it possible to always conceal such interference by deviously selecting weighted ranking criteria that incidentally produce the intended result (by way of "data snooping").

Does any of this change if the ranking criteria is made public? Do we need to open-source the criteria search engines use?

This reminds me of the result that detecting whether or not a complex financial instrument such as a CDO has been tampered with by the seller is equivalent to solving the densest-subgraph problem:

http://www.cs.princeton.edu/~rongge/derivative.pdf

Thanks!

This is obviously a very open ended question, but so as to stay on topic, here is one CS theory approach to the idea of "fairness" and how to enforce it.

"Fairness Through Awareness" Dwork, Hardt, Pitassi, Reingold, Zemel
http://arxiv.org/abs/1104.3913


Type a variable-argument function? Is it possible to type a variable-argument function?

EDIT: like those defined in Scheme.

Such functions can be typed in dependently typed programming languages (among others).

This is an example in Agda, a dependently typed language that looks similar to Haskell:

more : Nat -> Set
more 0 = Nat
more (S x) = Nat -> more x

sum : \forall {x : Nat} -> Nat -> more x
sum {0}   a = a
sum {S x} a = \lambda m -> sum {x} (m + a)

The function sum takes x natural numbers as arguments and returns with the sum of all arguments. The S in the pattern matches is the "successor" constructor on the natural numbers.

Note: Agda has a much nicer Unicode syntax, but most browsers can't display it correctly.


A data structure for minimum dot product queries Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of the following format: given $x \in \mathbb{R}^n$ output $\min_i \langle x, v_i \rangle$. Is it possible to go beyond the trivial $O(nm)$ query time? For example if $n = 2$, then it is immediate to get $O(\log^2 m)$.

The only thing I can come up with is the following. It is an immediate consequence of Johnson-Lindenstrauss lemma that for every $\varepsilon > 0$ and a distribution $\mathcal{D}$ on $\mathbb{R}^n$ there is a linear mapping $f \colon \mathbb{R}^n \to \mathbb{R}^{O(\log m)}$ (which can be evaluated in $O(n \log m)$ time) such that $\mathrm{Pr}_{x \sim \mathcal{D}}\left[\forall i \quad \langle x, v_i \rangle - \varepsilon (\|x\| + \|v_i\|)^2 \leq \langle f(x), f(v_i)\rangle \leq \langle x, v_i \rangle + \varepsilon (\|x\| + \|v_i\|)^2 \right] \geq 1 - \varepsilon$. So, in time $O((n + m) \log m)$ we can compute something that is in some sense close to $\min_i \langle x, v_i \rangle$ for most $x$'s (at least if the norms $\|x\|$ and $\|v_i\|$ are small).

UPD The abovementioned bound can be somewhat sharpened to the query time $O(n + m)$ if we use locality-sensitive hashing. More precisely, we choose $k := O(\frac{1}{\varepsilon^2})$ independent Gaussian vectors $r_1, r_2, \ldots, r_k$. Then we map $\mathbb{R}^n$ to $\{0,1\}^k$ as follows: $v \mapsto (\langle r_1, v \rangle \geq 0, \langle r_2, v \rangle \geq 0, \ldots, \langle r_k, v \rangle \geq 0)$. Then we can estimate the angle between two vectors within an additive error $\varepsilon$ by computing $\ell_1$-distance in the image of this mapping. Thus, we can estimate dot products within an additive error $\varepsilon \|x\| \|v_i\|$ in $O(\frac{1}{\varepsilon^2})$ time.

Consider the special case where you just want to determine if your query vector is orthogonal to some vector in your preprocessed collection. (That is, you want to determine if $\min_i \langle x, v_i \rangle = 0$, where the vectors under discussion have non-negative coefficients.) This case is already very interesting.

Suppose you can answer queries in $n^{O(1)} m^{1-\delta}$ time for some $\delta > 0$, with $m^{O(1)} n^{O(1)}$ preprocessing (the polynomial's degrees should not depend on $m$ or $n$ or $\delta$).

In the paper "A new algorithm for optimal 2-constraint satisfaction and its implications", I observed that such a data structure would actually allow you to solve CNF-SAT in $2^{\alpha v}$ time for some $\alpha < 1$, where $v$ is the number of variables. This would refute the "Strong Exponential Time Hypothesis" that k-SAT requires essentially $2^n$ time for unbounded $k$.

To see why, suppose the preprocessing time is bounded by $(nm)^c$. Consider a CNF formula $F$ with $v$ variables and $n$ clauses. We split the set of variables into two parts $P_1$ and $P_2$ of size $v(1-1/(2c))$ and $v/(2c)$, respectively. List all possible assignments to the variables in the parts (getting $2^{v(1-1/(2c))}$ and $2^{v/(2c)}$ assignments, respectively). Associate each of these partial assignments $A_i$ with an $n$-bit vector $w_i$ where $w_i[j]=1$ iff the $j$th clause of $F$ is not satisfied by $A_i$. So we have two lists of exponentially many bit vectors.

Notice that $F$ is satisfiable iff there is a vector $w_1$ from an assignment on $P_1$ and a vector $w_2$ from an assignment on $P_2$ such that $\langle w_1, w_2 \rangle = 0$.

Now let $m=2^{v/(2c)}$, and preprocess the assumed data structure with all vectors from part $P_2$. This takes $n2^{v/2}$ time, by assumption. Run the query algorithm on all vectors from assignments on part $P_1$. By assumption this takes $2^{v(1-1/(2c))} \cdot n^{O(1)} m^{1-\delta} = n^{O(1)} 2^{v - \delta v/(2c)}$. Let $\alpha = 1 - \delta/(2c)$.

Perhaps it is possible to get efficient preprocessing and $n^{O(1)} m^{1-1/(\log \log m)}$ query time with existing techniques. The best known CNF-SAT algorithms don't rule it out. (They get something like $2^{n-n/\log n}$.) But to compute $\min_i \langle x, v_i\rangle$ is slightly stronger -- in this setup, it would be like solving MAX CNF-SAT.


What are the best known upper bounds and lower bounds for computing O(log n)-Clique? Input: a graph with n nodes,
Output: A clique of size $O(\log n)$,
Providing links to references would be great

The best known upper bound is essentially $n^{O(\log n)}$. You can improve a little on the constant factor in the big-O using fast matrix multiplication, but that's about it. There are a lot of algorithmic references on the $k$-clique problem which describe this reduction, it originates from papers of Itai and Rodeh and Nesetril and Poljak. (Apologies to Czech readers, I am ignorant of the proper diacritical marks.) See http://en.wikipedia.org/wiki/Clique_problem

If you could solve $\log n$-clique in $n^{\varepsilon \log n}$ for every $\varepsilon > 0$, then you could also solve 3SAT in subexponential time. This can be seen as a "lower bound" to further progress. One way to prove this is to first show that if $\log n$-clique in $n^{\varepsilon \log n}$ for every $\varepsilon > 0$, then MaxCut on $n$ nodes is in $2^{\varepsilon n}$ time for every $\varepsilon > 0$. This follows directly from a theorem in my ICALP'04 paper that relates the time complexity of MaxCut to the time complexity of $k$-clique. From there, one can appeal to standard reductions to reduce 3SAT to MaxCut, showing that subexponential MaxCut implies subexponential 3SAT.

In terms of unconditional lower bounds, nothing nontrivial is known, to my knowledge. We don't even know how to show that $O(\log n)$-clique isn't solvable with an algorithm that runs in linear time and uses only logarithmic workspace.


Is 0-1 programming with constant number of constraints polynomially solvable? It was shown in the paper "Integer Programming with a Fixed Number of Variables" that integer programmings with constant number of constraints (or variables) are polynomially solvable.

Does this hold for 0-1 programming?

I'm assuming that by "0-1 programming with a constant number of constraints" you mean the following problem:

Maximize some linear function of (x_1, x_2, ..., x_n) subject to the constraints that each x_i is in {0,1} and a constant number of additional linear constraints.

This problem is NP-complete even with 1 additional constraint since 0-1 knapsack can be written in this form.


How does one augment AdaBoost with cross-validation? How does one augment AdaBoost with cross-validation?

The question is stated very succinctly; yet I think I can help since I'm familiar with the terminology. I'm gonna use information from Data Mining: Concepts and Techniques, which is a standard textbook.

Chapter 6 discusses different algorithms for classification. Then, in section 6.14, two methods are introduced for increasing the accuracy of a classifier:

Bagging: Creates an ensemble of models (classifiers or predictors) for a learning scheme where each model gives an equally-weighted prediction.
Boosting: Creates an ensemble of classiﬁers. Each one gives a weighted vote.

The two methods incorporate a base classifier, trying to improve its accuracy by sampling the data several times, and training the classifier on the sampled instance.

AdaBoost is a boosting method. (The name stands for "Adaptive Boosting".)

AdaBoost works as follows:

http://img181.imageshack.us/img181/8198/adaboost.png

The equation (6.66) mentioned in the image is as follows:

$error(M_i)=\sum\limits_j^d{w_j \times err(X_j)}$

where:

$error(M_i)$ is the error rate of model $M_i$;
$err(X_j)$ is the misclassiﬁcation error of tuple $X_j$: If the tuple was misclassiﬁed,
then $err(X_j)$ is 1. Otherwise, it is 0.

Now, what is cross-validation?

Quoting a part of section 6.13.2 of the above textbook:

  In k-fold cross-validation, the initial data are randomly partitioned into $k$ mutually
  exclusive subsets or “folds,” $D_1, D_2, \ldots , D_k$, each of approximately equal size. Training and testing is performed $k$ times. In iteration $i$, partition $D_i$ is reserved as the test
  set, and the remaining partitions are collectively used to train the model. That is, in
  the ﬁrst iteration, subsets $D_2, \ldots , D_k$ collectively serve as the training set in order to
  obtain a ﬁrst model, which is tested on $D_1$; the second iteration is trained on subsets
  $D_1, D_3, \ldots , D_k$ and tested on $D_2$; and so on.

Can AdaBoost be Augmented with Cross-Validation?

Yes. In AdaBoost, you need $D$, a set of $d$ class-labeled training tuples. Applying a k-fold cross-validation on this set, you will have 1 test sample (containing $d/k$ tuples) and $k-1$ training samples (containing $d(k-1)/k$ tuples). Using this strategy, and iterating $k$ times, the algorithm will benefit from the best of both worlds.

Note that cross-validation is an accuracy evaluation method, while AdaBoost is an accuracy improvement method. In the method I suggested above, cross-validation is used to retain the best classifier obtained from AdaBoost (in terms of accuracy), and discarding other classifiers.


Correspondence between complexity classes and logic I took a class once on Computability and Logic. The material included a correlation between complexity / computability classes (R, RE, co-RE, P, NP, Logspace, ...) and Logics (Predicate calculus, first order logic, ...).

The correlation included several results in one fields, that were obtained using techniques from the other field. It was conjectured that P != NP could be attacked as a problem in Logic (by projecting the problem from the domain of complexity classes to logics).

Is there a good summary of these techniques and results?

Neil Immerman produced a beautiful diagram that provides at-a-glance correspondences between complexity classes and logics interpreted by finite models.  It's on the cover of his book, and also at the bottom of his web page here: http://www.cs.umass.edu/~immerman/


Name this satisfiability problem? I've got a specific problem, but I'm not sure where to look to solve it:

In the context of my application, there are critical services, non-critical services, and agents which provide exactly one critical service and one or more non-critical services. I must choose from the collection of all agents (with replacement) a finite number of agents, such that each critical service is provided by a certain number of agents. This is straightforward. However, I have the secondary objective that I would like the set I choose to also provide as many different non-critical services as possible.

I'm sure this can be done via SAT, but I don't really want to mess around with NP-complete solvers. The goal for either kind (critical or not) of the services could be constructed as a network flow problem and solved in a straightforward way, but I can't seem to merge them, even as a multi-commodity network flow.

Has anyone seen this problem before, or something embarrassingly similar? I'd really appreciate a pointer to where I could start looking for solutions.

-- David

Let $k$ be the finite number of agents you're allowed to choose. If there are no critical services, finding the set of $k$ agents that maximize the number of non-critical services provided is equivalent to Max-$k$-Cover, which can't be approximated better than $1-1/e$ unless P=NP. So for an exact solution, you'll have to use something capable of solving NP-hard problems.

If you'd be happy with an approximation, you're in luck. The constraint that you have to choose $k$ agents such that there are sufficiently many of them providing each service is a matroid constraint. This paper shows how to achieve a $1-1/e$ approximation on set cover problems under a matroid constraint.

If you want something simpler to implement, the matroid greedy algorithm gives a $1/2$ approximation on submodular set functions. So you just need to repeatedly choose the agent that provides the most new non-critical services, after at each step removing from consideration any agent whose choice would prevent you from providing enough of each critical service before reaching $k$ agents. If each agent provides unique non-critical services, you're just maximizing a weight function over a matroid, so the greedy algorithm gives an exact solution.


How to prove that a formula can not be expressed in LTL, but can be in Buchi automata? I am looking for a general technique which can help me to prove not just that Buchi automata is more expressive model than LTL, but that the specific formula can/can't be expressed in LTL.

For example, "$p$ occurs at least on even positions" can be described by the following Buchi automata: $({q_0, q_1}, \Sigma, \delta, q_0, \{q_0\})$ where $\delta(q_1, *) = q_0$ and $\delta(q_0, p) = q_1$.

I've read that that automata can't be expressed in LTL, but I don't understand how to formally prove it.

Thanks.

First you need to know what you want to express and how you are going to express it. For instance, you can represent a property as a set of infinite traces.

The properties definable by Buechi automata are the $\omega$-regular languages. The properties definable by LTL formulae are the star-free regular languages. The star-free languages are a strict subset of the $\omega$-regular languages.

Section 5.1 of Principles of Model Checking by Baier and Katoen is a good, elementary starting point. If you want general proof techniques there are a variety of ways to proceed. One general technique that appeals to me is to use games. The first player is trying to show two structures can be distinguished with an LTL formula. The second shows they are the same. Two structures are LTL equivalent if the second player has a winning strategy. So, if you take two structures which are not isomorphic but the second player has a winning strategy, then, there is no LTL formula to distinguish between the two.

  An Until Hierarchy and Other Applications of an Ehrenfeucht-Fraisse Game for Temporal Logic, K. Etessami and Th. Wilke.

There are algorithms for checking if a given $\omega$-regular language is star-free. Unfortunately these are usually couched inside the proofs of theorems.

  Logical definability on infinite traces, Werner Ebinger and Anca Muscholl

I'll dig around a bit more and try to find a more algorithmic presentation.


Diameter vs. Tractability I would like to find examples of (unweighted) optimization problems $\Pi$ that satisfy 1) or 2):

1) $\Pi$ is NP-hard but polytime solvable in the class of graphs with diameter $\le k$, for all $k\ge 1$.

2) there is a $k_0\ge 1$ such that $\Pi$ is polytime tractable in the class of graph with diameter at most $k_0$ but NP-hard in the class of graphs with diameter at most $k_0+1$.

Any ideas ? What about DominatingSet for instance ?

For part (1), if you allow additional restrictions on your graph class, then independent set, Hamiltonian circuit, dominating set, etc., are NP-hard on arbitrary planar graphs but FPT on planar graphs of bounded diameter (because in planar graphs a bound on diameter implies a bound on treewidth). You can turn this into an artificial problem that is NP-hard on arbitrary graphs but FPT on arbitrary graphs of bounded diameter e.g. by asking whether the graph has either a Hamiltonian cycle or a Kuratowski subgraph.

For part (2), dominating set clearly is polynomial in graphs of diameter 1 (just pick a vertex within distance one from everything as your dominating set) but hard for graphs of diameter 2. To reduce from dominating set in arbitrary graphs to graphs of diameter 2, start with an arbitrary hard instance $G$ of dominating set with $n$ vertices $v_i$. Add $n$ more vertices $u_i$, and an additional new vertex $c$, with each $u_i$ adjacent to $v_i$ and to $c$. Call the resulting diameter-2 graph $G'$. Then $G'$ has dominating sets formed by adding $c$ to any dominating set of $G$. However, the dominating sets of $G'$ that avoid $c$ must have size at least $n$ because they include at least one vertex from each $u_i$–$v_i$ pair.


Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$? Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$?

This question came up while watching "Graduate Complexity at CMU - Lecture 2: Hierarchy Theorems (Time, Space, and Nondeterministic)" https://www.youtube.com/watch?v=HrJKTTJfweo

In time 00:53:30 - Prof. Ryan O'Donnell states that "there are languages decidable in $DTIME(2^{t(n)})$ that are undecidable in $NTIME(t(n))$".

Is this currently a known fact?

Your answers will be greatly appreciated!

Thanks,
Avi Tal

If $\mathrm{NTIME}(n) \supseteq \mathrm{DTIME}(2^{n/2000})$ (where NTIME and DTIME uses constant factor in the big-oh) then for all time-constructible $t\geq n$, we have that $\mathrm{NTIME}(t) = \mathrm{DTIME}(2^{\mathrm{O}(t)})\supsetneq \mathrm{DTIME}(2^t)$ to the contrary to your quest. So, in that case, requiring the NTM to read a tape of nondeterministic guesses are essential to separate these classes.

And it is still open that $\mathrm{NTIME}(n) = \mathrm{E}$.

Given a language $\mathrm{L}\in \mathrm{DTIME}(2^{\mathrm{O}(t)})$ decided by a TM running in time $2^{ct}$ where $c$ is some constant, construct the language $\mathrm{L}_\mathrm{pad} = \{x10^{2000*ct-1-\vert x\vert}\vert x\in \mathrm{L}\}$. Clearly, $\mathrm{L}_\mathrm{pad}$ can be decided by a TM running in time $\mathrm{DTIME}(2^{n/2000})$, i.e. $\mathrm{L}_\mathrm{pad}\in \mathrm{DTIME}(2^{n/2000})$. By our assumption, we have that $\mathrm{L}_\mathrm{pad}\in \mathrm{NTIME}(n)$, i.e. there exists an NTM deciding $\mathrm{L}_\mathrm{pad}$ in non-deterministic time $dn$ for some constant $d$. Now, we describe the NTM for $\mathrm{L}$. When given an input dtring $x$, our NTM for $\mathrm{L}$ first pads it up to length $2000*ct$ and then run the $\mathrm{NTIME}(n)$ NTM for $\mathrm{L}_{pad}$. Clearly, our NTM runs in non-deterministic time $cdt$, putting $\mathrm{L}$ inside $\mathrm{NTIME}(t)$.


A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut I am studying the Unique Games Conjecture and the famous reduction to Max-Cut of Khot et al. From their paper and elsewhere on the internet, most authors use (what to me is) an implicit equivalence between the MAX-CUT reduction and constructing particular tests for long codes. Because of my own lack of clarity about that equivalence, I struggle to follow this train of thought.

It also seems clear from these expositions that one could describe the reduction purely in terms of graphs, but that by coincidence or preference nobody chooses to do it that way. For example, in these lecture notes of O'Donnell he hints that the long-code test corresponds to a natural definition of the edges in the graph being constructed, but since it's not spelled out that rule seems to depend on the choice of a cut to define the boolean function being tested, and it has left me rather confused.

So I'm asking for someone to explain the reduction "just" graph-theoretically. I think this will help me understand the equivalence between the two viewpoints.

Let me see if I can clarify this, on a high level. Assume the UG instance is a bipartite graph $G = (V \cup W, E)$, bijections $\{\pi_e\}_{e \in E}$, where $\pi_e\colon \Sigma \to \Sigma$, and $|\Sigma| = m$. You want to construct a new graph $H$ so that if the UG instance is $1-\delta$ satisfiable, then $H$ has a large cut, and if the UG instance is not even $\delta$-satisfiable, then $H$ has only very small cuts.

The graph $H$ contains, for each vertex in $W$, a cloud of $2^m$ points, each labeled by some $x \in \{-1, 1\}^\Sigma$. The intention is that you should be able to interpret a long code encoding of the labels of $W$ as a cut of $H$. Recall that to encode some $\sigma \in \Sigma$ with the long code, you use a boolean function $f\colon \{-1, 1\}^\Sigma \to \{-1, 1\}$; in particular it is the dictator function $f(x) = x_\sigma$. Let's produce a cut $S\cup T$ (i.e. bi-partition of the vertices) from the long code encoding as follows. If $w \in W$ has a label encoded by the boolean function $f$, go to the the cloud of vertices in $H$ corresponding to $w$, and put in $S$ all vertices in the cloud that are labeled by some $x$ for which $f(x) = 1$. All others go to $T$. You can do this backwards to assign boolean functions to all $w \in W$ based on a cut of $H$.

In order for the reduction to work, you need to be able to tell only by looking at the value of a cut $S\cup T$ whether the boolean functions corresponding to the cut are close to a long code encoding of some assignment of labels to $W$ that satisfies a lot of the UG constraints of $G$. So the question is what information do we get from the value of a cut $S \cup T$. Consider any two vertices $a$ with label $x$ in the cloud corresponding to $w$ and $b$ with label $y$ in the cloud corresponding to $w'$ (in the reduction we only look at $w$, $w'$ in different clouds). We said that the cut can be used to derive boolean functions $f_w$ and $f_{w'}$. Now if there is an edge $(a,b)$ in $H$, then $(a, b)$ is cut if and only if $f_w(x) \neq f_{w'}(y)$. Therefore, using only the value of a cut to tell if the boolean functions it induces are "good" is the same as having a test that, given boolean functions $\{f_w\}_{w \in W}$, only asks for what fraction of some specified list of pairs $((w, x), (w', y))$ we have $f_w(x) \neq f_{w'}(y)$.

In other words, whenever Ryan says in the notes "test if $f_w(x) \neq f_{w'}(y)$", what he really means is "in $H$, add an edge between the vertex in the cloud of $w$ labeled by $x$ and the vertex in the cloud of $w'$ labeled by $y$". I.e. for every $v\in V$, every two of its  neighbors $w, w'$, and every $x,y \in \{-1, 1\}^n$, include the edge between the vertex in the cloud of $w$ labeled by $x\circ \pi_{v,w}$ and the vertex in the cloud of $w'$ labeled by $y \circ \pi_{v,w'}$, and assign the edge weight $(({1-\rho})/{2})^d(({1+\rho})/{2})^{n-d}$ where $d$ is the Hamming distance between $x$ and $y$. In this way the value of a cut divided by the total edge weight is exactly equal to the success probability of the test.


Diagonalization arguments for QMA type proof systems Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, with the essential idea being that of constructing an oracle in stages and diagonalizing any $\cal{P}$ machine against that oracle. Similarly, diagonalization arguments can also be used to diagonalize a $\cal{BQP}$ machine against an oracle like the Grover oracle, and achieve a separation between $\cal{BQP}$ and $\cal{QMA}$. I was wondering whether I can use diagonalization (against $\cal{QMA}$ machines) to separate classes like $\cal{QMA}$ and $\cal{PP}$, or $\cal{QMA}$ and $\cal{AWPP}$. Is there any literature on these types of separations? A subtlety that I note is that for the diagonalization argument against $\cal{BQP}$ machines, the essential idea is that the quantum machine cannot "search for a needle in a haystack", meaning that if there are an exponential number of query states to keep track of, a quantum machine is almost blind to the change in any one of them. However, if you have a prover as well as a quantum machine, the prover can just "give you the needle"; meaning, the prover can just send you the right state to query. Can diagonalization still work in these settings?

Yes, diagonalization arguments can still be used. For the oracle separation $\mathcal{QMA}^\mathcal{O}\subsetneq \mathcal{PP}^\mathcal{O}$, design an oracle $\mathcal{O}$ such that the following language separates the classes:

$$L = \{1^n\ |\ \left| \mathcal{O}\cap\{0,1\}^n\right|>\tfrac{1}{2}2^n \}$$

This language is clearly in $\mathcal{PP}^\mathcal{O}$ for any choice of oracle $\mathcal{O}$. However, it is not always in $\mathcal{QMA}^{\mathcal{O}}$, "because" it is difficult for a quantum machine to estimate whether a state $a|0\rangle |\phi\rangle+b|1\rangle |\psi\rangle$ has $|a|>|b|$ when the difference $|a|-|b|=\mathcal{O}(2^{-n})$ is exponentially small. This is true even in the presence of a prover, because even if the prover supplies the correct answer, it is not possible to verify whether the answer is correct. In your terminology: There is no needle to give; rather, the task is to count the number of needles, and then a single needle doesn't help much.

I hope somebody can supply useful literature references.


One-way functions with respect to various resource bounds Informally, one-way functions are defined with respect to PTIME algorithms. They are computable in polynomial time but not invertible in average-case polynomial time. The existence of such functions is an important open problem in theoretical computer science.

I'm interested in one-way functions (not necessarily for cryptographic applications) defined with respect to different resource bounds. Such resource bounds could be LOGSPACE or bounded nondeterminism.

  Is there a candidate (natural) problem which is one-way with respect to LOGSPACE algorithms? Is there a candidate (natural) problem which is one-way with respect to nondeterministic linear time algorithms ($\text{NTIME(n)}$)?

I'm fine with worst-case hardness of invertiblity with respect to the above resource bounds.

Regarding log-space:  Several candidate one-way functions are computable in log-space or below (and are supposedly secure even against poly-time adversaries).  You can find several pointers for example in the Cryptography in NC$^0$ paper.

Two specific examples include:

Integer multiplication (there are some subtleties for standard OWF, but if you only care about worst-case this is enough)

The Impagliazzo-Naor candidate based on subset-sum:
$f(a_1,...,a_n,S) := (a_1,..., a_n, \sum_{i \in S} a_i \mod 2^n)$.


Dinner-table description of theoretical computer science? I'm often asked what a theoretical computer scientist does.  It would be great to have some nice responses to this question.  I tend to fall back to technical jargon and people's eyes usually glaze over at this point.

  What does a theoretical computer scientist do, in terms that can be understood by people who are not computer scientists?

A good answer should be snappy, accurate in spirit, without sounding vague or trite.  For bonus points, the answer should hint at why a theoretical computer scientist is neither a mathematician nor an IT practitioner.

This question is inspired by the MO question https://mathoverflow.net/questions/3559/colloquial-catchy-statements-encoding-serious-mathematics although the intent is different.

I give people a concrete example. Specifically, I often motivate complexity theory with the same very illustrative (but simple) problem. I ask my audience how they would instruct a small child to discover whether his name is in an alphabetically sorted list of names (and tell them that it takes the child 3 seconds to compare any one name to another). It is often the case that the person/group will come up with the naive, linear approach. I force the conversation to turn to the logarithmic algorithm (I might use a different word than logarithm) either by asking the person for something better or by mentioning it myself. I show them how doubling the size of the list only adds three seconds of work for the child with this new approach. And I compare this directly with the linear version, which will now seem entirely silly.

Of course, I bring it back to earth. I tell them that child in question is generally a computer but that it could be a child or really anyone in general. That the questions we ask aren't really about computers but are more about the amount of space, time and information you need to solve problems. And I motivate complexity analysis by analogy to the two different methods for solving the same problem.

When I've got their attention - I bring out the heavy hitters. I ask them "can you prove that the logarithmic solution is the best you can ever hope to do or can you find something better?" and I ask them "are there problems that no process (algorithm) can hope to solve?" I've been surprised at how people try to tackle these questions when they don't have a TCS background.


Under what conditions is the Dining Philosophers Problem unsolvable? The wikipedia article for the Dining Philosophers Problem lists some solutions which are dependent on external information, i.e.:

Numbering of forks
A waiter to act as mutex
Messaging between philosophers

If we restrict the problem to the bare essentials, i.e.:

No information encoded in the table/forks
No prior meeting between philosophers, and hence no ordering/numbering
No communication between philosophers at the table

Is it provably impossible for every philosopher to have a strategy that avoids deadlock/starvation?  Is there a good understanding of the "minimal" conditions necessary for a solution to exist?

Well, if the philosophers are following the exact same strategy and there is nothing to distinguish them (like who is closest to the door etc.) then they will do exactly the same and deadlock must occur: Whenever one (Aristotle) picks up the left fork then the philosopher on the right (Beauvoir) takes Aristotle's right fork.

If you allow access to a source of randomness this should be easily fixable, however (everyone eats for a short time when possible and waits for a long, random, time thereafter).


What CS theories are absolutely paramount for someone new to TCS to understand? First - I'm happy to be a part of this community. Electronics and software engineering are both my passion and my profession, yet I feel as if I'm missing a solid basis in theoretical computer science. This field absolutely fascinates me, and I was pleased to see a Stack Exchange community built around it. So thanks to everyone who contributes.

I'm interested in building well-rounded foundation TCS, but don't know where to start. Of course Turing, etc is very popular, but I'd like some reference from researchers in the field on what theories are critical to have a greater, well rounded understanding of computers, while actually solving real problems. Please include any examples/advice where TCS has helped you solve a specific problem, if applicable.

My questions..

What areas are critical for me to study in mathematics?
What areas are exciting and "hot" in theoretical CS right now?
What areas are incredibly useful to consider for hardware innovation?
What areas are useful when considering software innovation?

If it helps at all I work in IoT as a software/cloud architect, primarily writing ruby/C++, while occasionally working with EE on hardware design. I'm just starting to get into PCB design in my free time.

Thanks again in advance, looking forward to learning!

(Disclaimer: this answer has a focus on programming languages theory, which is only one of the many disciplines under the TCS umbrella.
Apologies for the length.)

A small digression

You are asking for topics in TCS which

are "hot" in theoretical CS right now
are useful for innovative applications in software/hardware in the next future

From the way you pose the question, I am led to think that you believe that the two requirements above largely overlap, and/or that only bleeding edge research in TCS can have some impact in future technologies. If that is the case, I would instead argue that the overlap is instead much smaller.

First, CS theory is usually very far ahead most applications.
This is not unlike theory in other science disciplines. In the past, some great theoretical developments took much time to influence the industry.
A few examples:

Turing's vision of computers influenced automatic computers
Church's $\lambda$-calculus influenced programming languages
Higher order functional programming influenced Google's map/reduce
System F influenced generic types of Java (and C#, Scala, etc.)
System F$\omega$ influenced Scala higher kinds
Dependent types influenced Haskell GADTs
Church-style encodings of algebraic data types influenced the "visitor pattern" in OOP
Category theory influenced functional programming
Constructive/intuitionistic logic influenced type systems

These influences did not happen overnight. If history repeats, some new
technology tomorrow is more likely to draw from old-ish theory (relatively speaking) than bleeding edge discoveries.

Second, while some theoretical research is directed by some clear applications, sometimes research is driven by curiosity: when we discover a new approach and the first results appear to lead to an elegant theory, which reshapes our way of thinking about some topic, then we follow that direction. Often, even if we can't find a practical application right now, we still want to know how far we can go!

Third, some of the most powerful theory involves negative results. These, on the one hand do not tell us how to solve problems, but on the other hand tell us to avoid wasting resources trying to achieve the impossible.

For instance, computability theory tells us that we cannot precisely count the number of pages in a PostScript document (!), so we need to either move to better document formats or live with some approximate solution. Dually, we learn that if we design a new media format, we should try to avoid the same issues.

Another example: the so-called "free theorem", or parametricity property, can be used to prove the impossibility of writing a function with a certain polymorphic (or generic) type, in some languages.

Another: the Curry-Howard isomorphism can be used for a similar goal, proving the impossibility of a hypothetical program. (Shameless plug: I once used that to answer a Scala question on StackOverflow)

Some suggested "paramount" topics

(The following lists are not, by any means, complete. I only wrote the first topics that came to my mind.)

I would recommend the following topics as the bare minimum.

[Logic] Classical propositional logic. First order logic. Naive set theory.
[Computability] Decidable and semidecidable problems. Rice theorem. Many-one reduction.
[Computational complexity] P vs NP. Completeness / hardness. Polynomial reduction.
[Programming languages] $\lambda$ calculus: untyped & simply-typed. Church encodings (for untyped). Fixed points vs recursion.

These are more advanced. I would not recommend to study them all, albeit maybe one should know what these topics are about, at least. Having even a superficial understanding of these can help in keeping the mind open.

[Logic] Intuitionistic logic. ZFC set theory. Linear logic.
[Geometry] Basic topology.
[Domain theory] Posets. $\omega$CPOs. Complete lattices. Scott topology. Fixed point theorems (Tarski, Kleene). Induction  ($f(x)\sqsubseteq x \implies \mu f \sqsubseteq x$). Coinduction.
[Computability] Rice-shapiro.
[Type theory] Polymorphic types (System F). Dependent types and recursive/inductive types (Calculus of Constructions, Coq, Agda, etc.). Curry-Howard. Homotopy type theory (hot topic).
[Category theory] Products/coproducts. Functors. Natural transformations.
$F$-algebras/coalgebras.
[Programming languages] Imperative, functional, and logic programming. Formal semantics: operational (small and big step), denotational, axiomatic (Hoare logic). Continuations.
[Model checking] Temporal logics (modal $\mu$ calculus, CTL, LTL, etc.). SAT-solvers. SMT-solvers.
[Concurrency] Petri nets. Process algebras.

These are even more advanced or hotter topics.

[Programming languages]  Verification. Abstract interpretation. Gradual typing.
[Category theory] Cartesian closed categories. More "abstract nonsense" in general.
[Model checking] SAT-solvers. SMT-solvers.
[Type theory] Homotopy type theory (hot topic).
So. Many. Others.

And finally,

the topics mentioned in the digression above :-)

Most, if not all, these topics have had a deep influence on the design of modern programming languages. Some of these can also affect the way we think rather deeply. Here's a few examples from my experience.

When stuck in writing a correct while loop, one might stop and try to think about the loop invariants, and solve the issue. Of course, this only happens if one has seen Hoare logic before.

Remembering certain programming techniques can be hard. Sometimes, theory can help to quickly recall / reconstruct such techniques. For instance, above I mentioned the visitor pattern. Its definition can be recovered remembering that recursive types are interpreted as initial $F$-algebras, so by initiality, we immediately obtain an associated type
$$
\mu F \to \forall \alpha.\ (F\alpha \to \alpha) \to \alpha
$$
So, in OOP, we would take the object (of recursive type $\mu F$), the visitor (of type $F \alpha \to \alpha$), and must return the result of the visitor ($\alpha$). Translating this into OOP, say Java, is routine.

This might look as gibberish before studying these topics, but I believe one
can see that, in this way, a one-line theoretical description can summarize a complex technique like the visitor pattern.

Concluding, I hope I managed to show that the topics above have had an impact on software, and probably will have more in the future. I also hope this does not feel too overwhelming, especially since it's only about the PL part of TCS! :-)


Is the collapse of $PH$ known to extend downward to classes in-between its levels? Contained in-between each level of the polynomial hierarchy are various complexity classes, including $\Delta_i^{\text{P}}$, $\text{DP}$, $\text{BH}_k$, and $\Sigma_i^\text{P} \cap \Pi_i^\text{P}$. For lack of better terminology, I will refer to these and any others as intermediate classes between levels $i$ and $i+1$ in the polynomial hierarchy. For the purposes of this question, assume they are the classes contained in $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$ but contain $\Sigma_i^\text{P}$ and/or $\Pi_i^\text{P}$. We want to avoid including $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$, if possible, as it is trivially equivalent to $\text{PH}$ if it collapses to the ${i+1}^{th}$ level.

In addition, define the following:
$\text{DP}_i = \left \{ L \cap L' : L \in \Sigma_i^\text{P} \text{ and } L' \in \Pi_i^{\text{P}} \right \}$

The above is a generalization of the class $\text{DP}$ (also written $\text{D}^\text{P}$). In this definition, $\text{DP}$ is equivalent to $\text{DP}_1$. It is considered in another cstheory.se question. It is easy to see that $\text{DP}_i \subseteq \Delta_{i+1}^{\text{P}}$ and contains both $\Sigma_i^\text{P}$ and $\Pi_i^\text{P}$.

Reference Diagram:

Question:
Suppose that the polynomial hierachy collapses to the ${i+1}^{th}$ level, but does not collapse to the $i^{th}$ level.  That is, $\Sigma_{i+1}^\text{P}=\Pi_{i+1}^\text{P}$ and $\Sigma_{i}^\text{P}\neq\Pi_{i}^\text{P}$.

Can we say anything more about the relationships between these intermediate classes themselves and others in any level below $i+1$? Is there a schema for a collection of complexity classes where, for every collection, the classes are equivalent if and only if the $\text{PH}$ collapses exactly to an arbitrarily chosen level?

Just as a followup, suppose that the hierarchy collapsed to any particular one of these intermediate classes (such as $\Delta_{i+1}^{\text{P}}$). Depending on the class selected, do we know if this collapse must continue to extend downwards, perhaps even to the $i^{th}$ level?

The above question was partially explored and answered in a paper by Hemaspaandra et. al:
A Downward Collapse within the Polynomial Hierarchy
Does someone happen to know of additional examples not mentioned in this paper or have further intuition as to what needs to happen in order for a class to accomplish this?

I don't have a good answer, but in the spirit of complexity, I have some answers which suggest that a good answer may be hard to come by :).

Note that the generalized version of Ladner's Theorem implies that there are infinitely many poly-time degrees strictly in between $\mathsf{\Sigma_i P}$ and any poly-time degree strictly above it. In particular, if the hierarchy collapses to the $i+1$-st level but not the $i$-th, then there are infinitely many p-degrees between $\mathsf{\Sigma_i P}$ and $\mathsf{\Sigma_{i+1} P} \cap \mathsf{\Pi_{i+1} P}=\mathsf{\Sigma_{i+1} P}$.
If I recall correctly, constructing an oracle for which $\mathsf{PH}$ looks like the arithmetic hierarchy is still an open problem. By "looks like the arithmetic hierarchy," I mean that $\mathsf{PH}$ does not collapse, and $\mathsf{\Sigma_{k} P} \cup \mathsf{\Pi_k P} \subsetneq \mathsf{\Delta_{k+1} P} = \mathsf{\Sigma_{k+1} P} \cap \mathsf{\Pi_{k+1} P}$ for all $k$. This at least suggests that the answer to your question may not be known.
Ker-I Ko gives oracles in which he separates the levels of $\mathsf{BPH}$ from those of $\mathsf{PH}$. As these two hierarchies intertwine one another, this gives you at least some information about relativizable collapses of problems between the levels of $\mathsf{PH}$.
This next reference is the wrong direction, but you might also be interested in the result and its techniques. Chang and Kadin showed that if the Boolean hierarchy (which lives entirely below the second level of $\mathsf{PH}$, but extends $\mathsf{DP}$ to a whole hierarchy) collapses to its $k$-th level then $\mathsf{PH}$ collapses to the $k$-th level of the Boolean hierarchy over $\mathsf{\Sigma_2 P}$.


Defining inductive types in intensional type theory purely in terms of type-theoretic data To define a (non-indexed) W-type all we need is a type $A:U$ and a function $B:A\to U$ and we get a type $W_{a:A}B(a)$. To check that this definition is valid we only need to check that the definitions of $A$ and $B$ are valid.
Now general inductive types seem like very scary beasts and I still don't entirely understand what a proof checker kernel (e.g. in Coq) is doing to make sure the definition is valid.
In intensional type theory there is apparently a big gap between W-types and general inductive types. For example the generic W-type recursion applied to the W-type encoding of unary natural numbers is not as strong as standard recursion for natural numbers.
So the question is: is there a way to set up inductive types so that to check the validity of a definition you only need to check the validity of finitely many non-inductive typing judgements?
A strongly normalizing type theory can't fully interpret itself but I guess we could have a partially defined quote unquote specifically for the bits of data necessary to define inductive types. Can you suggest any references?

It turns out that $W$ types plus identity types (eq/= in Coq) allow you to construct pretty much all the general inductive types you want, with the expected computation rules, and even canonicity. This is a very recent result of mine, you can read a preprint at Why not W?, which has been accepted for publication in the TYPES 2020 post-proceedings.
The idea is that even though the standard construction of say the natural numbers from W types does not work, as is well known, a refined, slightly more complicated construction can be made to work. The way my refinement works is to use identity types to pick out the elements of the standard construction which are in canonical form.
This puts general inductive types on an internal, finitary footing, which is a large simplification of the theory. However, there remain some practical problems to be looked at around efficiency and usability.
Other, prior work on simplifying the theory of inductive types includes The Gentle Art of Levitation, by James Chapman, Pierre-Evariste Dagand, Conor McBride, and Peter Morris.


Math talk: Theorem about git revision control system? I would like to give a mathematics talk on the git revision control system. It is now widely used in mathematics as well as in the computer science industry.  For example, the HoTT (Homotopy Type Theory) community uses it, and it is the go to system for collaborative editing of text files, whether they be source code or latex markup.

I know git uses the notion of a directed acyclic graph, which is a start.  However, a good mathematics talk mentions proofs and theorems.

What theorem might I prove about git that is actually relevant for its use?

Interestingly, there is a nascent mathematisation of version control systems, although at this point it's only partially applicable to Git. It's called patch theory [1, 2, 3, 4, 5] and  arose in the context of the DARCS version control system. It can be seen as an abstract theory of branching and merging. Recently patch theory has been given HoTT [ 6 ] and categorical [ 7 ] treatments.

Patch theory is work in progress, and doesn't cover all aspects of version control, but contains a lot of theorems that you could look at. It is a clear example of theory that's applicable to the 'real world' -- not surprising, for patch theory is an abstraction / simplification of something very concrete. At the same time it connects with cutting-edge maths like HoTT.

J. Dagit, Type-Correct Changes - A Safe Approach to Version Control Implementation.
G. Sittampalam, Some properties of darcs patch theory.
I. Lynagh, Camp Path Theory.
D. Roundy, Implementing the darcs patch formalism ... and verifying it.
J. Jacobson, A Formalization Of Darcs Patch Theory Using Inverse Semigroups.
C. Angiuli, E. Morehouse, D. R. Licata, R. Harper, Homotopical Patch Theory.
S. Mimram, C. Di Giusto, A Categorical Theory of Patches.


What is the most powerful kind of parser? As a side-project, I'm writing a language using Python. I started by using a flex/bison clone called Ply, but am coming up against the edges in the power of what I can express with that style of grammar, and I'm not interested in hacking up my language because of an impedance mismatch with the tool. Therefore, I'm not averse to writing my own.

So what's the most powerful type of parser? Citations to papers (as well as more introductory articles) would be welcome.

(I know that 'powerful' is not precisely defined, but let's be a little loose with it and see where the answers go)

A grammar is usually defined as a Context Free grammar - a precise definition is given on the Wikipedia page, but it works the same as it does in PLY, which is based on Bison, which is in turn based on yacc.

It says here that PLY uses a LALR parser. This is essentially an LR parser where the lookup tables are condensed, possibly introducing parsing conflicts, reducing some of the expressiveness of an LR grammar (ie, a context free grammar that an LR parser can parse). If you want to know about the limitations of this particular branch of parsers and those of other parsers, an overview of all kinds of parsing techniques (LL, LR and others) is given here.

To answer your question: there exist parsing algorithms capable of parsing any context-free language, even if the language is ambiguous (ie, there is more than one way to interpret the input):

The first such algorithm was the CYK algorithm, which unfortunately has a running time of $O(n^3 |G|)$, where $n$ is the length of the input string and $|G|$ is the size of the grammar and is therefore impractical for parsing languages.

The second algorithm is the Earley algorithm. This algorithm is also capable of parsing any context free grammar. Although the algorithm needs $O(n^3)$ time to parse an ambiguous language, it only needs $O(n^2)$ time to parse an unambiguous language. In addition, it apparently works in linear time for most LR grammars and works particularly well on left-recursive grammars.

Here you can find a paper discussing a practical implementation of (an adaptation of) the Earley algorithm. They conclude: "Given the generality of Earley parsing compared to LALR(1) parsing ((which is roughly what PLY does)), and considering that even PEP’s ((their implementation of Earley's algorithm)) worst time would not be noticeable by a user, this is an excellent result".

The last type of parser is the GLR parser. This is a generalised version of LR parsing, capable of parsing any context-free language.

A mature implementation of GLR is ASF+SDF. Bison can also generate a GLR parser, though its implementations is slightly different from the 'standard' GLR algorithm. The Elkhound Algorithm is a GLR/LALR hybrid algorithm. It uses LALR when possible and GLR when needed, in order to be both fast and capable of parsing any grammar.

Beyond context free grammars there are context sensitive grammars, but these are in general hard to parse and don't add that much expressiveness: you can do more with them, but for most applications the extra uses are not relevant, unless you're parsing a natural language.

As the final step there are unrestricted grammars. At this point the grammar is Turing-complete, so there is no bound one can give on how long it will take to parse a particular language, which is undesirable for most parsing applications. The extra power is almost never needed. If you do want to use all that power, there is the language machine available.

Lastly, implementing your own parser-generator is not a trivial affair, in particular to get it to be fast. I've personally just finished making my own version of flex (the lexer generator), and while this seemed like an exercise in relatively simple algorithmic problems, it became quite complex to get right, in particular when I tried to support Unicode. Consider using an already existing implementation instead of writing your own.


Interesting results in TCS which are easily explainable to programmers without technical background Suppose you're meeting with programmers who have taken some professional programming courses (/ self thought) but didn't study a university level math.

In order to show them the beauty of TCS, I'd like to gather some nice results/open questions coming from TCS which can easily be explained.

A good candidate for this purpose (IMHO) will be showing that the halting problem is not decidable. Another will be showing a lower bound on the running time of comparison based sorting (although that's a bit pushing it from what I expect them to understand).

I can also use the ideas from Explain P = NP problem to 10 year old, assuming some of them are unfamiliar with it.

So, questions has to be:

(0. Beautiful)

Explainable with (at most) high school math.
(preferably) not trivial enough to be shown in professional programming courses (for C++/Java/Web/etc.).

In addition to the halting problem, I suggest discussing:

Rice's Theorem.  Some of the explanation on Wikipedia is a bit jargon-heavy, but it's generally not a hard theorem or proof to understand other than that; it has a lot of relevance to real-world concepts like anti-virus software.  The proof is about as involved as the proof of the halting problem (and actually depends on the undecidability of the halting problem).  Basically, just understand that a "computable function" is a Turing machine or computer program.