Can one do quantum computing without negative amplitudes?

This would be better suited as a comment but since I lack the reputation to comment (!), I am going to write it as an answer. Sorry for the inconvenience.

Yes, you can do quantum computing without complex numbers. As mentioned by @DmitriUrbanowicz it known that Toffoli and Hadamard are universal for quantum computing. (See this simple proof due Dorit Aharonov.)

First, I would like to point out something we all learnt in kindergarten: In quantum computing, the amplitudes can be negative (this happens if you are using Toffoli and Hadamard as your gate set) and even complex (if you are using, say, Toffoli, Hadamard, and Phase) but the probabilities are still non-negative.

Now, as pointed by @JoshuaGrochow above, if your amplitudes themselves are positive real numbers then your gates become classical---you collapse to BPP.

Finally, if you just restrict to your probabilities being positive real numbers and adding up to $1$, then you can potentially solve any problem. This is because you are not putting any restriction on the evolution.


The author is not misinformed, I'm afraid; it's part of the development process of any computer scientist to go through several phases:

Phase 1: $\alpha$-equivalence is easy! Why is everyone making a big deal about this?
Phase 2: $\alpha$-equivalence is impossible! Why should I do computer science if such a basic notion is so impossibly complex?
Phase 3: I've finally understood $\alpha$-conversion! I should write up a paper to explain it to the world!

I'm currently in phase 2. However I'll try to explain my limited understanding.

Your algorithm is flawed: it doesn't distinguish
$$ \lambda x.\lambda y. x\ y$$
and
$$\lambda x.\lambda y. y\ x$$
It's not completely trivial to fix: if you want to prove the equivalence of $\lambda x.\lambda y.x\ y$ and $\lambda y.\lambda x. y\ x$ (which does hold!), you have to find a new variable $z$, and replace $x$ by $z$ in the first term, and $y$ by $z$ in the second. If you simply replace $y$ by $x$ in the second term, you'll get $\lambda x.\lambda x.x\ x$ which is not what you want.
It seems you can "pre-process" your terms by requiring all bound variables to be distinct. This is called hygiene. Unfortunately hygienic terms like
$$ (\lambda x. x\ x)\ (\lambda y.y)$$
become unhygienic when applying $\beta$-reduction:
$$ (\lambda x. x\ x)\ (\lambda y.y)\rightarrow_\beta (\lambda y.y)\ (\lambda y.y)$$

There is a vast literature on how to do this properly. The main approach on how to handle $\alpha$-equivalence that I know of is Nominal Logic which instead of re-naming, advocates "swapping" which is better behaved. The other (non)-solution is to do away with variable names altogether and simply have pointers from variable positions to $\lambda$s, as seen in the variants of the de Bruijn index method.


Expected vs worst-case communication complexity

The reason is that a lower bound on the worst-case complexity automatically implies a lower bound on the expected complexity, so there is no reason to prove the latter.

To see the implication, observe that every randomized protocol with expected complexity $c$ and error probability $\varepsilon$ can be transformed into a randomized protocol with worst-case complexity $c/\varepsilon$ and error probability $2\varepsilon$: The new protocol simulates the old protocol, but forces the simulation to halt after $c/\varepsilon$ bits have been transmitted. By Markov inequality, a forced halting occurs with probability at most $\varepsilon$, so it adds at most $\varepsilon$ to the original error probability.

Since error probability can be amplified, it follows that every randomized protocol with expected complexity $c$ and constant error probability can be transformed into a randomized protocol with worst-case complexity $O(c)$ and the same error probability. Thus, if we show that there is no randomized protocol with worst-case communication $O(c)$ and constant error probability that computes a function $f$, the same holds for protocols with expected communication $O(c)$.


Hardness of approximating chromatic number of triangle-free graphs

They can be 3-colored in polynomial time, no? I didn't check the literature but here is a simple approach: take a DFS tree of the graph and color a node $u$ at depth $d(u)$ with color $(d(u)\mod 3)$. This gives a proper coloring since (1) the neighborhood of each vertex is an independent and (2) two nodes $u,v$ such that $|d(u)-d(v)| \geq 2$ cannot be adjacent.


Questions about P vs NP and geometric complexity theory

The short answer is no these are not known, though they are certainly not out of the question. There are no direct implications known to P vs NP, and we do not even have a conjecture (let alone theorem) that such-and-such a representation is an obstruction iff $VP \neq VNP$.
One can start to get at an implication to ordinary P vs NP by trying to implement GCT in positive characteristic, using the polynomials from GCT I that more closely capture P/poly and NP. Since poly-size Boolean circuits are equivalent in power to poly-size algebraic circuits over a finite field, this would actually show NP not in P/poly. However, in positive characteristic both the geometry and the representation theory get harder (and it's not even clear if multiplicity is the right notion any more, because one is then dealing with modular representation theory, where representations need not be completely reducible).
Even in characteristic zero, we don't know the "general converse" about obstructions, namely, we don't know that $VP \neq VNP$ implies existence of multiplicity obstructions. But we do know that if $VNP \not\subseteq \overline{VP}$ then a separating module (equivalently, HWV obstruction, see Bürgisser-Ikenmeyer STOC '13, arXiv) must exist.


Breadth first search and Eppstein K shortest paths algorithm

The main reason is that the non-constant degree would imply that the time per result is too high. The number of nodes found by the search, in the end, is going to be k, but all but the last one needs to have their children expanded, so the number of expanded nodes is kd where d is the degree. Unless d is O(1) this will be larger than the eventual time bound of the algorithm.


Efficiently picking free position from array with uniform probability.

Reservoir sampling can be used to uniformly pick a "free position with only one scan".


I think the best known result is that the blow-up can be quasi-linear (the new instance has size $n\cdot(\log n)^{O(1)}$). This is given in Dinur's 2007 paper (Thm 8.1), which is also cited by the Moshkovitz-Raz paper mentioned by Yuval Filmus.

As far as I know it is still open if the blow-up can be brought down to linear. Some people call this the Linear PCP conjecture, see e.g. the recent paper by Bonnet, Egri and Marx


The randomized query complexity of the conjoined trees problem

I think I have a deterministic algorithm that finds the exit in $O(n2^{n/2})$ oracle calls.

First, find the labels for all the vertices of distance $n/2$ from the entrance. This takes $O(2^{n/2})$ queries. Then, start from the entrance and walk $n+1$ steps to get to a node $X$ of distance $n+1$ from the entrance. We will try to reach the exit from this node.

We have two options of where to go from $X$, and we wish to choose the one closer to the exit. To do this, pick one of the options arbitrarily, arriving at a node $Y$. Then explore all the $O(2^{n/2})$ ways of walking $n/2$ steps from $Y$. If one of them gives a label of distance $n/2$ from the entrance, we know that going from $X$ to $Y$ was the wrong choice. Otherwise, $Y$ was the right choice. Thus in $O(2^{n/2})$ we found a node $X_2$ of distance $n+2$ from the entrance.

We can keep proceeding this way. To find a node of distance $n+3$ from the entrance, we start at $X_2$ and walk two arbitrary steps. We then explore all options of walking $n/2$ additional steps (while never walking backwards), and check if any of them have distance $n/2$ from the entrance. This will happen if and only if the first step we walked from $X_2$ was wrong.

Getting to the exit requires doing this $n$ times, for a total of $O(n2^{n/2})$ oracle calls. In addition, perhaps surprisingly, this algorithm is deterministic.

Edit: Just to clarify, to get from $X_t$ to $X_{t+1}$, we walk $t$ arbitrary steps, then run a search of depth $n/2$, for a total of $t+2^{n/2}$ steps. If the first step lead away from the exit, then all the first $t$ steps did, and we therefore find a label of distance $n/2$ from the entrance. This means $t+2^{n/2}$ steps suffice for determining the next single step to take from $X_t$.


Is there a constant factor approximation algorithm for 2D rectangle coloring problem?

As suggested by the other answer, $\Omega(\log n)$ lower bound is not too hard to see. Let us do the sweeping bottom up with a horizontal line. The idea is to build components that require larger and larger number of colors. In particular, let $C(i)$ be a gadget that has a top rectangle with color $i$ (i.e., the first fit would assign it color $i$). Clearly, $C(1)$ is just a single rectangle.
The component $C(2)$ is

In general, the component $C(k)$ is a rectangle with $C(1), \ldots, C(k-1)$ hanging below it:

Now, it is easy to verify that a fit-first algorithm with sweeping  horizontally from the bottom would use $k$ colors to color $C(k)$. However, the intersection graph of $C(k)$ is just a tree, and it can be colored by $2$ colors. Now, $C(k)$ is just a Fibonacci tree in structure, and as such the number of nodes in it is $2^{O(k)}$, which implies $\Omega( \log n )$ gap.

Since there is a simple algorithm that gets $O( \log n)$ approximation to coloring of rectangles, this might be tight. I don't know.


Piotr Indyk has some lecture notes on streaming and related topics at stellar.mit.edu/S/course/6/fa07/6.895

A MADALGO summer school a few years ago also has some good notes. I would say all the papers listed in the bibliography there are good reads for anyone interested in the area.


Common terminology used for lower/upper bounds

The term “tight” has multiple uses, as is mentioned in a comment. However, you seem to be interested in a combinatorial context or on a combinatorial-type problem so I’m going to assume that contexts. Let’s say we are talking about a function, $f(n)$, that bounds $g(n)$. In your case, $g$ is the true number of vertices of the $n^{th}$ graph in your family and $f$ is your bound.

  $f$ is a tight bound for $g$ if there exists an $n$ such that $g(n)=f(n)$.

Notice that $f$ can be tight but still improvable. If you have that $g(n)=n-\epsilon\sin((n-1)/100)$ then $f(n)=n^2$ is a tight bound. It is an upper bound for $g$ and they agree for $n=1$. However, that doesn’t mean it cannot be improved. A better bound might be $f_k(n)=n^{1+k^{-1}}$. This family has the property that $g(n)<f_k(n)<f(n)$ for $n>1$ and $g(1)=f_k(1)+f(1)$.

I am generally not a fan of the term “optimal bound” because it’s usually inaccurate. The optimal bound for a sequence of integers is simply that sequence of integers, so if you have an “optimal bound” you almost always have an expression for the underlying process.

There are contexts in which the previous paragraphs is wrong, however, and you seem to think that you’ve proven that you bound is the best possible. If that’s the case, there aren’t any caveats to that sentence, and what you’ve proven is indeed a bound rather than an expression for the number of vertices in the graph, then “optimal bound” or “best possible bound” is the terminology that I would recommend using.


Hypersequents: proof term assigments or translations to hybrid logic

I know this is a bit late, but perhaps it is still of interest.

While not exactly the logic you are interested in, Gödel-Dummett logic, the intermediate logic characterised by linear Kripke-frames, is closely related to S4.3, and for this logic people have looked into similar questions:

The paper A Lambda Calculus for Goedel-Dummett Logic Capturing Watifreedom by Yoichi Hirai gives a lambda calculus based on a hypersequent calculus for that logic.
The paper A Natural Deduction System for Intuitionistic Fuzzy Logic by Matthias Baaz, Agata Ciabattoni and Christian Fermüller gives a natural deduction system for the same logic, which might be used to give proof term assignments.

Also, you might be interested in the paper From Frame Properties to Hypersequent Rules in Modal Logics by Ori Lahav, which includes an alternative hypersequent calculus for S4.3.


Question on the Prize-Collecting TSP's ratio related to inapprox. of general TSP

Edited may answer, I hope it becomes clearer now (or I find out what I did not understand):

Your process is as follows: If you have an edge $e = \{u,v\}$ with weight $t$ you replace $e$ by a path of length two with edges $\{u,z_e\}$ and $\{z_e,v\}$. $z_e$ is a new node and each of the two new edges get weight $t/2$. For each edge, we introduce a new node.

So far, we do not have a metric instance, because there is no edge between $u$ and $v$ so far and the distance between $u$ and $v$ is infinite. Therefore, you take the shortest path metric to get these distances. (I suppose that this is what you mean by "having Euclidean distances equal to that". Otherwise, you should clarify this.)

My point is that after adding distances according to the shortest path metric, the distance between $u$ and $v$ might not be $t$ anymore, so you do not get your original instance back:
Consider a triangle with edge lengths $1$, $1$ and $t$. Let $u$ and $v$ be the nodes of the edge with weight $t$. Apply your construction. The shortest path between $u$ and $v$ is $2$ (it takes the four edges with weight $1/2$) and not $t$.

Btw: Euclidean distance should just be distance in the question.


Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power

The result appears as Theorem 7 in the following paper by Smolensky:

Smolensky, Roman. "On representations by low-degree polynomials." Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. IEEE, 1993.
https://doi.org/10.1109/SFCS.1993.366874

The techniques in this paper are still algebraic but slightly different (and more general) than what people usually teach as the "Razborov-Smolensky polynomial argument".

Yuval Filmus has a nice set of notes on the above paper as well, with more exposition and details in some places:
http://www.cs.toronto.edu/~yuvalf/Smolensky.pdf

Update: Given that Smolensky's paper is quite terse, let me say a few words about how the implied proof proceeds. Since Filmus' notes, linked above, are fairly thorough, I won't try to be completely precise, but instead give the main technical ideas.

1) The connection between $ACC[q]$ and polynomials seems to indeed be the standard one. More precisely, if there is a constant-depth circuit computing $F$, then there exists a polynomial $P$ of polylogarithmic degree that approximates $F$, where the degree depends on the depth. Unless I'm mistaken, it is actually straightforward to see that this result works even when $q$ is a prime power. See for example section 4 in these lecture notes from MIT.

2) Then, the goal is to prove that such low-degree polynomials cannot approximate the $MOD_p$ function when $(p,q) = 1$, which shows that $MOD_p \notin ACC[q]$.

