The complexity of Area-lawed Hamiltonians I have recently thought about "importing" some physics-related question into quantum CS:

The notion of the area-law phenomenon in Hamiltonian systems usually stands for a local Hamiltonian on some lattice, whose groundstate exhibits a property in which entanglement of any closed region is proportional to the surface of the region, and not its volume (as it would for a general state).
A famous conjecture is whether all constant-gapped Hamiltonians exhibit this area-law property.
For 1-dimensional systems, this question was answered in the positive by Hastings (arXiv:0705.2024).

Yet, the connection between such systems and complexity theory is very vague: while Hastings' result implies that 1-D area-law-abiding systems can be classically simulated, for general systems this is unknown.
So my question is, is the quest to solve the area-law conjecture worthwhile?
Or adversarially put, can one come up with a QMA-complete local Hamiltonian which is also area-law-abiding.
A small glance at the known QMA-complete local Hamiltonians, which are essentially all based on Kitaev's quantum Cook-Levin theorem yields that these Hamiltonians do not have the area law property.

One could consider the following slightly silly example of a 2d system which obeys an area law which is QMA-complete.  Take a 2d system, one row of which is equal to one of the known QMA-complete 1d Hamiltonians (see Aharonov, Gottesman, Irani, Kempe), and all the other rows are in a product state.  Then, this obeys an area law (consider drawing a rectangle which includes the given row, with k rows and l columns; the entanglement is bounded by a constant times l and the area is also at least equal to l).

However, this, in my opinion, certainly doesn't mean that proving an area law in 2d would be pointless from the point of view of complexity.  Rather, I think it means that we need to consider not just the area law for entanglement entropy, but other entanglement properties also.  One such property would be having a PEPS of polynomial bond dimension.  Actually, proving that there is an area law in 2d does not imply having a PEPS of polynomial bond dimension.  The implication in 1d relies on the fact that we can cut the system across various bonds, truncate to a polynomial Schmidt rank across each bond, and bound the error.  This procedure doesn't work in 2d.  So, proving the existence of a PEPS for a gapped system in 2d would be a next step.  My feeling is that proving an area law in 2d would be a good first step to doing that.

In fact, it is well-studied in condensed matter physics that there exist gapless 2d Hamiltonians which obey an area law.  While in 1d, the systems which are described by conformal field theory have a logarithmic behavior of the entanglement entropy, in 2d many critical systems show an area law and then the logs show up in subleading behavior, so the entropy is equal to L + const*log(L)+...  That is, the interesting, universal terms in the entropy are not the leading terms, but the subleading, in such 2d theories.


Is it hard to find optimal addition chains? An addition chain is a sequence of positive integers $(x_1, x_2, \dots, x_n)$ where $x_1 = 1$ and  each index $i\ge 2$, we have $x_i = x_j + x_k$ for some indices $1\le j,k < i$.  The length of the addition chain is $n$; the target of the addition chain is $x_n$.

What is known about the complexity of the following problem: Given an integer $N$, what is the length of the shortest addition chain whose target is $N$?  Is it NP-hard?

Wikipedia points to a 1981 paper by Downey, Leong, and Sethi that proves the following related problem is NP-hard: Given a set of integers what is the minimum length of an addition chain that includes the entire set?  Several authors apparently claim that this paper proves the single-target problem is NP-hard, but it doesn't.

The problem is mentioned as being open in Eric Lehman's PhD thesis "Approximation algorithms for grammar-based data compression" in 2002. From p35 of the thesis:

"Nevertheless, an exact solution to the addition chain problem remains strangely elusive. The M-ary method runs in time polylog(n) and gives a 1 + o(1) approximation. However, even if exponentially more time is allowed, poly(n), no exact algorithm is known."


Implemented code to compute pathwidth (= Node search number, vertex separation number, interval thickness) I am looking for an implementation of an algorithm to compute the pathwidth of a graph. It is well known that computing the pathwidth is equivalent to computing the node searching number, vertex separation number, or interval thickness of the graph. The algorithm does not have to be very fast; I want to run it on graphs of at most 20 vertices. I do require the algorithm to compute the pathwidth exactly, rather than giving an approximation.

I am aware that there are some implementations to compute the treewidth of a graph (a related concept) but have not been able to find any to compute the pathwidth. Any pointers are appreciated!

Don't know about "an implementation" but check out

Computing Pathwidth Faster Than 2^n
Karol Suchan and Yngve Villanger
Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009,Copenhagen, Denmark, Springer Verlag, Lecture Notes in Computer Science 5917, Pages 324-335.


Costs of performing approx. nearest neighbor search in a skip quadtree NOTE: The question has been restated in my answers: Assuming now that we can find the lowest sibling ancestors in $O(1)$ time, can the ANN be really performed in $O(\log n)$?

Quadtrees are efficient spatial indices. I have a puzzle with the implementation of a nearest neighbour search in a compressed quadtree structure as described in [2]. (Without going into details, the search is going top-down along so-called equidistant squares, ending in the tail node of an equidistant path. In the attached image this might be any of the nodes in the southeast filled with points.)

For their algorithm to work, one must maintain for each node -- a square with at least two non-empty quadrants -- pointers for each lowest (closest in the hierarchy) ancestor node in each of the four directions (north, west, south, east). These are indicated by the green arrows for the nodes' westward ancestor (the arrow points at the ancestor square's centre).

The paper claims these pointers can be updated in O(1) during point insertions and deletions. However when looking at the insertion of the green point, it seems I need to update any arbitrary number of pointers, in this case six of them.

I am hoping for a trick to do this pointer update in constant time. Maybe there is a form of indirection that can be exploited?

EDIT:

The relevant section from the paper is 6.3, where it reads: "if the path has bends, then in addition to the $log(c/ε)$ lowest ancestors of $q$, we should also consider for each of the $2^d$ directions the lowest ancestor of $q$ that goes towards that direction [...] Finding these squares from $q$ can be done in $O(1)$ time per square if we associate additional $2^d$ pointers to each square in $Q_0$ pointing to its closest ancestors for each direction. These pointers can also be updated in $O(1)$ time during an insertion or deletion of a point."

[2]: Eppstein, D. and Goodrich, M.T. and Sun, J.Z., “The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data,” in Proceedings of the twenty-first annual symposium on Computational geometry, pp. 296—305, 2005.

Like David, I don't know why Jonathan put in that remark about the 2^d pointers. They are not needed. As David mentioned above, the essential property is that when we are doing a point location to a leaf v in Q_0, it is sufficient to remember the sibling nodes (and their boxes) in the skip quadtree. When we process a box from P, we do a point location for the leaf box closest to our query point, inserting the sibling boxes as we go down. It sounds like this would be more or less the same as your answer. In addition, this procedure is very similar, for instance, to how approximate point location is done in the following paper:
Arya, Sunil and Mount, David M. and Netanyahu, Nathan S. and Silverman, Ruth and Wu, Angela Y., "An optimal algorithm for approximate nearest neighbor searching fixed dimensions", JACM, 1998.
Indeed, the skip quadtree (without those extra pointers) satisfies their conditions (a)-(e) that allow for fast approximate nearest-neighbor searching.


Barendregt's proof of subject reduction for $\lambda2$ I found a problem in Barendregt's proof of subject reduction (Thm 4.2.5 of Lambda calculi with types).

The last step of the proof (page 60), says:

"and hence by Lemma 4.1.19(1), $\quad\Gamma,x:\rho\vdash P:\sigma'$."

However, according to Lemma 4.1.19(1) it should be $\Gamma[\vec{\alpha}:=\vec{\tau}],x:\rho\vdash P:\sigma'$, since the substitution is made to the whole context, not only to $x:\rho'$.

I guess the standard solution may be to somehow prove that $\vec{\alpha}\notin FV(\Gamma)$, but I am not sure how.

I had a proof simplifying it by relaxing the generation lemma of abstractions, but I recently found that there was a mistake and my proof is wrong, so I am not sure how to solve this problem any more.

Can somebody, please, tell me what I am missing here?

I still think there is an imprecision in how he uses the lemma. However there is a solution (I must thank to Barbara Petit who came with the solution).

In fact, the solution comes from the definition of $\geq$ (def. 4.2.1), which is morally this:

$\sigma>\rho\quad$ if $\quad\dfrac{\Gamma\vdash P:\sigma}{\Gamma\vdash P:\rho}$

However, instead of defining it in that way, he defines the relation in terms of the types only. The advantage on defining it in terms of sequents, is that we can deduce that if $\sigma>\forall\alpha.\sigma$, then $\alpha\notin FV(\Gamma)$, which is exactly what he needs in the proof (and from where the imprecision comes).


Where's the Flaw in Blum-Feldman-Micali's Method Blum, Micali, and Feldman (BFM) put forward a new (cryptographic) model, in which all parties (honest or adversarial) have access to some string. The string is assumed to be selected according to some distribution (usually, uniform distribution) by a trusted party. It is called the reference string, and the model is aptly named the common reference string (CSR) model.

The model allows us to perform many interesting interactive protocols non-interactively, replacing queries by bits from the reference string. In particular, zero-knowledge proofs for any NP language can be conducted non-interactively, giving rise to the notion of non-interactive zero-knowledge (NIZK).

NIZK has a lot of applications, such as providing a method for realizing public-key cryptosystems secure against (adaptive) chosen-ciphertext attacks.

BFM first proved the existence of a single-theorem version of NIZK for every NP language; that is, given a reference string $\rho$ and a language $L \in \bf{NP}$, one can prove only one single theorem of the form $x \in L$. In addition, the length of the theorem is bounded in $|\rho|$. If the prover attempts to reuse some bits of $\rho$ in later proofs, there's a danger of knowledge leakage (and the proof will no longer be NIZK).

To remedy this, BFM used a multi-theorem version based on the single-theorem NIZK. To this end, they used a pseudo-random generator to expand $\rho$, and then used the expanded bits. There are some other details as well, but I'm not going to dig in.

Feige, Lapidot, and Shamir (in the first footnote on the first page of their paper) stated:

  The method suggested in BFM for overcoming this difficulty was found to be flawed.

(The difficulty refers to obtaining multi-theorem proofs rather than single-theorem ones.)

  Where does the BFM flaw lie?

I have not read the details of their flawed protocol, but I've heard about it on several occasions.  My impression was that their error was in how they used the PRG seed.  Their protocol puts the pseudorandom generator (PRG) seed in the public common reference string, and they attempt to argue that PRG security forces some statistical property of the PRG output to hold even with a known seed.  While it is possible to do this in a sound way (the signature schemes of Hohenberger and Waters here and here spring to mind), something went wrong in their argument.


Non uniform NC-hierarchy collapse? Jianer Chen's paper "Characterizing parallel hierarchies by reducibilities" Information Processing Letters 39(1991) 303-307 shows the theorem:

If $NC^{k+1} = NC^k$ then we have $NC = NC^k$

His proof is for uniform circuit classes. What is for non uniform classes? Does the result still hold?

