Complexity class for Optimization problems over #P functions

It's in $\mathrm{FP^{\#P}}$, since you can compute it in poly time using oracle calls to compute the $f$s.  If you can poly-time Turing reduce a $\mathrm{\#P}$-complete problem to it, then $\tilde{f}$ is $\mathrm{\#P}$-hard but you can't say it's $\mathrm{\#P}$-complete unless you can show that it's in $\mathrm{\#P}$. That seems unlikely, to me, as I can't see any way of building a nondeterministic Turing machine to have that many accepting paths.

Since $\tilde{f}\in\mathrm{FP^{\#P}}$ and $\mathrm{FP^{FP^{\#P}}}=\mathrm{FP^{\#P}}$ (just compose the reductions), $\mathrm{FP}^{\tilde{f}}\subseteq \mathrm{FP^{\#P}}$.  Note that $\mathrm{FP}^{\tilde{f}}$ is a complexity class (all problems that are poly-time Turing reducible to $\tilde{f}$), not a problem.


What is the fastest algorithm to compute rank of a rectangular matrix?

You can bring a $2n \times n$-matrix into echelon form in time
$O(n^{\omega + \epsilon})$ for any $\epsilon > 0$. See the book "Algebraic Complexity Theory" by Bürgisser, Clausen, Shokrollahi, Section 16.5.

Now you apply this procedure $m/n$ times to your $m \times n$-matrix.
This gives an algorithm with $O(mn^{\omega-1})$ arithmetic operations.

If you bring an $2n \times n$-matrix into echelon form, then it contains
a zero matrix of size $n \times n$ afterwards. You take the remaining $n \times n$-matrix,
add a new $n \times n$-block of your input matrix and bring this to echelon form and so on.


Approximation results on scheduling under an uncommon constraint

Even without the additional constraints you have the unrelated machine scheduling problem with precedence constraints is not well understood. If I am not mistaken nothing better than a polynomial factor approximation is known. It is an important open problem in approximation algorithms for scheduling problems. Some positive results are known when the precedence constraints form a tree. See the following paper. http://www.springerlink.com/content/p8321031hk718413/

Can you solve your problem in the simpler case when the machines are identical or related?


Unification-based elimination rule for equality

I've often attributed this to Rules of definitional reflection by Schroeder-Heister, though the idea goes back beyond that to Girard and others; the rule you're looking for is an instance of the first display in Section 4. You also, however, need a rule that says that if the unification instance is unsatisfiable, then the assumption of equality has the force of a contradiction.

A more general account has been used recently in a lot of work by Dale Miller, David Baelde, and company (see, for instance, Least and greatest fixed points in linear logic). The more general formulation - which also doesn't originate with Miller et al - is that the rule is

$${\{\theta \in {\sf csu}(t,s) \mid \theta\Gamma \vdash \theta{C} \}}\over{\Gamma, t \doteq s \vdash C}$$

where ${\sf csu}(t,s)$ is the complete set of unifiers - the set of all unifying substitutions of $t$ and $s$. You might also prefer the equivalent way of writing this rule that I prefer (see here for example).

$${\forall \theta. \theta{t} = \theta{s} \longrightarrow \theta\Gamma \vdash \theta{C}}\over{\Gamma, t \doteq s \vdash C}$$

In any case, in a term language with decidable unification where the existence of a unifier implies the existence of a most general unifier, having either of these rules above can be shown to be equivalent to having these two rules:

$$
{{{\sf no~mgu}(t,s)}\over{\Gamma, t \doteq s \vdash C}}
\qquad
{{{\sf mgu}(t,s) = \theta \quad \theta\Gamma \vdash \theta{C}}\over{\Gamma, t \doteq s \vdash C}}
$$

(P.S. Frank discussed this in his logic programming course in lectures 6, 7, and 8, which may be where you remember it from.)


Evaluate boolean circuit on batch of similar inputs

I'd consider it unlikely that such a trick is easy to find and/or will give you significant gains, as it would give nontrivial satisfiability algorithms. Here's how:

First of all, while ostensibly easier, your problem can actually solve the more general problem of, given a circuit $C$ and $N$ inputs $x_0, \ldots, x_{N-1}$, evaluate $C$ at all the inputs faster than $\tilde{O}(N\cdot|C|)$ time. The reason is that we can tweak $C$ into a circuit $C'$ of size $|C| + \tilde{O}(Nn)$ which, on input $0^i10^{N-1-i}$, outputs $C(x_{i})$. Basically, we just make a little lookup table that sends $0^i10^{N-1-i}$ to $x_i$, and wire it into $C$.

Nontrivial algorithms for batch evaluation of boolean-circuits can then be used to make fast satisfiability algorithms. Here's an example in the simple case where we suppose we have an algorithm doing evaluation in time $\tilde{O}(|C|^{2-\epsilon} + (N\cdot|C|)^{1-\epsilon/2} + N^{2-\epsilon})$ for any constant $\epsilon > 0$. On input a circuit $C$, we can decide satisfiability by expanding $C$ into a circuit $C'$ of size $2^{n/2}\cdot |C|$ which is just the OR over all possible choices of the first $n/2$ inputs to $C$ (leaving the other inputs free). We then batch-evaluate $C'$ on all of its $2^{n/2}$ inputs. The end result is that we find a satisfying assignment to $C'$ iff $C$ is satisfiable. The running time is $\tilde{O}(2^{(n/2)(2-\epsilon)}\cdot |C|^{2-\epsilon}) = \tilde{O}(2^{n(1-\epsilon/2)}\cdot \textrm{poly}(|C|))$.


It might come as no surprise, but there is a substantial overlap between cstheory Q&A power-users and the blogosphere. We even had a dedicated blog for a while, with some great posts but it fell into disuse. However, I thought I would list some of the blogs run by our top 38 users that have had new posts since 2012:

David Eppstein's 0xDE: graph-theory and algorithms.
Suresh Venkatasubramanian's The Geomblog: computational geometry, algorithms, and discussions of academic life.
Jeff Erickson's Ernie's 3D Pancakes: computational topology, and community announcements.
Neel Krishnaswami's Semantic Domain: programming languages, logic, and formal languages.
Joe Fitzsimons's Quantized Thoughts: quantum information and computation, theoretical physics, and community building.
Andrej Bauer's Mathematics and Computation: HoTT, logic, category theory, and philosophy of math.
András Salamon's Constraints: computational complexity through the lens of constraint satisfaction.
Marzio De Biasi's ... nearly 42 ...: computational complexity highlighted through NP-completeness and puzzles.
Scott Aaronson's Shtetl-Optimized: computational complexity, with a primary focus on quantum computing, philosophy, humour, and community building.
Lev Reyzin's Room for Doubt: theory and practice of machine learning, and academic life.
Noam Nisan's Turing's Invisible Hand: computational economics, algorithmic game theory, and community building.
Sariel Har-Peled's Vanity of Vanities, all is Vanity: computational geometry, and general social and academic commentary.
Shiva Kintali's My Brain is Open: computational complexity, polyhedral combinatorics, algorithms, and graph theory.
Artem Kaznatcheev's Theory, Evolution, and Games Group: evolutionary game theory, and algorithmic lens on evolution, learning and philosophy.
Hsien-Chih Chang's Finite Playground: bilingual blog on computational complexity, formal languages, and concrete math.
Aaron Sterling's Nanoexplanations: distributed computing, chemoinformatics, and general social commentary.
Lance Fortnow and Bill Gasarch's Computational Complexity : Computational Complexity and other fun stuff in math and computer science.
Emanuele Viola's Thoughts: computational complexity and general commentary -- started Summer 2014.


Problem understanding "connectivity" characteristic for the $k$-connected subgraph problem

I think I figured it out.

$Com_{H}(v, u)$ are paths leaving the region and connecting through some vertices outside the region.

$Path_{H}(v)$ are the paths connecting $v$ to the vertices that are not included in this region.

$Path_{H}$ are paths inside the region

If this is true, then the proof of Lemma 3.2 has some typing errors (the 2 a.m. kind). And it should be:

  To compute $Com_{H}(v, u)$ where u, u v are non-portal vertices in $H$, for each competition $D$ in $Com_{H}(v, u)$, we insert D and the set difference $D\backslash B$ into $Com_{H \cup B}(v, u)$ (not $H \cup C$).
  [The rest is good]

I am not really sure, so please let me know what you think about this via comments \ up-votes \ telepathy.


Is there an approximation algorithm for MAX k DOUBLE SET COVER?

(Comment $\rightarrow$ Answer)

Consider the following algorithms for a hypergraph $(U,\mathcal S)$, with $n=|U|$:

For a set $X\subseteq \mathcal S$ of sets and a set $A \in X$, define $d_X(A)$ as the number of elements in $A$ that are double covered by $X$, i.e. $|A \cap \left(\bigcup(X \setminus \{A\})\right|$. Additionally, let $c(X)$ denote the number of elements double covered by $X$. By simple counting arguments, $$\max_{A \in X} d_X(A) \leq c(X) \leq \tfrac{1}{2}\sum_{A \in X} d_{X}(A)$$.

Now do the following for each set $A \in \mathcal{S}$: fix your choice of $A$ as one of the sets in your candidate solution. Now consider the Max-$(k-1)$-cover problem with set system $\mathcal{S} \setminus \{A\}$ and universe $A$. Let $X$ be the output of the greedy algorithm for this Max-$(k-1)$-cover problem, which approximates the optimal solution to within a factor of $1-1/e$. Call this greedy solution $Y_A$, and consider the candidate solution $X_A = Y_A \cup  \{A\}$. Call the best such solution $Z$. For each $A \in \mathrm{OPT}$, the solution generated this way satisfies (by the guarantee of the greedy algorithm) $$d_{X_A}(A)/(1-1/e) \geq \max_{\stackrel{T \subseteq S}{|T|=k-1}} d_{T\cup\{A\}}(A) \geq d_{\mathrm{OPT}}(A)$$. Now, letting $B$ be the set in $\mathrm{OPT}$ maximizing $d_\mathrm{OPT}(B)$, we have

$$\begin{eqnarray}
c(\mathrm{OPT}) & \leq & \tfrac{1}{2}\sum_{A \in \mathrm{OPT}} d_{\mathrm{OPT}}(A) \\
& \leq & \tfrac{k}{2}d_\mathrm{OPT}(B) \\
& \leq & \tfrac{k}{2-2/e} d_{X_B}(B) \\
& \leq & \tfrac{k}{2-2/e} \max_{A \in X_B} d_{X_B}(A) \\
& \leq & \tfrac{k}{2-2/e} c(X_B) \\
& \leq & \tfrac{k}{2-2/e}c(Z).
\end{eqnarray}$$

$\,$

First, remove from $U$ all elements that can't possibly be double covered. Initialize $Y = \emptyset$. While $|Y| \leq k$ (and $Y$ doesn't fully double cover $U$), arbitrarily pick an element $x \in U$. We then add sets containing $x$ to $Y$ (chosen arbitrarily) until $Y$ at least double covers $x$. When the loop terminates, return $Y$. The total number of elements double covered this way ($c(Y)$) is at least $\min(|U|, k/2)$. If it's $|U|$, we solved the problem exactly so there's no need for further analysis. Otherwise, we have $$c(\mathrm{OPT}) \leq n = \tfrac{2n}{k} \cdot k/2 \leq \tfrac{2n}{k} \cdot c(Y).$$

Now run the two above algorithms, generating solutions $Z$ and $Y$, and let $X = \max(Y, Z)$. Multiplying the two inequalities, $$c(\mathrm{OPT})^2 \leq \tfrac{k}{(2-2/e)} \tfrac{2n}{k} \cdot c(Y)c(Z) = \tfrac{n}{1-1/e} c(Y)c(Z) \leq \tfrac{n}{1-1/e} c(X)^2.$$ So $$c(\mathrm{OPT}) \leq \sqrt{\tfrac{n}{1-1/e}} c(X),$$

giving an $O(\sqrt{n})$ approximation.


NP-hardness of minimum distance over a code

Berlekamp, McEliece and Van Tilborg
[On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)]
proved that deciding if a binary code contains a code word of weight $w$ is NP-complete. In http://statweb.stanford.edu/~cgates/PERSI/papers/85_04_radon.pdf
Diaconis and Graham prove that deciding if a binary code of length $2m$ contains a code word of weight $n$ is NP-complete.


Mutually exclusive replacement paths, an existing problem?

I found a replacement path allocation for $_$ in a more general setting. Consider an edge $_1$ that uses edge $_2$ on its path. The allocation induces a dependency from $_1$ to $_2$. Mutual exclusion defined above corresponds to a cycle of 2 such dependencies. Now consider the more general setting: a cycle of $$ dependencies induced by a path allocation on $_$. Assume vertices are $0,…,−1$. On edges $,$, the path allocation $,+1,0,+1,$ induces cycles of dependencies no shorter than $$. In my application it means that $_$ can tolerate up to $−1$ edge failures (i.e. edge removal).

Same problem on hypercubes, published here:
''Local Fast Segment Rerouting on Hypercubes''

Further solutions were submitted recently. Will update soon.


The discussion in the comments below indicades that I have misunderstood the question.  My answer is premised on the Oracle taking no input and returning $(x, f(x))$ where $x \sim p$ or $x \sim q$, depending on $f \in F$. This is apparently not what's being asked.

Because the target distribution is fixed for every target $f^* \in F$, the PAC-sample upper bound applies (this follows from the fact that the target distribution for this bound can even completely depend on $f^*$). Hence,
$$
m \le \tilde{O}\left(\frac{1}{\epsilon}\left(\mathrm{VC}(F) + \log(1/\delta) \right) \right)
$$
examples should suffice to find a hypothesis of error $\le \epsilon$ w.p. $\ge 1-\delta$. Note -- after seeing these examples, one needs to find a consistent hypothesis from $F$, and this may not be tractable.

On the other hand, one can get a nearly matching lower bound even for the case of $p=q=U$, the uniform distribution, where $m \ge \Omega(\mathrm{VC}(F))$ examples are still required (this can be improved slightly).

The variational distance between $p$ and $q$, as well as $k$ may play a role in the small gap between these bounds, but I doubt it.


What are natural examples of non-relativizable proofs?

As Steven notes, the canonical example is $\mathsf{IP} = \mathsf{PSPACE}$. This collapse does not relativize, in the sense that there is an oracle $A$, subject to which $\mathsf{IP}^A \ne \mathsf{PSPACE}^A$. The intuition why the known proof of this result avoids the relativization barrier is that it uses arithmetization (Yonatan alluded to this in a comment): an interactive protocol for the $\mathsf{PSPACE}$-complete problem TQBF is given by considering an extension of a quantified boolean formula to a low-degree polynomial over a suitably large field. If we are given a relativized boolean formula (with oracle gates), such an extension does not exist.

There is a refinement of the relativization barrier -- algebrization -- due to Aaronson and Wigderson. Generically, the arithmetization technique is not enough to circumvent the algebrization barrier. A complexity class inclusion $\mathsf{C} \subseteq \mathsf{D}$ algebrizes if for any oracle $A$ and any extension $\tilde{A}$ of $A$ to low-degree polynomials over a finite field, $\mathsf{C}^A \subseteq \mathsf{D}^{\tilde{A}}$. A separation $\mathsf{C} \not \subset \mathsf{D}$ algebrizes if for all $A$, and all extensions $\tilde{A}$, $\mathsf{C}^{\tilde{A}} \not \subset \mathsf{D}^{A}$. Aaronson and Wigderson show that $\mathsf{IP} = \mathsf{PSPACE}$ algebrizes, but many other results, including $\mathsf{NP} \not \subset \mathsf{P}$, do not.

A recent example of a technique that does not algebrize or relativize is Ryan Williams' proof that $\mathsf{NEXP} \not \subset \mathsf{ACC}$. The separation does not algebrize: there is an oracle $A$ and a low-degree extension $\tilde{A}$ such that $\mathsf{NEXP}^{\tilde{A}} \subset \mathsf{ACC}^A$.  Intuitively the reason why the proof avoids the barrier is that it relies on the existence of a faster-than-trivial satisfiability algorithm for $\mathsf{ACC}$ circuits, and the algorithm uses non-relativizing and non-algebrizing properties of such circuits. Ryan notes in the paper that all known faster-than-trivial satisfiability algorithms break down when oracles or algebraic extensions of oracles are added.

There is also an interesting approach to understanding relativization through logic. In an old manuscript, Arora, Impagliazzo, and Vazirani define a system of axioms such that the relativizing results are exactly those that follow from the axioms, while non-relativizing results are independent from the system. A paper by Impagliazzo, Kabanets, and Kolokolova does something similar for algebrization by introducing an additional axiom to the ones defined by Arora, Impagliazzo and Vazirani. They show that most known non-relativizing results follow from their axioms, while P vs NP, among others, is independent of them.

Apologies if I got something wrong, I am not quite an expert.


What is the best-known inapproximability result for MIN-3CNF-DELETION?

There is no approximation algorithm for MIN-3CNF-DELETION at all since it is not even possible to determine in polynomial time whether a 3 CNF SAT instance is satisfiable or not (if P≠NP). That is, it is not possible to determine if the objective function is equal to 0 or strictly positive. Specifically, if we had an $f(n)$ approximation algorithm for the problem, given a satisfiable instance the algorithm would find a solution of cost $0 \cdot f(n) = 0$ ; that is, a solution that satisfies the instance.

In contrast, if an instance of Min-Horn-Deletion or Min-2CNF-Deletion is (completely) satisfiable, we can efficiently find a solution that satisfies all clauses. Thus it makes sense to talk about approximation algorithms for Min-Horn-Deletion and Min-2CNF-Deletion.


Probability of generating a desired permutation by random swaps

I think that whether p>0 can be decided in polynomial time.

The problem in question can be easily cast as the edge-disjoint paths problem, where the underlying graph is a planar graph consisting of m+1 layers each of which contains n vertices, plus m degree-4 vertices to represent the possible adjacent swaps.  Note that the planarity of this graph follows from the fact that we allow only adjacent swaps.

If I am not mistaken, this falls in the special case of the edge-disjoint paths problem solved by Okamura and Seymour [OS81].  In addition, Wagner and Weihe [WW95] give a linear-time algorithm for this case.

See also Goemans’ lecture notes [Goe12], which gives a nice exposition of the Okamura–Seymour theorem and the Wagner–Weihe algorithm.

References

[Goe12] Michel X. Goemans.  Lecture notes, 18.438 Advanced Combinatorial Optimization, Lecture 23.  Massachusetts Institute of Technology, Spring 2012.  http://math.mit.edu/~goemans/18438S12/lec23.pdf

[OS81] Haruko Okamura and Paul D. Seymour.  Multicommodity flows in planar graphs.  Journal of Combinatorial Theory, Series B, 31(1):75–81, August 1981.  http://dx.doi.org/10.1016/S0095-8956(81)80012-3

[WW95] Dorothea Wagner and Karsten Weihe.  A linear-time algorithm for edge-disjoint paths in planar graphs.  Combinatorica, 15(1):135–150, March 1995.  http://dx.doi.org/10.1007/BF01294465


Applications of TCS to classical mathematics?

Expanders were developed to a large extent in TCS and they have profound connections and applications to mathematics.


Complexity of Tensor Rank over an Infinite Field

There is a recent preprint about this: http://galton.uchicago.edu/~lekheng/work/np.pdf . It shows that most rank-related issues with tensors are NP hard over $\mathbb{R}$ and $\mathbb{C}$. (It also mentions that deciding the rank over $\mathbb{Q}$ is NP hard.)


Shortest paths when randomly scrambling a Rubik's cube

At God's number is 20 site you can find a nice distance/count table:

"... Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are. The table on the right gives the count of positions at each distance; for distances 16 and greater, the number given is just an estimate. Our research has confirmed the prior results for entries 0 through 14 below, and the entry for 15 is a new result, which has since been independently confirmed by another researcher ...."

According to the table if you pick a random configuration it will be with high probability at distance 17-18 from the solution.

See also D. Joyner's notes Mathematics of the Rubik's cube (and D. Joyner's book "Adventures in Group Theory: Rubik’s Cube, Merlin’s Machine, and Other Mathematical Toys")


An edge orientation procedure to generate all acyclic orientations of a graph

The procedure maps each permutation of the vertices to some orientation of the graph whose topological ordering of the vertices is consistent with the permutation.

Every acyclic orientation of the graph induces at least one topological ordering of the vertices.

Every topological ordering of the vertices induces exactly one orientation of the graph (since if two distinct orientations were compatible with the ordering, they would differ in the orientation of at least one edge $(u,v)$ and hence $u$ would come both before and after $v$ in the permutation, which is a contradiction).

So the procedure generates all the acyclic orientations of the graph.


Internal Regret in Online Convex Optimization

Try "No-regret learning in convex games" by Gordon, Greenwald and Marks http://portal.acm.org/citation.cfm?id=1390202 . Its abstract sounds like it probably answers your question, or at least anyone answering that question would cite or be cited by that paper.


How to Define and Implement (Single-Writer) K-Atomic Snapshot Object?

Regarding Problem 1: I think the first part of the definition is fine.
The second item (about the time before $scan$) is not clear to me; More specifically, the order of quatifiers: is it $\exists time: \forall i$ or $\forall i: \exists time$ ? I guess the first, because in the second I don't see why it is necessary. But definitions should not need guessing ;-)

Regarding Problem 2: In principle there is two ways of looking at $K$. You can consider the last $K$ updates on a per item level or the last $K$ updates globally. The other choice is (already mentioned above) whether to require a point in time when the memory actually had the value returned by $scan$ (the $\exists time: \forall i$ case above) or whether not to require such a point.

A general comment: What happens when every process just updates $K$ times and scans until two scans are equal. Wouldn't that (trivially) implement ($1$-)atomic snapshot memory? If that is the case then the whole idea of $K$-atomic snapshpot memory could be hard to sell.


Statements that imply $\mathbf{P}\neq \mathbf{NP}$

A proof system for propositional logic is called polynomially bounded, if every tautology $\varphi$ has a proof in the system of length polynomial in the length of $\varphi$.

The statement "There is no polynomially bounded propositional proof system" is equivalent to $\mathsf{NP} \neq \mathsf{co}\text-\mathsf{NP}$ by a classic result of Cook and Reckhow, so it implies $\mathsf{P} \neq \mathsf{NP}$.


Integer programming with a fixed number of variables

The current fastest algorithm is actually linear in the length of the integer linear program for every fixed value of $n$. In his PhD thesis, Lokshtanov (2009) nicely summarizes the results by Lenstra (1983), Kannan (1987), and Frank & Tardos (1987) by the following theorem.

  Integer Linear Programming can be solved using $O(n^{2.5n+o(n)} \cdot L)$
  arithmetic operations and space polynomial in $L$. Here $L$ is the
  number of bits in the input and $n$ the number of variables in the
  integer linear program.

Thus, the problem is fixed-parameter linear parameterized by the number of variables.

1) Yes, Integer Linear Programming is "still" NP-complete. The running time of the theoretical result above depends only linearly on the number of constraints, so it scales nicely in the number of constraints. However I know of no actual implementation of this algorithm.

2) Yes, making the variables take binary values is straightforward as you observed.

Update. The dependence on $L$ can actually be improved in the running time for Integer Linear Programming. Based on Clarkson (1995) and Eisenbrand (2003) (see the comments below) one can obtain an algorithm with running time $$O(2^nnm + 8^n n \sqrt{m \log m} \log m + n^{2.5n+o(n)}s\log m)$$
where $m$ is the number of constraints and $s$ is the maximum number of bits required to encode a constraint or the objective function.


Here is an example, where one can produce a solution in polynomial time, but evaluating a given solution is NP-hard.

Input: Positive integers $n,k$ (in unary encoding), with $k\leq n$.

Task: Maximize the number of edges in an $n$-vertex graph under the  constraint that its maximum clique size is at most $k$.

Solution: It is known from extremal graph theory that the optimal graph will be  the Turan graph $T(n,k)$ (see here), which can be easily constructed in polynomial time. On the other hand, checking the quality of a given candidate solution (a given graph) involves checking that its maximum clique size is at most $k$, which is NP-hard.

Note: If we only want to check whether the solution is optimal, then it is easy, because the Turan graph is known to be the unique optimum, so it is enough to compare the candidate graph with the Turan graph, which has a simple structure. On the other hand, if we want to evaluate the quality of a candidate solution, as requested in the question, that is, whether it is feasible and how far it is from the optimum, then we have to check whether it satisfies the maximum clique constraint.


The simple answer would be that, having an infinite set of rules, this is not a grammar in the usual sense. Languages over infinite alphabets have been investigated, but usually using register automata rather than grammars.

That being said, you could treat the language as a limit (i.e. infinite union) of finitary languages defined by the "truncations" $G_i$ which you obtain by omitting all indices greater than $i$. I am unfortunately not familiar with research into such beasts.


How to solve this generalization of binary search?

The optimal strategy can be found through dynamic programming in $O(n^3)$ time.  Let $A[i,j]$ denote the worst-case cost of the optimal strategy when $T$ is already known to be in $\{i,i+1,\dots,j\}$.  Then we have the recursive relation

$$A[i,k] = \min \{f(j) + \max(A[i,j], A[j+1,k]) : j=i,i+1,\dots,k-1\},$$

with the base case $A[i,i] = 0$.  You can use dynamic programming to fill out this array.  The assumption that $f$ is non-decreasing is not needed; this works whenever $f$ is any non-negative function.


What kind of reinforcement learning is MENACE?

I found this question because I was searching for an answer to it myself...so take my answer on this with a grain of salt...but I believe that it's similar to policy gradients. In policy gradients you increase the probability of taking actions when you see a large reward which followed those actions...that seems to be the idea behind MENACE as well.


Network Flow with Non-contiguous Capacities

I think this is NP-complete, here I try to give a reduction from 1-in-3-SAT, where we want every clause to contain exactly one true literal. Suppose we are given a 3-CNF with $n$ variables and $m$ clauses, from this we construct a DAG.

The first level consists of the source $s$.

From here you have an edge of capacity $m$ to $v_i$ for each variable $x_i$.

The third level has vertices of the form $x_i$ and $\bar x_i$, with an edge of capacity $0$ or at least $m$ from the corresponding $v_i$.

On the fourth level, there is a vertex $c_j$ for every clause with an edge of capacity $0$ or at least $1$ from its literals. We also have an extra vertex, $w$ with edges of capacity $m$ from every literal vertex.

Finally, on the fifth level we have the target, $t$ with an edge of capacity $1$ from each $c_j$ and an edge of capacity $mn-m$ from $w$.

In this graph you have a flow of size $mn$ if and only if there is a 1-in-3-SAT assignment.


Enumerate all solutions of a SAT problem

You are looking for an ALL-SAT or all solutions SAT solver. This is a different problem from #SAT. You do not have to enumerate all solutions to count them.

I do not know of a tool that solves your problem because people add these algorithms on top of existing SAT solvers but rarely seem to release these extensions. Two papers that should help you in modifying a CDCL solver to implement ALL-SAT are below.

Memory Efficient All-Solutions SAT solver and its Application to Reachability, O. Grumberg, A. Schuster, A. Yadgar, FMCAD 2004

Here is a recent article posted on the arXiv.

Extending Modern SAT Solvers for Enumerating All Models, Said Jabbour, Lakhdar Sais, Yakoub Salhi, 2013

You could try contacting these authors for their implementation.


Is there a result in computability theory that does not relativize?

Higman's Embedding Theorem: The finitely generated computably presented groups are precisely the finitely generated subgroups of finitely presented groups. Furthermore, every computably presented group (even ones countably generated) is a subgroup of a finitely presented group.

Note that this statement could relativize to: "The $O$-computably presented groups (with some oracle $O$) are precisely the finitely generated subgroups of finitely presented groups," but it does not, as one can prove that for some uncomputable $O$ there are $O$-computably presented groups that are not computably presented.

Indeed, I think any non-relativizing result of computability theory must have something of this flavor, as some part of the result or its proof must somehow "nail down" true computability from computability with an oracle $O$. In this case, it is the finiteness which nails down "actual computability." Note that, as Scott Aaronson asked for, this result is invariant to any of the usual models of computation (Turing machine, RAM, etc), but does not relativize (again, because all of the usual models of "actual" computation share some common "finiteness property").

On the other hand, one might argue that this "doesn't count" for this question, as it is more akin to a definition of computability using groups than it is a "result of computability theory." On the other other hand, it is a definition of computability that is robust to model yet that doesn't relativize. (In contrast to, say, Kleene's characterization of the computable functions which easily relativizes, by simply adding the characteristic function of your oracle to the generating set of functions. There seems to be no analogous operation for groups in the context of Higman Embedding.)


