Computing any information about Max-3SAT

Here is an argument that if you could solve Max 3SAT on an m-clause instance given a constant number of bits of advice, then the polynomial hierarchy would collapse.

Fix an NP-complete problem L. From Cook's theorem, we know a transformation f() of inputs x for L into 3SAT formulas f(x), so that

1) if $x\in L$ then $M(f(x)) = m$

2) if $x\in L$ then $M(f(x)) = m-1$

where $m$ is the number of clauses in $f(x)$.

We also have a theorem of Kadin, that says that, if given $k$ inputs $x_1,\ldots,x_k$ of an NP-complete problem, you have a polynomial time algorithm that makes $\leq k-1$ queries to an NP oracle and determines the correct answer to the $k$ NP problems $x_i \in ? L$, then the polynomial hierarchy collapses.

Suppose we have an algorithm that solves Max SAT on m-clause inputs given k bits of advice. We will use Hastad's result to construct an algorithm as in the premise of Kadin's theorem.

Start from the $K=2^k+1$ inputs $x_1,\ldots,x_K$ to problem $L$. Apply Cook's theorem to each of them. After some normalization (which can be done by assigning weights to the clauses, or duplicating them if we do not want to use weights), we construct $K$ formulas $F_1,\ldots,F_K$ where, for a certain $m$:

1) $M(F_1)= m-1$ if $x_1 \in L$ and $M(F_1) = m-2$ otherwise

2) $M(F_2) = m\cdot (m-1)$ if $x_2 \in L$ and $M(F_2) = m\cdot (m-2)$ otherwise

...

k) $M(F_K) = m^{K-1} \cdot (m-1)$ if $x_K\in L$ and $M(F_K) = m^{K-1} \cdot (m-2)$ otherwise

Now take the union of the formulas, which were constructed over disjoint variables sets, and call it $F$. So we have $M(F) = M(F_1) + \cdots + M(F_k)$, and we can "read off" the answer to the $K$ problems $x_i \in? L$ by looking at the base-$m$ representation of $M(F)$. If we can compute $M(F)$ given $k$ bits of advice, it means that we can find $2^k$ values such that one of them is $M(F)$. We can then ask non-adaptively an NP oracle whether $M(F) \geq n_i$ for each of the candidate values $n_1,\ldots,n_{2^k}$ we generated. So we have been able to solve $2^k+1$ instances of NP-complete problems by making $2^k$ non-adaptive queries to an NP oracle, which implies that the polynomial hierarchy collapses.

Using Hastad's theorem instead of Cook's theorem, it's possible to push  the size of $F$ to $O(1)^k \cdot m$ instead of $m^k$, so it's possible to push $k$ to $\log m$, and the number of advice bits to $\log\log m$. Understanding what happens when you are given  $\log m  - O(1)$ advice bits seems really difficult.

