Realizability theory: difference in power between Lambda calculus and Turing Machines I have three related subquestions, which are highlighted by bullet points below (no, they could not be split, if you are wondering).
Andrej Bauer wrote, here, that some functions are realizable through a Turing machine, but not through lambda-calculus. A key step of his reasoning is:

  However, if we use the lambda
  calculus, then [the program] c is supposed to
  compute a numeral representing a
  Turing machine out of a lambda term
  representing a function f. This cannot
  be done (I can explain why, if you ask
  it as a separate question).

I would like to see an explanation/informal proof.

I don't see how to apply Rice's theorem here; it would apply to the problem "are this turing machine T and this lambda-term L equivalent?", because applying this predicate to equivalent terms gives the same result. However, the required function might compute different, but equivalent, TMs for different, but equivalent, lambda-terms.

Moreover, if the problem is with introspection of a lambda-term, I think that passing a Gödel encoding of a lambda-term would be also acceptable, wouldn't it?

On the one hand, given that his example involves computing, in the lambda calculus, the number of steps needed by a Turing Machine to complete a given task, I'm not very surprised.

But since here lambda-calculus can't solve a Turing-machine-related problem, I wonder whether one can define a similar problem for lambda-calculus and prove it unsolvable for Turing machines, or there is actually a difference in power in favor of Turing Machines (which would surprise me).

John Longley has a very extensive survey article discussing the issues involved, "Notions of Computability at Higher Type".

The basic idea is that the Church-Turing thesis is only about functions from $\mathbb{N} \to \mathbb{N}$ -- and there's more to computation than that! In particular, when we write programs, we make use of functions of higher type (such as $(\mathbb{N} \to \mathbb{N}) \to \mathbb{N}$).

In order to fully define a model of higher type computation, we need to specify the calling convention for functions, in order to allow one function to call another function it receives as an argument. In lambda calculus, the standard calling convention is that we represent functions by lambda-terms, and the only thing you can do with a lambda in the lambda calculus is to apply it. In typical encodings with Turing machines, we pass functions as arguments by fixing a particular Godel encoding, and then strings representing the index of the machine you want to pass as an argument.

The difference in encoding means that you can analyze the syntax of the argument with a TM-style encoding, and you cannot with a standard lambda-calculus representation. So if you receive a lambda-term for a function of type $\mathbb{N} \to \mathbb{N}$, you can only test its behavior by passing it particular $n$'s -- you can't analyze the structure of the term in any way. This is just not enough information to figure out the code of the lambda term.

One thing worth noting is that with higher types, if a language is less expressive at one order, it is more expressive one order up, because functions are contravariant. So similarly there are functions you can write in LC that you can't with a TM-style encoding (because they rely on the fact that you can pass functional arguments and know that the receiver can't look inside the function you give it).

EDIT: Here's an example of a function definable in PCF, but not in TM+Goedel encodings. I'll declare the isAlwaysTrue function

 isAlwaysTrue : ((unit → bool) → bool) → bool

which should return true if its argument ignores its argument and always returns true, should return false if its argument returns false on any inputs, and goes into a loop if its argument goes into a loop on any inputs. We can define this function pretty easily, as follows:

isAlwaysTrue p = p (λ(). true) ∧ p (λ(). false) ∧ p (λ(). ⊥)

where ⊥ is the looping computation and ∧ is the and operator on booleans. This works because there are only three inhabitants of unit → bool in PCF, and so we can exhaustively enumerate them. However, in a TM+Goedel-encoding style model, p could test how long its argument takes to return an answer, and return different answers based on that. So the implementation of isAlwaysTrue with TMs would fail to meet the spec.


Maximum weight "fair" matching I'm interested in a variant of the maximum weight matching in a graph, which I call "Maximum Fair Matching".

Assume that the graph is full (i.e. $E=V\times V$), has even number of vertices, and that the weight is given by a profit function $p:{V\choose 2}\to \mathbb N$. Given a matching $M$, denote by $M(v)$ the profit of the edge $v$ is matched with.

A matching $M$ is a fair matching iff, for any two vertices $u,v\in V$:
$$(\forall w\in V:\ \  p(\{w,v\})\geq p(\{w,u\}))\to M(v)\geq M(u)$$

That is, if for any vertex $w\in V$, matching $w$ to a vertex $v$ gives higher profit than matching it to a vertex $u$, a fair matching must suffice $M(v)\geq M(u)$.

  Can we find a maximum weight fair matching efficiently?

An interesting case is when the graph is bipartite and the fairness only applies to one side, that is assume that $G=(L\cup R,L\times R)$, and we are given a profit function $p:L\times R\to \mathbb N$.

A Fair Bipartite Matching is a matching in $G$ such that for any two vertices $u,v\in L$:
$$(\forall w\in R:\ \  p(\{v,w\})\geq p(\{u,w\}))\to M(v)\geq M(u)$$

  How fast can we find a maximum weight fair bipartite matching?

The motivation for this problem comes from the bipartite special case.
Assume you have $n$ workers and $m$ tasks, and worker $i$ can produce $p_{i,j}$ profit from work $j$. To problem here is to design a reasonable (in a sense workers will not feel "ripped-off''), while maximizing the total payoffs. (There is a tradeoff here between the power of the assignment mechanism and the social benefit).

If we define the social-welfare (or the factory profit) of the assignment of workers to jobs as the sum of profits.

Looking at different scenarios for the power of the job assigner, we get the following results:

If we are allowed to assign any worker to any job, we can optimize the factory efficiently (just find a maximal-weight matching).
If every worker chooses a task on his own, assuming that his work will be selected (only a single work can be selected for each job) should he be the most qualified worker that chose the task, workers will converge into the ''greedy'' equilibrium. The reason is that the worker that could earn the most ($i=\mbox{argmax}_i \max_j p_{i,j}$) will choose the most profitable job, and so on. By the approximation rate of the greedy algorithm for matching, this should give a 2-approximation of the maximal social-welfare possible.

I'm looking for something in-between. Let's assume we could assign workers to jobs, but have to promise them that no "less-qualified" worker earns more than them.

  How can we find a maximal weight matching promising "fairness" to employees efficiently?

I believe "maximum weight fair bipartite matching" as you've defined it is NP-hard.  Even more, determining the existence of a fair bipartite matching is NP-hard.

Before I give a proof sketch, for intuition, consider the following small instance.  Take $G'=(L, R, E'=L\times R)$ where $L=\{a,b\}$, $R=\{c,d,e,f\}$.  Take $p$ such that $p(u,w) = 0$ for $u\in L$ and $w\in\{c,d\}$, while $p(u,w) = 1$ for $u\in L$ and $w\in\{e,f\}$.  Then $a$ and $b$ are equivalent, in the sense that $p(a, w) = p(b, w)$ for all $w\in R$, so any fair matching must give $a$ and $b$ the same profit.  Hence, the only fair matchings either match $a$ and $b$ to $c$ and $d$, or they match $a$ and $b$ to $e$ and $f$.  Using this kind of gadget, we can force coordination of the edges in the matching.  This is the basis of the reduction.

Here's an attempt at a proof.  It's a bit involved. Probably there are some mistakes, but hopefully any mistakes can be fixed.

Lemma 1. Given $G'=(L, R, E'=L\times R)$ and $p:E'\rightarrow\mathbb{R}_+$ as described in the problem, determining whether $G'$ contains a fair matching is NP-hard.