Suppose that every circuit of depth $C\log^{k+1} n$ and size $Dn^\ell$ can be converted to an equivalent circuit of depth $C'\log^k n$ and size $D' n^{\ell'}$.

Now suppose we are given a circuit of depth $C\log^{k+2} n$ and size $Dn^\ell$, and assume furthermore that it's a levelled circuit (making a circuit levelled only increases the size polynomially). Make a list of all nodes at levels $C\log^{k+1} n,2C\log^{k+1} n,\ldots,C\log^{k+2} n$. A node at level $\alpha C\log^{k+1} n$ is the value of a circuit of depth $C\log^{k+1} n$ and size at most $Dn^\ell$ whose leaves are nodes at level $(\alpha+1)C\log^{k+1}n$. We can replace each of these circuits by an equivalent circuit of depth $C'\log^k n$ and size $D' n^{\ell'}$. In total, the new circuit will have depth $C'\log^{k+1} n$ and size at most $DD' n^{\ell+\ell'}$. This shows that $NC^{k+1} = NC^k$ implies $NC^{k+2} = NC^{k+1}$.


Does there exist a sentence of first-order logic that is satisfiable only in infinite models that do not have a finite algorithmic representation? There exist sentences of first-order logic that are satisfiable and are satisfiable only by models of infinite size. However, all such sentences I can think of are satisfied by infinite models that can be generated by a non-terminating algorithm of a finite size.

For a example, there exists a sentence of first-order logic that is satisfied only by a model of an infinite size:

$$ \exists x \lnot \exists y S ( y, x ) \land $$
$$ \forall x \exists y S ( x, y ) \land $$
$$ \forall x \forall y \forall z ( ( S ( x, z ) \land S ( y, z) ) \to x = y ) $$

A model for this sentence can be generated (listed, enumerated) by a finite algorithm that never terminates - just list the elements of the infinite model in a sequence one after another and make $S$ hold only for successive pairs of such elements.

Does there exist a sentence of first-order logic that is satisfiable only in some infinite models for which there does not exist a finite algorithm that generates them?

One possible answer to your question is Tennenbaum's Theorem. It states that no non-standard model of arithmetic can have only computable operations, i.e. either addition or multiplication will be non-computable given any recursive description of the elements of the model.

Now the remaining difficulty is having a single formula which has as models only non-standard models of arithmetic. Note that while arithmetic isn't finitely axiomatizable, there are conservative extensions of PA which are finite.

Now it's easy to build an infinite axiomatization of (an extension of) PA which has only non-standard models: add to PA a constant $c$ and the axioms
$$ c\neq 0,\ c\neq S(0),\ c\neq S(S(0)),\ldots$$

There's a trick to turn this into a finite axiom. Add the binary predicate $\mathrm{NS}$ to your language, along with the axiom
$$ \forall xy,\ \mathrm{NS}(x, y)\leftrightarrow x\neq y\wedge \mathrm{NS}(x, S(y))$$
Then the above schema is expressed by $\mathrm{NS}(c, 0)$.

Important edit: It is crucial that the induction schema (as axiomatized by your finite theory) does not apply to formulas containing $\mathrm{NC}$! Otherwise it is quite easy to show $\forall y,\ c\neq y$ and conclude $c\neq c$, a contradiction. I think that if you exclude those formulas from the induction principle, the above reasoning should go through without trouble.


Source Coding Theorem: what happen when we go below N*H(x) bits? I was following the textbook by David Mackay: Information theory inference and learning algorithms.

I have question on Shannon's source coding theorem (p81):

  $N$ i.i.d. random variables each with entropy $H(x)$ can be compressed into more than $N \cdot H(x)$ bits with negligible risk of information loss, as $N \to\infty$; conversely if they are compressed into fewer than $N \cdot H(x)$ bits it is virtually certain that information will be lost.

My question is the bold part of the above: what happens when you go below $N \cdot H(x)$ bits?

There is an example in the textbook (p77), where he shows that, as $N$ increases, the average entropy per symbol approaches $H(X)$, for a risk tolerance $0 \lt \delta \lt 1$. (So it becomes flatter as indicated on the diagram.) Therefore,  $N \cdot H(x)$ is the number of bits you can compress no matter how much risk tolerance you are willing to take.

In the definition above, however, it is saying that information will be lost if you go below $N \cdot H(X)$. My question is, how much information will be lost?

I found something on the web regarding this question: http://www.kim-bostroem.de/Library/Notes/Shannon.pdf

It is saying that for each symbol, if you compress below $H(x)$ bits, then               for $N \to\infty$, we will lose all the information. Can someone please confirm this?

It's not clear exactly what your question is. What the textbook is talking about is the strong converse to Shannon's source coding theorem, but rate distortion theory is another part of information theory relevant to this.

The strong converse says that if you try to compress information to fewer bits than the entropy, the probability that all of the information is restored correctly goes to zero as $N$ goes to $\infty$ (the theorem also gives you a bound on this probability).

Rate distortion theory answers the question: I have a signal that I want to compress to a length that is shorter than its entropy. How small an amount of distortion can I introduce into the signal to ensure that I can recover it with high probability? You can use this theory with an arbitrary formula for distortion (and there is a nice formula if the distortion is given by a single-symbol equation).

And of course, if you compress the source to $K$ bits, than you can choose $K/H(X)$ symbols of the original to keep and discard all the others.


Fastest polynomial time algorithm for solving minimum cost maximum flow problems in bipartite graphs Orlin's algorithm is known to solve minimum cost maximum flow problems in $O(|E|^2 \log |V| + |E| \; |V| \log^2 |V|)$ time, where $|E|$ and $|V|$ respectively denote the cardinalities of the edge and the node sets of the graph $G(V, E)$ in question.

If the graph $G(V = V_1 \cup V_2, E)$ is known to be bipartite (with $V_1$ and $V_2$ denoting the "left" and "right" node sets), can one compute the minimum cost maximum flow any faster? Here the flow is between an additional source that is connected to the nodes in $V_1$ and an additional sink that is connected to the nodes in $V_2$.

I'm also interested to hear about algorithms that do not have better time complexity, but perform well in practice.

You can assume that all capacities and costs are non-negative integers. There can be both limited-capacity and unlimited-capacity edges in the graph. Also, assume that both the maximum non-infinite capacity $c$, and the maximum edge cost $w$ is small; i.e. one can consider both as $O(1)$ terms for complexity purposes.

Thanks!

Edit: My current-best solution is to use a minimum cost augmentation algorithm, which solves the problem in $O(|E| \; F \log |V|)$ time, where $F$ is the value of the maximum flow. Since $F$ is bounded by $c \;|V|$ (which is $O(|V|)$ under our assumptions), this approach results in an overall time complexity of $O(|E| \; |V| \; \log |V|)$. Is it possible to beat this?

See this paper. I think adopting their technique, many(usually scaling based) min-cost flow algorithms with running time $O(f(n,m))$ can run in $O(f(n_1,m))$ time. Here $n_1$ is the size of the smaller bipartition.

If $f(n,m)$ is the best possible run time for min-cost flow on general graphs with $n$ vertices and $m$ edges. There is an easy argument that you can't expect anything running in $o(f(n_1,m))$ time. (with some reasonable assumptions, like $n\leq m$, $f(n,cm)=O(f(n,m))$ for any constant $c$)

Proof: Otherwise, you can apply the standard vertex splitting operation to the input graph and use the bipartite min-cost flow algorithm and get a better running time.

Finally, if you are restricting cost and capacities things, these scaling algorithms is still pretty much state of the art(difference is at most $\log c$ for w/e parameter $c$ you care about). You can decipher that Theorem 3.5 to see which one of them gives you the best result.


Variation on longest path in a DAG Consider a directed acyclic graph with $n$ nodes and $m$ edges. Each edge is assigned a positive weight. There is a start node $s$ and an end node $e$. We want to find the path from $s$ to $e$ that has the maximum number of nodes such that

  the total distance is less than some constant $d$, and
  starting from $s$, each node in the path is closer than the previous one to the node $e$. (As in, when you traverse the path you are getting closer to your destination $e$ in terms of the edge weight of the remaining path.)

Does a polynomial time algorithm already exist for this problem? Is there a formal name for this problem?

You could solve it using a dynamic programming approach:

First lay out vertices in a topological order like $v_1, v_2, ..., v_n$. If start and end vertices are  $s=v_a$ and $e=v_b$, you could get rid of all vertices after $v_b$ and before $v_a$. So let's assume $s=v_1$ and $e=v_n$. Next, define $L_{i,j,p}$ to be the shortest path between $v_i$ and $v_j$ which has $p$ nodes. In other words, among paths between $v_i, v_j$ which have $p$ nodes, it's the length of shortest one. Assume $w_{i,j}$ is the weight between $v_i, v_j$, and it is infinity if there is no edge. Now

Set $L_{i,i,1}=0$.
For $p>1$ we have $L_{i,j,p} = min_k \{L_{i,k,p-1}+w_{k,j} \}$, where  $i\le k<j$.

Now the final answer is $max\{k\}$ for all $k$s that we have $L_{1,n,k}<d$. The table (actually half of it need to be filled, because $i<j$) has $n^3$ elements, and for each element $O(n)$ time it takes to be computed. So the time complexity will be $O(n^4)$, but guess tighter bounds could be achieved.

UPDATE: As Neals pointed out in the comments an $O(n^2 m)$ bound is achievable. Also the algorithm can be thought of as a LDP algorithm running on transformed graph $G'$: make $n$ copies of the original graph $G$ and for each edge $e=(v,w)$ in $G$ connect the $i$th copy of $v$ and $(i+1)$th copy of $w$, for $1 \le i < n$.


Implementations of Undirected Disjoint Paths I'm looking into the Undirected Vertex Disjoint Paths problem:

  Given a list of tuples of vertices (s_i, t_i)

  Find simple, pairwise disjoint paths P_{s_0,t_0}, P_{s_1,t_1}, ... that connects the given vertices. If they exist.

I'm in particular interesting in implementing a solution to this this for grid meshes. A situation that comes up in many pen+paper puzzles. I know this will be NP hard in the list of tuples, but hopefully not in the size of the graph.

I know about the Robertson-Seymour theorem, and its complications. However I'm wondering if the required minors might be well known for say planar graphs or meshes?

I also found mentions that Schrijver has made a more approachable polynomial algorithm, but I haven't been able to find mentions of complexity in terms of implementation.

Can anyone point me in a good direction?
I'd be interested even in solutions for just two pairs.

If you want an implementation, Sage has one. With a LP, as usual ;-)

http://www.sagemath.org/doc/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.disjoint_routed_paths

Nathann


Automatic proofs or model checking in an extremely simplified functional language Imagine a stripped down functional programming language, that has the following properties

The only value type is an integer
There are no side effects
Functions are defined as a single expression, value of which becomes the return value of the function.
Program consists of zero or more function definitions and an expression. The expression can be defined in terms of the previously defined functions. Value of that evaluated expression is the result of the program.
Aside from simple arithmetic, there is only an if then else fi expression
The only way to do looping is through recursion

A program can then look like

f(x) = r(x+1,1)
r(x,y) = if x-(y*y) then r(x,y+1) else y*y fi

f(2)

so f() computes the second power of the given argument.

