Upper bounds on higher order eigenvalues of regular graphs Suppose $G$ is an undirected $d$-regular $n$-vertex graph for some constant $d$. Let $\lambda_k$ be the $k$-th largest eigenvalue of the normalized laplacian $L$ of $G$ (defined as $I - \frac{1}{d} A$ where $A$ is the adjacency matrix of $G$).

If the degree is constant, we can have good expanders of course but I want to say that the lower eigenvalues cannot be too close to $1$ if the degree is constant. I was wondering if there is a quantitative statement of this sort.

Are there any bounds known about how close $\lambda_k$ can be to $1$, as a function of $k$? In particular, is something of the following form known:

  ``For all $ k \ll n$,  we have $\lambda_k  \; \leq \; \left( 1 - O\left( \frac{1}{k^{0.99}}\right) \right)$'' ?

(where the constant in the order notation can hide factors of $d$).

I wanted to add this as a comment but it was too long. I am not sure if this completely answers the question.

For bipartite graphs for instance we can possibly get a simple first cut bound from a simple trace method. Lets look at the adjacency matrix. In your case we want to show that $\lambda_k$ is not close to 0. So consider $Trace(A^2)$. For a d-regular graph this is always $\geq dn$. Therefore $$\sum \lambda_i^2 \geq dn$$ which implies that $$2d^2k + n\lambda_k^2 \geq dn$$ Now for $k << n$ and $d$ a constant one can essentially get a $\Omega(\sqrt{d})$ bound for $\lambda_k$. So indeed they cant be very close to 1 in the normalized laplacian. I am not sure whether the parameters work out in the way you want them to.


Estimating graphs using random cuts How easy is it to estimate a graph by observing only a few random cuts? Is there prior work related to this? I did google but could not find anything concrete.

Any help would be appreciated. Thanks.

Its not clear what you want to estimate, or what you mean by looking at a random cut. But it is hard to learn much about a graph by just observing the size of a random cut. This is because a random cut will always cut $m/2$ edges in expectation (where $m$ is the number of edges in the graph), independent of the structure of the graph. Of course, the entire graph can be thought of as a vector of length ${n \choose 2}$, so if you get to observe the -exact- size of that many random cuts, because they are likely to be linearly independent, you can reconstruct the graph. There's nothing special about cuts here: you're just observing the exact value of the dotproduct of $d$ linearly independent vectors with an unknown vector of length $d$, and this system of linear equations will have an exact solution.


Adaptive vs Bernoulli sampling Flajolet analyzed Wegman's Adaptive Sampling for estimating distinct values (species) in a stream (population), giving an unbiased estimator for mean and specified the standard error to be approximately $1.2/\sqrt(n)$ where n is the number of samples. Another way of estimating the number of distinct values is by using Bernoulli sampling over uniformly hashed value of the target attribute. In this case, the standard error should be $\sqrt{pq/n}$. The obvious advantage of Adaptive Sampling is the number of samples retained is at most n whereas Bernoulli sampling would require $Np$ samples ($O(N)$ in $N$, the actual number of distinct values). Is my analysis correct? For some reason, I cannot accept the Bernoulli sampling can be more accurate than Adaptive for fixed sample size, $n$. Thoughts?

I do not quite understand the question because you do not define some of your paremters (what are $p$ and $q$?). But let me try to clarify things. Let $N$ be the true number of distinct items.

First Flajolet's guarantee for Wegman's algorithm is that, if the space used is $n$ words, then the estimate $X$ produced by the algorithm satisfies
$$
\sqrt{\mathbb{E}[(X - N)^2]} \leq \frac{1.2}{\sqrt{n}}N.
$$

Your suggestion is to sample at a rate $p$ from the $N$ different distinct items. I.e., you make a pass over the sequence of item identifiers and you keep each identifier in memory with probability $p$. Let the number of items stored in memory be $n$. Then the expected value of $n$ is $pN$, and the variance of $n$ is $p(1-p)N$, so we have
$$
\sqrt{\mathbb{E}\left[\left(\frac{n}{p}-N\right)^2\right]} =\sqrt{\frac{1-p}{pN}}N = \sqrt{\frac{1-p}{\mathbb{E}[n]}}N.
$$

So you are right that this is in some sense comparable with the guarantees for adaptive sampling (as well as those for the Flajolet-Martin probabilistic counting algorithm). However, the issue is that without knowing $N$, you do not know ahead of time what your space complexity $n$ will be, even in expectation. Or to put it another way, you do not know what to set $p$ to in order to make the space complexity acceptable.

A natural fix is to start with some sample rate $p$, say $p = 1$, and once your memory fills up, you lower $p$. This is essentially the adaptive sampling algorithm.

The simple sampling algorithm you suggest can be useful to refine a rough estimate of $N$. For example, you can use adaptive sampling or Flajolet-Martin to get a constant factor approximation to $N$, and then use that approximation to set $p$ in the Bernoulli sampling strategy. See this nice paper by Daniel Kane, Jelani Nelson, and David Woodruff, where they use this idea and a lot more to get an optimal space algorithm for the distinct items problem. The paper also gives references to much of the more important work on this problem.


Complexity of the inverse modulo a composite number Supposing $M$ is a composite number and supposing $a$ is an integer such that $a^{-1}\mod M$ exists,  can we compute $a^{-1} \bmod M$ by using $O(\log^{b}(M))$ ring operations in the RAM model, where $b>0$ and is some fixed number?

I'm interested in the case where $a$ and $M$ are of similar sizes.

When we apply the Euclidean algorithm, we compute the remainder of an integer divided by another. It is not clear to me if this can be done in unit time in the RAM model using only ring operations.

Let us call the function which takes $(a,b)$ to $r$ such that $a = bq + r$ with $r < b$ (and all of $a,b,q,r$ nonnegative integers) the Remainder function. This function cannot be computed at all using only ring operations in the integers: any function that can be computed using only ring operations is a polynomial of its inputs, so if the Remainder function could be computed using only ring operations, it would follow that $Remainder(a,b) = f(a,b)$ for some integer polynomial $f$. For any fixed $b > 1$, the function $g(x) = f(x,b)$ would then be a univariate polynomial. Now, $g(b+1) = 1$, so $g(x)$ is not identically zero; but $g(x) = 0$ whenever $b | x$, so $g(x)$ has infinitely many zeroes, a contradiction.

However, if you allow $<$ in addition to ring operations, then the Remainder function can be computed in polynomially many steps (in the number of bits of the input) as follows: start with $q=1$ and check if $qb > a$ (if so, then the remainder is just $a$). Otherwise, multiply $q$ by $2$ repeatedly until $qb > a$. Then do binary search on $q$ to find $q$ such that $qb \leq a$ and $(q+1)b > a$, and finally output $a - bq$. This takes $O(\log (a/b))$ ring operations and comparisons; on most standard Boolean models of computation each such operation can be done in nearly $O(\log a)$ time.


HITS and PageRank, topic drift problem Reading some papers and articles about PageRank and HITS algorithm, I've figured out that there's a problem called topic drift problem. Googling it, (since I wanted to know more about it) I only found a few articles which has mentioned it but not in detail. I'd like to know is the problem caused by the fact that these algorithms ignore web page content and only conider inlinks (PageRank) and outlinks. But how does it happen? what are researches done by far to avoid this problem?

this is a pretty good discussion in this ref p123: Google's PageRank and Beyond:
The Science of Search Engine Rankings
Amy N. Langville & Carl D. Meyer, Princeton University Press.

  A final disadvantage of HITS is the problem of topic drift. In building the neighborhood graph $N$ for a query it is possible that a very authoritative yet off-topic page be linked to a page containing the query terms. This very authoritative page can carry so much weight that it and its neighboring documents dominate the relevant ranked list returned to the user, skewing the results toward off topic documents. Henzinger and Bharat suggest a solution to the problem of topic drift, weighting the authority and hub scores of the nodes in $N$ by a measure of the relevancy of a query [26].

ref [26] is apparently:

Improved Algorithms for Topic Distillation in a Hyperlinked
Environment Bharat, Henzinger, 21st ACM SIGIR Conference on Research and Development in Information Retrieval 1998

on p.2 they have another description/example of topic drift:

  We often find that the neighborhood graph contains documents not relevant
  to the query topic. If these nodes are well connected, the topic drift problem arises: the most highly ranked authorities and hubs tend not to
  be about the original topic. For example, when
  running the algorithm on the query jaguar and
  car the computation drifted to the general topic
  car and returned the home pages of different car
  manufacturers as top authorities, and lists of car
  manufacturers as the best hubs.