Edited to add: Krentel (The Complexity of Optimization Problems. J. Comput. Syst. Sci. 36(3): 490-509 (1988)) proved that computing the value of the optimum of the maximum clique problem is complete for $FP^{NP[O(log n)]}$, the class of functions computable in polynomial time with $O(log n)$ queries to an NP oracle. The completeness is under "one query reductions," in which function f is reducible to function g if one can write $f(x) = r_1(g(r_2(x))$ for polynomial time computable $r_1$ and $r_2$. Presumably the same is true for Max Clique. Now, if Max Clique had a polynomial time algorithm that produces a list of $m^{o(1)}$ possible values, it would be in $FP^{NP[o(logn)]}$, because you could use binary search to find the optimum with a number of queries that is log of the list size.

Now, if we have $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$ we would definitely have $P^{NP[O(log n)]} = P^{NP[o(log n)]}$, which is the special case for decision problems, and that is known, by results of Wagner (improving a result of Kadin that applies to a constant number of queries), to collapse the polynomial hierarchy. But I think that it might be known that $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$  would actually imply P=NP. But in any case the results of Krentel and Kadin-Wagner should be enough to give another proof of Andy Drucker's result. Now I wonder if it is actually the same proof, that is, if the Fortnow-Van Melkebeek result works, explicitly or implicitly, via a "simulating NP queries with fewer NP queries" argument.

A good survey paper that explains what is going on with optimization problems and bounded query classes:

http://www.csee.umbc.edu/~chang/papers/bqabh/npfsat.pdf


The undecidability of the halting problem.

Beautiful for many reasons. It is an impossibility result. The proof uses diagonalisation. The statement applies to a broad range of models of computation. It can be formulated in a variety of ways, particularly, using standard programming languages. It was a watershed result in the history of computing. Extending this statement leads to Rice's Theorem, Turing degrees and many other cool results. Etc. Etc. Etc.


What is the Complexity Status of Arbitarily Weighted Planar Max Cut?

After reading the paper you mentioned, it seems that the reduction stated in the paper is incomplete, therefore the result may not be correct.

In the paper the author gave a reduction from 3SAT to a problem called planar max-cycle-covering (although it is not consistent with the usual sense of a covering in graph theory, it is more like max-edge-disjoint-cycles problem), and proving that the max-cycle-covering problem and max-cut problem are dual to each other on planar graphs. While the second implication is correct, the reduction part mimics a proof to the NP-hardness of planar Hamiltonian cycle problem, and there may be a flaw in it.

In that proof one need a gadget for XOR-in-series (See Fig. 3 in the Hamiltonian paper); although the construction works in the Hamiltonian ones, I see no evidence that a similar construction is possible for cycle-covering, and there are no explanations in the paper. (And we need such a gadget in the NP-hardness proof of cycle-covering, see Fig. 6 in the max-cut paper.) The main problem is that for Hamiltonian cycle we can always be sure that the middle edge C must be passed though, hence we can "transfer" the XOR by the presence of the middle edge; but in cycle-covering we cannot guarantee that edge C must be passed though unless it is within a cycle passing though a heavy-weighted edge, and this is not the case here. (In fact we cannot enforce the edge being passed though, since in Fig. 6 if an edge C is passed though then the corresponding literal in the clause is true.)

My guessing is that planar max-cycle-covering cannot simulate 3-fan-in OR function, which is required in 3SAT. Supported with the answer by @turkistany, one should believe that planar max-cut problem is polynomial time solvable.


Is where an oracle B in EXP that $P^B$ $ \ne$ $NP^B$?

Yes, the Baker-Gill-Solovay B oracle is itself in EXP.


Difference between Multiple Knapsack problem and Multidimensional Knapsack Problem

In a multiple knapsack problem you pack a set of items into several (one-dimensional) knapsacks, whereas in the multidimentional knapsack problem you pack d-dimensional items into one d-dimensional knapsack. The multiple knapsack problem $\max\{\sum_i p_i x_i \mid \sum_i w_{ij}x_i \leq d_j, j=1,2,\ldots,m\}$ is a general 0-1 integer program restricted to positive coefficients. Its integrality gap is unbounded, since it includes the maximum independent set problem whose formulation $\max\{\sum_{v\in V} x_v\mid x_u+x_v\leq 1, \{u,v\}\in E\}$ on an undirected graph $G=(V,E)$ has integrality gap $|V|/2$.

You can find more information on these problems in chapters 9 and 10 of  Kellerer, Pferschy, and Pisinger, "Knapsack problems".


Relative error estimation of a special type of GapP function

This is #P-hard, already for an arbitrary fixed constant approximation factor. As you noted, it allows you to approximate $|f(x)|$ for any GapP-function $f$, and therefore if $f$ is any #P (or GapP) function, it allows you to approximate $|f(x)-y|$ for a given $y$. With this, you can still compute $f(x)$ by a form of binary search.
Specifically, fix a constant $k\ge\gamma^2+1$, where $\gamma>1$ is the approximation factor. Starting with an initial estimate $0\le f(x)\le 2^{n^c}$, if you already have $a_0<a_1$ such that $a_0\le f(x)\le a_1$, you compute $a'_0\le a'_1$ such that $a'_0\le f(x)\le a'_1$ and $a'_1-a'_0\le\lfloor(1-\frac1k)(a'_1-a'_0)\rfloor$ by computing the approximations $d_0,d_1$ such that
$$\gamma^{-1}d_i\le|f(x)-a_i|\le\gamma d_i,$$
and putting
$$[a'_0,a'_1]=\begin{cases}\bigl[a_0,a_1-\lceil\frac1k(a_1-a_0)\rceil\bigr]&d_0\le d_1,\\{}\bigl[a_0+\lceil\frac1k(a_1-a_0)\rceil,a_1\bigr]&\text{otherwise.}\end{cases}$$
To see that this is correct: if, for example, $d_0\le d_1$, then
$$f(x)-a_0\le\gamma^2(a_1-f(x)),$$
hence
$$f(x)\le\frac{a_0+\gamma^2a_1}{\gamma^2+1}=a_1-\frac{a_1-a_0}{\gamma^2+1}\le a_1-\frac{a_1-a_0}k.$$
The case $d_1\ge d_0$ is symmetric.


Lower bound on number of oracle calls for solving $n$ instances of the halting problem

The result can be found in

Beigel, R., Gasarch, W. I., Gill, J., and Owings, J.  Terse, superterse, and verbose sets.  Inform. and Comput. 103 (1993), no. 1, 68–85.

Their proof in fact shows that your problem cannot be solved with fewer than $\log_2 n$ queries to any set $X$, let alone to the halting problem itself. For some notation, your problem is sometimes denoted $C_n^K$ or $C_n^{HALT}$ (depending on your favorite notation for the halting problem).

For this and many related results, see also:

This survey by Gasarch
The book Bounded Queries in Recursion Theory by Gasarch and Martin.


Does it help for clique if the vertices are partitioned into 3 cliques?

Computing a maximum clique in a graph whose vertex set can be partitioned into 3 cliques, is equivalent to computing a maximum independent set in the complement graph, which can be partitioned into 3 independent sets and is therefore 3-colorable. The latter problem is still NP-complete, which can be seen as follows: Start from an arbitrary instance $(G,k)$ of independent set and subdivide each edge twice, i.e., replace each edge ${u,v}$ by a path ${u,e_1, e_2, v}$ on two new vertices. It is not difficult to prove that the resulting graph $G'$ has an independent set of size $k + |E(G)|$ if and only if $G$ has a size-$k$ independent set: for every independent set in $G$, you can add exactly one of the two subdivider vertices on every edge without violating independence.

Hence the Clique problem is still NP-complete for such inputs.


Regarding Question 1.

The examples you gave, linear programs and SDPs (both of which are linear programs over convex cones), can be generalized to convex programs: minimization of a convex function over a convex feasible set.  Since you are looking for 'other families of problems' that are efficient thanks to the presence of convexity, the natural thing to drop is the convex function part, and just look at convex sets.  This is the realm of convex geometry, and here there are lots of algorithms.

One of the standard favorites is:

Martin Dyer,  Alan Frieze,  Ravi Kannan. A Random Polynomial Time Algorithm For Approximating The Volume Of Convex Bodies.

The difficulty here is that the dimension is (at it should be) a part of the input; on the other hand, a naive algorithm samples points on the grid, which sticks the dimension in the exponent of the running time.  The reason why convexity helps is intuitive: convexity gives separation results, things like Farkas's lemma which say that a point is either in a closed convex cone, or you can separate them with a hyperplane.  The relevance here is say that you know some point is in the convex body, whereas some constellation of points around it is not in the body: from here you can lop off a huge piece of the input and never bother sampling from it.  Perhaps I should clarify that the above paper does the estimation by producing a nice sampling algorithm within the body (both of which are useful).  Last I checked, there is still no deterministic analog to this; I just googled to see if the status has changed (seems not), and was fed these notes that have a few references which may interest you: http://www.cs.berkeley.edu/~sinclair/cs294/n16.pdf .  I never took this class and only looked briefly, so my apologies if there are some problems, but the references there at least seem to have value to you.

For more examples of algorithms exploiting convex geometry, one place to look is the 'Bibliography and Remarks' subsections concluding each section (of each chapter!) of Jiri Matousek's book "Lectures on Discrete Geometry".

Another thing that gets cited a lot, and which seems to have topics for you (but I've never looked beyond the table of contents myself; Matousek on the other hand is .. in my other hand), is "Geometric algorithms and combinatorial optimization" by Grotschel, Lovasz, and Schrijver. (Yes, that Lovasz.)

I think these references have a lot for you so I'll move onto the next question.

Regarding Question 2.

While it is definitely true that convexity is powerful, I have not seen a comment like the one you seek, and I think people are very careful to communicate such a sentiment.

I have an anecdote on this.  One way people 'inject' convexity into problems is to simply.. approximate/model them with something convex.  (For example: replacing rank constraints with norms on the matrix, replacing integers (nonconvex and not even connected) with convex sets of reals.)  A go-to text for this stuff is Boyd & Vandenberghe's "Convex Optimization".  But once I was watching Boyd's videos, and someone gave him the "is convex = efficient" question, and he immediately said SVD.  Note that SVD can be written as a rank constrained minimization problem.  Anyway, my point is that even Boyd is very quick to correct a comment like this.

That said, I have a desire to share two places where I was personally surprised by convex structures (experts can roll their eyes and doze here).  The first are so called 'sum of squares' problems, which are minimization problems over nonconvex polynomials.  Thanks to the interpolation properties of polynomials, you can rewrite these as SDPs.  There are some beautiful course notes on this topic by Pablo Parrilo; you can find that and more info on his web page and some other info in this MO post by Noah Stein:
https://mathoverflow.net/questions/32533/is-all-non-convex-optimization-heuristic/32634#32634 .

Another beautiful place is in exponential families.  Now, this is all "obvious" once you realize these are solutions to max entropy (a convex optimization problem), but it's amazing how much convex structure informs the behavior of exponential families (a reference I like here is Wainwright and Jordan's book on graphical models).  This in turn gives one justification for some of the things people do with this sort of modeling.


Exact Algorithm for edge labeling problem in DAG

havent heard of this problem exactly in literature [maybe someone else has] however as a "nearby problem" it seems to me the minimum spanning tree would have useful properties to solve your problem. for example maybe generating two minimum spanning trees starting from the source vertex & the sync vertex, and propagating them outward until they touch, etc. might solve the problem or give a close answer. before anyone dings me on this here plz understand I am extending the idea of the MST somewhat to be generated starting from a given vertex [normally it starts from shortest edge in the entire graph]. if it doesnt work Id be curious for the reason.


Weird claim of graphclasses about complexity of domination

The culprit is the claim that Weighted-IDS is polynomial on claw-free graphs, because the independent set problem is and for domination perfect graphs, IDS is equivalent to IS. But for domination perfect graphs, IDS is not equivalent to IS, but to dominating set. So the statement should be: IDS is NPC on line graphs, because domination is.


Is the finite inverse semigroup isomorphism problem GI-complete?

Yes, the finite inverse semigroup isomorphism problem is GI-complete! This is a corollary of

  Theorem: Lattice isomorphism is isomorphism complete

from section 7.2 Lattices and Posets in

  Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo.

because a (semi-)lattice is also an (idempotent commutative) inverse semigroup.

Proof of theorem from technical report:

  It suffices to represent a graph uniquely as a lattice. Given a graph $G$ with $n$ vertices and $m$ edges, we define a lattice with an element for each vertex, an element for each edge, and two additional elements $\text{'}0\text{'}$ and $\text{'}1\text{'}$. Element $\text{'}1\text{'}$ dominates all others (the supremum), and element $\text{'}0\text{'}$ is dominated by all other elements (the infimum). An edge dominates exactly those vertices which are its endpoints. The result is a lattice which uniquely represents $G$.

The idea for this answer came from a discussion with vzn about sufficiently focused questions. The motivation to spend time on graph isomorphism at all also came from vzn's repeated prodding. J.-E. Pin asked in the comment whether there are any specific reasons to consider inverse semigroups. The idea was to have a structure slightly generalizing groups, which is GI complete. I wanted to better understand the relation between group isomorphism and graph isomorphism, but I fear this answer doesn't provide any insight of this sort.


VC dimension of polynomials (in one variable) of degree d

The basic method works like this: Assume your inequalities are of the form

$$ \sum_{i \le d} a_i x^i \le 0$$

Then you construct a lifting map to a space of higher dimension in which each monomial corresponds to one dimension. Now the polynomial can be expressed as a linear combination of the new dimensions and you can invoke the usual result for half spaces in the resulting space.

I'm not sure where you get your bound from: the correct expression for the VC dimension of polynomials in d variables of degree D is $\binom{d + D}{d}$, which is the number of monomials of degree at most D formed from d variables.


This is the weighted, non-bipartite generalization of the Max-Rep problem, which is equivalent to LabelCover-Max. See Page 20 of Kortsarz. As far as I know, the best approximation algorithm to that problem is $O(n^{1/3})$, due to Charikar, Hajiaghayi, and Karloff

In terms of approximation, the original Max-Rep problem and your generalization are similar. Up to a factor of $O(\log n)$, the weights can be taken care of by a standard bucketing argument. Up to a factor of $2$, the graph can be made bipartite by randomly assigning each cluster one of two sets (say $A$ or $B$) according to a fair coin toss, and removing any edges that go from $A$ to $B$. So this gives an immediate $O(n^{1/3} \log n)$ approximation algorithm, using the algorithm of CHK as a subroutine.

The previous hardness of $O(2^{\log^{1-\epsilon} n})$ carries through (again, see the Kortsarz paper for more details), and there are some conjectures out there that for some $\epsilon>0$, the problem is hard to approximate to within $O(n^{\epsilon})$.


Which algorithms have been proposed to learn the architecture of a deep neural network?

This predates the start of the "deep learning craze" in the mid-2000s, but for me the cascade correlation algorithm (Fahlman & Lebiere, 1989; pdf) is the build-your-own-topology NN algorithm. I am not sure how popular the algorithm is in ML now-a-days, but it is still popular in cognitive science despite it's unrealistic grounding in biology. If you want intersections with genetic algorithms (like the one @vzn points out with more recent examples) then that has been done with CC as well (Potter, 1992; pdf).

You might also find the following questions on other SEs to be of interest:

Why do neural networks seem to perform better with restrictions placed on their topology?
Dynamically adjusting NN architecture: inventing the unnecessary? (also on MetaOptimize)


The perceptron algorithm as such is a simple case of Gradient Descent (which is widely used for convex optimization). It minimizes a convex function (here the sum of inner products of misclassified examples with the current hypothesis) by making a step in the direction of the gradient of the convex function. As such perceptron is not necessarily an online learning algorithm.

There is however work on primal dual interpretations of online learning algorithms that seem to be relevant to you:

http://ttic.uchicago.edu/~shai/papers/ShalevSi07_mlj.pdf


for Question 1, the answer is Yes, and can be shown as follows.  (I will also be implicitly sketching an affirmative answer to Q4, since the argument is uniform and will treat all input lengths at once.)

Fix any NP-complete language $L$, and a family of good binary error-correcting codes (with rate 1/4 and correcting from a .1 fraction of errors, say).  Let $Enc_n: \{0, 1\}^n \rightarrow \{0, 1\}^{4n}$ be the encoding function for length $n$; we use some such code where $Enc = \{Enc_n\}$ is computable by a uniform polynomial-time algorithm.

Define $L'$ as the set of strings $z$ that are within distance at most $.05 |z|$ from a codeword $y \in Enc(L)$ encoding some element of $L$.  Note that $L'$ is in NP, as you can guess and check the nearby codeword, the decoded word, and the NP certificate for the decoded word's membership in $L$.

Then the claim is that any "approximation" of $L'$ in your sense is NP-hard for $\varepsilon = .01$.  For if we consider a valid codeword $y = Enc(x)$ of some length $4n$, then with probability $1 - o(1)$ over a random $\varepsilon$-perturbed version $y'$ of $y$, it will disagree with $y$ in at most a .05 fraction of coordinates, and will therefore disagree with any other codeword of $Enc_n$ in a more than $.05$ fraction of coords.  For such $y'$ we have $y' \in L'$ iff $x \in L$.  So if $h$ is any approximation to the $\varepsilon$-smoothed version of $L'$ in your sense, then we must have $h(y) = L(x)$.  As $Enc$ is efficiently computable, this gives us a way to efficiently reduce membership questions for $L$ to ones for $h$.  So $h$ is NP-hard.

Two notes:

(1) error-correcting encodings of NP instances have been used before in several papers, notably
D. Sivakumar: On Membership Comparable Sets. J. Comput. Syst. Sci. 59(2): 270-280 (1999).

(2) the argument above of course says nothing about the average-case complexity of any NP problem, since error-correction is being applied on an instance-by-instance basis.


Best approximations of Minimum Dominating Sets in chordal graphs

The best approximation ratio that can be achieved in polynomial time should be $\Theta(\log n)$ where $n$ is the number of vertices. This can be seen by standard reductions from the Set Cover problem which is NP-hard to approximate within a factor of $(1-\alpha)\cdot N$ where $N$ is the input size [1].
First, we use the standard reduction from Set Cover to Red Blue Dominating Set: Build a bipartite graph with a red and a blue side. The red side corresponds to the sets of the Set Cover instance and the blue side corresponds to the elements of the universe and an edge connects a set $S$ and an element $e$ if $S$ contains $e$. Now selecting a set of red vertices to dominate all blue vertices is the same as selecting the sets of the Set Cover instance to cover the universe. Hence, the reduction is approximation-preserving.
The bipartite graph is of course not chordal and we have a coloring of the vertices but we can now make the red side a clique and forget the vertex colors. We will never select a formerly blue vertex since the red vertices have larger neighborhoods. The resulting graph is a split graph and thus also a chordal graph.
Dana Moshkovitz: The Projection Games Conjecture and the NP-Hardness of $\ln n$-Approximating Set-Cover. Theory Comput. 11: 221-235 (2015)


Pseudorandom generators indistinguishable by uniform deterministic adversaries

Yes, this notion has been studied. One interesting aspect is that the two notions of pseudorandomness known to be equivalent under the usual adversaries, "next bit predictability" and "indistinguishability", do not seem to be equivalent for deterministic adversaries. (If they were, we would have complexity class separations.) Here are three references; I'm sure there are more.

O. Goldreich and A. Wigderson. On pseudorandomness with respect to deterministic observers

O. Goldreich. In a world of P=BPP

R. Williams. Towards NEXP versus BPP?


See this lower bound for sorting, for example:
http://planetmath.org/lowerboundforsorting

You typically need to assume something about the algorithm's access to the input data. In this case, the assumption is that the algorithm sorts via pairwise comparisons. Any such algorithm must make at least $\Omega(n\log n)$ such comparisons. This is because the pairwise comparisons effectively induce a binary tree on $n!$ leaves -- one leaf for each possible input ordering. Such a tree must have depth $\Theta(\log(n!))=\Theta(n\log n)$.

Note that in a different data access model, algorithms can achieve linear-time sorting:
https://en.wikipedia.org/wiki/Radix_sort

Obiously, faster than linear time is impossible, since you have to at least read all of the inputs.


Is $\mathsf{DTIME}(n^{O(\log n)})$ an interesting complexity class?

Quoting the complexity zoo:

QP: Quasipolynomial-Time
Equals DTIME(2polylog(n)).

QPLIN: Linear Quasipolynomial-Time
Equals DTIME(nO(log n)).
Has the same relationship to QP that E does to EXP.

Both these classes exist. I know that Quasipolynomial-time algorithms arise frequently in many areas. A google search will reveal several known quasipolynomial-time algorithms. Some of these may actually be QPLIN algorithms.
One of the advantages of QP over QPLIN is that it's more robust. For example, it is closed under composition, so if you have a quasipolynomial-time subroutine that takes an input of size $n$ to an input of size $n^{\log n}$ and now run a quasipolynomial-time algorithm on this new input, you will have an algorithm that runs in $O(n^{\textrm{polylog}(n)})$ time.


A variant of maximum matching: disjunctive constraints on the endpoints' degrees of edges in matching

The case of trees and a constant $c$ seems to admit a straightforward dynamic programming algorithm.

You root your tree arbitrarily. You will start from the leaf nodes and propagate information towards the root. You will keep track of the following pieces of information for each subtree; here $u$ is a node and $T(u)$ is the subtree rooted at $u$:

$M_1(u)$ = best matching in $T(u)$ if $u$ has unlimited capacity,
$M_2(u)$ = best matching in $T(u)$ if $u$ has capacity $c - 1$,
$M_3(u)$ = best matching in $T(u)$ if $u$ has capacity $c$.

Note that $M_1(u)$ and $M_2(u)$ can be extended by adding the edge $(v,u)$, where $v$ is the parent of $u$.

All of these values are trivial to compute for a leaf node. Once you have computed these values for all subtrees of a node $v$, you can compute them for $v$; let $C$ consist of the children of $v$:

$M_1(v)$: For each $u \in C$ of $v$ we take either $M_2(u) + (v,u)$ or $M_3(u)$, whichever is better.
$M_2(v)$: We check all subsets $S \subseteq C$ of size at most $c - 2$. For each child $u \in S$ we take $M_1(u) + (v,u)$ or $M_2(u) + (v,u)$, whichever is better. For each child $u \notin S$ we take $M_1(u)$, $M_2(u)$, or $M_3(u)$, whichever is best.
$M_3(v)$: Similar to $M_2(v)$, but we consider subsets of size at most $c - 1$.

Everything is polynomial if $c$ is a constant.


Computational complexity of modular power towers (tetration)

Sorry if this answer doesn't tell anything nontrivial, but you don't seem to imply these results in the questionm.

Consider first the problem of computing a modular exponentiation $ a^r \mod m $.

You say above that you can compute this by repeated squaring modulo $ m $, and that this needs $ O(\log r) $ multiplications.  This is true, and it's certainly a practical algorithm for some range of inputs.  But for other inputs, it's not the best you can do. The important case I want to talk about comes up when $ r $ is very large.

First, let $ c = gcd(a, m) $ and $ b = a/c $ and we'll compute the result as the product of the $ c^r \mod m $ and $ b^r \mod m $ values.  If $ \log_2 m < r $ then $ c^r \equiv 0 $, otherwise computer $ c^r $ by the simple algorithm with $ \log r $ multiplications.  Now we need a number $ s $ such that $ b^s \equiv 1 $, from which we can compute $ b^r $ as $ b^{r \mod s} $.  The Euler phi function $ s = \varphi(m) $ is such a number.  To compute $ s $, you need the integer factorization of $ m $, which takes $ O(m^\epsilon) $ time.

If the exponent $ r $ is so large that even $ \log r $ is significantly greater than $ m $, then reducing the exponent this way gives a faster method for the modular exponentiation.  Alternately, if you have a problem where the inputs are constrained so you always know the factorization of $ m $, such as if you take only prime or power of two exponents, then this method is worth already when $ r $ is significantly greater than $ m $.

This case of the faster method comes up when you want to evaluate an exponential tower $ a^{r^t} \mod m $, supposing $ t $ is significantly larger than $ m $.  For this, first compute $ s = \varphi(m) $ like above, then compute $ r^t \mod s $ by some modular exponentiation algorithm, then compute $ a^{r^t} $ as above.  As $ r^t $ is large, this is faster than the simple method of first computing $ r^t $ and then doing $ O(\log(r^t)) $ modular multiplications.  You can apply this to any exponential tower, thus recursively computing the exponential tower modulo $ m $.  If you have an exponential tower of at least four levels and the final exponent is of comparable size to $ m $, such as in a tetration, then it is very likely that the logarithm of final exponent will be much greater than $ m $, so again this method is worth to compute a tetration.


Complexity classes for proofs of knowledge

This is not an actual answer; I'm just sharing some results (which do not fit in one comment).

Goldreich, Micali and Wigderson (J. ACM, 1991) proved that every language in NP has a zero-knowledge proof of language membership (assuming OWFs exist). To this end, their presented a ZK proof for graph 3-colorability. Later, Bellare and Goldreich (CRYPTO '92) proved that this ZK proof is also a ZK proof of knowledge (PoK). Using Levin reductions (see footnote 12 of the former paper), Every language in NP has a ZK PoK (assuming OWFs exist).
Itoh and Sakurai (ASIACRYPT '91) have a paper on complexity-theoretic results regarding relations having constant-round ZK PoK.
This is a seemingly unrelated result, though I can't help noticing some similarities. I somehow feel (not anything formal) that proof of membership vs. proof of knowledge is similar to decision vs. search. Perhaps in this sense, one can also cite the work of Bellare and Goldwasser (J. Computing, 1994), where they (conditionally) prove that not all languages in NP have a reduction from search to decision.

Some open problems (perhaps solved, but not that I know of) regarding complexity-theoretic aspects of PoKs:

Various efficiency measures for ZK PoKs of a specific relation with certain complexity (e.g., a relation in AM):

Communication complexity of the proof
Computational complexity of the parties
Knowledge tightness (i.e., the ratio between the (expected) running time of the simulator and the running time of the verifier in the real interaction)

Complexity of relations admitting ZK PoK with certain limitations, say limited round complexities (Itoh and Sakurai only consider constant-round ZK PoK). Another example is when the prover is polynomial time: He cannot use the reduction to 3-colorability, as he cannot solve NP-complete relations. All NP-complete problems have a Cook reduction from search to decision. Yet, by Bellare-Goldwasser result cited above, such reductions do not necessarily exist for all NP languages/relations.
Other interesting results regarding PoKs which are not necessarily ZK, but whose knowledge complexity is otherwise limited. See Goldreich and Petrank (Comput. complex., 1999).

Before concluding, allow me to mention that there are actually several definitions for PoKs, some of which are cited below:

1) Early attempts: Feige, Fiat and Shamir (J. Cryptology, 1988), Tompa and Woll (FOCS 1987), and Feige and Shamir (STOC 1990).

2) De facto standard: Bellare and Goldreich (CRYPTO '92). This paper surveys the early attempts at defining PoKs, observes their shortcomings, and suggests a new definition which can be considered as "the" definition of PoK. This definition has a black-box nature (the knowledge extractor has black-box access to the cheating prover).

3) Conservative PoKs: Defined by Halevi and Micali (ePrint Archive: Report 1998/015), this definition augments the previous definition to guarantee prover feasibility. It also gives a definition for the knowledge of a single prover, which is good when answering the question "what does it mean to say that P knows something?"

4) Arguments of Knowledge with Non Black-Box Extraction: As mentioned above, the standard definition of PoKs is black box, which makes it impossible to have resettable zero-knowledge proofs (or arguments) of knowledge for non-trivial languages. Barak et al. (FOCS 2001) provide a non-black-box definition, which is based on (but differs from) the definition of Feige and Shamir (STOC 1990) cited above.


