Is there a non-deterministic version of the complexity class PP?

PP is defined as a probabilistic class and we don't normally think of nondeterministic versions of any of these classes (as far as I'm aware). In a sense probabilistic classes and nondeterministic ones are already on the same spectrum -- let me illustrate. We can define a language to be in PP if there's a randomized poly-time TM ("RPTM") that on a yes instance accepts with $> 0.5$ probability and on a no instance accepts with $\leq 0.5$ probability. Similarly we can define a language to be in NP if there's a RPTM accepting yes-instances w.prob $> 0$ and accepting no-instances w.prob $0$. (Convince yourself of this if you haven't before.) BPP corresponds to probability thresholds $\geq 2/3$ and $\leq 1/3$ while RP corresponds to $\geq 1/2$ and $0$.

So you see, PP can already be viewed as a "nondeterministic" version of P, but with different requirements as compared to NP.


Decidability of first-order theory of real closed fields with functions

It's undecidable because we can interpret natural numbers (with addition and multiplication).

For example, let $Ind(f)$ be the formula:
$$f(0)=1 \land \forall x \ \big(f(x)=1 \to f(x+1)=1\big)$$

Now we can define the characteristic function of the set of natural numbers using its universality property as a minimal inductive function:
$$Ind(h) \land \forall f \ \big(Ind(f) \to \forall x \ (f(x)=0 \to h(x)=0)\big)$$

(As Emil wrote in his comment we don't even need the language of RCF, we can pick an arbitrary member of the structure as $0$, define a successor function as an injective function whose range lacks our $0$, and then define natural numbers using them. So the undeciability result applies to the second-order language of any infinite structure.)


Finding common label sequences in a directed acyclic graph

Can't you just use the graph to build a trie, and then have the counts of all words.  (You would have to augment the trie slightly.)  It's a simple step from there to sort the words by number of occurrences, although the most common word will trivially be the single label that appears the most in your DAG.  (It gets more interesting if you look at most common words of a given length...)


Solving an online problem without maximizing or minimizing an objective

@orlp's intuition is correct.

lemma. No online algorithm solves the problem in the worst case.

Proof.  Consider the following instance:

$$f(p) = (1+p_1)(1+p_2)(1+p_3) \ge 8 \text{ with } B=3.$$

This instance has just one solution (one $p$ that satisfies it), namely $p=(1,1,1)$.  So, given $B=3$ and $L=8$ and just the first factor $1+p_1$, the algorithm has to choose $p_1 = 1$.

But then the adversary instead continues by defining the following instance:

$$g(p) = (1+p_1)(1+ 1.49 p_2)(1+0\cdot p_3) \ge 8 \text{ with } B=3.$$

This instance is feasible (e.g. for $p_1=p_2=3/2$ we have $g(p)\approx 8.1$). However, the algorithm committed to $p_1 = 1$, so the residual problem it is faced with is now $2(1+1.49 p_2) \ge 8$ with $p_2 \le 2$.  Since $2(1+1.49\cdot 2) < 2\cdot 4 = 8$, this residual problem is not feasible.

So the online algorithm cannot guarantee a solution, even if it knows in advance that it will face just one of the two instances above. $~~~\Box$


How many edges are cut in a balanced partition of a graph?

Even in the current updated version of the question, it still remains ill defined. There many different ways by which you can partition a graph into symmetric (or balanced if you like) clusters. One question that you might have in mind but have problem expressing is the minimum multisection (or partition): Given a graph $G$ find a symmetric partition $P$ of its vertices such that it minimizes the edges between different clusters.

In which case the answer is that the problem is NP-hard [1] and moreover it is NP-hard to approximate within a constant factor [2].

[1] L. Hyafil and R. L. Rivest. Graph partitioning and constructing optimal decision trees are polynomial complete problems. 1973.

[2] K. Andreev and H. Racke. Balanced graph partitioning. 2004.


May Boolean circuits be exponentially more concise than Boolean formulae?

The circuit complexity of any boolean function of $n$ variables is at most $(1+o(1))2^n/n$, so a separation of between circuit and formula complexity of $\Omega(2^n)$ is not possible. This upper bound was established by Lupanov, and his method is known as the Lupanov representation of boolean functions. It also gives an upper bound of $(1+o(1))2^n/\log n$ for the formula complexity of any $n$-variable boolean function. See for example these lecture notes for a detailed presentation. Of course this does not rule out a separation of $2^{\Omega(n)}$.

To the best of my knowledge the biggest separation known currently is $n^{3-o(1)}$ (over the de Morgan basis). It was proved by Håstad for a function with linear circuit complexity. This was an improvement on the method of Andreev, who showed a formula size lower bound of $\Omega(n^{2.5})$ for the same function using the method of random restrictions. You can check these notes for Andreev's proof. Håstad's bound is essentially tight for Andreev's method.

The class of functions computable by polynomial size formulas coincides with (nonuniform) NC1 and the class of functions computable by polysize circuits is P/poly. Separating these two classes is a well-known open problem in complexity theory, and is almost certainly well out of reach.


To my knowledge, no one has figured out how to exploit the "counting solutions" property of #SAT in any lower bound on deterministic algorithms, so unfortunately the best known lower bounds for #SAT are basically the same as that for SAT.
However, there has been a little progress. Note that the decision version of #SAT is called "Majority-SAT": given a formula, do at least $1/2$ of the possible assignments satisfy it? "Majority-SAT" is $PP$-complete, and given an algorithm for Majority-SAT, one can solve #SAT with $O(n)$ calls to the algorithm.
The closest that people have gotten to new lower bounds for #SAT (that are not known to hold for SAT) is with lower bounds for "Majority-of-Majority-SAT": given a propositional formula over two sets of variables X and Y, for at least $1/2$ of the possible assignments to $X$, is it true that at least $1/2$ of the assignments to $Y$ make the formula satisfiable? This problem is in the "second level" of the counting hierarchy (the class $PP^{PP}$). Quantum time-space lower bounds (and more) are known for this class.
The survey at http://pages.cs.wisc.edu/~dieter/Papers/sat-lb-survey-fttcs.pdf gives an overview of results in this direction.
UPDATE: As of 2019, the first paragraph in the above is obsolete. It is known that #SAT requires a time-space product that is basically $n^2$. See for example
"Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle" https://drops.dagstuhl.de/opus/volltexte/2018/10149/


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

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

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

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


The concept of "witnesses" or "checkable proofs" is not totally new: as mentioned in the comments, look for the concept of "certificate". Three examples came to mind, there are more (in the comments and elsewhere):

Kurt Mehlhorn described in 1999 a similar problem in computational geometry algorithms (e.g. minor errors in coordinates can yield big errors in the results of some algorithm), solved in a similar way in the library Leda, by insisting that each algorithm produces a "certificate" of its answer in addition of the answer itself.
Demaine, Lopez-Ortiz and Munro in 2000 used the concepts of certificates (they call them "proofs") to show adaptive lower bounds on the computation of the union and intersection (and difference, but this one is trivial) of sorted sets. Don't exclude their work because they did not use certiticates to protect against computing errors: they showed that even though the certificate can be linear in the size of the instance in the worst case, it is often shorter, and hence can be "checked" in sublinear time (given random access to the input as a sorted array or a B-Tree), and in particular in time less than required to compute such a certificate.
I have been using the concept of certificates on various other problems since seeing Ian Munro presenting their implementation at Alenex 2001, and in particular for permutations (apologies for the shameless plug, another one is coming), where the certificate is shorter in the best case than in the worst or average case, which yields a compressed data structure for permutations. Here again, checking the certificate (i.e. the order) takes at most linear time, less than computing  it (i.e. sorting).

The concept is not always usefull for error checking: there are problems where checking the certificate takes as much time as producing it (or simply producing the result). Two examples come to mind, one trivial and one complicated, Blum and Kannan (mentioned in the comments) give others.

The certificate for proving that an element is not in an unsorted array of $n$ elements is obtained in $n$ comparisons and checked in the same time.
The certificate for the convex hull in two and three dimensions, if the points are given in random order, takes as much bits to encode as comparisons to compute [FOCS 2009] (other shameless plug).

The library Leda is the most general effort (that I know of) toward making deterministic certificate-producing algorithms the norm in practice. Blum and Kannan's paper is the best effort I saw to make it the norm in theory, but they do show the limits of this approach.

Hope it helps...


Does Memcomputing really solve an NP-complete problem?

I feel this has been answered sufficiently in the comments, so to just sum everything up:

The authors do not claim P=NP, which is a statement about deterministic and nondeterministic Turing machines.
The authors propose a model of computation that they claim to show is equivalent in power to nondeterministic Turing machines.
The authors construct physical machines that implement this model of computation for small input sizes.
The authors argue that building larger versions is physically realizable/possible with polynomial-sized resources.
This last claim, which is of course not proven and not really a formal statement, would imply a that it is generally physically possible to solve NP-complete problems with polynomial-sized resources.
Scott Aaronson in a blog post explains why this last claim is problematic and why the scalability of their approach has problems: http://www.scottaaronson.com/blog/?p=2212


Matrix rigidity and uses of matrices with low rigidity

lacking further clarification of the question, heres a try/sketch of an answer. matrix rigidity has deep connections to fundamental questions in TCS/complexity theory including circuit lower bounds,[1] and thereby complexity class separations, and coding theory[2] as well as other areas. [5] is a nice slide survey.

the terms "low" and "high" in reference to rigidty of matrices are used informally and not in a precisely defined technical sense. [although Friedman did define "strong" rigidity. [6]] random matrices are known to have high rigidity but basically, its ~a 3.5 decades old open problem in this area to explicitly construct any matrix with "significantly high" rigidity.

the question doesnt further define/clarify the subjective terms "nontrivial" or "nonobvious" & will take some freedom there.

in this area there is a line of research looking at the rigidity of Hadamard matrices which have misc uses/applications in coding theory & elsewhere.

it seems fair to say a provably high rigidity result would surpass the threshhold of leading at least to "new nontrivial corollaries in complexity theory" but the best known bounds on Hadamard matrices do not suffice.[3] but neither does this conclusively prove they have limited "low" rigidity. its basically the same story with Vandermonde matrices [also applications in coding theory] considered by Lokam.[4]

so to summarize about all that can be said is that "weak lower rigidity bounds" have been proven on some matrices including Hadamard/Vandermonde matrices.

there also do not appear to be any published numerical experiments, estimates, or algorithms in the area.

[1] Boolean Function Complexity by Stasys Jukna, 2011, sec 12.8 "rigid matrices require large circuits"

[2] On matrix rigidity and locally self-correctable codes Zeev Dvir

[3] Improved lower bounds on the ridigity of Hadamard matrices Kashin/Razborov

[4] On the Rigidity of Vandermonde Matrices Lokam

[5] Mahdi Cheraghchi matrix rigidity talk

[6] J. Friedman. A note on matrix rigidity. Combinatorica, 13(2);235-239, 1993


Correcting a conference paper error in the journal version

I think it is very helpful to point out if and where previous results are erroneous. I've done this myself (more times than I would have liked to). My style is to state the correct result, and in immediate proximity (above, below, footnote) a remark to the effect that "In the conference version [citation], Theorem X incorrectly stated that...".


Numerical precision in sum-of-squares method?

I think my answer is probably insufficient, but it remains for completeness' sake (although see Boaz's comments below for probably a better answer)

When we limit ourselves to boolean variables, the claim can be seen when $(x_i^2-1) \in E$ for all $i \in[n]$ with the observation that degree $2n$ pseudo-distributions are actual distributions, that is, suppose you have a pseudo-distribution $\mu(x)$ over solutions $x$ of your polynomial equalities $E$ satisfying:

$\sum_{ x \in \{-1,1\}^n} \mu(x)$ and $\sum_{x\in\{-1,1\}^n} \mu(x) p^2(x)\ge0$ for all polynomials $p$ with degree at most $n$

But degree $n$ polynomials include the indicator polynomial (for example, $x_1 = 1, x_2=-1, x_3=1$ has $2^{-3}(1+x_1)(1-x_2)(1+x_3)$ which is all-zero elsewhere and 1 on that assignment). So $\mu(x) \ge 0$ for all $x\in\{-1,1\}^n$, so we conclude $\mu$ is an actual distribution over the solutions of $E$. Degree $\ell$ pseudo-distributions can be found by using semidefinite programming to find an associated degree $\ell$ pseudo-expectation operator in $n^{O(\ell)}$ time, so we can find the actual distribution $\mu$ in time $n^{O(n)}$ by using that pseudo-expectation (now an actual expectation) to find all the moments of $\mu$.

So, if $|E| = O(1)$, then you can find a distribution of solutions to $E$ in $O(1)$ time. Of course, brute force search guarantees the same.

However, if the solutions are not necessarily boolean, then degree-$2n$ pseudo-expectations are not sufficient to find a distribution over solutions. As can be seen above, the proof that degree $2n$ pseudo-distributions are actual distributions depends on the fact that degree $n$ polynomials are sufficient to 'pick out' individual assignments, which is not true more generally. Another way of viewing it is that boolean-variable polynomials are considered $\mod(x_i^2)$, so the degree of every monomial is at most $n$.

For example, one could consider replacing every binary variable with a 4-ary variable, say by including $(x_i^2-1)(x_i^2-4) \in E$. Then you would have to have a degree $4n$ pseudo-expectation in order to guarantee recovery of a distribution over solutions.

Now, for theoretical guarantees, it seems like approximating a root of a system of polynomals is also known as Smale's 17th problem, and apparently there is a randomized (Las Vegas) polynomial time algorithm that solves this - see http://arxiv.org/pdf/1211.1528v1.pdf. Note that this seems to be in the Blum-Shub-Smale model, so real operations are the primitive. I am not sure if this gives the guarantee that you need.


Who coined the term "empirical entropy"?

I am interested in "empirical entropy" like you and the earliest paper I find was that from Kosaraju like the user "Marzio De Biasi" told in his comment.

But in my opinion the real definitions of "empirical entropy" are made later by generalizing the former concepts:

"Large Alphabets and Incompressibility" by Travis Gagie (2008)
"Emprical entropy" by Paul M. B. Vitányi (2011)

Gagie rephrase the definition of $k$th order empirical entropy to:

$H_{k}(w)=\frac{1}{|w|}\min\limits_{Q}\left\{\log\large\frac{1}{P(Q=w)}\right\}$

where $Q$ is a $k$th order Markov process. He also showed that this definition is equivalent to the previous one.
The next step from Vitányi was a generalization to arbitrary classes of processes (not only Markov-processes):

$H(w|\mathcal{X})=\min\limits_{X}\left\{K(X)+H(X):\;\left|H(X)-\log\large\frac{1}{P(X=w)}\right|\normalsize\;is\;minimal!\right\}$

where $\mathcal{X}$ is the class of allowed processes and $K(X)$ is the Kolmogorov complexity.
If we choose $\mathcal{X}$ to be the class of $k$th order Markov processes producing  a sequence of $|w|$ random variables and ignoring the Kolmogorov complexity, than this also leads to the definition of Gagie (multiplied with $|w|$).


Languages recognized by polynomial-size DFAs

the question does not seem to have been studied much (one possibility is attempting to find a relationship with a "nearby" complexity class say P/poly etc); although here is at least one ref that touches on it:

Language operations with regular expressions of polynomial size Gruber/Holzer

  This work deals with questions regarding to what extent regularity-preserving language operations affect the descriptional complexity of regular expressions. Some language operations are identified which are feasible for regular expressions in the sense that the result of the operation can be represented as a regular expression of size polynomial in that of the operands. We prove that taking language quotients, in particular the prefix and suffix closures, of a regular set can incur at most a quadratic blow-up on the required expression size. The circular shift operation can cause only a cubic increase in size and at least a quadratic bloat can be necessary in the worst case.

as AS suggests there may be other more natural ways to study something like the question posed. here is another somewhat similar way to study growth of a regular language based on number of words of size $n$ which does have some loose relation to the question eg

Finding the growth rate of a regular or context-free language in polynomial time
(Gawrychowski, Krieger, Rampersad, Shallit)

  Given a context-free language L, we can test whether it is of polynomial or exponential growth in polynomial time. Moreover, if it is of polynomial growth we can also find the exact order of this polynomial in polynomial time.


You could start with the survey article by Peter Hinman, Recursion on Abstract Structures, Chapter 11 of the Handbook on Computability Theory (editor E. R. Griffor). If you follow the references there you'll find a wealth of material.


NP-hard problems with very fast exponential-time algorithms

The desired property holds for Independent Set (and probably other problems) in graphs of suitably bounded tree width.

Fix any constant $\epsilon>0$ and consider the Independent Set problem restricted to graphs of tree width at most $n \log_2(1+\epsilon) = \Theta(\epsilon n)$, where $n$ is the number of vertices.  Call this problem $\Pi_\epsilon$.

Lemma 1. The problem $\Pi_\epsilon$ has an algorithm running in time $O((1+\epsilon)^n n^{O(1)})$.

Proof. This is a direct corollary of a result in [1] --- that Independent Set has an algorithm running in time $O(2^{\text{tw}(G)} n^{O(1)})$, where $\text{tw}(G)$ is the tree width of the given graph $G$.  $~~\Box$

Lemma 2. Assuming ETH, there is no algorithm for $\Pi_\epsilon$ that runs in time $2^{o(n)}$.

Proof. Per [2] Theorem 3.3, assuming ETH, there is no $2^{o(n)}$-time algorithm for Independent Set.  Suppose for contradiction that there is an algorithm $A$ for $\Pi_\epsilon$ running in time $2^{o(n)}$.  Construct an algorithm $B$ for Independent Set as follows:

Algorithm $B$ on input $G$, an arbitrary graph with $n$ vertices:

Let $G'$ be the graph obtained from $G$ by adding artificial vertices, each with no edges, to bring the total number of vertices to $n'=n/\log_2(1+\epsilon)$.
Run the algorithm $A$ for $\Pi_\epsilon$ on $G'$ to find a maximum independent set $I'$ in $G'$.
Let $I$ be $I'$ minus all artificial vertices.  Return $I$.

Graph $G'$ has tree width at most $n'\log_2(1+\epsilon) = n$ because $G$ has tree width at most $n$.  So $A$ returns a maximum independent set $I'$ for $G'$ in time $2^{o(n')} = 2^{o(n)}$. $I'$ must consist of a maximum independent set $I$ in $G$ together with all the artificial vertices.  So $B$ returns a maximum independent set in $G$ in time $2^{o(n)}$, contradicting Theorem 3.3 of [2]. $~~~\Box$

Note: Edited 12/30/2019 to correct an error in the lower-bound argument.

[1] Invitation to Fixed-parameter Algorithms. Rolf Niedermeier. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford

[2] Lower bounds based on the exponential time hypothesis. D Lokshtanov, D Marx, S Saurabh - Bulletin of the EATCS no 105, pp. 41 71, October 2011


Reductions of hard problems to physical models

Counting constraint-satisfaction problems (#CSP), evaluating partition functions of many physical models, as well as many topics in classically simulating quantum states/circuits, are all fundamentally contracting tensor networks, which is a #P-complete problem. For a good overview see the following papers:

Itai Arad, Zeph Landau, Quantum computation and the evaluation of tensor networks

Cai, Lu, Xia Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

See especially the introduction of the latter for the connection to physical models.


Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?

Yes, and you'd be right.    2^(2^(i+1)) = 2^((2^i)*(2^1)) = 2^((2^i)*2) = (2^(2^i))^2 ,  so just

pad the input n-vertex instance of vertex cover with 2^(2^(ceil(log2(log2(n))))) isolated vertices.

For all positive integers c, a similar thing will apply when 2^(2^i) gets replaced with 2^(2^(c*i)).

However, under plausible assumptions, that's tight:

Let S be the set of functions from {0,1,2,3,...} to itself that are in ω(1), consider any functions

f and g in S, and let Q be the result of replacing 2^(2^i) with 2^(2^(f(i))) before applying

your sparse embedding.  If Q is NP-hard even under polynomial-time Turing reductions,

then    NP $\subset$ r.o.$\hspace{-0.04 in}\big(\hspace{-0.05 in}$DTIME(2^(n^(o(1))))/g$\hspace{-0.04 in}\big)$ ,  where maxL(n) is an upper-bound

on the length of each of the reduction's oracle queries for n-bit inputs

and the advice can be any function h in S such that

max  (  {0,1,2,3,...,maxL(n)-1,maxL(n)}  ∩  Range(i $\mapsto$ 2^(2^(f(i))))  )    is r.o. at most n^(1/(h(n))).

Furthermore, if there is a function j in S such that  f(n)+j(n) ≤ f(n+1)  holds for all sufficiently large n, then the set of input-lengths on which the algorithm errs can be covered by a collection of

polynomial-length integer intervals such that the gaps between them have length n^(ω(1)),

and if additionally j is computable 2^(n^(o(1)))) time when n is the input itself, not the input's length,

then the advice can be removed.  (without losing the interval-cover property I just mentioned)


Bounds on this Strategy for Separating Words

The second section of Robson's "Separating strings with small automata" proves $F(n) = O((n \log n)^{1/2})$. The string sequence $(10^n)^n$ gives a lower bound of $\Omega(n^{1/2})$. If the automaton has $<n$ states then both of the sequences $\delta_0^{\circ m} (\delta_{(10^n)^{n-1}1}(q_0))$ and $\delta_{10^n}^{\circ m}(q_0)$ will reach a cycle before $m=n$.


One book that I can recommend is D. Grune, C. J. H. Jacobs, Parsing Techniques: a Practical Guide.


Does bit commitment yield oblivious transfer in the information-theoretic security model?

No, commitment has strictly lower complexity than OT. I think an easy way to see this is the approach taken in Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation by Maji, Prabhakaran, Rosulek in TCC 2009 (disclaimer: self promotion!). In that paper we have a result characterizing what you can do given access to ideal commitment in the UC model with statistical security.

Suppose there were a statistically secure protocol (against malicious adversaries) $\pi$ for OT using access to ideal black-box bit commitment. Then $\pi$ must be secure against honest-but-curious adversaries as well (not as trivial as it probably sounds, but not very difficult to show either). But you could compose $\pi$ with the trivial honest-but-curious protocol for commitment, and have an honest-but-curious OT protocol that is statistically secure with no setups. But this is known to be impossible.

Another way to see it is through Impagliazzo-Rudich. If you have computationally unbounded parties and a random oracle, you can do commitment (since all you need are one-way functions) but you cannot do things like key agreement, and thus not OT.


Are there any hard instances of 3-SAT when the clauses can only use literals that are "nearby" each other?

No.  If the 3-SAT instance has $m$ clauses, then you can test satisfiability in $O(m 2^N)$ time.  Since $N$ is a fixed constant, this is a polynomial-time algorithm that solves all instances of your problem.

The algorithm works in $m$ stages.  Let $\varphi_i$ denote the formula consisting of the clauses that use only variables from $x_1,\dots,x_i$.  Let $S_i \subseteq \{0,1\}^n$ denote the set of assignments to $x_{i-N},x_{i-N+1},\dots,x_i$ that can be extended to a satisfying assignment for $\varphi_i$.  Note that given $S_{i-1}$, we can compute $S_i$ in $O(2^N)$ time: for each $(x_{i-N-1},\dots,x_{i-1}) \in S_{i-1}$, we try both possibilities for $x_i$ and check whether it satisfies all clauses from $\varphi_i$ that contain the variable $x_i$; if so, we add $(x_{i-N},\dots,x_{i})$ to $S_i$.  In the $i$th stage, we compute $S_i$.  Once we have finished all $m$ stages, the 3-SAT instance is satisfiable if and only if $S_m \ne \emptyset$.  Each stage takes $O(2^N)$ time, and there are $m$ stages, so the total running time is $O(m 2^N)$.  This is polynomial in the size of the input, and thus constitutes a polynomial-time algorithm.

Even if you allow a fixed number of clauses to violate the constraint, the problem can still be solved in polynomial time.  In particular, if $t$ counts the number of clauses that violate the constraint, you can solve the problem in $O(m 2^{(t+1)N})$ time, by first enumerating all possible values for the variables in those clauses, then continuing with the algorithm above.  When $t$ is a fixed constant, this is polynomial time.  There may be more efficient algorithms.


Do all complexity classes have a leaf language characterization?

Have a look at

  Bernd Borchert, Riccardo Silvestri: A Characterization of the Leaf Language Classes. Inf. Process. Lett. 63(3): 153-158 (1997) (doi link here)

The authors characterize the leaf language classes as those which are (a) "countable", (b) are "downward" closed wrt polytime many-one reducibility, and (c) "join-closed" (i.e., disjoint union) wrt polytime many-one reducibility.

More formally, all the languages $L$ in a leaf language class have a bijection with the natural numbers, and the property that for every $C,D \in L$, if $E \leq^P_m C \sqcup D$ then $E \in L$ as well (the $\sqcup$ denotes disjoint union). Also, every "non-leaf language class" contains a language which fails to have one of these properties.

From these three conditions we can get many examples of classes which aren't leaf language classes. For example, the "countable" condition rules out advice classes like $P/poly$, and the "downward closed wrt polytime many-one reducibility" rules out fixed resource-bound classes like $SPACE[n]$. (Recall that the usual proof that $SPACE[n] \neq P$ uses the fact that $SPACE[n]$ is not closed under such reductions.)


Characterization of $L$ for which $\{ww : w \in L\}$ is not a CFL?

More of an extended comment with a conjecture, but here is a condition that seems to capture the problem, in the context of regular $L$ for $S(L)$ to be context-free.

Condition
In the minimal DFA $A$ for $L$, any accepting path contains at most one loop.

Exception: two loops are allowed if their labels and the label of the prefix before the first loop all commute, and the suffix after the second loop is empty. For instance $aa^*b(aa)^*$ is ok.

Recall that two words $u$ and $v$ commute if they are powers of a same word $t$. We can assume the suffix empty, because it cannot be non-empty and commute with the label of the second loop in a DFA.

Sufficient
Assume the  condition, you build a PDA for $L$ by treating each accepting pattern $xuy$ of $A$ where $u$ labels a simple loop. We want to accept words of the form $xu^nyxu^ny$. We read $x$, push a symbol for every occurence of $u$, read $yx$, then pop a symbol for every occurence of $u$, and finally read $y$.

About the exception, if we are in this case, a basic accepting path is of the form $xuyv$ where $u,v$ are the labels of the loops. We accept words of the form $xu^n y v^m xu^n y v^m$, but by assumption ($x,u,v$ commute) it is the same as $u^nxyu^n v^mxyv^m$, which can be done by a PDA: push $n$ times (for occurences of $u$), read $xy$, pop $n$ times, push $m$ times (for $v$), read $xy$, pop $m$ times.

The final PDA is the union of the PDAs for each pattern.

Necessary
(handwaving) If there is a path with two loops, even in the simplest case where you must take one then the other (for instance $a^*b^*$), you must remember how many times each one is taken, but the stack structure prevents you to repeat them in the same order. Notice that the fact that the DFA is minimal is important in the characterization, to avoid using two loops when one could suffice.

For now the necessary part is only a conjecture, and more exceptions could be needed to get the exact condition, I would be interested in counter-examples.


Not quite answering what you want, but if you want the gcd of all $k\times k$ minors, then you can compute it in $O(n^\omega)$ or up to logarithmic factors. This is known as Smith Normal Form. For any matrix over principal ideal ring (or PID), the $k$ invariant factor of Smith normal form is the ${\rm gcd}$ of all $k\times k$ minors.


APX is defined as a subset of NPO, so yes, if an optimization problem is in APX then the corresponding decision problem is in NP.

However, if what you're asking is whether an arbitrary problem must be in NP (or NPO) if there is a poly time O(1)-approximation, then the answer is no.  I don't know of any natural problems that serve as a counter-example, but one could define an artificial maximization problem where the objective is the sum of two terms, a large term that is easily optimized in P, and a much smaller term that adds a small amount if part of the solution encodes an answer to some hard problem (outside of NP).  Then you could find, say, a 2-approximation in poly time by concentrating on the easy term, but finding an optimal solution would require solving the hard problem.


Predict user's future location - location awareness mobile computing

My professor uses a hidden markov model based upon the previous routes that the bus has been. See http://www.cs.uic.edu/~jakob/papers/transitgenie-sensys09-demo.pdf for a paper on it. Although the paper doesn't go into the architecture I remember it from a lecture he gave on the application.


Are there any universal quantum gates?

Not for single gates.

{NAND} may also be represented as two gates {AND, NOT}, and remains a minimally functionally complete set of classical gates.

The Hadamard gate and Toffoli gate are one minimal set of universal quantum gates.


The way to view testing a math statement (e.g., a resolution of P vs NP) as a question of the form "is formula .. satisfiable" is the following:

Fix some axiom system.
Given a string of length n, whether the string is a proof for the math statement in the axiom system, is something one can define in a straightforward manner:
the string should consist of propositions. Each proposition should either be an axiom, or should follow from the previous propositions by one of the inference rules.

It's not a problem to define a Boolean formula that verifies all this.
All you should know is the length n of the proof!


There are pretty much no complexity-theoretic consequences of Factoring being in P. This means that there are no good justifications for factoring being hard, other than that nobody has been able to crack it so far.

Polynomial-time factoring would make it possible to take square roots over $Z_n$ (and also over a much more general class of rings as well), and give polynomial-time algorithms for a number of other number-theoretic problems for which the bottleneck in the algorithm is currently factoring.

As for practical consequences, banking transactions are probably not that much of a problem -- as soon as it was known that factoring was in P, the banks would switch to some other system, probably causing only a brief period of delays while this was being implemented. Decoding past banking transactions would probably not cause serious problems for the banks. A much more serious problem is that all the communication which was previously protected by RSA would now be in danger of being read.


#P-complete problems are at least as hard as NP-complete problems

It's not at all weird to compare the complexity of counting and decision problems: reductions allow you to do that very naturally. You can use reductions to compare any kind of problem: decision, counting, approximate counting, optimization, function problems, ... All of this follows from the intuitive notion that a reduction from A to B means "If I could solve B, I could also solve A at roughly the same cost."

The existence of easy decision problems whose counting version is hard is a red herring. Counting matchings is the hard problem: if you could do that, you could solve any NP problem by reduction. Detecting matchings is easy: you can do that but it doesn't (seem to) help you to solve NP-complete problems.


Finding a positive point for a collection of polynomials

Yes, your problem is NP-hard, by reduction from THREE-SATISFIABILITY.

  THREE-SATISFIABILITY:
  Instance: Boolean variables $u_1,\ldots,u_n$; clauses $c_1,\ldots,c_m$ of length three over the $u_i$
  Question: Does there exist a truth setting of the $u_i$ that makes all clauses $u_j$ true?

For every Boolean variable $u_i$, introduce a corresponding real variable $x_i$ together with the two polynomials $x_i^2-0.9^2$ and $1.1^2-x_i^2$.
We say that $x_i$ represents the Boolean variable $u_i$, and that $-x_i$ represents the negated Boolean variable $\bar{u}_i$.
For every clause $c_j$, introduce one corresponding polynomial that is the sum of the real variables corresponding to the three literals plus $1.1$.
(For instance, the clause $u_a\lor\bar u_b\lor\bar u_c$ is represented by the corresponding polynomial $x_a-x_b-x_c+1.1$.)

We claim that the THREE-SATISFIABILITY instance has answer YES, if and only if there exists a positive point for the constructed set of polynomials.

  (Proof of only if):

Consider a satisfying truth setting for the THREE-SATISFIABILITY instance. If $u_i$ is true, then set $x_i=1$, and if $u_i$ is false, then set $x_i=-1$. This makes all polynomials $x_i^2-0.9^2$ and $1.1^2-x_i^2$ positive. Since every clause contains at least one true literal, the sum of the corresponding three real variables is at least $-1-1+1=-1$, so that the corresponding polynomial yields a value of at least $0.1$.

  (Proof of if):

Consider a positive point for the constructed set of polynomials. Then $x_i^2-0.9^2>0$ and $1.1^2-x_i^2>0$ enforce that either $-1.1<x_i<-0.9$ holds (in which case we set $u_i$ false) or $0.9<x_i<1.1$ holds (in which case we set $u_i$ true). Suppose for the sake of contradiction that under the constructed truth setting, some clause $c_j$ would contain three false literals. Then each of the three corresponding real variables is $\le-0.9$. Then the polynomial corresponding to that clause has value at most $-0.9-0.9-0.9+1.1<0$; contradiction.


Your confusion appears to be over the fact that $\mathsf{NP}$ problems have more than one way to define a "solution" (or witness). The type of the solution is not part of the definition of the problem. For instance, for graph coloring, the obvious type of solution is an assignment of one color for each vertex (using at most the required number of colors); however, by the Gallai–Hasse–Roy–Vitaver theorem another type of solution that works equally well is an assignment of an orientation to each edge (creating directed paths of at most the required number of vertices). These two types of solutions can both be checked in polynomial time, but by different algorithms, and they also have different combinatorial properties. For instance, for a typical problem instance, the number of vertex color assignments will be different from the number of edge orientations. A lot of research on speeding up exponential algorithms for NP type problems can be interpreted as finding a new family of solutions to the same problem that has fewer possibilities to check.

Every problem in $\mathsf{P}$ has an $\mathsf{NP}$ "solution" consisting only of the empty string. To verify that this is a solution, just check that the solution string is empty and then run the polynomial time algorithm for the problem instance. With this type of solution, every yes instance has exactly one valid solution and every no instance has zero, meeting the definition of $\mathsf{UP}$ and showing that $\mathsf{P}\subset\mathsf{UP}$. If $\mathsf{P}=\mathsf{NP}$ then the same empty-string solution would also work for every problem in $\mathsf{NP}$, showing that $\mathsf{NP}=\mathsf{UP}$. So there is no contradiction between the fact that the empty-string solution is unique and the fact that some other type of solution for the same problem is non-unique.


Partition a graph into 2 connected subgraphs

The problem you asked is the unweighted version of the Balance Connected 2-Partition ($BCP_2$).

For unweighted case, any 2-connected graph can be partitioned into two connected subgraphs whose numbers of vertices differ by at most one. A simple algorithm uses st-numbering. For any 2-connected graph, we can label the vertices by $[1...n]$ such that any vertex has simultaneously a neighbor with smaller label and a neighbor with larger label. Let $V_1=\{1...n/2\}$ and $V_2=V-V_1$. It can be easily shown that both $V_1$ and $V_2$ induce connected subgraphs.

However, when there are cut vertices, the problem is NP-hard because it is equivalent to the weighted $BCP_2$. The transformation is as follows. Let $v$ be a cut vertex and $H$ be the maximum connected component in $G-v$. We shrink all components other than $H$ into $v$ and the weight of $v$ is given by the weight of the vertices combined in $v$. Repeat this process and we can obtain a weighted 2-connected graph.

It can be easily realized that there exists a graph such that the minimum part contains only $n/3$ vertices in any 2-partition.

For $BCP_2$, the currently best approximation algorithm is due to Chlebikova (I hope that it is not out of date):

Approximating the maximally balanced connected partition problem in graphs, Information Processing Letters, 60:225--230, 1996. The approximation ratio is 4/3. For some special graphs, there are better results. For example, FPTAS for interval graphs and 5/4-approximation for grid graphs (further improved to 7/6).


Why does the construction step of Aho-Corasick take linear time in the number of nodes?

Using for reference, Aho and Corasick, Efficient string matching: an aid to bibliographic search (Communications of the ACM, 18(6):333–340, 1975) (PDF).

Algorithm 2 is mostly creating a trie or "keyword tree" in the paper.

Important Note: They make the assumption that $g(s, a) = \texttt{fail}$ if either $a$ is undefined, or  $g(s, a)$ hasn't been defined yet. You can think of this function as an edge, it either points to the next state or returns $\texttt{fail}$. Assume evaluating and assigning to functions, such as $g$ or $output$, takes constant time.

Example:

Let's consider the intuition for a single keyword $x$. Use the last graph on page 335 with his, hers and she. Let's add "hello" and verify that it takes linear time in the length. We can generalize from there.

For this example, let $y = \text{hello}$.

$s = 0$, the initial state. First, we find out that $g(0, \text{h}) = 1$ so we
set $s = 1$. Next we check $g(1, \text{e})$, which takes us to $s = 2$.

Now $g(2, \textit{l}) = \texttt{fail}$, there is no edge for $\textit{l}$, we have to create a state, $s = 10$ and set $g(2, \textit{l}) = 10$. State $10$ corresponds to the string $\text{hel}$.

Again $g(10, \textit{l}) = \texttt{fail}$, we create a new state $s = 11 \text{(hell)}$. The same happens for $\textit{o}$ : $g(11, \textit{o}) = \texttt{fail}$, make a new state $12 \text{(hello)}$.

We've finished $\text{hello}$, as a last step we set $output(12) = \text{hello}$.

Rough Analysis:

Calling $g(s,a)$, assigning values, and creating new states are constant time. Since we perform a constant number of each operation per letter, the complexity is $\mathcal{O}(|\text{y}|)$.

Algorithm 2 does this for each key word. Notice that the same bound holds for each keyword added, regardless of what $g(s,a)$ returns for each letter. Then the total time complexity is $\mathcal{O}(\displaystyle \sum_i^k{|y_i|})$, proportional to the sum of the length of the keywords.

The algorithm also sets a self-loop for any unused symbols, or $g(0, a) = 0$ for all $a$ that weren't the first letter of a keyword. We only need to consider letters in the set of keywords, so this step is still bounded by the sum length.


The Complexity Zoo says:

... There exist oracles relative to which $EXP=NP=ZPP$ [Hel84a], [Hel84b], [Kur85], [Hel86],....

See for example Two oracles that force a big crunch.

Perhaps the original oracle used by Dekhtyar is less powerful (and simpler): On the relativization of deterministic and nondeterministic complexity classes in Proc. Mathematical Foundations of CS 1977 ... but I don't have his paper.


Theoretical proof of convergence of sequential weight update procedure (Neural Networks and Machine Learning)

As pointed out by Rong, for gradient descent to converge the learning rate $\eta$ has to be chosen appropriately. It has to be large enough that every update determines a big enough change in the weights, but it has to be small enough not to overshoot the local minimum of the cost function. You may want to take a look at this paper that analyzes some sufficient conditions for gradient descent to work

Armijo, Larry (1966). "Minimization of functions having Lipschitz continuous first partial derivatives". Pacific J. Math. 16 (1): 1–3.


Does the first order theory of a finite structure have bounded quantifier rank?

The theory of any finite structure is model complete. In fact, it is easy to see that any formula is equivalent to an existential formula with one quantifier per each element of the structure, after which all quantifiers of the original formula can be simulated by conjunctions and disjunctions. In particular, the number of quantifiers (hence quantifier rank) is bounded by the size of the structure.


Name of (and solution to) this generalization of linear assignment

It looks to me like this is a special case of minimum cost flow; introduce one vertex per row and one per column, with an edge for each entry whose cost is the negative of the value of that entry and whose capacity is 1.  Then add an edge of capacity $b$ from the source to each row, with cost 0, and similarly for the columns, and solve the resulting minimum cost flow problem -- which can be done in polynomial time.
Since all edge capacities are integers, stndard algorithms will return an optimal solution that is integral.


Barendregt's proof of subject reduction for $\lambda2$

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

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

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

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


Fastest approximate triangle counting algorithms in dense graphs

I have written up an answer, it can be found here: https://arxiv.org/abs/2104.08501
The best known triangle counting algorithm runs in time $\tilde{O}(n^\omega)$. I was able to retain the exponent of $n$ while having negative dependence on $T$. In fact, the running time is $\tilde{O}_\epsilon(n^\omega/T^\delta)$ such that there is the is no such algorithm for any constant $\delta' < \delta$. In this sense, the algorithm is optimal. (One could, however, imagine an algorithm with non-constant $\delta$.) The value of $\delta$ is $\omega - 2$. This degenerates to $0$, if there exists a quadratic matrix multiplication algorithm.
I have also done the same for sparse matrix multiplication. There, the state-of-the-art was $\tilde{O}(m^{2\omega/(\omega+1)})$. I have retained the exponent while again having "optimal" negative dependency on $T$ (albeit the optimality is in the fairly weak sense mentioned above).
For a sketch of the algorithm, see page 5 in the paper. If you have comments, I would be very happy to hear them.
Here is a diagram comparing the running time to other algorithms:

(I have just noticed that the diagram on the right should have log base $m$, I'll fix it later)
The "optimality" lies in the fact that the blue line (my algorithm) touches the dashed red line (the lower bound). And yes, our algorithm is in fact slower than state-of-the-art for large values of $T$. On that range, the optimal algorithm was in fact already known. One could probably fix that so that this algorithm is never slower than the state-of-the-art; however, the analysis is already technically non-trivial as it is now.


Partitioning a connected polygon into connected pieces of equal area

To complement Sariel's answer, some closely related problems are hard. In particular, for a non-convex polygon, it's NP-hard to find a partition into two pieces of equal area while minimizing the length of the cut. See: Elias Koutsoupias, Christos Papadimitriou, and Martha Sideri (1992), "On the optimal bisection of a polygon", ORSA J. Comput. 4 (4): 435–438, doi:10.1287/ijoc.4.4.435.


Approximating Max-Coverage when the elements need to be covered multiple times

If the required number of times we need to cover an element is 2, we have the following densest k-subgraph problem: (Imagine the edges are elements and nodes are sets.)

  Given a graph $G$ and an integer $k$, find a subgraph of $G$ on $k$ nodes with maximum density.

Khot proved that no PTAS exists under plausible complexity assumptions; there is an $O(n^{1/4+\epsilon})$ approximation to the problem by Bhaskara, Charikar, Chlamtac, Feige and Vijayaraghavan; a polynomial integrality gaps result by Bhaskara, Charikar, Guruswami, Vijayaraghavan and Zhou.  Therefore I believe your question is hard to approximate in the most general case.


Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$?

It's not quite what you ask, because the 3d version is even harder than NP-complete, but: Finding a shortest path between two points among polygonal obstacles in the plane is in polynomial time (most simply, construct the visibility graph of the two terminals and the polygon vertices and apply Dijkstra; there is also a more complicated O(n log n) algorithm due to Hershberger and Suri, SIAM J. Comput. 1999) but finding a shortest path among polyhedral obstacles in 3d is PSPACE-complete (Canny and Reif, FOCS 1987).


Is the Witness Size of Membership for Every NP Language Already Known?

If you don't mind artificial languages, we can construct such problems using pretty much any number k whose value is unknown to mathematicians. For example, we don't know the value of R(5,5) (the fifth Ramsey number), or the size of the largest excluded minor of the family of knotless graphs (this number is finite due to the Robertson-Seymour theorem), or the value of BB(10), where BB() stands for the Busy Beaver function. Let k equal any of these numbers. We know that k is finite, but we don't know the value of k.

Now construct some problem in NP where the witness is of size $O(n^k)$. Off the top of my head I can't think of a nice way of doing this, but here's one way. Let the input be a succinct description of a graph. Since the description size is n, the graph is on exponentially many vertices. (For example, maybe the input is a circuit that accepts two inputs x and y and tells you if (x,y) is an edge in the graph.) The question is to determine if the graph contains a path of length $n^k$. This problem is in NP because the prover can send the list of vertices on the path in order, which the verifier can check. The size of the witness is $n^k$.


What is best known space requrement for solving SATISFIABILITY problem in exp time

If I understand your question correctly, as far as I understand this is computational-model dependent. An excellent lecture on the subject by Prof. Ryan O'Donnell can be found here: https://www.youtube.com/watch?v=_nCBH_lVjGU


(Sorry but not enough reputation otherwise this would be a comment.)
Note that set difference is equivalent to set intersection with the complement i.e. $S_i\backslash S_j = S_i \cap \overline{S_j}$. Thus you could double the number of sets to $S_1, S_2, ...., S_k, \overline{S_1}, ..., \overline{S_k}$ and apply the set intersection pre-processing to the appropriate pairs.


Required mathematics for computational geometry research career

I'm going to answer a slightly different question (as indicated in my comment):

  Is there specific mathematical background that would help prepare for
  a graduate degree in TCS that focuses on computational geometry?

I have found (from conversations with other TCSers) that some kinds of geometric intuition are unfamiliar, so the best kind of background will help you in that regard. A comprehensive list along these lines would include:

Topology (point-set, combinatorial and algebraic)
Differential geometry (and some basic Riemannian geometry as well)
Convex analysis (especially duality)
Some basics in algebraic geometry (at least polynomials)
Basic functional analysis (normed spaces, Hilbert spaces, etc)

All of these tools show up in computational geometry nowadays on a regular basis, and their use will only get more sophisticated with time.

p.s As an aside, if you have a computer engineering degree, it's possible that your background in core theoryCS is weaker than if you had a straight-up CS degree (because of the emphasis on the EE side of things). If that's the case, then the material in the links provided by Kaveh will be immensely useful, probably more so than this list.


Efficient and simple randomized algorithms where determinism is difficult

Sorting nuts and bolts

The following problem was suggested by Rawlins in 1992:  Suppose you are given a collection of n nuts and n bolts.  Each bolt fits exactly one nut, and otherwise, the nuts and bolts have distinct sizes.  The sizes are too close to allow direct comparison between pairs of bolts or pairs of nuts.  However, you can compare any nut to any bolt by trying to screw them together; in constant time, you will discover whether the bolt is too large, too small, or just right for the nut.  Your task is to discover which bolt fits each nut, or equivalently, to sort the nuts and bolts by size.

A straightforward variant of randomized quicksort solves the problem in $O(n \log n)$ time with high probability.  Pick a random bolt; use it to partition the nuts; use the matching nut to partition the bolts; and recurse.  However, finding a deterministic algorithm that even runs in $o(n^2)$ is nontrivial.  Deterministic $O(n\log n)$-time algorithms were finally found in 1995 by Bradford and independently by Komlós, Ma, and Szemerédi.  Under the hood, both algorithms use variants of the AKS parallel sorting network, so the hidden constant in the $O(n\log n)$ time bound is quite large; the hidden constant for the randomized algorithm is 4.

Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Noar, and Rafail Ostrovsky. Matching nuts and bolts. Proc. 5th Ann. ACM-SIAM Symp. Discrete Algorithms, 690–696, 1994.
Noga Alon, Phillip G. Bradford, and Rudolf Fleischer. Matching nuts and bolts faster. Inform. Proc. Lett. 59(3):123–127, 1996.
Phillip G. Bradford. Matching nuts and bolts optimally. Tech. Rep. MPI-I-95-1-025, Max-Planck-Institut für Informatik, 1995. http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-025
Phillip G. Bradford and Rudolf Fleischer. Matching nuts and bolts faster.  Proc. 6th. Int. Symp. Algorithms Comput., 402–408, 1995. Lecture Notes Comput. Sci. 1004.
János Komlós, Yuan Ma, and Endre Szemerédi. Matching nuts and bolts in $O(n\log n)$ time. SIAM J. Discrete Math. 11(3):347–372, 1998.
Gregory J. E. Rawlins. Compared To What? : An Introduction to The Analysis of Algorithms. Computer Science Press/W. H. Freeman, 1992.


Edge-partitioning into rainbow triangles

I followed the link in the question, and the reduction there actually produces graphs whose edges have a natural coloring such that each $K_n$ present in the graph is a "rainbow $K_n$" (has exactly one edge of each color). In other words, we can easily adjust the reduction in that paper so that it reduces to your problem instead of reducing to the partition into $K_n$s problem: simply assign each edge a color according to this natural coloring and then the graph can be partitioned into "rainbow $K_n$s" if and only if it could be partitioned into $K_n$s at all.

The basic structure of the reduction in that paper can be accomplished with the following 3 steps:

Create many copies of a particular graph $H_{n,p}$.
Identify certain pieces of some copies of $H_{n,p}$ with each other (i.e. merge vertices/edges between multiple different copies of $H_{n,p}$).
Remove certain vertices/edges from some copies.

The graph $H_{n,p}$ has as its vertices the set of length-$n$ vectors modulo $p$ for which the components add to $0$ mod $p$. The edges connect every two vertices that differ in only two components with differences of $+1$ and $-1$ in those two components.

I propose the following coloring for this graph: assign a color to each edge according to its direction. If $x$ and $y$ are adjacent vertices, then $x-y$ is a vector with $n-2$ components equal to $0$, one component equal to $1$ and one component equal to $-1$. In other words, for every edge $(x, y)$ there are ${n \choose 2}$ options for which components of $x-y$ are non-zero. If we assign a unique color to each of these options then we have a coloring for all the edges such that every edge in the same direction has the same color. It is pretty easy to verify that no two edges in a $K_n$ in $H_{n,p}$ are in the same direction. Therefore every $K_n$ in $H_{n,p}$ is a rainbow $K_n$ under this coloring.

When we follow the reduction, we use this coloring for every copy of $H_{n,p}$. Therefore at the end of step 1 in the list above, every $K_n$ in the graph is a rainbow $K_n$.

In step 2 of the above list, we identify some vertices/edges with each other. In particular, in the reduction we always identify a $K_n$ with another $K_n$. But in this situation (where all the $K_n$s are from a copy of $H_{n,p}$), every $K_n$ is either a translation of the "standard $K_n$" which the paper calls $K$ or a translation of $-K$. Therefore, we are either identifying two parallel $K_n$s or two $K_n$s that are "flips" of each other. In either case, the edges that are identified across the two $K_n$s are parallel and are therefore the same color. For example, see Figure 2 in the paper; edges that are identified are always parallel. Thus, since we never try to identify two edges of different colors, the coloring at the end of step 1 in the above list can be naturally extended into a coloring at the end of step 2. Identifying certain vertices/edges together doesn't create any new $K_n$s, so it is still the case at the end of this step that every $K_n$ is a rainbow $K_n$.

Finally in step 3 we remove some vertices/edges, which also doesn't create any new $K_n$s. Thus, we have our desired property: under the coloring I provided, every $K_n$ in the graph generated by this reduction is a rainbow $K_n$.


What are some interesting applications of homotopical algebra in theoretical computer science?

Two big applications of homotopy theory in theoretical computer science are

Homotopy Type Theory revealed a completely unexpected connection between the theory of the typed lambda calculus and homotopy theory. As a quick intuition, think of it as either a (vast) generalization of the connection between intuitionistic logic and topological spaces, or a language for doing "synthetic homotopy theory".
The directed version of algebraic topology and homotopy theory (ie, where paths are not reversible) has been developed precisely with applications to computer science in mind. The intuition is that the possible evaluations of a concurrent program correspond to a space, program executions correspond to paths in that space, and synchronization primitives correspond to obstructions. By considering the geometric properties of these spaces/programs, it becomes possible to develop tools for reasoning about their behaviour.


Deciding the Most Significant Bit of Binary Multiplication

Multiplication is complete for $\mathsf{TC}^0$ and
this is a well know result.
The reduction is from Count
(number of 1 bits in a binary number).
Comparison of binary numbers is in $\mathsf{AC^0}$
so $\mathsf{Majority}$ is reducible to $\mathsf{Count}$.

To reduce $\mathsf{Count}$ to $\mathsf{Mult}$ do as follows:
consider input is $a_0a_1\ldots a_n$.
Insert $k$ 0s between $a_i$s and call it $a$.
Multiply it with $b$ which is like $a$ except that
$a_i$s in it are replaced with 1s.
Pick $k>3n$.
The number in the middle section of $ab$ is the answer.
The reduction is in $\mathsf{FO}$ and shows that
$\mathsf{Count} \in \mathsf{FO(Mult)}$.


Offline multidimensional RMQ/RSQ in query model

So, you are interested in range queries in the "dense case" (an array) as opposed to the case most frequently studied in theory (arbitrary points in space).

The RMQ problem is easier than the semigroup sum problem, and no $\alpha$ is needed. The most recent result I know is: Hao Yuan, Mikhail J. Atallah: Data Structures for Range Minimum Queries in Multidimensional Arrays, SODA 2010

The semigroup sum problem is mainly of theoretical interest, in my opinion (what is a natural semigroup beyond max?). This explains why the Chazelle-Rosenberg paper does not have a lot of citations.


Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?

For the question of when does $p=0 \Rightarrow q=0$, randomness can indeed help, as follows. First, factor $p$ (uses randomness when $p$ is given as a straight-line program; doesn't need randomness if $p$ is given as a coefficient vector). Let $\tilde{p}$ denote the square-free version of $p$ - that is, if $p=p_1^{k_1} p_2^{k_2} \dotsb p_\ell^{k_\ell}$ then $\tilde{p} = p_1 p_2 \dotsb p_\ell$. Then $q=0$ follows from $p=0$ iff $\tilde{p}$ divides $q$, which happens iff $q$ is of the form $q=p_1^{k'_1} \dotsb p_\ell^{k'_\ell} f$ with all of the $k'_j$ strictly positive. The latter can be checked by factoring $q$ (uses randomness, as before).
For the general question of $p_1=\dotsb=p_k=0 \Rightarrow q=0$, randomness seems not to help from the complexity perspective, as this problem is $\mathsf{EXPSPACE}$-complete (randomness may help in practice though...).
For the problem of telling whether the variety $\{\vec{x} : p_1(x)=\dotsb=p_k(x)=0\}$ is empty or not (for polynomials given by a list of monomials and coefficients - which is "sparse but not succinct", that is, not SLPs), randomness also seems to help: assuming GRH, this problem is in $\mathsf{RP}^{\mathsf{NP}}$ by a result of Koiran. It is $\mathsf{NP}$-hard, and not known to be in $\mathsf{P}^{\mathsf{NP}}$.


Existence of $d$-regular expander graph that can be represented as a bipartite graph

The obvious thing to try would be to convert a non-bipartite regular expander to a bipartite one using the bipartite double cover, which preserves regularity. But it might not preserve expansion; in particular, if you have only a small number of vertices involved in odd cycles, they would become a bottleneck in the double cover.

But if all you need is constant expansion (rather than stronger properties like, say, being a Ramanujan graph) then converting a non-bipartite graph to a bipartite one while preserving constant expansion is easy: just subdivide each edge to make it bipartite (as Yixin Cao already suggested in comments), and then add enough extra edges to the subdivision vertices to make it regular again.

For the stronger expansion that you get from Ramanujan graphs, see Marcus, Spielman, and Srivastava "Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees", FOCS 2013. Judging from the abstract (I haven't read the paper carefully) they appear to be using the bipartite double cover idea, but with a bit more care to avoid the bottlenecks.


here is one table about the different similarity measures which can be found in this paper https://www.cs.cmu.edu/~jingx/docs/DBreport.pdf


The problem is still NP-complete. Here's a reduction from the Treewidth problem on general graphs. Recall that for a graph G of treewidth at least two, the treewidth is not affected when subdividing an edge by a degree-2 vertex (i.e. replacing an edge $\{u,v\}$ by a new vertex $x$ and edges $\{u,x\}$, $\{x,v\}$ ).

Given an input graph $G$ on $n$ vertices, assume without loss of generality that it has treewidth at least two (otherwise we can solve the problem and output an equivalent constant-sized instance). Number the vertices of G from $1$ to $n$, in some arbitrary order. Now assign vertex $v_i$ to set $S_{2i}$, and observe that trivially, each set $S_i$ induces an independent set in the graph; we will maintain this during the following process. As long as the graph has an edge $\{u,v\}$ between two vertices which are not in adjacent sets, say an edge between a vertex in $S_i$ and one in $S_j$ for $i < j$ and $j-i > 1$, subdivide the edge, placing the newly created degree-2 vertex in set $S_{i+1}$. Since this subdivider vertex is placed between the endpoints of the subdivided edge, it decreases the difference between the indices of the sets that its neighbors are in, and therefore each edge of the original graph is subdivided no more than $n$ times. So  this process terminates after a polynomial number of steps. The resulting graph $G'$ was made from G by repeatedly subdividing edges, so its treewidth equals that of G. Let us verify that the resulting sets satisfy that all connected components of $G'[S_i \cup S_{i+1}]$ are bicliques. One of the indices $i, i+1$ is odd. By construction, the set for this odd index contains only degree-2 vertices which were added to subdivide an edge. Since the subdivider vertex was placed "in the gap between its two neighbors", each degree-2 vertex has one neighbor in the previous set, and one neighbor in the next set. So the set out of $S_i, s_{i+1}$ with odd index has only vertices which have degree one in the graph $G'[S_i \cup S_{i+1}]$, which shows that the graph is a disjoint union of stars which are bicliques. So the graph G' has treewidth equal to G, size polynomial in that of G, and can be constructed in polynomial time. Since treewidth is NP-complete, so is the restriction to your special graph class.


Forcing method used in Baker-Gill-Solovay Relativization paper and Cohen's Proof of Continuum Hypothesis Independence

For more uses of forcing (via so-called generic oracles) in complexity theory, see The Oracle Builder's Toolkit (freely available from Fortnow's homepage) by Fenner, Fortnow, Kurtz, and Li. They give a general theory of generic oracles, and show its many applications in complexity.

If you're interested in how oracles in complexity are like independence proofs in set theory, you might be interested in the following papers:

Arora, Impagliazzo, Vazirani. Relativizing versus Nonrelativizing Techniques: the Role of Local Checkability.
Impagliazzo, Kabanets, Kolokolova. An Axiomatic Approach to Algebrization. (full version freely available from Kabanets's homepage)

For the uses of forcing in set theory, see the book Set Theory (Set Theory on Amazon) by Jech, especially Parts II and III of the book (not to be confused with "Introduction to Set Theory" by Hrbáček and Jech).


Sublinear finite-precision sampling in a stream

The strategy will be to use Vitter's algorithm, but replace the arbitrary-precision random number with online generation of the bits of that random number.

Building block: sampling without arbitrary precision arithmetic

Suppose we want to sample a discrete random variable $X$ from a distribution with cdf $F$ (i.e., $F(x) = \Pr[X \le x]$).  Then one approach is to sample $y$ uniformly at random from $[0,1]$, find $x$ such that $F(x-1) < y \le F(x)$, and output $x$.  This requires arbitrary precision arithmetic.

Here is a variant that avoids the need for arbitrary precision arithmetic, at the cost of making the algorithm a Las Vegas algorithm (so the worst-case running time is unbounded but the expected running time is nicely bounded).  Basically, we sample the bits of $y$ one at a time, and stop as soon as we know what answer the prior method would output.  At the $b$th stage, we know the first $b$ bits of $y$, i.e., we know $\tilde{y}$ such that $y \in [y, y + 1/2^b)$ and $2^b \tilde{y}$ is an integer.  Now, we find $x$ such that $F(x-1) < \tilde{y} \le F(x)$.  If $F(x-1) < \tilde{y}$ and $\tilde{y} + 1/2^b \le F(x)$, then we output $x$ and stop.  (In this case, we don't know what the exactly value of $y$ is, but we still know it satisfies $F(x-1)< y \le F(x)$, so $x$ is certainly the right answer.)  Otherwise, we output nothing and continue, sampling the next bit of $y$.

What's the running time of this procedure?  The expected time until termination is $O(\lg n)$, where $n$ is the number of different possible values of $X$.  (Why?  Because at the $b$th stage, at most $n$ out of the $2^b$ possible values for $\tilde{y}$ will cause us to continue on to the $b+1$th stage.  In particular, once $b$ exceeds $\lg n$, each stage has at least a one-half probability of terminating.)  So, this gives a Las Vegas algorithm to sample from $X$, with exactly the right distribution, and with $O(\lg n)$ expected bits sampled from the RNG.

Solving your problem

Now we can solve your particular problem.  We simply apply Vitter's algorithm (e.g., Algorithm Y), but instead of sampling the random value $\mathscr{S}$ using arbitrary-precision arithmetic, instead use the method described above.

How many random bits do we need?  Based on the results in that paper, the expected number of times we need to sample $\mathscr{S}$ is $O(\log n)$, where $n$ is the length of the stream.  Also each time we sample $\mathscr{S}$ the expected number of bits we need to sample is $O(\log n)$.  Therefore, we'll need $O((\log n)^2)$ bits from the RNG, on average.

Also the total (expected) running time will be $O(n)$, if you use Vitter's efficient algorithms for sampling $\mathscr{S}$ (e.g., Algorithm Y and binary search or Newton's method).


Is there any programming language theory describing foreign function interfaces (FFI) and multiple language bindings?

The paper Operational Semantics for Multi-Language Programs
by Jacob Matthews and   Robert Bruce Findler presents two approaches for defining the semantics of programs written in two programming languages, taking particular care of data defined in one language and used in the other.  The lump embedding allows values created in one language to appear in running code of another, but these are can only be passed around, not operated on (or perhaps operated on by only a small interface).
The natural embedding  allows values in one language to be used in the other by performing a so-called cross-language cast, which converts values from one language to the other.

The paper JNI Light: An Operational Model for the Core JNI by Gang Tan presents a formal semantics of how existing JNI works. In contrast to the previous paper, this is formalises many of the low level details of what's going on, rather than trying to explore the issues from a foundational perspective.

Work on type-checking foreign function calls, such as Checking Type Safety of Foreign Function Calls by Michael Furr and Jeffrey Foster,  provide also a formal framework in which to phrase the type system and prove its soundness.

Looking at the references in these papers and finding where they are cited using google
scholar will help you discover a more thorough picture of what has been done in the area.


The answer to your question is "yes" for a wide variety of classes and reductions, including logspace reductions and the classes you mentioned, as is proved in these papers:

  H. Vollmer.  The gap-language technique revisited.  Computer Science Logic, Lecture Notes in Computer Science Vol. 533, pages 389-399, 1990.

  K. Regan and H. Vollmer.  Gap-languages and log-time complexity classes.  Theoretical Computer Science, 188(1-2):101-116, 1997.

(You can download gzipped postscript files of these papers here.)

The proofs follow the basic principle of Uwe Schöning's extension of Ladner's theorem:

  Uwe Schöning.  A uniform approach to obtain diagonal sets in complexity classes.  Theoretical Computer Science 18(1):95-103, 1982.

Schöning's proof has always been my favorite proof of Ladner's theorem -- it's both simple and general.


Decomposition of edges of eulerian graph into maximum number of cycles

This paper may be helpful with regard to the question you raised:
https://pdfs.semanticscholar.org/32a0/821e384e726819155065f7bc26e2d57329e5.pdf


Is this a known problem, and is it #P-complete?

To Question 1: The graphs induced by such edge sets are known as pseudoforests. As your proof of the membership to #P implies, an edge set is the image of a selection function if and only if the graph induced by the edge set allows an edge orientation in which each vertex has out-degree at most 1. A graph is a pseudoforest if each connected component is a tree or a tree + one edge. It is known (and easy to see) that a graph is a pseudoforest if and only if it admits an outdegree-at-most-1 orientation.

To Question 2: The problem is #P-hard on general graphs (not sure about bipartite graphs). The family of edge sets of a graph inducing pseudoforests forms the family of independent sets of a bicircular matroid. Counting the number of independent sets of a matroid $M$ is equivalent to computing the Tutte polynomial $t(M;2,1)$. It is shown by Giménez and Noy that computing $t(M;2,1)$ is #P-hard even if $M$ is a bicircular matroid given as a graph.


Proving liveness-like property on an infinite tree

See the comments on the question above: both a proof by contradiction and a use of König's lemma appear to suffice.


Is there a polynomial time algorithm for creating a set of vectors in general position?

Let me give some details for the Cauchy matrix construction, which is simple. Let $x = (x_1, \ldots, x_n)$, $y = (y_1, \ldots, y_m)$ be sequences of pairwise distinct numbers. The corresponding Cauchy matrix is
$$
C = \begin{pmatrix}
\frac{1}{x_1 - y_1} & \frac{1}{x_1 - y_2} & \ldots & \frac{1}{x_1 - y_m}\\
\frac{1}{x_2 - y_1} & \frac{1}{x_2 - y_2} & \ldots & \frac{1}{x_2 - y_m}\\
\vdots & \vdots & \ddots & \vdots\\
\frac{1}{x_n - y_1} & \frac{1}{x_n - y_2} & \ldots & \frac{1}{x_n - y_m}\\
\end{pmatrix}
$$

Then any square submatrix of $C$ is an invertible square Cauchy matrix. In particular, the $n\times n$ submatrix $C_J$ with columns indexed by $J = \{j_1, \ldots, j_n\}$, $j_1 \leq \ldots \leq j_n$, has determinant
$$
\det C_J = \frac{\prod_{i = 2}^n\prod_{k = 1}^{i-1}{(x_i - x_k)(y_{j_i} - y_{j_k})}}{\prod_{i = 1}^n\prod_{k = 1}^n{(x_i - y_{j_k})}}.
$$

Because $x$ and $y$ are sequences of distinct numbers, the determinant is nonzero, and $C_J$ is invertible.

If you prefer something even more concrete, you can take the Hilbert matrix: the Cauchy matrix with $x = (1, \ldots, n)$ and $y = (0, -1, -2, \ldots, -m)$. With $n = 3$ you get the points $(1, 1/2, 1/3),\ (1/2, 1/3, 1/4),\ (1/3, 1/4, 1/5),\ (1/4, 1/5, 1/6)$ and so on.


how to define "correlation" between languages?

Your idea only works on languages with finite descriptions; here is an approach that's well defined for all languages, but it requires choosing some probability distribution $\mu$ on the set of all finite words, $\Sigma^*$. Assuming that you've chosen one, let $A$ and $B$ be your two languages. Let $X$ be the random variable corresponding to the event that a $\mu$-random word belongs to $A$, and define $Y$ analogously for $B$. Now you can define correlation between $A$ and $B$ as the correlation between $X$ and $Y$ in the classical sense:
$$ cov(X,Y) = E[XY]-E[X]E[Y] =
\sum_{x\in\Sigma^*}1[x\in A\cap B]\mu(x)
-
\sum_{x,y\in\Sigma^*}1[x\in A]1[y\in B]\mu(x)\mu(y)
,
$$
and $cor(X,Y)=\frac{cov(X,Y)}{\sigma_X\sigma_Y}$, where
$$
\sigma_X^2 = \sum_{x\in\Sigma^*}1[x\in A]\mu(x)
-
\left(
\sum_{x\in\Sigma^*}1[x\in A]\mu(x)
\right)^2.
$$
A reasonable choice of $\mu$ would be to let word length be distributed, say, geometrically (or any other distribution on the integers), and within each fixed word length, $\mu$ is uniform. But of course the "reasonableness" or usefulness of this definition will depend entirely on your purposes.


Topological sorting of a DAG where special vertices have to come in even groups

The problem you are calling "two-by-two" topological sorting is the Two Processor Scheduling Problem (unit-length jobs, under precedence constraints given by a partial order on the jobs -- i.e., the DAG).  The partial order on the jobs constrains them so that if x<y then job y cannot be started until job x is completed.  Shelling the vertices of the DAG in pairs is like taking two unit-length jobs at a time to schedule on the two identical processors; a schedule with makespan n/2 is possible only if the DAG can be shelled in incomparable pairs, as required in your problem.

It is solvable in linear time, i.e., O(n+m) where n, m are number of, respectively, vertices and edges of the DAG. (Gabow, Gabow and Tarjan).  Earlier work by Coffman and Graham is a simpler but asymptotically not quite as fast algorithm; and Fujii, Kasami and Ninomiya also provide a poly-time algorithm. The Gabow and Tarjan algorithm has the advantage that you don't have to find the transitive reduction or transitive closure of the DAG first -- you can use it directly on the DAG.

I don't know the status of your original problem, though, where the distinguished vertices must be scheduled in blocks of even size.


Eta expansion in the pattern lambda calculus

This is not a complete answer; it is a comment that got too large.

If you extend typed lambda calculus with products with projective eliminators (ie, product eliminators fst(e) and snd(e)), there are no basically issues whatsoever. The reason it took so long to figure out is because it turns out to be more natural to do eta expansions rather than eta reductions.  See Barry Jay's The Virtues of Eta Expansion.

If you want products to have a pattern-style eliminator

let (a,b) = e in t

Then matters are more complex. The primary difficulty with pattern matching are the commuting conversions. That is, these calculi have the equation

C[let (a,b) = e in t] === let (a,b) = e in C[t]

and figuring out (a)  which context C[-] to use and (b) how to orient this equation gets tricky. IMO, the state of the art for rewriting-style approaches are Sam Lindley's  Extensional Rewriting with Sums and Gabriel Scherer's Deciding Equivalence with Sums and the Empty Type, both of which consider the typed lambda calculus with both products and sums.


The short answer: the really minimum knowledge of math to understand the first half of the plan of GCT, once you've seen a little of groups, rings, and fields, is basically laid out in Chapter 3 of my thesis (shameless self plug). That chapter is, however, incomplete, in that I don't get to the representation theory part of things. The representation theory is crucial for the second half of the plan (which is why I'm working on extending that chapter to include it).

If you really want to get into GCT, Symmetry, Representations, and Invariants by Goodman and Wallach and Actions and Invariants of Algebraic Groups by W. Ferrers Santos are both relatively self-contained and have lots of good information that is pertinent to GCT. I'm not sure if they're the best sources to learn from, as I only learned about them after I had learned much of this material, but they are good in terms of the ratio of what they cover to what's relevant to GCT. Fulton and Harris is great for representation theory and lots of the examples/exercises in the book are relevant to GCT.

The longer answer: it really depends on what/how much you want to learn about GCT, as Vijay pointed out. The topics below are just what I think is the background needed, since that was the question. I'm not sure this is a complete list - I would recommend trying to read some of the papers on GCT, and when you get lost go look for background material. As you're learning the background material, every so often come back to the GCT papers and see if you can follow further.

(Depending on what you want to learn, I would actually disagree with Zeyu that you should try some graduate commutative algebra first, though at some point in learning GCT this will become necessary.)

If you want to understand, for example, Mulmuley's recent FOCS paper, you'll want to understand:

the hardness vs. randomness principle (see Impagliazzo--Kabanets, and also perhaps Bill Gasarch's list of papers on hardness v randomness)
basic algebraic geometry up to Hilbert's Nullstellensatz and Noether's Normalization Lemma. These can be found in any basic textbook on algebraic geometry and probably in most lecture notes on it.
some classical invariant theory (you don't really need geoemtric invariant theory, schemes and the Mumford-Fogarty-Kirwan book for this paper). Sturmfels' book Algorithms in Invariant Theory comes to mind.
For certain results in the paper, but by no means for the paper in general, you might want some of (and these references can also be found in the paper): representation theory of $SL_n$ as in Fulton and Harris,  results on matrix invariants [Artin, Procesi, Razymslov], ...

If you want to understand the general outline of the GCT approach but in some mathematical detail, I'd suggest:

The permanent versus determinant problem. #P-completeness of permanent and GapL-completeness of determinant. Agrawal has a good survey (only very slightly outdated)  on this, and the proofs of completeness can be found in Burgisser's book Completeness and Reductions in Algebraic Complexity Theory.
Groups and group actions (algebraic groups and algebraic group actions are helpful, but not necessary at this level). You should understand the Orbit-Stabilizer Theorem.
Affine algebraic geometry through Hilbert's Nullstellensatz. Basically you just need to understand the correspondence between affine algebraic varieties and their coordinate rings.
Basic representation theory of $GL_n$ as in Fulton and Harris. Aside from basic definitions, you need to know complete reducibility of these representations, and the fact that representations of $GL_n$ are classified by partitions, but you don't necessarily need to know the proof/constructions of the latter.

If you want to understand deeply what's going on (and I'm not sure I can claim to be there yet, but I think I know what I need to know to get there), you should probably also understand:

The structure of reductive algebraic groups and orbit closures in their representations. I like the book by W. Ferrers Santos for this, but also Linear Algebraic Groups by Borel, The Classical Groups by Weyl, and other classics.
The Luna-Vust machinery (Luna's Slice Theorem, Luna-Vust complexity)
Tannakian Duality (see the paper by Deligne--Milne; this will be tough reading without some background in category theory and affine algebraic groups). This essentially says that "(pro-)affine algebraic groups are determined by their representations." I don't think you need the whole paper, so much as how to recover a group from its category of representations (Cor. 3.4).
More representation theory, especially as applied to the coordinate rings of algebraic groups and their orbit closures. I really like the book by Goodman and Wallach for this, particularly because it's basically self-contained, and it has a lot of exactly what you need to understand GCT. (Also, many of the expository/side sections and exercises in Fulton and Harris are right on the mark for GCT, especially those about Littlewood-Richardson and Kronecker coefficients.)

If you want to actually work on the representation theory, you probably want to understand more algebraic combinatorics / combinatorial representation theory. I don't really know all the right references for this, but certainly understanding the Littlewood-Richardson rule is a must, and Fulton's book Young Tableaux is good for this.

The most recent papers on this side of things that I know of are Blasiak, Kumar, and Bowman, De Visscher, and Orellana.

Depending on what direction you want to go in, you may also want to look into quantum groups, though this isn't necessarily necessary (note: these are not a special case of groups, but rather a generalization in a certain direction).

On the more geometric side of things, you'll want to look into things like differential geometry for tangent and osculating spaces, curvature, dual varieties, and the like, which are underlying the best known lower bound on perm vs. det due to Mignon--Ressayre and followed by Landsberg--Manivel--Ressayre. (Mignon--Ressayre can be understood without any of these things, but you can view their paper loosely as studying the curvature of certain varieties; for a less loose view, see the use of dual varieties in Landsberg--Manivel--Ressayre.) (See also Cai, Chen, and Li, which extends Mignon--Ressayre to all odd characteristics.) See also Landsberg and Kadish.

If you're interested in the GCT approach to matrix multiplication, it's all about tensor rank, border rank, and secant varieties. I'd suggest looking at the papers by Burgisser--Ikenmeyer, Landsberg and Ottaviani, Landsberg, Landsberg's survey and book. Of course, it would also be good to know the classical stuff on matrix multiplication (both upper and lower bounds), but that's a whole separate can of worms.


Dependent corrections in measurement-based Universal Blind Quantum Computation

Sure. The dependency sets arise from 'flow', which is indeed described in the paper you link to. This is, however, perhaps overkill for what we need.

The idea behind the corrections is to insure that the same effective operator is applied independent of which branch you find yourself in after making a measurement. To do this in principle is fairly simple. Since all the measurements we make are in the XY plane, obtaining a 1 as the measurement outcome for a particular qubit $q$ of state $| \psi \rangle$ yields the same final state as as obtaining a 0 for the same measurement of the same qubit on a state $Z_q | \psi \rangle$. Thus to correct for obtaining a 1 rather than a 0 it is sufficient to find an operator $C$ on the output state such that $Z_q \otimes C | \psi \rangle = | \psi \rangle$.

Now, this implies that $Z_q \otimes C$ is a stabilizer of the initial state. A stabilizer for a state is simply an operator which has that state as an eigenvector with corresponding eigenvalue $+1$.

As it turns out, it is extremely easy to enumerate the generators of the stabilizer group for any graph: For every vertex $v$ in graph $G$ the operator $X_v \prod_{i\in\mbox{nbgh{v}}} Z_i$ is a stabilizer of the graph state, where $\mbox{nbgh{v}}$ denotes neighbours of $v$ in $G$. Thus in order to find the correction for the measured qubit it we can simply pick the stabilizer corresponding to a qubit neighbouring $q$ and multiply it by $Z_q$. This gives a set of $X$ and $Z$ corrections which, when applied to the output state, yield a state equal to the output of the process had the measurement result been inverted.

We need one further requirement, which is that the correction set be in the future of $q$ (i.e. have not yet been measured). This obviously places restrictions on which neighbour of $q$ we choose. In the case of the brickwork state we introduce, this is satisfied uniquely by choosing $v$ to be neighbour of $q$ which is in the same row as $q$ but the next column on. This may sound arbitrary,but as it turns out, this is the unique choice satisfying the conditions I mentioned.

Hopefully this answers your question.

EDITED TO NOTE: You can propagate forward $Z$ corrections by applying the above procedure recursively, so that corrections on any qubit which is to be measured will be $X$ corrections. Whether or not an $X$ correction needs to be made to a particular qubit will then depend on the parity of the measurements for all qubits for which the correcting operator contains an $X$ at this location. To work out this set it is easiest to work the other way around: Simply calculate the correction operators for each vertex propagating all the $Z$ operators to the output qubits, and then once you have these operators work out which measurements alter the measurement at a given site.


Probability of random variable $X$ less than $max(Y_i)$

We have $\Pr[\max(Y_1,Y_2) \leq k] = \Pr[Pois(\lambda) \leq k]^2 = e^{-2\lambda}(\sum_{j=0}^k\frac{\lambda^j}{j!})^2$.

Therefore, $\Pr[X \geq \max(Y_1,Y_2)] = \sum_{k \in \mathbb N} \Pr[X = k] \cdot \Pr[\max(Y_1,Y_2) \leq k] = e^{-(2\lambda+\mu)} \bigg (\sum_{k = 0}^\infty\frac{\mu^k}{k!} \cdot (\sum_{j=0}^k \frac{\lambda^j}{j!})^2 \bigg)$.

From this, if you have some concrete values of $\lambda$ and $\mu$, you can try to see which terms are important, and which are negligible.

I guess the important terms are $k < O(\lambda)$.


How can I randomly generate bounded height spanning trees?

I was working on bounded-depth spanning trees a few years ago, they're really interesting.  Some of my colleagues came up with message passing algorithms that did a great job, but I can't find any of their code available.  We wrote it up in a physics style here:  http://iopscience.iop.org/1742-5468/2009/12/P12010/.  They've told me that it also works with degree bounds, although that didn't make it into the paper.

The approach you propose, which I would call Markov Chain Monte Carlo, is often a competitor to the message passing approach.  If you are interested in sampling approximately uniformly at random from the set of bounded-degree, bounded-depth spanning trees of a given graph, I suggest altering your approach to use "soft" bounds.  I.e. instead of rejecting an edge swap that makes the tree violate the depth bound, accept it, but with lower probability than a swap which does not violate the bound.  If you have a parameter that controls how much lower this probability is, you can make the constraint violating configurations less and less probable until you arrive at a feasible solution that is nearly uniformly random.

The big question is how long do you need to run the chain.  Since a spanning tree with degree at most 2 is a Hamiltonian path, you should expect any generic bound to be exponential in the size of the graph.  But maybe the graphs you are interested in are special in some way.


Is "Experimental Complexity Theory" being used to solve open problems?

In "Finding Efficient Circuits Using SAT-solvers", Kojevnikov, Kulikov, and Yaroslavtsev have used SAT solvers to find better circuits for computing $MOD_k$ function.

I have used computers to find proofs of time-space lower bounds, as described here. But that was only feasible because I was working with an extremely restrictive proof system.

Maverick Woo and I have been working for some time to find the "right" domain for proving circuit upper/lower bounds using computers. We had hoped that we may resolve $CC^0$ vs $ACC^0$ (or a very weak version of it) using SAT solvers, but this is looking more and more unlikely. (I hope Maverick doesn't mind me saying this...)

The first generic problem with using brute-force search to prove nontrivial lower bounds is that it just takes too damn long, even on a very fast computer. The alternative is to try to use SAT solvers, QBF solvers, or other sophisticated optimization tools, but they do not seem to be enough to offset the enormity of the search space. Circuit synthesis problems are among the hardest practical instances one can come by.

The second generic problem is that the "proof" of the resulting lower bound (obtained by running brute-force search and finding nothing) would be insanely long and apparently yield no insight (other than the fact that the lower bound holds). So a big challenge to "experimental complexity theory" is to find interesting lower bound questions for which the eventual "proof" of the lower bound is short enough to be verifiable, and interesting enough to lead to further insights.


the Erdos sunflower conjecture seems to be very difficult after now over a half century(!) of being open. youve already listed some of the very best and most recent refs on the subj that would be very hard to beat (Alons recent paper, Juknas book on combinatorics). the Alon paper is highly notable for newly linking the conjecture to lower bounds on matrix multiplication, an area that has seen recent groundbreaking advance in the Williams results.[4]

you can find some further treatment, mainly applications to extremal circuit theory (circuit lower bounds 1st discovered by Razborov & extended by others), in Jukna's outstanding book [1].

one notable/related recent ref along these lines apparently not-so-widely-known-or-cited-so-far is [2] by Rossman with a new direction of application (Erdos-Renyi random graphs over monotone circuits) and who proves extended and/or stronger results on "quasi-" sunflowers. the paper is a result from his Phd thesis [3]. from the paper abstract

  We introduce a new variant of sunflowers and prove an analogue of the sunflower lemma that may be of independent interest.

[1] Boolean function complexity, advances and frontiers

[2] The Monotone Complexity of k-Clique on Random Graphs (2009) Rossman

[3] Average-case complexity of detecting cliques by Rossman

[4] Commentary on Williams breakthrough on matrix product lower bound RJ Liptons Godels Lost Letter blog

[5] Detailed Materials on Sunflowers


Deciding whether a metric is a tree metric

If the given metric space embeds into a tree metric, the tree must be its tight span. The O(n^2) time algorithms referred to in Yoshio's answer can be extended to certain two-dimensional tight spans: see arXiv:0909.1866.

One method for solving the problem is incremental (as in the linked preprint, but much simpler): maintain a tree T containing the first i points from your metric space (that is, having the same distances as the corresponding entries of your input distance matrix) and extend it one point at a time; at each step there's at most one way to extend it.

To test whether to attach your new point r along edge uv of your existing tree, find points p and q of your metric space that are on opposite sides of edge uv. The new point attaches to a point inside edge uv iff d(p,r) > d(p,u) and d(q,r) > d(q,v); using this test on each of the edges of the existing tree, you can find where it attaches in O(n) time. Once you've found where to attach it you can test in O(n) time whether the distances to all the other points are correct. So each point you add takes time O(n) and the whole algorithm takes time O(n^2), optimal since that's the size of your input distance matrix.


Clearly polynomial mixing time implies polynomial cover time. (Well, not in general. We need the stationary probability at least $1/poly(n)$ at each vertex.) So check Mihail's paper Conductance and convergence of Markov chains-a combinatorial treatment of expanders which proves rapid mixing of regular directed graphs and general Markov chains based on conductance.

Also see the paper Pseudorandom walks on regular digraphs and the RL vs. L problem by Reingold, Trevisan, and Vadhan. Following Mihail's work. They defined the parameter $\lambda_\pi(G)$ which is equivalent to $\lambda_2(G)$, the second largest eigenvalue in absolute value, when the graph $G$ is time-reversible, and remains well-defined for general Markov chains. This parameter is then used to bound the mixing time of $G$.


Electrical engineering student interested in Theoretical computer science

Theoretical computer science has many dimensions. One of them is the study of programming languages (in
a general sense). Here is a path into this field.

An introductory textbook on logic like Dirk van Dalen's "Logic and
Structure". There are plenty of other good books on the subject, but
I recommend one that that talks a little bit about proof theory and intuitionistic
logic as both are at the heart of programming language theory's use of logic.
Followed by an implementation oriented book like John Harrison's
amazing "Handbook of Practical Logic and Automated Reasoning".
After finishing this book you could start coding, for example
SAT-solvers, a highly interesting field, merging theory and
practise. It's competitive too: http://www.satcompetition.org/
In parallel you can read an introductory text book on the theory of
programming languages.  Alas there is nothing really up-to-date,
reflecting the last 25 years of progress, but Glynn Winskel's "The
Formal Semantics of Programming Languages" might not be the worst
place to start.
Some, but not all parts of programming language research is
enamoured with category theory. The usefulness of category theory
for programming languages is fiercely debated. But since you've
already mastered abstract algebra, you should be able to pick up
category theory without too much pain. You could start with
"Category Theory" by Steve Awodey, or "Abstract and Concrete
Categories" by Adamek et al. The categorical viewpoint on a lot of
things can be quite mind-blowing.

You would be well-qualified to dive into more specialised subfields of programming language research with this background.

None of the above would be very useful for the algorithms / complexity
track of theoretical computer science.


Theoretically, can everyday computing tasks be broken down into ones solvable by a neural network?

Neural networks can arbitrarily approximate any computable function; see
http://en.wikipedia.org/wiki/Artificial_neural_network
or
http://en.wikipedia.org/wiki/Cybenko_theorem

Constructing a NN for a given function -- or worse yet, learning it from examples -- is a hard problem.


Is this graph transformation unique up to isomorphism? [Answer:NO]

Along with the already-given answers stating the existence of two graphs G1≠G2 for which T(G1)=T(G2), there is also a different problem: there exist pairs G1=G2 for which T(G1)≠T(G2). This is because the transformation depends not just on the isomorphism class of G, but also on the cyclic ordering of the edges around each vertex of G.

Edited to add an example based on Mark Reitblatt's comment:


An upper bound over the number of bipolar orientations for a regular graph

It is not always lower than the number of acyclic orientations by any factor, let alone an exponential one. In particular, in a complete graph, there are $n!$ acyclic orientations, all of which are bipolar.


Algorithms and computational complexity of clique and biclique covers

I am not sure if this is what you need.

Both Edge Clique cover and Edge Clique partition are in FPT, see

Data reduction and exact algorithms for clique cover

Parameterized complexity of the clique partition problem

Biclique cover is also studied and shown to be in FPT.


Implications of proof of abc conjecture for cs theory

Bhatnagar, Gopalan, and Lipton show that, assuming the abc conjecture, there are polynomials of degree $O((kn)^{1/2+\varepsilon})$ representing the Threshold-of-$k$ function over ${\mathbb Z}_6$. For fixed constant $k$, and $m$ which has $t$ prime factors, the abc conjecture implies a polynomial for Threshold-of-$k$ over $\mathbb Z_m$ with degree $O(n^{1/t+\varepsilon})$.

This presumably has relevance to the ${\sf TC^0}$ versus $\sf ACC^0[6]$ problem.


For example, I think you can decide if $\lfloor\log_2|w|\rfloor$ is even in time $O(n\log n)$: you first overwrite the input string with all 1s, and then do $\log n$ passes over the string where you turn every other 1 into a 0 (while skipping 0s that are already there). You keep track of the number of passes modulo 2.