Proof sketch. The proof is by reduction from Independent Set in cubic graphs.  Let $(G=(V,E),k)$ be a given instance of Independent Set where $G'$ is a cubic graph (every vertex has degree 3).  We describe how to construct a graph $G'=(L, R, E'=L\times R)$ and profit function $p:E'\rightarrow\mathbb{R}_+$ such that $G'$ has a fair bipartite matching if and only if $G$ has an independent set of size $k$.

The vertices in $L$ will come in pairs, called partners.
Likewise for the vertices in $R$.
For each vertex $v\in L\cup R$, we let $v'$ denote the partner of $v$.
Each vertex $\ell\in L$ and its partner $\ell'\in L$ will be equivalent, meaning that we will make
$$p(\ell, r) = p(\ell', r) \text{ for all } r\in R.$$
Consequently, any fair matching must assign the same profit to $\ell$ and $\ell'$.
In what follows, we use $\pi(\ell, r)$
to denote the value of $p(\ell,r) = p(\ell', r)$.

Further, for each pair $\ell$ in $L$,
and each pair of partners $r, r'$ in $R$,
either we make
$$\pi(\ell, r) = \pi(\ell, r')$$
or we make
$$\pi(\ell, r) \ne \pi(\ell, r').$$
In the former case, we say we allow $\ell$ and $\ell'$ to be matched to $r$ and $r'$
(because doing so would assign the same profit to $\ell$ and $\ell'$,
as required).
In the latter case, we say we prevent $\ell$ and $\ell'$ from being (both) matched to $r$ and $r'$
(because doing so would not assign the same profit to $\ell$ and $\ell'$).

As the given graph $G=(V,E)$ is cubic, it satisfies $3|V|=2|E|$, and any independent set $I$ of size $k$ in $G$ is incident to exactly $3k$ edges.  Assume for ease of notation that $V=\{1,2,\ldots,n\}$.

For each edge $\{i, j\}\in E$, do the following.

Add a pair of partner vertices $r(\{i,j\}), r'(\{i,j\})$ to $R$.
For endpoint $i$, add a pair of partner vertices $\ell(i,j),
    \ell'(i,j)$ to $L$. Set $$\pi(\ell(i,j), r(\{i,j\})) =
    \pi(\ell(i,j), r'(\{i,j\}))= i,$$ allowing $\ell(i,j)$ and
$\ell'(i,j)$ to be matched to $r(\{i,j\})$ and $r'(\{i,j\})$.
Symmetrically, for the other endpoint $j$: add another pair of
partner vertices $\ell(j,i), \ell'(j,i)$ to $L$, and set
$$\pi(\ell(j,i), r(\{i,j\}) = \pi(\ell(j,i), r'(\{i,j\}))= j,$$
allowing $\ell(j,i)$ and $\ell'(j,i)$ to be matched to $r(\{i,j\})$
and $r'(\{i,j\})$.

For every $\ell\in L$ and $r\in R$ added so far,
if the pair $\ell, \ell'$ is not explicitly allowed (above)
to be matched to $r, r'$, then prevent the match
by assigning $\pi(\ell, r)$ and $\pi(\ell, r')$ each some unique number.

Next, add $3(|V|-k)$ pairs of filler vertices to $R$.
For each filler vertex $r$ and each $\ell(i,j)\in L$,
set $\pi(\ell(i,j), r) = 0$.

Finally, add two vertices $L_0$ and $L'_0$ (partners) to $L$, along with a two vertices $R_0$ and $R'_0$ (also partners) to $R$.
Set $\pi(L_0, R_0) = \pi(L_0, R'_0) = 1$, allowing $L_0$ and $L'_0$ to be matched to $R_0$ and $R'_0$.  For every other vertex $r\in R$, set $\pi(L_0, r)$ to some unique number.  (Hence, any fair matching must match $L_0$ and $L'_0$ to $R_0$ and $R'_0$.)
For every $i\in V$, for every incident edge $\{i,j\}\in E$,
set $\pi(\ell(i,j), R_0) = i$ and $\pi(\ell(i,j), R'_0) = |V|-i+1$.

That completes the reduction.  To finish, we prove it is correct.

First consider for what pairs of vertices $\ell(i,j),\ell(i',j')\in L$
the latter dominates the former, that is,
$$(\forall r\in R)~\pi(\ell(i,j),r) \le \pi(\ell(i',j'), r).$$

Considering the profits assigned to edges incident to $R_0$ and $R'_0$,
this condition can only be met if $i=i'$, and, inspecting the definition of $\pi$ for the remaining edges, the condition $i=i'$ is sufficient.  Hence a matching is fair if and only if it assigns $L_0$ and $L'_0$ to $R_0$ and $R'_0$, and also, for each $i\in V$, gives the same profit to all vertices in
$$N(i) = \{\ell(i,j) : \{i,j\}\in E\} \cup \{\ell'(i,j) : \{i,j\}\in E\}.$$

First, assume that $G$ has an independent set $I$ of size $k$.  Obtain a fair matching for $G'$ from $I$ as follows.

Match $L_0$ and $L'_0$ to $R_0$ and $R'_0$.

For each vertex $i\in I$,
let $\{i,j_1\}, \{i,j_2\}, \{i,j_3\}$ be its three incident edges.
For each edge $\{i, j_h\}$,
match vertex $\ell(i,j_h)$ and its partner $\ell'(i,j_h)$
to $r(\{i,j_h\})$ and $r'(\{i, j_h\})$.
This gives all vertices in $N(i)$ profit $i$.

For each of the $|V|-k$ vertices $i\in V\setminus I$,
for each of the three edges $\{i,j\}$ incident to $i$,
match $\ell(i,j)$ and its partner $\ell'(i,j)$
to some unique pair of filler vertices $r$ and its partner $r'$.
This gives all vertices in $N(i)$ profit $0$.

Hence, this matching is fair.

Next, assume that $G'$ has a fair matching $M$.

$M$ must match $L_0$ and $L'_0$ to $R_0$ and $R'_0$.
For each $i\in V$, the matching must give each of the vertices in $N(i)$
the same profit.  For each $\ell(i,j)\in N(i)$, its partner $\ell'(i,j)$ is also in $N(i)$.  So, by inspection of the reduction,
the profit of each such vertex must be either $i$
(in which case all six vertices in $N(i)$ are matched
to vertices $r(\{i,j\})$ and their partners)
or zero
(in which case all six vertices in $N(i)$ are matched
to filler vertices in $R$).
Let $I$ be the set of vertices for which the former case holds.
For each edge $\{i,j\}$, the vertex $r(\{i,j\})$,
and its partner, are each matched to one vertex.
It follows that $I$ is an independent set.
Since the number of filler vertices is $6(|V|-k)$,
the size of $I$ must be at least $k$.

QED (?)

I think it's basically correct, if a bit convoluted.  Let me know if you see any mistakes, or a way to simplify the proof.

The reduction above assumes it's okay to take $|R|>|L|$.
If that's undesirable, then I'd guess we can pad $L$
with $|R|-|L|$ filler vertices, assigning profit 0
to all of their edges except the edges to $R_0$ and $R'_0$.
We can assign profits to the latter edges to ensure
the filler vertices are not dominated by (nor dominate)
any other vertex.


How to mechanically derive the recursor of a type from its constructors? In Martin-Löf Dependent Type Theory a type is commonly prescribed by how to construct its canonical terms and how to show that its canonical terms are definitionally equal. This means that the definition of a type contains no explicit information at all about its recursor / induction principle and how it should behave.

Am I right to suppose that, given the constructors of a type,
we already have an implicit characterization of its recursor / induction principle – in the sense that there exists an algorithm that mechanically derives the recursor / induction principle of this type?

If this is correct I would like to know:

How such an algorithm look like? (References are fine)
How is this all related to Gentzen’s inversion principles?

Section 5.6 of the HoTT book discusses the general schema for inductive types, including how to get the corresponding induction principle.

In short, yes there is a general way to derive the elimination principle from the signature (the description of the construcotrs), and it is of course algorithmic. Coq does it, for instance, when you define an Inductive foo and it generates the eliminator foo_rect.


Is Asymptotic PTAS $\subseteq$ APX? The definition of asymptotic polynomial-time approximation scheme (Asymptotic PTAS) is defined as follows:

  A minimization problem $\Pi$ is Asymptotic PTAS if for all $\epsilon$ there exists an algorithm $A_\epsilon$ and $N_\epsilon > 0$, such that $A_\epsilon(I) \leq (1+\epsilon)OPT$ for $OPT(I) \geq N_\epsilon$.

I have two questions:

Is Asymptotic PTAS contained in APX?
If problem $\Pi$ is APX-Hard, does it imply that $\Pi$ is not Asymptotic PTAS (suppose $P \neq NP$)?

I know above are true if we replace Asymptotic PTAS with PTAS (which are common-sense now). But I can't figure out how the definitions of Asymptotic PTAS and APX give answers to above questions..

Both statements seem to be false.

Consider all Boolean formulas $\Phi$ in 3-CNF. The objective value of an $n$-variable formula $\Phi$ is $1/n$ if $\Phi$ is satisfiable, and is $1$ if $\Phi$ is not satisfiable. The corresponding minimization problem has an asymptotic PTAS (it is easy to come within an additive $+1$), but is not in APX (as this would allow you to solve 3-SAT).
Consider all undirected graphs. The objective value of a graph $G$ is its edge-chromatic number $\chi'(G)$. Holyer has proved that deciding $\chi'(G)=3$ is NP-hard. The corresponding minimization problem is APX-hard (there is no approximation algorithm with worst case ratio better than $4/3$), but the problem has an asymptotic PTAS (Vizing's theorem tells us that $\chi'(G)$ is between the max-degree and the max-degree plus 1).


Random grid point in a d-dimensional ball I would like to know if there is any standard algorithm to generate
a random grid point inside a d-dimensional ball with a given radius r.

Thanks

Bin Fu

Let $B$ be the ball you want to sample in. Let $B'$ be the ball centered at the same point, but larger in radius by $\sqrt{d}$. Sample a random point in $B'$ Round off to the nearest integer point. Now, if this integer point is in $B$, accept it. Otherwise, discard it and try again.

This works because every point of the original ball is contained in a unit cube in ball $B'$.

When will this be efficient? You want the ball of $r+ \sqrt{d}$ to be not too much larger than the ball of radius $r$. The ratio of these distances is

$$ \left(\frac{r+\sqrt{d}}{r}\right)^d = \left(1 + \frac{\sqrt{d}}{r}\right)^d \leq \exp\left({\frac{d^{3/2}}{r}}\right).$$

So it works well if $r > d^{3/2}$.

How do you find a random point in $B'$? Thomas's answer give an algorithm for this.

If $r < d^{3/2}$, use the Metropolis algorithm. Start with a point $P$ in the ball—the lattice point closest to the center is easiest. Now, repeatedly perform the following steps.

Choose a random coordinate.
Keeping the remaining coordinates fixed, compute the lowest and highest integer values for this coordinate that are still in the ball.
Pick a random value $v$ for this coordinate, and set this coordinate to $v$ in $P$.

This is guaranteed to converge, and there are theorems that will tell you how quickly it will converge ... I am fairly sure that this case is one that converges in polynomial time.


Is it possible to convert a Max heap to a Min heap in place? I was just wondering if this was possible?

Surely there maybe some naive methods of doing so, but I was just wondering if someone can suggest efficient ways to do so.

You can just ignore that you have a max heap and build your min heap from it. O(n) time
complexity. No need for additional array.


Place of tree-adjoining grammars in the hierarchy of tree grammars As tree-adjoining grammars operate with trees, I suppose they can be considered as a kind of tree grammars. If this assumption is correct, I'm wondering: where should we place them in the tree grammar hierarchy?

By the tree grammar hierarchy I mean one which is similar to the Chomsky hierarchy of word grammars, e.g. as on this figure taken from

  Matsuda K., Mu SC., Hu Z., Takeichi M. (2010) A Grammar-Based Approach
  to Invertible Programs. In: Gordon A.D. (eds) Programming Languages
  and Systems. ESOP 2010. Lecture Notes in Computer Science, vol 6012.
  Springer, Berlin, Heidelberg

Actually I've found the answer. Here is quote from unpublished work (lecture notes?) of M. Kanazawa:

  The class of tree languages of tree-adjoining grammars is included in
  the class of tree languages generated by monadic simple context-free
  tree grammars.


Class of languages accepted by Python RegEx? Python / Java / Perl / Ruby / etc. extend regular expressions to permit
look-ahead and look-behind, e.g.,
LookAround:

(?=...)
(?<=...)
(?!...)
(?<!...)

I would appreciate a formal definition of the languages accepted by these
modern "regex" modules. They don't reach context-free, do they? What is the superset of regular languages achieved by these recursive-backtracking additions
to regular languages?

I think the answer is "it's complicated", and they probably do not recognize a definite level in the Chomsky hierarchy

Lookaround in regular expressions does not allow them to recognize non-regular languages. This is difficult to see in the standard automata formalism, but this paper describes using Brzozowski's more intuitive "derivative" formalism, which allows defining "extended regular expressions" affording complementation $\neg r$ and intersection $r \& s$. The set of regular languages is also closed under these operations, and looaround operations can be defined in terms of them. For example, negative lookahead $r(?!s)p$ can be written as $r(p\&\neg (s.*))$

This post describes the power of "perl compatible regular expressions" (PCREs). They can recognize at least the context free languages and more. However, Python does not use full PCREs, and in particular lacks the DEFINE keyword, which the author used to prove it can recognize all context-free languages. (The proof is basically embedding BNF-style grammar productions into a PCRE.)

I'm not aware of a way of embedding BNF-style productions into python regular expressions, so it's unclear whether python regexes can recognize all CFLs. They can also clearly recognize non-regular languages like the collection of strings on the alphabet $\{a\}$ which have a composite length r'^(aa+)(\1)+$', which is not even context-free.


Can neural networks be used to devise algorithms? After the newer and newer successes of neural networks in playing board games, one feels that the next goal we set could be something more useful than beating humans in Starcraft. More precisely, I wondered whether

  Can neural networks be trained to solve classic algorithmic problems?

Here I mean that for example the network would get an input graph $G$ with weighted edges, and two vertices $s$ and $t$ specified, and we asked it to find a shortest $st$ path as fast as possible.
Then I guess the neural network would discover and train itself to use Dijkstra or something similar.

On one hand, we know that the computational power of neural networks is $TC^0$.
On the other, I don't know if this is necessarily related to my question.
Even so, for most problems we don't know whether they can be solved in $TC^0$ or not.
Seeing whether a neural network can train itself, might be a good indicator whether there's a fast algorithm or not.
For example, if neural networks can't train themselves to solve SAT fast, then that makes it (even more) likely that $NP\not\subset TC^0$.
I wonder what a neural network would do with GRAPHISOMORPHISM or FACTORIZATION.

Of course, extracting the algorithm is a whole different question.
I suspect experts know how to do that, but discussing it is not the topic of this question.

Added two days later: After seeing the answers, let me specify that if you answer in the negative, then I would like to know

  Why is playing chess easier than Dijkstra or Graphisomorphism?

According to this blog By Reza Zadeh, training a neural network to produce correct output even for just two-thirds of the training examples is computationally hard:

Indeed, in 1988 J. Stephen Judd shows the following problem to be NP-hard:
Given a general neural network and a set of training examples, does there exist a set of edge weights for the network so that the network produces the correct output for all the training examples?
Judd also shows that the problem remains NP-hard even if it only requires a network to produce the correct output for just two-thirds of the training examples, which implies that even approximately training a neural network is intrinsically difficult in the worst case. In 1993, Blum and Rivest make the news worse: even a simple network with just two layers and three nodes is NP-hard to train!


NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs? It is well known that the Hamiltonian cycle problem is NP-complete on the family of planar, cubic and triply connected graphs: https://epubs.siam.org/doi/abs/10.1137/0205049

For a problem I'm thinking about, it would be insightful to know if the Hamiltonian cycle problem was also NP-complete on the family of plane graphs whose dual is cubic and triply connected.

I would be interested in any result of the following form:

Let $D_d = \{ G \text{ a planar graph} : G^* \text{ has max degree bounded by } d \}$. Then for some $d$, Hamiltonian cycle is NP complete on $D_d$.

The following paper shows that the Hamiltonian cycle problem is NP-complete in maximal planar graphs:

  A. Wigderson
  The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs
  Technical Report #298, Department of EECS, Princeton University, February 1982.
  https://www.math.ias.edu/avi/node/820

In a maximal planar graph, every face is a triangle; hence the dual of a  maximal planar graph is cubic. It is easy to see that the dual of a maximal planar graph is triply connected.

Therefore your problem is NP-complete.


Non-Uniform Lower Bounds for NSPACE If I'm not mistaken it is not known whether $E^{NP} \subseteq {\rm SIZE}(n)$
where $E^{NP}$ is the class of problems solvable by a TM which works in time $2^{O(n)}$ and is allowed to make queries of size $2^{O(n)}$ to an NP oracle, and ${\rm SIZE(n)}$ is the class of functions solvable by non-uniform circuits of size $O(n)$.

Since ${\rm NSPACE}[n]\subseteq E \subseteq E^{NP}$ the above observation implies that the question of whether ${\rm NSPACE}[n]\subseteq {\rm SIZE}[n]$ is open.

Questions:

What is the smallest function $f(n)$ such that it is known
unconditionally  that ${\rm NSPACE}[f(n)]\nsubseteq {\rm SIZE}[n]$?
What is the smallest class $\mathcal{C}$ containing $E^{NP}$ such that it is known unconditionally that $\mathcal{C}\nsubseteq SIZE[n]$?
What is a good reference for relations between uniform and non-uniform circuit classes?

For any space-constructible function $f$ such that $f(n)=\omega(n)$, we have $\mathrm{NSPACE}(f(n)\log n)\nsubseteq\mathrm{SIZE}(n)$. This follows by simple brute force: you can compute the predicate

  $\exists$ a truth-table $t$ of a Boolean function in $O(\log f(n))$ variables such that ($\forall$ circuit $C$ of size $f(n)$, $C$ does not compute $t$) and ($\forall$ truth-tables $t'$ lexicographically smaller than $t$, $\exists$ a circuit of size $O(f(n))$ that computes $t'$) and $t(x)=1$

(where $x$ is the given input of length $n$) on an alternating TM with space $O(f(n)\log n)$ and $O(1)$ alternations, hence in $\mathrm{NSPACE}(O(f(n)\log n))$ by the Immerman–Szelepcsényi theorem. (The $\log n$ factor comes from the fact that a description of a circuit of size $f(n)$ takes $O(f(n)\log f(n))$ bits; we may assume $f(n)\le n^2$, thus $\log f(n)=O(\log n)$.)

The same kind of argument shows that $\mathrm{TIME}(n^{f(n)})^\mathrm{NP}\nsubseteq\mathrm{SIZE}(n)$ for any function $f(n)$ as above. However, this is really overkill. For example, it is known that oblivious $S_2^\mathrm P$ is also not contained in $\mathrm{SIZE}(n)$ (or $\mathrm{SIZE}(n^k)$ for any fixed $k$, for that matter), and it sits fairly low in the polynomial-time hierarchy, hence it is “almost” a much smaller class than $\mathrm{E^{NP}}$.


Can we not output the Kolmogorov complexity? Let us fix a prefix-free encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ (encoded as the prefix-free code of $T$ followed by $x$) outputs whatever $T$ outputs on input $x$ (possibly both running forever).
Define the Kolmogorov complexity of $x$, $K(x)$, as the length of the shortest program $p$ such that $U(p)=x$.

  Is there a Turing machine $T$ such that for every input $x$ it outputs an integer $T(x)\le |x|$ that is different from the Kolmogorov complexity of $x$, i.e., $T(x)\ne K(x)$ but $\liminf_{|x|\rightarrow \infty} T(x)=\infty$?

The conditions are necessary, because

(a) if $T(x)\not \le |x|$, then it would be easy to output a number that is trivially different from $K(x)$ because it is bigger than $|x|+c_U$,

(b) if $\liminf_{|x|\rightarrow \infty} T(x)<C$ is allowed, then we can just output $0$ (or some other constant) for almost all numbers, by "luckily" guessing the at most one (finitely many numbers) that evaluate to $0$ (to some other constant) and output there something else.
We can even guarantee $\limsup_{|x|\rightarrow \infty} T(x)=\infty$ by outputting something like $2\log n$ for $x=2^n$.

Also note that our job would be easy if we know that $T(x)$ is not surjective, but little is known about this, so the answer might depend on $U$, though I doubt it would.

I know that relations are studied a lot in general, but

  Has anyone ever asked a similar question where our goal is to give an algorithm that does not output some parameter?

My motivation is this problem http://arxiv.org/abs/1302.1109.

The question can be rephrased as whether or not $\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} = 0$, and as Denis points out in the comments this is false for some encodings.  Here is a weaker statement and an attempted proof of it that doesn't depend on any details of the encoding, but I'll assume a binary language for simplicity:

Let $T:\{0,1\}^* \rightarrow \mathbb{N}$ be a computable function satisfying $0 \le T(x) \le \vert x \vert$ and $\lim \inf_{\vert x \vert \rightarrow \infty}{T(x)} = \infty$.  Then $\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} \lt \infty$.  Informally, if there is a target around each string's Kolmogorov complexity that grows unboundedly wide, no computable function can avoid hitting it.

To see this, let $n$ be a random $b$-bit number, i.e. $0 \le n \lt 2^b$ and $K(n) \ge b$.  For all $b$ such a random $n$ exists.   Also note that there are an infinite number of values of $b$ for which $\vert \{T(x) = b\} \vert \ge 2^b$, this follows from the conditions placed on $T$.  Now let $x$ be the $n^{\text{th}}$ smallest string such that $T(x) = b$.  Clearly there is a constant $c_1$ such that $K(x) \gt b - c_1$, because $K(n) \ge b$ and $n$ can be computed from $x$.  And there is a constant $c_2$ such that $K(x) \lt b + c_2$, because $K(n)$ is also bounded from above by only a constant more than $b$, and $x$ can be computed from $n$.  Then $\vert K(x) - T(x) \vert \lt c_1 + c_2$, and we have an infinite number of choices for $b$ (those with a preimage of cardinality at least $2^b$), yielding an infinite number of values for $x$, so we are done.

An implication is that for some $c \in \mathbb{Z}$, $T(x) = K(x) + c$ infinitely often.  So one might say we can't not output something that's not the Kolmogorov complexity!


Is the current best approximation ratio for Vertex Cover problem also a lower bound? In textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. in pp.1110-1111, they argue that the vertex-cover problem is a 2-approximation algorithm and it is lower bound so we cannot improve better than 2. However, there is an old paper by Johan Hastad here he shows that by using PCP technique we cannot do better than 7/6=1.16 which is an NP-complete. So, we have a gap between 2 and 7/6 which tells us that whether we have a better approximation algorithm is still open problem. Is that right?! or suppose that Hastad is wrong, then there must be a new analysis about the hardness of vector cover in terms of approximation algorithm.

*As I understand who argues that we cannot do better than the approximation ratio which is 2, the reason is that to give tight example (nontrivial example) which is a complete bipartite graph (K_{n,n}) and since the algorithm choose n number of edges, therefore we have 2n number of vertices, and the vertex cover is only n in this case. Their claim is that if you find 2(n-1) edges, then you have n-1 vertices, and there is a contradiction since we are not covering all vertices which is n. (this is how I understand it so it could be wrong) (Of course there is no polynomial algorithm to find n vertices, and the best approximation algorithm is to find 2n in polynomial time, and they say that it is tight bound) I also read this lecture notes

Also, Is there any new results about the hardness of vertex cover in terms of approximation.

Cormen, Leiserson, Rivest and Stein say that this algorithm that achieves ratio of 2 is tight. They did not exclude the possibility of another algorithm achieving better.

Vertex Cover is NP-hard to approximate with a factor better than 1.36:
http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf

Also check the following paper which give a 2-epsilon inapproximability result based on unique games hardness:
http://www.sciencedirect.com/science/article/pii/S0022000007000864

For approximation algorithms, see the wiki article for Vertex Cover and in particular the paper of Karakostas 2009: https://eccc.weizmann.ac.il/report/2004/084/


Generalization of Beck's theorem Beck's theorem is a classical result in discrete geometry which describes about the geometry of points in the plane. The result states that a finite collections of points in the plane fall into one of two extremes; one where a large fraction of points lie on a single line, and one where a large number of lines are needed to connect all the points.

Formally, the statement of the theorem is as follows:

Theorem: Let $S$ be a set of $n$ points in the plane. If at most $(n-k)$ points lie on any line for some $0 \leq k < n-2$, then there exist $\Omega(nk)$ lines determined by the points of $S$.

Now, my question is that if the generalization/variation of the above result is known in the case of higher dimension $(dim\geq 3)$?

If you are asking if the same statement holds true or not in higher dimensions, it does. Just project all the points to a random 2-dimensional plane.
Another natural generalization is to consider hyperplanes instead of lines. Here, you have Beck's "other" theorem:

Theorem: For any $d \geq 2$, there are constants $\beta_d, \gamma_d \in (0,1/2]$ such that for any set $P$ of $n$ points in $\mathbb{R}^d$, at least one of the following holds:

a hyperplane contains at least $\beta_d n$ points of $P$
the $d$-tuples of $P$ span at least $\gamma_d n^d$ distinct hyperplanes.

Here, a hyperplane is a $(d-1)$-dimensional flat. For $d=2$, this is essentially what you stated. The restriction that $\beta_d \leq 1/2$ is from the example of having two skew lines in $\mathbb{R}^3$ containing $n/2$ points each, where the number of spanned planes is $n$. For more, see: http://www.cs.elte.hu/~elekes/Abstracts/elest.ps


Online version of All pair shortest path when path weights are updated Given

an undirected graph of $n$ nodes with weighted edges and
a sequence $S=((e,w),...)$ of updates, always decreasing, of the weight $w$ of edge $e$.

What is the online complexity of computing the shortest pair between each pair of nodes in the graph after each updates? Is there any solution better than solving the problem offline in time within $O(n^3)$ (using Floyd-Warshall's algorithm) after each update?

I think adding the keywords decremental/incremental might help you find the relevant papers.

See e.g.
Camil Demetrescu, Giuseppe F. Italiano: Decremental All-Pairs Shortest Paths. Encyclopedia of Algorithms 2008 for an overview, Camil Demetrescu, Giuseppe F. Italiano: Fully dynamic all pairs shortest paths with real edge weights. J. Comput. Syst. Sci. 72(5): 813-837 (2006), and Camil Demetrescu, Giuseppe F. Italiano: A new approach to dynamic all pairs shortest paths. J. ACM 51(6): 968-992 (2004)

Approximate versions have been considered as well; the most recent result I know of is Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai: Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization, FOCS 2013.
Table 1 in their paper has an overview of results.


"Snake" reconfiguration problem While writing a small post on the complexity of the videogames Nibbler and Snake; I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such problems have not been well studied in the motion planning area (imagine for example a chain of linked carriages or robots). The games are well known, however this is a short description of the related reconfiguration model:

SNAKE PROBLEM

Input: given a planar graph $G = (V,E)$, $l$ pebbles $p_1,...,p_l$ are placed on nodes $u_1,...,u_l$ that form a simple path. The pebbles represent the snake, and the first one $p_1$ is his head. The head can be moved from its current position to an adjacent free node, and the body follows it. Some nodes are marked with a dot; when the head reaches a node with a dot, the body will increase by $e$ pebbles in the following $e$ moves of the head. The dot on the node is deleted after the traversal of the snake.

Problem: We ask if the snake can be moved along the graph and reach a target configuration $T$ where the target configuration is the full description of the snake position, i.e. the position of the pebbles.

It is easy to prove that the SNAKE problem is NP-hard on planar graphs of max degree 3 even if no dots are used and also on SOLID grid graphs if we can use an arbitrary number of dots. Things get complicated on solid grid graphs without dots (it is related to another open problem).

  I would like to know if the problem has been studied under another name.
  and, in particular, if there is a proof that it is in NP ...

Edit: the problem turned out to be PSPACE-complete even on planar graphs and the result seems very interesting, so it remains to find out if it is a new problem
and if there are known results about it.

A simple example (pebbles are shown in green, the snake's head is P1).

Moving a snake from one position to some other is PSPACE complete.
Snake is trivially in PSPACE.
We give a PSPACE hardness reduction from Hearn's Nondeterministic Constraint Logic.

Nondeterministic Constraint Logic

Let a constraint graph be a directed graph with edges of weight $1$ and $2$, such that every vertex has incoming weight $\geq 2$.
Given two constraint graphs, it is PSPACE hard to transform one into the other by reversing edges, one at a time, keeping the incoming weight of each vertex $\geq 2$.
This still holds if the graph is planar and each vertex has degree $3$, and either $1$ or all $3$ of its edges have weight $2$.
The former type of vertex is called And and the latter is called Or (see figure).

Snake

In our construction, the snake's head will be chasing its tail at some small distance and will be forced to repeat the same cycle with minor modifications.
We embed each edge of the constraint graph as in the figure (edges shown in red), where we indicate the position of the snake by thick lines.
An edge has two sides (vertices) and the snake takes the central route at the vertex to which the edge is directed.

To reverse an edge, the snake first clears the center route and then takes the center route once its head reaches the opposite vertex.

We embed vertices of the constraint graph as shown below, where each of the three colored parts is a half of an edge gadget shown above. The points where the edges touch make sure that the incoming weight of each vertex is at least $2$ by forcing the snake to take the center route of some edge gadgets.

Finally, the black lines of all edge gadgets are connected to form a single cycle, so the head of the snake chases its tail.
If between two edge gadgets, we make the black path sufficiently long, the snake must always traverse the black paths in the same cyclic order.

To show that the black paths can always be constructed in a planar manner, consider a spanning subtree (thick edges in the figure below) of the constraint graph.
Then we can make black edges follow this tree as illustrated below, resulting in a planar graph.

The target position of the snake can be derived by the same transformation.
Hence, reconfiguring a snake is PSPACE complete, even on planar graphs.


How fine-grained can the time hierarchy theorem be in a reasonable model? One version of the sharp or additive space hierarchy theorem is that for Turing machines (and a number of other deterministic sequential computational models) $\mathrm{Space}(f-ω(\log(n+f))) ⊊ \mathrm{Space}(f)$ for space-constructible $f(n)$, where space is measured in bits.

Are there reasonable computational models where we have an analogous sharp version of the time hierarchy theorem: $\mathrm{Time}(f+O(1)) ⊊ \mathrm{Time}(f+O(g))$ for $g$-time-computable $f(n)$ with $g(n)≥\log(n+f(n))$?

Since I already know one (arguably reasonable) class of models with the sharp time hierarchy, I am including it as an answer, but I am still interested in related results, including
- other models with the sharp time hierarchy theorem
- whether this model or other models were studied in literature
- weaker forms of time hierarchy, especially if stronger than $\mathrm{Time}(f) ⊊ \mathrm{Time}((1+ε)f)$
- whether there is a speed-up theorem for Turing machines with a fixed number of binary tapes that would prevent this form of sharp time hierarchy.

Footnotes/References:
* The additive/sharp space hierarchy theorem can proved using "Halting Space-Bounded Computations" by Michael Sipser (1978).  See also "Improved time and space hierarchies of one-tape off-line TMs" by Kazuo Iwama and Chuzo Iwamoto (1998).
* A weak form of additive time hierarchy is discussed in "Computational Models with No Linear Speedup" by Amir Ben-Amram, Niels Christensen, Jakob Grue Simonsen (2012).

The three ingredients of a diagonalization based proof of the time hierarchy theorem are universal simulation, timing, and reversal.  By choosing (or defining) a computational model where these operations are efficient, we get a sharp hierarchy theorem.  In particular, by using a model with a timed virtualization primitive satisfying certain conditions, we get a time hierarchy in the requested form.  However, unlike the sharp space hierarchy, the precise time usage and hierarchy is on a per-model basis (and thus somewhat arbitrary).

If we set up things appropriately, the following algorithm can be implemented in time $f(n)+O(g(n))$ but not in time i.o.-$(f(n)+O(1))$ where $g(n)≥\log(n+f(n))$ and $f$ is $g$-time computable (i.o. means infinitely often):
* Determine the input length $n$, and compute $f(n)$.
* Read a small portion of the input to get a code $M$.
* Run TimedVirtualize($M$, $f(n) + \lg(n)$)  # check whether $M$ accepts the input in $f(n) + \lg(n)$ steps; TimedVirtualize must be fast enough.
* If $M$ accepts, then Reject, and otherwise Accept.

For the time hierarchy, the simplest model is to have a special tape to write the parameters, and an instruction to call TimedVirtualize with a mapping: {Accept, Reject,Timeout}→{Accept,Reject,Timeout} (with no further instructions after TimedVirtualize finishes; TimedVirtualize runs in real time).

However, it is more natural to be able to use virtualization repeatedly, and the rest of the answer gives a partial specification of a class of timed virtualization models, and how such a model can be implemented efficiently.

Timed Virtualization

A computational model defines how a program is interpreted and how much time it takes.  A problem is solvable in time $f$ iff some program solves in time $f(n)$ for all valid inputs where $n$ is the input length.  We assume that input length can be determined in logarithmic time.

One approach to timed virtualization is to use code, data, and privileged data 'tapes'.  The code tape need not be directly accessible.  The data and privileged data tapes are accessible, except that at a given time, a portion of the privileged data tape may be invisible and undetectable. In addition to ordinary instructions, the models have a virtualization function
TimedVirtualize(Code, Time) such that:

The machine executes Code for up to Time steps (Code and Time are obtained from the privileged data tape).  The code is executed and each step is counted as if we initially set the code to Code (and the data tape to its current state.)  All instructions (including TimedVirtualize) are permitted.  The code sees the privileged data tape as initially empty.  The previous privileged data remains unchanged (but the hierarchy theorems would also hold if it were erased instead).
TimedVirtualize returns a value coding Timeout/Accept/Reject depending on whether the code timed out or called an Accept/Reject instruction (that would otherwise Accept/Reject the input).
(optional extension) an optional space bound can be set.
Full-speed condition:  The number of steps TimedVirtualize(Code, Time) takes equals the number of steps Code took (which is ≤Time), plus Time-independent overhead, plus $O(\log(\mathrm{Time}))$.
A number of features can be added to TimedVirtualize, but they are not needed for the hierarchy theorems.  For example, we might want to set initial privileged data, get the time spent by Code, allow unbounded time, or (optionally) do nonvirtualized execution that replaces the code and (visible) privileged data (thus saving space).

Under basic assumptions about the code and timings, every model of this type satisfies the sharp time hierarchy theorem.  The computation of $f(n)$ must erase the worktape at the end (except for the input data if do not use a read-only input tape); we can either define time-constructibility to include the erasure, or use a model where the erasure can be done in linear time.

Efficient Example and Implementation

For every $k$, there is such a model that can simulate in linear time $k$-tape Turing machines (time depends on the machine simulated), and in turn can be simulated in linear time by a $k+2$-tape Turing machine, which suggests that the full-speed condition is computationally reasonable.  (Since a model defines timings, an implementation is an important evidence of reasonableness.) I am not sure if the two tape gap can be reduced to 0.

To get such a model, we fix an interpretation and timings of the code such that an efficient universal Turing machine can simulate the code in linear time, with the constant factor independent of the code size.  For example, we can interpret the code as a Turing machine, but with the state transition specifying the relative offset $d$ (in bits) and taking $k(d+1)$ time, and with a convention and timings for TimedVirtualize (also, note that without random access tapes, head/cursor position is important).  In addition to the tapes in the model, the machine uses a tape storing the timers (and if implemented, space bounds).  While at time $t$, we might have $O(t / \log t)$ timers, we only need the antimonotonic case (timers that are set later trigger sooner), so we can use a counter for the innermost timer, and efficiently use subtraction to update the previous timer when TimedVirtualize finishes.

TimeSpace Hierarchy

If we define space usage in a reasonable way (and allow space bounds in virtualization), we can even get models with a sharp TimeSpace hierarchy theorem:   $\mathrm{TimeSpace}(T+O(1), S+O(1)) ⊊ \mathrm{TimeSpace}(T+O(g), S+h+O(\log T))$ for $\mathrm{TimeSpace}(g,h)$-constructible $(T,S)$ with $g(n)≥\log(n)$ and $T(n)≥n$.  The need for precise timings makes the space hierarchy less sharp here (at least to the extent we can currently prove the hierarchy).


How do you remember parameters? I'm currently doing research in pseudorandomness, which involves a zoo of wonderful objects such as pseudorandom generators, randomness extractors, expander graphs, etc. I find it a fascinating topic, but one thing that drives me crazy is the glut of parameters that are involved. I understand that these objects are very complex, but I cannot help but break out into a sweat when I see "Let $G$ be a standard $(\alpha,V,\epsilon^2,k,\delta)$-pseudorandom widget...". Then I have to flip back in the paper or find another paper (which probably uses a different parameterization) and try to remember what all $\alpha,V,\epsilon,k$ and $\delta$ all meant.

It takes me quite a while to acquire a feeling for "good" parameter settings versus "bad" parameter settings, versus "natural" settings versus "easy" settings.

There's probably no magic bullet for this issue - but I was wondering if other people had some method of managing the "parameter explosion" so that it's easier to retain in memory for a longer period of time?

Thanks!

My research practices, when I go into new research domain, cover combination of memory management, mnemonic, notes and other practices.

I have no one recipe, cause each is dependent on nature of given domain.

For some inspiration and sake of discussion, here is and example that came now into my mind:

Go through papers into a few iterations:

First, to get adjusted to domain and get first intuition about approaches and notations.
Next step is preparation to "clusterization" of papers.

prepare list of tags representing approaches, notations, features and other interesting me properties.
Before I start tagging I go through papers and evaluate my tags, correct appropriately.
Finally I tag papers

Then I process papers according to tags in groups: with similar notation, approach...

Thanks to working with papers sharing common properties, you can concentrate on differences.
I prepare notes in form of MindMap with FreeMind. To easily reach "what was what".

After processing papers grouped in sets with tags, try look at whole area with all groups to get boarder view.
Now is step of looking thought whole domain to see connections and differences. When I can't remember details, I check-out in my MindMap to remind, what was what.

Try to avoid overloading your memory, when it's unneeded, use: Mnemonics and Art Of Memory techniques. Use MindMapping.


Does Standard ML validate (CBV) eta equivalence? $\eta$ equality of functions is fundamental in their Category-theoretic semantics but in practice even "functional" languages include "impure" features that violate it.
Note that this is not an issue of CBN vs CBV, in CBN eta equality $M = \lambda x. M x$ should hold for any term $M : A \to B$ whereas in CBV this will be restricted to values $V = \lambda x. V x$. The CBV $\eta$ equality has a perfectly good category-theoretic explanation, see Levy's Call-by-push-value.

Haskell includes seq, which can distinguish between (\x -> error "") and error ""
OCaml includes operations like "physical equality" (==), and which will distinguish fun x => x from fun y => (fun x => x) y because == corresponds to pointer equality.

So I wonder do any "real" languages satisfy eta for observational equivalence at all?
All the better if it is known that a (correct) compiler implementation performs eta reductions just based on the type.

The only example I know of is Coq which includes it as a definitional equality as of a recent version. Maybe similar languages (Agda, Idris) do as well. These are not surprising because they include an equality type and it is very frustrating to prove equality of functions without $\eta$ or the stronger(?) extensionality principle.

My main question is about Standard ML specifically which I think does not have pointer equality for functions. Does it satisfy the CBV $\eta$ law? Furthermore do compilers for SML such as MLton use $\eta$ when optimizing programs?

@xuq01's guess is (extremely surprisingly!) wrong. The CBV eta rule described in the question is sound in Standard ML: the value v is contextually equivalent to fn x => v x.

There are two caveats to this.

First, in specific implementations this equivalence might not be sound: in SML/NJ, you could use Unsafe.cast to detect physical equality of function values. However, unsafe features are not part of the standard.
Second, eta with functions and sums interacts in a slightly subtle way, due to clausal definitions and incomplete pattern matching. In particular, the definitions:

fun f (SOME x) (SOME y) = x + y

and

val g = fn (SOME x) => (fn (SOME y) => x + y)

are not contextually equivalent. This is because the call f NONE will return a function, and g NONE will raise an error.

- f NONE;
val it = fn : int option -> int

- g NONE;
uncaught exception Match [nonexhaustive match failure]
raised at: stdIn:2.32

The reason this happens is operationally obvious, and of course a call-by-push-value/polarization setup makes this choice explicable. But if you really want to seriously understand clausal definitions, you are led to the idea that clausal definitions should be primary, and the usual term formers should be derived notions. See Abel, Pientka, Thibodeau and Setzer's Copatterns: programming infinite structures by observations for an example of a polarized calculus in this style. (See also Paul Levy's Jumbo Lambda-Calculus, for another calculus based on this observation.)


What is the size of a function? I'm not sure whether this question should be asked on mathoverflow.com or here, but as it is in the context of computational complexity, I will ask here.

Context

Oded Goldreich states in his book Computational Complexity: A Conceptual Perspective (no advertising intended!) that a search problem is in PC (Polynomial-Time Check) if it fulfills this condition among others:

  There exists a polynomial $p$ s.t. if $(x, y) \in R$ then $|y| \leq p(|x|)$.

Question

If the solution to a search problem is a function, how is the size of the function ($|y|$) determined? I thought, it could be size of the input of that function, but I am not sure.

This is a basic question, yet I tend to answer simple ones too :)

In the book you mentioned, take a look at section 1.2.1 (page 18). It describes how various objects are encoded. Among other things, it includes a section "Strings," in which "relation encoding" is described:

At times, we associate $\{0, 1\}^∗ \times \{0, 1\}^∗$ with $\{0, 1\}^∗$; the reader should merely consider an adequate encoding (e.g., the pair
$(x_1 \dots x_m, y_1 \dots y_n) \in \{0, 1\}^∗ \times \{0, 1\}^∗$
may be encoded by the string $x_1x_1 \dots x_mx_m01y_1 \dots y_n \in \{0, 1\}^∗$).

Functions are a special type of relation, so they can be similarly encoded. In particular, a (finite and discrete) function can be seen as a list of input-output relations: $f=\{(x_1,y_1),\dots,(x_n,y_n)\}$. This can be easily encoded by incorporating a special symbol, say $\circ$. That is, $enc(f)=x_1 \circ y_1 \circ \dots \circ x_n \circ y_n$. (The encoding can be done without any special symbol, but it adds unnecessary intricacy.)

This way, the size of $f$ is the size of its encoding: $|enc(f)| \approx \sum_{i=1}^{n}{(|x_i|+|y_i|)}$.

Needless to say, infinite functions have infinite size, unless you can compress the list somehow. (This brings up the "Kolmogorov Complexity Theory", which is a story for another day!)


Difficulty in understanding the quantum algorithm for the abelian hidden subgroup problem I've difficulty in understanding the last steps of the AHSP algorithm. Let $G$ be an abelian group and $f$ be the function which hides the subgroup $H$. Let $G^*$ represent the dual group of $G$.

Here are the steps of the algorithm

First prepare the state,

$\qquad \displaystyle I=\frac{1}{|G|} \sum_{g \in G} |g\rangle|0\rangle$.
Then apply the quantum oracle which evaluates $f$ on $I$, we get

$\qquad \displaystyle I'=\sum_{g \in G} |g\rangle|f(g)\rangle$.
Now measure the the second qubit of $I'$, we get

$\qquad\displaystyle I'= \left(\frac{1}{|H|}\Sigma_{g \in H} |rh\rangle\right) \otimes |f(rh)\rangle$

for some $r \in G$.
Now we  apply the quantum fourier transform on the first qubit, we get

$\qquad \displaystyle I_m = \frac{1}{|H^*|}\sum_{\chi \in H^*} |\chi\rangle$,

where $H^*= \{\chi \in G^*: \chi(h)=1 ,\forall h \in H\}$.

Now from the state $I_m$ how can we get generators of the group $H$?

This classical post-processing exploits several non-trivial group theoretical properties of Abelian groups. I wrote a didactic explanation of how this classical algorithm works here [1]; other good sources to read about are [2, 3, 4].

So, measuring at the end of the algorithm in the standard basis will give you elements of $H^{*}$ uniformly at random. It is not hard to check that the set $H^{*}$ is a (finite Abelian) subgroup of the character group $G^{*}$; due to, after $O(\log{|G|})$ measurement rounds a generating set of $H^{*}$ is obtained with probability exponentially close to one.

The most technical part is how to reconstruct $H$ given a generating set of $H^{*}$. Let us focus on this problem from now on. For this, we will need some rudiments from character theory.

Character Theory

First of all, remember that, when $G$ is finite Abelian, characters form a group isomorphic to $G$ and that they can be written as
\begin{equation}
\chi_g(h)=\exp{\left(2\pi i \sum_{i=1}^{m} \frac{g(i)h(i)}{d_i}\right)}.
\end{equation}
The label $g$ of the character $\chi_g$ is an element of $G$. The map $g\rightarrow \chi_g$ defines an isomorphism between $G^*$ and $G$, so that we can identify both groups.

Now, given $H$, the set $H^*$ you describe is calle the orthogonal subgroup of $H$ or, depending on the source, the annihilator of $H$. This subgroup has some important mathematical properties:

First of all, $H^*$ is also subgroup of $G$;
It is dual to $H$, in the sense that, if we consider the
double annihilator subgroup $H^{**}$, this subgroup is isomorphic to
$H$: i.e., $H\cong H^{**}$. This guarantees that the solutions to the system of equations $$\chi_g(h)=1,\quad \textrm{ for every } g\in H^*$$
are precisely the elements of the subgroup $H$ that you want.

Linear Equations over Groups

Now, a key observation that we can use is the following (I will follow  [1] for this part): the former systems of equations can be re-written as a ''system of linear equations over finite Abelian groups''. By that, I mean a problem where the input are to finite Abelian groups $X$, $Y$; an element $b\in Y$; a group homomorphism$ \alpha:X\rightarrow Y$ and the task is to find the solutions of the equation $$\alpha(x)=b$$ You can show that any homomorphisms can be written as a matrix $A$, in such a way that the problem above can be re-expressed as
\begin{equation}
A x=
\begin{pmatrix}
a_1(1) & a_2(1) & \cdots & a_n(1)\\
a_1(2) & a_2(2) & \cdots & a_n(2)\\
\vdots & \vdots & \cdots & \vdots\\
a_1(m) & a_2(m) & \cdots & a_n(m)
\end{pmatrix}
\begin{pmatrix}
x(1)\\
x(2)\\
\vdots\\
x(n)
\end{pmatrix}
=
\begin{pmatrix}
b(1) \\
b(2) \\
\vdots\\
b(m)
\end{pmatrix}
\begin{matrix}
\mod d_1\\
\mod d_2\\
\vdots\\
\mod d_m
\end{matrix}
= b
\end{equation}
where we assume $Y=\mathbb{Z}_{d_{1}}\times\cdots\times \mathbb{Z}_{d_{m}}$.

The final key observation is that there exist efficient classical algorithms to decide whether these systems admit solutions, count them and find them (we survey some in [1]). The set of solutions is always of the form $x_0+\ker{\alpha}$, where $x_0$ is a particular solution and $\ker{\alpha}$ is the kernel of $\alpha$ (a subgroup of $X$). These classical algorithms can find a particular solution of the system and compute a generating set of $\ker{\alpha}$. These classical algorithms make crucial use of Smith Normal Forms to rewrite the system in an almost diagonal form (some other intermediate steps are necessary, but that should give you the intuitive picture).

The system of equations that you obtain in your case encodes the hidden subgroup $H$. In particular is of the form $\Omega x = 0$, for some group homomorphism $\Omega$. The kernel of $\Omega$ is precisely the hidden subgroup. A particular solution in that case is 0, the trivial one.


$RL=L$ Progress Since 2006 Reingold, Trevisan, and Vadhan's breakthrough 2006 paper (http://dl.acm.org/citation.cfm?id=1132583) reduced the problem of showing $RL=L$ to producing pseudorandom walks on regular digraphs that are not consistently labeled.

Has any further progress on this problem been made since then?

One line of work has shown how to improve the analysis of the classic INW PRG for the special cases of fooling regular and permutation branching programs. The seed length is only $\widetilde{O}(\log n)$ or $O(\log n)$ in some cases. [LRTV09] [BV10] [De11] [KNP11] [Ste12] [BRRY14] [HPV21]
Another line of work has developed a PRG framework based on iterated pseudorandom restrictions. This framework has been used to fool various classes of functions that can be computed by "arbitrary-order" read-once branching programs. Again, in some cases the seed length is $\widetilde{O}(\log n)$ or even $O(\log n)$. [GMRTV12] [GLS12] [RSV13] [CSV15] [SVW17] [CHRT18] [HLV18] [FK18] [MRT19] [DHH19] [Lee19] [LV20] [DHH20] [DMRTV21]
The paper referenced in the original question is part of a line of work that uses spectral techniques to design graph algorithms for space-bounded derandomization. That line of work, which most famously includes Reingold's algorithm for undirected connectivity, has continued. Recently the focus has been on simulating random walks of length much less than the mixing time of the graph. [CRV11] [MRSV17] [MRSV19] [AKMPSV20]
Finally, there is a line of work designing improved low-error generalized PRGs for polynomial-width read-once branching programs. By "generalized PRGs," I am referring to (a) hitting set generators and (b) weighted pseudorandom generators, aka pseudorandom pseudodistribution generators. [BCG20] [HZ20] [CL20] [CDRSTS21] [PV21] [Hoz21]

Please forgive me for inevitably omitting many excellent papers from this summary, including lots of work that doesn't fit neatly into the four themes above.
See also: Reingold's two-part presentation "Recent Developments Related to RL vs. L" at the DIMACS Day of Complexity Tutorials prior to CCC 2019, and the STOC 2020 workshop "Derandomizing Space-Bounded Computation" organized by Meka, Tal, and Zuckerman.


Finding the nearest node to a given set of nodes in a graph I am looking for an algorithm that, given a large weighted undirected graph, would find the node that has minimum average distance from a given set of nodes in the graph.

I think Dijkstra's shortest path algorithm would be suitable for your problem. But since you want to find the shortest-path node from a set of nodes and not from just one node, you need to tweak it.

The algorithm is quite straightforward but a bit obtuse, try searching for animated expositions on YouTube.


Is $LL(k)$ for large $k$ considered harmful? If so, why? I took a course touching on lexer and parser theory this semester (a sizeable chunk was devoted to regexes and other FSA, but context-free grammars were covered as well).

Over the course of the semester, the prof mentioned that grammars should be optimized to $LL(1)$ whenever possible. Unfortunately, he never explained properly why such grammars are "better." Wouldn't a greater lookahead make for more effective predictive parsing? Or is it considered harmful taking into account physical resource (RAM, CPU) constraints? Or do parsers with more lookahead simply become more complex than they're worth?

The parsing table of a $LL(k)$ grammar grows exponentially in $k$.
This is however the worst-case scenario, which is not typical, as Niel pointed out:
For an $LL(k)$ grammar $G$, $k$ is the size of the maximal lookahead needed across $L(G)$.
But it appears that in practice, the need for a $k$ lookahead is restricted to a small portion to the language, so that the size of the parsing table remains reasonable.

We face here a quite common problem of theoretical complexity not reflecting the practical experience.
Beyond $LL(k)$ are $LL(*)$ grammars, whose lookahead is adaptative, so as to keep the parsing table no larger than necessary.
$LL(*)$ technique is examplified by ANTLR, and described in this paper by Terence Parr.

Finally, I would say that many teachers focus on $LL(1)$ to emphasize that $LL(1)$ suffices to parse most languages in practice.
Philosophically, our programming languages lie somewhere between Deterministic and Non-Deterministic Pushdown Automata, but in fact way closer to DPA than to the full NPA.
A similar observation can be done for natural languages: context-free is not enough, yet context-sensitive is way too powerful.


Proof that all Boolean functions can be computed by $(MOD_2-MOD_3)$ circuit I was reading "Some properties of MOD m circuits computing simple functions" (Amano & Maruoka, 2003) where the authors prove that every Boolean function can be computed by depth $2$ by $(MOD_2-MOD_3)$ circuit. They claim what follows:

  It was known that the $OR$ function of $n$
  variables, i.e., $\vee_{i=1}^n x_i$
  , can be
  computed by a depth two $(MOD_3-MOD_2)$ circuit.

I agree with the above part and I am able to show a construction for $n$-ary $OR$. Based on this fact they note that:

  This implies that every disjunction of $n$
  literals, i.e., $\vee_{i=1}^n l_i$
  where $l_i\in \{x_i,\overline{x_i}\}$
  ,
  also can be computed by a depth two $(MOD_3-MOD_2)$ circuit.

Which I also accept. Afterward, they set up grounds for the main proof:

  Let $f$ be an arbitrary Boolean function on $n$
  variables. Consider a CNF formula representing
  $f$, where each clause contains exactly $n$
  literals. Without loss of generality, we
  can assume that the formula has $m\equiv 1(\mod 3)$ clauses.

So far so good. But then comes the part I get lost at:

  If the value of $f$ is 0, then $m-1\equiv 0(\mod 3)$
  clauses of $f$ takes value $1$, and if the value of $f$
  is $1$, then all of the $m\equiv 0(\mod 3)$ clauses takes value $1$. Thus the $MOD_3$ gate, whose inputs are all $(MOD_3-MOD_2)$
  circuit computing each clause in the CNF formula, evaluates the func-
  tion $f$

Could anyone please explain to me why the sentence

  If the value of $f$ is 0, then $m-1\equiv 0(\mod 3)$
  clauses of $f$ takes value $1$

is true? Isn't it possible for a CNF with $m$ clauses to evaluate to $0$ and have $m-2$ clauses true? Or $m-3$ or $m-113$. What if, for example, my CNF is a big $AND$ of $n$ variables? Then this doesn't hold, any number of clauses might be 'dead'...

(Note this is not the whole proof, you have to show how to transform this bigger circuit to a smaller one).

The key observation is that $f$ is not represented by any CNF but by a CNF where all clauses have $n$ literals with distinct variables where $n$ is the number of variables.

It is easy to see that such a CNF exists. Indeed, let $S$ be the set of solutions of $\neg f$. Each solution $s \in S$ can be seen as a conjunction of $n$ literals. For example, $s = \{x=0, y=1, z=0\}$ may be seen as $\neg x \wedge y \wedge \neg z$. Thus $\neg f = \bigvee_{s \in S} s$ and then $f = \bigwedge_{s \in S} \neg s$ which is a CNF formula.

Now this is important since the clauses of this CNF, let's call it $F$, are  in one to one correspondance with assignments of the variables: to each clause $\neg s$ of $F$, we associate $s$, the only assignment that does not satisfy the clause. For instance, the only way not to satisfy  $\neg s = x \vee \neg y \vee z$ is $s=\{x=0, y=1, z=0\}$. Thus, given an assignment, at most one clause of $F$ is not satisfied.

Now there is still something to explain. The authors claim that we can assume $m \equiv 1 \mod 3$ wlog. That is not completely true since we cannot grow the number of clauses artificially and still have the previous property. However, for the sake of their argument, it is enough to add trivial clauses such a $x \vee \neg x$ that always evaluate to $1$.


Is there a suitable algorithm to draw a mixed constituency/dependency graph in a coordinate system? I am looking for an algorithm to draw a mixed constituency/dependency graph (for a linguistic application). Such a graph would have two different types of vertices (tokens, nodes), and two different types of edges (hierarchical, non-hierarchical).

I'm new to graph theory and algorithms in general, and I hope that this question doesn't collide e.g. with the research-level requirements of this site. It should however generally be in the scope of cstheory.

The graph would have to be drawn bottom-up (I think), as all tokens should be displayed with the same y-coordinate, and the y-coordinates of nodes grouping tokens and/or nodes into constituents will have to be calculated dynamically, e.g., via their longest path to a token.

Hierarchical edges (used for grouping tokens/nodes into constituents) should have a minimum number of bendpoints (ideally 0), but there should also be a minimum number of crossings, overwriting the former requirement if needs be.

Non-hierarchical edges (used for dependencies) should have a minimum number of crossings, and be drawn as Bézier curves.

The next best thing I have come across is the algorithm described by Buchheim et al., improving Walker's algorithm to run in linear time.

Please do let me know should there be any need to improve my question, and thanks a lot in advance for any pointers.

EDIT:

As pointed out in a comment, I should mention that I basically want a default graph layout by an algorithm, which I - in the long run - want to edit and revise within the Eclipse GEF possibilities. I have previously looked into options to get Graphviz to work with GEF, but there seems to be no working solution that preserves all editing functionality inherited from GEF.

you seem to want the following

a graph layout algorithm. many std algorithms typically use force-based methods where nodes are connected by replusive/attractive "springs" and the equilibrium/low energy state is obtained through some amt of iteration (of the corresponding globally-constructed force-related differential equation). the output of the algorithm is a set of 2-d or 3-d coordinates for nodes and (usually) edges.
ability to hand-modify the results of that algorithm. typically called a "graph editor". this starts with the coordinates from the layout algorithm and allows adjustment.

re (1) the forefront software seems to be graphviz. re (2) see eg this question "what is the best graph editor" on mathoverflow.

browsing the graphviz gallery, here are two graph types similar to what you want.

ER diagram and traffic light.

you say you have two types of edges. a simple way would be to have directed edges "toward or away" as in the traffic light example. or the edges can be labelled in two ways as in the ER diagram. both examples show two different node types using different shapes or labels, or shading etc. other approaches would be to use coloring.

as the mathoverflow Q/As indicate there are many graph editors. the std one with graphviz is "dotty". see eg pdf "editing graphs with dotty" by Koutsofious.

another technique for graphing, possibly large graphs, is to look at structural compositions eg clique decompositions.


Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)? I've learned from several sources that an LL(1) grammar is:

unambiguous,
not left-recursive,
and, deterministic (left-factorized).

What I can't fully understand is why the above is true for any LL(1) grammar. I know the LL(1) parsing table will have multiple entries at some cells, but what I really want to get is a formal and general (not with an example) proof to the following proposition(s):

A left-recursive (1), non-deterministic (2), or ambiguous (3) grammar is not LL(1).

I have done some more research, and I think I've found a solution for the 1st and 2nd questions, as for the 3rd one, I found an existing solution on StackOverflow for it, the proof attempts are written below:

We start by writing the three rules of the definition of an LL(1) grammar:

For every production A -> α | β with α ≠ β:

FIRST(α) ∩ FIRST(β) = Ø.
If β =>* ε then FIRST(α) ∩ FOLLOW(A) = Ø (also, if α =>* ε then FIRST(β) ∩ FOLLOW(A) = Ø).
Including ε in rule (1) implies that at most one of α and β can derive ε.

Proposition 1: A non-factored grammar is not LL(1).

Proof:

If a grammar G is non-factored then there exists a production in G of the form:

A -> ωα1 | ωα2 | ... | ωαn

(where αi is the i-th α, not the symbols α and i), with α1 ≠ α2 ≠ ... ≠ αn. We can then easily show that:

∩(i=1,..,n) FIRST(ωαi) ≠ Ø

which contradicts rule (1) of the definition, thus, a non-factored grammar is not LL(1). ∎

Proposition 2: A left-recursive grammar is not LL(1).

Proof:

If a grammar is left-recursive then there exists a production in G of the form:

S -> Sα | β

Three cases arise here:

If FIRST(β) ≠ {ε} then:

    FIRST(β) ⊆ FIRST(S)

=>  FIRST(β) ∩ FIRST(Sα) ≠ Ø

which contradicts rule (1) of the definition.
If FIRST(β) = {ε} then:

2.1. If ε ∈ FIRST(α) then:

ε ∈ FIRST(Sα)

which contradicts rule (3) of the definition.

2.2. If ε ∉ FIRST(α) then:

    FIRST(α) ⊆ FIRST(S) (because β =>* ε)

=>  FIRST(α) ⊆ FIRST(Sα) ........ (I)

we also know that:

FIRST(α) ⊆ FOLLOW(S) ........ (II)

by (I) and (II), we have:

FIRST(Sα) ∩ FOLLOW(S) ≠ Ø

and since β =>* ε, this contradicts rule (2) of the definition.

In every case we arrive at a contradiction, hence, a left-recursive grammar is not LL(1). ∎

Proposition 3: An ambiguous grammar is not LL(1).

Proof:

While the above proofs are mine, this one is not, it's by Kevin A. Naudé which I got from his answer that is linked below:

https://stackoverflow.com/a/18969767/6275103


Inherent limitation of Switching Lemma for finer lower bounds The Switching Lemma is the one of the classic and most basic tools to prove concrete circuit lower bounds. We will only consider AC$^{0}$ circuits.

The Switching Lemma claims that we can get a shallow circuit by restricting most input wires at random. More precisely,

  Lemma (Håstad’s switching lemma)
  Suppose $f$ is expressible as a $k$-DNF, and let $\rho$ denote a random restriction that assigns random
  values to $t$ randomly selected input bits. Then for every $s$,
  $$Pr[f|\rho \text{ is not expressible as $s$-CNF} ]\leq (\frac{(n − t)k^{10}}{n})^{s/2}$$
  where $f|\rho$ denotes the function f restricted to the partial assignment.

My  question is about the reason why this lemma is NOT applicable to derive finer lower bounds of constant depth $d$ circuit complexity. For example, the PARITY function has a bound of $2^{\Omega (n^{1/(d-1)})}$.  Why do we fail to obtain  bounds such as $2^{\Omega (n^{1/(\sqrt{d})})}$,$2^{\Omega (n^{1/(\log{d})})}$, or stronger $2^{\frac{n}{\text{polylog}(n)}}$ for some boolean function?

It seems that the number of remaining so called star variables, which are not be fixed by restrictions, is too small to be considered as "an input size".

  Let $F(s(n),C)$ be the Maximum number of star variables to reduce a circuit with depth $d$ and size $s(n)$ and $n$ input wires to a depth-$2$ circuit, that is, DNF or CNF. Let $F(s(n))=\min_{C} F(s(n),C)$. What are upper bounds and lower bounds as tight as we can at this moment for the following concrete $s(n)$s?

  $s(n)=F(2^{Cn^{1/(\sqrt{d})}})$ or $F(2^{Cn^{1/(\log{d})}})$ or $F(2^{\frac{n}{\text{polylog}(n)}})$

I think you can't beat the $\exp(n^{\Omega(1/d-1)})$ lower bound. Here's a construction that should work for computing parities:

In order to compute parity of $n$ variables, partition them into groups of size $t \approx n^{1/d}$, compute parity of each group and recursively compute the parity of parities. That is, start with a parity tree of fan-out $t$. The depth of this tree would be $d$.

Then, replace each parity gate with a CNF or DNF or size $\approx \exp(t)$. This way you get a circuit of depth $2d$. It is possible to alternate between CNFs and DNFs at different levels so the circuit collapses to depth $d$. This way you get a depth $d$ circuit of size $\approx \exp(n^{1/d})$ that computes the parity of $n$ bits.

Now, since switching lemma is tight for the parity function, you shouldn't hope to get a better lower bound for more sophisticated functions just relying on that.


Mutual information and entropy to prove minimal Relevance Maximum Dependency I'm reading through a paper on feature selection: Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance,and in-Redundancy
 but I'm unable to understand parts of the proof presented in section 2.3 where they are using information theory to prove that Max-Dependency is equivalent to the algorithm they present (mRMR).

I don't follow how they derive the equality for minimal redundancy...

... from ...

... and ...

(There is a similar step for the maximal relevance term which I also don't grasp)

My best understanding of what they are doing is that the entropy for each individual feature is found in the summation of the H(x_i) terms, and then the mutual information between all features is subtracted out in the J term, and that this is done (some how) through the chain rule, and then collection of the mutual information terms?

I don't have a strong back ground in information theory - so this is mostly conjecture. Hopefully some one with a stronger information theoretic background could elucidate this. Thanks.

For the equations you are reporting, $J(S_m) = I(S_{m-1}; x_m)$, i.e. $J(S_m)$ is the mutual information between $S_{m-1}$ and $x_m$. Since for any two random variables $X$ and $Y$

$I(X; Y) = H(X) + H(Y) - H(X; Y)$

the equation follows directly from the definition of mutual information (the chain rule does not apply here, since there is no need to deal with conditional entropy):

$\begin{gathered}
  H({S_{m - 1}},{x_m}) = H({S_m})  \\
   = \sum\limits_{i = 1}^m {H({x_i})}  - J({S_m})  \\
   = \sum\limits_{i = 1}^m {H({x_i})}  - I({S_{m - 1}};{x_m})  \\
   = \sum\limits_{i = 1}^m {H({x_i})}  - (H({S_{m - 1}}) + H({x_i}) - H({S_{m - 1}},{x_m}))  \\
   = \sum\limits_{i = 1}^m {H({x_i})}  - (\sum\limits_{i = 1}^m {H({x_i})}  - H({S_{m - 1}},{x_m}))  \\
   = H({S_{m - 1}},{x_m})  \\
\end{gathered}$


Bounded-cardinality bounded-frequency set cover: hardness of approximation Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets.

Example: the case $k = 4$ and $f = 2$ is equivalent to the minimum vertex cover problem in graphs with maximum degree 4.

Let $a(k,f) > 1$ be the largest value such that finding an $a(k,f)$-approximation of the minimum set cover problem with parameters $k$ and $f$ is NP-hard.

Example: $a(4,2) \ge 1.0128$ (Berman & Karpinski 1999).

Question: Do we have a reference that summarises the strongest known lower bounds on $a(k,f)$? In particular, I'm interested in concrete values in the case that both $k$ and $f$ are small but $f > 2$.

Restricted versions of the set cover problem are often convenient in reductions; typically there is some freedom in choosing the values of $k$ and $f$, and further information on $a(k,f)$ would help to choose the right values that provide the strongest hardness results. References here, here, and here provide a starting point, but the information is somewhat outdated and fragmentary. I was wondering if there is a more complete and up-to-date source?

Using the more common parameter notation $(\Delta,k)$ instead of $(k,f)$, this is equivalent to (and I think more commonly known as) the Vertex Cover problem in $k$-uniform hypergraphs of maximum degree $\Delta$.  To emphasize, for consistency with the literature I'm using $k$ where you use $f$, and $\Delta$ where you use $k$.

For any constant $\varepsilon > 0$, results ignoring $\Delta$ include

$\sup_\Delta\{ a(\Delta,k) \}\leq k$ from general set cover.
$\sup_\Delta\{ a(\Delta,k) \}\geq k-1-\varepsilon$ (Dinur et al., 2004), as noted by Lev.
If the unique games conjecture is true, then $\sup_\Delta \{a(\Delta,k)\} \geq k-\varepsilon$, which is tight (Khot & Regev, 2008).

Ignoring $k$,

$\sup_k\{ a(\Delta,k) \}\leq \Delta$ (trivial).
$\sup_k\{ a(4,k) \}\geq 2-\varepsilon$ (Holmerin, 2002)

The only result I know that combines the two parameters is

$a(\Delta,k) \leq k - (1-o(1))\left(\frac{k(k-1)\ln\ln\Delta}{\ln(\Delta)}\right)$ for fixed $k$, or $k$ growing slowly with $\Delta$ (Halperin, 2002)

There is a connection between this problem and the (Weak) Independent Set problem, but I'm not exactly sure how they're related in terms of approximability.  I would recommend investigating this, perhaps starting here: [PDF].


Oracle complexity of a problem in the Counting Hierarchy In "On The Complexity of Numerical Analysis" (SIAM J. Comp. Vol. 38, 2009), Allender et al. introduce the problem of PosSLP and show that its complexity lies in the counting hierarchy, and more precisely in
$P^{\mathit{PP}^{\mathit{PP}^{\mathit{PP}}}}$.

I have a problem, call it $X$, that I have shown can be solved in
$\mathit{NP}^{\mathit{PosSLP}}$. Can I correctly conclude that $X$ lies in
$\mathit{NP}^{\mathit{PP}^{\mathit{PP}^{\mathit{PP}}}}$?

Yes. Each time your $\sf NP$ machine want to query the $\sf PosSLP$ oracle, simply simulate the polynomial time oracle Turing machine underlying the inclusion $\sf PosSLP \subseteq {P}^{{PP}^{PP^{PP}}}$, passing its oracle queries to the $\sf {PP}^{PP^{PP}}$ oracle.


Papers every complexity theorist should read I am starting my PhD this autumn and I am planning to work in complexity theory for my thesis.

I am compiling a list of important papers that every complexity theorist should know.

What papers would you suggest to a person like me? And please briefly explain why you think the paper is important.

Ryan William's Non-uniform ACC Circuit Lower Bounds and all the results cited therein.

Not only is this a recent important result, it is a very well-written paper. Furthermore, the results the paper uses and cites cover a pretty good range of seminal complexity results. So if you trace through the references and read those as well - get to a point where you understand every part of the ACC lower bound from first principles - I would think that would be an excellent start to a graduate complexity education.


Concurrent data structures vs. Distributed data structures In the context of multi-processor/multi-threaded systems, there are plenty of well-studied concurrent data structures, including stacks, queues, linked lists, etc. Here is an excellent survey on concurrent data structures by Mark Moir and Nir Shavit.

Even though they use a "shared memory" model similar to the one used by concurrent data structures, I can only find information on a few distributed data structures: those data structures designed specifically for distributed systems. Such data structures are typically characterized by replication and certain consistency models. The examples I have found include

An Optimized Conflict-free Replicated Set (arXiv, 2012)
Randomized Shared Queues (PODC, 2001)

My questions are

What are the big challenges of designing distributed data structures (even harder than those of concurrent data structures)?
Did I miss other distributed data structures in the literature?

What are the big challenges of designing distributed data structures (even harder than those of concurrent data structures)?

Some important challenges that practically all distributed data structures face, are handling dynamic changes, implementing a scalable design, and being fault-tolerant.

This includes finding answers to questions such as:

How can we maintain/repair the properties of the data structure in the presence of churn? That is, new nodes join and old nodes leave the network over time.
Can we design the data structure  such that it is robust against faults?
How can we deal with the congestion on the communication links caused by many parallel requests?
Do the connections required per node and the necessary length of messages scale (at most) logarithmically with the system size?
Is it possible to design a system that is "spam resistant" in the sense that it can withstand attacks by adversarial nodes?

There are also locality issues since, in a distributed system, each node runs its own instance of a distributed algorithm and has only a local view of the network due to being directly connected to only a small number of other nodes. (Typically you would want a node degree of $O(\log n)$ to make the system scalable.) These issues come into play when maintaining global state such as counting the number of data items, finding the maximum, etc.

  Did I miss other distributed data structures in the literature?

DHTs: To give you some pointers, you might want to look at distributed hash tables (DHT) such as Chord, CAN, Tapestry, and Pastry.

Skip Graphs: Since you mentioned skip lists, you might be interested in skip graphs, which is a data structure providing range-queries and $O(\log n)$-time operations for lookups, inserts, etc.
The advantage of a skip graph (vs a skip list) is that a skip graph contains an expander as a subgraph with high probability.
This implies that routing can be done efficiently (i.e. link congestion is low) and that the skip graph remains connected even if a lot of nodes fail.


Why do equalities between complexity classes translate upwards and not downwards? Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the conversion (say from say $NP$ to $P$), which yields a "magic" algorithm which you can run on the padded input. While this makes technical sense, I can't get a good intuition of how this works. What exactly is going on here? Is there a simple analogy for what padding is?

Can provide a common sense reason why this is the case?

I think the best way to get intuition for this issue is to think of what the complete problems for exponential time classes are.  For example, the complete problems for NE are the standard NP-complete problems on succinctly describable inputs, e.g., given a circuit that describes the adjacency matrix of a graph, is the graph 3-colorable?  Then the problem of
whether E=NE becomes equivalent to whether NP problems are solvable in polynomial time on the
succinctly describable inputs, e.g., those with small effective Kolmogorov complexity.   This is obviously no stronger than whether they are solvable on all inputs.  The larger the time bound, the smaller the Kolmogorov complexity of the relevant inputs, so collapses for larger time bounds are in effect algorithms that work on smaller subsets of inputs.

Russell Impagliazzo


What is "Effects" in Program Graph? I have a doubt regarding the "effects" in Program Graph. Below is the image from the book Principle of Model Checking from Christel Baier and Joost-Pieter Katoen
(The MIT Press Cambridge, Massachusetts London, England)

I know what interleaving means and also I know what Effects are. As per my knowledge, effects are nothing but the result of the action on your variable (correct me if I am wrong). What does the Greek letter "η" mean?
In the book, it states that η is the evaluation, but can somebody please elaborate it me with respect to the below example?

Example 2.14. Beverage Vending Machine
The graph described in Example 2.12 (page 29) is a program graph. The set of variables is
Var = { nsoda, nbeer }
where both variables have the domain { 0, 1, . . . , max }. The set Loc of locations equals {start, select} with Loc0 = {start}, and
Act = { bget , sget, coin, ret coin, refill }.
The effect of the actions is defined by:
Effect(coin, η) = η
Effect(ret_coin, η) = η
Effect(sget, η) = η[nsoda := nsoda−1]
Effect(bget, η) = η[nbeer := nbeer−1]
Effect(refill, η) = [nsoda := max, nbeer := max]

Why is the Effect(coin, η) = η and Effect(ret_coin, η) = η?
Thank you very much.

What you wrote is correct. The actions $\textit{coin}$ and $\textit{ret_coin}$ do not change the values of the variables $\textit{Var} = \{\textit{nsoda}, \textit{nbeer}\}$, i.e., the number of soda and beer cans in the machine.

Inserting a coin is only possible in the $\textit{start}$ location, and with this action the location changes to $\textit{select}$. If you’re wondering how the machine keeps track of payment at all, this is it: By the PG's two locations.
Only after the user selects a beverage, a can is dispensed, and the variable evaluation changes (the effect of $\textit{[sb]get}$).

Similarly, returning the coins (which can only happen in the case the vending machine has neither beer nor soda cans) does not change the number of cans.

You could propose a different model that does track the exact amount of coins inserted as a variable, and define

$\textit{Effect}(\textit{coin},η) = η[\textit{coins_inserted} := \textit{coins_inserted} + 1]$ as well as
$\textit{Effect}(\textit{ret_coin},η) = η[\textit{coins_inserted} := 0]$

but the example given does not do so.


Algorithms on graphs represented using BDDs The simplest representations for graphs use adjacency matrices/lists, meaning that each node and edge is explicitly represented. The importance of implicit representations for graphs exhibiting strong regularities has long been recognized. For instance, Galperin & Wigderson (1983), Papadimitriou & Yannakakis (A Note on Succinct Representations of Graphs, 1986) explored the question of graphs whose adjacency matrix is represented by a Boolean formula answering whether or not (i,j) is an edge given the binary representation of the node numbers i and j. Under some commonly satisfied constraints on reductions, P-complete problems for explicit graphs become PSPACE-complete for this representation, NP-complete problems become NEXPTIME-complete, etc.

A natural approach to such regular graphs is to represent the Boolean formula using a ROBDD; the difficulty is that classical algorithms tend to enumerate nodes one by one, which incurs exponential cost on such a representation and thus is to be avoided. There have been papers published on classical problems being solved using such a representation, e.g. Gentilini et al. (Computing strongly connected components in a linear number of symbolic steps), Woelfel (Symbolic topological sorting with OBDDs).

I'm wondering whether there is some survey of such techniques, because it's inconvenient to dredge the literature in such of the state of the art...

You may find this link is useful.
http://www.andrew.cmu.edu/user/vanhoeve/mdd/


Obituaries of dead conjectures I am looking for conjectures about algorithms and complexity that were viewed credible by many at some point in time, but later they were either disproved, or at least disbelieved, due to mounting counter-evidence. Here are two examples:

Random oracle hypothesis: relationships between complexity classes that hold for almost all relativized worlds, also hold in the unrelativized case. This was disproved by the result $IP=PSPACE$, and by showing that $IP^X\neq PSPACE^X$ holds for almost all random oracles $X$, see The Random Oracle Hypothesis is False.
Bounded error randomness properly extends the power of polynomial time (i.e., $P\neq BPP$). This was believed for a while, but later, due to sophisticated derandomization results and their connections to circuit complexity,  the opposite conjecture ($P=BPP$) has become prevalent (although still open).

Which are some other conjectures that failed the test of time?

$\mathsf{NL} \neq \mathsf{coNL}$. Prior to the result that these two were equal, I think it was widely believed that they were distinct, by analogy with the belief that $\mathsf{NP} \neq \mathsf{coNP}$ (i.e. the general principle that "nondeterministism and co-nondeterminism are different"; this turned out to be false under space complexity bounds that were at least logarithmic).


Hamming weight of powers Given positive integers $b$ and $e$, what is known about the space and time complexity of finding the Hamming weight (number of binary 1s) of $b^e$?

If $e\log b$ bits are available, the number can simply be calculated by standard techniques and the 1s counted.  But what techniques are possible when less memory can be used?

This answer expands my comment above.

You can do it with $O(\log e + \log \log b)$ space as follows:

1) First compute $b^e$ in Chinese remainder representation modulo sufficiently many primes.

2) Then use the Chiu-Davida-Litow algorithm to convert the Chinese remainder representation into binary representation. (Informatique Theoretique et Applications, Vol 35(3), pages 259-275, 2001)

3) Finally, just count the number of $1$'s.

This is a composition of a finite number of log-space computable functions, which is itself log-space computable.


Why doesn't P=NP imply P=AP (i.e. P=PSPACE)? It is well known that if $\mathbf{P}=\mathbf{NP}$ then the polynomial hierarchy collapses and $\mathbf{P}=\mathbf{PH}$.

This can easily be understood inductively using oracle machines.
The question is - why can't we continue the inductive process beyond a constant level of alternations and prove $\mathbf{P}=\mathbf{AltTime}(n^{O(1)})$ (aka $\mathbf{AP}=\mathbf{PSPACE}$)?

I am looking for an intuitive answer.

The proof for $\mathbf{P}=\mathbf{AltTime}(O(1))$ ($=\mathbf{PH}$) is an induction using $\mathbf{P}=\mathbf{NP}$. The induction shows that for any natural number $k$, $\mathbf{P}=\mathbf{AltTime}(k)$ (and $\mathbf{AltTime}(O(1))$ is just their union).

The induction does not work when the number of alternation can change with the input size (i.e. when the number of possible alternations of the machine is not a number but a function of the input size, i.e. we are not showing that an execution of the machine on a single input can be reduced to no alternation, we are showing that the executions of the machine on all inputs can be "uniformly" reduced to no alternation).

Let's look at a similar but simpler statement. We want to show that the identity function $id(n)=n$ eventually dominates all constant functions ($f \ll g$ iff for all but finitely many $n$ $f(n) \leq g(n)$). It can be proven say by induction. For all $k$, $k \ll n$ (i.e. $f_k \ll id$ where $f_k(n)=k$), but we don't have this for non-constant functions like $n^2$, $n^2 \not \ll n$.