Security of message authentication codes and tag size

Theoretically, that is correct. Given your approach, the attacker needs to try $2^t/2$ tags on average, while to find the key, he needs to try $2^n/2$ keys on average. In CBC-MAC with AES-256, we have $t=128$. Therefore, the adversary needs to try about $2^{128}/2=2^{127}$ tags to find the correct one. While in this case the brute force needs much less effort than trying to break the key itself (which amounts to $2^{255}$ trial-and-errors), it is still far beyond the  current computing power of supercomputers.

It is worth noting that, we usually take any scheme whose best attack needs at least $2^{80}$ operations as secure. (I read this somewhere, but forgot the reference. Sorry!)


Is there an oracle that separates two complexity classes known to be equal?

We have IP = PSPACE = PPSPACE, where PPSPACE is the "probabilistic polynomial space," as defined by Papadimitriou's Games Against Nature.

However, relative to a random oracle O, we have IPO ≠ PSPACEO = PPSPACEO with probability 1. (See The Random Oracle Hypothesis is False.)

Another example: let the assumption be false; that is, if A=B the AO = BO for any oracle O and all complexity classes A and B. The contrapositive will say: If AO ≠ BO, then A ≠ B. Specially, since there exists an oracle O such that PO ≠ NPO, then P ≠ N, and a long-standing problem is solved!!!

Obviously, this reasoning has no basis, and I believe it can be refuted as such.

PS: When we use the "=" sign with respect to sets, we mean that every element of one set is also a member of the other set, and vice versa. However, the sets might have totally different definitions. In the axiomatic set theory, this is called the axiom of extensionality. The reason of "IP = PSPACE but IPO ≠ PSPACEO with probability 1 for a random oracle O" is exactly this: While IP and PSPACE are externally identical, their internal structure is quite different.


Stream fusion in total functional language

If all you have are are plain inductive and coinductive types, fusion is impossible, for the reason you point out.

However, it is possible if your type system supports sized types. These types let you track how big the elements of a type are. So you can use a coinductive representation, but instrument the type with size information, to guarantee that you can convert back to an inductive representation.
A reasonably gentle introduction to these ideas is in Hughes, Pareto and Sabry's paper Proving the Correctness of Reactive Systems Using Sized Types, and they have also recently been  implemented in Agda.


Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