3) To prove this, Smolensky establishes in Theorem 4 a relationship between
 (i) the Hilbert function for the one-set of $F$, that is, the set $S = \{x \mid F(x) = 1\}$, and
 (ii) the ability of any low-degree polynomial $P$ to approximate $F$, where $F = MOD_p$ for this question.
Theorem 4 is proved in the paper (albeit in quite a terse way, hence the pointer to Filmus' notes).

4) The final step is to analyze the Hilbert function of the one-set of $F$. Smolensky refers to his proof for Parity for the "proof" of $MOD_p$ case. What actually needs to be shown is that the Hilbert function on $S$ is as large as possible, for all degrees less than $n/2$. In his words "...we proved that over $S$ there is no linear relation among monomials of degree smaller than $n/2$. Hence for $m < n/2$, $l^a_m(S)$ are as large as possible." The reason he omits the formal proof is that it is indeed the same as the case for parity, once you have the equation (8) that he provides.

I hope this makes sense, with the omitted details being medium-hard exercises.


can some one use a polynomial one-to-many reduction for NP-comp problems?

I think what you are looking for is the notion of polynomial-time Turing reduction, denoted $\leq_{T}^{p}$ (also called Cook reduction, since this was the notion of reduction Cook used in the paper in which he defined NP-completeness; poly-time many-one reductions are called "Karp" or "Karp-Levin" for a similar reason), or polynomial-time truth-table reductions, denoted $\leq_{tt}^{p}$.

For any notion of reduction, you get a notion of NP-completeness: e.g. a problem is "NP-complete under $\leq_{T}^{p}$ reductions" if it is in NP and every problem in NP $\leq_{T}^{p}$-reduces to it.  The different notions of completeness are a priori distinct; however, even if they are distinct, showing that a problem is NP-complete under Cook reductions is still good evidence of its intractability.

Terminologically, when people say "NP-complete" without further specifying, they usually mean NP-complete under many-one reductions.

Lutz and Mayordomo showed that if NP does not have measure 0 in EXP,  there are problems that are NP-complete under $\leq_{T}^{p}$-reductions that are not NP-complete under $\leq_{m}^{p}$-reductions. The Lutz and Mayordomo paper has lots of other references, but one result that should be mentioned is that (under no assumptions), there are problems that are  $\leq_{T}^{p}$-complete for $NE$ that are not $\leq_{m}^{p}$-complete for $NE$ [1,2].

Truth-table reductions can be viewed either as a multi-query version of many-one reductions (in a sense they are "many-many") or as non-adaptive Turing reductions, or as Turing reductions in which all the queries are made in parallel.  The idea is that the reducing machine looks at the input, decides all the queries it's going to make without asking any of them, then asks all of them and gets answers from the oracle, then decides its answer without making further queries.

[1] H. Buhrman, S. Homer and L. Torenvliet, Completeness for nondeterministic complexity classes, Math. Systems Theory 24 (1991) 179-200.

[2] O. Watanabe, On the Structure of Intractable Complexity Classes, PhD thesis, Tokyo Institute of Technology, 1987.


In a random perfect matching of a regular bipartite graph, are all edges equally probable?

No.

Construction: Take two copies of $K_{3,3}$, one with the nodes $\{a,b,c\} \cup \{a',b',c'\}$ and the other one with the nodes $\{d,e,f\} \cup \{d',e',f'\}$. Remove the edges $(c,c')$ and $(d,d')$. Add the edges $(c,d')$ and $(d,c')$.


Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1

EDIT: My original proof had a bug. I now believe that it is fixed.

We reduce the problem of EQUAL SUM SUBSETS to this problem. EQUAL SUM SUBSETS is the problem of: given a set of $m$ integers, find two disjoint subsets which have the same sum. EQUAL SUM SUBSETS is known to be NP-complete.

Suppose these bit strings were not vectors but representations of $n$-bit numbers in binary. Then the problem would be NP-complete by a reduction from EQUAL SUM SUBSETS.  I will show how to make these vectors behave like they are binary numbers. What we need is to be able to do carries; that is, for every pair of adjacent coordinates, we need to be able to replace the vector ..02.. by ..10.. .