Deterministic Parity Automata require unbounded index

Take a look at the following paper:
Relating hierarchies of word and tree automata.
They cite the result you are interested in.

As a more concrete answer, consider the following argument: let's look at the language $M_n=\{w\in \{0,...,n\}^\omega: \limsup w_i \text{ is even}\}$ (the same as your language with $i=0$), and assume it has a parity automaton $A$ with ranks $1,...,n+1$ (note that proving it doesn't have a parity automaton with ranks $1,...,n$ is not enough, as it's still possible for it to have ranks $0,...,n-1$).

We will construct a word that is accepted by $A$, but is not in the language (or vice-versa). Denote by $k$ the number of states in $A$. Consider the run of $A$ on the word $0^\omega$. It's accepting, so the limsup degree is even, and so at least $2$. Moreover, it must occur during the first $k$ steps, otherwise, since $A$ is deterministic, we have a non-accepting cycle. In addition, this is true for every $0^k$ infix of any word.

Now, consider the word $(0^k1)^\omega$. This word is not accepted, so the limsup degree is odd, but must be at least 3, since the $0^k$ infixes induce the degree $2$. Finally, this odd degree must occur within the first $k$ cycles of $0^k1$, for similar reasons as above.

We can repeat these alternating examples, constructing a word of the form $(0^k1)^k2$, and so on, with each word requiring a higher degree. However, since we only have degrees $1,...,n+1$, then eventually we will have a word that uses the letters $0,...,n-1$, whose limsup degree is $n+1$. From there, continuing this construction will still leave the limsup degree $n+1$, but will change the word from accepted to non-accepted, or vice-versa. In either case, the automaton fails to recognize the language.