I believe that the answer is as you suggest that no other asymptotics than $\Theta(1)$, $\Theta(\sqrt{n})$ and $\Theta(n)$ are possible. A promising route to prove this could be to apply the techniques from the paper which derives the $\Theta(\sqrt{n})$ asymptotics to the run trees of the regular language. Notice that a tree is accepted if there exists a run tree so it should be possible to first derive (using loc.cit.) the average height of a randomly generated run tree and take it from there, i.e. show that projecting away the states does not change the average height.


Finding max of two elements in linear time with restriction

Ok, so as I understand it, you are given as input an undirected graph (representing the "within range" restrictions) with weights on its vertices, and you want to find a non-adjacent pair of vertices that has maximum total weight. I'm going to interpret linear time as being linear in the number of edges in the input graph, not just the number of vertices, because otherwise it doesn't make sense — you need to have enough time to be able to look at the whole input.

Here's an $O(m+n)$ time solution (simplifying an earlier solution I posted here):

Assume for simplicity that $n$ is a power of two (if not round up).
Find the median of the vertex weights, the median of the highest $n/2$ vertex weights, the median of the highest $n/4$ vertex weights, etc. These median computations take a total of $O(n)$ time, and once completed they give you the set of $2^i$ largest weights for every choice of an integer $i$
For each vertex $v$ with degree $d_v$, let $i_v=\lceil\log_2(d_v+1)\rceil$. Form the pairs $(v,w)$ where $w$ is in the set of $2^{i_v}$ largest vertex weights found during the median calculations.
From the sets of pairs found in the previous step, remove the pairs that correspond to adjacent pairs of vertices (either by using a hash table of edges for fast adjacency lookup, or by using two passes of bucket sort to make a sorted list of both pairs and input edges).
The remaining pairs for each vertex $v$ necessarily include the heaviest nonadjacent neighbor of $v$. In particular the heaviest nonadjacent pair in the whole graph is somewhere in this list of pairs. Compute the weight for each pair and choose the max.


Here's a quote from this version which can be found on the author's page (emphasis mine):

  The term $(t)u$ should be thought of as “$t$ applied to $u$” ; it will also be denoted by $t u$ if there is no ambiguity ; the term $(\dots (((t)u_1)u_2)\dots)u_k$ will also be written $(t)u_1u_2\dots u_k$ or $tu_1u_2\dots u_k$. Thus, for example, $(t)uv$, $(tu)v$ and $tuv$ denote the same term.

I'd expect the "if there is no ambiguity" condition to also apply to the second notation (which is just the first notation applied $k-1$ times).


k-outerplanar graphs are subgraphs of bounded diameter planar graphs? of bounded diameter bounded genus graphs?

No: see the nested triangles graph. It has bounded treewidth (more strongly, bounded pathwidth and bandwidth) but cannot be augmented to have bounded diameter while preserving planarity.


What are some careers in theoretical computer science that do not require a PhD?

I work at a national lab and in a directorate that employs many theoretical computer scientists, of which some do not have PhDs.

I think that what would differentiate or establish you would be a quality of your work.
If you are a talented theoretician, strong at algorithms and you can/have been publishing your work in reputable theoretical computer science journals then I do not see why place like national lab would not hire you.

PhD is a testimony of ones ability to pursue relevant and significant research on his or her own.


I'm not sure if this is what you're looking for, but people have studied consistency of surrogate risk minimization. There, we define a surrogate loss function $L$ and a link $\psi$. We first minimize surrogate loss on our dataset, yielding some surrogate hypothesis $h$. Then we define $f(x) = \psi(h(x))$. This procedure is roughly consistent if, as data $\to \infty$, we have $f \to f^*$.
The question is, given e.g. $C$, what are some nice, consistent surrogate losses? Example: for binary $0-1$ loss, one can use hinge loss or logistic loss as a surrogate, and one can show this is consistent as long as the hypothesis class is rich enough.
Tewari and Bartlett (2007) study multiclass classification, but I think not cost-sensitive, and relate consistency to calibration. A more recent work is Agarwal and Agarwal (2015), which has some more references.
[1] Tewari, Bartlett. On the Consistency of Multiclass Classification Methods. JMLR 2007. https://www.jmlr.org/papers/volume8/tewari07a/tewari07a.pdf
[2] A. Agarwal, S. Agarwal. On consistent surrogate risk minimization and property elicitation. COLT 2015. http://proceedings.mlr.press/v40/Agarwal15.pdf


How many different Huffman encoding for a given number of symbols

The answer is $C_{n-1} n!$ . That is, the $(n-1)$st Catalan number times $n$ factorial.

There are $C_{n-1}$ ways of making a complete binary tree with $n$ leaves, and there are $n!$ ways of assigning these leaves to the symbols to get a Huffman code.

This sequence goes 2, 12, 120, 1680, 30240, and is listed in the Online Encyclopedia of Integer Sequences as Quadruple Factorial Numbers, with a simpler formula than I give above.

The above argument shows that the quadruple factorial numbers give the number of ways of assigning $n$ symbols to codewords in a complete binary prefix code. It's not hard to show that you can assign probabilities to the symbols to make this encoding optimal (so it satisfies the definition of a Huffman code). It's not clear that a given Huffman coding algorithm will generate all of these, however.


Active learning for inferring a convex optimization formulation

Those are some very technical terms to be throwing around and although I'm familiar with some of the literature from either side, I don't think that I've ever seen them used together. What is the distinction between using a convex program and an LP? They are significantly different, and you refer to both in your question. What you are mentioning sounds really similar to cutting plane or column generation methods in optimization, so perhaps you want to check those out and see if any active learning approaches have been used. In most cutting plane methods, there is usually an efficient (but ad hoc) way to search for violated constraints, usually found by an optimization subproblem; that could be considered similar to active learning but I'm not sure how a canonical active learning approach would look different.


Conclusions from reverse mathematical strength of graph minor theorem

I am not sure I understood your question, but if you are asking how difficult it is to compute the set of obstructions, you may be interested in the following http://www.jucs.org/doi?doi=10.3217/jucs-003-11-1194 where the non computabubility is proved even if the graph class is MSOL-definable. In this paper http://www.sciencedirect.com/science/article/pii/S0012365X97830798?via%3Dihub the computability is proved when the graph class is given by the HR grammar.


What is considered significant when applying for a TCS PhD with major changed

If you're currently a masters student in CS, then a lot of your 'switched major' issues have already gone away. the main concern in applying for a Ph.D in TCS is if you have sufficient mathematical background, as well as background in algorithms. If your MS program experience can demonstrate this, and you also can demonstrate mathematical expertise via your paper in combinatorics, then that concern goes away.

But admissions decisions are multivariate and stochastic. Maybe the right question is whether you have the right background to succeed, and there are answers regarding what constitutes the right background (on mathematical background). Also see this on how to prepare for a TCS advanced degree.


Book recommendations for CompSci related math

I am not only searching for a book, but also an approach of how to learn matc without pain on my own.

If you learn best from and/or enjoy a good lecture, your best bet is probably the MIT open courseware lectures. They have Calculus, multiple versions of Linear Algebra

  I am still going to "Gymnasium", the german counterpart to the high school

Unsurprising, MIT open courseware also has an excellent collection of canonical CS courses that will be helpful for gaining background in CS theory for the high schooler. I worked through the Structure and Interpretation lectures my Junior year of high school, and that was definitely worth the time. There is also an Introduction to Algorithms course.

Of course, there is also a course on exactly what you want -- Math for CS -- but there are no video lectures.

See here: http://ocw.mit.edu/courses/#electrical-engineering-and-computer-science


Major mistakes in accepted FOCS/STOC papers

One case is Blum-Feldman-Micali's STOC '88 paper. The flaw was pointed to them by Mihir Bellare (private communication). You can find the relevant discussion here.
The Petri net reachability problem has a rich history where incomplete or flawed proofs later lead to new results.  G.S. Sacerdote and R.L. Tenney presented an incomplete decidability proof at STOC '77, which was however instrumental in the later proof of E.W. Mayr at STOC '81 and its improvement by S.R. Kosaraju at STOC '82.  These decidability proofs did not come with complexity upper bounds (they employ well quasi-orderings for termination).  Z. Bouziane later claimed to have found a 2ExpSpace algorithm at FOCS '98.  A flaw was pointed by P. Jančar (and finally published in a note), but Bouziane's work has helped renewing the interest into this old question.  Although there are still no known upper bounds on the complexity of this problem, J. Leroux has recently presented a new decidability proof at POPL '11.

Not in STOC/FOCS:

Another case happened in Structure in Complexity Theory (1988) conference (If I'm not mistaken, it's now called Conference on Computational Complexity.) The paper's title was On the power of multi-power interactive protocols. Two years later, the authors (Fortnow, Rompel, and Sipser) published a two-page paper "Errata for On the Power of Multi-Prover Interactive Protocols" in the same conference. Unfortunately, IEEE does not offer this paper for download.


I don't know about whether this specific problem has been studied before but I can point you to a general class of problems that include it and that have been studied: This looks like an LP-type problem (or perhaps even a low-dimensional linear program although I am not quite seeing how to coordinatize it so that works). If so it can be solved by a linear-time combinatorial algorithm.

To set this up as an LP-type problem, we need an objective function mapping sets of line segments to some totally ordered set of solution values. The obvious objective function to use here is the numerical value $l$ that you're trying to optimize (the length of the longest split segment), but I think that's not quite good enough. Instead you should use a lexicographic combination of $l$ with the coordinate vector of a line achieving value $l$. With this lexicographic combination, the problem automatically satisfies the monotonicity and locality properties of LP-type problems: adding another segment to an instance only makes its solution worse, and if a given line is the solution to two sets $A\subset B$ of segments, and adding a new segment $x$ to $A$ doesn't change the solution (because the line cuts $x$ in pieces shorter than $l$) then adding $x$ to $B$ also doesn't change the solution (because the same line cuts $x$ in the same way).

So the main remaining question is whether this problem has bounded dimension, where the dimension of an LP-type problem is defined as the largest size of a minimal instance with a given solution value. So, in any problem of this type, is there a subset of a constant number of the line segments that has the same solution as the whole problem? I think the answer must be yes, because the optimal line must cross some three segments at points that are at distance $l$ from the ends of their segments (else it could be moved continuously to a better solution) and those three segments should determine the solution value.


What is the probability that a random Boolean function has a trivial automorphism group?