How can we do that? We need a gadget that lets us do that. In particular, we need two subsets whose sums are ..02.. x  and ..10.. x, where x is a bit string using new coordinates (i.e., coordinates which aren't any of the $n$ coordinates making up the binary representations), and where there is only one way to create two subsets with the same sum in the new bit positions corresponding to x.

This is fairly easy to do. For every pair of adjacent bit positions, add three vectors of the following form. Here the last two bits are coordinates which are non-zero only in these three vectors, and every bit not explicitly given below is 0.

  ..10.. 11
  ..01.. 10
  ..01.. 01

Let me do an example. We want to show how 5+3=8 works.

Here is 8 = 5 + 3 in binary:

  1000

=

  0101
  0011

These bit strings give the same sum in binary, but not in vector addition.

Now, we have carries in the 1, 2, 4 places, so we need to add three sets of three vectors to the equation so as to perform these carries.

  1000 00 00 00
  0001 00 00 01
  0001 00 00 10
  0010 00 01 00
  0010 00 10 00
  0100 01 00 00
  0100 10 00 00

=

  0101 00 00 00
  0011 00 00 00
  0010 00 00 11
  0100 00 11 00
  1000 11 00 00

These sets now have the same sum in vector addition. The sums are:

  1222 11 11 11

in both cases.

This construction works great if there is only one carry per position, but there could potentially be up to $n$ carries per position, and you need to make sure that your construction can handle up to $n$ carries, and that the different carries don't interfere with each other. For instance, if you added two different sets of three vectors for the same pair of adjacent positions (which is what I proposed in my original proof):

  ..01.. 01 00
  ..01.. 10 00
  ..10.. 11 00
  ..01.. 00 01
  ..01.. 00 10
  ..10.. 00 11

you have the problem that you get two different sets of vectors giving the same sum:

  ..01.. 01 00
  ..01.. 10 00
  ..10.. 00 11

=

  ..01.. 00 01
  ..01.. 00 10
  ..10.. 11 00

How to fix this? Add one set of vectors which lets you carry 1, one set which lets you carry 2, and one set for 4, 8, $\ldots$, 2$^{\lfloor \log n \rfloor}$. I'm not going to go work out the details of this construction right now, but it should be fairly straightforward. Since each number has a unique binary representation, this will let you carry any number up to $n$. For carrying 4, for example, you need find four vectors which have the same sum as two vectors, and for which this is the only linear relation between the two sets. For example, the set

  ..01.. 11000
  ..01.. 00100
  ..01.. 00010
  ..01.. 00001
  ..10.. 10001
  ..10.. 01110

works. You can easily check that the relation

  11000
  00100
  00010
  00001

=

  10001
  01110

is the only possible relation among these six vectors because the matrix formed by these six rows has rank 5.


Papers on relation between computational complexity and algebraic geometry/topology?

As background, you should definitely study Ben-Or's work on lower bounds, as well as Mulmuley's P vs NC paper.


How to analyze a randomized recursive algorithm?

Here is a proof that this algorithm runs in $O(n\,m)$ time in expectation and with high probability.

First consider the algorithm modified so that $k$ is chosen in $\{2,3,..,\min(c,n)\}$ instead of randomly in $\{1,2,...,\min(c,n)\}$.

Lemma 1. For this modified algorithm, regardless of the random choices of the algorithm, the time is always $O(n\,m)$.

Proof.  Fix an input $A[1..n]$ and $B[1..m]$ and fix the random
choices of the algorithm arbitrarily.  In each (possibly recursive)
call to partition(), the two arguments correspond respectively to two
subarrays: a subarray $A[i_1..i_2]$ of $A$ and a subarray
$B[j_1..j_2]$ of $B$.  Identify such a call with the rectangle
$[i_1-1,i_2] \times [j_1-1,j_2]$.  Thus, the top-level call is
$[0,n]\times[0,m]$, and each recursive call corresponds to a
sub-rectangle within this $n\times m$ rectangle.  These rectangles
form a tree, where the rectangle corresponding to one call has as
children the rectangles that correspond to the calls made directly by
that call.  Each parent rectangle is partitioned by its child
rectangles, which form a $k\times k$ grid (of non-uniform rectangles) with $k$ at least 2.  Of course each rectangle's corners have only integer coordinates.

The running time of the algorithm is bounded by a constant times the sum, over the rectangles, of the perimeters of all of these rectangles.  (This is because the time within each call is O(n+m), and the perimiter of the corresponding rectangle is $2(n+m)$.)

I claim that in any set of rectangles as described above, the sum of the perimeters is at most $12 n\,m$.  If true, this proves the lemma.

To prove the claim, observe first that, because $k \ge 2$, for any parent rectangle, the perimeter of the parent is at most 2/3 times the total perimeter of the children. (The perimeter of the parent is $2(n+m)$.  The total perimiter of the children is $(1+k)(n+m)$, and $k >= 2$.)

It follows by a standard charging argument that the total perimiter of all the rectangles is at most $(1 + 2/3 + (2/3)^2 + \ldots ) = 3$ times the perimiter of just the leaf rectangles.  (The observation implies that $P_N \le (2/3) P_T$, where $P_N$ is the total perimeter of the non-leaf rectangles and $P_T$ is the total perimeter of all the rectangles.  This implies $P_T \le 3(P_T-P_N)$, and $P_T-P_N$ is the total perimeter of the leaf rectangles.)

Next, observe that the leaf rectangles partition the original $n\times m$ rectangle.  The maximum possible perimeter of the leaves is obtained when the leaves correspond to the unit squares with integer endpoints, in which case the total perimeter of the leaves is $4\,n\,m$.  Thus, the sum of the perimeters is at most $3\cdot 4\,n\,m$, that is, at most $12 n\,m$.

This proves Lemma 1.

Corollary: The original algorithm runs in $O(n\,m)$ time in expectation.

Proof. If partition chooses $k=1$, it just duplicates the rectangle.  Since $n>1$, the probability that $k=1$ is at most 1/2.  Thus, the expected number of times each rectangle is duplicated is at most 1 (and the expected number of copies of each rectangle is at most 2).  Thus, for the original algorithm, the expected sum of the perimiters of all the rectangles is at most twice that of the modified algorithm, i.e. at most $24 n\,m$.  Just as in the analysis of that algorithm, the running time is proportional to this sum, so is $O(n\,m)$.  QED

Corollary. The bound also holds with high probability (assuming both $n$ and $m$ tend to infinity).

Proof sketch. Fixing every random choice except the number of duplicates of each rectangle, the time is proportional to
$$\sum_{r\in R} (1+X_r) |r|$$
where $R$ is the set of rectangles generated, $X_r$ is the number of times $r$ is duplicated (i.e., times when $k=1$ for that rectangle), and $|r|$ is the perimeter of $r$.

The variables $\{X_r : r \in R\}$ are independent, and each $|r|$ is $O(n+m) = o(n m)$, so by a standard Chernoff bound, the probability that the sum exceeds twice its expectation is $o(1)$.  (More specifically, take $Y_r = (1+X_r) |r|/2(n+m)$, then apply Chernoff to the sum of the $Y_{r}$'s.) QED

As an aside: if the algorithm were to choose $k$ randomly up to $\min(n,m)$ instead of $\min(c,n)$ and then do $O(m n)$ work in each call (instead of $O(m+n)$), the total time would still be $O(mn)$ in expectation.

Proof. First note that the total time would be proportional to the sum of the areas of all the rectangles.  This sum equals the sum, over the integer coordinates $(i,j)$, of the number of rectangles that $(i,j)$ occurs in.  This is $O(nm)$ in expectation because, in expectation, any given $(i,j)$ in the original rectangle occurs in $O(1)$ rectangles.

To see this, suppose $(i,j)$ is contained in a rectangle $r$, and consider the call to partition on $r$.  Let $q(r) = \min(n_r,m_r)$.  Let $r'$ be the rectangle that is the child (containing $(i,j)$) of $r$.  With probability at least $1/3$, $k$ is chosen to be at least $(2/3)q(r)$.  Conditioned on that, $E[q(r')] \le 3/2$, so with constant probability $q(r')$ is at most 1.  If that happens, then $r'$ is a leaf (has no children).  It follows from this that the expected number of rectangles that $(i,j)$ is in is $O(1)$.  QED

(Whether the $O(nm)$ bound would hold with high probability is an interesting question.. I think it would.  Certainly $O(nm\log(nm))$ would hold w.h.p.)


Time complexity of counting triangles in planar graphs

The number of occurrences of any fixed subgraph H in a planar graph G can be counted in O(n) time, even if H is disconnected. This, and several related results, are described in the paper Subgraph Isomorphism in Planar Graphs and Related Problems by David Eppstein of 1999; see Theorem 1. The paper indeed uses treewidth techniques.


Software package for decomposing quantum circuits

This package (CUGates.m) was announced on the arXiv a couple of days ago which could be useful for you. It uses Mathematica. I haven't tried it out though, and it may or may not do what you need. From the abstract:

  This paper presents a highly efficient decomposition scheme and its
  associated Mathematica notebook for the analysis of complicated
  quantum circuits comprised of single/multiple qubit and qudit quantum
  gates. In particular, this scheme reduces the evaluation of multiple
  unitary gate operations with many conditionals to just two matrix
  additions, regardless of the number of conditionals or gate
  dimensions. This improves significantly the capability of a quantum
  circuit analyser implemented in a classical computer. This is also the
  first efficient quantum circuit analyser to include qudit quantum
  logic gates.


Natural NP-complete problems with "large" witnesses

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

See also this possibly related question


What is the complexity of rectangle packing when rotations are allowed?

We can reduce the no-rotations packing problem to the rotations-allowed packing problem as follows.  Take any instance $(R, r_1, r_2, \dots, r_n)$ of the no-rotation problem.  Vertically scale the entire instance by twice the ratio of the smallest width of any rectangle $r_i$ divided by the height of the container rectangle $R$.  (This ratio has a polynomial number of bits, so the transformation can be executed in polynomial time.)  Each scaled rectangle $r'\!\!_i$ fits inside the scaled container $R'$ only in its original orientation, so allowing rotations adds no new solutions.


Communication complexity for deciding associativity

There are $n^{n^2}$ binary operations on $S$. The question is how many of them are associative. Kleitman, Rothschild and Spencer give an asymptotic counting formula for this problem in their paper The number of semigroups of order $n$. It has a relatively simple form in what they call the "non-rare instances" where the peak of $f(t)$ dominates so the other terms can be neglected without affecting the asymptotics. You should be able to give a lower bound for your question by cranking through the math with this formula.


Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

Any arithmetical statement provable in ZFC is provable in ZF, and hence does not "need" the axiom of choice.  By an "arithmetical" statement I mean a statement in the first-order language of arithmetic, meaning that it can be stated using only quantifiers over natural numbers ("for all natural numbers x" or "there exists a natural number x"), without quantifying over sets of natural numbers.  At first glance it might seem very restrictive to forbid quantification over sets of integers; however, finite sets of integers can be "encoded" using a single integer, so it's O.K. to quantify over finite sets of integers.

Virtually any statement of interest in TCS can, with perhaps a bit of finagling, be phrased as an arithmetical statement, and so doesn't need the axiom of choice.  For example, $P\ne NP$ looks at first glance like an assertion about infinite sets of integers, but can be rephrased as, "for every polynomial-time Turing machine, there exists a SAT instance that it gets wrong," which is an arithmetical statement.  Thus my answer to Ryan's question is, "There aren't any that I know of."

But wait, you may say, what about arithmetical statements whose proof requires something like Koenig's lemma or Kruskal's tree theorem?  Don't these require a weak form of the axiom of choice?  The answer is that it depends on exactly how you state the result in question.  For example, if you state the graph minor theorem in the form, "given any infinite set of unlabeled graphs, there must exist two of them such that one is a minor of the other," then some amount of choice is needed to march through your infinite set of data, picking out vertices, subgraphs, etc. [EDIT: I made a mistake here. As Emil Jeřábek explains, the  graph minor theorem—or at least the most natural statement of it in the absence of AC—is provable in ZF.  But modulo this mistake, what I say below is still essentially correct.] However, if instead you write down a particular encoding by natural numbers of the minor relation on labeled finite graphs, and phrase the graph minor theorem as a statement about this particular partial order, then the statement becomes arithmetical and doesn't require AC in the proof.

Most people feel that the "combinatorial essence" of the graph minor theorem is already captured by the version that fixes a particular encoding, and that the need to invoke AC to label everything, in the event that you're presented with the general set-theoretic version of the problem, is sort of an irrelevant artifact of a decision to use set theory rather than arithmetic as one's logical foundation.  If you feel the same way, then the graph minor theorem doesn't require AC.  (See also this post by Ali Enayat to the Foundations of Mathematics mailing list, written in response to a similar question that I once had.)

The example of the chromatic number of the plane is similarly a matter of interpretation.  There are various questions you can ask that turn out to be equivalent if you assume AC, but which are distinct questions if you don't assume AC.  From a TCS point of view, the combinatorial heart of the question is the colorability of finite subgraphs of the plane, and the fact that you can then (if you want) use a compactness argument (this is where AC comes in) to conclude something about the chromatic number of the whole plane is amusing, but of somewhat tangential interest.  So I don't think this is a really good example.

I think ultimately you may have more luck asking whether there are any TCS questions that require large cardinal axioms for their resolution (rather than AC).  Work of Harvey Friedman has shown that certain finitary statements in graph theory can require large cardinal axioms (or at least the 1-consistency of such axioms).  Friedman's examples so far are slightly artificial, but I wouldn't be surprised to see similar examples cropping up "naturally" in TCS within our lifetimes.


shortest path algorithm taking into account angular deviation

My first guess would be to do a simple graph transformation and running the shortest-path algorithm on the transformed graph. This way, we could convert angular deviation between two roads into an additional shortest path cost along the path and thusly penalize paths involving heavy turns.

The conversion would go along the following lines: say, we are at some node 'n' of degree 'd'. Then, we could substitute this 'n' with a complete graph on 'd' nodes, with each node in this complete graph associated with an edge incident to 'n'. In addition, a 'u-v' edge in the complete graph would have cost proportional to the angle between the edges corresponding to 'u' and 'v'. Exactly how you set the proportion is a matter of taste: I would first try a linear function and experience with different scaling factors.


It is perfectly possible to define satisfaction using just sentences as you suggest, and in fact, it used to be the standard approach for quite some time.

The drawback of this method is that it requires to mix semantic objects into syntax: in order to make an inductive definition of satisfaction of sentences in a model $M$, it is not sufficient to define it for sentences of the original language of $M$. You need to first expand the language with individual constants for all elements of the domain of $M$, and then you can define satisfaction for sentences in the expanded language. This is, I believe, the main reason why this approach went into disuse; if you use valuations, you can maintain a clear conceptual distinction between syntactic formulas of the original language and semantic entities that are used to model them.


What is the best text of computation theory/theory of computation?

I strongly recommend the book Computational Complexity: A Modern Approach by Arora and Barak. When I took computational complexity at my Master level, the main textbook is Computational Complexity by Papadimitriou. But, maybe due to my background in Software Engineering, I found the writing in Papadimitriou challenging at times. Whenever I had problem understanding Papadimitriou's book, I simply went back to Sipser, or read the draft of Arora and Barak.

In retrospect, I really like Papadimitriou's book, and I often find myself looking up from this book. His book has plenty of exercises that are quite effective at connecting readers to research-level questions and open problems.

In any case, you should have a look at both Papadimitriou and Arora-Barak. People also suggest Oded Goldreich's textbook, but I really prefer the organization of Arora-Barak.


Is there a name for this concept in Communication Complexity?

What you call $cc_{max}$ is known as the worst-case partition communication complexity, and what you call $cc_{min}$ is known as the best-case partition communication complexity.
These have been studied for several functions, you can find some results in the book of Kushilevitz and Nisan in chapter 7.
I'm not aware of anyone introducing the difference or the ratio as a parameter to study.


Complexity for single-linkage clustering with max norm

Single-linkage clustering gives the same connections in the same order that you would find using Kruskal's algorithm for the minimum spanning tree, and the clustering can be found by finding a minimum spanning tree and then running Kruskal's algorithm on the resulting $(n-1)$-edge graph. Therefore, the time is bounded by the MST construction + the time to sort the edges of the MST.

The two-dimensional $L^\infty$ MST can be constructed in $O(n\log n)$ time using rectilinear Voronoi diagrams, and an $O(n\log n)$ algorithm for the three-dimensional version is given by

Krznaric, Drago; Levcopoulos, Christos; Nilsson, Bengt J. (1999),
Minimum spanning trees in $d$ dimensions,
Nordic J. Comput. 6 (4): 446–461.

more generally an algorithm that is within a polylog factor of linear for any fixed dimension is given by

Gabow, Harold N.; Bentley, Jon Louis; Tarjan, Robert E. (1984), Scaling and related techniques for geometry problems, Proc. 16th ACM STOC, pp. 135–143, doi:10.1145/800057.808675


Using partial functions to prove correctness

If I read you correctly, the intuition you have in mind goes like this:

Suppose we have a program $P$, which takes a function as an argument. Further suppose that we have two functions $f$ and $g$, such that $f$ terminates on a subset of the inputs $g$ terminates on, but agrees with $g$ whenever they both terminate.

Now, if $P\;g$ is partially correct, then you want to argue that $P\;f$ must also be partially correct. After all, the "only thing" that $P$ can do with its functional parameter is to apply it (what you call "use as an oracle"), and so $P\;f$ must compute the same values as $P\;g$, possibly terminating less often.

This is more or less exactly the intuition underlying domain theory. The idea is that we can interpret computations at a particular type as CPPOs, or chain-complete pointed partial orders.

That is, a CPPO is a triple $(X, \bot, \leq)$, with $X$ as the set of elements denoting computations, $\bot$ as the nonterminating computation, and $\leq$ as a partial order representing how close to fully defined a computation is. $\bot$ is the least element in this partial order, and the chain-completeness condition says that if you have a countable chain $x_0 \leq x_1 \leq \ldots$, then the chain has a least upper bound $\bigsqcup_{i \in \mathbb{N}} x_i$.

Programs are interpreted by continuous functions between CPPOs, with the idea that continuity is a stand-in for computability. That is, a function $f : X \to Y$ should be a monotone function which preserves lubs.

In particular, the set of continuous functions $X \to Y$ also forms a CPPO, with the least element given by $\lambda x.\;\bot_Y$, and the order given pointwise, so that

$$f \leq_{X \to Y} g \iff \forall x \in X.\; f\;x \leq_Y g\;x$$

Then the property you want follows more or less instantaneously. Suppose we have a continuous $P : (X \to Y) \to Z$. Then $f$ being "less defined" than $g$ amounts to saying that $f \leq g$. Then, by the continuity of $P$, it follows that $P\;f \leq P\;g$.

Samson Abramsky and Achim Jung have a chapter on domain theory in the Handbook on Logic in Computer Science, which is freely available online.


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

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

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


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

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


Bi-criteria combinatorial approximation algorithms for min k-vertex cover

Partial Vertex Cover (PVC) solves the problem without the need for bi-criteria. In PVC the input is a graph $G=(V,E)$ and an integer $m' \le |E|$ and the goal is to find a minimum cardinality subset $S$ of vertices such that they cover at least $m'$ edges. Hence, if $m' = |E|$ we have the usual Vertex Cover problem. A $2$-approximation is known for PVC. To solve the OP's question, if we know the number of edges that are not covered by an optimum solution consisting of $k$ vertices (which we can guess), say $\ell$, we set $m' = |E| - \ell$ and run the approximation algorithm for PVC. We will obtain a set $S \subseteq V$ of cardinalty at most $2k$ such that no more than $\ell$ edges are uncovered.


Since k-means minimizes the within-cluster sum of squares, the cluster centers will always be the mean of the points within that cluster. If you use a different criterion, you are basically using a different method than k-means.


I am not sure I understood the question.  But it seems to me that under the assumption that $PSPACE$ contains problems requiring exponential time, such problems would fulfill your requirements, since if $M$ is $O(\log N)$ you would need an exponential number of I/O operations (since you can't "stay" in the same memory block of size $O( \log N)$ more than a polynomial number of steps without going into a cycle) and if $M=N$ you would only need a linear number of I/O operations. Also, concerning your observation that such a problem cannot belong to $P$, it is correct if the speedup must hold for values of $M$ that are $\Omega(N)$ (since it would mean we have an exponential number of operations). But if the speedup only applies to smaller values of $M$, intuitively I believe this is not true, because I feel it should be possible to design a problem that is in fact the concatenation of smaller problems of size $O(\log N)$ each requiring exponential time in its own size, and an exponential number of I/O operations (that is, $poly (N)$, since $poly(N)$ is exponential in $O(\log N)$). In practice I believe $PSPACE$-complete problems such as $TQBF$ fulfill your condition.


Hamiltonian Cycle as an integer linear programming problem

Describing connectivity in integer programming is not as straightforward as the rest of the reduction, I think.

However, it is quite clean to reduce HAMCYCLE to SAT (e.g. here), and it is very clean to reduce SAT to integer programming. I think you will end up with a system that is not all that complicated. Perhaps it is worth doing so than busting your head over a direct reduction.


Regular languages and constant communication complexity

For $\Rightarrow$, you have "Communication Complexity", Eyal Kushilevitz in Advances in Computers, Volume 44, 1997 (http://www.sciencedirect.com/science/article/pii/S0065245808603423).

You can also find a section "Communication Complexity and Chomsky Hierarchy" in the book "Communication Complexity and Parallel Computing" by Juraj Hromkovič where it is proven. It may be that $\Leftarrow$ is also proven somewhere in the book but I fail to find it here. The closest thing there seems to be is Exercise 5.2.5.2 but, it is only an exercise (see the whole Chapter 5 too, which extensively study finite automaton but I do not think it explicitly answers your question).

For what it is worth, the proof of both directions looks easy so I think that if you need it in a paper you can sketch it quickly: for $\Rightarrow$, take a finite automaton for $L$ and observe that it is sufficient for Alice to communicate the state she reaches after having read her part of the input. Then Bob finishes the simulation in the automata. For $\Leftarrow$, if you have a protocol bounded by a constant, then $L$ has a finite number of quotient $w^{-1}L = \{u : wu \in L\}$ which is a well-known characterization of regular languages.


How can I find the distribution of a recursive relation with two parameters?

I've never done an exact solution for a "change of variable" problem with a recursive function, but I can give you a formula that might help. If $p : \mathbb{Z}_p \times \mathbb{Z}_p \to [0,1]$ is a probability mass function (i.e. sums to one over its domain), then the probability of any specific output for $G$ is

$$\mathrm{Pr}[x]\ =\ \sum_{(n,m) \in G^{-1}(\{x\})} p(n,m)$$

where $G^{-1} : \mathcal{P}(F) \to \mathbb{Z}_p \times \mathbb{Z}_p$ computes preimages under $G$ by

$$G^{-1}(A)\ =\ \{(n,m) \in \mathbb{Z}_p \times \mathbb{Z}_p\ \lvert\ G(n,m) \in A\}$$

In other words, it's the sum of the probabilities of the pairs $(n,m)$ for which $G(n,m) = x$.

Despite the size of the formula, there are advantages to having it in terms of preimages. Unlike inverses, they always exist. They are often compositional, meaning that preimages under a function can often be defined in terms of preimages under its defining subexpressions, which is often necessary when dealing with recursion. For example, if $f : A \to B$ and $g : B \to C$, then

$$(g \circ f)^{-1}\ =\ f^{-1} \circ g^{-1}$$

Another: if $f_1 : A \to B_1$, $f_2 : A \to B_2$, and $f : A \to B_1 \times B_2$ is defined by $f(x) = (f_1(x),f_2(x))$, then

$$f^{-1}(B_1' \times B_2')\ =\ f_1^{-1}(B_1') \cap f_2^{-1}(B_2')$$

for all $B_1' \subseteq B_1$ and $B_2' \subseteq B_2$.

For addition... well, there might be something for your specific problem.

At the very least, it leads to a nice way to factor a program that enumerates the probabilities of each $x \in F$.


Actually, the motivation for introducing dependent types goes in the opposite direction! Curry had noticed that there was a direct correspondence between typed terms in the $SK$ calculus and proofs in (minimal implicational) propositional logic, but there was no programing language known to correspond in such a way to predicate logic.

Indeed, introducing $\Pi$ types are necessary to model propositions of the form $\forall x.P$, which clearly do not admit representation as a simple type $A\rightarrow B$. (Actually, one can imagine a "forgetful" translation, where $A$ is the domain of $x$, and $B$ is the domain of "proofs of $P$", and in this way one can construct something very similar to certain forms of realizability, but this is clearly not an isomorphism.)

In summary, there is an isomorphism between functions $\mathbb{N}\rightarrow\mathbb{N}\rightarrow\mathbb{N}$ in the simply typed $\lambda$-calculus and proofs of $N\Rightarrow N\Rightarrow N$ in minimal logic, in the context $N,N\Rightarrow N$.

It is clear, however, that most programing languages have more than the STLC to define functions, and that there is more reason to care about the operational behavior of programs than that of (most) proofs.

It makes sense to use dependent types to explore these distinctions, as well as more subtle notions of types to distinguish between "computationally relevant" things and "computationally irrelevant" ones (e.g. in Coq, the $\mathrm{Prop}$ vs $\mathrm{Set}$ distinction).

But these were not the original motivation for dependent types.

As a direct answer to your question, the "statement" $\mathbb{N}\Rightarrow\mathbb{N}\Rightarrow\mathbb{N}$ should be read in English as something like

  For every pair of natural numbers, there is a natural number.

And that's it! The fact that $\lambda x y. x+y$ and $\lambda x y. x\cdot y$ are two very computationally meaningful proofs of that statement does not factor at all into the statement as it stands.


Which (almost) balanced Boolean function has smallest "total" influence

You have the lower bound of $\mathbf{Inf}[f] \geq \operatorname{Var}[ f ]$ for $f\colon  \{-1,1\}^n\to\mathbb{R}$ (Poincaré Inequality), so that for an (almost) balanced $f\colon  \{-1,1\}^n\to\{-1,1\}$ one must have
$$
\mathbf{Inf}[f] \gtrsim 1 \tag{1}
$$
(say, $1-\epsilon$, depending on the near-unbalanced assumption). Further, for a dictator function, this is tight:
$$
\mathbf{Inf}[\chi_1] = \mathbf{Inf}_1[\chi_1] = 1\,. \tag{2}
$$


Computational Library to compute Quantum Cluster States

As Peter mentions in the comments, it seems impossible to give an authoritive answer without knowing what exactly you are planning on doing with them. That said, there are at least a few places I can point you which may be of some use.

Firstly, Pauli measurements on cluster states can be efficiently simulated on a classical computer. This is a direct result of the Gottesman-Knill theorem (see this paper by Gottesman and this follow-up paper by Gottesman and Aaronson), which Clifford group circuits can be efficiently evaluated via the stabilizer formalism. So it may be that stabilizers are the way you want to go.

However, if you want to be a little less general, and restrict yourself to graph states (a general name for cluster states on general graphs) then there are two papers by Hein, Eisert and Briegel and Schlingemann which describe how Pauli measurements performed on a graph state result in states which are locally equivalent to graph states, and provide rules for these transformations. Thus it is quite possible to work with graphs as your data structure, as long as you do not intend to leave the Clifford group.

Finally, Ross Duncan and Lucas Dixon have taken a category theoretic approach for automated reasoning about graphs and have produced some nice proof of concept software using this approach (see here).

Also, I would point out that Raussendorf, Harrington and Goyal have previously looked at implementing topological computations via measurements on cluster states (they use it to achieve fault-tolerance in cluster states in a very beautiful way), and so you might be interested in their work (see here and here). These papers give an explicit encoding for encoding braids in a cluster state.

UPDATE: I notice you have just added the forth point. The Raussendorf-Harrington-Goyal papers I linked to above do provide a very nice way of doing topological quantum computing via cluster states, which allows classical operations on the knots to be done within the Clifford group, and hence the stabilizer and graph transformation approaches I previously mentioned can be used to efficiently simulate these operations.


Is there a simpler proof of Beigel and Tarui's transformaion of ACC0 circuits

This result is presented in the Web Addendum of Arora-Barak, which can be found here.


Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges

The longest path problem can be reduced to this problem. Let $G = (V,E)$ be an instance of longest $s,t$-path problem. For each vertex $v \in V$ create two vertices, $v_{in}$ and $v_{out}$, and a directed edge with weight $-1$ from $v_{in}$ to $v_{out}$. For each edge $(u, v) \in E$, create an edge from $u_{out}$ to $v_{in}$ with weight $0$. Now each trial in this graph corresponds to a simple path in the graph $G$, and the edges with weight $-1$ count its length.


$n^2$ processors can compare all ${n \choose 2}$ possibilities in constant depth, so yes it's in NC.


What are the limitations on formal proofs of Erlang systems?

Erlang is a concurrent, higher-order programming language. To a decent approximation, this covers everything difficult about program verification.

When a language is higher-order, the control structure of the program is not evident from the source code, since code are values, and so the control structure depends on the data flow in the program. When a language is concurrent, this means you have to reason about interference -- the possibility that multiple processes are trying to act on the same data at once. As a result, you have to think through all the possible interleavings of thread executions.

Erlang is a reasonably clean language design, so it doesn't layer many  accidental difficulties on top of these two. But those two capabilities ensure that the essential difficulty is not easy.

In fact, it's fair to say that the general problem of how to verify concurrent higher-order programs is still open --  proofs still tend to be tour-de-force efforts, rather than a systematic application of a methodology. We're a lot closer than we were five or ten years ago, though.


Unary language examples between L and NP

Classes of unary languages (above DLOGTIME) are just trivial variants of classes of usual, binary languages. Say, let us enumerate $\{0,1\}^*$ by natural numbers using the function $N(w_0\dots w_{n-1})=\sum_{i<n}2^iw_i+2^n-1$, and define the unary encoding of a language $L\in\{0,1\}^*$ to be $U(L)=\{1^{N(w)}:w\in L\}$. Then straightforward padding arguments show:

Unary languages in L are exactly the unary encodings of languages from $\mathrm{LinSPACE=DSPACE}(O(n))$.

Unary languages in NL are exactly the unary encodings of languages from $\mathrm{NLinSPACE=NSPACE}(O(n))=\mathrm{CSL}$.

Unary languages in P are exactly the unary encodings of languages from E.

Unary languages in NP are exactly the unary encodings of languages from NE.

Therefore:

There exist unary languages in $\mathrm{NL\setminus L}$ if and only if $\mathrm{LinSPACE\ne NLinSPACE}$.

There exist unary languages in $\mathrm{P\setminus NL}$ if and only if $\mathrm{NLinSPACE\ne E}$.

There exist unary languages in $\mathrm{NP\setminus P}$ if and only if $\mathrm{E\ne NE}$.

The “hardest” (under DLOGTIME reductions) unary languages in NP are exactly the languages $U(L)$ where $L$ is NE-complete under linear-time reductions (such languages exist).

Etc.


A question to the #P-complete proof of the permanent from Ben-Dor/Halevi

This topic has been extensively investigated in recent years under the name of Holographic Algorithms by researchers such as Valiant, Cai, Lu, Xia, Lipton, and others. Essentially all tractable cases of #CSP (counting constraint satisfaction problems) have been identified in terms of dichotomy theorems (FP vs. #P-complete). In particular, Matchgate computations have been identified as the specific class of counting problems that become tractable on planar graphs. See e.g. this link for further references.


Does an initial algebra for a class have to belong to the class itself?

Yes, the initial algebra is by definition one of the members of the class for which it is initial.

You may however be interested in the category-theoretic concept of a limit. Given a diagram (a collection of objects and morphisms between them), we can ask for an object which "best approximates" the diagram, but needs not be an element of the diagram. There are two such "best approximations", namely limit and colimit. The limit is like an initial algebra.


Are there "small" machines which can efficiently match regular expressions?

It's easy enough to trade off time for space, as follows.

Convert the regular expression to an NFA — for concreteness in comparing algorithms, we'll assume that $r$ is the number of NFA states, so that your $O(rs)$ time bound for directly simulating the NFA is valid and your $O(2^r)$ space bound for running the converted DFA are also valid whenever you're working in a RAM that can address that much memory.

Now, partition the states of the NFA (arbitrarily) into $k$ subsets $S_i$ of at most $\lceil r/k\rceil$ states each. Within each subset $S_i$, we can index subsets $A_i$ of $S_i$ by numbers from $0$ to $2^{\lceil r/k\rceil}-1$.

Build a table $T[i,j,c,A_i]$ where $i$ and $j$ are in the range from 0 to $k-1$, $c$ is an input symbol, and $A_i$ is (the numerical index of) a subset of $S_i$. The value stored in the table is (the numerical index of) a subset of $S_j$: a state $y$ is in $T[i,j,c,A_i]$ if and only if $y$ belongs to $S_j$ and there is a state in $A_i$ that transitions to $y$ on input symbol $c$.

To simulate the NFA, maintain $k$ indices, one for each $S_i$, specifying the subset $A_i$ of the states in $S_i$ that can be reached by some prefix of the input. For each input symbol $c$, use the tables to look up, for each pair $i,j$, the set of states in $S_j$ that can be reached from a state in $A_i$ by a transition on $c$, and then use a bitwise binary or operation on the numerical indices of these sets of states to combine them into a single subset of states of $S_j$. So, each step of the simulation takes time $O(k^2)$, and the total time for the simulation is $O(sk^2)$.

The space required is the space for all the tables, which is $O(k^2 2^{r/k})$. The time and space analysis is valid on any RAM that can address that much memory and that can do binary operations on words that are large enough to address that much memory.

The time-space tradeoff you get from this doesn't perfectly match the NFA simulation, because of the quadratic dependence on $k$. But then, I'm skeptical that $O(rs)$ is the right time bound for the NFA simulation: how do you simulate a single step of the NFA faster than looking at all of the (possibly quadratically many) transitions allowed from a currently active state to another state? Shouldn't it be $O(r^2 s)$?

In any case by letting $k$ vary you can get time bounds on a continuum between the DFA and NFA bounds, with less space than the DFA.


Example of logarithmic length witness being easier to verify than find

Consider the decision problem which decides whether a given binary input $x$ of length $n$ is a non-palindrome.
There is a pretty standard communication complexity proof that a single tape TM requires at least $\Omega(n^2)$ time to solve this problem.
On the other hand, we can also solve this problem using a nondeterministic algorithm with a $\log(n)$ length witness $i$: the algorithm accepts whenever the $i$th bit from the start of $x$ differs from the $i$th bit from the end of $x$. Identifying the $i$th bit from the start or end of a length $n$ bitstring can be accomplished in $O(n \log n)$ time on a single tape TM.


Graph that maximizes minimum hitting time?

It is well known that a barbell graph (two cliques of size $n/3$ connected by a path of length $n/3$) has average hitting time $\Omega(n^3)$, but I believe the same applies to minimum hitting time (for uniform or stationary distribution). Whatever vertex you choose as the one that you think is easiest to hit, you have constant probability of starting in the far clique from that vertex, after which it will take $\Omega(n^3)$ time in expectation before you traverse the connecting path to your chosen vertex.


Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory

I recommend looking at Stasys Jukna's books Extremal Combinatorics and Boolean Function Complexity. For discrepancy and the like, you can look at Bernard Chazelle's book The Discrepancy Method (available online at his homepage).


BSP, but with curved surfaces (NURBS? kernelized support vectors?)

You can absolutely do it with kernelized support vectors.  I don't have a publication handy but I've implemented it myself before.  You'll probably want to use quadrics for the split planes, and unfortunately I only found a suboptimal way to do csg (Naylor's original bsp/csg algorithm from 1990); there may be a better way.  But it's very possible, and allows for a couple really interesting things:

ray segment/quadric bsp intersection tests can be done extremely effectively with the following procedure: first, early exit if the two points are not in the same node, then ray-march using the signed distance from the nearest quadric hyperplane, which is easy to compute by traversing the tree.  This becomes very efficient, especially for certain smoother shapes, because the trees tend to be very shallow.
you can fit the hyperplanes to a sampling of a signed distance function by using linear least squares.  Recursively split until all sample points are in the same node of the tree and the mean square error of the signed distance to the shape is below a certain tolerable level, at each stage using least squares to optimize the coefficients of the quadric split.

as implied in (1), determining whether one point is accessible from another reduces to determining whether they are in the same node of a very shallow tree, useful for 3d blob detection and such.

As far as the implementation, it really is simple, as you have hinted.  Just use a few more coefficients in the hyperplanar equation for each node, and the rest will flow.   But if you want to look at my implementation, it's somewhere buried in my github (vpostman).


Is finding Logspace reductions harder than P reductions?

Kaveh is correct in saying that all of the "natural" NP-complete problems are easily seen to be complete under (uniform) $\mathrm{AC}^0$ reductions.  However, one can construct sets that are complete for NP under logspace reductions that are not complete under $\mathrm{AC}^0$ reductions.  For instance, in [Agrawal et al, Computational Complexity 10(2): 117-138 (2001)) an error-correcting encoding of SAT was shown to have this property.

As regards a "likely" candidate for a problem that is complete under poly-time reductions but not under logspace reductions, one can try to cook up an example of the form
{$(\phi,b)$ : $\phi$ is in SAT and $z$ is in CVP [or some other P-complete set] iff $b=1$, where $z$ is the string that results by taking every 2nd bit of $\phi$}.  Certainly the naive way to show that this set is complete will involve computing the usual reduction to SAT, and then constructing $z$ and computing the bit $b$, which is inherently poly-time.  However, with a bit of work, schemes such as this can usually be shown to be complete under logspace reductions via some non-naive reduction.  (I haven't worked out this particular example...)


A search for "Quantum GCD" yields a 2013 paper by Saeedi and Markov titled "Quantum Circuits for GCD Computation with O(n \log n) Depth and O(n) Ancillae". It's not mentioned in the title, but the size of the circuit used in their algorithm $O(n^2)$.


Dividing users with certain files into 2 equal groups

The problem is NP-complete. The reduction is from the Set cover problem. Let one user has all the files $F$. Then our only hope is to achieve $\mathcal{F}(G_2)= \mathcal{F}(G_1)$. So the question is, from given $2k-1$ sets, are there $k$ that cover the ground set? This easily reduces to the decision version of the Set cover problem after adding a few dummy users/files.

My old answer, which gives a polytime algorithm if we do not allow $\mathcal{F}(G_2)= \mathcal{F}(G_1)$:
Yes, you can check this in P. Your condition is equivalent to that there is an $f_i$ and $f_j$ such that $f_i\in \mathcal{F}(G_1)\setminus \mathcal{F}(G_2)$ and $f_j\in \mathcal{F}(G_2)\setminus \mathcal{F}(G_1)$. So all you have to do is for each pair, $f_i, f_j$, you check whether you can divide the users appropriately. This can be done if no user has both files and at most $k$ users have any of the files. The total running time is $O(n^2k)$ (if the info is stored appropriately) which can be easily improved.


What are the limits of computation in this universe?

Seth Lloyd has a paper on the subject. You need energy to compute, but if you put too much energy into a small region, it forms a black hole. This slows down time (making the time it takes for the computation to complete relatively longer), and any computation done in the interior of a black hole is wasted, as the results cannot be extracted from the black hole and used. Seth calculates the limits on the amount of computation possible, and shows that for some measures of computation, the most computationally intensive environment possible in the universe would be that surrounding a black hole.


Definition of Projection Measure in the characterization of strong approximation Resistance in a paper by Khot et al

Section 1 of the paper, in which the first definition appears, is introductory. The formal development starts at Section 2. The part of the paper starting at Section 2 is completely self-contained. Therefore, if there is any mismatch between a definition in Section 1 and a definition elsewhere, the latter is the correct one.

In theoretical computer science, papers are published in conferences. Conference reviewers cannot be expected to read 50-page strong manuscripts, and so the argument has to be described in an elaborate introduction. This is why there is so much technical content in Section 1. The development there is simplified and more leisurely to facilitate reading. The authoritative part of the paper is Section 2 and forward.


Log space algorithms for modular decomposition tree

There is a logarithmic-space algorithm for the modular decomposition of any graph.

The result is part of the paper "Capturing Polynomial Time using Modular Decomposition", which will appear at LICS 2017 (http://lics.rwth-aachen.de/lics17/).
It is also part of the PhD thesis of the author. A preliminary version can be found here:
https://www2.informatik.hu-berlin.de/~grussien/grussien-pre-phd-thesis.pdf.

The algorithm uses the connection between modules and transitive orientation that was first shown by Gallai in 1967 and combines this with Reingold's logspace algorithm for undirected reachability. Given two vertices u and v, it can compute the minimal module containing both vertices. (A naive implementation of this closure would need some form of directed reachability.)
Every module of the modular decomposition tree is equal to the union of certain modules that are minimal containing two vertices.


Why is Proof Checker required in Proof Carrying Code

The purpose of the proof checker is to minimise the trusted computing base.

By having a proof checker, neither the compiler nor the theorem prover need to be correct. The paper makes this point on Page 3:

Neither the compiler nor the prover need to be correct in order to be guaranteed to
detect incorrect compiler output. This is a significant advantage since the VCGen and
the  proof checker are significantly simpler than the compiler and the prover.

A proof checker is just a couple of lines of code, and can be hand-inspected for correctness. In contrast, an automated prover that performs well is extremely complex and unlikely to be correct, although with well-tested and widely used provers, the mistakes will be in edge cases that might not be easy to trigger.
Have a look at the 30k LOC C code that make up Lingeling, a state-of-the-art SAT solver to see just how complicated automated theorem provers can be. Without a proof checker, you'd have to prove correct that theorem prover. This is beyond whaty we can economically do in 2015.


Comparing $\mathbf{NP}$ and $\mathbf{E}$

This was a comment, but it became too long. I want to give an explicit example where the input size increases. Take the classic reduction from CircuitSAT to 3SAT. The usual idea is to assign a variable to every gate in the circuit. The variable's value is the output of the gate. The you add the constraints that make a gate's output reflect the gate's input and gate type. So if a gate (whose variable is g_1) is an AND gate and has input wires coming from gates g_2 and g_3, you'll get a constraint like g_1 = g_2 AND g_3. We also have variables for the inputs, of course.

With this reduction, even though there are n inputs, if the size of the circuit is, say, $O(n^5)$, then the resulting SAT instance will have $O(n^5)$ variables, which will require $O(2^{n^5})$ time to solve by brute forcing on a deterministic TM.

You also asked why E is not closed under Karp reductions. That's easy. Take a problem that only be solved in $O(2^{n^2})$ time, and therefore it is not in E.  Now we can Karp-reduce this to a language in E by padding the input with $O(n^2)$ zeros. The language in E to which we're reducing is the original language with each input of size n padded with $O(n^2)$ zeros. Now since the input size is $O(n^2)$ and we know an algorithm that solves this in $O(2^{n^2})$ time, this problem is in E.  So we reduced a problem not in E to a problem in E, showing that E is not closed under Karp reductions.


This problem has indeed been studied.  Goldreich, Goldwasser and Ron studied it in their seminal paper which kicked off graph property testing, and then, Feige, Langberg, and Schechtman also have results on it in their FOCS '02 paper "Graphs with tiny vector chromatic numbers and huge chromatic numbers".

Specifically, [FLS '02] show that one can distinguish between graphs with an independent set of size $\rho n$ from graphs $\epsilon$-far from being so (meaning, at least $\epsilon n^2$ edges need to be removed to create such an independent set) by choosing a random subgraph induced by $s = \tilde{O}(\rho^4/\epsilon^3)$ random vertices in the graph and checking whether the random subgraph has an independent set of size $\rho s$ or not.   ([GGR '98] showed a weaker bound on $s$ of $\tilde{O}(\rho/\epsilon^4)$.)  [FLS '02] also show a lower bound on $s$ of $\Omega(\rho^3/\epsilon^2)$.


Is optimal equal-point graph splitting NP-Complete?

Editing my answer to give a stronger result:

The problem is NP-hard for k=2 and called the Minimum Bisection Problem.


Simulating quantum measurements by unitaries

The basic idea here is that any operation that uses measurement can be replaced by an operation that instead CNOTs qubits onto ancillae.

Any circuit with an intermediate measurement can be converted to a circuit that only has measurement as the last step. Doing so involves performing three simple transformations again and again:

Moving measurements onto a fresh ancilla qubit.

Using fresh qubits instead of resets

Deferring measurements until later.

Once you have a circuit where all the measurements happen at the end, replace the measurements with CNOTs onto fresh ancillae and throw away the ancillae without doing anything to them (or do stuff to them, it doesn't matter).

(Note that, if you do any classical post-processing of the measurement results, that post-processing should be moved into the quantum circuit. We're taking away the mechanism by which information was reaching the classical computer.)

The resulting circuit is unitary, and a black-box drop-in for the original circuit (except for all the extra clean ancillae that must be fed in).


This source states that it comes from the concept of a combination set, which is backed up by Hennesy & Patterson's explanation in "Computer Organization and Design", p.340.

The reasoning behind it seems to be as follows. In a combination the order of elements is irrelevant: in (n choose k) it doesn't matter in which order you pick the k elements. Similarly, a combinational logic circuit is a logic circuit where the order of inputs doesn't matter for the outputs. Note here that "an input" refers to the entire input to the circuit, not the individual lines. So, the intuition is that you give a combinational circuit some sequence of inputs, and "order doesn't matter" is true in the sense that the output for each input is the same, even if you permute the sequence.

This is to be understood in opposition to sequential logic, where the order of inputs does matter, because sequential circuit can have internal state (e.g. flip-flops) that can and usually influence individual outputs.


Example of context-free tree language which can not be generated by monadic CFTG

Based on the comment of Michael Wehar, I've found this grammar to be that one which doesn't have an equivalent MCFTG:

$S\rightarrow T(a,a)$

$T(x_1,x_2)\rightarrow T(b(x_1,x_2),c(x_1,x_2))$

$T(x_1,x_2)\rightarrow a(x_1,x_2)$

This grammar produces perfect binary trees where in each branch the left child has a label a if it is a leaf, and has a label b otherwise; the right child has a label a if it is a leaf, and has a label c otherwise.

I don't have a very rigorous proof of this fact, however here below there are some observations.

It makes it impossible to build such a monodic context free tree grammar which will produce the same language of trees. This is because any single-ranked non-terminal can not properly set a parent node label (b or c). This label depends on "context": a knowledge about wether this node is left or wether it is right.

Also, because the depth of each path in the given tree is the same, it can not be produced by a grammar where each next branch is generated by an independent non-terminal.


Sorting array of distances by proximity to each other

Although it's hard to discern a precise question here, evidently it concerns spatial data structures for efficient local searches of objects.  Hanan Samet's books on the subject are classics and almost encyclopedic.  He wrote a brief overview of the subject available here.  I suspect a simple quadtree would be an attractive solution.  In many cases, exploiting a pre-sorting by one of the coordinates provides fine performance and is simple to code.


Hitting set of very restricted linear forms

There is a tight lower bound of size $\Omega(n/ \log n)$ by simple counting argument.

Suppose there is a hitting set $H=\{\alpha_{1},\dots,\alpha_{k}\}$
of size $k$. We will show that there is always {-1,0,1}-linear
form $f$ such that $f(\alpha_{i})=0$ for all $i$ when $k\le c_{0}n/\log n$
and $c_{0}$ is small enough.

For each $S\subseteq[n]$, let $f_{S}=\sum_{i\in S}x_{i}$ and $f_{S}(H)=(f_{S}(\alpha_{1}),\dots,f_{S}(\alpha_{k}))$.

Since $|f_{S}(\alpha_{i})|\le n^{c+1}$, there are at most $(2n^{(c+1)})^{k}$
possible distinct values of $f_{S}(H)$. But there are $2^{n}$ distinct
linear forms $f_{S}$.

Because $(2n^{(c+1)})^{k}<2^{n}$ when $k\le c_{0}n/\log n$, we have
that there are $S$ and $S'$ where $f_{S}(\alpha_{i})=f_{S'}(\alpha_{i})$
for all $i$.

So $(f_{S}-f_{S'})(\alpha_i)=0$ for all $i$, $f_{S}-f_{S'}$ is a {-1,0,1}-linear form.


If there is an Arthur-Merlin protocol for knottedness similar to the [GMW85] and [GS86] Arthur-Merlin protocols for Graph Non Isomorphism, then I believe such a cryptocurrency proof-of-work could be designed, wherein each proof-of-work shows that two knots are not likely to be equivalent/isotopic.

In more detail, as is well known in the Graph Non Isomorphism protocol of [GMW85], Peggy the prover wishes to prove to Vicky the verifier that two (rigid) graphs $G_0$ and $G_1$ on $V$ vertices are not isomorphic.  Vicky may secretly toss a random coin $i\in\{0,1\}$, along with other coins to generate a permutation $\pi\in\ S_V$, and may present to Peggy a new graph $\pi(G_i)$.  Peggy must deduce $i$.  Clearly Peggy is only able to do this if the two graphs are not isomorphic.

Similarly, and more relevant for the purposes of a proof-of-work, as taught by [GS86] an Arthur-Merlin version of the same protocol includes Arthur agreeing with Merlin on $G_0$, $G_1$, given as for example adjacency matrices. Arthur randomly picks a hash function $H:\{0,1\}^*\rightarrow\{0,1\}^k$, along with an image $y$.  Arthur provides $H$ and $y$ to Merlin.  Merlin must find a $(i,\pi)$ such that $H(\pi(G_i))=y$.

That is, Merlin looks for a preimage of the hash $H$, the preimage being a permutation of one of the two given adjacency matrices.  As long as $k$ is chosen correctly, if the two graphs $G_0$ and $G_1$ are not isomorphic then there will be a higher chance that a preimage will be found, because the number of adjacency matrices in $G_0 \cup G_1$ may be twice as large than if $G_0\cong G_1$.

In order to convert the above [GS86] protocol to a proof-of-work, identify miners as Merlin, and identify other nodes as Arthur.  Agree on a hash $H$, which, for all purposes, may be the $\mathsf{SHA256}$ hash used in Bitcoin.  Similarly, agree that $y$ will always be $0$, similar to the Bitcoin requirement that the hash begins with a certain number of leading $0$’s.

The network agrees to prove that two rigid graphs $G_0$ and $G_1$ are not isomorphic.  The graphs may be given by their adjacency matrices
A miner uses the link back to the previous block, along with her own Merkle root of financial transactions, call it $B$, along with her own nonce $c$, to generate a random number $Z=H(c\Vert B)$
The miner calculates $W= Z\:mod\: 2V!$ to pick $(i,\pi)$
The miner confirms that  $\pi(G_i)\neq G_{1-i}$ - that is, to confirm that the randomly chosen $\pi$ is not a proof that the graphs are isomorphic
If not, the miner calculates a hash $W=H(\pi(G_i))$
If $W$ begins with the appropriate number of $0$’s, then the miner “wins” by publishing $(c,B)$
Other nodes can verify that $Z=H(c\Vert B)$ to deduce $(i,\pi)$, and can verify that $W=H(\pi(G_i))$ begins with the appropriate difficulty of $0$’s

The above protocol is not perfect, some kinks I think would need to be worked out.  For example, it's not clear how to generate two random graphs $G_0$ and $G_1$ that satisfy good properties of rigidity, for example, nor is it clear how to adjust the difficulty other than by testing for graphs with more or less vertices.  However, I think these are probably surmountable.

But for a similar protocol on knottedness, replace random permutations on the adjacency matrix of one of the two graphs $G_1$ and $G_2$ with some other random operations on knot diagrams or grid diagrams... or something.  I don’t think random Reidemeister moves work, because the space becomes too unwieldy too quickly.

[HTY05] proposed an Arthur-Merlin protocol for knottedness, but unfortunately there was an error and they withdrew their claim.

[Kup11] showed that, assuming the Generalized Riemann Hypothesis, knottedness is in $\mathsf{NP}$, and mentions that this also puts knottedness in $\mathsf{AM}$, but I’ll be honest I don’t know how to translate this into the above framework; the $\mathsf{AM}$ protocol of [Kup11] I think involves finding a rare prime $p$ modulo which a system of polynomial equations is $0$.  The prime $p$ is rare in that $H(p)=0$, and the system of polynomial equations corresponds to a representation of the knot complement group.

Of note, see this answer to a similar question on a sister site, which also addresses the utility of such "useful" proofs-of-work.

References:

[GMW85] Oded Goldreich, Silvio Micali, and Avi Wigderson.  Proofs that Yield Nothing but their Validity, 1985.

[GS86] Shafi Goldwasser, Michael Sipser.  Private Coins versus Public Coins in Interactive Proof Systems, 1986.

[HTY05]  Masao Hara, Seiichi Tani, and Makoto Yamamoto.  UNKNOTTING is in $\mathsf{AM} \cap \mathsf{coAM}$, 2005.

[Kup11] Greg Kuperberg.  Knottedness is in $\mathsf{NP}$, modulo GRH,  2011.


The answer is yes without any requirement on the size of the automaton. It can be computed in $O(\log^2 n)$ space even for $k$ DFAs where $k$ is a constant.

Let $A_i = (Q_i, \Sigma_i, \delta_i, z_i, F_i)$  ($i \in [k])$ be $k$ DFAs. We show that, given $\langle A_1, \ldots, A_k \rangle$, computing the minimal DFA recognizing $\text{L}(A_1) \cap \cdots \cap\text{L}(A_k)$ can be done in $O(\log^2 n)$ space. We first prove some technical results.

Definition 1: Let $q, r$ be two states then $q \equiv r$ iff $\forall w \in \Sigma^*$, $q . w \in F \Leftrightarrow r . w \in F$

We now consider the automaton $A$ given by the classical cartesian product construction. Let $q = (q_1, \ldots, q_k)$ and $r = (r_1, \ldots, r_k)$ be states of $A$.

Lemma 1: Deciding whether $q \equiv r$ is in NL.

Proof (sketch): We show that testing inequivalence is in NL and use NL = coNL. Guess a word $w \in \Sigma^*$ (one letter at the time) such that $q . w$ is a final state and $r . w$ isn't. This can be achieved by computing $q_i . w, r_i . w$ in log-space for $i \in [k]$ and using the fact that $q$ is final iff $q_i \in F_i \, \forall i \in [k]$. It can be shown that $q \not\equiv r$ implies the existence of a $w$ of poly-size.

Lemma 2: Deciding whether $q$ is (in)accessible is in NL.

Proof (sketch): Guess (poly-size) paths from $z_i$ to $q_i$ ($i \in [k]$).

Definition 2: Consider the states of $A$ in lexicographical order. Define $s(1)$ as being the first accessible state and $s(i)$ the first accessible state following $s(i-1)$ which isn't equivalent to any previous state. We define $c(q)$ as the unique $i$ such that $q \equiv s(i)$.

Lemma 3: $s(i)$ can be computed in $O(\log^2 n)$ space.

Proof (sketch): Definition 2 yields an algorithm. We use $k$ counters to iterate over the states. Let $j \leftarrow 0$ and $q$ be the current state. At each state, we use lemma 2 to verify if $q$ is accessible. If it is, we loop on every previous states and we verify if any of them is equivalent to $q$. If there isn't any, we increment $j$ and output $q$ if $j = i$. Otherwise, we store $q$ as being $s(j)$ and we continue. Since we only store a constant number of counters and our tests can be carried out in $\text{NL} \subseteq \text{DSPACE}(\log^2 n)$, this completes the proof.

Corollary 1: $c(q)$ can be computed in $O(\log^2 n)$ space.

Theorem: Minimizing $A$ can be done in $O(\log^2 n)$ space.

Proof (sketch): Let $1 \leq m \leq |Q_0| \cdots |Q_1|$ be the largest $i$ such that $s(i)$ is defined (ie. the number of classes of $\equiv$). We give an algorithm outputting an automaton $A' = (Q', \Sigma, \delta', z', F')$ where

$Q' = \lbrace s(i) : i \in [m] \rbrace$;
$F' = \lbrace q \in Q' : q_i \in F_i \, \forall i \in [k] \rbrace$;
$z' = s(c(q))$ where $q = (z_0, \ldots, z_k)$.

We now show how to compute $\delta'$. For every $i \in [m], a \in \Sigma$, compute $q \leftarrow s(i) . a$ and output the transition $\left(s(i), a, s(c(q))\right)$. By lemma 3 and corollary 1, this algorithm runs in $O(\log^2 n)$ space. It can be checked that $A'$ is minimal and $\text{L}(A') = \text{L}(A)$.


Your problem is equivalent to End-of-Metered-Line.

This can be shown by reducing your problem to End-of-Potential-Line (see https://arxiv.org/abs/1702.06017). This is a version of End-of-the-Line where the line is equipped with a potential function, and a solution is either the end of a line, or a vertex on the line at which the potential function decreases. This differs from EOML, since the potential is not required to increase by exactly one at each vertex.

We can reduce your problem to EOPL by taking the successor of each vertex to be the neighbor with the larger index, and the predecessor of each vertex to be the neighbor with the smaller index. Any vertex that has two neighbors with smaller indices is the end of a line, and any vertex that has two larger neighbors is also the end of a line. The potential function of a vertex is just its index, which is monotonically increasing along each line.

It was shown in https://arxiv.org/abs/1702.06017 that EOPL is equivalent to EOML, under polynomial-time reductions, and thus is in CLS.

For the other direction, EOML can be reduced to your problem by embedding the potential space into the vertex space using the higher-order bits. In other words, each vertex $v$ in the EOML instance is mapped to the integer $K \cdot p(v) + v$, where $p(v)$ is the potential of $v$, and $K$ is some constant that is larger than the total number of vertices in the EOML instance.

So to answer your question, the problem is unlikely to be PPAD-complete since that would imply PPAD $\subseteq$ CLS.


The origin of the terms "efficient" and "feasible" computation/algorithm

I don't know about the terms "efficient" and "feasible."  Since these terms even today have no precise technical meaning, I suspect that the history of their usage will turn out to be murky, just as the history of most words in most languages is murky.

"Computational complexity" is a more interesting term.  With the help of MathSciNet, I find that Juris Hartmanis seems to have been the first to popularize it.  The famous 1965 paper by Hartmanis and Stearns uses the term in the title, but even before that, Hartmanis's Mathematical Review of Michael Rabin's paper "Real time computation" (Israel J. Math. 1 (1963), 203–211) says:

  This result is very instructive and contributes new techniques to the emerging theory of computational complexity of recursive sequences and functions. This theory is mainly concerned with the classification of computable problems by their degree of computational difficulty, the study of the properties of these complexity classes, their relation to each other and their dependence on the (abstract) computing devices.

Note that Rabin himself does not use the term "computational complexity" in this paper.

MathSciNet also turns up a couple of earlier reviews that use the term "computational complexity," but these seem to be spontaneous and sporadic occurrences.


Is there any triangle-free, star-cutset-free, circle graph, with more than n edges?

Suppose $G$ is a triangle-free star-cutset-free circle graph.
I will show that $G$ contains no vertex with degree more than 2. Therefore, $G$ has at most $n$ edges.

Consider a circle representation $C$ of $G$. A set of chords is parallel if no two of them cross but there is a line crossing all the chords.

Property 1: $C$ has no 3 parallel chords.

Proof. Suppose $C$ has 3 parallel chords. Condider the vertex $v$ corresponding to the middle chord. Then, $N[v]$ is a cutset. This proves the property.

For the sake of contradiction, assume $G$ has a vertex $v$ of degree at least 3. Then, the chord corresponding to $v$ intersects 3 other chords. Since these 3 chords intersect one line, they are either parallel or two of them intersect. Due to Property 1, two of them intersect, which means their vertices form a triangle with $v$, which contradicts $G$ being triangle-free.


Enumeration of discrete objects for which recognition problem is coNP-complete

This is not a complete answer, but let me try to explain the case for the Hamiltonian graphs and the non-Hamiltonian graphs with $n$ vertices.

There are $2^{\binom{n}{2}}$ graphs on $n$ vertices, and each of them is either Hamiltonian or non-Hamiltonian.  So one of the following is true.

There are at least $2^{\binom{n}{2}}/2$ Hamiltonian graphs.
There are at least $2^{\binom{n}{2}}/2$ non-Hamiltonian graphs.

I don't know which is true, but suppose 1 is true.  Let $H(n)$ be the number of Hamiltonian graphs with $n$ vertices.  Then $H(n)\geq 2^{\binom{n}{2}}/2$.  In this case, listing all the Hamiltonian graphs with $n$ vertices can be easily done in output polynomial time: Look through all the $2^{\binom{n}{2}}$ graphs, check the Hamiltonicity for each of them (in $2^{O(n)}$ time), and output if it is Hamiltonian.  The running time is $O(2^{\binom{n}{2}}\times 2^{O(n)}) = O(H(n)^2)$, since $2^{O(n)} = O(H(n))$.  If 2 is true, then by the same argument we can list all the non-Hamiltonian graphs with $n$ vertices in output polynomial time.

Namely, if the output size is polynomial in $2^{\binom{n}{2}}$, then such a trivial algorithm runs in output polynomial time (assuming that the verification can be done in $\text{poly}(2^{\binom{n}{2}})$ time).  So the only interesting cases are when the output sizes are subpolynomial in $2^{\binom{n}{2}}$.


Is an infinite incomputable sequence random wrt a computable measure?

Mucknik, Semenov and Uspensky showed that there are sequences which are not Martin-Löf random for any computable measure.  They call all other sequences (which are Martin-Löf random for some computable measure) "natural sequences".

  Andrei A. Muchnik, Alexei Semenov, and Vladimir Uspensky. Mathematical metaphysics of randomness. Theoretical Computer Science, 207(2):263–317, 1998.

This topic is also discussed in

  Laurent Bienvenu and Christopher Porter. Effective randomness, strong reductions and Demuth’s theorem.

  Jan Reimann and Theodore A. Slaman. Probability measures and effective randomness.

  Jan Reimann and Theodore A. Slaman. Measures and their random reals.

Here is a quick proof (which may be different from the above references):

Let $\{U_i\}$ be a (non-effective) enumeration of all $\Sigma^0_1$ sets making up some level of the universal Martin-Löf test for some computable measure $\mu$.  Each $U_i$ is dense and open, so by the Baire category theorem (countable intersection of dense open sets is dense), the intersection $\bigcap_i U_i$ is nonempty.  Any sequence in this intersection cannot be Martin-Löf random for any computable measure $\mu$.

The same can be done for Schnorr randomness (which is weaker than Martin-Löf randomness). Let $\{U_i\}$ be the collection of all dense $\Sigma^0_1$ sets of computable $\mu$-measure for some computable measure $\mu$.

UPDATE Oct 23, 2013:

I realize there are three things to add (which I am sure are all well-known and they are probably in the above mentioned papers).

My above proof actually shows that 1-generics cannot be Martin-Löf random for a computable measure, since 1-generics are in all dense $\Sigma^0_1$ sets.
The K-trivials are not Martin-Löf random on any computable measure.  A sequence $X \in \{0,1\}^\mathbb{N}$ is low-for-random (a.k.a. $K$-trivial) if $\text{MLR}^X = \text{MLR}$. It can be shown that this property also extends to all computable $\mu$.  That is, if $X$ is K-trivial, then $\text{MLR}_{\mu}^X = \text{MLR}_{\mu}$ for all computable $\mu$. Hence, the non-computable $K$-trivials cannot be random for any computable measure.  For if a $K$-trivial $X$ is random on a computable measure $\mu$ then $X$ is random relative to $X$.  This means $X$ is an atom.  However, only computable points can be atoms of computable measures.
The set of all "natural sequences" is precisely the set of sequences truth-table reducible to a Martin-Löf random (on the fair-coin measure).  (The main idea is that every computable measure is the push-forward on an a.e. computable map, and the Martin-Löf randoms on the measure $\mu$ are exactly the sequences pushed over to the new measure.  The reason this computation is "truth-table" involves using "layerwise computability".)


The problem turned out to be NP-complete. You can read more in detail here and here. Short summary:

The reduction is from a problem was shown to be NP-complete by Dasgupta, Jiang, Kannan, Li, and Sweedyk: given a bipartite graph G and an integer k, decide if G has an induced subgraph on 2k nodes that can be extended to be uniquely matchable. It was observed by Stéphane Vialette that this reduces to the bipartite unique matching version of this problem if we add n-k isolated nodes to both classes.


I doubt your features simplify the problem at all, but it's very easy to 6-color a planar graph: find and remove a vertex of minimum degree, color the remaining graph recursively, put back the removed vertex, and give it a color that's different from all of its neighbors.

If you maintain an array indexed by vertex degree, with a list of the vertices with that degree in each array cell, and move the vertices to different lists when a removal causes their degrees to change, then you can find the minimum degree vertex by scanning the array from low to high degrees, and the overall algorithm will be linear time.

This also has the advantage that it automatically and quickly takes care of the completely surrounded regions: they have degree one, so they're dealt with first.

I think the best known time bound for 4-coloring planar graphs is still larger — more specifically, $O(n^2)$ from the work of Robertson, Sanders, and Thomas in the mid-1990s. But there are more complicated methods for 5-coloring planar graphs in linear time; one relevant reference is the paper by Hagerup, Chrobak, and Diks in ICALP 1987, and another is by Frederickson in IPL 1984.


What do stronger circuit lower bounds give in terms of derandomization?

It is known that if $E = DTIME(2^{O(n)})$ is not contained in $SIZE(2^{\varepsilon \cdot n})$ for some $\varepsilon>0$  then $BPP = P$ (https://dl.acm.org/citation.cfm?id=258590).

(Actually, a slightly stronger assumption is needed, namely, the separation between $E$ and $SIZE(2^{\varepsilon \cdot n})$ should hold for almost all input lengths - thanks to Ryan O'Donnel for pointing it out.)

More generally, this paper gives a direct optimal translation of any circuit lower bound into a corresponding derandomization result:
http://users.cms.caltech.edu/~umans/papers/SU01-final.pdf


What is the difference between LTL and CTL?

To really understand the difference between LTL and CTL you have to study the semantics of both languages. LTL formulae denote properties that will be interpreted on each execution of a program. For each possible execution (a run), which can be see as a sequence of events or states on a line — and this is why it is named "linear time" — satisfiability is checked on the run with no possibility of switching to another run during the checking. On the other hand, CTL semantics checks a formula on all possible runs and will try either all possible runs (A operator) or only one run (E operator) when facing a branch.

In practice this means that some formulae of each language cannot be stated in the other language. For example, the reset property (an important reachability property for circuit design) states that there is always a possibility that a state can be reached during a run, even if it is never actually reached (AG EF reset). LTL can only state that the reset state is actually reached and not that it can be reached.

On the other hand, the LTL formula $\Diamond\Box s$ cannot be translated into CTL. This formula denotes the property of stability : in each execution of the program, s will finally be true until the end of the program (or forever if the program never stops). CTL can only provide a formula that is too strict (AF AG s) or too permissive (AF EG s). The second one is clearly wrong. It is not so straightforward for the first. But AF AG s is erroneous. Consider a system that loops on A1, can go from A1 to B and then will go to A2 on the next move. Then the system will stay in A2 state forever. Then "the system will finally stay in a A state" is a property of the type $\Diamond\Box s$. It is obvious that this property holds on the system. However, AF AG s cannot capture this property since the opposite is true : there is a run in which the system will always be in the state from which a run finally goes in a non A state.

I don't know if this answers to your question, but I would like to add some comments.

There is a lot of discussion of the best logic to express properties for software verification... but the real debate is somewhere else. LTL can express important properties for software system modelling (fairness) when the CTL must have a new semantics (a new satisfiability relation) to express them. But CTL algorithms are usually more efficient and can use BDD-based algorithms. So... there is no best solution. Only two different approaches, so far.

One of the commenters suggests Vardi's paper "Branching versus Linear Time: Final Showdown".


What is the VC dimension of Turing machines with specified maximum size?

The exact VC bounds will depend on the alphabet size and the exact specification of the transition function (must it always move left or right, or can it stay put, etc). For fixed alphabet size, say 2, I think you can apply the DFA-VCdim analysis of

  Ishigami and Tani, VC-dimensions of finite automata and commutative finite automata with $k$ letters and $n$ states, Discrete Applied Mathematics 74 (1997), no. 3, 229-240

to show that the VC-dim of $n$-state TM's will be $\Theta(n\log n)$.

Those other VC bounds you mentioned in terms of the NN connection weights are more in the spirit of SVM bounds in terms of the norm of the separating hyperplane.

Update: Here's a proof sketch. For a fixed alphabet size (say, 2) and $n$ states, there are $n^{cn}$ transition functions from (state,letter) to (state,letter,head move), where $c$ is a universal constant. Taking logs gives you a VC upper estimate of $O(n\log n)$. The lower bound comes from the Ishigami-Tani analysis, since an $n$-state DFA can be realized as an $n$-state TM (plus $n$ additional bits to indicate which states are accepting, but this is negligible compared to the $n^{cn}$ factor).


Improved lower bounds or upper bounds on union-find structures since Tarjan?

There's a matching lower bound in the cell probe model (with a logarithmic number of bits per memory cell); see Fredman and Saks, "The cell probe complexity of dynamic data structures", STOC 1989.