A simple proof that decidability of typability in System F ($\lambda 2$) implies decidability of type checking?

As far as I know, showing that this direction is the hard part of Wells proof! At least this is what Pawel (Urzyczyn) explained to me a few years back.

Apparently it is not too hard to show that type checking is undecidable; the hard part is showing that this implies undecidability of type reconstruction! Indeed there are some cases in which the first is undecidable and the second decidable: see e.g. Dowek 1993.


What is the Turing degree of Kleene's O?

There is a talk given by Stephen Simpson, located here http://www.personal.psu.edu/t20/talks/pisa0104/talk.pdf, where he discusses the relative consistency strengths of various subsystems of second-order arithmetic $Z_2$. In particular, the theory $\Pi^1_1-CA_0$ denotes a subsystem of $Z_2$ whose set of true $\Pi^1_0$-consequences is of Turing degree $\emptyset^{(\omega^{CK}_{1})}$, which is the Turing degree corresponding to Kleene's $\mathcal O$. However, no proof is given, but I'm sure that one can be found in his bibliography for the talk (or perhaps even in his text on reverse mathematics http://www.personal.psu.edu/t20/sosoa/).

The relevant information in the PDF is on page 29.


Why do timeouts require synchronized clocks?

Note that the authors also assume the following:

  Crucial to our proof is that processing is completely asynchronous; that is, we make no assumptions about the relative speeds of processesor about the delay time in delivering a message.

The notion of "timing out processes" refers to the ability of knowing when to conclude that a process must have crashed.
If you have a completely asynchronous system, then it does not help to equip processes with perfectly synchronized clocks, as these cannot be used to distinguish a slow process from one that has crashed.


Shortest paths with structured dependence on earlier path

You can model the situation as a "regular language constraint path problem" as investigated in Barret, Jacob, Marathe 2000.
If you were interested in any shortest path (not just simple ones), this would solve your question:
First, transform your graph into a directed one that additionally has an edge per node (every node is split into two, one for the incoming edges and one for the outgoing edges, these are connected by a new edge, the node edge).  Now, you encode the markers and the functions as labels in an alphabet of size $2^K+2^{2K}$.  The constraining language now has to accept such a word if following your rules leads to the vector of all ones.  This is clearly a regular language because it can be accepted by an automaton with $2^K$ states.

For treewidth bounded graphs the above transformation and an algorithm for regular languages and simple paths (presented in the mentioned paper) allows to solve your question in polynomial time.

For more general graphs, finding a simple paths according to some fairly easy fixed regular language is NP-complete, which does not really imply anything for your question.
In particular the complexity for constant $K$ (and limited path-length) sounds like an interesting question to me.


SAT in finite model theory without order