Yes. To your first question, the probability goes to zero double-exponentially fast. This can be calculated as follows. For each permutation $\pi$, we can bound the probability that $\pi \in Aut(f)$, i.e. that $f(\pi(x)) = f(x)$ for all $x \in \{0,1\}^n$. Consider the orbits of $\pi$ acting on $\{0,1\}^n$. We have that $\pi$ is an automorphism of $f$ iff $f$ is constant on the $\pi$-orbits. If $\pi$ is nontrivial, it has at least one orbit on $[n]$ that is not a singleton, and therefore at least on orbit on $\{0,1\}^n$ that is not a singleton. Suppose that orbit has $k$ elements in it. The probability that $f$ is constant on that orbit is thus precisely $2^{-(k-1)}$. Suppose that $\pi$ acting on $[n]$ has $c_1$ fixed points, $c_2$ cycles of length 2, etc. (in particular $\sum_{i=1}^n i c_i = n$). Then the number of points of $\{0,1\}^n$ fixed by $\pi$ is precisely $2^{\sum_i c_i}$. All the remaining points of $\{0,1\}^n$ are in nontrivial orbits of $\pi$. To upper bound the probability that $\pi \in Aut(f)$, note that the best possibility is if all the non-fixed elements of $\{0,1\}^n$ come in orbits of size 2. So we get that $Pr(\pi \in Aut(f)) \leq (1/2)^{M/2}$ where $M = 2^n - 2^{\sum_i c_i}$. Now, we want a lower bound on $M$, which means we want an upper bound on $\sum_i c_i$. Since $\pi \neq 1$, the largest $\sum c_i$ can be is when $c_1 = n-2$ and $c_2 = 1$, i.e. $\sum c_i = n-1$ and $M = 2^n - 2^{n-1} = 2^{n-1}$, so $M \geq 2^{n-1}$ and $Pr(\pi \in Aut(f)) \leq (1/2)^{2^{n-2}}$. Now apply the union bound: $|S_n| = n!$, so $Pr((\exists \pi \in S_n)[\pi \neq 1 \text{ and } \pi \in Aut(f)]) \leq n! 2^{-2^{n-2}}$, which is basically $2^{n \lg n - 2^{n-2}} \to 0$ as $n \to \infty$, pretty quickly.

For any given $G \leq S_n$ you could use similar reasoning, but the probability will also go to zero very quickly.


Misunderstanding the Church-Turing thesis?

The fields of philosophy and CS apparently have different definitions/interpretations of the thesis. In CS, I believe it is standard/accepted to define the Church-Turing thesis as the article's "Misunderstandings" section's "Thesis M" (under the narrow/worldly view). However, the article claims that this is an incorrect definition of Church-Turing. So we simply disagree. (And let's try to avoid starting an argument with them about it ... pointless arguments are their forte, after all.)

The approach taken by philosophers is unfortunate, as the average layman is probably interested in the CS Church-Turing thesis, not the philosophy one espoused in the article. So they will cite the article while thinking it refers to our practical/reasonable definition, when it doesn't.

So my answers to your specific questions:

Yes, as far as I can tell.
I'd tell them that the article refers to a highly specialized philosophy-definition of Church-Turing. But regardless of what one calls the "true" Church-Turing thesis, the following thesis is almost universally believed among computer scientists: "Any usable machine of computation that can be built in this universe can be simulated by a Turing Machine".
If by hypercomputation you mean physically possible/realizable, then no, it's not taken seriously. But it is interesting to study hypercomputation models even if they cannot appear in the real world, and we do so all the time. For instance, we may consider a Turing Machine that has access to an oracle that solves the halting problem. This object is studied all the time in theory and is uncontroversial, but nobody believes that one can actually be built.


Background Required to understand Quantum Monte Carlo techniques?

Do you have a tame physicist (preferably one who is familiar with Quantum Monte Carlo techniques) that you can talk to?  I don't think it's actually all that hard, but if you try to understand it by reading about it, I strongly suspect that you'll find the books all assume you understand some moderately advanced quantum mechanics/quantum field theory (time-ordered integrals, some non-obvious properties of operators) which they don't explain, and if you don't understand these, you'll find their explanations completely incomprehensible.

I also see from Google that there are lots of different variations on the Quantum Monte Carlo method, some of which will be harder than others, and deciding which one to use for a particular problem is very likely a skilled art.


Is set packing easier when the sets are squares?

I think your problem is NP-complete already for M=3, as there is a quite straight-forward reduction to it from 3SAT. Just for each variable xi, make a pair of squares, truei and falsei. For a clause Cj, make a pair of squares for each of its literals, e.g., Aj1, Bj1, Aj2, Bj2, Aj3, Bj3. Let Aj1 intersect the respective square of the variable (e.g., truei) (but disjoint from any other similar clause-squares intersecting it), while the Bj1, Bj2 and Bj3 are put somewhere in a disjoint way. Finally, for each clause we have a collection of three squares, which is also Bj1, Bj2 and Bj3.


NP-complete problems with optimal approximation in poly-time

One example is the chromatic index (edge-coloring number) of undirected graphs. By Vizing's theorem, the chromatic index either equals the max-degree $\Delta$ or equals $\Delta+1$.

Vizing's proof gives a polynomial time (inductive) procedure for finding a coloring with $\Delta+1$ colors.
Holyer has proved that deciding whether the chromatic index equals $\Delta$ is NP-complete.


What is the axiomatic (set theory) context of the P vs NP and NP=EXPTIME conjectures?

It's not specified. When there is a serious enough candidate paper purporting to resolve P ≟ NP, a Special Advisory Committee will be formed to decide whether (and to whom) to award the prize. I presume that the Special Advisory Committee will decide whether your system of axioms is acceptable. If you assume Z-F with choice, I guarantee you they will take it. If you assume P ≠ NP as an axiom, I guarantee you they won't.


Shouldn't relativisation contain consistency proof ?

Whether or not $P^{A,B}$ equals $NP^{A,B}$ is going on the particular oracle languages A and B that you are using.  Iirc, in the BGS paper the language A is TQBF (or any other PSPACE-complete language).  The language B, somewhat ironically, is actually defined via a diagonalization construction.  Now, if you use the construction from the paper and apply it to TMs with an A oracle, then the resulting language B will be such that $P^{A,B} \ne NP^{A,B}$.  On the other hand, if you stick with the original language B from the paper, it will depend on the details of B's construction.  If B is in PSPACE (I don't know offhand if it is or not), then a TM with an A oracle could simulate any queries to B, and you should have $P^{A,B} = NP^{A,B}$.

The bottom line, though, is that this has nothing to do with consistency--it is just a technical question about the specific oracle languages A and B (and you could get different answers depending on the particular choices of A and B that you use).


Compactly representing the solution set of a SAT instance

As stated (revision 3), the question has a simple answer: no.

The reason is that even for the highly restricted class of representations given by Boolean circuits with AND, OR, and NOT gates, no nontrivial lower bounds are known.  (Clearly a circuit that represents $F$ will also represent $S$ implicitly, and it is easy to enumerate the solutions by changing the inputs to the circuit.)

For even more restricted representations, like monotone or constant depth circuits, exponential lower bounds are known.  There are also exponential lower bounds for representing formulas in CNF or DNF form, although these can be seen as special cases of constant depth circuits.  Finally, BDD representations can be seen as compact forms of DNF, but there exist formulas for which the BDD requires exponential size for any variable ordering.

To make your question more precise, please consider @Joshua's answer in some detail, and please clarify what you mean by "trivial to enumerate every single solution".

For revision 4, note the statement about BDD size.  Part of what you seem to be asking is: is there a more compact representation of DNF formulas than BDDs?  Let "BDD $B$ has superpolynomial size" mean "every BDD representing the same function as $B$, regardless of variable ordering, has superpolynomial size", and let "nice representation" mean "a representation that allows solutions to be enumerated with polynomial delay".  This more specific question then becomes:

  is there a family of formulas and a nice representation that has polynomial size while its BDDs have superpolynomial size?

Does this capture the essence of what you are asking?


Quantum annealing vs adiabatic quantum computation

Adiabatic quantum computing (AQC) is a computational model (as Peter said in the comments). Compare AQC with other models of computation such as:

circuit-based quantum computing (CBQC)
Adleman-Lipton model (a model for computing using DNA)
Turing machine model (a model where computations are done with symbols on a tape)

One can devise algorithms using the AQC model, such as this algorithm for factoring integers: http://arxiv.org/abs/1411.6758.

Quantum annealing is a physical process which attempts to implement such algorithms. Start with a set of quantum states, and a time-dependent Hamiltonian $H(t)$ such that the ground state of $H(t_F)$ at a final time $t_F$, encodes the solution to your problem. Let the states evolve according to $H(t)$, and hope that in the end one of the candidate states ends up in the ground state of $H(t_F)$.

If you're lucky enough to have a qubit that starts in the ground state of $H(0)$, and $H(0)$ evolves into $H(t_F)$ slowly enough, then according to the "adiabatic theorem", the qubit always remains in the ground state of $H(t)$ for all $t$, and you are guaranteed to get the right answer which is encoded in the ground state of $H(t_F)$. This is what the AQC model has in mind, but since it is experimentally difficult to start in the ground state, we sometimes try to implement AQC algorithms using quantum annealing, which unfortunately might not end up in the ground state.


Is it decidable whether the langauge accepted by a reversal-bounded counter machine is deterministic?

I found a similar argument for context-free languages, which can be used here.
It is not decidable, since universality for non-deterministic reversal-bounded multicounter machines is undecidable, but becomes decidable for the deterministic version.

Suppose we can decide if $M$ can be determinized, and perform the determinization if it can.
Then we can decide if $L(M) = \Sigma^*$ as follows:

If $M$ cannot be determinized, then clearly it is not universal, since there is a deterministic machine accepting $\Sigma^*$.
If $M$ can be determinized, then we determinize it and test if it is universal.

This question on CS.SE give the analogous argument for CFL vs. DCFL.


Computing sum of sparse polynomials squared in O(n log n) time?

Squaring a polynomial with $x_i$ nonzero coefficients takes time $O(x_i^2)$ using ordinary term-by-term multiplication, so this should be preferred to the FFT for those polynomials where $x_i < \sqrt{n \log n}$.  If $\sum_i x_i = n$, then the number of polynomials with $x_i$ greater than $\sqrt{n \log n}$ is $O(\sqrt{n / \log n})$, and these will take time $O(n^{3/2}({\log n})^{1/2})$ to square and combine (as will the remaining polynomials).  This is an improvement over the obvious $O(m n \log n)$ bound when $m$ is $\Theta(\sqrt{n / \log n})$.


Why go to theoretical computer science/research?

I can relate my reasons as an undergraduate applying to TCS graduate programs this upcoming Winter (so little time left!).