My question is, whether it is possible with current automated tools to prove theorems about such programs without human assistance. And what exactly?

Is it for example possible to automatically say for sure that for two functions f and g for every x: f(x) = g(x) ?

The ACL2 system includes all of the features of your language, and supports impressive automated theorem proving about program in that language.

In ACL2, you would write the theorem you describe as:

(defthm f-g-equal (equal (f x) (g x)))

having previously defined f and g.


Quantum oracle implementation overhead I am a physicist  getting acquainted with one of the typical constructs for formulation and analysis of quantum algorithms (such as search problems or query complexity models), namely the "oracle function". As far as I understand, the oracle is a quantum black-box entity which computes the quantity to be analyzed. For example, in a qubit circuit formulation of a universal quantum computer the oracle is a deterministically computed Boolean function (correct me here if I'm wrong).

My question is:

Is quantum oracle implementation overhead counted when the
computational complexity of specific/well-known algorithms is compared to
alternatives?

Examples: deterministic Deutsch-Jozsa algorithm algorithm is exponentially faster than a classical counterpart only if the implementation of the unknown function $f$ requires less than $2^n$ classical "steps'' (including obtaining the guarantee that $f$ is either partial or constant). A stochastic example: collapse of the Grover algorithm speedup by a faulty oracle with an arbitrary small but constant failure probability.

Why do one care: Of course, one can alsways say that we look just at the non-oracle part or count only the number of queries etc. But any talk of quantum speedup has any chance of empirical relevance only if the overhead for implementation of all of the quantum parts of the construction is taken into account (if it is trivial/constant - no problem). In other words, I find it meaningful to compare quantum algorithms only after they are "fully compiled'' onto (at least hypothetically) realizable classically-driven hardware (e.g., universal set of gates plus as many qubits as one needs - but we'll count all the time & memory required).

My question is probably fairly typical for a non-expert, perhaps I just got confused by some less sophisticated introductions to quantum computation. Please deconfuse me.

As  pointed out by Logan Mayfield, Scott Aaronson's blogpost on the topic completely resolves my question. Oracles is a fundamental tool for rigorous investigation of computational complexity classes,

  “bring out the latent strengths” of one class over another class.

The root cause of my concerns was that little (as far as I understand - nothing) can be proven unconditionally about quantum speedups in the unrelativized (compiled to physical hardware) world. Of course, this obstacle does not diminish the power of the oracle framework as a major tool enabling progress in quantum computation theory, including the celebrated example of Shor's algorithm.

Personally, it is a consolation to learn from Scott that

  This [relativized vs. unrelatized complexity] is an absolutely crucial distinction that trips up just about
  everyone when they’re first learning quantum computing.


Examples of the price of abstraction? Theoretical computer science has provided some examples of "the price of abstraction."  The two most prominent are for Gaussian elimination and sorting.  Namely:

It is known that Gaussian elimination is optimal for, say, computing the determinant if you restrict operations to rows and columns as a whole [1].  Obviously Strassen's algorithm does not obey that restriction, and it is asymptotically better than Gaussian elimination.
In sorting, if you treat the elements of the list as black boxes that can only be compared and moved around, then we have the standard $n \log n$ information-theoretic lower bound.  Yet fusion trees beat this bound by, as far as I understand it, clever use of multiplication.

  Are there other examples of the price of abstraction?

To be a bit more formal, I'm looking for examples where a lower bound is known unconditionally in some weak model of computation, but is known to be violated in a stronger model.  Furthermore, the weakness of the weak model should come in the form of an abstraction, which admittedly is a subjective notion.  For example, I do not consider the restriction to monotone circuits to be an abstraction.  Hopefully the two examples above make clear what I'm looking for.

[1]  KLYUYEV, V.V., and N. I. KOKOVKIN-SHcHERBAK: On the minimization of the
number of arithmetic operations for the solution of linear algebraic systems of
equations. Translation by G. I. TEE: Technical Report CS 24, June t4, t965,
Computer Science Dept., Stanford University.

Another beautiful example of the price of abstraction: network coding. It's known that in multicast settings, the max-flow-min-cut relation is not one of equality (the primal and dual don't match). However, the traditional models assume flow that's merely passed on and not "processed" in any way. With network coding, you can beat this limit by cleverly combining flows. This example was a great motivator for the study of network coding in the first place.


Transition Diagram of a Universal Turing Machine I have searched the web for the transition diagram of a universal Turing machine without luck. Is anyone aware of such a diagram?

I need this as a reference, so preferably a book or a published article. I don't want anything strange, just a standard Turing Machine with one tape that computes the Universal Turing Machine. The tape will contain a Turing machine and an input string. The rest of the tape is filled with blank.

I would prefer historic references.

Here are some references:

Claude Shannon, "A universal Turing machine with two internal states", 1956.
Marvin Minsky, "A 6-symbol 6-state Universal Turing Machine", 1960.
Shigeru Watanabe, "5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines", 1961.

Also Odifreddi writes ["Classical Recursion Theory", vol I, p. 133]:

  "..., and explicit constructions of universal Turing machines are in Turing
  [1936], Wang [1957a] and in many textbooks, e.g. Hermes [1965], Minsky
  [1967], Arbib [1969], Hopcroft and Ullman [1979]. More information on
  the topic is in Davis [1956], [1957], Shannon [1956], Rogers [1967]
  and Priese [1979]."


Cutting-sticks puzzle Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2.

Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time?

Surprisingly, the only reference I find for this problem is this ancient discussion:

http://www.iwriteiam.nl/cutsticks.html