Can Polar Codes (or any other efficient codes) reach the second order capacity? In channel coding, it is known (e.g. Yury Polyanskiy's thesis, and the arxiv article A Tight Upper Bound for the Third-Order Asymptotics of Discrete Memoryless Channels) that certain codes, for example polar codes, can reach the Shannon limit for large enough block lengths $n$. However, for finite $n$, the best theoretically possible codes are known to satisfy

$$\log M \leq n C - \sqrt{n V}\, \Phi^{-1}(1-ε) + \frac{1}{2} \log n + O(1),$$

where $M$ is the size of the code, $C$ the capacity of the channel, $V$ the dispersion of the channel, and $ε$ the required (average or maximum) error.

Is it known how Polar codes (or any other codes) compare to this fundamental bound? The bound can be achieved using random codes, but I was wondering if there are any efficient codes that come close.

As far as I know, people conjecture that for Polar codes and any fixed DMBSC (discrete memoryless binary symmetric channel), $\log M \leq nC - O(n^{1-c})$ for some absolute constant $c > 0$ and vanishing error probability should be possible (or in other words, in order to be $\epsilon$ close to capacity, only a polynomially large $n$ in $1/\epsilon$ would suffice. However, there is no rigorous published proof available at this point. There are rumors about an upcoming proof, but that's not official yet.


Literature reference for search-BPP I'm trying to find the first article/paper that the complexity class search-BPP appeared in. Search-BPP, as defined as follows (in [1]):

A binary relation $R$ is in search-BPP if there is a probabilistic polynomial-time search algorithm $A$ that given $x \in R_L$ (the language defined by membership in the relation), outputs $y$ s.t. with probability $\geq 2/3$, $(x,y) \in R$.

Essentially, this is the generalization of BPP to search problems. The earliest article I could find mentioning search-BPP was in Goldreich's 2011 paper "In a world of P=BPP" (http://www.wisdom.weizmann.ac.il/~oded/COL/bpp-p.pdf). Was this introduced earlier? If so, could someone please provide a reference.

[1] Pseudo-Deterministic Proofs, Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden (https://arxiv.org/abs/1706.04641)

I’m not sure about the exact definition as given. However, the kind of search problems that has been studied the most in the literature are NP-search problems. In this context, there is no meaningful difference between “BPP-like”, “RP-like”, or “ZPP-like” randomized polynomial-time algorithms, as we can check the correctness of any purported solution in deterministic polynomial time. Thus, while the class of NP-search problems solvable in probabilistic polynomial time has been studied for a long time, it has not been generally called “Search-BPP”. In particular, the class is mentioned in Papadimitriou’s seminal papers [1,2], where it is denoted FZPP.

[1] Christos Papadimitriou, On inefficient proofs of existence and complexity classes, Annals of Discrete Mathematics 51 (1992), pp. 245–250, doi: 10.1016/S0167-5060(08)70637-X.

[2] Christos Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences 48 (1994), no. 3, pp. 498–532, doi: 10.1016/S0022-0000(05)80063-7.


Approximation for metric TSP: Worst case using nearest neighbor heuristic? I'm looking at different heuristics that approximate solutions for a metric Traveling Salesman Problem. I was wondering if there is a worst case ratio of tours calculated by the nearest neighbor heuristic to the optimal tour.

Apparently, the Minimum Spanning Tree heuristic is a 2-approximation for metric TSPs meaning that it will only find tours that - in the worst case - are twice as long as the optimal tour. Is there some factor like this for the nearest neighbor heuristic for metric TSPs?

No, the NN heuristic does not have constant factor for metric TSP.

Rosenkrantz, Stearns, and Lewis proved in An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM J. Comput. 6(3): 563-581 (1977) that the worst case ratio of the tour obtained by the nearest neighbor method is bounded above by a logarithmic function of the number of nodes.


Is deciding whether all satisfying assignments are NAE assignments coNP-complete? Let the language $L$ consist of the $k$-CNF formulas $\phi$ with the property that any satisfying assignment $x$ of $\phi$ is a Not-All-Equal (NAE) assignment, i.e. every clause of $\phi$ has at least one false literal under $x$. Equivalently, $L$ includes those $k$-CNF formulas $\phi$ for which $\phi(x) \implies \phi(\neg x)$.

Clearly $L$ is in coNP, since a certificate for a "no" instance is given by a satisfying assignment which is not a NAE assignment. Is $L$ also coNP-complete for $k > 2$?

As a simple example consider the $2$-CNF formula $(a \vee b) \wedge (\neg a \vee \neg b)$ whose satisfying solutions have exactly one of $a$ or $b$ true, but not both.

Consider the following reduction from coNP-complete problem $k$-UNSAT to your language $L$ (where $k$-UNSAT is the language of all unsatisfiable $k$-CNF formulas):

On input a $k$-CNF formula $\psi$, create new variables $x_1, \ldots, x_k$ and output formula $\phi = \psi \land (x_1 \lor x_2 \lor \cdots \lor x_k)$.

If $\psi$ is unsatisfiable then $\phi$ is also unsatisfiable. In that case, it is vacuously true that every satisfying assignment $x$ of $\phi$ is a NAE assignment. (Equivalently, $\phi(x) \implies \phi(\neg x)$ is always true since $\phi(x)$ is always false.) This shows that $\phi \in L$. Thus, we see that if $\psi \in k$-UNSAT (that is, $\psi$ is unsatisfiable) then $\phi \in L$.

On the other hand, if $\psi$ is satisfiable then $\phi$ is also satisfiable by keeping the old assignment for the variables in $\psi$ and setting $x_1 = x_2 = \ldots = x_k = 1$. Notice that this is a satisfying assignment of $\phi$ that is not NAE. In other words, $\phi \not\in L$. Thus, we see that if $\psi \not\in k$-UNSAT (that is, $\psi$ is satisfiable) then $\phi \not\in L$.

The above shows that $\psi \in k$-UNSAT if and only if $\phi \in L$ and therefore that the reduction is correct. Since $k$-UNSAT is coNP-complete, we can conclude that $L$ is coNP-hard.


Tolerance parameter of statistical query model and adaptivity It seems that the reasonable assumption for the tolerance parameter of statistical query model is roughly $1/\sqrt{n}$, which is obtained from concentration inequalities (see, e.g., Definition 2.3 of Statistical Algorithms and a Lower Bound for Detecting Planted Cliques, http://arxiv.org/pdf/1201.1214v5.pdf).

My question is why this is a reasonable choice. The rationale of this choice seems to come from the argument that the oracle can return the average of the query function over $n$ data points. However, since the query function is adaptively chosen, the $1/\sqrt{n}$ rate of concentration does not always hold. This is because the query function itself also depends on data and thus the independence is ruined. For example, this paper (Section A, Preserving Statistical Validity in Adaptive Data Analysis http://arxiv.org/pdf/1411.2664v2.pdf) gives an example in which the concentration fails due to adaptive choice of the query.

What you are saying is that given $N$ random samples one cannot simulate an algorithm that makes $T$ queries to VSTAT$(N)$. If the $T$ queries are chosen adaptively then one might need more samples (the best upper bound is $\sqrt{T} N$ samples).
This is true but not an issue for the planted clique paper you mentioned. That paper is concerned with proving a lower bound against algorithms using VSTAT. Specifically we prove that any algorithm using a polynomial number of queries to VSTAT$(N)$ will not be able to solve the planted $k$-biclique problem for $N=\tilde{\Omega}(n^2/k^2)$ ($n$ is the number of vertices on each side). Answering even a single query to VSTAT$(N)$ requires $\Omega(N)$ samples so the lower bound reflects the difficulty of solving the problem with with $N$ (or less) samples.


Can limit of hard languages be easy? Can the following all hold simultaneously?

$L_s$ is contained in $L_{s+1}$ for all positive integers $s$.
$L = \bigcup_s L_s$ is the language of all finite words over $\{0,1\}$.
There is some complexity class $C$ and a notion of reduction appropriate for $C$ such that for each $s$, $L_s$ is hard for $C$.

I think we can just start with some base language $L$, then take $L_0 = L$ and $L_{s+1} = L_s \cup \{0,1\}^{s+1}$.

That is, each $L_s$ is the union of $L$ with all strings of length up to $s$. Each $L_s$ is at least as hard as $L$ but is no harder (in an asymptotic sense), assuming we can count to $s$.

I also thought about the opposite "limit", so each $L_{s+1}$ is contained in $L_s$, and $L = \cap_s L_s$ is easy while each $L_s$ is hard. But I think we could just start with a hard (but countable) language $L_0$ and just remove one word at each step; the intersection should be empty (every word is eventually removed).


Regular safety properties and bad prefixes of $\omega$-regular properties I have two questions:

By starting with a nondeterministic Büchi automaton (NBA) $\mathcal{A}^{\varphi} = (Q, \Sigma, \rightarrow, I, F )$ for an $\omega$-regular property $\varphi$, we can construct a NFA $\widehat{\mathcal{A}}^{\varphi} = (Q^{\prime}, \Sigma, \rightarrow^{\prime}, I^{\prime}, F^{\prime} )$ that recognizes the bad prefixes of $\varphi$ as the complement of NFA $\overline{\mathcal{A}}^{\varphi} = (Q, \Sigma, \rightarrow, I, F_1 )$:

For every state $q \in Q$, if there is a nontrivial strongly connected component (SCC) $C \subseteq Q$ such that  $C \cap F \neq \emptyset$ and $C$ is reachable from $q$, then $F_1 \leftarrow F_1 \cup \{q\}$. Basically, $q$ is in $F_1$ iff the language of $\mathcal{A}^{\varphi}$ starting from $q$ is nonempty.

N.B. A SCC consisting of a single state with a self-loop is considered nontrivial SCC.

  Does NFA $\widehat{\mathcal{A}}^{\varphi}$ recognize all bad prefixes of $\varphi$ and, hence, $\omega$-regular safety properties are regular safety properties, where a safety property is regular if its set of bad prefixes is a regular language?

By determinizing and complementing $\widehat{\mathcal{A}}^{\varphi}$, we can get a NBA $\mathcal{B}^{\psi}$.

  Is $\psi = Closure(\varphi)$?

According to PMC, $Closure(\varphi)$ of a linear-time property $\varphi \subseteq \Sigma^{\omega}$ is the set of all infinite words whose finite prefixes are also prefixes of $\varphi$. This coincides with the notion of closure from topology, and $Closure(\varphi)$ will always be a safety property.

Sorry for the elementary question.

Your construction for bad prefixes is not correct on NBA's.
For instance take the NBA on alphabet $A=\{a,b\}$ with two initial states $q_a$ and $q_b$ where for both $x\in A$, $q_x$ goes to an accepting sink if the first letter is $x$ and to a rejecting sink if the first letter is not $x$.

Then the language recognized is $A^\omega$, but the set of "bad prefixes" you compute is $A^*$ i.e. all finite words.

Your construction works if you first determinize the automaton. Then the new final states are the ones which cannot reach a component $C$ accepting some infinite word. Careful though, the deterministic automaton is no longer Büchi, it is a parity automaton, so it is a little more complicated to check if a component has empty language.

As for your question about closure, you are essentially asking if for any regular language $L$, $Closure(L)$ is the set of words containing no bad prefixes of $L$. This is true: a word is in the closure of $L$ iff it is arbitrarily close to words in $L$ iff it does not contain a bad prefix.


What is the time complexity of increasing the precision of finding matrix eigenvalues? There are various algorithms that output the eigenvalues of an $n \times n$ matrix in time $O(n^3)$. However, I can't find anywhere that tells me about the precision of the output of the algorithm. That is, what is the time complexity of increasing the number of bits I require the answer to?

Furthermore, how does this rely on the number of bits we use to specify the initial matrix? For example, if I specify the matrix elements to exponential precision in $n$.

Any starting point for this would be helpful.

I do not have a complete answer to your question but here are some thoughts and references. First of all, it is crucial to specify the model of computation and the representation of the input, I expect this post will clarify why. I know of essentially two cases:

the input matrix has coefficients that are algebraic numbers (*): then the eigenvalues are also algebraic numbers and can be determined effectively, one can also determine the multiplicities of the eigenvalues. There exists very good algorithms to get rational approximations of algebraic numbers such a [1] where the bit complexity is $O((b+n)n^2)$ (neglecting some log factors) where $b$ is the number of bits and $n$ is the degree of the polynomial that represents the algebraic number (which in turns depends polynomially on the heigh of the coefficient of the matrix).
the input matrix has coefficients that can be arbitrary real numbers but we can query arbitrary rational approximations of them: this fits into the theory of Computable Analysis and things get complicated. It is known that eigenvalues are uniformly computable (because they are roots of the characteristic polynomial) from the input coefficient [2], the algorithm runs in polynomial time (in the precision), probably using [1] it runs in linear time (if we ignore the cost of computing approximations of the input). However the eigenvectors are not computable nor are multiplicities, unless you known them in advance [3].
your do not care about the representation of numbers and assume all arithmetic operations have a unit cost: this is the BSS model and [4] gives a very precise arithmetic complexity that is logarithmic in the precision (ie $O(\log b)$ where $b$ is the number of bit). But of course this completely neglects the complexity of representing and operating on the numbers and assume that equality is a unit operation (whereas it is uncomputable in general). I personally find this model to be very inadequate to express the complexity of this problem.

Based on your question, I suspect your matrix has rational inputs (which are algebraic numbers of degree 1), thus it would fit in the first case. In this case, I think (but have not checked) that the bit complexity will be linear (maybe with polylogarithmic factors) in the precision, but the constant will depend on the size and numbers in the input matrix (most probably in a polynomial fashion).

(*) algebraic numbers can be represented exactly with a finite number of bits, all arithmetic operations (and more) on algebraic numbers can be performed effectively, however the complexity details on the height of the numbers, thus on field extension in which the coefficients of the input lie.

[1] Optimal and nearly optimal algorithms for approximating polynomial zeros, Pan, 1996

[2] Complexity Theory of Real Functions, Ko

[3] A Computable Spectral Theorem, Brattka and Ziegler

[4] The Complexity of the Matrix Eigenproblem, Pan and Chen


Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions? Consider a permutation $\sigma$ of $[1..n]$. An inversion is defined as a pair $(i, j)$ of indices such that $i < j$ and $\sigma(i) > \sigma(j)$.

Define $A_k$ to be the number of permutations of $[1..n]$ with at most $k$ inversions.

Question: What's the tight asymptotic bound for $A_k$?

A related question was asked before: Number of permutations which have the same Kendall-Tau distance

But the question above was regarding computing $A_k$. It can be computed using dynamic programming, since it satisfies the recurrence relation shown here: https://stackoverflow.com/questions/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble-sort-swaps

The number of permutations with exactly $k$ inversions has also been studied and it can be expressed as a generating function: http://en.wikipedia.org/wiki/Permutation#Inversions

But I can't find a closed-form formula or an asymptotic bound.

According to Wikipedia, the number of permutations in $S_n$ with exactly $k$ inversions is the coefficient of $X^k$ in
$$1(1+X)(1+X+X^2)\cdots(1+X+\cdots+X^{n-1}).$$
Denote this by $c(n,k)$. This shows that
$$c(n+1,k) = \sum_{l=0}^k c(n,k-l).$$
So the number of permutations in $S_n$ with at most $k$ inversions is equal to the number of permutations in $S_{n+1}$ with exactly $k$ inversions. This has a neat combinatorial proof as well (hint: take $\pi\in S_{n+1}$ and remove $n+1$).

If we are interested only in the coefficient of $X^k$, then factors $X^m$ for $m > k$ don't make any difference. So for $n > k$, $c(n,k)$ is the coefficient of $X^k$ in
$$
\begin{align*}
&1(1+X)\cdots(1+X+\cdots+X^{k-1}) (1+X+\cdots+X^k+\cdots)^{n-k} \\ =
&1(1+X)\cdots(1+X+\cdots+X^{k-1}) \frac{1}{(1-X)^{n-k}} \\ =
&1(1+X)\cdots(1+X+\cdots+X^{k-1}) \sum_{t=0}^\infty \binom{t+n-k-1}{t} X^t.
\end{align*}
$$
This implies the formula
$$
c(n,k) = \sum_{t=0}^k \binom{n+t-k-1}{t} c(k,k-t), \quad n > k.
$$

When $k$ is constant, the asymptotically most important term is the one corresponding to $t = k$, and we have
$$
c(n,k) = \binom{n-1}{k} + O_k(n^{k-1}) = \frac{1}{k!} n^k + O_k(n^{k-1}).
$$
The same asymptotics work for $c(n+1,k)$, which is what you were after.

For non-constant $k$, using the fact that $\binom{n+t-k-1}{t} = \binom{n+t-k-1}{n-k-1}$ is increasing in $t$ and $\sum_{t=0}^k c(k,t) \leq k!$, we get the bounds
$$
\binom{n-1}{k} \leq c(n,k) \leq k! \binom{n-1}{k}.
$$
Better bounds are surely possible, but I'll leave that to you.


Reference for the fact that (0=1) implies false requires a universe in MLTT It's a fairly well-known fact that deriving a contradiction from a disequality (for example, $(0=1) \to \bot$) in Martin-Loef type theory requires a universe.

The proof is also fairly straightforward -- in the absence of universes, we can erase the dependencies from any dependent type to get a simple type as its shape, and so proving that $(0=1) \to \bot$ implies we can prove $p \to \bot$ for an arbitrary atom $p$, which is of course not possible.

However, I can't find who proved this first! Does anyone have a reference?

I know of:

Jan M. Smith, The independence of Peano's fourth axiom from Martin-Löf's type theory without universes, The Journal of Symbolic Logic 53(3), p. 840-845, 1988.


Comparison versus RAM models I have been wondering about comparison versus RAM models and have some very basic sounding questions.

Is there a name for the subset of P (or FP really) that is computable by comparison RAM algorithms? For the avoidance of confusion we can think of the comparison RAM model as just being the normal RAM model where the input symbols are given in terms of rows/columns of a ternary matrix that tells us if pairs of symbols are bigger, the same, or smaller.  That is we never get to find out or use the value of the input symbols.

What are the biggest known gaps for the time complexity of RAM and comparison RAM algorithms for natural problems coming from this subset of P (or FP)? We can imagine unnatural examples where comparisons are constant time but the RAM model has to spend a lot of time inputting the bits.  Those are not the ones I am interested in.  Sorting is the simplest example with a log gap for poly size inputs but is there anything bigger?

Related to the last question, is there some reason to suppose a maximum gap between (natural) RAM and comparison RAM problems? I suppose one route would be to say that you could simulate one with the other efficiently.

You can defiintely cook up promise problems where RAM is much stronger.  Of course it's weird because you have to actually phrase your problems in terms of comparisons. suppose your memory is initialised into a permtuation, i.e. with memory registers x(1), ..., x(n) taking on the values 1, .., n exactly once each.    The problem is to compute the # of i s.t. x(i) < x(1).


Real representation versus communication complexity Suppose that Alice and Bob communicate to compute a function $f:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$. Does the minimal degree of a real polynomial/rational representation of $f$ play a role for upper and/or lower bounds on the deterministic, non-deterministic, randomized or quantum communication complexity of computing $f$?

The minimal degree of a real polynomial representing the parity function of $n$ variables is $n$. However, the deterministic communication complexity is at most $2$ bits.


Decide if a given sequence is regular or context-free Given a sequence s (or a finite set of sequences) I would like to know if this was generated by a regular or by a context-free (supposes these are the only options) grammar.

Of course, this is an ill-posed problem because any finite language is regular. So I am more interested in work which tried to discover context-free, non-regular structures inside a given sequence. I could think of two possible ways of doing it:

is a smallest CF grammar "much smaller" than a smallest regular grammar? If yes, this would be a good indicator that the generative grammar should be CF
try to find specific context-free structures (in the sense of the pumping lemma).

Any work out there I should know about?

As you already noted, a single example or any finite number of words in $L$ is not going to be the right notion. So why not look beyond? A somewhat famous paper did so in 1967 and revealed what happens when you try to learn in the limit.

An alternative interpretation of your question leads to the field of descriptive complexity theory where one looks for a minimal representation $\langle M,w\rangle$ of a string in terms of a TM $M$ and an input word $w$ to it. Asking whether a single word had been (better?) generated by a CFG or a DFA is indeed ill-posed: either one would be a special case of such a pair $\langle M,w\rangle$.

Finally, given $w\in\Sigma^*$, asking for the smallest DFA $A$ and CFG $G$ with $w\in L(A)$ and $w\in L(G)$ is going to disappoint. The simplest DFA (with just one state) and the simplest CFG (with one non-terminal) will do because the universal language $\Sigma^*$ is blatantly regular. To make this intersting you'd need some negative instances, which brings you back to reading said famous article. I recommend it.


Dual BCH codes of design distance $d$ The SODA 2008 Ailon-Liberty paper on fast Johnson-Lindenstrauss transforms uses a "dual BCH code of design distance 5" as part of the construction. They cite the
MacWilliams-Sloane book on error-correcting codes as the source for how to construct these codes, but my initial wading through the book doesn't appear to yield the answer (there are dual codes and BCH codes, but...)

Is there an easy way to describe how to construct such a matrix, for general matrix dimensions $m \times d$ ?

(I'm not an expert in this subject, but here's my understanding.)

The BCH code of code length $n=2^m-1$ and designed distance $2t+1$ is specified in terms of its generator polynomial.  Fix $\alpha$ to be a primitive element of $GF(2^m)$.  Then, $g$ is the polynomial of smallest degree with coefficients in $GF(2)$ which has its roots $\alpha, \alpha^2,\alpha^3,\dots,\alpha^{2t}$.  (The codewords are then given by all multiples of $g$ of degree at most $n-1$; see the wikipedia page for polynomial codes).  The designed distance is a lower bound on the distance of the code.

The dual BCH code of design distance $2t+1$ is just the dual of the BCH code in the usual sense, the set of vectors orthogonal to the codewords of the BCH code of design distance $2t+1$.  Its generator polynomial is given by $(X^n+1)/g(X)$.  I believe the matrix in the Ailon-Liberty paper has the codewords as its rows.

Here are some notes which describe the BCH code construction: http://www.uotiq.org/dep-eee/lectures/4th/Communication/Information%20theory/2.pdf


Unique games conjecture - edge permutations What do the edge permuations in the unique games conjecture represent?

These permutations represent the constraints on the labeling. for each edge, there is some set of labellings for the edge's vertices which is legal. Since we are talking about unique games, these legal labellings are limited in the following way: if (u,v) is an edge, then for any possible labeling of u, there exist a single legal labeling of v. This means that we can represent the legal labellings of any edge's vertices by a permutation $\phi :[k] \to [k]$ where $[k]$ is the set of labels.


Relation between transcendental numbers and computational complexity? Regarding the relation, there is the Hartmanis-Stearns conjecture, but beyond Turing Machine of the realtime output, there is no further conjecture or theorem. Obviously irrational algebraic number can not be outputted by real time TM, and so are  infinite transcendental numbers. But beyond realtime TM and in the same complexity classes like P, are there irrational algebraic numbers and transcendental numbers? Or we can separate transcendental numbers from irrational algebraic numbers by the different complexity classes?

One other way to look at this, which brings in potentially all complexity classes above $\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$, is to consider real numbers in their binary expansion. Any real number whose binary expansion doesn't end with $0^\infty$ or $1^\infty$ - i.e., which is not a dyadic rational - has a unique binary expansion. We can treat this binary expansion as an element of $\{0,1\}^{\mathbb{N}}$, which in turn we can view as a subset of $\mathbb{N}$, and therefore (under the standard identification of $\mathbb{N}$ with $\Sigma^*$ for $\Sigma$ a finite alphabet) a language. One can then ask about the complexity of this language. (Dyadic rationals correspond to languages which are only finitely different from $\emptyset$ or from $\Sigma^*$, so aren't all that interesting anyways...)

Note that if a language $L$ has its characteristic function $\chi_L$ being real-time computable, then $L$ itself is in $\mathsf{E}$: given input $x$ of length $n$, suppose that $x$ is the $N$-th string in length-lexicographic order (that is, the string $x \in \Sigma^*$ corresponds to the integer $N \in \mathbb{N}$ under the standard identification). To decide whether $x \in L$, use the real-time machine to output the first $N$ bits of $\chi_L$ and read off the $N$-th bit. This takes $O(N)$ time; but $|x| = \log_{|\Sigma|} N$, so this is $O(|\Sigma|^{|x|}) = 2^{O(|x|)}$ time.

(As far as I can tell the converse need not hold. Or at least, the naive proof that I was thinking of doesn't work. That is, suppose $L \in \mathsf{E}$. The naive way  decide the first $N$ bits of $\chi_L$ takes $\approx N \cdot 2^{O(\log N)} = N^{1 + c}$ time for $c > 0$.)

Using this identification, you can in principle use all complexity classes that aren't contained in $\mathsf{E}$ to try to understand the "complexity" of any non-real-time-computable transcendental numbers. However, I don't know how to relate complexity properties of the language $L$ to whether $\chi_L$ is algebraic or transcendental. Strikes me as a very interesting question. As pointed out by Emil Jerabek in the comments, using this identification, all algebraic numbers are in the linear-time version of the counting hierarchy $\mathsf{CH}$, hence also in $\mathsf{E}$. So this approach seems mainly useful for distinguishing the complexity of transcendental numbers from one another, rather than for distinguishing e.g. the complexity of real-time computable and algebraic numbers.


Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M) Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the promise that the language accepted by this automaton $L(M)$ is a deterministic context-free language and outputs a deterministic pushdown automaton $N$ which accepts precisely the language accepted by $M$?

An equivalent problem would be to construct an algorithm which takes as input a pushdown automata $M$ (with the promise that $L(M)$ is deterministic, as above) and a deterministic pushdown automata $N$. The output would be yes if $L(M) = L(N)$ and no if $L(M)\neq L(N)$.

I believe that an algorithm solving the first would give an algorithm solving the second by the decidability of equivalence of deterministic pushdown automata. I think a solution to the second would imply a solution to the first as we enumerate all deterministic pushdown automata and run the algorithm on them one by one, once we get a yes instance we output that automaton.

I wonder if anyone knows anything about this? Maybe it's a known problem and/or has a known solution? As an aside, I believe it is decidable if you introduce the restriction which says that the language generated by the PDA is the word problem of a group.

Take a deterministic TM $M$ and a word $w$. Consider its computation histories for the word $w$. Let $L$ be invalid histories (those which don't start with $w$, don't end with acceptance or are invalid). Either $L = A^{\ast}$ ($M$ doesn't accept $w$) or $L = A^{\ast} - \{h\}$ for some string $h$ ($M$ accepts $w$ with computation history $h$). First of all, $L$ is effective CFL, in the sense that you can build a grammar/PDA recognising it. Moreover, $L$ is a (noneffective) DCFL, but you can't show a DPDA for it effectively. Even more, $L$ is (noneffective) regular.

Small clarification:

You asked if the following problem is decidable:

given PDA $M$ promised that $L(M)$ is a DCFL, and a DPDA $N$ determine if $L(M) = L(N)$.

The answer is no, and in fact the following stronger fact holds: The following problem is undecidable:

given PDA $M$ promised that $L(M)$ is regular, determine if $L(M)=A^{\ast}$.


Structural normalization algorithm for the simply typed lambda calculus I would like to know if there is a (piecewise) structural normalization algorithm for the simply typed lambda calculus. By structural I mean a recursive function that only calls itself on subterms of its argument.
Suppose $T$ is an inductive type of terms, then it doesn't seem like there should be any way to define such a function $\text{nf} :T\to T$ directly, so what I want to know is whether one could define an intermediate inductive type $E$ and structural functions $p : T\to E$ and $r:E\to T$ so that $r\circ p:T\to T$ is the normalization function.
The motivation for this is that proving termination is immediate from the well-foundedness of the inductive types.
Are there any other references or implementations that address this question?

You can: define /hereditary substitution/ on already normalized STLC terms using structural induction (where the induction is (in part) on the type).
I couldn't find the reference I was thinking of right now, but a quick search for "agda hereditary subtitutions STLC" pointed to various relevant pages, such as https://github.com/ezyang/lr-agda/blob/master/STLC.agda


Is it possible to encrypt something in such a way that it can be decrypted by two different keys? I'm a lowly web dev / programmer of 10 years who's never tried to wrap his brain around the high concept stuff, so apologies is this is a stupid question (or if it belongs in programmers.stackexchange.com)

I started wondering the other day, is it possible to encrypt something and have it decryptable by two different keys?

Suppose you wanted to have a user's data encrypted by a user-defined key, but you also wanted a safely stored "backup" key in case the user forgot their key. Is that even theoretically possible?

This is possible, for instance using the following straight-forward approach (where $E(\cdot,\cdot)$ is some encryption function and $H(\cdot)$ is a cryptographic hash function):

Input: A message $m$ and a set of keys $\{k_1,\dots,k_n\}$.
Generate a random ephemeral key $k_e$ that is used to encrypt $m$ only.
Output (for instance):
$$(H(k_e), n, (E(k_1,k_e),\dots,E(k_n,k_e)), E(k_e,m))\text.$$

A message's recipient can subsequently decrypt all the encrypted keys $E(k_1,k_e)$ to $E(k_n,k_e)$
using his key $k$ and check whether the result's hash matches $H(k_e)$. If it does, he (highly likely) found the right $k_e$ and can proceed to decrypt $m$.

On the other hand, an adversary who does not have one of the keys $k_1,\dots,k_n$ learns nothing about $k_e$ from the hash $H(k_e)$ (as long as $H$ is not broken) nor any of the encryptions of $k_e$ (as long as $E$ is not broken), so he can't decrypt the message $m$ (as long as $E$ is not broken).

Drawbacks:

This approach leaks the number of keys for which a message is encrypted, which may not be desirable.
The method doesn't scale well if you need to support a larger number of keys, but it should do for as few as two. A possibility to avoid having to decrypt all encryptions of $k_e$ until one matches is to add some key ID (for example, a hash of the corresponding recipient's key) to each encrypted key that a recipient can compare to a hash of his own key, at the expense of a slightly longer ciphertext and potential correlation of the recipients' identities.


Does this variant of Multiplicative Linear Logic with mix rule enjoy cut elimination? In Multiplicative Linear Logic (MLL), addition of the mix rule eliminates 'connectedness' from Danos-Regnier criterion. I'm investigating how the criterion changes if we do not distinguish between tensor and par.

Let's take a MLL inference rules with the mix rule and forget the difference between tensor and par:

$$ \frac{}{\vdash A, A^\bot} \;\mathtt{id} $$
$$ \frac{\vdash \Gamma_1, A\quad \vdash \Gamma_2, A^\bot}{\vdash \Gamma_1, \Gamma_2} \;\mathtt{cut} $$
$$ \frac{\vdash \Gamma_1 \quad \vdash \Gamma_2}{\vdash \Gamma_1, \Gamma_2} \;\mathtt{mix}$$
$$ \frac{\vdash \Gamma, A, B}{\vdash \Gamma, A \cdot B} \;\mathtt{par}$$
The tensor rule is obsolete as it can be derived from the mix and par rules:
$$ \frac{\vdash \Gamma_1, A\quad \vdash \Gamma_2, B}{\vdash \Gamma_1, \Gamma_2, A \cdot B} \;\mathtt{tensor} $$

My intuition is that not all proof-structures are valid i.e. some variant of Danos-Regnier criterion for this system still is necessary. The intuition is that it admits cycles but only the trivial ones, not 'real' deadlocks. But I don't know how to formalize it, so I'll move to cut elimination formalization.

The above, might be considered a type system for an interaction net with a single self-annihilating node $ \mu $ (notation defined in the footnote):
$$ \{\ldots, e \frown \mu (a_1, a_2), e \frown \mu (b_1, b_2), \ldots, \} \rightsquigarrow \{\ldots, a_1 \frown b_1, a_2 \frown b_2, \ldots \}$$

Let's extend standard cut-elimination procedure with one more rule:
the trivial cycle, made from identity and cut only, disappears:

$$
\{\ldots, a \frown b, b \frown a, \ldots, \} \rightsquigarrow
\{\ldots, a \frown a, \ldots \} \rightsquigarrow
\{\ldots, \ldots \}
$$

Example of a deadlock: $a \frown \mu(a,b)$.

Questions:

Does the described type system, when applied in an obvious way to the interaction net, eliminates the possibility of deadlocks?
Does the type system enjoy cut elimination?
Are these two questions equivalent?
Are there any publications about it?

Footnote

Notation for the nets:

Net is a set of links.
Variables denote edges.
$ e \frown \mu(a,b)$ represents an a node $\mu$  with two auxiliary edges $a, b$ and a principal edge $e$.
Each variable is present in the set exactly 1 or 2 times, 1 means it is a 'free edge',
$\frown$ is commutative.
Two connected edges are just an edge: $\{\ldots, a \frown b, b\frown c, \ldots \} \rightsquigarrow \{\ldots, a \frown c, \ldots \}$

For question 1, if by "deadlock" you mean "non-trivial vicious circle", then the answer is obviously yes, simply because a non-trivial vicious circle cannot be typed: you will have a cut between a formula $A$ and a formula $F$ containing $A^\bot$ as strict subformula, so it is impossible that $F=A^\bot$. But this is kind of trivial: by refusing a priori to consider cyclic wires as deadlocks, you are eliminating the only possible typed deadlock, so of course you are deadlock-free...

For question 2, there are definitely problems with your sequent calculus.  First, I assume that you are working with orthogonality defined by $(A\cdot B)^\bot=A^\bot\cdot B^\bot$.  Then, you have that the formula $A^\bot\cdot A$ is essentially self-dual and, since it is provable, you have a proof of the empty sequent. But your inference rules (except cut) still verify the subformula property, which means that there is no cut-free proof of the empty sequent. In other words, you are forgetting the rule
$$\frac{}{\vdash}$$
Without this rule, cut-elimination does not hold. There is a further problem though, namely that you cannot represent the cut-elimination steps inside the sequent calculus: in other words, as a type system, you do not have subject reduction.  For that, you need to consider a unary cut rule:
$$\frac{\vdash\Gamma,A^\bot,A}{\vdash\Gamma}$$
Note that, like the tensor rule, the binary cut rule is derivable from this one (and mix).

For question 3, I assume that you are asking whether the system captures your notion of deadlock-freedom.  Since you are excluding cyclic wires a priori (i.e., you are artifically adding a cut-elimination rule that makes them disappear) the the answer is, again, trivially yes: a net normalizes (with your additional reduction rule) to what Lafont calls a reduced net (no vicious circle, no active pair) iff it is typable in the above system. This is provable by standard arguments: subject reduction/subject expansion and typability of reduced nets.

For question 4, I doubt anyone has published anything because this system is so degenerate that I honestly do not see what its interest may be.  In fact, one may further simplify the types by eliminating duality altogether: there is no negation, formulas are just
$$A,B::=\alpha\mathrel |A\cdot B$$
and axioms/cuts introduce/eliminate pairs of equal formulas. This system, albeit logically trivial (because of self-duality), has the same normalization property as above. It boils down to the so-called relational semantics of MLL, which is applicable to untyped structures too, in which tensor equals par.

Regarding your search for a Danos-Regnier correctness criterion for single-agent nets, there is not much to be said: if you make cyclic wires disappear "by fiat", then the self-dual "typing" above suffices and correctness criteria play no role; if you stick to the standard definitions, then there can be no meaningful correctness criterion: every one-conclusion net cut with itself generates cyclic wires.


What are the open ended questions for an CS Undergraduate to think about? What can be a possible open ended research topics in Computational Complexity (or something equally fun), for an undergraduate to think about?

[I am planning to take up something fun, however my objective is not to publish a paper, but just to think about it for the joy of the subject :) , but of course, if a paper comes along, that might be fun as well...

P.S. I have taken basic courses in Theory of Computing, Algorithms, Advanced Algorithms, Advanced DS and Discrete Mathematics among others.]

Of course, for us in academia, most problems are fun anyway: we would not be there otherwise ;) But I understand that you might be more interested in problems which do not require much background and/or which are related to mundane topics like social games. Note that it might be harder (and more important) for you to find someone willing to comment on your solution and help you to improve it than to find a fun problem itself. For this reason,  asking a professor in your department might be a better starting point. That said, here are some suggestions as to where to find ideas, and a modest proposal of mine.

Have a look at the  proceedings of the conference "Fun with Algorithms": they should provide you with a good selection of "Fun" problems to work on, and a venue where to submit your results for feedback.
Check the publications of people known to consider fun problems and problems for fun. For instance:

Kurt Mehlhorn has several, one of the latest being a study of a variant of the game "Master Mind", published in "The Query Complexity of Finding a Hidden Permutation" (another one of his is a mathematical model for how a mold can compute the path of minimal length in a maze).
Erik Demaine has a long sequence of such problems, one of the latest being the study of variants of the game "Instant Insanity".
Elkhanan Mossel wrote a nice study of the "Mine Sweeper game".

Have a look at my (modest) proposal of "fun" problem below. If you work on it, get in touch with me!

Levitating Towers

As an undergraduate, you probably know the problem of the Hanoi Tower. If you want to "have fun", you might consider simple variants of it. Here is a very simple variant you might be interested in, which I designed for an assignment while I was a TA for an algorithm course, but never gave to students because I found it too hard for undergraduate (at least too hard for a marked assignment).

Consider the case where you insert and remove disks always in the middle of the tower (defined in a symmetric way when the number of disks is even, so that you always remove the last disk that you inserted), while keeping at all time the constraint that no disk stands upon a smaller one. In how many moves can you move a tower of $n$ disks from one peg to another?

The exact answer is not known. I obtained at the time a complicated upper bound of $2^{n/2}$ via a combination of 3 recursive functions. The graph of all possible states and transitions (a classical way to study the original Hanoi tower problem) is fragmented. I believe there should be a reduction to the original problem but did not find it when I played with it.

Play with it. An example of the difficulty of the analysis (say, for symmetric rules removing the lower middle disk when the number of disks on a peg is even, and inserting below the center disk when the number of disk is odd) is the case where there is $1$ small disk (e.g. $1$) on the destination peg and $2$ larger ones (e.g. $8,9$) on the source peg. This particular sub-tower of height $2$ can be moved without any intermediate peg in $2$ moves (as opposed to $3$ moves and one intermediate peg in the traditional Hanoi tower): the removal order of the source peg is the same as the insertion order of the destination peg.


Potentially equal complexity classes without known contradictory relativizations What are some examples of pairs of complexity classes $A$ and $B$ such that

we do not know whether $A=B$, and
we do not know contradictory relativizations either (i.e., we do not know oracles $P$ and $Q$ such that $A^P = B^P$ and $A^Q \ne B^Q$)?

To phrase the question another way, what are some exceptions to the heuristic that if can't figure out contradictory relativizations then it is easy to resolve the equality question outright?

I think the biggest such example at present is $BQP $ (quantum polybomial time) vs $PH $ (the polynomial time hierarchy). Significant effort has been put into separating them relative to an oracle, with no success. (Of course a powerful enough oracle will make them equal.) And the best known containment result is that $BQP $ is in $PP $.

Some references for attacks on the oracle problem:
http://arxiv.org/abs/0910.4698
http://arxiv.org/abs/1007.0305


Complexity Classes - separations and inclusions What are the basic complexity class seperation and inclusion results that everybody should know? (I mean specifically results that are known, and the proofs can be understood by a non-expert)

It would be great to have a book or paper (or set of papers) which go through and prove all the simplest and most fundamental results in this area. Where could I find it?

Thank you.

I like Papadimitriou's book.

Specially, it has "Class Review" sections at the end of several chapters, illustrating the relations among complexity classes.

The relevant sections are:

 Section 10.4.1 (page 235): P, NP, coNP.
 Section 11.5.1 (page 272): P, ZPP, RP, coRP, BPP, NP, coNP, PP.
 Section 15.5.1 (page 385): AC, NC, RNC, P.
 Section 16.4.1 (page 405): NC$_1$, L, SL, RL, SC, NL, PolyL, P.
 Section 17.3.1 (page 433): PH and PSPACE.
 Section 20.2.1 (page 499): P, NP, coNP, PSPACE, EXP, NEXP, coNEXP, EXPSPACE, 2-EXP, ELEMENTARY, R.

The book also includes a nice take on time- and space-hierarchy theorems; see Chapter 7.

EDIT: I also recommend Complexity Zoo's Active Inclusion Diagram (requires Firefox 1.5 or later, or Opera 9 or later). If you don't have that, you may try Zoo's Static Inclusion Diagram.


Hardness of UNAMBIGUOUS-3DM Let UNAMBIGUOUS-3DM be defined by analogy to UNAMBIGUOUS-SAT, i.e. as a promise problem version of three-dimensional matching where we may assume there is no more than one solution.

Is there a randomised reduction from SAT, as there is for UNAMBIGUOUS-SAT, so that a polynomial-time algorithm for UNAMBIGUOUS-3DM would imply NP=RP?
For example, it would suffice for there to be a parsimonious reduction from SAT to 3DM, but I haven't found one in the literature.

If so, does it still work when restricting to planar instances of 3DM, i.e. where the bipartite graph associated with the 3DM instance is planar?

The answer to both questions is yes.
The standard reduction from 3-SAT to 3DM – as used by Garey and Johnson, for example – is not parsimonious, but there is a sequence of parsimonious reductions that goes:
3-SAT → 1-IN-3-SAT → MONOTONE-1-IN-3-SAT → 3DM
Moreover, these reductions can be done in a way that preserves planarity. The details can be found in [1, 2]. The key reduction MONOTONE-1-IN-3-SAT → 3DM is from [1]. It is shown to be parsimonious by [2], which also shows how to do the other reductions in a parsimonious way. The reduction from 3-SAT to PLANAR-3-SAT is done using the crossover gadget from [3], which [2] also shows to be parsimonious.
[1] M.E Dyer, A.M Frieze, Planar 3DM is NP-complete, Journal of Algorithms, Volume 7, Issue 2 (June 1986), Pages 174-184. PDF
[2] Harry B. Hunt, III, Madhav V. Marathe, Venkatesh Radhakrishnan, and Richard E. Stearns. The Complexity of Planar Counting Problems. SIAM J. Comput. 27, 4 (August 1998), 1142-1167. arXiv:cs/9809017
[3] David Lichtenstein. Planar Formulae and Their Uses, SIAM Journal on Computing 11:2 (1982), 329-343. doi:10.1137/0211025


Proving not NP-complete by non-existence of gadget Suppose we suspect a problem to be polynomial time solvable, but we are unable to prove this. So, we attempt to prove that the problem cannot be NP-hard. Known proofs in this direction show that if the problem under consideration is NP-hard, then some widely believed complexity assumption fails (e.g.: Graph Isomorphism).
Is it possible to show that a problem $X$ is not NP-hard by showing the following?
(i) certain type of gadget must exist for a reduction from 3-SAT to $X$, and
(ii) the type of gadget asserted in point (i) cannot exist.
I am afraid such results are not there. Are there at least conjectures that take this direction?

First, I agree w/ Ludwik & other comments that I think (i) is unlikely. Polynomial-time reductions are just polynomial-time algorithms satisfying a certain (fairly flexible! compared to say p-time algorithms computing a fixed function $f$) input-output relationship, and polynomial-time algorithms are just too varied to say that they must take a certain form. You can always compose a gadget-based reduction with a p-automorphism to get something that does not recognizably have gadgets anywhere. (So at the very least you probably want to say "up to p-isomorphism, every reduction must have a gadget of this form", but "up to p-isomorphism" is a pretty hairy equivalence relation to work with at this level.)
But for (ii), I know of one result like this:

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf, Planarizing Gadgets for Perfect Matching Do Not Exist, MFCS '12.

I don't think I can do much better than quoting the abstract:

To reduce a graph problem to its planar version, a standard technique is to replace crossings in a drawing of the input graph by planarizing gadgets. We show unconditionally that such a reduction is not possible for the perfect matching problem and also extend this to some other problems related to perfect matching. We further show that there is no planarizing gadget for the Hamiltonian cycle problem.


Consequences of a $p$-optimal proof system for $\operatorname{TAUT}$ I'm reading a paper which shows the result:

$(1)$ There is a $p$-optimal proof system for $\operatorname{TAUT}$. $\Leftrightarrow$
$(2)$ $L_{\leq}$ is a $P$-bounded logic for $P$.

Both $(1)$ and $(2)$ are unproven Conjectures.

A proof system for a problem $Q \subseteq \Sigma^*$ is a surjective function $P: \Sigma^* \to Q$ computable in polynomial time (see my other question). A proof system is $p$-optimal if for every proof system $P'$ for Q there is polynomial computable $T: \Sigma^* \to \Sigma^*$ such that f.a. $w \in \Sigma^*$

$$P(T(w)) = P'(w).$$

My first question is an intuition of the  $p$-optimal property: Does it mean that $P$ is minimal in a way? How does that work? Is it similar to the polynomial reduction one uses to show that a problem is $\operatorname{NP}$-hard?

A Logic $L$ is $P$-bounded for $P$ if there is a algorithm which decides the model relation $\mathcal{A} \models_{L} \varphi$ polynomial in $|\mathbb{A}|$. $L_{\leq}$ is variant of least fixed point logic (LFP). A formula $\varphi$ is $m$-invariant if for all structures $\mathcal{A}$ of size at most $m$ we have for all orderings $<_1, <_2$

$$(\mathcal{A},<_1) \models_{LFP} \varphi \Leftrightarrow (\mathcal{A},<_2) \models_{LFP} \varphi.$$ A formula in $L_{\leq}$ is satisfied on a structure $\mathcal{A}$ if it is at least $|\mathcal{A}|$-invariant and $(\mathcal{A},<) \models_{LFP} \varphi$ for one $<$.

I am interested in the consequences if $(1)$ was true (or even consequences if it was false?). $\operatorname{TAUT}$ is in $\mathrm{co}-\mathrm{NP}$ and $\operatorname{SAT}$ is in $\mathrm{NP}$. Is $(1) \Rightarrow \operatorname{NP} =
co-\operatorname{NP}$ and why? Is okay to "mildly assume" that $\operatorname{NP} = co-\operatorname{NP}$ is not true?

See the Wikipedia article for propositional proof complexity. p-simulation is similar to reductions between complexity classes. Existence of a p-optimal proof system is a well-known open problem in proof complexity.

It is statement 7 in Krajicek and Pudlak 1989. See page 1066 and 1067 for a list of statements implied/implying it. There are more statements that you can find by Googling.

There are experts who conjecture that extended Frege is an p-optimal proof system. Existence of a p-optimal proof system is a weaker statement than existence of a super proof system (which is equivalent to $\mathsf{NP}=\mathsf{coNP}$).

Jan Krajicek and P. Pudlak, "Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations", J. Symbolic Logic, 54(3), (1989), pp. 1063-1079.

Yijia Chen and Jörg Flum, "On optimal proof systems and logics for PTIME", 2010.

Zenon Sadowski, "On an optimal propositional proof system and the structure of easy subsets of TAUT", 2002.


Extending Hindley-Milner to type mutable references I have been trying to implement a programming language from scratch, and have gotten reasonably far. It reads just like Python, other than the fact that let is used to declare a variable as opposed to a bare assignment.

However, I'm now trying to add mutability into the language, specifically in the syntactical form

let mut x = 1

where x is now a rebindable variable. This is effectively the same as

let x = ref 1 in ...

in ML, but my type-checker inserts the dereference operator (!) automatically. So something like ref is never directly used. Any instance of x has a ! applied to it. So, if you do

let mut x = 1
let y = x
x = 2

Then x is still rebindable, and has the value of 2, but y is immutable and has the value 1.

I am having great difficulty extending my implementation of Hindley-Milner 's unification to support mutable references. The main paper I was reading was Standard ML-NJ Weak Polymorphism and Imperative Constructs by John Mitchell, as I was hoping to get an inference algorithm that had similar behavior to OCaml's weak polymorphism implementation.

This paper is pretty good and explains most things well enough, but it lacks a formal description of the type inference algorithm for its language. Are there any good resources on extending Hindley-Milners unification algorithm, that is, not the type system, with mutable references. I know the two go hand in hand, but I'm just having a really hard time jumping from the type inference rules from the paper I'm using to extending my implementation. I'm wondering if there is at least a description of an algorithm that unifies types in a language that supports mutable references.

Lastly, I saw this question here asking something similar. The asker states "I only find solutions for a language with mutable references but without genuine imperative control structures", I would like to see those references! I completely understand how to extend my language to have imperative control structures once I get my mutable references working, but this is where I am stuck now.

To get behaviour similar to Ocaml, simply avoid generalizing the type of mutable variables.

With ordinary let-bindings, you generalize if you bind a value, and don't generalize otherwise. With mutable variable bindings, you never generalize.

The standard ML-like behaviour is then:

let xs = []          // xs : forall a. list a

let as = 1 :: xs     // as : list int   -- instantiate a to int
let bs = true :: xs  // bs : list bool  -- instantiate a to bool

The mutable variable typing will go:

let mut xs = []     // xs : list ?a  -- a is an unification variable

let as = 1 :: xs    // as : list int  AND ALSO
                    // xs : list int, since ?a gets resolved to int
let bs = true :: xs // TYPE ERROR, since xs : list int


Complexity of sorting It is not difficult to show that sorting an array of numbers is hard for $\mathsf{TC^0}$.
If the input is an array of 1s and 0s then it is essentially the function $Count$ (given $n$ bits, output the number of 1s in binary) since $Count$ is complete for $\mathsf{TC^0}$ and it is possible to convert unary numbers to binary numbers and (logarithmicly) small binary numbers to unary numbers in $\mathsf{AC^0}$:

  $Count(\vec{x}) = Binary(Sort(\vec{x}))$
  $Sort(\vec{x}) = Unary(Count(\vec{x}))$

So the power of $\mathsf{TC^0}$ is essentially sorting a binary string (eg. 100011 to 000111).
This is true more generally when the numbers in the array are bounded. My question is what if the numbers are not bounded?

Is the problem of sorting an array of unbounded numbers still in $\mathsf{TC^0}$?  Is it  complete for a larger class like $\mathsf{NC^1}$?

Suppose you have $n$ numbers $x_1,\ldots,x_n$ of width $m \geq \log n$. Without loss of generality, all numbers are different (add an extra $\log n$ lower-order bits). Two numbers can be compared in AC0, so in AC0 we can compute, for each $x_i$, a binary vector $v$, defined by $v_j = 1$ if $x_j \geq x_i$. In TC0 we can sort $v$ to $w$, and then locate (in AC0) the position $k$ such that $w_k = 1$ while $w_{k-1} = 0$ (where $w_0=0$, $w_{n+1}=1$). Given these values $k$ for each $i \in [n]$, we can compute the sorted array in AC0. In total, we get a TC0 circuit.


Counterexample for Corneil's efficient algorithm for Graph Isomorphism In the paper An Efficient Algorithm for Graph Isomorphism by Corneil and Gotlieb, 1970 a conjecture was stated upon which the stated algorithm relied for solving GI in polynomial time. Namely:

  that the representative graphs exhibit the automorphism partitioning of the
  given graph

Obviously, this conjecture isn't proven until now (otherwise we would know that GI is in P). My question is whether it was already shown to be false and possibly a counter example was given?

Mathon has shown that the conjecture used by Corneil and Gotlieb is false. The first reference states this fact.

1- P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism, Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition, 2001, pp. 188-199.

2- R. Mathon, Sample graphs for isomorphism testing, Congressus Numerantium, 21, pp.
499-517, 1978


FO-uniform AC0 with some predicate My question is about finite model theory/descriptive complexity, so $FO(R)$ will mean "first order over finite binary words, using predicates Rs and a unary predicate P true on the position of the 1 in the word".

I would like to know, are there any caracterisation of $FO(<,R)$ with R any predicate on $\mathbb N^r$ for some r? For example on $FO(<,+)$, or $FO(<,P_2)$ where $P_2$ is the set of power of 2. Especially, it seems to me that it should be equal to $AC^0$ with some uniformity condition, but I can not find any resultat that states this.

Here is what I already know, for some value of $R$.

It is well known that $FO(<,bit)$, the first order logic on words with an order and a bit predicate is equal to $AC^0$-$FO(<,bit)$ uniform. By this it means they both recognise exactly the same languages.  See for example "Descriptive complexity" of Immerman, page 82.
(It is also equal to a lot of other caracterisation, such as $AC^0$-logtime uniform, and constant-time parallel random access machine, but it is not what I am searching for here.)

If we can use arbitrary numerical predicate in our first order logic, then we have $AC^0$ (non uniform), if $C$ is a class of function containing the log-time computable function, then $FO(<,C)$ is equal to $AC^0-C$-uniform (for these two results see Barrington, "Extensions of an Idea of Mc-Naughton", 1993).

Finally $FO(<)$ is the class of star-free language (language that can be defined by a regular expression using no Kleene star), but this give no information in term of circuit complexity.

I am not completely sure what you are looking for, but the following might
be interesting to you:

The idea that restricting numerical predicates in FO-formula corresponds to uniformity conditions is explicitly investigated, for example, in the paper
"FO(<)-uniformity" by Behle and Lange.
The survey "Arithmetic, first-order logic, and counting quantifiers"
by Schweikardt provides i.a. an overview of known results about
the expressive power of different arithmetical predicates


Estimating a percentile among distributed nodes without revealing values I have a fairly unique problem to solve and I am hoping somebody here can give me some insight into how to best tackle it.

Problem: Suppose a list of N numbers is shared among a set of participants in such a way that no single participant actually knows any of the numbers they share. All participants know N (the size of the list of numbers) and the sum of all of the numbers on the list, but nothing more a priori.

By working together, it is possible to compare two shared numbers a and b in such a way that the participants learn whether the statement "a < b" is true, but nothing more. However, this is an extremely expensive thing to do (read: it could take many seconds, perhaps even minutes, to complete a single comparison). See the end of this post for a bit more information on how such a thing is possible.

At the end of the day, the parties wish to output of which indices in the list correspond to the "top K percent" (the K% which is largest) shared numbers in the list. This can of course be done by sorting, or using a "top K" selection algorithm. However, these tend to use an aweful lot of comparisons, which is to be avoided. (These are either O(n log n) or O(n), with fairly large hidden constants.)

Another alternative is to "guess" at a number X for which (1-K)% are smaller than X and K% are larger. Then you can compare each element with X and see how many are larger and how many are smaller. If your guess was wrong, revise it using something like a binary search until you converge on a correct solution. This takes far fewer comparisons if your guess is good.

So, my question is,

  Given only N and the sum, what is the best way to "predict" X?

Of course this will depend on the underlying distribution. For different use-cases the underlying distribution will likely be different but will be known, so I am interested in good solutions for all the common ones (normal, uniform, exponential, perhaps a few others). I would also love to hear suggestions regarding how best to do the "binary-like" search to minimize the number of steps given an assumption about the underlying distribution.

APPENDIX: Each value on the list is shared among participants using Shamir's secret sharing scheme. Suppose there are M participants and the list is of length N. Then, the i-th number on the list is represented by a polynomial $f_i$ of degree M-1 over some finite field F. The constant term of $f_i$ is the number that is shared, all other coefficients are chosen uniformly at random from F. The j-th participant's shares are then $f_i(j)$, $1\leq i\leq N$. Given this share, the participant has no information (in an information-theoretic sense) about the number; in fact, no proper subset of participants can combine knowledge to learn any information about the shared numbers. However, using a sophisticated secure multi-party computation technique, it is possible to determine if one shared value is less than another without revealing any more information. This technique involves all participants cooperating, which is why it is so costly to do and should be done the fewest number of times possible.

You seem to ask two related questions:

“which indices in the list correspond to the top”
“Estimating a percentile”, “a number X for which … K% are larger”

These may need very different numbers of pairwise comparisons.

An other aspect that may have significant impact is what information is shared. Everybody knows the number he received, knows the sum, and the yes/no results of comparisons they have taken part in. However, you also say that “parties wish to output of which indices in the list correspond to the top” thus you suggest that some information about the indices will be shared. Depending on what exactly is shared you may get very different solutions again.


"Largest" class properly contained in PSPACE for a random oracle Green [1] showed that $PP^{PH}$ is properly contained in $PSPACE$ relative to some oracle. Around the same time, in the famous "voting polynomials" paper [2], it was shown that $PP$ is properly contained in $PSPACE$ for a random oracle.

Question

  Is it also true that $PP^{PH}$ is properly contained in $PSPACE$ relative to a random oracle?

Observations

From what I understand, this can be proved by showing that "small" $AC^{0}$ circuits with a MAJORITY gate at the root fail to compute the PARITY function even on a (1/2+small)-fraction of inputs. I found such claim in Theorem 6 of [3]. Does this reasoning make sense? Am I interpreting Klivans' theorem in the right way?
I wrote "largest" class in the title, because I am also interested in classes that have this same property and that are uncomparable with $PP^{PH}$.

Motivations

Nostalgia for 90s research :)
I am looking at similar questions in quantum complexity theory.

References

Frederic Green, An oracle separating $\oplus P$ from $PP^{PH}$, Information Processing Letters, '91
James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich, The expressive power of voting polynomials, STOC '91
Adam Klivans, On the Derandomization of Constant Depth Circuits, RANDOM '01

Yes, because $PP^{PH}=PP$ relative to a random oracle. Follows from Toda-Ogihara


Theoretical guarantees for running times of belief propagation methods? Belief propagation has been shown to be a very powerful method through research in probabilistic graphical models.

However, I don't know anything about BP that's comparable to MCMC methods where we can have fully polynomial randomized approximation schemes (FPRAS) for #P-complete problems.

Could someone point me to some references?

BP and most of its variants are proved to converge on graphs without cycles. When you have cycles they show very strange behavior sometimes. For these cases people have tried different approximations schemes, for example Sherali-Adams, Lovasz-Schrijver, and Lasserre Hierarchies.

See [1] for a comprehensive review of these approximations. Also (Wainwright and Jordan, 2008) includes other class of approximations.

[1] http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf


Is the backup problem NP-complete? Is the following decision problem NP-complete:

  Let $G$ be an undirected graph and $b \le c$
  two integers. Is it possible to
  select for every vertex of $G$ exactly
  $b$ different neighbors such that no
  node is chosen more then $c$ times.

The case $b = 1$ can be solved for any $c$ in polynomial time using maximal matching.

Motivation: Each node wants to place $b$ backups at different neighbors, but each node has only capacity to store $c$ backups.

I think the following is a polynomial-time algorithm based on maximum flow. Let $G(V,E), b, c$ be the input.

Construct a directed bipartite graph $H(L,R,F)$ with $L$ and $R$ being the left and right partitions and $F$ being the directed edges from $L$ to $R$.
Let $|V| = n$. There are $n$ vertices in $L$ and $n$ vertices in $R$.
Each vertex $v \in V$ has a "copy" in $L$ (say $v_l$) and a copy in $R$ (say $v_r$).
If $(u,v) \in E$ add a directed edge from $u_l$ to $v_r$. Each such edge has capacity 1.
Add a "source" node $s$ and add directed edges from $s$ to each vertex in $L$. Each such edge has a capacity $b$.
Add a "sink" node $t$ and add directed edges from each vertex in $R$ to $t$. Each such edge has a capacity $c$.
Find maximum flow from $s$ to $t$.

The given graph $G$ has a solution if and only if the max-flow computed above saturates every edge from $s$ to $L$, i.e., the flow on every edge from $s$ to $L$ is equal to $b$.


Lower bound on the number of "short" paths in a rooted tree with polynomial size Let $T$ be a rooted binary tree. Every path from the root of $T$ to a leaf has length $n$. Every node of $T$ has always a left and a right child node but it is possible that they are the same (So there are always $2^n$ paths possible). The size of $T$ is bounded by $O(poly(n))$. A node with different child nodes is called branching node.

We say that two paths are different iff there is one shared branching node and one path goes to the left child node and the other path goes to the right child node.
It is clear that there is at least one path in $T$ with $O(\log n)$ branching nodes. Otherwise there would be too much nodes in $T$.

Is there a better lower bound on the number of paths with $O(\log n)$ branching nodes if I know there are $\omega(\log n)$ branching nodes in the tree?

The lower bound is $\Omega(\log n)$ paths with $O(\log n)$ branching nodes, if you have at least $\Omega(\log n)$ branching nodes in the tree.

This can be achieved: use a tree which has one long path (length $n$) all of whose nodes are branching nodes, with no other branching nodes in the tree.

Here is a sketch of the lower bound.

First, compactify the tree by contracting any interior node that isn't a branching node. If the original size of the tree was $< n^c$, the new tree must still be $< n^c$, since you've only reduced the number of nodes. Now, the depth of a leaf is the number of branching nodes on the original path to that leaf, and we have a complete binary tree (every node has either degree 2 or 0).

If there are no leaves of depth $\Omega(\log n)$, then the number of paths is one more than the number of branching nodes, which is $\Omega(\log n)$, so we can assume that at least one leaf has depth $\Omega(\log n)$.

Next, recall Kraft's inequality. If the depth of a leaf in a complete binary tree is $d(v)$, then $\Sigma_{v \mathrm{\ leaf}} 2^{-d(v)} = 1$.

Now, we have fewer than $n^c$ leaves. We want to show that we have a lot of them at depth $O(\log n)$. Suppose we eliminate from consideration the ones that are depth at least $\log_2(n^{c+1}) = (c+1) \log_2 n$. This removes at most weight $1/n$ from the sum in Kraft's inequality, so for those leaves $v$ at depth at most $d(v)\leq (c+1) \log_2 n$, we have $\sum_{v\mathrm{\ low \ depth \ leaf}} 2^{-d(v)} > 1-\frac{1}{n}$.  We also have $\sum_{v\mathrm{\ low\ depth\ leaf}} 2^{-d(v)} < 1$ (since at least one leaf has depth too large to be included in this sum).

It's fairly easy to show that to get a sum of numbers $2^{-k}$ strictly between $1$ and $1-\frac{1}{n}$, we need at least $\log_2 n$ of them. This shows that there are $\Omega(\log n)$ paths with $O(\log n)$ branching nodes.


Is there a fine grained relation between LH and AC0? The wikipedia article states that the Logarithmic time hierarchy (LH) is equal to FO-uniform AC0. But since the natural way to think about LH is in terms of its levels (with DLogTime at the zeroth level, NLogTime and coNLogTime at the first level, and the log-time machines with (k-1)-alternations at the k-th level), it is natural to wonder whether there is a fine grained relation between the classes from the individual levels like (coNLogTime) with specific subclasses of AC0.

Here are the definitions that make it work. Fix $d\ge1$:

Let $\Sigma_d\text-\mathrm{TIME}(f(n))$ denote the set of languages recognizable in time $O(f(n))$ by an alternating Turing machine that starts in an existential state, and makes at most $d-1$ alternations. Since we are interested in logarithmic time, we work in a model where we do not have an input tape, but we can access the input by writing on a query tape the index of an input position in binary, and its assumed value, and asking the input oracle if our assumption is correct. Additionally, we require that the ATM makes only one such query, at the very end of the computation, and returns the answer of the oracle as the result of the computation. (In order to make this feasible, we need to stipulate that the machine starts with the input length $n$ written in binary on one of its tapes. A log-time TM can compute the length of its input, but it needs $\Omega(\log n)$ input queries to do that.)
A Boolean formula or circuit is $\Sigma_d$ if it consists of $d$ alternating layers of (unbounded fan-in) conjunctions and disjunctions, the top layer being a disjunction, and a layer of literals (variables and negated variables) at the bottom. A language is in non-uniform $\Sigma_d\text-\mathrm{AC}^0$ if it is computable by a family of polynomial-size $\Sigma_d$ circuits $\{C_n:n\in\mathbb N\}$. A language is in DLOGTIME-uniform $\Sigma_d\text-\mathrm{AC}^0$ if, additionally, we can enumerate the nodes of $C_n$ by numbers of $O(\log n)$ bits in such a way that we can compute the following in (deterministic) time $O(\log n)$:

Given $n$ and $u$, check if $u$ is the output node of $C_n$.
Given $n$ and $u$, find the type ($\land$, $\lor$, variable, negated variable) of node $u$ in $C_n$.
Given $n$, $u$, and $v$, determine if there is a wire from node $v$ to $u$ in $C_n$, or if $u$ denotes variable number $v$ or its negation.

  Proposition: For any $d\ge1$, $\Sigma_d\text-\mathrm{TIME}(\log n)$ equals DLOGTIME-uniform $\Sigma_d\text-\mathrm{AC}^0$.

Note that the definition of DLOGTIME uniformity above refers to more-or-less the standard direct connection language of the circuit. It is not sensitive to minor changes in the definition.

On the other hand, the restriction to input queries only at the end in the definition of $\Sigma_d\text-\mathrm{TIME}(\log n)$ does appear to be significant. I cannot exactly characterize the class without this restriction, but it is somewhere between DLOGTIME-uniform $\Sigma_d\text-\mathrm{AC}^0$ and $\Sigma_{d+\frac12}\text-\mathrm{AC}^0$, where a $\Sigma_{d+\frac12}$-circuit is a $\Sigma_{d+1}$-circuit whose bottom layer only allows connectives of fan-in $O(\log n)$.

The proof of the proposition is fairly straightforward.

On the one hand, a language described by a DLOGTIME-uniform family of $\Sigma_d$ circuits can be evaluated by an ATM in a top-down fashion: in the initial existential state, we guess (and check) the top node of the circuit, which is a disjunction, and nondeterministically choose one of its input conjunction nodes. We switch to a universal state, and co-non-deterministically choose the next node. We proceed this way down the circuit. At the bottom layer of connectives, we (existentially or universally, as appropriate) choose not only the next node, which is a literal, but also its type ($x_v$ or $\neg x_v$). Then we make an input query to find the value of the literal, and return it.

On the other hand,  consider a language computable by a $\Sigma_d\text-\mathrm{TIME}(\log n)$ machine. We may assume that as the machine computes, it records a log of the states it has been in (which in particular tells us if it is in an existential or universal state, how many alternations it went through, and which nondeterministic choices it has taken). Let $C_n$ be the circuit whose nodes are certain configurations of the ATM on inputs of $n$ bits, namely: the initial configuration; the final query configurations; and configurations just after an alternation between existential and universal states. The type of a non-final node is $\lor$ or $\land$ according to if the corresponding configuration is existential or universal. There is a wire from $v$ to $u$ if there is an alternation-free computation path from $u$ to $v$; note that this computation path is uniquely determined by $v$’s log, hence it can be checked in DLOGTIME.


Is parametrized maximum independent clauses problem in FPT? Parametrized maximum independent clauses problem:
Input : A r-CNFSAT formula F having n variables and m clauses, k
Ques  : Does there exists at least k clauses such that they are mutually independent i.e. no variable occurs more than once in all these clauses combined.
Parameter : k
I would like to know whether this problem is in FPT or not. In both situations, an idea to proceed forward will be appreciated.

The problem is known as r-Set Packing:
Instance: A collection $\mathcal{C}$ of subsets of size at most $r$ of a finite set $S$ and an integer $k$.
Parameter: $k$
Question: Is there a subcollection $\mathcal{C'} \subseteq \mathcal{C}$ which consists of at least $k$ mutually disjoint subsets?

For unbounded $r$, the problem is W[1]-hard by an easy reduction from Independent Set (see for example [1]).
However, for constant $r$, the problem becomes fixed parameter tractable (see for example [2]).

[1]: Rodney G. Downey, Michael R. Fellows: Parameterized Complexity. Springer, 1999.
[2]: Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, Sue Whitesides: Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems. Algorithmica 52(2): 167-176 (2008)


Accomplished autodidact theoretical computer scientists While it is very common to see successful autodidact musicians, painters, authors and architects - I am not familiar with any famous autodidacts in the field of TCS.
Are there any examples of an accomplished autodidact theoretical computer scientist (i.e., someone who published a significant paper, without ever going to grad school) ?

In addition to some of the great people listed in the comments, Gregory Chaitin independently developed much of Kolmogorov complexity while he was a highschool student in New York city.


What is the smallest class of reductions under which there is a $\mathsf{P}$-complete problem? It is common to define $P$-completeness with respect to log-space many-one reductions.

I am looking for a complexity class $C \subseteq \mathsf{L}$ such that
there are $\mathsf{P}$-complete problems w.r.t. many-one $C$-reductions.

  What is the smallest known many-one reduction class $C$
  such that HornSAT is complete for $\mathsf{P}$ under $C$-reductions?

The question was originally posted on CS with no answer.

It is easy to show that the Circuit Value Problem is complete for $\mathsf{P}$
under $\mathsf{AC^0}$ reductions (see  András's comment below).

For an easier example consider
$$A = \{\langle M,x,y\rangle \mid \text{$M$ accepts $x$ in $|y|$ steps} \}$$

If a class of reductions $C$ contains constant functions, pairing of strings, and functions where the size of their output can bound any polynomial;
then $A$ is complete for $\mathsf{P}$ w.r.t. $C$.


Are a few hundred reduction steps too many to get the normal form of Y fac ⌜3⌝? As I have been teaching the basis of λ-calculus lately, I have implemented a simple λ-calculus evaluator in Common Lisp. When I ask the normal form of Y fac 3 in normal-order reduction, it takes 619 steps, which seemed a bit much.

Of course, each time I did similar reductions on paper, I never used the untyped λ-calculus, but added numbers and functions operating on them. In this case, fac is defined as such:

fac = λfac.λn.if (= n 0) 1 (* n (fac (- n 1)))

In this case, considering =, * and - as currying functions, it only take approximately 50 steps to get Y fac 3 to its normal form 6.

But in my evaluator, I used the following:

true = λx.λy.x
false = λx.λy.y
⌜0⌝ = λf.λx.x
succ = λn.λf.λx.f n f x
⌜n+1⌝ = succ ⌜n⌝
zero? = λn.n (λx.false) true
mult = λm.λn.λf.m (n f)
pred = λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)
fac = λfac.λn.(zero? n) ⌜1⌝ (* n (fac (pred n)))
Y = λf.(λf.λx.f (x x)) f ((λf.λx.f (x x)) f)

In 619 steps, I get from Y fac ⌜3⌝ to the normal form of ⌜6⌝, namely λf.λx.f (f (f (f (f (f x))))).

From a quick skimming of the many steps, I guess it's the definition of pred that warrants such a long reduction, but I still wonder if it just may be a big nasty bug in my implementation...

EDIT: I initially asked about a thousand steps, some of a which were indeed caused a incorrect implementation of the normal order, so I got down to 2/3 of the initial number of steps. As commented below, with my current implementation, switching from Church to Peano arithmetic actually increases the number of steps…

Church coding is really bad if you want to use pred.
I would advise you to use some more efficient coding in Peano style:

// arithmetics

: p_zero = λs.λz.z
: p_one = λs.λz.s p_zero
: p_succ = λn.λs.λz.s n
: p_null = λn.n (λx. ff) tt
: p_pred = λn.n (λp.p) p_zero
: p_plus = μ!f.λn.λm.n (λp. p_succ (!f p m)) m
: p_subs = μ!f.λn.λm.n (λp. p_pred (!f p m)) m
: p_eq = μ!f.λm.λn. m (λp. n (λq. !f p q) ff) (n (λx.ff) tt)
: p_mult = μ!f.λm.λn. m (λp. p_plus n (!f p n)) p_zero
: p_exp = μ!f.λm.λn. m (λp. p_mult n (!f p n)) p_one
: p_even = μ!f.λm. m (λp. not (!f p)) tt

// numbers

: p_0 = λs.λz.z
: p_1 = λs.λz.s p_0
: p_2 = λs.λz.s p_1
: p_3 = λs.λz.s p_2
...

This is some code taken from one of my old libraries, and μ!f. … was just an optimized construction for Y (λf. …). (And tt, ff, not are booleans.)

I'm not really sure you would obtain better results for fac though.


Natural NP-complete problems with "large" witnesses The question on cstheory "What is NP restricted to linear size witnesses?" asks about the class NP restricted to linear size $O(n)$ witnesses, but

  Are there natural NP-complete problems in which (yes) instances
  of size $n$ require witnesses of size greater than $n$?

Clearly we can build artificial problems like:

$L = \{ 1^nw \mid w \text{ encodes a satisfiable formula and } |w|=n \}$
$L = \{ \varphi \mid \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$

After a quick look at G&J, every natural NPC problem seems to have witnesses (strictly) smaller than $n$.

  Is there a "reason/explanation" for it ?

How about the edge coloring number in a dense graph (aka Chromatic index)? You are given the adjacency matrix of an $n$ vertex graph ($n^2$ bit input), but the natural witness describing the coloring has size $n^2\log n$. Of course, there might be shorter proofs for class 1 graphs in Vizing's theorem.

See also this possibly related question


Hierarchical sorting strategies for pattern-avoiding permutations? For a class $\mathcal{C}$ of permutations, we cannot expect to sort the permutations of $\mathcal{C}$ with less than $O(\log |\mathcal{C}_n|)$ comparisons, where by convention $\mathcal{C}_n := \mathcal{C} \cap S_n$.

In particular, when $\mathcal{C}$ is closed by subpatterns, it follows by Marcus-Tardos theorem (refined by J. Fox) that $|\mathcal{C}_n| \leq C^n$ where $C$ is the Stanley-Wilf constant of $\mathcal{C}$. This leads to the following question: is it possible to sort such a class using at most $O(n \log C)$ comparisons? This question is a strengthening of Question 1 in the paper 'Fast Sorting and Pattern-avoiding Permutations' by D. Arthur.

It seems possible to represent such a sorting strategy by a binary tree which would essentially mimic an 'unbalanced' merge-sort algorithm. Here is the idea: given a permutation $\pi$, we would look for a tree $T_{\pi}$ leaf-labeled by the points of $\pi$, such that for each node $u$ of $T_{\pi}$ the 'overlap' between the two child subtrees would be $O(\log C)$ (either worst-case or on average). However I suspect that a more involved structure is necessary to solve this problem; should it admit a positive solution.

Another approach is enumerative encoding. Consider for example $231$-avoiding permutations, of which there are $C_n$. The number of $231$-avoiding permutations with $\pi^{-1}(n) = i$ is $C_{i-1} C_{n-i}$, and this gives a recursive algorithm for encoding $231$-avoiding permutations: divide the interval $[0,C_n)$ into $n$ intervals $I_1,\ldots,I_n$ of lengths $C_i C_{n-i-1}$ for $i=1,\ldots,n$ arbitrarily. Given a permutation with $\pi^{-1}(n) = i$, notice that $\pi|_{1,\ldots,i-1}$ is a $231$-avoiding permutation of $\{1,\ldots,i-1\}$, and $\pi|_{i+1,\ldots,n}$ is a $231$-avoiding permutation of $\{i+1,\ldots,n\}$. Recursively encode the first part in $[0,C_{i-1})$ and the second part in $[0,C_{n-i})$, and put both encodings together to encode $\pi$ in $I_i$.

For any other $\tau \in S_3$, $\tau$-avoiding permutations are bijectively related to $231$-avoiding permutations, through taking the inverse, complementing the elements, reversing, or the Simion–Schmidt bijection between $132$- and $123$-avoiding permutations. So this encoding applies to all patterns of length $3$.


Rabin–Karp vs Karp–Rabin The wise other editors at Wikipedia have declined my request to move the Wikipedia article on the Rabin–Karp algorithm to what I think it should be called, the Karp–Rabin algorithm, on the basis that the Rabin–Karp name is used more often (false, if one goes by Google scholar's numbers), or that it sounds better out loud (really?). The original publication name order was Karp and Rabin, alphabetically as it usually is for theory papers, which is why I requested the move.

One major proponent of the Rabin–Karp name ordering is the Cormen–Leiserson–Rivest–Stein Introduction to Algorithms textbook. The Wikipedia outcome is unlikely to change barring significant new evidence one way or another, and it seems unlikely that either Rabin or Karp cares about $\epsilon$ more credit, but now I'm curious: Do any readers remember the history of this and have any explanation why CLRS (or anyone else) chose the Rabin–Karp name order?

I've asked Dick personally out of curiosity a few years back. He said that as far as he knows Rabin-Karp was a random switch many years after the paper was first published. He also indicated that it is his understanding that Michael would say the same thing if asked, since at some point they had talked about it.


Statistical distance between uniform and biased coin Let $U$ be the uniform distribution over $n$ bits, and let $D$ be the distribution over $n$ bits where the bits are independent and each bit is $1$ with probability $1/2-\epsilon$.  Is it true that the statistical distance between $D$ and $U$ is $\Omega(\epsilon \sqrt{n})$, when $n \le 1/\epsilon^2$?

Denote the random bits by $x_1,\dots, x_n$. By definition, the statistical distance between $U$ and $D$ is at least $\Pr_U\left(\sum x_i \geq t\right) - \Pr_D\left(\sum x_i \geq t\right)$ for every $t$. We choose $t = n/2 + \sqrt{n}$.

Note that $\Pr_U\left(\sum x_i \geq t\right) \geq c_1$ for some absolute constant $c_1 > 0$. If $\Pr_D\left(\sum x_i \geq t\right) \leq c_1/2$, then the statistical distance is at least $c_1/2$, and we are done. So we assume below that $\Pr_D\left(\sum x_i \geq t\right) \geq c_1/2$.

Let $f(s) = \Pr\left(\sum x_i \geq t\right)$ for i.i.d. Bernoulli random variables $x_1,\dots, x_n$ with $\Pr(x_i = 1) = 1/2-s$. Our goal is to prove that $f(0) - f(\varepsilon) = \Omega(\varepsilon \sqrt{n})$. By the mean value theorem,
$$f(0) - f(\varepsilon) = -\varepsilon f'(\xi),$$
for some $\xi \in (0, \varepsilon)$. Now, we will prove that $-f'(\xi) \geq \Omega(\sqrt{n})$; that will imply that the desired statistical distance is at least $\Omega(\sqrt{n} \varepsilon)$, as required.

Write,
$$f(\xi) = \sum_{k\geq t} \binom{n}{k} \left(\frac12 - \xi\right)^k \left(\frac12+\xi\right)^{n-k},$$
and
$$\begin{align}
f'(\xi) &= \sum_{k\geq t} \binom{n}{k} \left(-k \left(\frac12 - \xi\right)^{k-1} \left(\frac12+\xi\right)^{n-k} + (n-k) \left(\frac12 - \xi\right)^{k} \left(\frac12+\xi\right)^{n-k-1}\right) \\
&= -\sum_{k\geq t} \binom{n}{k} \left(\frac12 - \xi\right)^{k} \left(\frac12+\xi\right)^{n-k}\frac{k/2 + k\xi - (n-k)/2 + (n-k)\xi}{(1/2 - \xi)(1/2 +\xi)}.
\end{align}$$
Note that
$$\frac{k/2 + k\xi - (n-k)/2 + (n-k)\xi}{\left(1/2 - \xi\right)\left(1/2 +\xi\right)} =
\frac{(2k-n)/2 + n\xi}{(1/2 - \xi)(1/2 +\xi)} \geq 2(2t - n)  = 4\sqrt{n}.$$
Thus,
$$\begin{align}-f'(\xi) &\geq 4\sqrt{n} \sum_{k\geq t} \binom{n}{k} \left(\frac12 - \xi\right)^{k} \left(\frac12+\xi\right)^{n-k} \\&= 4\sqrt{n} f(\xi) \geq 4\sqrt{n} f(\varepsilon) \geq 4\sqrt{n}\cdot (c_1/2).\end{align}$$
Here, we used the assumption that $f(\varepsilon) = \Pr_D(x_1+\dots+x_n \geq t) \geq c_1/2$. We showed that $-f'(\xi) = \Omega(\sqrt{n})$.


How to cite Babai's new graph isomorphism result? Recently, Babai has published a paper on STOC 2016 claiming that graph isomorphism can be solved in quasipolynomial time.

In the beginning of 2017, Babai retracted the quasipolynomial claim due to some serious mistakes found by Harald Helfgott. As explained by Babai himself, this flaw makes the improvement more modest in terms of running time.

About 5 days after retracting the quasi-polynomial claim, Babai posted another update in his homepage arguing that he had fixed the flaw in the proof, restoring in this way the quasi-polynomial running time.

I have to say that after this fast change on the status of the correctness of the proof I would normally completely ignore the new paper until it was published in a well respected journal.

But since Babai is Babai, most of the community is taking his's word for granted, at least publicly, even though the new version of the paper with all corrections implemented is not even available. Note that even great people make mistakes and there is a non-negligible chance that the new fix also has a flaw and so on.

So now, how should I cite the new result?

Cite the STOC paper claiming the quasipolynomial upperbound.
Cite the STOC paper explaining that it has a serious flaw and that the real running time improves the previous subexponential lower bound.
Cite the STOC paper saying that it had a flaw that was fixed by Babai.
Do not cite at all, and state the old upper bound of $2^{O(\sqrt{n})}$ as the current established upper bound.

First off, I would discourage submitting for publication an unconditional paper which depends on the quasi-polynomial result, if that's what you want the citation for. Rephrase the result as conditional upon the the existence of a quasi-polynomial GI algorithm and state in a footnote that Babai may have proven this but that the paper is not publicly available. In this case, no citation is necessary because you don't need the result for the paper.

In any other context, I don't think it's particularly necessary to cite an available paper - citing his website is fine. It depends a little on what you are writing, but I would recommend asserting something along the lines of "it is widely believed that GI is solvable in quasipolynomial time and a proof of this has been announced by Laszlo Babai [citation to the webpage where he makes the claim]."

One notable advantage of citing his online claim is that his website contains both his own words as to the current claim and a link to his preprint.