There's the beauty. This isn't something I can explain (and have witnessed other mathematicians failing to explain). It's like "yellow." If you haven't seen it, I'm not sure I could communicate to you what it is. But since you've become interested in theory, I suppose maybe you do experience it.
There's universality. Universality beyond the Church-Turing Thesis. TCS at it's core investigates high level and low level phenomena in information - it's the "physics" of information. And since information is qualitatively atomic, information theory does have things to say about physics (my QM professor has specifically told me he loves information theory). All of this being said, it's somewhere between Pure Math and Engineering. It has the capability and flexibility to contribute directly to both, and to be contributed to directly by both. Still, it fights on its own frontier.
There's the scope. This was hinted at in the previous bullet. Informatics finds its way into many different applications - stuff everyone from the DHD to startups are interested in. You won't find yourself as starving for funding like Pure Mathematics. (You'll still always find yourself starving for funding.)
There's the challenge. Take a look at a list of open problems in Theoretical Computer Science (and pursue an understanding of them to the end of inquiry). They are very hard - here are some reasons why. We really don't understand TCS - most of our proofs boil down to mounting evidence. There's just so much work left to do!


Bivariate low-degree polynomial testing of Polishchuk-Spielman

If I understand it correctly, Gauss's lemma implies that that $P$ and $E$ have a non-trivial common factor over $\mathbb{F}[x,y]$.

But in the beginning of the proof of Lemma 8 they assume without loss of generality that $P$ and $E$ do not have a common factor. More specifically, they show that if $P$ and $E$ have a common factor then they can use induction to show that $E$ divides $P$.


Remove specific edge from ST (link-cut) tree

For any edge $(u,v)$ either $u$ is $v$'s parent or vice versa. So you just call CUT for "deeper" vertex.

UPD: To determine which vertex is deeper you can use Access($v$). If after this operation $u$ is a rightmost node of $v$'s left (path)subtree, then $u$ is $v$'s parent and you can call CUT($v$) (or just $\mbox{left}(v) \gets \mbox{Null}$ because Access($v$) was called before). Else you call CUT($u$).


Beigel-Tarui transformation of ACC cricuits

Isn't the probability of $\Sigma_{i:h (i) =1}  x_{i} \mbox{mod }  2 = 1$ at least 1/2 ? It seems that $1/(10k)$ is a weak lower bound.

In fact the answer is no. (It would be that $\Sigma_{i:h (i) =1}  x_{i} \mbox{mod }  2 = 1$ holds with probability at least $1/2-\varepsilon$, if we were working with an $\varepsilon$-biased hash family, and indeed using $\varepsilon$-biased hash functions gives a way to improve the parameters of the construction. But pairwise independence is not necessarily $\varepsilon$-biased.)

It seems they are missing one additional step here. To apply Valiant-Vazirani directly, you would need to also randomly choose the range of the hash function. Rather than picking random pairwise-independent $h : [2^k]\rightarrow\{0,1\}$, it seems you should pick random $\ell \in \{2,\ldots,k+1\}$ and then pick random pairwise-independent $h : [2^k]\rightarrow \{0,1\}^{\ell}$. (Here I am deliberately using Arora-Barak's statement of Valiant-Vazirani, found on page 354.)
 Let $s$ be the number of $x_i=1$. Valiant-Vazirani says that when you have chosen $\ell$ such that $2^{\ell-2} \leq s \leq 2^{\ell-1}$, then the probability that $\Sigma_{i:h (i) =1}  x_{i} = 1$ (over the integers!) is at least $1/8$.

So by picking random $\ell$ and picking random pairwise independent $h: [2^k]\rightarrow\{0,1\}^{\ell}$, then you have probability at least $1/(8k)$ that $\Sigma_{i:h (i) =1}  x_{i} \mbox{mod } 2 = 1$. To simulate the random choice of $\ell$ in the circuit, you could simply take the $OR$ over all possible $\ell$ (their number is logarithmic in $2^k$, after all), so the probability of success becomes at least $1/8$ again. So rather than having $O(k\log s)$ hash functions with range $\{0,1\}$, you'll want $O(k)$ different sets of hash functions (each set having a different range), with $O(\log s)$ hash functions in each set.

  Why does this replacement give an equivalent SYM+ circuit ?

A SYM of AND (i.e, SYM+) circuit of size $K$ is essentially equivalent to having a multivariate polynomial $h : \{0,1\}^n \rightarrow \{0,\ldots,K\}$ with at most $K$ monomials, a lookup table $g : \{0,\ldots,K\}\rightarrow \{0,1\}$, and computing $g(h(x_1,\ldots,x_n))$. (For instance, a proof can be found in Beigel-Tarui.) The intuition is that each monomial in $f$ is an AND gate, and $g$ is the SYM gate. I say "essentially equivalent" because the multilinear polynomial $h$ could also have negative coefficients for some terms, and negative coefficents are not obviously implementable in SYM of AND. But I claim (and Beigel and Tarui claim) that this is not a problem. Think about it :)


I assume the generalization you are thinking of is the following:

Given value $d$, and values $s_i$ and $r_i$ for $i = 1,2,...,k$, find (if possible) an $\alpha$ such that
$$\sum_{i = 1}^k\min(r_i, s_i\alpha) = d$$

Consider the expression $\min(r_i, s_i\alpha)$. This expression is sometimes equal to $r_i$ and sometimes equal to $s_i\alpha$, with a threshold between these two behaviors at $\alpha = \frac{r_i}{s_i}$.

Then consider the $k$ thresholds of this form for the $k$ different $\min(r_i, s_i\alpha)$ expressions. These thresholds separate the number line into $k+1$ sections. In each section, the behavior of each $\min(r_i, s_i\alpha)$ expression is known. Therefore, we can rewrite the expression $\sum_{i = 1}^k\min(r_i, s_i\alpha)$ for each section without the $\min$s. Then in each section we get an expression of the form $a+b\alpha = d$ which we can solve for $\alpha$; if in any section we find a value $\alpha$ that is both a solution to the equation in that section and a value within the section of the number line, then that $\alpha$ solves the whole problem.

Another way of thinking about this is in terms of your idea of trying every combination of which expressions the $\min$s evaluate to. If you do it by brute force, you have to try exponentially many cases, but using the idea of these threshold values it is possible to narrow down the possibilities to just $k+1$ cases.


Covering only one of two types of objects in a cartesian space using minimum number of rectangles

This sounds like the minimum rectangle cover problem.

  Given an orthogonal polygon with holes, find the minimum number of
  rectangles needed to cover the interior of the polygon without
  covering any of the holes.

In your case, the red points mark the holes, and the blue points mark the interior of the polygon(s). In general, two blue regions might be disconnected, but then the minimum equals the sum of the minimum covers for the two disconnected regions.

Your problem can be easily mapped to the rectangle cover problem, and conversely the rectangle cover problem can be mapped to your problem assuming that all vertices of the polygon are on a grid, which can be assumed w.lo.g.

The bad news is that the minimum rectangle cover is NP-hard. It's also fairly hard to approximate in general (the best current approximation ratio is $O(\sqrt{\log n})$. However, if you had more information about the red and blue points, it's possible you might fall into one of the many special cases of rectangle cover that are easier to solve.


Are there digraphs such that any two arborescences are arc-disjoint?

Leaving aside the trivial case (graphs which only have one $r$-arborescence), this won't be possible.

Suppose $(V,E)$ is an $r$-arborescence of $(V,A)$. Then $E$ contains some (nonzero) number of arcs $(r,s_1),\ldots,(r,s_k)$ out of the root (otherwise we are in a trivial case). Now if $(V,F)$ is another arborescence, then either

$F$ also contains some $(r,s_i)$, so the arborescences are not arc-disjoint, or
$F$ contains $(r,t)$ for some $t\notin\{s_1,\ldots,s_k\}$, and for each $i$, an arc $(p_i,s_i)$ for some (not necessarily distinct) vertices $p_1,\ldots,p_k\neq r$. But then we can replace one such arc with $(r,s_i)$ - it is easy to see that $(V,F\cup\{(r,s_i)\}\setminus\{(p_i,s_i)\})$ is again an $r$-arborescence: For any vertex $v$ in the subtree of $(V,F)$ rooted at $s_i$, the only path from $r$ to $v$ is now the old one, with the prefix up to $s_i$ replaced by $(r,s_i)$; for all other vertices, the paths remain unchanged. This new arborescence is distinct from $(V,E)$ since it still contains $(r,t)$, but they are not arc-disjoint since they both contain $(r,s_i)$.


Exercises of polynomial and turing reductions

A good start is Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson. Chapter 3.2 discusses techniques and 3.3 has exercises. You can find more in the books about complexity everyone should read.


Optimality of Greedy algorithm for minimization Knapsack Problem

I didn't understand the question very well, but I think you're asking about the ratio of the greedy solution to the optimal solution when the problem instances are taken out of a certain probability distribution. I don't have a theoretic solution to this problem, but if you need the answer for practical reasons, then I think a Monte-Carlo simulation would give reliable results.  You can approximate knapsack to the desired precision using the well-known dynamic programming algorithm to obtain an approximate value of the optimal solution and then compare it to the greedy algorithm. You generate a number of random instances, and see where the ratio usually falls.
In order to have more reliable estimates, you can establish confidence intervals for the fraction of instances whose greedy/optimal ratio falls within a given interval, etc.


Finding balanced disjoint cycles in bridgeless cubic graphs

This is NP-complete; reduction from the question, "Does a 2-edge-connected cubic graph $H$ contain a Hamiltonian cycle avoiding a given edge $e$?"

Construct $G$ as follows.  Take two copies of $H-e$, denoting the endpoints of $e$ in the first copy $v_1$, $u_1$ and denoting the endpoints of $e$ in the second copy $v_2$, $u_2$.  Add edges $e_v$ between $v_1$ and $v_2$, and $e_u$ between $u_1$ and $u_2$.  Observe that $G$ is 2-edge-connected.

Any cycle of $G$ contains both or neither of $e_v$ and $e_u$, since these edges form an edge cut.  Thus if $G$ has two vertex-disjoint cycles of length $|V(H)|$, they must each lie in a separate copy of $H$.  Such cycles exist precisely if $H$ contains a Hamiltonian cycle avoiding $e$.

Edit: Am I missing something obvious, or is the question of finding a good perfect matching clearly equivalent to finding the two long cycles?


Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

This problem generalizes dominating set: given an unweighted graph, there exists a set of k centers such that all other vertices are at distance 1 from them if and only if there exists a dominating set of size k.

Dominating set is hard to approximate with a ratio better than $\ln n$. In the above observation the optimal value for the k-center problem is either 1 or at least 2. Let $A$ be a $(c,2-\epsilon)$ bi-criteria approximation for $k$-center for some $c < \ln n$. If a dominating set of size $k$ exists, then the corresponding $k$-center problem would have optimum cost of 1, and $A$ would return a solution of cost at most $2-\epsilon$ using at most $k \ln n$ centers. Thus, $A$ can be used to find a $\ln n$ approximation for dominating set, which is known to be not possible. Therefore, I think that no $(c,2-\epsilon)$ bi-criteria approximation can exist for $c<\ln n$.


Is the following graph optimization problem approximable within a constant factor?

The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. For brevity, let me call you problem $\cal P$ and Min Uncut $\cal U$.
Observation. An instance $G$ of $\cal P$ has a solution of cost 0 if and only if $G$ is bipartite.
Proof: Assume that $G$ is bipartite with parts $L$ and $R$. Consider $\pi$ that first puts the vertices from $L$ and then the vertices from $R$ (the relative ordering of vertices in $L$ and $R$ may be arbitrary). Then the cost of this solution is $0$, as required.
Now assume that $G$ has a solution $\pi$ of cost $0$. Note that $G$ cannot have an odd cycle. Indeed if $a_1  \to a_2 \to \dots \to a_k$ is an odd cycle, then the direction of edges along the cycle should alternate: say $(a_1, a_2)$ goes forward (w.r.t. $\pi$), then $(a_2, a_3)$ goes backward, then $(a_3, a_4)$ goes forward etc (or the other way around). That is impossible since the cycle is odd. We conclude that $G$ doesn't have any odd cycles and thus is bipartite.
QED
Claim. Let $G$ be a regular graph, whose vertices have degree $d$. Denote the costs of optimal solutions of problems $\cal U$ and $\cal P$ in $G$ by $U_G$ and $P_G$, respectively. Then
$$P_G =\Theta(d\cdot U_G).$$
Proof: Let $E'$ be an optimal solution for $\cal U$ in $G$. Then $|E'| = U_G$. Let $(L, R)$ be a bipartition of $G - E'$. Consider a permutation $\pi$ defined by $L$ and $R$, as in the proof of Observation. The cost of $\pi$ is at most $d \cdot |E'| = d\cdot U_G$ (to get this, write the formula for the cost of $\pi$; upper bound $|\mathrm{succ}_{\pi}(u)|$ by $d$ for vertices in $L$; upper bound $|\mathrm{pred}_{\pi}(u)|$ by $d$ for vertices in $R$). Thus, $P_G \leq d\cdot U_G$.
Now consider an optimal solution $\pi$ for $\cal P$. For every vertex $u$, either $|\mathrm{pred}_{\pi}(u)| \leq d/2$ or $|\mathrm{succ}_{\pi}(u)| \leq d/2$. In the former case, mark edges from $u$ to $\mathrm{pred}_{\pi}(u)$ as bad; in the latter case, mark edges from $u$ to $\mathrm{succ}_{\pi}(u)$ as bad. Note that when we process $u$, we mark $\min(|\mathrm{pred}_{\pi}(u)|, |\mathrm{succ}_{\pi}(u)|)$ edges. We have,
$$\min(|\mathrm{pred}_{\pi}(u)|, |\mathrm{succ}_{\pi}(u)|) \leq |\mathrm{pred}_{\pi}(u)| \times |\mathrm{succ}_{\pi}(u)| / (d/2).$$
Adding up this inequality over all $u$, we get that the total number of bad edges is at most $2P_G/d$. Now let $E'$ be the set of bad edges. Clearly, $P_{G- E'} = 0$. From Observation, we get that $G-E'$ is bipartite. Thus, $E'$ is a feasible solution for $\cal U$. We conclude that $U_G \leq 2P_G/d$.
We have proved that
$$\frac{d}{2} U_G \leq P_G \leq d\cdot U_G.$$
QED
We see that in regular graphs, $\cal P$ and $\cal U$ are essentially equivalent. Note that it was shown in