The standard method for showing inexpressibility results for FO(PFP) (and for FO(LFP), by the way) is by using the fact that FO(PFP) is embedded in the finite-variable infinitary logic $\mathrm{L}^\omega_{\infty\omega}$. Here $\mathrm{L}^\omega_{\infty\omega}$ is the finite-variable fragment of $\mathrm{L}_{\infty\omega}$, where the latter is the class of (infinitary) formulas build from the atoms by means of negations, finitary or infinitary disjunctions and conjunctions of the type $\bigvee_i \phi_i$ and $\bigwedge_i \phi_i$, and existential and universal quantification. The logic $\mathrm{L}^k_{\infty\omega}$ is the collection of all formulas in $\mathrm{L}_{\infty\omega}$ that involve at most $k$ variables (quantified or not), and $\mathrm{L}^\omega_{\infty\omega} = \bigcup_k \mathrm{L}^k_{\infty\omega}$.

It is known that FO(PFP) $\subseteq \mathrm{L}^\omega_{\infty\omega}$ (see Theorem 7.4.2 in Ebbinghaus and Flum book "Finite Model Theory"). Thus, if you prove that something is not expressible in $\mathrm{L}^k_{\infty\omega}$ for any $k$, then you also prove that it is not expressible in FO(PFP).

Now, how does one prove inexpressibility results for $\mathrm{L}^k_{\infty\omega}$? By playing the $k$-pebble games. These are Ehrenfeucht-Fraissé-type of games where the number of rounds is unbounded but each player has at most $k$ pebbles that he can re-use (see Ebbinghaus and Flum book again for details).

After all this background, now we can show that CNF-SAT is not expressible in $\mathrm{L}^k_{\infty\omega}$ for any $k$. For every fixed $k$, we need to find a satisfiable CNF formula $F_k$ and an unsatisfiable CNF formula $G_k$ such that $F_k \equiv^k_{\infty\omega} G_k$, where $A \equiv^k_{\infty\omega} B$ means that the Duplicator has a winning strategy for winning the $k$-pebble game on the structures $A$ and $B$ (here we need to fix some sensible way of encoding CNF formulas as finite structures: let's say we encode them as their bipartite incidence graph with elements representing clauses on one side, elements representing variables on the other, and 2 types of binary relations indicating which variables appear in which clauses and under what sign). I claim that an explicit choice of $F_k$ and $G_k$ is possible. But instead I will give you an indirect proof.

It is trivial to see that $K_k \equiv^k_{\infty\omega} K_{k+1}$, where $K_a$ denotes the clique-graph on $a$ vertices. In particular EVENNESS is not definable in $\mathrm{L}^\omega_{\infty\omega}$. It is also known that CNF-SAT is NP-complete under first-order reductions (see Theorem 7.16 in Immerman's "Descriptive Complexity" book). Since trivially EVENNESS is in NP, this means that there is a first-order reduction from EVENNESS to CNF-SAT. Since first-order reductions (in pure first-order logic, without built-in linear-order or anything as it is the case in Theorem 7.16 from Immerman's book) preserve expressibility in $\mathrm{L}^\omega_{\infty\omega}$ backwards, the result follows: if CNF-SAT were expressible, EVENNESS would also be; a contradiction.


Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

What if you simply do the following: Given a graph $G = (V,E)$, construct another graph $G' = (V \cup U, E')$ by subdividing each edge of $G$ in 4 parts; here $U$ is the set of new nodes that we introduced, and $|U| = 3|E|$.

The graph $G'$ is bipartite. Moreover, if $G$ is planar and has max. degree 3, then $G'$ is also planar and has max. degree 3.

Let $D'$ be a (minimum) dominating set for $G'$. Consider an edge $(x,y) \in E$ that was subdivided to form a path $(x,a,b,c,y)$ in $G'$. Now clearly at least one of $a,b,c$ is in $D'$. Moreover, if we have more than one of $a,b,c$ in $D'$, we can modify $D'$ so that it remains a valid dominating set and its size does not increase. For example, if we have $a \in D'$ and $c \in D'$, we can equally well remove $c$ from $D'$ and add $y$ to $D'$. Hence w.l.o.g. we have $|D' \cap U| = |E|$.

Then consider $D = D' \cap V$. Assume that $x \in V$ and $x \notin D'$. Then we must have a node $a \in D'$ such that $(x,a) \in E'$. Hence there is an edge $(x,y) \in E$ such that we have a path $(x,a,b,c,y)$ in $G'$. Since $a,b,c \in U$ and $a \in D'$, we have $b, c \notin D'$, and to dominate $c$ we must have $y \in D'$. Hence in $G$ node $y$ is a neighbour of $x$ with $y \in D$. That is, $D$ is a dominating set for $G$.

Conversely, consider a (minimum) dominating set $D$ for $G$. Construct a dominating set $D'$ for $G'$ so that $|D'| = |D| + |E|$ as follows: For an edge $(x,y) \in E$ that was subdivided to form a path $(x,a,b,c,y)$ in $G'$, we add $a$ to $D'$ if $x \notin D$ and $y \in D$; we add $c$ to $D'$ if $x \in D$ and $y \notin D$; and otherwise we add $b$ to $D'$. Now it can be checked that $D'$ is a dominating set for $G'$: By construction, all nodes in $U$ are dominated. Now let $x \in V \setminus D'$. Then there is a $y \in V$ such that $(x,y) \in E$, and hence along the path $(x,a,b,c,y)$ we have $a \in D'$, which dominates $x$.

In summary, if $G$ has a dominating set of size $k$, then $G'$ has a dominating set of size at most $k + |E|$, and if $G'$ has a dominating set of size $k + |E|$, then $G$ has a dominating set of size at most $k$.

Edit: Added an illustration. Top: the original graph $G$; middle: graph $G'$ with a "normalised" dominating set; bottom: graph $G'$ with an arbitrary dominating set.


Average performance of universal computation

By $T(A)$ I will mean the runtime of $A$ on the empty input, and will define $T(A) = \infty$ if $A$ doesn't halt. By $|A|$ I mean the length of $A$ in bits.

What you are trying to calculate in part (1) is:

$$T = \sum_{A | T(A) < \infty} \frac{1}{2^{|A|}}T(A)$$

Where the fraction is the Chaitin probability of generating program $A$. For each length $n$ there is (at least) one machine $A_n$ such that for all halting $A$ with $|A| = n$ we have $T(A) \leq T(A_n) = BB(n)$. Here $BB$ is the relevant busy-beaver function, which grows faster than any computable function, in particular $BB(n) > 2^n$. From this we have:

$$T \geq  \sum_{n = 1}^{\infty} \frac{1}{2^n}BB(n) > \sum_{n = 1}^{\infty} 1$$

Thus your sum does not converge, and $T$ is not finite. I guess that answers the rest of your questions, too. If you want to achieve your goal, then you need to pick a better density function on programs, maybe something where probability of $A$ is proportional to say $\frac{1}{2^{BB(|A|)}}$. However, for learning more about this I recommend CS.SE.


I think we can just start with some base language $L$, then take $L_0 = L$ and $L_{s+1} = L_s \cup \{0,1\}^{s+1}$.

That is, each $L_s$ is the union of $L$ with all strings of length up to $s$. Each $L_s$ is at least as hard as $L$ but is no harder (in an asymptotic sense), assuming we can count to $s$.

I also thought about the opposite "limit", so each $L_{s+1}$ is contained in $L_s$, and $L = \cap_s L_s$ is easy while each $L_s$ is hard. But I think we could just start with a hard (but countable) language $L_0$ and just remove one word at each step; the intersection should be empty (every word is eventually removed).


How to become a Theoretical Computer Scientist

You asked three questions:

Q1 is really out of scope for this forum: it relates to GATE and how you gain admission to Indian grad schools.
Q2 I interpret as "do I need a graduate degree to study theoretical computer science". In general, of course the answer is "no", but the discipline of studying at the grad level (with the access to professors and other grad students) is hard to replace with a self-study unless you're supremely motivated.
Q3: of course you can apply to foreign universities for graduate studies: again, you might find it useful to peruse academia.stackexchange.com for a plethora of information on how to go about doing this.


Analysis of variables of varying numbers

"My question is what is the importance/effect of amino acid A occuring at position I in the sequence with respect to the model?"

I suggest Monotony and Surprise by Apostolico for the modeling of importance of words appearing at certain positions, or in certain patterns.  Beyond that, I'm not sure what you're looking for.


Linked List size in constant time or linear time

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


Hardness of Computing Weisfeiler-Lehman labels

The problem of deciding whether two graphs have equivalent labelings and hence also the problem of computing the canonical labeling are PTIME complete. See