What else is known about the problem? Can we prove the problem to be `in the limbo'?

Update: The cutting-sticks problem has the constraint that each stick is at least $n$ units long. (See the comments and Tsuyoshi's answer for the unconstrained case).

Caution: As Jukka Suomela commented on the question, the page linked from the question is about a problem different from the problem stated in the question in that the problem on the page has a restriction that the lengths of given sticks are greater than or equal to n.  This answer is about the problem without this restriction.  Since Emil’s comment on the question refers to the problem with the restriction, there is no contradiction between his comment and the following answer.

The problem is NP-complete, even if the numbers are given in unary.

The 3-partition problem is the following problem:
Instance: Positive integers a1, …, an in unary, where n=3m and the sum of the n integers is equal to mB, such that each ai satisfies B/4 < ai < B/2.
Question: Can the integers a1, …, an be partitioned into m multisets so that the sum of each multiset is equal to B?

The 3-partition problem is NP-complete even if a1, …, an are all distinct [HWW08] (thank you to Serge Gaspers for telling me about this).  It is possible to reduce this restricted version of the 3-partition problem to the problem in question as follows.

Suppose that we are given an instance of the 3-partition problem consisting of distinct positive integers a1, …, an.  Let m=n/3 and B=(a1+…+an)/m, and let N be the maximum among ai.  Consider the following instance of the stick problem: the instance consists of one stick of length k for each k∈{1, …, N}∖{a1, …, an} and m sticks of length B.  By using the fact that each ai satisfies ai > B/4 ≥ N/2, it is easy to prove that this stick problem has a solution if and only if the instance of the 3-partition problem has a solution.

References

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger.  Multigraph realizations of degree sequences: Maximization is easy, minimization is hard.  Operations Research Letters, 36(5):594–596, Sept. 2008.  http://dx.doi.org/10.1016/j.orl.2008.05.004


Proof of the pumping lemma for context-free languages using pushdown automata The pumping lemma for regular languages can be proved by considering a finite state automaton which recognizes the language studied, picking a string with a length greater than its number of states, and applying the pigeonhole principle. The pumping lemma for context-free languages (as well as Ogden's lemma which is slightly more general), however, is proved by considering a context-free grammar of the language studied, picking a sufficiently long string, and looking at the parse tree.

Given the similarity of the two pumping lemmas, you would expect that the context-free one can also be proved in a similar way to the regular one by considering a pushdown automaton which recognizes the language, rather than a grammar. However, I didn't manage to find any reference to such a proof.

Hence my question: is there a proof of the pumping lemma for context-free languages which only involves pushdown automata and not grammars?

I thought about this problem again, and I think I have a full proof. It is a bit more tricky than what I anticipated. Comments are very welcome! Update: I submitted this proof on arXiv, in case this is useful to someone: http://arxiv.org/abs/1207.2819

$\DeclareMathOperator{\fp}{fp}$
$\DeclareMathOperator{\lp}{lp}$
$\newcommand{\fpp}[1]{\widehat{\fp{#1}}}$
$\newcommand{\lpp}[1]{\widehat{\lp{#1}}}$

Let $L$ be a context-free language over an alphabet $\Sigma$. Let $A$ be a
pushdown automaton which recognizes $L$, with stack alphabet $\Gamma$. We denote
by $|A|$ the number of states of $A$. Without loss of generality, we can assume
that transitions of $A$ pop the topmost symbol of the stack and either push no
symbol on the stack or push on the stack the previous topmost symbol and some
other symbol.

We define $p' = |A|^2 |\Gamma|$ and $p = |A| (|\Gamma|+1)^{p'}$ the pumping
length, and will show that all $w \in L$ such that $|w| > p$ have a
decomposition of the form $w = u v x y z$ such that $|vxy| \leq p$, $|vy| \geq
1$ and $\forall n \geq 0, u v^n x y^n z \in L$.

Let $w \in L$ such that $|w| > p$. Let $\pi$ be an accepting path of minimal
length for $w$ (represented as a sequence of transitions of $A$), we denote its
length by $|\pi|$. We can define, for $0 \leq i < |\pi|$, $s_i$ the size of the
stack at position $i$ of the accepting path. For all $N > 0$, we define an
$N$-level over $\pi$ as a set of three indices $i, j, k$ with $0 \leq i
< j < k \leq p$ such that:

$s_i = s_k, s_j = s_i + N$
for all $n$ such that $i \leq n \leq j$, $s_i \leq s_n \leq s_j$
for all $n$ such that $j \leq n \leq k$, $s_k \leq s_n \leq s_k$.

(For an example of this, see the picture for case 2 below which illustrates an $N$-level.)

We define the level $l$ of $\pi$ as the maximal $N$ such that $\pi$ has an
$N$-level. This definition is motivated by the following property: if the size
of the stack over a path $\pi$ becomes larger than its level $l$, then the stack
symbols more than $l$ levels deep will never be popped. We will now distinguish
two cases: either $l < p'$, in which case we know that the same configuration
for the automaton state and the topmost $l$ symbols of the stack is encountered
twice in the first $p+1$ steps of $\pi$, or $l \geq p'$, and there must be a
stacking and unstacking position that can be repeated an arbitrary number of
times, from which we construct $v$ and $y$.

Case 1. $l < p'$. We define the configurations of $A$ as the couples
of a state of $A$ and a sequence of $l$ stack symbols (where stacks of size less
than $l$ with be represented by padding them to $l$ with a special blank symbol,
which is why we use $|\Gamma| + 1$ when defining $p$). By definition, there are
$|A| (|\Gamma| + 1)^l$ such configurations, which is less than $p$. Hence, in
the $p+1$ first steps of $\pi$, the same configuration is encountered twice at
two different positions, say $i < j$. Denote by $\widehat{i}$ (resp.
$\widehat{j}$) the position of the last letter of $w$ read at step $i$ (resp.
$j$) of $\pi$. We have $\widehat{i} \leq \widehat{j}$. Hence, we can factor $w =
u v x y z$ with $y z = \epsilon$, $u = w_{0 \cdots \widehat{i}}$, $v =
w_{\widehat{i} \cdots \widehat{j}}$, $x = w_{\widehat{j} \cdots |w|}$. (By $w_{x
\cdots y}$ we denote the letters of $w$ from $x$ inclusive to $y$ exclusive.) By
construction, $|vxy| \leq p$.

We also have to show that $\forall n \geq 0, u v^n x y^n z = u v^n x \in L$, but
this follows from our observation above: stack symbols deeper than $l$ are never
popped, so there is no way to distinguish configurations which are equal
according to our definition, and an accepting path for $u v^n x$ is built from
that of $w$ by repeating the steps between $i$ and $j$, $n$ times.

Finally, we also have $|v| > 0$, because if $v = \epsilon$, then, because we
have the same configuration at steps $i$ and $j$ in $\pi$, $\pi' = \pi_{0 \cdots
i} \pi_{j \cdots |\pi|}$ would be an accepting path for $w$, contradicting the
minimality of $\pi$.

(Note that this case amounts to applying the pumping lemma for regular languages
by hardcoding the topmost $l$ stack symbols in the automaton state, which is
adequate because $l$ is small enough to ensure that $|w|$ is larger than the
number of states of this automaton. The main trick is that we must adjust for
$\epsilon$-transitions.)

Case 2. $l \geq p'$. Let $i, j, k$ be a $p'$-level. To any stack
size $h$, $s_i \leq h \leq s_j$, we associate the last push
$\lp(h) = \max(\{y \leq j | s_y = h\})$ and the first pop
$\fp(h) = \min(\{y \geq j | s_y = h\})$.
By definition, $i \leq \lp(h) \leq j$ and $j \leq \fp(h) \leq
k$. Here is an illustration of this construction. To simplify the drawing, I omit the distinction between the path positions and word positions which we will have to do later.

We say that the full state of a stack size $h$ is the triple formed
by:

the automaton state at position $\lp(h)$
the topmost stack symbol at position $\lp(h)$
the automaton state at position $\fp(h)$

There are $p'$ possible full states, and $p' + 1$ stack sizes between $s_i$ and
$s_j$, so, by the pidgeonhole principle, there exist two stack sizes $g, h$ with
$s_i \leq g < h \leq s_j$ such that the full states at $g$ and $h$ are the same.
Like in Case 1, we define by $\lpp(g)$, $\lpp(h)$, $\fpp(h)$ and $\fpp(g)$ the
positions of the last letters of $w$ read at the corresponding positions in $\pi$.
We factor $w = u v x y z$ where $u = w_{0 \cdots \lpp(g)}$,
$v = w_{\lpp(g) \cdots \lpp(h)}$,
$x = w_{\lpp(h) \cdots \fpp(h)}$,
$y = w_{\fpp(h) \cdots \fpp(g)}$,
and $z = w_{\fpp(g) \cdots |w|}$.

This factorization ensures that $|vxy| \leq p$ (because $k \leq p$ by our
definition of levels).

We also have to show that $\forall n \geq 0, u v^n x y^n z \in L$. To do so,
observe that each time that we repeat $v$, we start from the same state and the
same stack top and we do not pop below our current position in the stack
(otherwise we would have to push again at the current position, violating the
maximality of $\lp(g)$), so we can follow the same path in $A$ and push the
same symbol sequence on the stack. By the maximality of $\lp(h)$ and the
minimality of $\fp(h)$, while reading $x$, we do not pop below our current
position in the stack, so the path followed in the automaton is the same
regardless of the number of times we repeated $v$. Now, if we repeat $w$ as many
times as we repeat $v$, since we start from the same state, since we have pushed
the same symbol sequence on the stack with our repeats of $v$, and since we do
not pop more than what $v$ has stacked by minimality of $\fp(g)$, we can follow
the same path in $A$ and pop the same symbol sequence from the stack. Hence, an
accepting path from $u v^n x y^n z$ can be constructed from the accepting path
for $w$.

Finally, we also have $|vy| > 1$, because like in case 1, if $v =
\epsilon$ and $y = \epsilon$, we can build a shorter accepting path for $w$ by
removing $\pi_{\lp(g)\cdots\lp(h)}$ and $\pi_{\fp(h)\cdots\fp(g)}$.

Hence, we have an adequate factorization in both cases, and the result is
proved.

(Credit goes to Marc Jeanmougin for helping me with this proof.)


Properties of toroidal graph I am interested in work pertaining to graphs that have genus 1 i.e. toroidal graphs. Specifically, i am trying to find answers to the questions below.

Since toroidal graphs can be recognized in $P$ , what are some different known characterizations of toroidal graphs ?
There are more than thousand forbidden minors for toroidal graph class, and only four of them does not contain $K_{3,3}$ as a subdivision (This paper). Where can i find a bigger list of forbidden structures of toroidal graphs ?
Two disjoint copies of $K_5$'s are not toroidal. Is it true that if a graph $G$ have two vertex disjoint non-planar induced subgraphs, then $G$ is not a toridal ? If not, then what is special about disjoint copies of $K_5$'s ?

Regarding (3), yes,
if a graph $M$ has two vertex disjoint non-planar induced subgraphs $G$ and $H$, then $G\cup H$ (and hence $M$) is not toroidal.

I don't know a reference but here's a proof sketch.

Thinking of the torus as $T=S^1\times S^1$, if a non-planar $G$ is embedded without crossing on $T$ then its edges must meet every $S^1\times\{a\}$ and $\{a\}\times S^1$, or else we cut such a circle out and realize $G$ as planar. By tracing where they so meet we obtain a subgraph of $G$ realized as homotopic to some
$$\left(\{a\}\times S^1\right)\cup \left(S^1\times\{b\}\right)$$
(so two circles meet in $(a,b)$). Similarly for the second graph $H$ and say
$$\left(\{c\}\times S^1\right)\cup \left(S^1\times\{d\}\right).$$
But then $G$ and $H$ are not disjoint (they share a vertex or have crossing edges) as the embedded graphs meet in $(a,d)$ and $(c,b)$.


Software for Graph Analysis I have some graph-data which I would like to analyze. If the software could automatically determine some characteristics (Is the graph planar, clique number or any other graph property) it would be great, but if I could move the vertexes per drag and drop it would be good enough.

I know that I can visualize graphs with Graphviz, but I can't interact with the graph.

SAGE supports interactive graph drawing. You can easily create customized software for your own use.

Graph editor


Graphs in which every minimal separator is an independent set Background:
Let $u, v$ be two vertices of an undirected graph $G=(V,E)$.
A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$
belong to different connected components of $G-S$. If no proper
subset of a $u,v$-separator $S$ is a $u,v$-separator then $S$ is
a minimal $u,v$-separator. A vertex set $S\subseteq V$ is a (minimal)
separator if there exist vertices $u, v$ such that $S$ is a (minimal)
$u,v$-separator.

A well-known theorem of G. Dirac states that a graph has no induced
cycles of length at least four (called triangulated or chordal graph)
if and only if every of its minimal separators is a clique.
It is also well-known that triangulated graphs can be recognized
in polynomial time.

My questions: What are graphs in which every minimal separator is an independent set?
Are these graphs studied?  And what is the recognition complexity of
these graphs?
Examples for such graphs include trees and cycles.

Your graphs have been characterized by this paper http://arxiv.org/pdf/1103.2913.pdf.

Edit: In the paper above it is proved that graphs in which every minimal separator is an independent set are exactly those containing no cycle with exactly one chord.

Graphs containing no cycle with exactly one chord have been studied in depth by
Trotignon and Vuskovic, A Structure Theorem for Graphs with No Cycle with a Unique Chord and Its Consequences,  J. Graph Theory 63 (2010) 31-67 DOI.
As a result of this paper, these graphs can be recognized in polynomial time. (However, this paper did not point out the connection to independent minimal separators!)

Edit (17 Sept 2013): Very recently (see here),
Terry Mckee describes all graphs in which every minimal vertex separator is a clique or an independent set. It turns out that these are the ''edge sums'' of chordal graphs and graphs in which every minimal vertex separator is an independent set.


Equality of decidable proofs? I want to know if the decidability of equality of two decidable proofs of the same proposition can be proved without any additional axioms in Calculus of Inductive Constructions.

Specifically, I want to know if this is true without any additional axioms in Coq.

$$\forall P: \texttt{Prop}, P \vee \neg P \Rightarrow
(\forall p_1 : P, \forall p_2: P, \{p_1 = p_2\} \vee \{p_1 \neq p_2\})
$$

Thanks!

Edited to correct the error:
Edit 2 to make Prop more explicit

As Neel points out if you work under the "propositions are types" then you can easily come up with a type whose equality cannot be shown decidable (but it is of course consistent to assume that all types have decidable equality), such as $\mathbb{N} \to \mathbb{N}$.

If we understand "proposition" as a more restricted kind of type, then the answer depends on what precisely we mean. If you are working in the calculus of constructions with a Prop kind then you still cannot show that decidable propositions have decidable equality. This is so because it is consistent in the calculus of constructions to equate Prop with a proof-relevant type universe, so for all you know Prop might contains something like $\mathbb{N} \to \mathbb{N}$. This also implies you cannot prove your theorem for Coq's notion of Prop.

But in any case, the best answer comes from homotopy type theory. There a proposition is a type $P$ which satisfies
$$\forall x, y : P \,.\, x = y.$$
That is, a proposition has at most one element (as it should if it is to be understood as a proof-irrelevant truth value). In this case the answer is of course positive because the definition of proposition immediately implies that its equality is decidable.

I am curious to know what you mean by "proposition".


What's the complexity of counting odd nodes in graph? According to Handshaking Lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are given a graph and an odd-degree vertex, and we are asked to find some other odd-degree vertex, then we are searching for something that is guaranteed to exist (so, we have a total search problem).

PPA ( Christos Papadimitriou in 1994 [1]) is defined as follows. Suppose we have a graph on whose vertices are n-bit binary strings, and the graph is represented by a polynomial-sized circuit that takes a vertex as input and outputs its neighbors. (Note that this allows us to represent an exponentially-large graph on which we can efficiently perform local exploration.) Suppose furthermore that a specific vertex (say the all-zeroes vector) has an odd number of neighbors. We are required to find another odd-degree vertex. The corresponding class of parity arguments for directed graphs is belong to PPAD.

My question: What is the complexity of counting odd nodes in directed and undirected graph?

[1] Papadimitriou, Christos H. "On the complexity of the parity argument and other inefficient proofs of existence." Journal of Computer and system Sciences 48.3 (1994): 498-532.

Well, at least $\#\mathsf{P}$-hard. Given a SAT formula, construct a graph with two vertices, $v_x$ and $v_x'$, for every possible assignment of variables $\vec{x}$. If $x$ is a satisfying assignment for the formula, draw an edge between $v_x$ and $v_x'$; these are the only edges. It is easy to construct the circuit for this graph from the SAT formula, and the number of odd vertices is exactly twice the number of satisfying assignments.


Subquadratic 3SUM when one set is in [n^1.99] Chan and Lewenstein (STOC 2015) said:

  3SUM for three integer sets where only one set is assumed to be in $[n^{2−\delta}]$ can still be solved
  in subquadratic time (by doing several FFTs, without requiring additive combinatorics - a simple exercise we leave
  to the reader).

Note, that the other 2 sets can be from $[n^{3+o(1)}]$.

Nevertheless I have no idea how to solve this exercise. Do you have any hints? (probably you can use their paper but it looks like an overkill)

I think one can solve this problem as follows. Assume that we have three sets $A, B, C$ of integers, $|A|=|B|=|C|=n$, and $C\subseteq [n^{2-\delta}]$. We want to check whether there exist $a\in A, b \in B, c \in C$ such that $a+b+c=0$.

First, we partition the set $A$ into $k\leq n$ sets $A_1,\ldots A_k$, where each $A_i$ contains numbers in an interval of length $n^{2-\delta}$. Now from the set $B$, we construct sets $B_1,\ldots, B_k$ as follows. $B_i$ contains numbers from $B$ in the interval $[-n^{2-\delta}-\max_{a \in A_i}{a}, -\min_{a\in A_i}a]$. This way each number from $B$ appears in at most two sets $B_i$. And now we only need to check whether for some $i$ there exists a solution in $A_i + B_i + C$.

Let $a_i=|A_i|$, $b_i=|B_i|$. If $a_i\geq n^{1-\delta/2}$ or $b_i\geq n^{1-\delta/2}$, we solve $A_i+B_i+C$ by FFT in time $O(n^{2-\delta}\log{n})$. (Because numbers in all three sets lie in intervals of length $O(n^{2-\delta})$.) Since $\sum_i a_i=n$ and $\sum_i b_i\leq 2n$, the total number of such $a_i$ and $b_i$ is at most $3n^{\delta/2}$, which means that the running time of this step is $O(n^{2-\delta/2}\log{n})$.

For the remaining values of $i$, we solve the problem by trying all $a\in A_i$ and $b \in B_i$, and looking up their sum in $C$ in logarithmic time. This step takes time $\sum a_i b_i \log{n} \leq O(n^{2-\delta/2}\log{n})$. (I believe one can shave off the $\log{n}$ factor here by using the standard 3-SUM trick.)


Concise introduction to algorithms for mathematicians I am looking for a concise introductory text on algorithms with a high ratio $$\frac{\mbox{theory covered}}{\mbox{total number of pages}}.$$ It should begin at the beginning but then progress quickly without spending too much time on real world examples, elementary proof techniques, etc. As a research mathematician I have a solid background in mathematics which I happily employ to understand formalisms and condensed proofs, for example.

Do there exist such texts? Any recommendations?

I like this textbook very much:

Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani: Algorithms
Published by McGraw-Hill 2007.

I don't calculate your suggested ratio but I think you will also like it :)


Linked List size in constant time or linear time The space-time complexity of getting the size of the linked list can differ in different implementations as far as I understand it.

In the Boost C++ library one finds that the size() function can be constant time or linear time.

I was wondering what the differences are in getting the size to be constant time over getting it to be linear?

Can anyone elaborate on the algorithm differences?

The key difference is that you have a field tracking the size of the list. This field can be accessed in constant time. The field must be updated for every addition or removal. If you compute the size of the list by counting the elements, then it will be linear.


Uniqueness of the distribution maximizing the channel capacity Setting: We look at a discrete memoryless channel which takes an input probability distribution acting over symbols in $\mathcal{X}$ to an output probability distribution over symbols in $\mathcal{Y}$.

To simplify notation, let the input symbols be labelled as $[1,2, ..., N]$ where $N = |\mathcal{X}|$ and the output symbols be labelled as $[1,2, ..., M]$ where $M = |\mathcal{Y}|$. The input probability vector of size $1\times N$ is denoted by $p$ and the output probability vector of size $1\times M$ is denoted by $q$. The stochastic matrix $Q$ of size $N\times M$ is the channel matrix i.e. $q = Qp$. The capacity of this channel is given by

$$C = \max_{p}\sum_{i=1}^N\sum_{j=1}^M p_iQ_{ij}\log\frac{Q_{ij}}{q_j}$$

Let the distribution that achieves $C$ be $p^*$.

Conjecture: If $p^*$ does not use the entire input alphabet in $X$ i.e. $p^*_i = 0$ for some component $i$, then it is guaranteed that there exists another distribution $\tilde{p}^* \neq p^*$ which also achieves the capacity of the channel.

Can anyone help prove this or show a counterexample?

Suppose we have a binary symmetric channel:

$x_1 \rightarrow y_1$ with probability $1-\epsilon$ and $y_2$ with probability $\epsilon$,

$x_2 \rightarrow y_2$ with probability $1-\epsilon$ and $y_1$ with probability $\epsilon$.

Now add a third input $x_3$ that goes to $y_1$ and $y_2$ with probability $\frac{1}{2}$ each.

Then the optimal input probability distribution is $(\frac{1}{2}, \frac{1}{2}, 0)$.

Proof: Let $X$ be the random variable describing the input, and $Y$ be the random variable describing the output. The capacity $C = H(Y) - H(Y|X)$, where $H(Y)$ is the entropy of $Y$, and $H(Y|X)$ is the conditional entropy of $Y$ given $X$.

If you have an input distribution $(p_1, p_2, p_3)$ for $X$, you can replace it by the distribution $(p_1+p_3/2, p_2 + p_3/2, 0)$. This keeps $Y$ the same, so $H(Y)$ is unchanged, and it reduces $H(Y|X)$. Thus, capacity strictly increases.


Defining Mutually Recursive functions in Coq This question is related to (but not the same as):

How to define a function inductively on two arguments in Coq?

In particular, I used those techniques (defining a second fixed point function) and Coq still complains.

Consider the following formalization of regular expressions.

Inductive symbol : Set := Zero | One.

Definition string := list symbol.

Fixpoint symbol_eq (a:symbol) (b:symbol) : bool :=
  match a with
    Zero =>
    match b with
      Zero => true
    | One => false
    end
  | One =>
    match b with
      Zero => false
    | One => true
    end
  end.

Inductive regexp : Set :=
    Symbol (s:symbol)
  | Concat (r1:regexp) (r2:regexp)
  | Union (u1:regexp) (u2:regexp)
  | Star (u1:regexp)
  .

Fixpoint rgm (r:regexp) (s:string) :=
  match r with
    Symbol ss =>
      match s with
        nil => false
      | a::nil => (symbol_eq ss a)
      | a::b::tl => false
      end
   | Union r1 r2 => (orb (rgm r1 s) (rgm r2 s))
   | Concat r1 r2 =>
       let fix f s1 s2 :=
         match s2 with
           nil => (andb (rgm r1 (rev s1)) (rgm r2 s2))
         | a::tl => (orb (andb (rgm r1 (rev s1)) (rgm r2 s2))
                         (f (a::s1) tl))
         end
       in (f nil s)
   | Star r1 =>
       match s with
         nil => true
       | a::tl =>
         let fix f s1 s2 :=
           match s2 with
             nil => (rgm r1 (rev s1))
           | a::tl => (orb (andb (rgm r1 (rev s1)) (rgm r s2))
                           (f (a::s1) tl))
           end
         in (f (a::nil) tl)
       end
  end.

Coq refuses to compile it for the following reason:

Error: Cannot guess decreasing argument of fix.

Question: how can we fix this?

As stated in Coq Reference Manual (2.3)

  in Fixpoint, the decreasing argument must be given (unless the
  function is not recursive), but it must not necessary be structurally
  decreasing.

Key word is structurally, Coq can't guess, which arguments is decreasing at each step of the recursion.

The reason for this is nicely described in Software Foundations

  Since Coq is not just a functional programming language, but also a
  consistent logic, any potentially non-terminating function needs to be
  rejected. Here is an (invalid!) Coq program showing what would go
  wrong if Coq allowed non-terminating recursive functions:

 Fixpoint loop_false (n : nat) : False := loop_false n.

  That is, propositions like False would become provable (e.g. loop_false 0 would
  be a proof of False), which would be a disaster for Coq's logical
  consistency.


Entropy and computational complexity There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, computational complexity $F(n) $ is correlated to the average consumption of energy, hope I can get some answer here.

Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there is an important difference between energy needed to make a computation run, and entropy generated by the computation and put out into the environment, typically in the form of heat.)
Based on Landauer and Bennett's original analysis that erasing a bit "must" generate $kT \ln(2)$ entropy (see below for why there are scare-quotes), several researchers have pursued various questions along these lines. One line of research was to simulate irreversible Turing machines by reversible ones, which, it was suggested, would generate no entropy. There are several works showing space-time tradeoffs for how to simulate irreversible TMs by reversible ones, e.g.:

Bennett, Time/Space Trade-Offs for Reversible Computation. SICOMP 1989

Levine & Sherman. A Note on Bennett’s Time-Space Tradeoff for Reversible Computation. SICOMP 1990.

Li & Vitanyi. Reversible simulation of irreversible computation. CCC 1996

Lange, McKenzie, and Tapp. Reversible Space Equals Deterministic Space. JCSS 2000.

More recently,

Demaine, Lynch, Mirano, and Tyagi. Energy-Efficient Algorithms, 2016.

studied partially reversible algorithms - that is, if you are willing to pay some entropy, for standard algorithmic tasks can one improve upon the general irreversible-to-reversible simulations mentioned above. Reversible computing has a whole community of researchers devoted to it, viz. the Reversible Computing conference, now in its 10th year.
It has actually been known for a long time, going all the way back to Landauer and Bennett, that the relationship between computational irreversibility and entropy generation is more subtle than is suggested by the tagline "erasing a bit generates $\ln(2)$ entropy." However, in the past 20 years or so nonequilibrium statistical mechanics has advanced to the point that this more subtle relationship can be captured by precise numerical equations involving not just entropy difference, but also a difference of KL divergences, see

Kolchinsky & Wolpert, Dependence of dissipation on the initial distribution over states. J. Stat. Mech. 2017 (arXiv link)

(and references therein).
We hosted a workshop on this at the Santa Fe Institute in August 2017 (where you can see the names of some researchers and talk titles of relevance), and it raises a whole new set of questions in both physics and thermodynamic computational complexity.


Why is it impossible to work with polylog length encoding schemes for quantum circuits? I am going through Quantum Computational Complexity by John Watrous. On page $12$, he said:

  The encoding disallows compression: it is not possible to work with
  encoding schemes that allow for extremely short (e.g.,
  polylogarithmic-length) encodings of circuits; so for simplicity it is
  assumed that the length of every encoding of a quantum circuit is at
  least the size of the circuit.

My question:

Why is it impossible to work with polylogarithmic-length encoding schemes for quantum circuits?

Clearly you can work with abstract compressed representations of circuits. You can reason about them and manipulate them and turn them into concrete lists of gates. We do it all the time.

But in context the author is in the middle of explaining the complexity class BQP (bounded-probability quantum polynomial-time). I think they're just making sure that you don't sneak non-polynomial amounts of work into the encoding. You don't want "repeat the diffusion operator $\sqrt{2}^n$ times" to count as being in BQP with respect to $n$.


Is the dual of a polyhedral embedding a polyhedral embedding? A polyhedral embedding of a graph on a surface is an embedding without edge crossings such that all the faces are bounded by simple cycles, and any two faces share a common vertex, share a common edge, or do not intersect at all. Moreover, all the faces are disks.

Given a graph $G$ with a polyhedral embedding on a surface $S$, one can define a dual graph $G'$ embedded in the same surface $S$, by creating a vertex in $G'$ for each face of $G$, and adding an edge between two vertices of $G'$ for each edge that the corresponding two faces in $G$ share.

I have a feeling that this will be simple, but I don't know how to prove it, so here it goes anyways. Question: The dual embedding that one obtains for $G'$ is also polyhedral?

You need to specify that $G$ is a simple graph (else the trigonal hosohedron is a counterexample) but then the answer is yes. What can go wrong? If a dual face is not a simple cycle then one of its edges is repeated, giving a self-loop in the primal, or a vertex but not an edge is repeated, in which case this face and vertex form a configuration of the same type in the primal. If two dual faces meet at more than one edge then there is a multiple adjacency in the primal. If the dual has a self-loop or multiple adjacency then we get a face with a repeated edge or two dual faces meeting at more than one edge in the primal. If two dual faces meet at two vertices but do not share an edge between these two vertices then a configuration of the same type happens in the primal. And if two dual faces meet in an edge and a third vertex then in the primal we have three faces sharing the same two vertices and they can't all three contain the edge connecting these two vertices.


Forbidden subgraph characterisation of interval graphs A graph is an interval graph iff it is chordal and asteroidal triple free.
An interval graph is proper interval graph iff it is $K_{1,3}$ free.

However i googled intensely to find a minimal set of forbidden subgraphs for proper interval graphs,but in vain.

My question is : What are the minimal set of forbidden subgraphs for proper interval graphs ?
Any link to journal/paper is welcome.

ISGCI's page on proper interval graphs (from our FAQ) lists a few equivalent classes; one of them is the class of $(C_{n+4}$, $S_3$, claw, net)-free  graphs (see the same website for definitions).


Configurations from arrangement of lines Suppose we have an arrangement of $n$ lines in the plane. This partitions the plane into regions. We can label each region by a string in $\{+1, -1\}^n$, where the $i$'th coordinate is +1 if the region lies above the $i$'th line and -1 if it lies below the $i$'th line. (By rotating the arrangement if necessary, we can assume that no line is perfectly vertical.)

Say that a subset $S$ of $\{+1,-1\}^n$ is realizable by a linear arrangement if there exists a linear arrangement such that the labels of the regions are exactly the strings in $S$. Is there previous study of which subsets of $\{+1, -1\}^n$ are realizable by linear arrangements? One can also ask the same question for hyperplane arrangements.

This problem is known as the question of realizability of pseudoline arrangements by straight lines. An arrangement of pseudolines is an arrangement of $n$ curves in the plane, such that any two curves intersect exactly once. For pseudolines, you can define the same labeling as the OP does. Pseudoline arrangements are related to oriented matroids, and you can use these to give a polynomial-time algorithm for telling whether a labeling of regions is realizable by a pseudoline arrangment.

The question of whether a pseudoline arrangement can be realized by straight lines
exhibits Mnëv universality, which means that it's at least NP-hard (and probably strictly harder). In particular, it is equivalent in complexity to the existential theory of the reals, which is known to be NP-hard, and to be contained in PSPACE.

There is a very nice AMS feature column on oriented matroids. You can read Richter-Gebert's paper "Mnëv Universality Revisited" for a nice discussion and simplification of the proof of Mnëv universality of line arrangements.

Hyperplane arrangements also exhibit Mnëv universality. I don't know offhand of a good reference for this, but it's clear that they have to be at least as hard as line arrangements, and so they are also equivalent to the existential theory of the reals.


When is relaxed counting hard? Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some constant and $v$ is the number of edges with endpoints are colored the same. As $c$ goes to 0, this reduces to counting proper colorings which is hard for many graphs. When c is 1, every colorings gets the same weight and the problem is trivial. When adjacency matrix of the graph multiplied by $-\log(c)/2$ has spectral radius below $1-\epsilon$, this sum can be approximated by belief propagation with convergence guarantee, so it's easy in practice. It's also easy in theory because a particular computation tree exhibits decay of correlations and hence allows a polynomial time algorithm for guaranteed approximation -- Tetali, (2007)

My question is -- what other properties of the graph make this problem hard for local algorithms? Hard in a sense that only a small range of $c$'s can be addressed.

Edit 09/23: So far I came across two deterministic polynomial approximation algorithms for this class of problem (derivatives of Weitz's STOC2006 paper and of Gamarnik's "cavity expansion" approach to approximate counting), and both approaches depend on the branching factor of self-avoiding walks on the graph. Spectral radius comes up because it's an upper bound on this branching factor. The question is then  -- is it a good estimate? Could we have a sequence of graphs where branching factor of self-avoiding walks is bounded, while branching factor of regular walks grows without bound?

Edit 10/06: This paper by Allan Sly (FOCS 2010) seems relevant...result suggests that branching factor of infinite tree of self-avoiding walks precisely captures the point at which counting becomes hard.

Edit 10/31: Alan Sokal conjectures (p.42 of "The multivariate Tutte polynomia") that a there's an upper bound on the radius of zero-free region of the chromatic polynomial which is linear in terms of maxmaxflow (maximum s-t flow over all pairs s,t). This seems relevant because long-range correlations appear as the number of proper colorings approaches 0.

This is hard for planar graphs, at least for six colours or more. See
"Inapproximability of the Tutte polynomial of a planar graph" by Goldberg and Jerrum


Complexity of a graph-rewriting problem I recently came across the following problem which seems to fall in the context of graph rewriting problems:

Input: A graph $G=(V,E)$ with maximum degree 3, an edge $e_0 \in E$ and pairs of graphs $(A_1,B_1),\ldots,(A_k,B_k)$ where both $A_i$ and $B_i$ are subgraphs of the complete graph with vertex set $V$ and $A_i$ is isomorphic to $B_i$ for $i=1,\ldots,k$.

Question:  Is there a sequence $a_1,\ldots,a_n$ such that successively replacing the subgraphs $A_{a_i}$ with $B_{a_i}$ in $G_{i-1}$ (where $G_0=G$) to obtain $G_i$ yields a graph $G_n$ with $e_0 \in E(G_n)$.

Note that one can only replace $A_{a_i}$ with $B_{a_i}$ in $G_{i-1}$ if $E(A_{a_i}) \subseteq E(G_{i-1})$.

Is anything about the complexity of this problem known (in particular is it NP-hard?).

I don't know if it has been studied before, but after a quick look I think it should be PSPACE complete.

We can build a reduction using the Nondeterministic Constraint Logic model of computation (NCL).

I quick idea is the following (I assume you're familiar with the NCL model): given an NCL graph $G$, you can replace red and blue directed edges with a suitable gadget (with undirected edges) that "marks" the direction of the edge.

Then build the $A_i \to B_i$ subgraphs in such a way that if $A_i$ is a  subgraph of $G$ that represents an NCL  node with valid incoming/outgoing edge constraints, then it can be replaced with $B_i$ which represents a valid flip of one of those edges.

The $A_i / B_i$s should be isomorphic; but this is not a problem for the OR gadget: just add 2 dum nodes "D" so that every node $u$ of the NCL, in the resulting graph has degree 5 with 3 incoming (blue) edges and 2 outgoing (red) edges.

The AND gadget is a little bit more complex, but you can use a "circle" (green edges in the figure) that forces the correct correspondence between the flip of the 2 red edges and the flip of the blue edge (on the opposite side).

If I have enough time I'll give more details about the proof.


theorems for universal set of quantum gates for SU(d) It seems that there is a theorem that for prime dimension d, the set of Clifford gates and one non-Clifford gate together forms a universal set of quantum gates for SU(d). It also seems that for a universal set of gates, there is a requirement of a gate using which can provide non-trivial rotation by an irrational multiple of Pi. Does this imply that using any non-Clifford gate for prime d, one can construct such a gate ? Also, it probably does not follow directly that the non-Clifford gate used to get such a non-trivial rotation itself has irrational eigenvalues but it seems that is usually the case- for example, the qubit T gate and qudit versions of it.

Is there any similar theorem as mentioned above, for composite d ? It seems that if one finds a gate using which one can construct a non-trivial rotation by an irrational multiple of Pi, that should be enough to have universal set of gates even for composite d. Is it obvious that such a gate has to be non-Clifford ?

I'm not aware of any proof that the Clifford group + any non-Clifford element gives a universal set of quantum gates. The closest related result that I know is that the Clifford group + any non-Clifford element densely generates an infinite group. (This is theorem 6.5 of Nebe et al. http://arxiv.org/abs/math/0001038v2). But this falls short of proving that the Clifford group + any non-Clifford element is universal, because it is possible you could densely generate a continuous group on $n$ qubits that is not all of $U(2^n)$. So I believe that proving this result remains open.
Note that in the case of the Clifford group on qubits, one can easily show that the Clifford group + any non-Clifford one-qubit gate is universal, using the representation theory of $SU(2)$. But the more general statement about adding arbitrary elements to the Clifford group is open.

Update: The answer to the first problem is known. In particular, the statement that the Clifford group + any non-Clifford element yields a universal gate set follows from two theorems of Nebe, Rains and Sloane. First, Theorem 6.5 of Nebe et al (http://arxiv.org/abs/math/0001038v2) shows that adding any element to the Clifford group renders it infinite. Second, Corollary 6.8.2 of Nebe et al. (Self-Dual Codes and Invariant Theory (Springer 2006)) states that any infinite group which contains the Clifford group contains all of $SU(d^n)$. Combining these shows that the Clifford group + any non-Clifford element is universal, in any local dimension $d$ (prime or composite). This was previously discussed on stackexchange here: Universal sets of gates for SU(3)?

With regards to rotations by irrational multiples of pi: it's not necessary for your gate set to contain a rotation by an irrational multiple of pi to be universal - for example the gate set $CNOT, H,T$ is universal where $T$ is a Z-rotation by $\pi/8$. All that's required for universality is that the gate set densely generates all rotations. A priori it's possible that even as you take longer and longer products of your gate elements, all the resulting rotations are by rational multiples of pi, but the gate is still universal as the rational rotations are dense in the reals.  So I don't believe one can argue that "the gate added to the Clifford group must generate an irrational rotation to be universal". We only know that "the gate added to the Clifford group must densely generate and irrational rotation to be universal".


Counting number of solutions to a specific SAT formula I have a n×n grid of binary bits, where n is a natural number. I want to count the number of bit patterns which have the following property: out of the four (North, West, South and East) adjacent bits of any bit, at most 3 can have a value different from it. Alternatively, if C is the center bit, and N, W, E and S are its four adjacent neighbours, then
              (C xor W)∧(C xor S)∧(C xor E)∧(C xor N)=0

              N
            W-C-E
              S

This should hold for every bit in any valid pattern. I am not sure if this is a #P problem. The counting for 1D version of this problem (a 1×n or n×1 grid), where every bit has only two adjacent neighbours, and at most one can be different from the bit, can be done in polynomial time. I am not sure if the same is true for this problem or not..

Inductive Proof for the case of a $n \times 1$ grid:

Counting for the 1D case can be done using the following inductive argument:

For an $n \times 1$ grid, let $b_{n}b_{n-1}...b_{1}b_{0}$ be a unique bit pattern. For this pattern to be valid, for any $b_{i}$, $i \in [1, n-1]$, atmost one of $b_{i-1}$ or $b_{i+1}$ can be equal to $\neg b_{i}$.
We now define the following quantities for a $n \times 1$ grid:
• $T(n)$ is the total number of distinct $n$ bit patterns
• $T_{v}(n)$ is the total number of valid patterns
• $T_{iv}(n)$ is the total number of invalid patterns
• $T_{vs}(n)$ is the total number of valid patterns which satisfy the property $b_{n} = b_{n-1}$
• $T_{vd}(n)$ is the total number of valid patterns which satisfy the property $b_{n} \neq b_{n-1}$

Then, for $n \geq 3$:
$T_{v}(n) = 2 \times T_{vs}(n-1) + T_{vd}(n-1)$
$T_{vs}(n) = T_{vs}(n-1) + T_{vd}(n-1)$
$T_{vd}(n) = T_{vs}(n-1)$

Also, by the definition of $T_{v}(n)$ and $T_{vs}(n)$, we have:
$T_{v}(n)=T_{vs}(n)+T_{vd}(n)$
$T_{vs}(n)=T_{v}(n-1)$  (Only one pattern of the type $T_{vs}$ for a $1 \times n$ grid can be created from a $T_{v}$ pattern for a $1 \times n-1$ grid)

Now,
$T_{v}(n) = 2 \times T_{vs}(n-1) + T_{vd}(n-1)$
$T_{v}(n) = T_{vs}(n-1) + T_{vs}(n-1) + T_{vd}(n-1)$
$T_{v}(n) = (T_{vs}(n-1) + T_{vd}(n-1)) + T_{vs}(n-1)$
$T_{v}(n) = T_{v}(n-1) + T_{v}(n-2)$

By using $n=2$ and $n=1$ as the base cases, we can compute the number of valid patterns for a $n \times 1$ grid for any $n$. This inductive method breaks for a $n \times n$ grid, because it would require creating exponential intermediate variables to do an exact counting.

Thanks,
Rajeev

This is not an answer, just a long comment.

First, you say that you are unsure if this problem in in #P.  It depends on how you define your input, which can either be the $n$-by-$n$ graph or just $n$.  I would say that it is more natural to take the graph as input, in which case, an NP machine can guess $n^2$ bits (which is a polynomial, linear even, in the size of the input) and can check in polynomial time, linear even, if all your constraints are satisfied.  If the input is just $n$, then $n^2$ is exponentially larger than the input size $\log(n)$, so we can't say your problem is in #P, but it is in the counting class related to NEXP (in the same way that #P is the counting class related to NP).

Second, this input issue also affects what types of hardness we can expect to prove. If the input is the grid graph, then you have at most one input for each input length.  Such problems are said to be sparse (which means there is at most a polynomial number of inputs for each input length) and are not expected to be hard by (a generalization of) Mahaney's theorem.  But if you pick $n$ to be your input so that set of instances is no longer sparse, then your output is exponentially larger than your input.  What I am trying to say here is that the typical notions of hardness don't apply very well to your problem.

Third, I can say something about the possibility of this problem being tractable.  My research is in counting problems defined by local constraints, which we formally define as Holant problems. The difference between Holant problems and your problem is that we don't put such tight restrictions on the inputs graphs.  We allow restrictions like planar, bipartie, and prescribed degree (such at $k$-regular or at most degree $k$), none of which defines a sparse set of graphs.

The best I can do to cast your problem as a Holant problem is as follows.  For omitted definitions, see the preliminary section in a recent paper of mine.  In the Holant framework, edges take values from a finite domain and vertices impose constraints on the values assigned to its incident edges.  To (partially) model your problem, we consider the Boolean domain $\{0,1\}$.  As a first attempt to capture your problem, think of an $n$-by-$n$ grid graph as the input.  To associate a bit with each vertex $v$, we add an edge $e_v$ incident $v$ and to a new vertex $u_v$.  To communicate this bit value to the neighboring internal vertices, we duplicate all the edges between internal vertices (i.e. vertices not on the boundary) in the original $n$-by-$n$ grid graph.

The vertices on the boundary have no constraint, which is represented by the signature $[1,1]$ tensored with itself twice for the corner vertices and three times for the vertices on the sides.  The remaining interior vertices pick an edge in each direction and require these four edges and the other edge added above (with its associated bit) to take the same value. Then we impose your constraint by comparing this value with the four values assigned to the remaining four edges (one edge in each direction).  Of course, between each pair of internal vertices, they have to agree on which edge each uses to communicate their bit value.  One way to decide this, in a planar embedding of this graph, is that each vertex should use the edge that is encountered first in a clockwise traversal of its incident edges.

The paper of mine that I linked to above is a dichotomy for Holant problems that use symmetric signatures (which means that the output is invariant under any permutation of the input).  Unfortunately, the constraint that I used to capture your problem at internal vertices is not symmetric and it is still an open problem to prove the generalization of that dichotomy for general (i.e. not necessarily symmetric) signatures.  Worse yet, we currently do not even know how to decide if this Holant problem is easy or hard according to what we conjecture the dichotomy to be.  Furthermore, we can impose restrictions on the input graphs like being planar and bipartite that are satisfied by your grid graph, the hope being that this Holant problem may become tractable under these restrictions. However, a dichotomy for such Holant problems is years, maybe even a decade away.

In closing, let me emphasize that this Holant problem that I have described is "more difficult" than your problem (when the input is the grid graph).  The input to this (planar, bipartite) Holant problem can only use the complicated arity 9 constraint (that was assigned to the internal vertices) and the (unconstraining) unary constraint $[1,1]$ but the graph is not restricted to grid graphs. Formally speaking, your problem (when the input is the grid graph) reduces to this Holant problem. So, if this Holant problem were easy, then your problem (when the input is the grid graph) is easy too, but if this Holant problem is hard, then I want to say that your problem is hard, but I don't know how to do so (as I discussed above).


Element distinctness in O(n) time? We all know that element distinctness in the comparison based model cannot be done in $o(n\log n)$ time. However, on a word-RAM, one can possibly achieve better.

Of course, if one assumes the existence of a perfect hash function that can be computed in linear time, we get a linear time algorithm for element distinctness: just keep hashing the numbers one by one and return 1 if there is a collision.

However, there are two issues: 1) most constructions of perfect hash functions that I could find used randomness and 2) I cannot find a discussion of the pre-processing time anywhere, i.e., the time required to decide what hash function one is going to use based on the input set of numbers.

Fredman et al.'s "Storing a sparse table with $O(1)$ worst case access time" does resolve the first issue by providing a hash function with $O(1)$ access time in the worst case, but says nothing about the second issue.

So to sum up, here's what I want:

Design an algorithm that given a set $S$ of $n$ numbers (each number being $w$ bits long) on a word-RAM with word length $w$, finds a hash function $h:S\rightarrow \{1, \ldots , m\}$ in $O(n)$ time, where $m = O(n)$. The function $h$ should have the property that for any $j \in \{1, \ldots , m\}$, the number of elements of $S$ that map to $j$ is a constant and computing $h(i)$ should take $O(1)$ time in a "reasonable" word-RAM model, i.e., the model should not allow "exotic" functions on words to be evaluated in $O(1)$ time.

I will also like to know if there are algorithms to solve element distinctness on the word-RAM that do not use hash functions at all.

Element distinctness can be solved deterministically in the RAM model in time within $O(n\log\log n)\subset o(n\log n)$ time:

Sort in time within $O(n\log\log n)$ your $n$ numbers of $w$ bits using the sorting algorithm described by Han in STOC 2002 ("Deterministic sorting in $O(n\log\log n)$ time and linear space"), then scan in linear time for collisions.

As far as I know, that is the best result known to this day.


Computational complexity of pi Let

$L = \{ n : \text{the }n^{th}\text{ binary digit of }\pi\text{ is }1 \}$

(where $n$ is thought of as encoded in binary).  Then what can we say about the computational complexity of $L$?  It's clear that $L\in\mathsf{EXP}$.  And if I'm not mistaken, the amazing "BBP-type" algorithms for computing the $n^{th}$ bit of $\pi$ using quasilinear time and $(\log n)^{O(1)}$ memory, without needing to compute the previous bits, yield $L\in\mathsf{PSPACE}$.

Can we do even better, and place $L$ (say) in the counting hierarchy?  In the other direction, is there any hardness result whatsoever for $L$ (even an extremely weak one, like $\mathsf{TC}^0$-hardness)?

An interesting related language is

$L' = \{ \langle x,t\rangle : x\text{ occurs as a substring within the first }t\text{ digits of }\pi \}$

(where again, $t$ is written in binary).  We have

$L' \in \mathsf{NP}^L$

and hence $L' \in \mathsf{PSPACE}$; I'd be extremely interested if anything better is known.

OK, James Lee has pointed me to this 2011 paper by Samir Datta and Rameshwar Pratap, which proves that my language $L$ (encoding the digits of $\pi$) is in the fourth level of the counting hierarchy ($\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$; thanks to SamiD below for pointing out a missing $\mathsf{PP}$ in the paper, which I'd simply repeated in my answer!).  The paper also explicitly discusses my question of lower bounds on the complexity of computing the binary digits of irrational numbers, though it only manages to prove a very weak lower bound for computing the binary digits of rational numbers.  This is exactly what I was looking for.

Update (April 3): An amusing consequence of the digits of $\pi$ being computable in the counting hierarchy is as follows.  Suppose that $\pi$ is a normal number (whose binary expansion converges quickly to "effectively random"), and suppose that $\mathsf{P} = \mathsf{PP}$ (with the simulation involving only a small polynomial overhead).  Then it would be feasible to program your computer to find, for example, the first occurrence of the complete works of Shakespeare in the binary expansion of $\pi$.  If that sounds absurd to you, then maybe it should be taken as additional evidence that $\mathsf{P} \ne \mathsf{PP}$. :-)


Computational consequences of Friedman's (unprovable) Upper Shift Fixed Point theorem? Harvey Friedman showed that there is a neat fixed point result that cannot be proved in ZFC (the usual Zermelo-Frankel set theory with the Axiom of Choice).  Many modern logics are built on fixed point operators, so I was wondering: are there any consequences known of the Upper Shift Fixed Point theorem for theoretical computer science?

  Unprovable Upper Shift Fixed Point Theorem
  For all $R \in \text{SDOI}(Q^k,Q^k)$, some $A = \text{cube}(A,0) \setminus R[A]$ contains $\text{us}(A)$.

The USFP Theorem seems to be a $\Pi^1_1$ statement, so it might be "close enough" to computability (such as checking non-isomorphism of automatic structures), to impact theoretical computer science.

For completeness, here are the definitions from Friedman's MIT talk from November 2009 (see also the draft book on "Boolean Relation Theory").

$Q$ is the set of rational numbers.  $x, y \in Q^k$ are order equivalent if whenever $1 \le i,j \le k$ then $x_i \lt x_j \Leftrightarrow y_i \lt y_j$.  When $x \in Q^k$ then the upper shift of $x$, denoted $\text{us}(x)$, is obtained by adding 1 to every non-negative coordinate of $x$.  A relation $A \subseteq Q^k$ is order invariant if for every order invariant equivalent $x,y \in Q^k$ it holds that $x \in A \Leftrightarrow y \in A$.  A relation $R \subseteq Q^k \times Q^k$ is order invariant if $R$ is order invariant as a subset of $Q^{2k}$, and is strictly dominating if for all $x,y \in Q^k$ whenever $R(x,y)$ then $\max(x) \lt \max(y)$.  Further if $A$ is a subset of $Q^k$ then $R[A]$ denotes $\{ y | \exists x \in A R(x,y)\}$, the upper shift of $A$ is $\text{us}(A) = \{\text{us}(x) | x \in A\}$, and $\text{cube}(A,0)$ denotes the least $B^k$ such that $0 \in B$ and $A$ is contained in $B^k$.  Let $\text{SDOI}(Q^k,Q^k)$ denote the set of all strictly dominating order invariant relations $R \subseteq Q^k \times Q^k$.

Edit: As Dömötör Pálvölgyi points out in comments, taking $k=1$ and $R$ to be the usual ordering on rationals seems to yield a counterexample.  First, the set $A$ cannot be empty, as $R[A]$ is then also empty and $A$ would then have to contain 0 by the cube condition, a contradiction.  If the non-empty set $A$ has an infimum then it cannot contain any rationals greater than this, so it must be a singleton, which contradicts the upper shift condition.  If on the other hand $A$ has no infimum then $R[A] = Q$ so $A$ must be empty, a contradiction.  Any comments on whether there are any hidden non-obvious definitional problems, such as perhaps an implicit nonstandard model of the rationals?

Further edit: The argument above is roughly correct, but is wrong in the application of the upper shift.  This operator only applies to non-negative coordinates, so setting $A$ to be any negative singleton set yields a fixed point, as desired.  In other words, if $m < 0$ then $A = \{m\}$ is a solution, and there are no other solutions.

I don't know of any consequences of this particular theorem, but normalization proofs of lambda calculi like the calculus of inductive constructions rely on large cardinal axioms -- even though the set of lambda-terms is as countable as you could want.

I think the best way to understand the computational significance of set-theoretic axioms asserting the existence of large cardinals is to think of set theory as a way of phrasing the theory of graphs. That is, a model of a set is a collection of elements equipped with a binary relation used to interpret membership. Then, the axioms of set theory tell you properties of the membership relation, including how you can form new sets from old. In particular, the axiom of foundation means that the membership relation is well-founded (ie, it has no infinite descending chains). This well-foundedness in turn means that if you can line up the execution states of a program with the transitive membership of the elements of a set, then you have a termination proof.

So an assertion that a "big" set exists has a computational payoff as a claim that a certain class of loops in a general recursive programming language terminate. This interpretation works uniformly, all the way from the plain old axiom of infinity (which justifies natural number iteration) all the way up to large cardinal axioms.

Are these axioms true? Well, if the axiom is false you can find a program in one of these classes which doesn't terminate. But if it's true, we will never be sure, thanks to the Halting theorem. Everything from natural number induction on is a matter of scientific induction, which may always be falsified by experiment -- Edward Nelson has famously hoped to prove exponentiation is a partial function!


My exact divide-conquer algorithm for counting antichain in a poset? This post is a little lengthy, thank your for your patience for reading. ^_^

As known, counting antichains in a poset is #P-complete, so it is NP-hard to get the exact answer. Following is my simple divide-conquer algorithm for the antichain counting problem (#ANTICHAIN). I wonder if more helpful properties releavnt to my algorithm could be found? And whether the worst condition may happen?

We represent the poset as a DAG. Notice: We can assume that $G$'s underlying undirected graph is connected. Otherwise, we can calculate each connected component and just multiply the number of each component. Also, we assume that $G$ is transitive reduction of itself, i.e, $G$ is free of transitive edge.

Consider a vertex $u$ of $G$, let $R^+[u]=\{ v | u \leadsto v \}$ denote the set of vertices which are reachable from $u$, including $u$ itself. Similarly, let $R^-[u]=\{ v | v \leadsto u \}$.

When $u$ is selected as a member of an antichain, $R^+[u]$ is excluded from further selection, i.e., $G \leftarrow G-R^+[u]$. Just delete $R^+[u]$ and any edge which has an head (ending-point) in $R^+[u]$ from $G$.
When $u$ is not selected, $R^-[u]$ is excluded from further selection, i.e., $G \leftarrow G-R^-[u]$. Just delete $R^-[u]$ and any edge which has an tail (starting-point) in $R^-[u]$ from $G$.

Let $|R^+[u]|=a$ and $|R^-[u]|=b$, then the recurrence relation is at least as good as
$$T(n)=T(a)+T(n-a)+T(b)+T(n-b) \text.$$

Why at least? Because the underlying undirectd graph of $G-R^+[u]$ or $G-R^-[u]$ may be disconnected.

For a DAG, let ${\Delta^-}(G)$ and ${\Delta^+ }(G) $ represent the maximum indegree and outdegree of vertices of $G$.
If ${\Delta ^ - }(G) \le 1$ and ${\Delta ^ + }(G) \le 1$ , then #ANTICHAIN is in $\mathcal{O}(n)$. Otherwise, my algorithm satisfies the recursion

$$T(n)=T(n-1)+T(n-3) \text,$$

nearly $\mathcal{O}(1.45^n)$.
I wonder whether the recursion is tight? Does there exists a DAG when using my simple divide-conquer algorithm, the running time is $T(n)=T(n-1)+T(n-3)$?

This algorithm is really kind of stupid. Are there more elegant, effective algorithm exist already?  Has anyone thought about the possible FPRAS of it? Or has prove that #ANTICHAIN does not have a FPRAS?

Wow, closed. Sincerely thanks for your answer/comment in advance. ^_^

Counting antichains in an $n$ element poset is equivalent to counting independent sets in a comparability graph on $n$ vertices. The problem of counting the independent sets in an $n$ vertex graph has an $O(1.2461^n)$ time algorithm, see Fürer and Kasiviswanathan http://eccc.hpi-web.de/report/2005/033/ .


Design a sampling process to select an element with probability proportional to its appear probability in a simulation We are given a black box $A$ that can do a simulation. Each time running box A gives a sample $S \in 2^X$ where $X$ is a finite ground set.

Let $\Pr[x]$ be the probability that $x \in X$ appears in the sample $S$.

We try to design a sampling process $B$ which can produce an element in $X$ randomly.

Let $\Pr_1[x]$ be the probability that $x$ is produced by $B$.

We need that $\Pr_1[y]=\frac{\Pr[y]}{\sum_{x \in X} \Pr[x]}$ for each $y \in X$.  An approximately correct algorithm would be OK too, i.e., $\Pr_1[y] \approx\frac{\Pr[y]}{\sum_{x \in X} \Pr[x]}$.

How to design such a sampling process $B$ by using the black box $A$?

First try:

1 run A once and obtain a sample $S$.

2 select an element from $S$ uniformly at random.

3 return $x$.

Intuition: First, the probability that $x \in S$ is $\Pr[x]$. In the second step, each element in $S$ is selected with probability $1/|S|$. The expected value of $|S|$ is actually $\sum_{x \in X} \Pr[x]$. At the first glance, the probability that $y$ is returned seems to be  $\frac{\Pr[y]}{\sum_{x \in X} \Pr[x]}$. However, that $x \in S$ and $|S|$ are not independent.

Counter Example:
Suppose $X=\{1,2\}$ and the distribution associated with $A$ is $\Pr[\{1\}]=0.5$ and $\Pr[\{1,2\}]=0.5$. Then $\Pr_1[1]=0.5+0.5*0.5=0.75$. However, $\Pr[1]/(\Pr[1]+\Pr[2])=1/(1+0.5)=2/3$.

Any help is appreciated.

This can be done efficiently if the size of the samples $S$ is not too large.  Let $m$ denote the maximum possible size of $S$. Then the following procedure outputs exactly the correct distribution:

Draw a sample $S$ (using the black box $A$).  With probability $|S|/m$, keep $S$ and go to step 2.  Otherwise, go back to step 1 and draw a new sample.
Choose an $x$ uniformly at random from $S$.  Output $x$.

You can verify that this yields the correct distribution.  It requires at most $O(m)$ samples (possibly less, depending on the distribution of the size of $S$).

On the other hand, if the samples can be very large, then approximating the distribution accurately may require many samples.  Consider the following situation. Randomly choose a subset $X_0$ of $X$ of size $|X|/2$, and imagine a black box $A$ that works as follows: with probability $1/s$, it outputs the set $X_0$; otherwise, it outputs a single element chosen uniformly at random from $X$ (i.e., a random singleton set).  Then if you draw $s$ samples, you have about a $1-1/e \approx 0.37$ probability of hitting the large set $X_0$.  Moreover, if you don't hit the large set, the probability distribution of your procedure will be off by a total variation distance of $1/s$ (the probability for each element will be off by an additive error of $1/(s|X|)$).  So, if you want a distribution that is close to correct in total variation distance, you'll need many samples. If you want an additive error of $\epsilon$ with probability at least $1-\delta$, you might need something like $O(1/\epsilon)$ samples (I'm not sure about the dependence on $\delta$).


How far has computer science moved past Knuth's TAoCP, if at all? The seminal book The Art of Computer Programming got its start in 1968. I have been finding references to it in many literature reviews, apparently there are many problems for which a review by Knuth done in the 1970s has remained state-of-the-art up until today. It is amazing to me that so many of the theoretical developments of the time have survived decades of the obsolescence cycles that have eliminated all of their original implementations.

What fraction of the content of TAoCP have been eclipsed by later research? If an algorithm is found in TAoCP, what are the odds that a better one is out there in today's literature?

Matrix multiplication exponent has been improved and integer multiplication has recently reached speculated optimal complexity.

Perhaps Han`s sorting applies if correct (on which there was a post here).

Note Knuth`s book is his view.

Modern view is richer. For example I doubt Knuth has spent much time on $NC$ algorithms for perfect matching or derandomization of primality or linear programming or counting algorithms.

So perhaps the algorithms he studies probably on whole not much more progress. However the analogy to mathematics that mathematics problems open in classical view does not mean mathematics has not moved forward holds in algorithms.