Chawla, Shuchi, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D.
Sivakumar. "On the hardness of approximating Multicut and
Sparsest-cut." Computational Complexity 15, no. 2 (2006): 94-114.

that there is no constant factor approximation for $\cal U$ if the Unique Games Conjecture holds. On the other hand, there is an $O(\sqrt{\log n})$ approximation algorithm for $\cal U$; see

Agarwal, Amit, Moses Charikar, Konstantin Makarychev, and Yury
Makarychev. "$O(\sqrt{\log n})$ approximation algorithms for Min UnCut, Min
2CNF Deletion, and directed cut problems." In Proceedings of STOC 2005, pp. 573-581.

What about the regularity assumption?
The regularity assumption is not really necessary and was made above to simplify the exposition.
Hardness of approximation. We can start with any (not necessarily regular) instance $G = (V, E)$ of $\cal U$. Let $d$ be the maximum degree of $G$. Attach $d - \deg u$ new vertices to every vertex $u\in V$. We will obtain a new graph $G' = (V', E')$, in which every vertex has degree $d$ or $1$. Clearly, $U_{G} = U_{G'}$. Now we apply the reduction from Claim to $G'$. It's easy to see that the reduction still works for $G'$, even though it's not regular (since $\deg u\in\{1, d\}$ for every $u$).
Algorithm. Given an instance $G = (V, E)$ of $\cal U$, we create a weighted graph $G'$; $G' = (V, E, w)$ is the same graph as $G$ except that edge $(u,v)$ has weight
$$w(u,v) = \min(\deg u, \deg v).$$
We solve $\cal U$ in $G'$, and get a partition $(L,R)$ of $V$. We define $\pi$ as follows: first put vertices from $L$ and then vertices from $R$. Importantly, the order of vertices in $L$ and in $R$ is not arbitrary now. We put vertices with smaller degrees closer to the boundary between $L$ and $R$. (In other words, vertices in $L$ and $R$ are sorted by their degrees in the descending and ascending orders, respectively.) It's not hard to see that this algorithm gives $O(\sqrt{\log n})$ approximation.
Conclusion:

There is no constant factor approximation for $\cal P$ if the Unique
Games Conjecture holds.
There is an $O(\sqrt{\log n})$ approximation algorithm.
In order to get a better approximation factor, one needs to improve the best known approximation algorithm for Min Uncut (which would be a breakthrough result in the field, especially since the problem is closely related to Sparsest Cut and Balanced Cut).

(Informal note: we will not get any better algorithms if we assume that the graph has a high average degree or a relatively low average degree.)
Generalization: The proof can be adapted in a straightforward way to this problem, where instead of looking for a permutation of the nodes, we look for an orientation of the edges (that is a less constrained problem where the edge orientation does not have to induce a DAG).
It can also be adapted in a straightforward way to the case where the objective to minimize is $\sum_{v\in V} ~\min(\left|\text{succ}_{\pi}(v)\right|,
\left|\text{pred}_{\pi}(v)\right|)$ instead of $\sum_{v\in V} ~\left|\text{succ}_{\pi}(v)\right|\times
\left|\text{pred}_{\pi}(v)\right|$. Interestingly, with that new objective we have $U_G = P_G$.


Non-hamiltonian Graphs with unique hamiltonian path between exactly 4 pair of vertices

Here's a trivial example class [and now, also generalized slightly in view of Esha's comment]: graphs G(h,k,n) constructed from a path of length n, by adjoining a cycle of length h and a cycle of length k to the two ends. If the two cycles are

  A1 – P0 – A2 – ... – Ah−1 – A1

and

  B1 – Pn – B2 – ... – Bk−1 – B1 ,

connected by the path

  P0 – P1 – ... – Pn ,

then there are Hamiltonian paths between each vertex pair {Aa , Bb} for a,b ∈ {1,2} but for no others.


This is really less about graph per se and more about topology. A combinatorial embedding defines a 2-manifold, a topological space in which every point has a neighborhood homeomorphic to a 2-dimensional open disk: the embedding allows a face to be defined, and we can define a topological space by choosing a disk for each face and gluing them together along the graph edges. A well known theorem in topology (called the classification of 2-manifolds) tells us exactly which 2-manifolds are possible, and they are all distinguishable from each other either by whether they are orientable or whether they have the same Euler characteristic (or both) — see http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdf for some reasonable lecture notes on this subject, that include the proof you're asking for. There are no other 2-manifolds in this classification that have the same Euler characteristic as the sphere, so if you calculate the Euler characteristic and find that it matches the formula for a sphere, you know your embedding must be onto a sphere.

Finding an embedding with actual geometric coordinates in the plane, once you have a planar combinatorial embedding, is not entirely trivial but can be done e.g. using the theory of Schnyder woods. I have some lecture notes on this at http://www.ics.uci.edu/~eppstein/gina/schnyder/ for instance.


What are the most effective algorithms to find random number?

As other answers mentioned, any deterministic process (such as Turing/Register Machines) can not produce 'philosophical' or 'true' random numbers. Allow me to answer a slightly rephrased question: "What are the most effective algorithms for finding pseudorandom numbers?"

There are arguably four important properties to consider in pseudorandom number algorithms:

Security/Hardness of prediction (under varying contexts, i.e. given different amounts of information about the internal state of the algorithm as it runs or bits generated from its output)
Cycle length, the amount of time it takes for the algorithm to enter into a cycle / repeat its output (and also how this cycle length is distributed according to its input; whether there are some inputs that cause very short cycles)
Distribution of output values (usually this distribution can be 'flattened' into the uniform distribution using various tricks, but this introduces additional overhead)
Speed of the algorithm

There is an old engineering joke involving steam engines. An engineer that specialized in trains confronts his investor, telling him that steam engines have three properties: speed, safety, and cheapness; and that due to some fundamental laws of physics, steam engines can only be designed with two of the three properties.

This story relates well to the current state of pseudorandom number generators. Many algorithms are believed to have several of these properties, but no algorithm (as far as I know) is known to have all of these properties.

And so you must choose the algorithm most appropriate for your application. For example, in Computer Graphics algorithms often use Monte Carlo techniques to find an approximate solution to raytracing problems. Obviously for these applications a long cycle of non-redundant, uniformally distributed outputs are required. The faster this algorithm works, the better. Because the application does not need to keep its bits safe from an adversarial entity, rendering algorithms are free to use non-secure PRGNs that simply pass statistical randomness tests. Monte Carlo applications like this are popular and can be encounterd in statistical physics, primality testing (another) and other probabilistic algorithms, Computer Go, and many more places.

For these types of applications, Lagged Fibonacci Generators have been popular. The Mersenne Twister has in recent years been adopted more and more frequently (despite some criticism). The Mersenne Twister is generally easy to predict and should not be used for applications where hardness is a requirement (caveat: some research has been done in developing variants that are thought to be secure in this manner).

There are some applications that need security garuntees. For example, in Interactive Proof Systems, verifiers need to challenge provers with random decisions. If the prover is capable of predicting the verifier's decisions, the protocol breaks down and we get can get no garuntees on the validity of the proof. For this application, a low speed on the algorithm is an acceptable loss for a hardness garuntee (the prover does almost all of the processing in these schemes). Similarly, when choosing bits of prime numbers to generate an RSA key, it is acceptable to absorb the one-time cost of a slow algorithm that has some garuntee of unpredictability.

There are a number of cryptographically secure pseudorandom number generators. However, the level of security varies greatly between these algorithms. One can use symmetric encryption algorithms and hash functions as PRNGs, although this is generally not suggested in the literature. Fortuna and Yarrow (both by Bruce Schneier) are considered cryptographically secure. However, these are examples of algorithms whose security proofs are derived from the statement "all known methods for breaking PRNGs fail on this algorithm" which is considered a weaker security proof than that of explicitly showing an intractibility proof from reasonable complexity assumptions. Blum Blum Shub is an algorithm noted for its unusually strong security proof.


I believe that a type of automata that your are looking for could be "visibly counter automata". It is easy to imagine what they should be - they are just standard automata but equipped with a set of non-negative unbounded counters that can be incremented/decremented after you read a specific letter (like in the case of VPA).
You might want to check the paper "Regularity Problems for Visibly Pushdown Languages" by Barany et al.: https://www.logic.rwth-aachen.de/~vbarany/BLS_stacs06_withAppendix.pdf


Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem?

EDIT: Adding the caveat that Roger's fixed-point theorem may not be a special case of Lawvere's.

Here is a proof that may be "close"... It uses Roger's fixed-point theorem instead of Lawvere's theorem.  (See comment section below for further discussion.)