M. Grohe,  Equivalence in finite-variable logics is complete for polynomial time.
Combinatorica 19:507-532, 1999. (Conference version in FOCS'96.)

Note that colour refinement equivalence corresponds to equivalence in the logic C^2.

-Martin


Measurable language which is not $\omega$-regular

A simple class of examples can be found by considering singleton languages $\{w\}$. These are measurable (Let $C_n(w)$ be the set of words agreeing with $w$ up to the $n$-th letter, then $\{w\}$ is the intersection of all $C_n(w)$). However, unless $w$ is eventually periodic, the language is not $\omega$-regular.

For a concrete example, consider the word $w=ababbabbba\dots$. If $w$ is accepted by a nondeterministic Büchi automaton $A$ with $k$ states, then while parsing the $n$-th block of $b$s, with $n>k$, $A$ needs to visit some state twice, so we can construct another word accepted by $A$ by pumping this block suitably. Therefore no automaton recognizes $\{w\}$.


On a Linearization of the Quadratic Assignment Problem

I don't recall having seen this encoding anywhere in the literature. It would not be surprising if indeed no such academic literature exists, though.

First of all note that your trick to translate a binary quadratic programming problem to an integer programming one is pretty straight-forward. You can find a casual mentioning it on the web from 2005 here.

But there is more to it. Solving the Quadratic Assignment Problem is known to be NP-complete already, and you reduce it to an NP-hard problem. So in theory, you don't gain anything.

In practice, however, you might. But unless you have evidence that the ILP instances that you get are particularly easy to solve for modern solvers, I wouldn't use your encoding, and here is why: the efficiency from ILP solvers comes from the fact that they can use the convexity of the solution space to their advantage. This allows to perform a branch-and-bound search on the feasible solutions while using an LP solver to find not-quite-yet-valid candidate approximate solutions. But in your encoding, all values are binary! So the ILP solver can't really take advantage of it.

If we now have a look at state-of-the-art other methods to solve the problem, there seem to be both exact and heuristic methods (I found this page by following links from Wikipedia). One of the methods is reported to work well for problems with $n \leq 15$. For such instances, your encoding requires $15 \cdot 15$ variables of the type $x_{ij}$, and $15^4$ variables of the type $y_{ijkl}$. Even though we can reduce this number of variables by a factor of $16$ (I think), that is an awful lot of variables for an ILP problem where the ILP solver cannot really take advantage of the structure of the problem. So it is possible that the approach that you mention has been invented before but did not make it into any publication as it does not perform well.


Does the System F with pairs have the strong normalisation and subject reduction properties?

The treatment of pairs given by encoding, such as that in Proofs and Types, isn't what you usually want since they aren't "surjective pairs", i.e., there is no eta rule.  Let's call surjective pairs, products.

An extension of system F with products and unit is given in: Di Cosmo, 1995,  Isomorphisms of types: from lambda-calculus to information retrieval and language design,  Birkhauser: Basel.


Quantum polynomial hierarchy vs counting hierarchy

I was quite surprised as well to not find this hierarchy in the literature, so I wrote my graduate thesis about it. It will be available online soon, at which point I will update this answer with a link to it. I was able to prove some interesting theorems about it.

Theorem For every $i$, $\Sigma_i^{\mathsf{BQP}}\subseteq C_i^\mathsf{P}$, where $C_i^\mathsf{P}$ is the $i$-th level of the counting hierarchy. So the whole hierarchy is contained in the counting hierarchy.

Proof Trivially from $QMA\subseteq PP$. $\square$

Theorem If $\Delta_i^{BQP}=\Sigma_i^{BQP}$ then $BQPH=\Delta_i^{BQP}$.

Proof Excercise for the reader.

Theorem If $QMA=PP$ then $PH\subseteq QMA$ and indeed $PH^{PP}=QMA$.

The first part of this theorem was originally by Vyalyi [4], but his proof is six pages of algebra, whereas new ideas that originated from thinking about your hierarchy allow me to get there in just a few lines:

Proof I prove a new theorem: $QMA\cap coQMA=P^{QMA\cap coQMA}$. This gives us $QMA=P^{QMA}=P^{PP}\supseteq PH$ by Toda. $\square$

For the new part, $PH^{PP}=QMA$, you will have to read my thesis. There's no obvious analogue of Toda's theorem. The reason is that the critical ingredient $QMA\subseteq BPP^{\oplus P}$ seems hard in the quantum case, whereas classically $NP\subseteq BPP^{\oplus P}$ follows trivially from Valiant-Vazirani, because here we don't have a way to "count" solutions. Even if you take $QCMA$ instead of $QMA$, there's the inconvenience that a QCMA protocol can behave arbitrarily on bad certificates to yes-instances. To see what I mean, start with [1].

There's also no obvious analogue of a Karp-Lipton collapse, or Kannan-type circuit lower bounds. Recall that in the classical case, we have

Theorem [3] For every $k\in\mathbb{N}$, there is a language in $\Sigma_4^{P}$ that requires circuits of size $\Omega(n^k)$.

The reason there's no(t yet) a theorem replacing every $P$ in this theorem with $BQP$ is that a critical ingredient in his proof is that he is able to (non-deterministically) guess a circuit and then evaluate that circuit, i.e. compute the circuit's output on an input. Sure, we can guess a (description of a) quantum circuit, but we can only say that we evaluate it if it is a bounded-error circuit, and verifying this is a $\# P$-Hard problem.

Scott Aaronson and Andy Drucker prove something along the lines of a "quantum PH", going only to the second level:

Theorem [2] If $NP\subset BQP_{/qpoly}$ then $\Pi_2^P\subseteq QMA^{PromiseQMA}$.

When I asked Scott Aaronson, he said that people had been thinking about this hierarchy for 15+ years, but nobody had published it because nobody had proved anything non-trivial about it. Here's to hoping you or I change that.

Bonus Theorem! If $QMA=coQMA$ then $PH\subseteq QMA$. Just for you, because you made it all the way to the end of a long answer.

[1] Aharonov, Dorit, et al. "The pursuit for uniqueness: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings." arXiv preprint arXiv:0810.4840 (2008).

[2] Aaronson, Scott, and Andrew Drucker. "A full characterization of quantum advice." Proceedings of the forty-second ACM symposium on Theory of computing. ACM, 2010.

[3] Kannan, Ravi. "Circuit-size lower bounds and non-reducibility to sparse sets." Information and Control 55.1-3 (1982): 40-56.

[4] Vyalyi, Mikhail N. "Qma= pp implies that pp contains ph." In ECCCTR: Electronic Colloquium on Computational Complexity, technical reports. 2003.


Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994

Let $f\colon \{0,1\}^n \to \{0,1\}$, and let $g\colon \{0,1\}^n \to \{0,1\}$ be chosen uniformly. Then $\Pr[f=g] \sim 2^{-n}\mathrm{Bin}(2^n,1/2)$, and so a Chernoff bound shows that
$$
\Pr_g[\Pr[f=g] \geq \tfrac{1}{2}+\epsilon] \leq e^{-2\epsilon^2 2^n}.
$$
Now suppose that $f$ goes over all $2^{O(n^2s)}$ circuits of size $s$. The probability that one of them has correlation at least $\frac{1}{2}+\epsilon$ with $g$ is at most $e^{O(n^2s) - \Omega(\epsilon^2 2^n)}$. If $s = o(\frac{\epsilon^22^n}{n^2})$ then this probability is $e^{-\Omega(\epsilon^2 2^n)}$, which is smaller than $\epsilon$ for $\epsilon = \omega (\sqrt{n/2^n})$. We obtain $\sqrt{n/2^n}$ by approximately solving $e^{-\epsilon^2 2^n} = \epsilon$: rearranging, we get $\frac{\epsilon^2}{\log(1/\epsilon)} = 2^{-n}$, which shows that $\epsilon \approx 2^{-n/2}$ and so $\log(1/\epsilon) \approx n$. Plugging in the approximation for $\log(1/\epsilon)$, we see that $\epsilon \approx \sqrt{\log(1/\epsilon) 2^{-n}} \approx \sqrt{n/2^n}$.

This proves the first corollary. For the second corollary, substitute $n := \log (n/2)$.


Is balanced Hamiltonian cycle NP complete on maximal plane graphs?

Yes, it is still $NP$ complete. This is because of:

Claim: All Hamiltonian cycles on maximal planar graphs are balanced.

Proof: This is a special case of Grinberg's theorem: https://en.wikipedia.org/wiki/Grinberg%27s_theorem


maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph

It's NP-complete by a reduction from vertex cover.

Let $G$ be a graph in which an optimal vertex cover is hard to find.
Make a new graph $H$ with twice as many vertices, by attaching a new degree-one vertex to each vertex of $G$. Turn $H$ into a metric space by making the distance between adjacent vertices equal to $1$ and the distance between non-adjacent vertices equal to $2$. For this metric space, the weight of a minimum spanning tree of an induced subgraph equals the number of vertices plus the number of connected components of the subgraph minus one.

We can assume that the subgraph with the heaviest MST includes all of the degree-one vertices, because adding one of these vertices to a subset can never decrease the number of components. So the vertices that were removed to form the subgraph are a subset of $G$. We can assume also that these removed vertices form a vertex cover of $G$. For, if some other induced subgraph is formed by removing vertices that do not form a vertex cover, and $uv$ is an edge that is not covered, then removing $v$ leads to an induced subgraph that is at least as good: it has one less vertex but one more connected component, created by the degree-one vertex of $H$ that was attached to $v$.

So the optimal subgraph of $H$ is formed by removing a vertex cover from $G$. Such a subgraph will have exactly $n$ components (one for each degree-one vertex added to $H$, either by itself or connected to a vertex of $G$), and a number of vertices equal to $2n-k$ where $n=|V(G)|$ and $k$ is the size of the cover. Thus, the weight of its MST will be $3n-k+1$. To maximize this, we must minimize $k$.


It is not known if there is an $\varepsilon > 0$, $c > 2$, and $k > c$ such that $(c,k)$ hyperclique is in $n^{k-\varepsilon}$ time. Note that the case of $k \leq c$ is trivial. For years I have communicated this problem to many people, and taught it in cs266 at Stanford, due to its connection to solving $k$-Sat. (Several open problem sessions at workshops probably recorded this.)  Here are a few things I know:

I proved several years ago that solving $4-cycle$ on $n$ node graphs in $n^{2-\varepsilon}$ time implies $(3,4)$ hyperclique in $n^{4-\varepsilon}$ time. Haven't published it.

UPDATE (Aug 2019) the aforementioned result and some generalizations now appear in the paper

Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams:
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. SODA 2018: 1236-1252

If you can solve $(3,4)$ hyperclique as indicated above, then Max-3-Sat can be solved in strictly less than $2^n$ time. Similarly, solving $(k,k+1)$ hyperclique would yield a faster $k$-Sat algorithm. So if you believe Strong ETH then there is an obvious limit here. The reduction is a natural generalization of the reduction from Max-2-Sat to triangle finding ($(2,3)$ clique) from ICALP'04 and my PhD thesis.

You can solve $(c,k)$ hyperclique in $n^k/(\log n)^{\Omega(k)}$ time by generalizing the paper Efficient Algorithms for Clique Problems.


See Mike Domaratzki's paper, State complexity of proportional removals

http://dl.acm.org/citation.cfm?id=782471

http://www.cs.umanitoba.ca/~mdomarat/pubs/sc_jalc.ps


Shortest formula for an n-term monotone CNF

You can get an $\Omega(n^2/\log n)$ lower bound using a counting argument: there are $exp(n^2)$ $n$-term CNFs on $n$ variables (this is easy but requires just a little care as to make sure that there is no over-counting), but there are $exp(s \log s)$ formulae (or even circuits) of size at most $s$.

It seems that winning the last $\log n$ factor will be hard since it would require proving a quadratic lower bound on formula size, and my guess is that the few existing techniques for this don't suffice.  $O(n^2/\log n)$ may even be the right answer -- at least for circuit size -- using some four-Russian-like technique.


Trampoline that automatically balances heap and stack

Is it possible to make a "smart" trampoline function that takes two forms of a function, a trampolined version and a non-trampolined version, and chooses (or predicts) the most efficient strategy?*

Yes, it's possible to do things like this, but if you control the compiler, it's usually faster and easier to do something else. The main exception is when you are writing parallel code.

Trampolining style essentially does two things.

First, you do a continuation-passing-style transformation to make the continuation explicit as a data structure. However, if you directly represent continuations as functions, the standard calling conventions mean that you will blow the stack. This is because programs in CPS never directly return -- they always pass control to their continuation.
So instead of representing continuations as functions, you represent continuations as resumptions. A resumption is a data structure representing a computation, which lets you evaluate a bit at a time until it is finished. That is, resumptions may be seen as a datatype declaration such as:

type 'a resumption = Done of 'a | Wait of (unit -> 'a resumption)

So a value of type t resumption is either a value Done v containing a value v of type t, representing a finished computation, or it is a value Wait thunk, where thunk is a function that will do some work and hand you back a new resumption representing a bit more progress towards the answer.
Once you represent continuations as resumptions, you can write a scheduler which runs in a while-loop, and incrementally forces the resumption. Since the scheduler runs in a loop, it won't automatically blow the stack. I call this loop a scheduler because precisely the same approach of using resumptions is used in implementations of green/lightweight threads.

Implementing resumptions naively is slow, because the continuations in most programming languages are used in highly stylized ways. That is, in most languages you can implement continuations as a single imperatively-updated stack, and the overhead of trampolining simply arises from the fact that a linked list of thunks is a less efficient representation than a mutable stack. So compiler writers often use resumption-based intermediate forms, but implement them using better data structures. (And as a programmer, you can often use an optimized continuation representation "by hand".)

Papers you might want to look at:

Ganz, Friedman and Wand's 1999 ICFP paper, Trampolined Style

This is probably the best survey paper on trampolining and how it works.
Wand's 1980 JACM paper, Continuation-Based Program Transformation Strategies

This is one of the fundamental papers on using custom data structures to represent continuations, and how it can make algorithms radically more efficient. The notation is kind of old-fashioned and clunky, but once you get past that, it's extremely accessible and mind-blowing. Highly recommended!
Hieb, Dybvig and Bruggeman's 1990 PLDI paper, Representing Control in the Presence of First-Class Continuations

This paper gives a nice example of just how far compiler writers will go to implement continuations efficiently.
Appel's 1993 book, Compiling with Continuations

EDIT: This is not out of print, and if you can afford it, it's a book-length explanation.
Abramsky's CONCUR 1996 paper, Retracing Some Paths in Process Algebra

This paper gives a theoretical introduction to the application of resumptions to concurrency.
Acar, Charguéraud, and Rainey's 2011 OOPSLA paper, Oracle scheduling: controlling granularity in implicitly parallel languages

This paper implements your suggestion of using two versions of the same function, in the context of parallelizing divide-and-conquer algorithms. Basically, the idea is that the optimal point to switch from spawning new tasks for subproblems to doing it sequentially depends a lot on details like the amount of parallelism in your hardware, the cost of thread spawning, and how much work each recursive call will do. So if you write a function to the scheduler can use to estimate how much work is left, it can automatically choose the best point to switch.


Definitional function extensionality for functions out of $\mathbf{2}$

Yes, you can. However:
The complexity issue is bad -- testing whether two $2^n \to 2$ functions are equal is NP-complete, and to make it bearable in practice would require some clever integration with a SAT solver or BDD engine in the implementation of definitional equality.
Moreover, you can potentially defeat such smartness by asking questions about Boolean functions which are free variables. For example, for any $f : 2 \to 2$, it is extensionally the case that $f(f(f(x))) = f(x)$, which you establish by exhaustive enumeration.
You can find some links to papers with algorithms for coproduct in this link:
Programming languages with canonical functions


In a triangle-free graph, a completeness tree must be a Hamiltonian cycle (minus one of its edges). ISGCI says Hamiltonian cycle is NP-complete in triangle-free graphs. Therefore, so is finding a completeness tree (regardless of any restriction on max number of leaves).


Approximation algorithms for dominating set problem

The class of line graphs can be characterized by a finite family of forbidden induced subgraphs (Beineke).  A dominating set in a line graph G corresponds to an edge dominating set of the root graph of G (and vice versa), and the size of minimum edge dominating set can be approximated by factor of 2 in polynomial time.

http://en.wikipedia.org/wiki/Line_graph
http://en.wikipedia.org/wiki/Edge_dominating_set


Optimization Problem on a Directed Graph

lemma 1. The posted problem (as I understand it) is NP-hard, even on DAGs,

Proof. The proof is by reduction from Subset Sum.  Given a Subset Sum instance with $n$ positive integers $x_1, x_2, \ldots, x_n$ and target $T$, the reduction produces the following instance of your problem.  The instance will have a minimal solution (one with objective equal to the sum of the activation values -- the minimum possible) if and only if some subset of the $x_i$'s sums to $T$.

Let the $x_i$'s be $b$-bit integers for some $b$, so the input instance has size polynomial in $n$ and $b$ and each $x_i$ is an integer in $\{1,2,\ldots, 2^b\}$.

Construct a "tower" gadget with two leaves $u_0, w_0$ with activation 1.  For each $i\in\{1,2,\ldots, b\}$, add two vertices $u_i, w_i$ each with activation threshold $2^i$ and two incoming edges: $(u_{i-1}, u_i)$, $(u_{i-1}, w_{i})$, $(w_{i-1}, u_i)$, $(w_{i-1}, w_i)$.  In any feasible solution to the instance (so far), each such vertex $u_i$ and $w_i$ will have to use both its incoming edges, and will have incoming activation value exactly equal to its activation threshold $2^i$.

Next, for each integer $x_i$ in the given Subset Sum instance, construct a vertex $X_i$ with activation threshold $x_i$, with edges from every $u_j$.  In any minimal solution, each $X_i$ will use just those incoming edges that represent the binary representation of $x_i$, thereby achieving incoming activation value equal to $x_i$ (and this is always possible).

Finally, construct a "root" vertex $R$ with activation value $T$ (the Subset Sum target) and edges from every vertex $X_i$.  There will be a subset of edges into $R$ to use to achieve activation value $T$ if and only if there is a subset of the $x_i$'s that sums to $T$.  $~~~\Box$

What am I missing?  As I understand the problem, showing NP-hardness seems like a nice homework exercise...

Given that Graphman was last active in 2016, perhaps clarification is not to be had.


Generalization of locally bounded treewidth graphs

The concept of exploiting properties that a graph possesses locally can be taken even further. Dawar, Grohe and Kreutzer in Locally Excluding a Minor considered classes of graphs that locally exclude a minor and Dvorak, Kral and Thomas in Deciding first-order properties for sparse graphs considered classes of graphs that have (locally) bounded expansion.

Both of those classes are subsumed by classes of nowhere dense graphs, introduced by Nesetril and Ossona de Mendez.

Grohe announced this week at the Highlights conference that Grohe, Kreutzer and Siebertz. have proved that every property of graphs definable in first-order logic can be solved in almost linear time on nowhere dense classes of graphs. This implies many fixed-parameter tractability results on nowhere dense graphs, e.g. for the (connected) dominating set and digraph kernel (both parameterized by the size of the solution), Steiner tree (parameterized by the size of the tree) and circuit satisfiability (parameterized by the depth of the circuit and the Hamming weight of the solution).


What is the etiquette of naming concepts after people?

It is best to spend some time researching to ensure that you associate the correct person with the idea and mention related ideas by others. You wouldn't want a misnomer to be called a Squark - like Squark says: "Be LessWrong". :)
By simply explaining the concept and mentioning that you believe it was first developed by a particular person you permit others to write to you, the author, and correct you with earlier references, this comes across as better than expounding falsehoods and detracting from the creditability of your work.
When the person whom you propose to associate with the idea is available (alive, and replies to email) it is useful and respectful to contact them; they may be planning a retraction or know of another whom is actually the developer, they mearly refined (or copied) the idea.
The Wikipedia section on concepts has this to say:

Concepts
Buildings, such as the Trump Tower, and companies, like the Ford Motor Company, are often named for their founders or owners. Biologic species and celestial bodies are frequently named for their discoverers. Alternatively, their discoverers may name them in honor of others. Occasionally, material goods, such as toys or garments, may be named for persons closely associated with them in the public mind. The teddy bear, for example, was named for President Theodore "Teddy" Roosevelt, because of a popular story in which the then-President objected to cruel treatment of a bear by hunters.
The fedora hat may be considered the "namesake" of a fictional character, Princess Fédora Romanoff, from an 1887 play, Fédora, by Victorien Sardou. In her famous portrayal of that character, Sarah Bernhardt wore a soft felt hat with a center crease, which became known popularly as a "fedora".


Cook reduction for search problems, by universal property?

(2.) implies (1.) by a standard compactness argument.

First note that it suffices to exhibit a Cook-reduction $M$ from $R$ to $S'$ for any relation $S'$ such that $S(x,y)\iff S'(x,y)$ for all but finitely many values of $x$. This is because we can then give a Cook-reduction from $R$ to $S$ by simulating $S'$ using $S$.

Suppose for contradiction that there is no such Cook-reduction. Let $M_1,M_2,\dots$ be a enumeration of polynomial-time oracle Turing machines. Pick a sequence $S_1\supseteq S_2\supseteq \dots$ as follows. Let $S_1=S$. Suppose we have constructed $S_k$ such that $S_k(x,y)\iff S(x,y)$ for all but finitely many $x$. We know that $M_k$ is not a Cook-reduction from $R$ to $S_k$: there is some $f$ solving $S_k$ and some $x$ such that $R(x,M_k^f(x))$ does not hold. Set $S_{k+1}$ to be the relation that agrees with $f$ on all the oracle queries used by evaluating $M_k^f$ on $x$, and otherwise agrees with $S_k$.

Pick a function $f$ solving $S_k$ for all $k$. Clearing $S\in\mathsf{FP}^f$, but by construction $R\notin\mathsf{FP}^f$.


Is Deolalikar's 2010 proof that $P \ne NP$ correct?


A clear and rigorous explanation of critical pairs and the Knuth-Bendix completion algorithm?

The two obvious references are:

Chapter 7 of Term Rewriting and All That, notable for its pedagogy and accessible examples

Chapter 7 of Term Rewriting Systems, notable for its completeness and attention to detail, though a bit dated at this point I guess.

Note that neither refers to completion as "Knuth-Bendix" completion in the index, since the science of completion has come a long way since it was first introduced. This survey by Dershowitz and Jouannaud might be a bit more historical.
It might help to understand what your needs are, since the field is vast, and somewhat technical. Are you trying to use a completion algorithm? Implement it? Adapt it to a specific setting?


Proving that inclusion is antisymmetric in Coq

Theorem inclusion_is_antisymmetric : forall x y:set, subset x y /\ subset y x -> x = y.
Proof.
  firstorder using equality.
Qed.


Are there good locally decodable _erasure_ codes

Locally decodable codes and locally decodable erasure codes are qualitatively equivalent. Both imply $\Omega(m)$ many disjoint $q$-tuples from which one can recover a given message coordinate, where $m$ is the codeword length and $q$ is the query complexity. A formal argument appears in Section 3.4 of Kerenidis and de Wolf's paper.


What games best represent well-known computer science problems?

If by 'show computational theories in them' you mean correspond to complexity classes or fit nicely within complexity classes, then you first have to generalize the game to depend on some parameter $n$. For instance, for a game of Chess with a clock (and maybe a 50-move no checkmate rule) on an 8-by-8 board there are only a finite number of possible games. Thus, everything about the game is solvable in $O(1)$.

To overcome this, complexity theorists usually define a generalized game. So for instance a variant of chess on $n$-by-$n$ boards, then standard complexity questions can be asked. In that case, a lot of the 'fun' two player games become PSPACE-complete or EXPTIME-complete. For instance Reversi and Hex are PSPACE-complete and Chess, Go, and Chinese Checkers are EXPTIME-complete. You can learn more on wikipedia

In terms of NP-completeness, sometimes end-games become NP-complete. In particular, in a really fun game called phutball deciding if a player has a win in one move is NP-complete. Solving who will win the game in general is PSPACE-hard given arbitrary initial configuration


I do not quite understand the question because you do not define some of your paremters (what are $p$ and $q$?). But let me try to clarify things. Let $N$ be the true number of distinct items.

First Flajolet's guarantee for Wegman's algorithm is that, if the space used is $n$ words, then the estimate $X$ produced by the algorithm satisfies
$$
\sqrt{\mathbb{E}[(X - N)^2]} \leq \frac{1.2}{\sqrt{n}}N.
$$

Your suggestion is to sample at a rate $p$ from the $N$ different distinct items. I.e., you make a pass over the sequence of item identifiers and you keep each identifier in memory with probability $p$. Let the number of items stored in memory be $n$. Then the expected value of $n$ is $pN$, and the variance of $n$ is $p(1-p)N$, so we have
$$
\sqrt{\mathbb{E}\left[\left(\frac{n}{p}-N\right)^2\right]} =\sqrt{\frac{1-p}{pN}}N = \sqrt{\frac{1-p}{\mathbb{E}[n]}}N.
$$

So you are right that this is in some sense comparable with the guarantees for adaptive sampling (as well as those for the Flajolet-Martin probabilistic counting algorithm). However, the issue is that without knowing $N$, you do not know ahead of time what your space complexity $n$ will be, even in expectation. Or to put it another way, you do not know what to set $p$ to in order to make the space complexity acceptable.

A natural fix is to start with some sample rate $p$, say $p = 1$, and once your memory fills up, you lower $p$. This is essentially the adaptive sampling algorithm.

The simple sampling algorithm you suggest can be useful to refine a rough estimate of $N$. For example, you can use adaptive sampling or Flajolet-Martin to get a constant factor approximation to $N$, and then use that approximation to set $p$ in the Bernoulli sampling strategy. See this nice paper by Daniel Kane, Jelani Nelson, and David Woodruff, where they use this idea and a lot more to get an optimal space algorithm for the distinct items problem. The paper also gives references to much of the more important work on this problem.


Best known joint containments for/by NP and Parity-P?

By Valiant-Vazirani, NP is contained in BP dot Parity-P (which obviously contains Parity-P).
Moreover, Toda showed that PH is in BP dot Parity-P which is in P^(#P) (which is in PSPACE).

For lower bounds, I think both classes contain a class known as FewP which contains UP and is like NP but you ask that strings in the language have at most polynomially many accepting paths.

[Update: corrected typo BPP instead of BP]


How powerful are nondeterministic constant-depth circuits?

A polynomial amount of nondeterministic bits is enough to encode the computation of a nondeterministic polynomial time algorithm. The only thing we need is to check if a given string is an accepting computation which is syntactic task that can be performed by a polynomial-size $\mathsf{AC^0}$ circuit (in fact a polynomial size CNF can do this).

Another way to look at this is to consider the Tseitin translation from arbitrary circuits to CNFs which has a polynomial size increase and uses only polynomially many new propositional variables.

If you look at the $\mathsf{NP}$-compeleteness proof of CNF-SAT (or 3SAT) you see that the part that checks if a given CNF is satisfied by a given truth assignment can be computed by an $\mathsf{AC^0}$ circuit (IIRC $\mathsf{AC^0_d}$ circuits can be evaluated by an $\mathsf{AC^0_{d+1}}$ circuit).


What are some results on algorithms that estimate polynomials over a given set of points?

Not really what you asked for, but your question was a bit open, so maybe this will interest you.

For the specific problem of estimating infinite polynomials (generating functions), $A(z) = \sum_{n=0}^\infty a_n z^n$, with a combinatorial origin, there is a recently published paper, "Algorithms for combinatorial structures: Well-founded systems and Newton iterations" by Pivoteau, Salvy and Soria. I believe (though I might be slightly off) it shows that approximations can be computed in complexity that is quadratic in the required precision. The set of points is the radius of convergence, and in particular the singularity of the generating function.


Hardy, in his classical book Orders of infinity, considered the class of logarithmic-exponential functions. This is a rather general class of functions, which is the minimal set of functions containing $\mathbb{R}$ and $x$, closed under addition, multiplication and division (unless it has infinitely many zeroes), closed under $\exp$ and $\log|\cdot|$ (same constraint), and closed under solution of polynomial equations (i.e. the function satisfying $f(x)^5 + f(x) = x$ is in the family). Hardy showed that any two such functions can be compared asymptotically. I'm not sure if the proof is algorithmic, but it is worth checking.

Boshernitzan extended this class even further, and doubtlessly there is other work on the subject.


Exact number of comparisons to compute the median

Kenneth Oksanen has published an expanded table of values up to $n=15$, based on his own computer search.  Okansen also provides descriptions of the optimal comparison trees for most of the values he reports.  Here's a screenshot of his table:

Thanks to @MarkusBläser for the lead!


Definition and Computational Model of EnumP

First, you have to know that enumeration complexity is not as cleanly defined as other fields of complexity theory. People are still looking for the right definitions. Notions of reductions or completeness for example do not seem to generalize well. You will then have plenty of different names and notations for the same thing depending on the authors. For general overview of these notions, you can read the preliminaries of several thesis: Wojciech Kazana [4], Yann Strozecki [5] etc. The preprint [2] you cite is still a work in progress.

Now a clarification: Valiant does not use his Counting Turing Machines for defining P-enumerable. He uses them to define #P then reverts back to deterministic TM and defines P-enumerable. He is not really interested in enumeration complexity. He only vaguely defines it (he says that the set can be enumerated without defining it formally) to show that some #P-complete problems can still be enumerated (using fact 7, also known as "flashlight method" for enumeration).

Finally the answer. EnumP and P-enumerable are different indeed but not comparable. EnumP only says that the predicate you want to enumerate behave "nicely", that is, you can verify in PTIME that the outputs of your algorithms are indeed solutions. It does not says anything on the complexity of the problem of enumerating.

The notion of P-enumerable of Valiant corresponds to what is called Output polynomial algorithm, that is, you can enumerate the set in time polynomial in its size and the input size. This is what is called $OutputP^F$ in [2], as the "uniformity" condition (that the predicate should be in EnumP) is not present in Valiant's work. For example $SAT(\phi) = \{\tau \mid \tau \models \phi \}$ is in EnumP but not P-enumerable. See Proposition 7 of [2] for example to see a problem P-enumerable but not in EnumP.

As for the choice of RAM over TM for enumeration, the polynomial time is usually not affected by this choice, so this does not make a huge difference for complexity classes. However, such a choice is common in enumeration complexity as people are often interested in constant or linear delay, which is more robust on RAM than on TM (see for example, Wojciech Kazana thesis [4] for constant delay or the work of Étienne Grandjean for consideration on the class of linear time solvable problem).

[4] http://www.lsv.ens-cachan.fr/~kazana/PAPERS/Wojciech_Kazana_16Septembre2013_QueryEvaluationWithConstantDelay.pdf

[5] http://www.prism.uvsq.fr/~ystr/these_strozecki


Problem of graph bi-partition (related to graph isomorphism)

Your problem is NP-complete. Two-colorable perfect matching (which is NP-complete even when restricted to cubic planar graphs) is reducible to your problem. Take $H_1$ and $H_2$ to be perfect matchings each of $|V|/2$ nodes. Then your problem is to find 2-coloring of $V$ such that each color class induces a perfect matching.


I believe the answer to your question is "no" because an equivalent condition would imply a polynomial time solution to GI.

For $A$, the adjacency matrix of the graph $G$, note that the number of paths from $i$ to $j$ of length $k$ is $(A^k)_{i, j}$ (with repetition of vertices and edges allowed).  For two graphs $G_1$ and $G_2$ (with adjacency matrices $A_1$ and $A_2$) and $k \ge 1$, if you sorted the elements of $A_1^k$ and $A_2^k$ then in order for $G_1$ to be isomorphic to $G_2$, it is a necessary condition that the lists be identical for all $k$.

I believe your conjecture is equivalent to:

If the sorted lists of elements of $A_1^k$ and $A_2^d$ are identical for $k = 1$ to $n - 1$ (upperbound on the longest path with non-repeating vertices) then $G_1$ and $G_2$ are isomorphic.

So to solve GI, one only has to perform $n - 1$ multiplications of $n \times n$ matrices (and a little extra time to sort and compare $n^2$ elements).  This would take less than $n^4$ time.

I admit two possible flaws in my argument.  First, it is totally possible that GI has a polynomial time algorithm and that we just discovered it together, just now (hooray, we're famous!).  I find this highly unlikely.  Second (and much more probable), what I've proposed is not actually equivalent to your conjecture.

Final thought.  Have you tried this out for all, say, 3-regular graphs for size 8 or so?  I would think that if your conjecture is false, that there should be a counter example in 3-regular graphs of fairly small size.


Configurations from arrangement of lines

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

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

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

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


Are there nice generalizations of SPQR trees to k-connected components for k>3?

For edge connectivity rather than vertex connectivity, there's always the Gomory–Hu tree.


Polynomial-time distinguishability threshold of planted clique

My understanding is that no algorithm is known for finding cliques with polynomially high success probability for $k=O(n^{1/2-\epsilon})$.  I think it is believed that getting a polynomially large success probability is not possible.

The reason for my holding this belief is that after a clique-finding algorithm outputs a clique, one can check if it succeeded.  So if the algorithm fails, it can be re-run until the clique is found, which would yield polynomial time algorithm for polynomially high edges.  Of course, this isn't quite right -- an algorithm may be deterministic and its success could depend on the random target graph, and so this trick wouldn't work.  So this is more intuition than proof.

The paper of mine you cite gives concrete lower bounds, but only for a restricted class of algorithms.


Two paper appear to imply collapse via coloring $P_5$-free graphs

One of those papers is about k-colorability and the other of

those papers does not specify a constant number of colors.

(For a similar example, consider k-variable-SAT versus SAT.)


How many instances of 3-SAT are satisfiable?

A long history of work on phase transitions in SAT has shown that for any fixed $n$, there's a threshold parametrized by the ratio of number of clauses to $n$ that decides satisfiability. Roughly speaking, if the ratio is less than 4.2, then with overwhelming probability the instance is satisfiable (and so a huge fraction of the number of instances with these many clauses and variables are satisfiable). If the ratio is slightly above 4.2, then the reverse holds - an overwhelming fraction of instances are unsatisfiable.

The references are way too many to cite here: one source of information is the book by Mezard and Montanari. If anyone has sources for surveys etc on this topic, they could post it in comments or edit this answer (I'll make it CW)

References:
 - Achlioptas survey
 - Where the really hard problems are
 - Refining the phase transition in combinatorial search


Consequences of Complete problems for NP intersects coNP

This is a (wide) open problem; as in, we know almost nothing. Specifically, because of the trickiness in proving $NP \cap coNP$-complete problems, we need very different proof techniques than currently exist. As such, a discussion of consequences should reasonably include a tangent on "What would it mean to have such powerful, new proof techniques?"

For a relatively recent discussion of the topic, there is David Johnson's 26th NP-Completeness column in the ACM Transactions on Algorithms from 2007 (PDF). Allow me to paraphrase some of what David says regarding the question of proving $NP \cap coNP$-complete problems' existence and add my thoughts:

Currently, we only have "weak," natural candidates for membership in $NP \cap coNP - P$ in the sense that the strongest evidence for their membership is that we haven't managed to find a polynomial time algorithm for them yet. He lists a couple candidates: SMALL FACTOR, SIMPLE STOCHASTIC GAME, and MEAN PAYOFF GAME. Some of the extra "weirdness" of these problems comes from the best heuristic run times for solving them, e.g. SMALL FACTOR, aka INTEGER FACTOR $\le k$, has a randomized time complexity of $poly(n) 2^{\sqrt{k log(k)}}$. (If complete problems exist in $NP \cap coNP - P$, then is such sub-exponential (neither purely exponential, nor quite polynomial) runtime endemic of the class?)

So specifically, we would want to prove something like: problem A is only in $P$ iff $NP \cap coNP = P$, i.e. a completeness result like Cook's theorem for 3SAT and $NP$. For $NP$, such proofs universally involve polynomial-time reductions (and fix your favorite, additional restrictions, e.g. Cook-reductions, Karp-reductions). As a result, under polynomial-time reduction techniques, it must be the case that there exists a polynomial-time recognizable representation of the class. For $NP$, we can use non-deterministic Turing machines that halt within a polynomial, $p(|x|)$, number of steps. As David points out, we have similar representations for other classes (where the status is more clear) such as $PSPACE$ and #$P$.

The difficulty, however, with providing a similar representation for $NP \cap coNP$ is that the "natural" analog allows us to embed the Halting Problem within the representation and is therefore undecidable. That is, consider the following attempt to represent $NP \cap coNP$ with two non-deterministic Turing machines that, purportedly, recognize complementary languages:

Question: Does a Turing Machine $M^*$ halt on input $x \in {0,1}^n$?

Construct two linear-time Turing machines $M_1$ and $M_2$ as follows. On input $y$, $M_1$ reads the input and always accepts. $M_2$ always rejects unless $|y| \ge |x|$ and $M^*$ accepts $x$ in steps $\le |y|$.

Therefore, $M_1$ and $M_2$ accept complementary languages iff $M^*$ does not halt on input $x$. Therefore, by contradiction, deciding if two polynomial-time Turing machines accept complementary languages is undecidable.

So, the "natural" representation of $NP \cap coNP$ problems is not polynomial-time recognizable. The question remains: How do you represent $NP \cap coNP$ problems such that they are polynomial-time recognizable?

There has been no significant work done on this issue, but its successful resolution is necessary to prove completeness in $NP \cap coNP$. Hence, I claim that the existence of a proof technique that can resolve the completeness of $NP \cap coNP$ will be the bigger story here -- not the "automatic" results of $NP \cap coNP$-complete problems (e.g. complexity classes, perhaps, collapsing) that we are already aware of (or rather, will be aware of, hypothetically in the future).


How many disjoint edge-cuts a DAG must have?

Short answer: no.

Let $G$ be a complete DAG (transitive tournament) on $n$ vertices with $s$ and $t$ its source and sink, and let $k=\sqrt{n/3}$. Observe that there can be at most four disjoint cuts that contain more tham $n/3$ edges incident to $s$ or more than $n/3$ edges incident to $t$. So, if there are to be many disjoint cuts, we can assume that there exists a cut $C$ that does not contain large numbers of edges incident to $s$ and $t$.

Now let $X$ be the complete subgraph induced in $G$ by the set of vertices $x$ such that edges $sx$ and $xt$ do not belong to $C$. The number of vertices in $X$ is at least $n/3$, because otherwise $C$ would touch too many edges incident to $s$ or $t$. However, $X\setminus C$ cannot contain a $k$-path, because if such a path existed it could be concatenated with $s$ and $t$ to form a long path in $G\setminus C$. Therefore, the longest-path layering of $X\setminus C$ has fewer than $k$ layers, and has a layer containing more than $(n/3)/k=k$ vertices. Since this is a layer of the longest path layering, it is independent in $X\setminus C$, and therefore complete in $C$, so $C$ contains a path $P$ through the vertices of this layer, of length $k$. This path must be disjoint from all of the other cuts.

Every cut that is not $C$ must contain either the edge from $s$ to the start of path $P$ or the edge from the end of path $P$ to $t$, or else it would not block the path $s$–$P$–$t$. So if $C$ exists, there can be at most three disjoint cuts. And if $C$ does not exist (that is, if all cuts cover more than $n/3$ edges incident to $s$ or to $t$) there can be at most four disjoint cuts. Either way, this is a lot fewer than $k$ cuts.


What is a commutative transitive closure operator?

Take a relation $R \subseteq X \times X$. Now, let $R^\dagger$ be the converse relation to $R$, and let $\Delta_X$ be the identity relation on $X$.

The commutative transitive closure $R^*$ is the smallest relation $S $ such that $\Delta_X \cup R \cup R^\dagger \cup S \circ S \subseteq S$.

Intuitively, think of the relation $R$ as being the edge relation on a directed graph. The commutative transitive closure tells you whether or not there is a path between two nodes, if you let yourself ignore the directedness.


Efficiently finding the minimum number of transpositions needed to sort a list

Unfortunately, the problem is NP-hard in general, according to Amir, Hartman, Kapah, Levy and Porat (see http://epubs.siam.org/doi/abs/10.1137/080712969), even if each symbol appears at most three times. I didn't find a mention of a constant factor approximation algorithm, or of something reasonably fast to tackle the problem. Are there any additional restrictions you can think of in your case?

EDIT: the authors also give a 3/2-approximation algorithm, but I don't know if it's good enough for your purposes.


Most important new papers in computational complexity

The recent paper of László Babai showing that Graph Isomorphism is in Quasi-P is already a classic.

Here is a more accessible exposition of the result published in the ICM 2018 proceedings.


The UCI Network Data Repository has a collection of social networks, with additional attributes (not just vertices and edges). They also have a set of links to similar collections elsewhere.


Use the k-center clustering algorithm: see Section 4.2 in http://goo.gl/pLiEO.

One can get 1+eps approximation algorithm using sliding grids.

It is natural to assume the problem is NP-Hard because of the work by Feder and Greene.


In computer science, DBLP might be a better idea than MathSciNet. Your own page in DBLP lists all your coauthors; the database is certainly not complete, but usually the information is correct.

You can also try to use Google Scholar, with a search similar to this:

author:foo author:bar

As always with Google Scholar, double-check the results.


Is the following restriction of cellular automata / tile assembly / CRN a known model?

If you partition $\mathbb{Z}^d$ into the $(d-1)$-dimensional slices $S(n) := \{ \vec v | \sum_{k=1}^d \vec v_k = n \}$, then your model is essentially a spacetime diagram of the $(d-1)$-dimensional cellular automaton that maps $x|_{S(n)}$ to $x|_{S(n+1)}$. The initial configuration $x|_{S(0)}$ has a special quiescent state everywhere except at the origin. If the CA is linear over a field of characteristic $p$, then these diagrams are $p$-automatic; if not, they can be quite complex, since you don't restrict $f$ in any way. They are not necessarily semilinear in either case. For example, it's pretty easy to embed a computation history of an arbitrary Turing machine in the configuration.


Fully linear time regular expression matching

Groz et al. explicitly state that the best known algorithm for general regular expressions (as of 2012) is $O(nm(\log\log n)/(\log n)^{3/2}+n+m)$, due to Bille and Thorup 2009, doi:10.1007/978-3-642-02927-1_16 (preprint).

For a fixed size alphabet, Sebastian Maneth pointed out to me that $O(n+m)$ is possible for deterministic regular expressions by constructing the Glushkov DFA: each position in the regular expression is one state, and the transitions are determined by the bounded set of symbols that may appear before moving to a position.
However, without fixing the alphabet size, it still holds that "finding a time $O(m+n)$ algorithm remains an open problem" even in the deterministic case.


Using Indicator Functions as Transfer Functions for Neural Networks

Sigmoid functions have clear probabilistic interpretation, so one can derive optimal learning algorithms for them within the bayesian approach. Moreover, they are differentiable, so the gradient descent can be directly applicable.
However, in general, neural networks are "universal approximators" in almost the same sense as, for example, polynomials. They can capture a limited set of regularities. Different activation functions (like different basis functions in functional approximation) will capture different regularities and will have different biases in approximating other regularities.
Thus, what activation functions are better depends on what underlying regularities are presented in data. Indicator functions can surely be better for some tasks. However, no generally applicable (task-independent) theory advocating the use of indicator functions is possible.


Difference between statically and dynamically typed languages

The question is subtle and simple at the same time, hence deep. Let me give you
a simplifying answer.

First you need to realise there there three somewhat orthogonal distinctions which are often mixed up, leading to confusion:

Typed vs untyped languages
Type-checking vs type-inference
Static vs dynamic typing

Types are simply an algorithmic technique to define and decide
language subsets (think: if a program is typable, it's in the
subset). Typically subset decided by types are somehow well-behaved, and we consider programs not in the subset to be somehow bad
or in error, think programs like "hello" * 17 are rejected).
The essence of this algorithmic technique is that you have a second language (that of types) which gives a second version on the program in question. Typically the language of types is  simpler than the ambient programming language.

Type-checking vs type-inference is about a detail of this algorithmic technique: in
type-checking a program is compared against user-specified types: are
the two in 'harmony', while in type-inference the internal consistency
of a program with itself is checked. In practise no programming
language is fully type-checked, instead at least some parts of programs are
 inferred, e.g. you don't have  to write

((3 : int) (+ : (int, int) -> int) (4 : int)) : int

or some monstrosity like this, instead,
you can get away with

3 + 4

even in Java.

Finally statically vs dynamically typed is about when programs are
accepted or rejected.  With dynamic typing that happens during
execution. With static typing, there is a distinct phase (sometime called semantic analysis) before
execution, typically during compilation. If the program fails semantic analysis, compilation or interpretation is abandoned, hence no execution.


What specific evidence is there for P = RP?

The existence of problems in DTIME(2^O(n)) which require exponential-size circuits to compute (which is the assumption in IW) seems plausible since otherwise we would have non-uniformity giving a speedup on EVERY computational problem -- which goes completely against the current thinking that does not see a "too significant" gap between uniform and non-uniform complexity for "normal" problems.  This thinking comes from the fact that there are very few examples where a "non-uniform" algorithm is known that is significantly better than the known uniform one (again except for derandomization).

Another piece of "evidence" is that relative to a random oracle we do have P=BPP.


One direction is clear:  the union of any finite number of DCFL's is a CFL.

However, a precise characterization of the union-closure of DCFL's was not obvious to me at all (and I teach this stuff and wrote a book on it), so I went searching with a google search.  I found this paper by my colleagues  Martin Kutrib and Andreas Malcher:   Context-Dependent Nondeterminism for Pushdown Automata, O.H. Ibarra and Z. Dang (Eds.): DLT 2006, LNCS 4036, pp. 133–144, 2006.  Theorem 1 gives a characterization of this class.


Graph class with easy chromatic number, but NP-hard coloring

I think you need to specify more carefully what you mean by "NP-hard" for a problem like this with a known solution but an unknown witness.

The most natural definition, to me, would be something like a many-one reduction, where there exist two polynomial time functions $p$ and $q$, where $p$ maps SAT instances to graphs with a known chromatic number and $q$ maps colorings of these graphs to truth values, such that $q(\chi)$ equals the correct truth value for SAT instance $X$ whenever $\chi$ is a valid optimal coloring of $p(X)$. However, this is not possible unless $\mathsf{NP}=\mathsf{coNP}$. For, if such $p$ and $q$ existed, then every unsatisfiable SAT instance $X$ would have a witness to its unsatisfiability, namely a coloring of $p(X)$.