Let $K(x)$ be the Kolmogorov complexity of string $x$.

lemma.  $K$ is not computable.

Proof.

Suppose for contradiction that $K$ is computable.
Define $K'(x)$ to be the minimum encoding length of any Turing Machine $M$ with $L(M) = \{x\}$.
There exists a constant $c$ such that $|K(x) - K'(x)|\le c$ for all strings $x$.
Define function $f$ such that $f(\langle M \rangle) = \langle M' \rangle$ where $L(M') = \{x\}$ such that $x$ is the minimum string such that $K(x) > |\langle M\rangle| + c$.
Since $K$ is computable, so is $f$.
By Roger's fixed-point theorem, $f$ has a fixed point, that is, there exists a Turing Machine $M_0$ such that $L(M_0) = L(M_0')$ where $\langle M_0' \rangle = f(\langle M_0\rangle)$.
By the definition of $f$ in line 4, we have $L(M_0) = \{x\}$ such that $K(x) > |\langle M_0\rangle| + c$.
Lines 3 and 7 imply $K'(x) > |\langle M_0\rangle|$.
But by the definition of $K'$ in line 2, $K'(x) \le |\langle M_0 \rangle|$, contradicting line 8.


Approximating the value of k in $k$-mean clustering problem

This problem is known as Geometric Set Cover (which deals with covering with different shapes, so unit balls are a special case). I'm unaware of any relation to $k$-means which is a clustering algorithm whose clusters are not limited in radius.

The problem is known to be NP-complete for $k\geq 2$.

For unit balls, this problem has a PTAS ( ($1+\epsilon$)-approximation) ) for the 2D case and is known to be APX-hard for $d=3$.


I think it's still quadratic, for arbitrarily large choice of $c$.

Let $\epsilon$ be small, and place two line segments $s_1$ and $s_2$ of length $\epsilon^2$, each tangent to the unit sphere at their midpoints, at distance roughly $\epsilon$ apart from each other. Because the line segments are so short, the Voronoi diagram of the two line segments approximates the Voronoi diagram of the two midpoints, which is just a plane $P$ bisecting the sphere. At the center of the sphere, the two equal closest sites are the midpoints of the segments.

Now, place equally spaced points on each segment. This will cause the Voronoi diagram of the points of a single segment $s_i$ to consist of two halfplanes separated by many thin slabs bounded by parallel planes, that all pass near the center of the sphere. These slabs intersect $P$ in thin parallel two-dimensional stripes, whose slope can be controlled by the angle at which $s_i$ is placed relative to the sphere. By choosing the angles of $s_1$ and $s_2$ so that they are skew to each other, the stripes for $s_1$ on $P$ can be made to cross the stripes for $s_2$ on $P$, near the center of the sphere. This in turn means that for each pair of a Voronoi region from $s_1$ and a Voronoi region from $s_2$, there is a boundary between the two regions near the center of the sphere. Thus, the Voronoi diagram has quadratic complexity in a region of space (the center of the sphere) that is far from a bounding box of the generating sites.


Answer converted from comment.

Definition: 1-in-$k$ SAT is a $k$-SAT problem with the tighter condition that - given a truth assignment to the variables - each clause must contain exactly one true literal (and thus $k$-1 false literals).

See for example 1-in-three SAT on Wikipedia

The reduction from 1-in-$k$ SAT to $k$ SAT can be done easily.

following the definition, convert each $(X_1 \vee X_2 \vee \cdots \vee X_k)$ clause of the 1-in-$k$ SAT problem into $(X_1 \wedge -X_2 \wedge \cdots \wedge -X_k) \vee (-X_1 \wedge X_2 \wedge \cdots \wedge -X_k) \vee $ $\cdots \vee (-X_1 \wedge -X_2 \wedge \cdots \wedge X_k)$;
convert to CNF distributing ORs over ANDs;
convert the resulting CNF formula to $k$ SAT

For example $(x_1 \vee x_2 \vee -x_3)$ becomes:

$(x_1 \wedge -x_2 \wedge x_3) \vee (-x_1 \wedge x_2 \wedge x_3) \vee
    (-x_1 \wedge -x_2 \wedge -x_3)$;
$(x_1 \vee x_2 \vee -x_3) \wedge (-x_1 \vee -x_2) \wedge (-x_1 \vee x_3) \wedge (-x_2 \vee x_3)$
$(x_1 \vee x_2 \vee -x_3) \wedge (-x_1 \vee -x_2 \vee x4) \wedge (-x_1 \vee -x_2 \vee -x4)$ $\wedge (-x_1 \vee x_3 \vee x4) \wedge (-x_1 \vee x_3 \vee -x4)$ $\wedge (-x_2 \vee x_3 \vee x4) \wedge (-x_2 \vee x_3 \vee -x4)$

Note: at step 3, if you allow repeated variables in a clause, then there is non need for the extra variable and the final $k$ SAT formula of the example can be:
$(x_1 \vee x_2 \vee -x_3) \wedge (-x_1 \vee -x_2 \vee -x2)$ $\wedge (-x_1 \vee x_3 \vee x3)$ $\wedge (-x_2 \vee x_3 \vee x3)$


Any fundamental papers in TCS which were found to be incorrect/wrong later?

One example is the claimed proof of the Gilbert-Pollak conjecture on the Steiner ratio, which appears in FOCS'90, and Algorithmica. The conjecture is now considered open.

Another examples include a sequence of algorithms on graph embedding.

There are more examples, but without similarly published refutations as above, it is difficulty to list due to the subtle nature.


Examples of $\Sigma_2^p$ complete problems?

Marcus Schaefer and Chris Umans have a nice Garey-and-Johnson-esque survey of complete problems in the polynomial hierarchy.


If we have a fixed number of tapes then yes we can simulate them without the logarithmic overhead. E.g simulation of two-tape (and in general $k$-tape) TMs on a two-tape machine can be done without the logarithmic factor increase.

If we want to simulate an arbitrary constant number of tapes then AFAIK we don't know any such simulation.

See these questions and the references there:

Justification of log f in DTIME hierarchy theorem

Universal simulation of Turing machines


Multi prover, verifier games and PCP theorem

Let me sketch the relation between the PCP theorem and 2-provers 1-round game. For concreteness let's consider the MAX-3-SAT problem. In this problem we are given a 3-CNF formula, and our goal is to find an assignment that maximizes the number of satisfied clauses. This problem is NP-hard, and (the CSP view of) the PCP theorem says that given a satisfiable formula it is NP-hard to find an assignment that satisfies 99% of the clauses.

The 2-provers 1-round game view of PCP theorem says that if we are given a game as an input it is NP-hard to distinguish between the two cases:

YES case: The provers have a strategy that always satisfies the verifier.

NO case: In every strategy of the provers will satisfy the verifier with probability at most $1-\epsilon$ for some constant $\epsilon>0$.

Let us now translate the MAX-3-SAT problem into a 2-provers one round game. That is we show a reduction from MAX-3-SAT to 2P1R-game. The verifier chooses one clause from the formula and one variable from the clause at random. He sends the clause to the first prover, and the variable to the second prover. The first prover replies with an assignment to the three variables in the clause, and the second prover sends an assignment to his variable. The verifier then checks that the assignment of the first prover indeed satisfies the clause, and that the answer of the second prover is consistent with the answer of the first prover.

Now, what is left to show is that this reduction gives a gap problem for the 2-prover 1-round game.

YES case: If the given formula is satisfiable, then the provers have a strategy that will satisfy the verifier. This is easy, they just need to reply according to the satisfying assignment.

NO case: If the provers have a strategy that allows them to win with probability $1-\epsilon$, then there exists an assignment that satisfies at least $1-3\epsilon$ of the clauses. This part is also not hard to prove. Just look at the assignment of the second prover to the variables, and claim that it must satisfy at least $1-3\epsilon$ fraction of the clauses.

I hope it makes sense...


Pi-calculus (or session types) - proof for weakening lemma

You should $\alpha$-rename to avoid conflict with the variable names. That is, you should prove weakening of the form: $\Gamma \vdash (\upsilon y) P$ implies $\Gamma, x : T \vdash (\upsilon y) P$.
$\alpha$-equivalence and capture-avoiding substitution is an important concept to understand in type theory: I would recommend studying this concept for the untyped or simply-typed $\lambda$-calculus to begin with, before trying to prove things about a more complicated calculus.


Why does predecessor(zero) need to be zero in Church numerals?

The other reason (than the one already stated) for pred 0 = 0 are the (all too often unstated) requirements that

pred be a total function from nat to nat
pred succ n = n be true.
pred be as close to injective as possible.
pred be as close to a monotone decreasing function as possible.

It is that last requirement which really 'seals the deal' in forcing pred 0 = 0, since that is the choice which minimizes the distance to not being monotone decreasing.


What is the role of "universe" types in intuitionistic type theory?

In ordinary set theory one can write statements about all sets using the universal quantifier "$\forall x$" to have $x$ range over all sets.

In type theory without universes there is nothing that allows you to make a type that refers to all types. For example, the statement

  "For all types $A$ and $B$, $A \times B$ and $B \times A$ are equivalent types."

is not a judgement in type theory. It is a meta-statement in which $A$ and $B$ are schematic symbols. In order to express it as a judgement in type theory, we need something else. One solution is to have a universe (and another to have polymorphism a la System $F$). With a universe $U$, we can use "$\prod_{A : U}$" to make a product type that ranges over "for all types $A$ (in the universe $U$)", inside type theory. For instance, the type
$$\prod_{A : U} \prod_{B : U} (A \times B \simeq B \times A),$$
where $X \simeq Y$ is the type of equivalences from $X$ to $Y$, is how one would express the above statement using types.


Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?

Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou got the Godel prize in 2004 for their use of algebraic topology in the study of some problems in distributed computing.


Are there good implementations for easy subclasses of NP-hard graph problems

I'd be surprised if there existed a graph library recognizing them all (there is a lot of them), but most of the algorithms you will find in the litterature are focused on a very small amount of classes... For example chordal graphs (easy to recognise), or treewidth-bounded graphs (much harder.. hopefully the algorithms given for these classes are almost useless in practice), planar graphs, ...

In Sage (http://www.sagemath.org/), we are trying to build a large graph library, with recognition algorithms and methods to solve NP-Hard problems. For instance, we have the following methods :

g.is_bipartite
g.is_chordal
g.is_circular_planar
g.is_clique
g.is_drawn_free_of_edge_crossings
g.is_equitable
g.is_eulerian
g.is_even_hole_free
g.is_forest
g.is_gallai_tree
g.is_hamiltonian
g.is_interval
g.is_line_graph
g.is_odd_hole_free
g.is_overfull
g.is_perfect
g.is_planar
g.is_prime
g.is_regular
g.is_split
g.is_transitively_reduced
g.is_tree
g.is_triangle_free
g.is_vertex_transitive

The best is probably to read the (unfortunately) long list of methods related to graphs...

http://www.sagemath.org/doc/reference/graphs.html

(I wrote a short tutorial there : http://www-sop.inria.fr/members/Nathann.Cohen/tut/Graphs/ )

Nathann