Here is a counterexample, i.e. a language with an $O(n^{2+ε})$ algorithm (using multitape Turing machines) for every $ε>0$, but not uniformly in $ε$:
Accept $0^k 1^m$ iff $k>0$ and the $k$th Turing machine halts in less than $m^{2+1/k}$ steps on the empty input.  Other strings are rejected.

For every $ε$, we get an $O(n^{2+ε})$ algorithm by hardcoding all sufficiently small nonhalting machines, and simulating the rest.

Now, consider a Turing machine $M$ deciding the language.

Let $M'$ (on the empty input) be an efficient implementation of the following:
for $n$ in 1,2,4,8,...:
     use $M$ to decide whether $M'$ halts in $<n^{2+1/M'}$ steps.
     halt iff $M$ says that we do not halt but we can still halt in $<n^{2+1/M'}$ steps.

By correctness of $M$, $M'$ does not halt, but $M$ takes $Ω(n^{2+1/M'})$-steps on input $0^{M'} 1^{n-M'}$ for infinitely many $n$.  (If $M$ is too fast, then $M'$ would contradict $M$.  The $Ω(n^{2+1/M'})$ bound depends on $M'$ simulating $M$ in linear time and otherwise being efficient.)


What data structures exist for fast calculation of distances between multi-dimensional points

I'm not sure what you mean by 'overlapping points', and even less clear how you construct a 2D scatter plot from 4D data unless by doing some kind of projection. Having said that, what I think you're looking for is a dynamic near-neighbor data structure. Specifically, you want a data structure that processes queries of the form "Who's my nearest neighbor in the current set" and "insert a point into the current set"

While there's a ton of work on different kinds of near-neighbor structures, your particular situation (dynamic 4D points) suggests at least starting with a grid-based structure. Make (4D) buckets based on segmenting the coordinates, and hash the points in, and then for a query you can do a spiral search (or something similar) around the cell your query lies in.

The next idea would be to build a generalized quad tree data structure (a compressed quad tree) or even something involving space-filling curves, if this first approach doesn't yield the performance you need. There are even more powerful methods, but I wouldn't recommend looking into them till you've exhausted the simple approaches.

Bottom line: "dynamic" and "nearest-neighbor" and "low dimensional" are your google friends.


Many problems in computer vision are naturally expressed as constraint satisfaction problems.  There is a history going back several decades of applying constraint programming to such problems.  One of the key early papers in constraint satisfaction was completely motivated by problems from computer vision.

Ugo Montanari, Networks of constraints: Fundamental properties and applications to picture processing, Information Sciences 7 95–132, 1974. doi: 10.1016/0020-0255(74)90008-5

See this book for a recent overview of the application of constraints to particular problems in computer vision.

Martin Cooper, Line Drawing Interpretation. Springer-Verlag, 2008. (publisher's site)

If you really do want SAT and would like to avoid constraint satisfaction, then you can translate the constraint formulation into SAT, either manually or using an automated translation tool like Sugar.  Note that Chapter 2 of the recent Handbook of Satisfiability claims that it is common to first express one's problem as a constraint satisfaction problem, and only then to translate this formulation to SAT.  So constraint satisfaction should probably be considered even when one wants to work with SAT.

There is one big advantage of staying within a more expressive paradigm.  The constraint satisfaction framework allows the use of interval and numeric constraints.  These often occur in computer vision, but can lead to SAT instances that are infeasibly large.  Specialised constraint solvers may be greatly preferable to SAT solvers in such cases.

(A final aside: I have heard that the computer vision community tends not to be aware of constraint satisfaction approaches, and that this has led to the reinvention of well-known constraints techniques and results.  I do not know if this is a correct assessment, but if it is, then it would be worth translating constraints results to the terminology and specific concerns of computer vision.)


Reference for unpublished but quoted manuscript

I assume you've looked online, though I'd be amazed if a 1980s master's thesis was online.

Ask one of the authors: they should have read the thesis before citing it, which suggests that at least one of them has access to a copy or, at least, had access at the time they wrote the paper. If that fails, try asking your university library.

Also, although the citation doesn't mention it, be prepared for the thesis to be in Russian.


Design a sampling process to select an element with probability proportional to its appear probability in a simulation

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

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

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

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


The number of isomorphism classes of groups of order $\leq n$ is asymptotically $n^{\Theta(\log^2 n)}$, so to even specify all such groups requires strings of length $\Omega(\log^3 n)$, so this is also a lower bound on your action complexity.


This is not an answer but is too long for a comment:

The graph you care about is called the line graph of the hypergraph. For usual graphs, it is well known that the line graph of an expander graph is also an expander graph (because vertex and edge expansion are equivalent). Whether this holds for hypergraphs probably depends on which of the many notions of expansion you can choose for hypergraphs/simplicial complexes. For one of these notions (based on the spectrum of an adjacency matrix of the hypergraph), this is mentioned as an open problem in the conclusion of this thesis.


Bounds on the smaller eigenvalues of the adjacency matrix of a graph

You might like this recent paper: http://arxiv.org/abs/1211.0589v1

The paper shows, e.g., that "for any finite graph with $n$ vertices and all $k ≥ 2$, the
$k$th largest eigenvalue" of the graph's Laplacian, i.e. $L=I-A/d$, "is at most $1−\Omega(\frac{k^3}{n^3})$", where $A$ is the adjacency matrix and $d$ a bound on the degree.


Deciding whether a graph contains a complete balanced bipartite graph

If the vertex pair $(u, v)$ is not in $E$ then they can't be on opposite sides of the partition, so they must be in the same half. Create a union-find data structure and merge every vertex pair which is not an edge. Then you just need to solve the partition (subset-sum) problem to group some disjoint sets into a set of size $\frac{|V|}{2}$. The union-find phase can be done in $O(V^2 \alpha(V))$ and the pseudo-polynomial algorithm for subset sum takes $O(V^2)$ so this is in P. (Thank you to those who corrected an earlier error).

In the other direction, an oracle for balanced bipartite subgraph would give a pseudo-polynomial algorithm for the partition problem.

FWIW the generalisation which takes a parameter $K$ and asks whether there's a subgraph of $G$ which is a complete $K \times K$ bipartite graph is NP-complete by reduction from CLIQUE. Hat tip to Mohammad Al-Turkistany who cited a reference which proves this even when $G$ is known a priori to be bipartite: David S. Johnson, The NP-completeness column: An ongoing guide. Journal of Algorithms, 8(3):438–448, 1987.


A coupon collector type problem with changing probabilities

Lemma. In the unbounded case, the expected number of flips is at most $\sqrt t + 3/2$.

Proof. Let r.v. $F$ be the number of flips until a head.
Then the expected number of flips is

\begin{align}
E[F] & = \sum_{i=1}^\infty \Pr[F \ge i] && (1)\\
&= \sum_{i=0}^\infty \Pr[\text{first $i$ flips are tails}] && (2)\\
&= \sum_{i=0}^\infty \prod_{j=t}^{t+i-1} (1-1/\sqrt{j}) && (3)\\
&\le \sum_{i=0}^\infty \exp(\textstyle-\sum_{j=t}^{t+i-1} 1/\sqrt j)
& \text{as } 1+z\le e^z~~ & (4)\\
&\le \sum_{i=0}^\infty \textstyle\exp(-\int_{t}^{t+i} 1/\sqrt x ~dx)
& \text{as } \textstyle \sum_{j=a}^{b-1} f(j) \ge \int_{a}^b f(x)\, dx~~&(5)\\[-10ex]
&&~~\text{for $f$ decreasing}~~\\
&= 1+\sum_{i=1}^\infty \textstyle\exp(2\sqrt{t}-2\sqrt{t+i})
& \text{as } \textstyle\int 1/\sqrt x ~dx = 2\sqrt x~~&(6)\\
&= 1+e^{2\sqrt{t}} \sum_{i=t+1}^\infty e^{-2\sqrt i}&&(7)\\
&\le 1+e^{2\sqrt{t}} \int_{t}^\infty e^{-2\sqrt x}\,dx
&\text{as } \textstyle \sum_{i=a}^{\infty} f(i) \le \int_{a-1}^\infty f(x)\, dx ~~&(8)\\
&&\text{for monotonic $f$}~~\\
\\
&= 1 + e^{2\sqrt{t}} \,e^{-2\sqrt t}(\sqrt t + 1/2)
& \text{as } \textstyle\int_t^\infty e^{-2\sqrt x}\,dx = e^{-2\sqrt t}(\sqrt t + 1/2)~~&(9)\\\\
&= \sqrt {t} + 3/2&&~~\Box
\end{align}

Of course the same bound holds in the bounded case as well.


Cover time and spectral gap for reversible random walks

Roughly speaking, the mixing time is the worst-case hitting time of the half the vertices.  Cover time is a stopping time when ALL subsets of vertices are hit.  In other words, it is always larger than the the mixing time.  Thus is your example one cannot have mixing time $n^{1000}$ and cover time $n^2$.

Making this intuition precise requires a bit of care since we need to relate mixing times to eigenvalue gap, take not half the vertices but half the stationary distribution $\pi$, etc.  None of this is difficult.  Start with this paper by Lovasz and Winkler, which gives the above version of the mixing time and relates it to more standard mixing time in total variation.


What kind of computational model is the brain?

This is pretty much an open problem and subject to active research. There are a few proposals available. Here are some of the latest ones:

Brain computation by assemblies of neurons Christos H. Papadimitriou, Santosh S. Vempala, Daniel Mitropolsky, Michael Collins, Wolfgang Maass Proceedings of the National Academy of Sciences Jun 2020, 117 (25) 14464-14472; DOI: 10.1073/pnas.2001893117 [Link]

Manuel Blum's model of consciousness: [Video]


You can also transform the ATSP to TSP; the process requires doubling number of nodes (adding dummy cities).

http://www.sciencedirect.com/science/article/pii/0167637783900482
http://www.sciencedirect.com/science/article/pii/0167637786900817


(I now realize that one of the questions I gave at the bottom of my OP is trivial,

and for another, a yes answer would have a simple unlikely consequence.

As I stated in my OP, 2.5-coloring is logspace-complete even with k=0,

so it certainly is hard for TC0, and if it's in ACC0 then  ACC0 = logspace .)

More interestingly, I recently learned about the odd cycle transversal problem.  By using Reingold's algorithm as I mentioned in my OP, odd cycle transversal is logspace-equivalent to 2.5-coloring.  Accordingly, this paper yields a significant amount of information

"about the complexity of 2.5-coloring", and this paper gives a faster algorithm for it.


Maximize Edge Disjoint Paths (EDP)

The problem is NP Hard and here are some results:

1) It accepts $O(\sqrt{m})$ approximation by Kleinberg in 96 in general graphs.

2) The above is tight for directed graphs (Guruswami et. al.).

3) Inapproximation result by Andrews, Zhang : O($log ^{\frac{1}{2}-\epsilon}n$).

4) For planar graphs, Chekuri et. al. has found a O(1) approx with any edge being in O(1) paths.

I will update with references later but you can google out.

EDIT: There is a recent paper by Chekuri in 06 which has improvised it to $O(\sqrt(n))$ in undirected graphs. You will get the above references in that paper. The paper is at

theoryofcomputing.org/articles/v002a007/v002a007.ps.gz


The reduction is the following.

Consider a graph as directed (that means, each edge $(u,v)$ is actually a pair of arcs pointing in the opposite directions). Split each vertex $v \in V$ to 2 different vertices $v_{in}$ and $v_{out}$ and fix the adjacent edges such that all in-arcs ends in $v_{in}$ and all out-arcs starts from $v_{out}$. Also add an arc $(v_{in}, v_{out})$ of unit capacity for each such pair. This guarantees that the flow will not pass through any original vertex more than once (which is necessary for path simplicity).

Then add a sink $t$ and arcs $(a_{out},t)$ and $(b_{out}, t)$ of unit capacity. Find a maximum flow from $x_{out}$ to $t$. If a simple path $a-x-b$ exists in the original graph, the parts $x-a$ and $x-b$ will not share a vertex (except from $x$) and the maximum flow will have size 2 so you will be able to reconstruct the answer from the flow. The opposite is true, too.

Upd.: The aforesaid was written under assumption that "simple path" means "a path with no repeated vertices". In other case there is no need for vertices splitting.


Exact exponential-time algorithms for 0-1 programming

If $m$ is superlinear, such an algorithm would disprove the Strong Exponential Time Hypothesis, since formulas in conjunctive normal form are a special case of 0-1 programming and the Sparsification Lemma allows us to reduce $k$-SAT to CNF-SAT on linearly many clauses.

However, there is an algorithm due to Impagliazzo, Paturi, and myself that can solve such a system of inequalities if the number of wires, i.e. the number of nonzero coefficients in $A$ is linear. In particular, if the number of wires is $cn$, the algorithm runs in time $2^{(1-s)n}$, where $s=\frac1{c^{O(c^2)}}$.


Let's assume all possible paths are finite to make the discussion simpler. This is the case for the vast majority of game actually played such as Chess (because of the 50-move rule) or Go (assuming superko is forbidden).

The idea you have about chosing the move maximizing the minimum path is actually an instance of the following more general idea. A proof tree for player P is a subtree of game tree starting at the current position such that for every node n of the tree

if the position corresponding to n is terminal then P has won on that position
if P is to play in the position corresponding to n, then n has exactly one child
if the opponent of P is to play, then every opponent's move leads to a child of n
A proof tree corresponds to a winning strategy for P, so if a position is a theoretical win, then it should be possible to find a proof tree.

Now, there may be several proof trees to choose from in a given won position. To decide which one should be chosen, you can define a cost for each proof tree. For instance, the fastest win is obtained by finding a proof tree of minimal depth. The simplest win is obtained by finding a proof tree of minimal size etc.
After you have decided on the definition of cost, you get a strategy for the losing player: play the move leading to a position with maximal cost.

Now, the only things that remains is finding the minimum cost for won positions and finding the maximum cost for lost positions. As you have discovered, this can be done by retrograd analysis when the cost is the depth of a tree. It turns out it's not too hard to generalize this for other cost measures still using retrograd analysis.

If your game is too large to perform retrograd analysis or you are only interested in a specific starting position, the problem becomes a little bit harder but you can to use a kind of generalization of the A* algorithm. Shameless plug: I have a paper on this very topic.


The point of such a factor in general is that you want to be able to calibrate the scores you get, by forcing them to be within a specific range like $[0,1]$. In particular, this factor would be computed (in principle) by getting the rank of all pages and then dividing by their sum.


Cheap online selection with weighted comparisons

Brute-force case analysis reveals that the optimal competitive ratio for the special case  $n=3$, with no other restrictions on the cost matrix, is the golden ratio $\phi = (\sqrt{5}+1)/2$.  Thus, no online algorithm can achieve a competitive ratio better than $\phi$.

Suppose $C_{1,2}=0$, $C_{1,3}=1$, and $C_{2,3}=\phi$.

Without loss of generality, the algorithm starts by comparing $S_1$ to $S_2$, at cost zero.
The adversary declares $S_1 > S_2$.
If the algorithm compares $S_1$ to $S_3$:

The adversary declares $S_1 > S_3$.
The algorithm must compare $S_2$ and $S_3$.
The adversary declares $S_2 < S_3$, so $S_2$ is the minimum.
The total cost of the algorithm's comparisons is $1+\phi$.
The adversary reveals the total order $S_2 < S_3 < S_1$.
The total cost of the optimal comparisons ($S_1>S_2$ and $S_2<S_3$) is $\phi$.

If the algorithm compares $S_2$ to $S_3$:

The adversary declares $S_3 > S_2$, so $S_2$ is the minimum.
The total cost of the algorithm's comparisons is $\phi$.
The adversary reveals the total order $S_2 < S_1 < S_3$.
The total cost of the optimal comparisons ($S_1>S_2$ and $S_1<S_3$) is $1$.

In either case, the algorithm's comparisons cost a factor of $\frac{1+\phi}{\phi} = \frac{\phi}{1} = \phi$ more than the optimal set of comparisons for the revealed total order.

More generally, the competitive ratio is $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$, where $a\le b\le c$ are the three comparison costs.  (There are more cases to consider here, because there are optimal algorithms that do not perform the cheapest comparison first, but the case analysis is still elementary.)  Tedious calculations imply that the expression $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$ is maximized when $a=0$, $b=1$, and $c=\phi$.

In particular, if $\frac{a+c}{a+b} > \frac{a+b+c}{a+c}$, the best possible algorithm can be forced to perform all three comparisons.


Checking formulas with two quantifiers ($\forall \exists$) - 2QBF

If I may, quite blatantly, advertise myself, we wrote an article about this last year
Abstraction-Based Algorithm for 2QBF. I've got an implementation for qdimacs, which I can provide if you wish but from my experience, one can benefit greatly from specializing the algorithm for a particular problem. There is also an older paper A Comparative Study of 2QBF Algorithms, which also presents fairly easily implemetable algorithms.


Is it possible to create a machine learning classifier to generate Mock interfaces for systems testing?

A classical result from automaton theory shows that even the problem of finding minimum-size DFA consistent with given positive and negative samples is NP-hard. This was shown by Gold in 1978. Your problem is much harder, as in practice you would have to learn data relationships in addition to any finite-state control of the system interface.


NP-hardness of coloring uniform hypergraphs

$2$-coloring $s$-uniform hypergraphs is also called Set Splitting, problem [SP4] in Garey-Johnson book.
The hardness proof is due to Lovasz in this paper.


How to produce a random graph that does not have a Hamiltonian cycle?

This is impossible (unless NP=coNP) since in particular that implies a poly-time function whose range is the non-Hamiltonian graphs (the function goes from the random string to the output graph), which in turn will imply an NP-proof of non-Hamiltonianicity (to prove G doesn't have an Hamiltonian circuit, show x that maps to it.)


Statement that inequality of P and NP obstructs finding a proof of their separation

I also think that what was meant might have been obstructions akin to the natural proofs barrier of Razborov and Rudich. The barrier on a high level shows that current methods of proving circuit lower bounds are "self-defeating" when applied to the P vs NP problem. Suppose you want to prove that SAT is hard by showing that it satisfies some predicate which is not satisfied by problems in P. Suppose the predicate is satisfied by most boolean functions (the largeness property) and can be computed in time $2^{O(n)}$ on functions that take $n$ inputs, when given the $2^n$-size truth table of the function (the constructivity property). Razborov and Rudich show that if such a predicate exists, then there are no strong pseudorandom number generators. So the existence of the object we're trying to use to separate P from NP would itself imply a statement in the spirit of P=NP.

There are arguments why you expect that hardness predicates would satisfy the largeness property. Certain "formal complexity measures" have the property that if they lower bound the complexity of any one function, then they lower bound the complexity of most functions. Also, by the classical counting argument, most functions are hard, so if you expect that the predicate captures hardness, then it should be satisfied by most functions. The constructivity property gets to your question. It is true that there could in principle exist a hardness predicate that cannot be evaluated in time polynomial in the truth table of the function. But most combinatorial proofs of existence can be made constructive. Even proofs that on first inspection seem to use inherently non-constructive arguments were often later made constructive. Two recent examples are the algorithmic Lovasz Local Lemma of Moser and Tardos and Nikhil Bansal's constructive version of Spencer's discrepancy upper bound for general set systems. So it looks like we might not have proof methods that take us outside the realm of polynomial time constructions.

Check the details in the natural proofs chapter of Arora-Barak: http://www.cs.princeton.edu/theory/complexity/naturalchap.pdf


Is there a natural problem in quasi-polynomial time, but not in polynomial time?

There has, in fact, been quite a lot of recent works on proving quasi-polynomial running time lower bound for computational problems, mostly based on the exponential time hypothesis. Here are some results for problems that I consider quite natural (all results below are conditional on ETH):

Aaronson, Impagliazzo and Moshkovitz [1] show a quasi-polynomial time lower bound for dense constraint satisfaction problems (CSPs). Note that the way CSP is defined in this paper allows the domain to be polynomially large, as the case where the domain is small is known to have a PTAS.
Braverman, Ko and Weinstein [2] prove a quasi-polynomial time lower bound for finding $\epsilon$-best $\epsilon$-approximate Nash equilibrium, which matches Lipton et al.'s algorithm [3].
Braverman, Ko, Rubinstein and Weinstein [4] show a quasi-polynomial time lower bound for approximating densest $k$-subgraph with perfect completeness (i.e. given a graph that contains a $k$-clique, finds a subgraph of size $k$ that is $(1 - \epsilon)$-dense for some small constant $\epsilon$). Again, there is a quasi-polynomial time algorithm for the problem (Feige and Seltser [5]).

References

AM with multiple Merlins. In Computational Complexity (CCC), 2014 IEEE 29th Conference on, pages 44–55, June 2014.
Mark Braverman, Young Kun Ko, and Omri Weinstein. Approximating the best nash equilibrium in $n^{o(log n)}$-time breaks the exponential time hypothesis. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’15, pages 970–982. SIAM, 2015.
Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM Conference on Electronic Commerce, EC ’03, pages 36–41, New York, NY, USA, 2003. ACM.
Mark Braverman, Young Kun-Ko, Aviad Rubinstein, and Omri Weinstein. ETH hardness for Densest-$k$-Subgraph with perfect completeness. Electronic Colloquium on Computational
Complexity (ECCC), 22:74, 2015.
U. Feige and M. Seltser. On the densest $k$-subgraph problems. Technical report, 1997.


I think it can be compressed to linear space.

I assume the machine $M$ has one tape. Initially the first $n$ cells contain the input, which is followed by $2^O(n)$ zeroes. $M$ is oblivious and always makes $k$ passes through the tape (from left end to right and back), and then accepts or rejects. Let $p_i$ denote the state the machine enters after reading the $n$-th cell on $i$-th pass during the left-right phase, and let $q_i$ denote the state the machine enters after reading the $n+1$-th cell on $i$-th pass during the right-left phase. Note that $q_1$ is a function of $p_1$ alone, and generally $q_i$ depends only on the sequence $p_1, p_2, \dots, p_i$ (this sequence has length at most $k$, which is fixed). Therefore we can always compute the state $q_i$ without actually continuing the pass through the extra scratch space - the transitions can be hardcoded into the description of the machine.


Places where the order of points along a simple polygon passing through them is useful

Your comment that "there are probably too many simple polygons" is the key, because actually there aren't that many.  $n$ points have $n!$ paths (permutations) and $(n-1)!/2$ polygons if we allow self intersections -- that is, $2^{\Theta(n \log n)}$.

The numbers of paths or polygons without self intersections are $2^{\Theta(n)}$, easiest observed from the fact such paths and polygons can be completed to triangulations, the number of triangulations of a given point set in the plane is $<30^n$ [Sharir-Sheffer'09, latest in a long history], and the number of proper subsets of edges of each triangulation is $<2^{3n-6}$.

The convex hull of simple polygons has been one of my favorite things since using it to find and/or formulae for polygons in SIGGRAPH'88 http://dx.doi.org/10.1145/54852.378472


Is that edge orientation optimization problem NP-hard?

We answer OP's last question: can an approximate solution to IQP be obtained by randomized rounding?
We show that the natural randomized-rounding scheme gives a 2-approximation, and a $(1+1/\overline d)$-approximation in graphs with average degree $\overline d$. (Note that any connected graph has average degree at least $2-2/|V|$.)
For the record, here's the rounding scheme. Given a fractional solution $x$ for QP, define 0/1 solution $x'$ as follows: for each edge $(u,w)$ independently: take $x'_{uw} = 1$ and $x'_{wu}=0$ with probability $x_{uw}$; otherwise take $x'_{uw} = 0$ and $x'_{wu} = 1$.
Let $f(x)$ be the objective function of QP.
Lemma 1. For any feasible $x$,
$$E[f(x')] = f(x) + 2\sum_{(u,w)\in E} x_{uw}x_{wu} \le f(x) + |E|/2.$$
Proof. This is a standard calculation.  Note that
$$f(x) = \sum_{u\in V} \Big(
\sum_{w\in N(u)} x^2_{uw} + 2\sum_{w'\in N(u), w'\ne w} x_{uw}x_{uw'}\Big)$$
and by linearity of expectation, the independence of $x'_{uw}$ and $x'_{uw'}$, and $E[x'^2_{uw}] = x_{uw}$,
$$E[f(x')] = \sum_{u\in V} \Big(
\sum_{w\in N(u)} x_{uw} + 2\sum_{w'\in N(u), w'\ne w} x_{uw}x_{uw'}\Big).$$
Using this and $x_{uw} = 1 - x_{wu}$,
$$
E[f(x')] - f(x)
= \sum_{(u,w)\in E} x_{uw} - x^2_{uw} + x_{wu} - x^2_{wu}
= 2\sum_{(u,w)\in E} x_{uw} x_{wu}.$$
Lemma 2. For any feasible $x$, $E[f(x')] \le 2 f(x)$. That is, the rounding scheme gives a 2-approximation.
Proof.
By inspection of the expansion of $f(x)$ in the proof of Lemma 1,
$$f(x) \ge \sum_{(u,w)\in E} x^2_{uw} + x^2_{wu}.$$
Applying $p^2 + (1-p)^2 \ge 2p(1-p)$ for $p\in[0,1]$ (with $p=x_{uw}$)
to each term gives
$$f(x) \ge 2\sum_{(u,w)\in E} x_{uw}x_{wu}.$$
This and Lemma 1 imply $E[f(x')] \le f(x) + f(x) = 2 f(x)$. $~~~\Box$
The bound is tight in that for any graph with maximum degree 1,
the fractional solution $x_{uw} = x_{wu} = 1/2$ obtains value $|E|/2$,
but any integer solution has value $|E|$.
(Also note that $|E|$ is a lower bound on OPT,
using $\sum_{u\in V} d^2_{out}(v) \ge \sum_{u\in V} d_{out}(v) = |E|$.)
Lemma 3. In any graph with average degree $\overline d = 2|E|/|V|$, the rounding scheme gives at least a $(1+1/\overline d)$-approximation.
Proof.  Fix an optimal solution. Let $d'_v$ denote the out-degree of vertex $v$ in the optimal solution,
so $d'$ is a vector in $\mathbb R_+^{|V|}$.
Let $\mathbf 1$ denote the all-ones vector in $\mathbb R^{|V|}$.
By Cauchy-Schwarz,
$$\text{OPT} = d' \cdot d'
\ge (d' \cdot \mathbf 1)^2/(\mathbf 1\cdot \mathbf 1)
= \textstyle \big(\sum_v d'_v\big)^2/|V|
= |E|^2/|V| = |E|\overline d/2.$$
By this and Lemma 1
$$E[f(x')] \le f(x) + |E|/2 \le f(x) + \text{OPT} / \overline d \le \text{OPT}(1+1/\overline d).$$
$~~~\Box$


In external memory, is grouping equal elements easier than sorting?

Even testing whether $n$ elements are distinct is known to require $\Omega(n \log n)$ time on a model with some pretty reasonable restrictions.  See, for example,
Anna Lubiw, András Rácz:
A Lower Bound for the Integer Element Distinctness Problem. Inf. Comput. 94(1): 83-92 (1991).


Re your first question, re whether this type of graph has a name: it is the line graph of a bipartite graph (the bipartite graph that has a vertex for each nonempty row or column and an edge for each point). Line graphs of bipartite graphs are an important subclass of the perfect graphs. They are generally not planar (e.g. if you have five points on the same row or column you get a $K_5$ subgraph).


I found the reference for CPO-like categories.
Scott's paper Continuous Lattices in the book Toposes, Algebraic Geometry and Logic. It is explained in the comments right after corollary 4.3.
A more general theorem can be found in Smyth's and Plotkin's paper Category-Theoretic Solution of Recursive Domain Equations. It is lemma 2.

However, again, the functors are not arbitrary. One needs some sort of a continuity assumption.


Path of exact cost in edge labelled DAG?

Yes, it's NP-complete, by a reduction from subset sum. It's easiest to see using a multigraph: make a directed path, double each edge, and make one of the two doubled edges have cost zero, then cost $a$ can be achieved if and only if it is the sum of some subset of the weights of the nonzero edges. If you don't like multigraphs, subdivide the edges.

If you assume that $\max w_i<C$ then there's a dynamic programming algorithm with time $O(mnC)$: just process the nodes in a topological ordering, and for each node calculate the set of path lengths by which it can be reached from $s$.


Will Martin-Löf Type Theory lead to a greater ability to write provably correct code?

I don't think your question is particularly well posed. It mostly asks for opinions. Here are mine:

Yes.
I do not know what you mean, but the answer is probably "there is more MLTT theory to be done, although we do know a lot".
You cannot do all of homotopy type theory in Coq and Agda. This is an active area of research.


Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments

The polynomial hierarchy would collapse to the fourth level (indeed, the third, see below).
Proof. First, we get that $\oplus P\subseteq \Sigma_2^P$. This is because a $\Sigma_2^P$ machine can use its $\exists$ quantifier to guess a polynomial number of assignments and then, using its $\forall$ quantifier, verify that this list contains all of the formula's satisfying assignments. By Valiant-Vazirani we have $PH\subseteq BPP^{\oplus P}$. We have $BPP\subseteq \Sigma_2^P$, so we get $BPP^{\oplus P}\subseteq {\Sigma_2^P}^{\oplus P}\subseteq {\Sigma_2^P}^{\Sigma_2^P}=\Sigma_4^P=PH$. $\square$
@Emil Jerábek gives a stronger argument; the polynomial hierarchy collapses to the third level. This is because counting assignments can be done in $P^{NP}$, which is better than the $\Sigma_2^P$ method described above.
Proof. We get $\oplus P\subseteq P^{NP}$, because a $P^{NP}$ algorithm can count a formula's satisfying assignments, if it is polynomially-bounded. (algorithm below). Consequently, we get $PH\subseteq BPP^{\oplus P}\subseteq BPP^{P^{NP}}=BPP^{NP}\subseteq \left(\Sigma_2^P\right)^{NP}=\Sigma_3^P=PH$.
Algorithm [For counting satisfying assignments in $P^{NP}$].$\quad$ Given a Boolean formula $\psi$, query the oracle. If the formula is not satisfiable, return. Otherwise, find a satisfying assignment $x$ using $n$ more queries to the oracle. Remove the assignment, i.e., construct a new formula $\psi^\prime:=\psi\wedge \neg x$. Repeat this procedure until the oracle returns ``not satisfiable''. This happens exactly after all the satisfying assignments have been "removed". This procedure therefore runs in time polynomial in the number of satisfying assignments, which, by assumption, is polynomial.
The inclusion $\oplus P\subseteq P^{NP}$ is obtained by simply returning ``yes'' at the end of the computation if and only if the number of satisfying assignments is discovered to be odd. $\square$
Perhaps there are other consequences; I hope others can give some.


Random functions of low degree as a real polynomial

Here's an algorithm that beats the trivial attempts.

The following is a known fact (Exercise 1.12 in O'Donnell's book) : If $f:\{-1,1\}^n\to\{-1,1\}$ is a Boolean function which has degree $\le d$ as a polynomial, then every Fourier coefficient of $f$, $\hat{f}(S)$ is an integer multiple of $2^{-d}$.
Using Cauchy-Schwarz and Parseval one gets that there are at most $4^d$ nonzero Fourier coefficients and $\sum_{S}{|\hat{f}(S)|}\le 2^{d}$.

This suggests a sampling method -

Choose random non-negative integers $a_S$ for all sets $S\subseteq[n]$ of size at most $d$, which sum up to $\le 4^d$.
Let $f(x) = \sum_{S}{\frac{a_S}{2^d} \chi_S(x)}$.
Verify that $f$ is Boolean. If so, return $f$. Else, go back to $1$.

Note that for every degree $\le d$ polynomial $f$ exactly one choice of random integers in Step 1 will generate the polynomial $f$. The probability of getting a specific degree $\le d$ polynomial is
$$1/\binom{\binom{n}{\le d}+4^d}{4^d} =1/O(n/d)^{d4^d}.$$
Hence, we need to repeat this process at most $O(n/d)^{d4^d}$ times, in expectation, before halting.

It remains to show how to perform step 3. One can define $A = \bigcup\{S:a_S\neq 0\}$. Check that $|A| \le d 2^d$ (which should hold by Nisan-Szegedy for every Boolean function) and then evaluate $f$ on all possible assignments to the variables in $A$. This can be done in time $2^{d 2^d}$.
Gur and Tamuz offer a much faster randomized algorithm for this task, however since this part doesn't dominate the time complexity this is enough.

Overall the algorithm produces a random sample of a degree $\le d$ polynomial in time $O(\frac{n}{d})^{d4^d}$.
Under the assumption that $n \le d2^d$ the time complexity is $2^{O(d^2 4^d)}$.

This is not a polynomial time sampling algorithm, although it is much faster then sampling a completely random function (in which case the probability of getting a specific degree $\le d$ polynomial is $1/2^{2^n}$).


Regarding Elements of Programming, is a uniqueness of the value type sufficient for equality testing?

Looking at the book, they give a really good example where representational equality doesn't imply equality. You have two unordered collections, which are equal if after sorting and removing duplicates, they are representationally equal. For example

Collection A:    5 5 2 3 1 1 1 1
Collection B:    1 5 5 5 3 3 3 2

Are representationally unequal. But if you sort them and remove duplicates...

Collection A:    1 2 3 5
Collection B:    1 2 3 5

And are now representationally equal. In this sense, they're originally representationally unequal, for the sake of easier processing perhaps. However, once you perform the operation which determines equality, they are indeed equal.

So no, they don't have to be representationally equal to be equal.


From Church-encoding to induction principle

Let $F : \mathsf{Type} \to \mathsf{Type}$ be a type constructor and let $W_F$ be the inductive type defined by $W_F = F W_F$. Not every $F$ has such an inductive types, but this is not important for this discussion.

The starting point of Church's encodings is the observation that $W_F$ ought to be
$$\forall T : \mathsf{Type} \,.\, (F T \to T) \to T.$$
Thus, to get an induction principle out of a Church encoding, we take the following steps:

Rewrite the Church encoding in the form $\forall T : \mathsf{Type} \,.\, (F T \to T) \to T$ for a suitable $F$.
Derive an induction principle for $F$, as in your own answer to your own question.

Let us try a couple of examples.

Unit type

\begin{align*}
\mathsf{unit} &= \forall T . T \to T \\
&= \forall T . (1 \to T) \to T \\
&= \forall T . (F T \to T) \to T
\end{align*}
where $F X = 1$.

Empty type

\begin{align*}
\mathsf{unit} &= \forall T . T \\
&= \forall T . 1 \to T \\
&= \forall T . (0 \to T) \to T \\
&= \forall T . (F T \to T) \to T
\end{align*}
where $F X = 0$.

Natural numbers

\begin{align*}
\mathsf{nat} &= \forall T . (T \to T) \to (T \to T) \\
&= \forall T . (T \to T) \times T \to T \\
&= \forall T . T \times (T \to T) \to T \\
&= \forall T . ((1 + T) \to T) \to T \\
&= \forall T . (F T \to T) \to T
\end{align*}
where $F X = 1 + X$.

Binary trees

We can also go backwards. The binary trees are the inductive type for $F X = 1 + X \times X$, thus their Church encoding is

\begin{align*}
\mathsf{tree} &= \forall T . (F T \to T) \to T \\
&= \forall T . ((1 + T \times T) \to T) \to T \\
&= \forall T . (T \times (T \times T \to T) \to T \\
&= \forall T . T \to (T \to T \to T) \to T
\end{align*}

It all works beautifully.


the type system does not tell the whole story due to "exception"

There have been numerous type systems dealing with exceptions and other kinds of computational effect, so the reason it doesn't appear in O'Caml is not that it cannot be done. I think there are two reasons why exceptions do not appear in types:

The types that programmers have to write become larger.
Exception typing interacts poorly with subtyping and higher-order features, such function types. Ultimately, this is because exception declarations will be an over-approximation of the exceptions that will be thrown, so reusable code needs to have very general exception declarations. For example, the exception declarations for a higher-order function need to be general enough to describe all possible functions passed to the higher-order function. Similarly, the exception declarations on a superclass need to anticipate all possible exceptions that can occur in the subclasses.  (Subtyping among exception types alleviates this problem somewhat.)

Java is a good example programming language that has exception typing and these two problems.

Here is some of the research done in the area:

Type-based analysis of Uncaught Exceptions by Xavier Leroy and Francois Pessaux
Monadic effects by Andrzej Filinski
A type system for call-by-name exceptions by Sylvain Lebresne
A theory of substructural types and control by Jesse A. Tov and Riccardo Pucella

Looking at these papers and chasing the references within will give you more details of what has been done in the field.


Minimax agnostic risk for Lipschitz functions

Sasha Rakhlin kindly pointed me to:
https://projecteuclid.org/euclid.bj/1486177384

where a rate of $n^{-2/3}$ is shown.


Given a graph, decide if its edge connectivity is at least n/2 or not

You can easily check this in linear time, since a graph has edge
connectivity at least $n/2$ if and only if its minimum degree is at
least $n/2$. You already argued for the “only if” part. Consider now a
graph where every vertex has degree at least $n/2$ and a cut that
divides the graph into two vertex sets $X$ and $\bar X$ with $x := |X|
\leq n/2$. A vertex in $X$ can have at most $x - 1$ connections to
other vertices in $X$, and thus must contribute at least $n/2 - (x -
1)$ edges to the cut. Thus, the cut must have size at least $x (n/2 -
x + 1)$. It remains to show that $x (n/2 - x + 1) \geq n/2$, which is
true since $(x - 1)(n/2 - x) \geq 0$.

Strangely enough, the only reference I find to this result is this from a bioinformatics conference. I'd be really curious to see whether it has been proven somewhere else.

Edit: An earlier reference is: Gary Chartrand: A Graph-Theoretic Approach to a Communications Problem, SIAM J. Appl. Math. 14-4 (1966), pp. 778-781.


Simulation of deterministic turing machines

For what regards (apparently) "weaker" models, one of the recent new results that I saw is that a deterministic Turing machine can be efficiently simulated by a 2-tag system:
Damien Woods and Turlough Neary, On the time complexity of 2-tag systems and
small universal Turing machines (FOCS 2006)

...

Theorem 1: Given a single tape deterministic Turing machine $M$ that computes in time $t$ then there is a 2-tag system TM that simulates the computation
of $M$ and computes in polynomial time $O(t^4(\log t)^2)$.

...

Corollary 1: The small UTMs of Minsky, Rogozhin and others are polynomial time, $O(t^8(\log  t)^4)$, simulators of Turing machines.


Is there a standard definition of Quantum Randomness?

The randomness used in quantum computing comes from quantum mechanics and is postulated to be an inherent 'randomness' of nature (and one of the problems Einstein, for instance, had with QM). If you take a state like

$|+\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}$

and measure it in the computational basis, there is absolutely nothing you can do to predict the result (assuming our standard pictures of QM is not horribly wrong). Half the time you will measure $0$ and half the time you will measure $1$. Of course, if you measure in the Hadamard ($|+\rangle$, $|-\rangle$) basis, then your result will always be $+$.

I don't think there is a standard notion of quantum randomness, mostly because how random a state looks depends on your choice of measurement. Once you choose a particular basis to measure in, then you might as well start talking about the classical probabilities associated with the results and then you can do your standard classical tests of randomness.

Usually when someone talks about the 'quantumness' of a state, they try to capture ideas like entanglement.


I think you are looking for a typed variant of anti-unification. Anti-unification can be described as follows. First, suppose that we have a grammar of terms as follows:

t ::= () | (t, t) | C t | X

Here, () and (t, t) denote units and pairs, C t is a term with a leading constructor, and X is a term variable, which could be substituted for any term.

The anti-unification problem says, if you give two terms t1 and t2, what is the least general term t such that there are substitutions s1 and s2 such that s1(t) = t1 and s2(t) = t2.

As a concrete example, given two terms

t1 = Cons(3, Cons(2, Cons(1, Nil)))
t2 = Cons(1, Cons(2, Cons(3, Nil)))

the anti-unification algorithm would return the anti-unifier

t = Cons(X, Cons(2, Cons(Y, Nil)))

because the substitutions s1 = [X:3, Y:1] and s2 = [X:1, Y:3] applied to t would give you t1 and t2 back. As an aside, we needed to  specify "least general" because otherwise:

t' = Z

with the substitutions s1 = [Z:t1] and s2 = [Z:t2] would do the trick.

Anti-unification was invented by Gordon Plotkin, and is a delightfully simple algorithm. Assume you have an injective name-generation function gen $: \mathrm{Term} \times \mathrm{Term} \to \mathrm{Var}$. Then we can find an antiunifier as follows

antiunify ()       ()         = ()
antiunify (t1, t2) (t1', t2') = (antiunify t1 t1', antiunify t2 t2')
antiunify (C t)    (C t')     = C (antiunify t t')
antiunify t        t'         = gen(t, t') -- default: t and t' dissimilar

Augmenting this algorithm to return the two substitutions s1 and s2 I leave as an exercise.


Constructing terms of function types out of the empty type

I already answered how to construct such terms in a related question, so let me just amend that answer with some equations.

A standard type constructor which has constructors and eliminators, for instance $A \times B$ has pairing and projections, will have:

$\beta$-rules which says how destructors operate on constructors, for instance: $\pi_1 (a,b) \equiv a$,
$\eta$-rules which say that if we take a thing apart with destructors and put it back together we get the original thing, for instance: $(\pi_1\,u, \pi_2,u) = u$.

The empty type is special because it has no constructors, so where do equations come from? We can take the idea that $\mathbf{0}$ is the initial type and express it as an equation:
$$\mathsf{absurd}_A(e_1) \equiv_A e_2 \tag{1}$$
where $\mathsf{absurd}_A : \mathbf{0} \to A$ is the eliminator (it could also be written as an empty case statement), $e_1 : \mathbf{0}$ and $e_2 : A$. The equation says that $\mathsf{absurd}_A(e_1)$ is equal to every term of type $A$, which is absurd, as it should be. The effect of the equation is that as soon as we have a variable $x : \mathbf{0}$ in the typing context, everything becomes trivial. In categorical language, slicing over $\mathbf{0}$ gives the terminal category -- which is just another way of saying that $\mathbf{0}$ is a terminal object.

We can now show that every two maps $f, g : \mathbf{0} \to A$ are equal, simply because
$$x : \mathbf{0} \vdash f\,x \equiv \mathsf{absurd}_A(x) \equiv g\,x$$
and now by congruence rule for $\lambda$ and $\eta$-rule for functions
$$f \equiv (\lambda x : \mathbf{0} \,.\, f\,x) \equiv (\lambda x : \mathbf{0} \,.\, g\,x) \equiv g.$$
Note however that (1) above is not the kind of equation that type theorists like, because it screwes up various algorithms for checking equality of terms.


Computational complexity of the 3-partition problem with distinct numbers

It is proved in [1, Corollary 7], that 3-partition is strongly NP-hard when the integers $a_1, \ldots, a_n$ are all distinct. The bounds $B/4 < a_i < B/2$ are not imposed in [1], but this should not make a difference.

[1]: Heather Hulett, Todd G. Will, Gerhard J. Woeginger: Multigraph realizations of degree sequences: Maximization is easy, minimization is hard. Oper. Res. Lett. 36(5): 594-596 (2008). DOI


Here are answers to your two questions. The details will depend upon which solver you are using:

Ensuring that $w$ and $x$ are assigned values before $y$ and $z$ can often be done programmatically by expressing the variable ordering used by the solver. That is, specifying which variables the solver tries to find values for first. This is possible, for example, in the choco solver (which is a constraint satisfaction problem (CSP) solver not one for LP or MILP), though I'm sure other solvers offer this possibility too.
The GNU Linear Programming Kit actually has an if-then-else construct for expressing conditionals. Look for "conditional" in the manual. You could wrap the clauses you are interested in in such a statement: if U1 + U2 < T2 then y = 0 and z = 0 else true. (Note that I haven't actually tried this, so the syntax may be wrong.)
An alternative answer to the second question takes advantage of the fact that $U1$, $U2$ and $T1$ are constants. Simply, have two variants of the LP problem, one for when $U1 + U2 < T1$ and one for when $U1 + U2 \ge T1$.


Throwing Balls into Bins, estimate a lowerbound of its probability

The answer is $\Theta(\sqrt{n})$.

First, let's compute $E_{n-1}$.

Let's suppose we throw $n$ balls into $n$ bins, and look at the probability that a bin has exactly $k$ balls in it. This probability comes from the Poisson distribution, and as $n$ goes to $\infty$ the probability that there are exactly $k$ balls in a given bin is $\frac{1}{e} \frac{1}{ k!}$.

Now, let's look at a different way of distributing balls into bins. We throw a number of balls into each bin chosen from the Poisson distribution, and condition on the event that there are $n$ balls total. I claim that this gives exactly the same distribution as throwing $n$ balls into $n$ bins. Why? It is easy to see that the probability of having $k_j$ balls in the $j$th bin is proportional to $\prod_{j=1}^n \frac{1}{k_j!}$ in both distributions.

So let's consider a random walk where at each step, you go from $t$ to $t+1-k$ with probability $\frac{1}{e}\frac{1}{k!}$. I claim that if you condition on the event that this random walk returns to 0 after $n$ steps, the probability that this random always stays above $0$ is the probability that the OP wants to calculate. Why? This height of this random walk after $s$ steps is $s$ minus the number of balls in the first $s$ bins.

If we had chosen a random walk with a probability of $\frac{1}{2}$ of going up or down $1$ on each step, this would be the classical ballot problem, for which the answer is $\frac{1}{2(n-1)}$. This is a variant of the ballot problem which has been studied (see this paper), and the answer is still $\Theta\left(\frac{1}{n}\right)$.
I don't know whether there is an easy way to compute the constant for the $\Theta\left(\frac{1}{n}\right)$ for this case.

The same paper shows that when the random walk is conditioned to end at height $k$, the probability of always staying positive is $\Theta(k/n)$ as long as $k = O(\sqrt{n})$. This fact will let us estimate $E_s$ for any $s$.

I'm going to be a little handwavy for the rest of my answer, but standard probability techniques can be used to make this rigorous.

We know that as $n$ goes to $\infty$, this random walk converges to a Brownian bridge, i.e., Brownian motion conditioned to start and end at $0$. From general probability theorems, for $\epsilon n < s< (1-\epsilon)n$, the random walk is roughly $\Theta(\sqrt{n})$ away from the $x$-axis. In the case it has height $t>0$, the probability that it has stayed above $0$ for the entire time before $s$ is $\Theta(t/s)$. Since $t$ is likely to be $\Theta(\sqrt{n})$ when $s = \Theta(n)$, we have $E_s \approx \Theta(1/\sqrt{n})$.


What’s the best way to test if a sphere is a polytope? (the Simplicial Steinitz Problem)

This is not an answer, just a comment.
Frank Lutz in Berlin is one of the experts on this topic, and you might ask him.
He maintains a nice web page,
The Manifold Page, which includes lots of information and references, including
descriptions of
Barnette's non-polytopal 3-sphere and
Grünbaum-Sreedharan's non-polytopal 3-sphere.

Incidentally, I believe this related problem is still open (if not, I'd like to know of its resolution):

  Does every triangulation of a genus 1 torus have a geometric realization (embedding) in $\mathbb{R^3}$?

For sufficiently large genus (I think 5?), there are non-realizable examples.


Reference request: Skeptics of classical threshold theorem

It has been a while since I read von Neumann's paper, but I don't recall having the same impression that Scott Aaronson had. It seemed to me that von Neumann was addressing an argument that human brains must be qualitatively different from computers, because while human brains' individual components, neurons, are unreliable, human brains on a whole are much more reliable than electronic computers are.

While Claude Shannon does not actually make this argument explicitly in his 1953 paper "Computers and Automata" (it's quite possible other people did), he certainly brings up the question of reliability and brains. I have extracted a few sentences below:

  The brain has often been compared, perhaps overenthusiastically,
  with computing machines.
  ...
  Comparisons of this sort should be taken well salted—our understanding of brain functioning is still, in spite
  of a great deal of important and illuminating research,
  very primitive.
  ...
  The similarities between the brain and computers
  have often been pointed out. The differences are perhaps
  more illuminating, for they may suggest the important
  features missing from our best current brain
  models. Among the most important of these are:
  ...
  3. Differences in reliability organization. The brain
  can operate reliably for decades without really serious
  malfunctioning (comparable to the meaningless
  gibberish produced by a computer in trouble
  conditions) even though the components are probably
  individually no more reliable than those used
  in computers.


List of number theoretic or algebraic problems in various complexity classes

Algebraic geometry

Noether's Normalization Lemma (NNL) for explicit varieties is currently only known to be in $\mathsf{EXPSPACE}$ (like general NNL), but is conjectured to be in $\mathsf{P}$ (and is in $\mathsf{P}$ assuming that PIT can be black-box derandomized). Update 4/18/18: It was recently shown that for the variety $\overline{\mathsf{VP}}$ it is in $\mathsf{PSPACE}$ over the rationals (Forbes & Shpilka) and then over arbitrary fields (Guo, Saxena, & Sinhababu).
Testing whether a given set of polynomials has an algebraic dependence. This problem was recently shown to be in $\mathsf{AM} \cap \mathsf{coAM}$ by  Guo, Saxena, & Sinhababu (improving the previous upper bound of $\mathsf{NP}^{\mathsf{\# P}}$ due to Mittmann, Saxena, & Scheblechner, also on the arXiv).
There are several (arXiv) new algorithms for computing topological invariants of complex varieties (with various restrictions like smoothness, etc.). I believe for most of these the optimal upper bound is still open.
Hilbert's Nullstellensatz (HN): given integer polynomials, decide if they have a common complex solution, is in $\mathsf{AM}$ assuming GRH (Koiran). It is unknown if it is in $\mathsf{NP}$.
Algorithms for resolution of singularities of algebraic varieties in characteristic zero. The current best time upper bound, due to Bierstone, Grigoriev, Milman, and Włodarczyk is $\mathcal{E}^{d+3}$ where $d$ is the dimension of the variety and $\mathcal{E}^{\bullet}$ is the Grzegorczyk hierarchy of primitive recursive functions. There aren't particularly good (any?) lower bounds on this problem, but for a seemingly much simpler problems related lower bounds are known, namely: There are ideals in $n$ variables generated in degree at most $n$ that require $\mathcal{E}^{n+1}$ such generators. So the current upper bound for resolution of singularities may not be far from the truth, but little is really known.

Isomorphism problems

Many problems on permutation groups - such as coset intersection, permutation group isomorphism, etc. - are in $\mathsf{NP} \cap \mathsf{coAM}$, but it is unknown if they are in $\mathsf{NP} \cap \mathsf{coNP}$, and it is suspected that they are not in $\mathsf{P}$. Graph Isomorphism reduces to most of those problems, so a better upper bound on them implies a better upper bound on GI.
In particular, for permutation group isomorphism, the current best upper bound is $2^{O(n)}|G|$, and it is open if it can be done in $2^{O(n)}$ time (depending only on the degree of the permutation group and not on its order), let alone quasi-poly time like GI and coset intersection.
Group Isomorphism where groups are given by multiplication tables is known to be in $\mathsf{TIME}(n^{O(\log n)})$, but is suspected to be in $\mathsf{P}$. Known to be in $\mathsf{P}$ for several classes of groups (update 4/18/18: and a couple (arXiv) more (arXiv)), but not in general.

Other

Update 4/18/18: Tensor rank over any field $\mathbb{F}$ is $\exists \mathbb{F}$-complete (Schaefer & Stefankovic). Is tensor rank over $\mathbb{Q}$ in $\mathsf{NP}$? It is known to be $\mathsf{NP}$-hard (Håstad), and over finite fields it is in $\mathsf{NP}$.
More generally, many problems on tensors over $\mathbb{Q}$ are $\mathsf{NP}$-hard but not known to be in $\mathsf{NP}$ (Hillar and Lim, also on the arXiv).

It would (somewhat sadly) seem that the Adleman-McCurley survey, despite being 21 years old, is pretty up to date in terms of number-theoretic problems, with the exception of the fact that we now know that $\mathsf{PRIMES}$ is in $\mathsf{P}$...


n-coloring the n x n Sudoku graph is trivial, but if some of the colors are given to you (the extendability version) it becomes NP-complete.

By the "Sudoku graph" I mean the natural graph whose associated coloring problem is Sudoku. Namely, suppose $n=k^2$ is a square. The graph will have $n^2$ vertices, which we will denote by $(r_1, r_2; c_1, c_2)$ for $r_1,r_2,c_1,c_2 \in [k] = [\sqrt{n}]$. For each fixed $(r_1,r_2)$, the vertices $(r_1, r_2; *, *)$ form an $n$-clique; for each fixed $(c_1, c_2)$ the vertices $(*, *; c_1, c_2)$ form an $n$-clique; and for each fixed $(r_1, c_1)$, the vertices $(r_1, *; c_1, *)$ form an $n$-clique.


Yes, there are good (efficient) algorithms.  This is completely solved, and the algorithms are widely used in the cryptographic community.

If $\gcd(n,p-1)=1$, then everything is a $n$th residue.

If $n$ divides $p-1$, then $a$ is a $n$th residue if and only if $a^{(p-1)/n} \equiv 1 \pmod p$.

If $1<\gcd(n,p-1)<n$, $a$ is a $n$th residue if and only if it is a $\gcd(n,p-1)$-th residue (see previous case).

For more details, see Finding roots in ℤp on Crypto.SE.


Is there an NP-complete language that contains precisely half of the n-bit instances?

I asked this question a few years ago and Boaz Barak positively answered it.

The statement is equivalent to the existence of an NP-complete language $L$ where $|L_n|$ is polynomial-time computable.

Consider Boolean formulas and SAT.
Using padding and slightly modifying the encoding of formulas
we can make sure that
$\varphi$ and $\lnot \varphi$ have the same length.

Let $\langle\ \rangle$ be an encoding that

for all formulas $\varphi$ and
for all truth assignment $\tau \in \{0,1\}^{|\varphi|}$,
$|\langle\varphi\rangle| = |\langle\varphi, \tau\rangle|$.
$|\langle\varphi\rangle| \mapsto |\varphi|$ is polynomial-time computable.
the number of formulas with encoded length $n$ is polynomial-time computable.

Consider
$$L := \{\langle\varphi\rangle \mid \varphi \in \mathsf{SAT} \} \cup
\{\langle \varphi, \tau \rangle \mid \tau \vDash \varphi \text{ and }
\exists \sigma<\tau\ \sigma\vDash\varphi \}$$

It is easy to see that $L$ is NP-complete.

If $\varphi \in \mathsf{SAT}$,
the number of truth assignments satisfying
$$\tau \vDash \varphi \text{ and }
\exists \sigma<\tau\ \sigma\vDash\varphi$$
is equal to the number of satisfying truth assignments $- 1$.
Adding $\varphi$ itself it adds up to
the number of satisfying truth assignments for $\varphi$.

There are $2^{|\varphi|}$ truth assignments.
Each $\tau$ either satisfies $\varphi$ or $\lnot \varphi$ (and not both).
For every formula $\varphi$,
consider the $2(2^{|\varphi|}+1)$ strings $\langle\varphi\rangle$,
$\langle\lnot \varphi\rangle$,
$\langle\varphi, \tau\rangle$, and
$\langle \lnot\varphi, \tau\rangle$
for $\tau \in \{0,1\}^{|\varphi|}$.
Exactly $2^{|\varphi|}$ of these $2^{|\varphi|+1}+2$ strings are in $L$.
This means that the number of strings of length $n$ in $L$ is
the number of formulas $\varphi$ of encoded length $n$ multiplied by $2^{|\varphi|}$ which polynomial-time computable.


Travelling Salesman and Planar Travel - Generalized TSP

If the tour is required to visit one node in each group, then the problem is called Group-TSP, or TSP-with-neighborhoods. There's a ton of work on this in the plane (just google it), and in general it's as hard as HITTING SET (the case in which your metric is all 1s). There's a paper by Safra and Schwartz that shows that Geometric group TSP (in the plane) is hard to any constant factor.


Learning a discrete distribution in $\ell_r$ norm

Clément Canonne and I worked this out at some point.

Let $X_j$ be the number of realizations of $j \in [d]$. So $\mathbb{E} X_j = np_j$.
\begin{align*}
  \mathbb{E} J_n^r &= \mathbb{E} \|\hat{P}_n - P \|_r^r \\
    &= \frac{1}{n^r} \sum_{j=1}^d \mathbb{E} |X_j - \mathbb{E}X_j|^r  \\
    &\leq \frac{1}{n^r} \sum_{j=1}^d 3\mathbb{E} X_j  & (*)  \\
    &= \frac{3}{n^{r-1}} .
\end{align*}
We get $(*)$ by a slightly tedious argument you can find in Theorem 5.1 of [1] or I can add here later. It just uses the extreme cases of $r=1$ or $r=2$.

In particular this gives a dimension-free bound. However, one can get a dimension-dependent upper bound simply by using the standard $p$-norm inequalities and the upper bound on the $2$-norm that you state. The dimension-dependent bounds will be better when the dimension is small relative to the number of observations, I believe when $d \leq O(n^{1/q})$ but will have to double-check (where $q = 1 - 1/r$).

[1]:  "$\ell_p$ Testing and Learning of Discrete Distributions" (Bo Waggoner, ITCS 2015), https://arxiv.org/abs/1412.2314


Testing boolean vectors orthogonality with fast query-time

The "offline" version of this question is addressed in my SODA 2014 paper with Huacheng Yu, Finding orthogonal vectors in discrete structures. For the case of $\mathbb F_2$, we give an $O(nd)$ time algorithm for determining, given two sets of $n$ vectors $A$ and $B$, whether there is a vector in $A$ and vector in $B$ with zero inner product.

I'm sure you can modify our algorithm appropriately, and get an interesting preprocessing/query version; we did not consider this question.


1) Here is a paper that studies your question in the case of finite languages $L$, and shows that if a finite language $L$ can be decided by an $n$-state DFA, then any permutation of $L$ can be decided by an $m$-state DFA for some $m \leq \frac13 (n^2 + n + 1)$:

  Palioudakis A., Cho DJ., Goč D., Han YS., Ko SK., Salomaa K. (2015) The State Complexity of Permutations on Finite Languages over Binary Alphabets. In: Shallit J., Okhotin A. (eds) Descriptional Complexity of Formal Systems. DCFS 2015. Springer Lecture Notes in Computer Science, vol 9118.

See slides here.

2) You might be interested in studies of read-once (algebraic) branching programs. Technically, this is a setting where the order of the input matters, but many of the results in this area apply regardless of how the input is ordered. While ro(A)BPs are slightly stronger than DFAs, they are closely related.


Of course if you show a lower bound of $\Omega(n \log n)$ for your question, it would imply the same lower bound for the unrestricted model, which is not known.

On the other hand, you are asking whether it is possible to compute the Fourier transform where each $x_i$ is known within $b$ bits of precision using $\ll n \log n$ arithmetic operations. If true, by the fact that the Fourier transform is a unitary operation (and thus, perfectly conditioned), we would be able to compute Fourier transform of any vector within $b$ bits of precision much faster than FFT, which is certainly not known either.


Why does LTL equivalence (with next oeprator) implie trace equivalence in finite transition machines?

The important thing to notice is that in finite transition systems, two systems $K_1,K_2$ over an alphabet $\Sigma$ are not trace equivalent (for infinite traces) if and only if there exists a finite trace $w\in \Sigma^*$ that is in one of them, but not the other.
Indeed, if $K_1$ and $K_2$ are not trace equivalent, denoted $L(K_1)\neq L(K_2)$, then w.l.o.g. there exists an infinite trace $x\in L(K_1)\setminus L(K_2)$, but we can say something stronger: since the transition systems are finite, we can actually assume $x$ is of the form $x=uv^\omega$ for finite words $u,v\in \Sigma^*$.
This "lasso" structure of $x$ tells us that there is a finite trace $uv^m\in L(K_1)\setminus L(K_2)$, for some $m\in \mathbb{N}$, thus getting rid of the "infinitely many prefixes" problem.
Now, we can define an LTL formula, using "next" operators, that states "$uv^m$ is not a prefix of the trace". This formula holds in $K_2$, but not in $K_1$.


What are some theory problems in Information Retrieval and Search Engines which are not yet solved or can be bettered?

Anaphor resolution:

  Since this type of understanding is still poorly implemented in software, automated anaphora resolution is currently an area of active research within the realm of natural language processing.


Define metric for systems of set of points

Hausdorff distance is what you are looking for.


min hitting set of every base of a matroid

I meant to leave this as a comment, but I don't have the reputation to do so yet.  This question was crossposted over at Mathoverflow, where I mention that the problem is NP-complete.

See here.

To avoid a contradiction with Chandra Chekuri's answer, I do not believe that the LP given in his answer is integral.  To see this consider the uniform matroids $U_{k,n}$, where the bases are all $k$-subsets of a $n$-set.  Note that the vector $(1/k, 1/k, \dots, 1/k)$ is a feasible solution to the LP.  Thus, if $c$ is identically 1, then the minimum value of the LP is at most $n/k$.  On the other hand, a minimum hitting for $U_{k,n}$ has size $n-k+1$.


Are there any open problems concerning decidability?

Given a finite automaton A over the alphabet {0,1}, does A accept the base-2 representation of at least one prime number?   This is currently not known to be either decidable or undecidable.

(By contrast, the same problem with "prime" replaced by "composite" is decidable.)


Algorithm to find s-t min paths in a weighted graph

Try searching for "k shortest paths". There are different answers depending on whether your graph is directed or undirected, whether you allow repeated vertices in your paths, etc.


Answer to A. Barwise & Etchemendy's Language, Proof, and Logic is a decent introduction to logic. From the perspective of someone coming from a CS background I found it especially accessible and fun. It's very clearly written, has lots of examples, and comes with 3 programs:

  Tarski's World: is a block world where you can verify the truths of sentences or find counterexamples in an intuitive, visual environment
  Fitch: is a Fitch-style proof system that will check your proofs
  Boole: is a truth-table tool

Once you're done with the main course (I-II), in part III they have more fun topics to explore:

  ZFC
  program correctness
  resolution
  Skolemization
  metalogic (e.g. Lowenheim-Skolem, Compactness, Incompleteness)

As I said, B & E is an introductory course, so next you can move to what's called mathematical logic, which is more technical but more precise and will turn out to be more rewarding in the long run. A canonical text here is Enderton's A Mathematical Introduction to Logic, which even has a special chapter dedicated to Second-Order Logic (something you said you're interested in). It's not as interactive as B & E, but it's a classic and it will prepare you for more advanced logic.

Answer to B. How to give the semantics of operators should become clear after studying these texts. But if you're looking for special kinds of semantics, such as Kripke,  topological, neighborhood, measure-theoretic, domain-theoretic, probabilistic, etc., you'll have to do a little digging to find papers that explain how these things are done.

Hope that addresses at least some of your questions.


Gowers "discretized Borel determinacy" approach

Let me give a summary of my understanding of the motivation for the approach. Be warned that I am fairly new to the concept of Borel determinacy, and not at all an expert in set theory. All mistakes are mine. Also I am not sure reading this is all that much better than reading Gowers' posts.

I think what Gowers has in mind is not a finitary analogue of the Borel determinacy theorem, but a finitary analogue of the following: Borel determinacy follows from ZFC, while determinacy of analytic games requires the existence of (essentially) measurable cardinals. I will very briefly describe what games we're talking about and what Borel determinacy is, and then I will tie this in with the approach to proving lower bounds. The very high-level idea is to consider the property "allows a finitary analogue of a proof of Borel determinacy to work" as a property that can separate P\poly from NP.

We think of games where two players I and II take turns "playing" an integer. The game goes on forever, so they produce a sequence $x= x_1, x_2, \ldots$. The game is defined by a winning set $A \subseteq \mathbb{N}^\mathbb{N}$ (i.e. a set of sequences). If $x \in A$ then player I wins, otherwise player II wins.

A game is determined if either player I or player II has a winning strategy: a way to decide a next move based on the play so far that guarantees a win. Whether all games are determined turns out to have intimate connections to the foundations of set theory (they are not, if you believe in the axiom of choice). In any case, one  simple example when games are in fact determined is when $A$ is open in the product topology on $\mathbb{N}^\mathbb{N}$, which is a fancy way of saying that membership $x \in A$ can be decided based only on a finite number of elements of $x$. For example the game in which player I wins if she is the first to play an even number is open. Another simple example of determined games is closed games, i.e. games where $x \not \in A$ can be decided based on a finite subsequence of $x$. Closed games are open games with the roles of players inverted.

Now we can come to Borel determinacy, and right after I will try to tie this in with circuits and complexity. A Borel set is a set that can be derived from open and closed sets by repeatedly applying a countable number of unions and intersections. You should think of open and closed sets as your basic sets, and Borel sets as derived from basic sets using several levels of a "small" (= countable) number of simple operations in each level. It turns out that you can prove in ZFC that Borel sets are determined, and there is a precise sense in which this is the best you can do.

The analogy that I think Gowers is drawing here is that Borel sets are like small circuits. In the finite world, we replace the "universe" $\mathbb{N}^\mathbb{N}$ by the hypercube $\{0,1\}^n$. Our basic sets become facets of the cube: $\{x \in \{0,1\}^n: x_i = b\}$ for $b \in \{0,1\}$; these are equivalent to literals $x_i$ and $\bar{x}_i$. You can write AND and OR of literals as unions and intersections of such sets. So, for a boolean functions $f:\{0,1\}^n \rightarrow \{0,1\}$, being able to produce $f^{-1}(1)$ out of $s$ unions and intersections of basic sets is equivalent to having a size $s$ circuit for $f$.

Let me throw a word in about analytic sets. An analytic set is a projection of a Borel set: if $S \subseteq X \times Y$ is a Borel set, then $T = \{x: \exists y\ (x,y) \in S\}$ is analytic. By our correspondence between Borel sets and functions of small circuit complexity, analytic sets are like NP/poly.

Now he draws inspiration from a proof of Borel determinacy to come up with a property (in the Razborov-Rudich sense) to distinguish functions of small circuit complexity from functions of large circuit complexity. The hope of course is that the property avoids the natural proofs barrier.

Martin's proof of Borel determinacy uses a conceptually very neat approach: Martin shows that every Borel game is a the image of an open (in fact clopen) game under a map $\pi$, so that $\pi$ preserves winning strategies -- let's call this a "lift". So what Martin shows is that each Borel game is the image of a game in which the winning set is a basic set. Since open games are easily seen to be determined, this proves Borel determinacy. The proof is inductive, with the base case showing that closed games can be lifted. The important part is that each step of the induction "blows" up the universe: getting rid of one level of the Borel set construction requires lifting a game to a game over a universe that is essentially the power set of the universe of the original game. Interestingly, this is unavoidable: Borel sets that require more levels to define can only be lifted to games over much larger universes. Analytic sets require universes that are so large, that their existence requires large cardinal axioms.

Drawing inspiration from this, Gowers formulates a game in which player I and player II must jointly specify some $x$; player I wins if $f(x) = 1$, otherwise player II wins. Player I can specify the first half of the coordinates, and player II the second half. The intuition now is that games corresponding to simple $f$, i.e. $f$ with small circuit complexity, should allow a Martin-style lift to a relatively small universe, just like Borel games do. On the other hand random $f$ should require double exponential size universes, and hopefully NP-hard $f$ should as well, because they would correspond to analytic games.

Let me be just slightly more concrete about what a Martin-style lift is, but do check Gowers' posts for technical definitions. A Martin-style (in Gowers' terminology, "Ramsey") lift is a lift to a game of specifying some $y \in U$ coordinate by coordinate, where $U$ is the universe and is potentially larger than $2^n$, but now the winning condition is very simple: whether player I or II wins is decided based on the value of a single coordinate of $y$. As in Martin's proof, a lift must preserve winning strategies.

The hope that this may avoid the natural proofs barrier is based on the intuition that the property "has Martin style lift to a small universe" is probably not easy to compute. But at this point it's not clear if the parity function has a lift to a small universe. I worry that the appropriate analogy to Borel sets may be functions $f$ in AC0: finding a small lift for parity would put at least that worry to rest.


Kolmogorov's conjecture that $P$ has linear-size circuits

[Following a suggestion of Kaveh, I am putting my (somewhat extended) comment as an answer]

This "conjecture" of Kolmogorov is just a rumor. It was not published anywhere. In the former USSR, "publishing" mathematics meant something different than what it does today: give a talk at a seminar or tell your colleagues at lunch. Counting papers was not an issue. (Actually, I've also enjoined this way of doing math.) I cannot exclude the possibility that this "conjecture" was just told to Levin by Kolmogorov during their walk to a seminar at Moscow University.  So don't take this too seriously as a formal conjecture; it is just a rumor that (needless to say) hasn't been refuted over the years. But since a giant such as Kolmogorov seriously thought about this problem, and hasn't excluded the possibility of a "devil's power", the conjecture should be treated seriously enough, just as a warning about our possibly wrong intuition on what circuits actually do.

Here is a (very, very rough) speculation of my understanding of this conjecture. Our (apparently wrong) intuition about how circuits work relies on viewing the computation by a program as a sequential process which gradually collects information about the input string. This intuition is borrowed from our view of how a Turing machine works. But each input string $x$ determines a subcircuit (witnessing $f(x)=1$ or $f(x)=0$). And for a circuit to be correct, it is enough that the sets of subcircuits for $f^{-1}(1)$ and $f^{-1}(0)$ are disjoint. That is, a circuit is a compact "local encoding" of a given partition of the $n$-cube. The length of this code is the Kolmogorov complexity of the given binary string $f_n$ of length $2^n$. A polynomial time algorithm, however, does more: it gives one "global encoding" of the entire infinite string $f$ for all $n$. Now, an infinite string $f$ allowing an encoding of size $n^c$ must be "simple", and its prefixes "should" allow even more compact "local" encodings. Of course, it remains a mystery why Kolmogorov thought that "local" encodings even of size $cn$ for some $c$ may then be sufficient...

P.S. Sorry, forgot to add: An excellent confirmation of my "thesis" that circuits should be viewed as (static) codes rather than (dynamic) algorithms is the famous
theorem of David Barrington that the entire class $NC^1$ can be simulated by polynomial-size branching programs of width 5. The "gathering information" view here is totally wrong: it is not even clear how to compute the majority function by keeping only 5 bits of information. A clever idea of David was just to encode the behavior of a given formula by particular sequences of 5-permutations, and to show that accepted and rejected strings will get different codes. The point is that a branching program also does not "compute" --- it rather encodes input strings by its sub-programs: when an input arrives, inconsistent edges disappear, and we have a code of this input.


Generalizations of planar graphs that include hypercubes with large side length in $R^d$

You may want to look at nowhere dense graphs.
http://www.sciencedirect.com/science/article/pii/S0195669811000151

One of the reasons why minor-closedness is natural is the following. We typically want to work with families of graphs rather than specific graphs. And we want to solve problems with arbitrary weights/capacities on edges/nodes. Suppose we want to solve the shortest path problem in a family of graphs. Then, if we allow for zero length and infinite lengths then basically we are allowing minor operations on the family. In some settings it makes sense to work with unweighted graphs where positive results can be obtained for larger families of graphs that are not necessarily minor-closed.


You can get a square-root speed-up with a time-space tradeoff if you are working in $\mathbb{F}_2$.
The matrix $M$ is a no-instance iff there exists a non-zero vector $v$ of Hamming weight $\le k$ (i.e., with at most $k$ non-zero coordinates) such that $Mv=0$.  This is equivalent to saying that there exist $t,u$ of Hamming weight $\le k/2$ such that $Mt=Mu$ (since then $M(t-u)=0$ and $t-u$ has Hamming weight $\le k$).
Now you can enumerate all such $t$ and store $Mt$ in a hashtable, and look for collisions (or, sort the values $Mt$ and look for repeats).  This requires approximately ${n \choose k/2}$ time and space, which is better than your brute-force method.  But again it only works over $\mathbb{F}_2$.
You can improve this a bit further as follows.  Randomly partition the $n$ coordinates into two groups of $n/2$ coordinates, and restrict $t$ to be non-zero only on the first group (its zero on the second group), and $u$ to be non-zero only on the second group (it is zero on the first group).  Then if such $v$ exists, with probability ${k \choose k/2}/2^k \approx 1/\sqrt{\pi k/2}$, there exist $t,u$ that satisfy this restriction.  So, enumerate all such $t$, store $Mt$ in a hashtable, and for each $u$, look up $Mu$ in the hashtable (or, merge a sorted list of $Mt$ values and a sorted list of $Mu$ values).  If you repeat $40 \sqrt{\pi k/2}$ times, with a different partition each time, then you'll have an overwhelming probability of finding a solution if one exists.
This requires $40 \sqrt{\pi k/2} {n/2 \choose k/2}$ time and space, which is better than the above.
It's possible you might be able to apply other algorithms for finding a low-weight codeword in a linear code to this problem, if you are working in $\mathbb{F}_2$.
If you are working over $\mathbb{F}_p$ with $p>2$, then you can still do this method, and the running time will be something like $40 \sqrt{\pi k/2} {n/2 \choose k/2} (p-1)^{k/2}$ time and space.  We can compare this to the brute-force approach of enumerating all subsets of $k$ of the columns, then using Gaussian elimination to compute its rank; that will have running time ${n \choose k} k^3$.  The brute-force approach is better when $n/k \ll p$, and my approach is better when $n/k \gg p$.


Relationship between contracts and dependent typing

On a practical level, contracts are assertions. They let you check (quantifier-free) properties of individual executions of a program. The key idea at the heart of contract checking is the idea of blame -- basically, you want to know who is at fault for a contract violation. This can either be an implementation (which does not compute the value it promised) or the caller (who passed a function the wrong sort of value).

The key insight is that you can track blame using the same machinery as embedding-projection pairs in the inverse limit construction of domain theory. Basically, you switch from working with assertions to working with pairs of assertions, one of which blames the program context and the other of which blames the program. Then this lets you wrap higher-order functions with contracts, because you can model the contravariance of the function space by swapping the pair of assertions. (See Nick Benton's paper "Undoing Dynamic Typing", for example.)

Dependent types are types. Types specify rules for asserting whether or not certain programs are acceptable or not. As a result, they do not include things like the notion of blame, since their function is to prevent ill-behaved programs from existing in the first place. There is nothing to blamed since only well-formed programs are even grammatical utterances. Pragmatically, this means that it is very easy to use dependent types to speak of properties of terms with quantifiers (eg., that a function works for all inputs).

These two views are not the same, but they are related. Basically, the point is that with contracts, we  start with a universal domain of values, and use contracts to cut things down. But when we use types, we try to specify smaller domains of values (with a desired property) up front. So we can connect the two via type-directed families of relations (ie logical relations). For example, see Ahmed, Findler, Siek and Wadler's recent "Blame for All", or Reynolds' "The Meaning of Types: from Intrinsic to Extrinsic Semantics".


Determining the convexity of a set on $S^n$

Yes, at least if you define your terms correctly.

Following standard usage in Riemannian geometry, a subset $M \subseteq S^n$ is convex if and only if, for every pair of points $x$ and $y$ in $M$, some shortest path from $x$ to $y$ lies entirely within $M$.  With this standard definition, any convex subset $M  \subseteq S^n$ is both the convex closure of the points in $M$ and the intersection of all closed hemispheres that contain $M$.  In particular, the only convex subset of $S^n$ that does not lie entirely in a closed hemisphere is the entire sphere $S^n$.  (And yes, $S^n$ is the intersection of the empty set of closed hemispheres containing $S^n$!) Your definition of convexity allows some non-standard convex sets, like the complement of a single point.

Let's assume that the sphere $S^n$ is centered at the origin of $\mathbb{R}^{n+1}$.  Following the standard definitions, a subset $M\subseteq S^n$ is convex if and only if $M$ is the intersection of $S^n$ with a convex cone in $\mathbb{R}^{n+1}$.   So let $C$ be a convex cone in $\mathbb{R}^{n+1}$, and let $M = C \cap S^n$.  Let $C^*$ denote the dual cone of $C$; this is also a convex cone, so the intersection $S^n\cap C^*$ is convex.  Your set $X$ is $S^n \cap (C^* \cup -C^*)$ = $(S^n\cap C^*) \cup -(S^n\cap C^*)$.  Thus, $X$ is the union of two  antipodal convex subsets of $S^n$.


Algorithms for the 2 Dimensional Planar Ising Model over Directed Graphs

If you take the standard Ising model: min $E= -\sum_{i \neq j}J_{ij}S_iS_j$, where $S_k =\pm 1$, and replace $J_{ij}$ with a non-symmetric matrix, it remains the standard Ising model. This is because you can rewrite the terms $- J_{ij}S_i S_j -J_{ji}S_j S_i = - \frac{J_{ij} + J_{ji}}{2} (S_iS_j + S_j S_i)$.

A more interesting asymmetric generalization of the planar Ising model is planar MAX 2-SAT (the problem planar MIN 2-SAT is equivalent). This is the problem MAX 2-SAT where the clauses are on the edges of a planar graph. Planar MAX 2-SAT is NP-hard: look at this paper by Guibas, Hershberger, Mitchell and Snoeyink. Thus, it appears that there may be no interesting polynomial-time generalization of the planar Ising model algorithm.

I should note that for planar MAX 2-SAT to be a generalization of the planar Ising model, you need to restrict the Ising model to polynomial-size integers $J_{ij}$. The obvious reduction also requires a planar multigraph, but there's an easy proof that planar MAX 2-SAT on a graph and on a multigraph are equivalent problems.


Circuits made out of general linear operators are $PP$-complete. See the PostBQP paper by Scott Aaronson  or Schuch's paper on the computational power of PEPS and tensor network contraction.


Have you considered converting this into a semantic problem?  Instead of grammar rules for all permutations of nonterminals { A, B, C }, simply have one rule to recognize (A | B | C)^3 together with special internal code that makes sure only one of each is recognized, otherwise it declares an error.  I would insert an empty production before the above clause, whose reduction triggers initialization of whatever you are using to count A's, B's, and C's, and one after, whose reduction triggers the counter check and (if necessary) asserts the error.  (of course this could get a bit tricky if the grammar is recursive through A, B, and/or C)


NP-hard problems on the class of caterpillars

A caterpillar is equivalent to a list of integers $n_1,n_2,...,n_m$ (given in unary), in which integer $n_i$ represents a central node $i$ and its $n_i$ neighbours.

So your question could be rephrased: "Are there hard problems in which the input is a list of (unary) integers?"

Clearly this is cheating, but a list of integers can encode everything (e.g. a binary number $(0,1,0,0,1,1,0,1)$, a string, a graph, ...), so given a polynomial time instance decoding/encoding algorithm, every problem (in particular all NP-complete problems) can be translated to a problem on a single caterpillar; note that this is not valid for problems in which the input is a single path given in unary: in this case we end up to the open (is it still open? :-) question $P=^?NP$ (through TALLY).

You could change your question to "Are there natural hard problems on caterpillars?", but like in many other contexts the word natural (probably) cannot be defined formally.

As a trivial (fairly natural :-) example of NP-hard problem: "Given a caterpillar $n_1,n_2,...,n_{3m}$ of length $3m$, can it be rearranged into a new caterpillar $n_{j_1}, n_{j_2}, ..., n_{j_{3m}}$ such that all groups of consecutive 3 central nodes (starting from the first) has the same number of total neighbours? ($n_{j_1} + n_{j_2} + n_{j_3} = n_{j_4} + n_{j_5} + n_{j_6} = ...$ and so on)


What is the time complexity of base conversion on a multi-tape Turing machine?

Base conversion can be done in time $O(M(n)\log n)$, where $M(n)$ is a bound on the time complexity of multiplication of two $n$-bit integers. (We assume that $M(n)$ satisfies usual regularity conditions: it is monotone, and $2M(n)\le M(2n)$.)

The standard divide-and-conquer algorithms are described e.g. in Brent&Zimmermann, Modern computer arithmetic, and go as follows:

Conversion from binary to base $b$

Let $a$ be the input number, of length $n$. By repeated squaring, compute the sequence $b$, $b^2$, $b^4$, $b^8$, ..., $b^{2^k}$, where $k\le\log n$ is such that $a<b^{2^k}$.

Using division with remainder, compute $a_0,a_1<b^{2^{k-1}}$ such that $a=a_1b^{2^{k-1}}+a_0$. Recurse with $a_0$ and $a_1$:

That is, in the second stage, compute $a_{00},a_{01},a_{10},a_{11}<b^{2^{k-2}}$ such that $a_0=a_{01}b^{2^{k-2}}+a_{00}$ and $a_1=a_{11}b^{2^{k-2}}+a_{10}$. In the third stage, split each of the 4 numbers in two using division by $b^{2^{k-3}}$, and so on. After the $k$-th stage, we will have a sequence of numbers $<b$, which is the base-$b$ expansion of $a$.

($a$ is its own expansion in base $b^{2^k}$. After the first stage, $a_1a_0$ is the expansion of $a$ in base $b^{2^{k-1}}$. After the second stage, we have the expansion of $a$ in base $b^{2^{k-2}}$, etc.)

The running time is
$$O(M(n)+2M(n/2)+4M(n/4)+\dots)\le O(M(n)\log n).$$

Conversion from base $b$ to binary

Reverse the process above: given the base-$b$ expansion $a_ma_{m-1}\dots a_0$, in the first stage, combine the elements in pairs as $a_{2i+1}b+a_{2i}$ to form the base-$b^2$ expansion; in the second stage, combine the blocks to larger blocks using multiplication by $b^2$ to obtain the base-$b^4$ expansion, and so on. After $\log n$ stages, we will have a single number. The running time is as above.


Probably the simplest approach is to perturb the edge weights symbolically rather than numerically.  Intuitively, you'd like to reassign the weight of each edge as
$$
\tilde{w}(e) = w(e) + \varepsilon \cdot w'(e)
$$
where $w(e)$ is the original edge weight, $w'(e)$ is a secondary edge weight, and $\varepsilon$ is a global scaling factor.  This perturbation scheme has to satisfy two requirements:

Every shortest path with respect to the perturbed edge weights must be also a shortest path with respect to the original edge weights.  It's not hard to prove that for any function $w'$, this property holds for all sufficiently small scaling factors $\varepsilon$.  Rather than spending time figuring out how small "sufficiently small" is, consider instead the limiting behavior as $\varepsilon$ approaches $0$.  Then your perturbed edge weights are best formalized as two-dimensional vectors
$$
\tilde{w}(e) = \big( w(e), w'(e) \big).
$$
The length of any path is also a vector, obtained by summing the vector-weights of each edge on the path.  Comparisons between length vectors are performed lexicographically:
$$
(a, a') < (b, b') \iff a<b \text{ or } (a = b \text{ and } a'<b')
$$
This definition trivially implies that for any paths $\alpha$ and $\beta$, if $w(\alpha) < w(\beta)$, then $\tilde{w}(\alpha) < \tilde{w}(\beta)$.  One nice feature of this scheme is that if shortest paths with respect to $w$ are already unique, the algorithm never even notices $w'$.
Shortest paths with respect to the perturbed edge weights must be unique.  It suffices to choose a function $w'$ such that shortest paths with respect to $w'$ are unique.  There are two standard methods for finding such a function $w'$.

The simplest method is to generate each $w'(e)$ randomly.  The Isolation Lemma of Mulmuley, Vazirani, and Vazirani implies that if each $w'(e)$ is chosen independently and uniformly at random from the set $\{1, 2, \dots, n^4\}$, then with probability $1-O(1/n)$, all shortest paths are unique.  This scheme works for any shortest path algorithm with no run-time penalty and little modification to the algorithm, but it does have a small probability of failure.
A more complex deterministic method (which linear-programming people know as "lexicographic perturbation") indexes the edges from $1$ to $m$ and defines $w'(e_i) = 2^i$.  Clearly every subset of edges has distinct total $w'$eight.  However, using this method requires manipulating $m$-bit integers, so it's more efficient to implement this method symbolically as well.  For any paths $\alpha$ and $\beta$, we have $w'(\alpha) < w'(\beta)$ if and only if the minimum edge-index in $\alpha\setminus\beta$ is smaller than the minimum edge-index in $\beta\setminus\alpha$.  Most shortest-path algorithms only compare paths that share a common prefix (starting at some source node $s$) and are otherwise edge-disjoint.  With an appropriate dynamic tree data structure (e.g., link-cut trees or top trees), it is possible to find the node where the two paths split and the minimum edge-index along the disjoint suffixes in $O(\log n)$ amortized time.  So, this scheme is always correct, but it imposes a penalty in the running time that is only $O(\log n)$ if your algorithm has the right structure, and it requires significant data structure overhead.

You can guess which method I recommend.  My recent journal paper with Sergio Cabello and Erin Chambers describes both of these perturbation schemes in more detail.

There are also more specialized methods for specific algorithms and specific classes of graphs.

  I would also like the "perturbed" shortest path to be chosen uniformly at random from the set of original shortest paths. Is this possible?

I don't know.  In particular, the randomized perturbation scheme I described does not have this property.


How big is the variance of the treewidth of a random graph in G(n,p)?

You don't need to calculate the variance to prove the concentration of tw(G(n,p)) around its expectation. If two graphs G' and G differ by one vertex then their treewidth differs by at most one. You can use the standard method, the Hoeffding-Azuma inequality applied to the vertex exposure martingale to show, for example,

$\mathbb{P}( | tw(G(n,p)) - \mathbb{E} tw(G(n,p))| > t) \le 3 e^{- t^2/(2 n)}$,

so the above probability tends to 0, if, say $t = n^{0.51}$.

The method was first applied to prove concentration for the chromatic number of $G(n,p)$. See B. Bollobás, Random graphs. Springer New York, 1998, page 298.


Asymptotic complexity of sorting using k-comparisons

As I was told by Abhishek Methuku, this has been studied already, in fact several times, see e.g. http://www.researchgate.net/publication/3042594_Sorting_n_objects_with_a_k-sorter

For $k$ large, the answer is close to $n \log_{k!}(n)$ but e.g. $k=3$ seems to be open.


On Defining Probabilistic/Nondeterministic Circuits

I found the following text in [1] (cited below); it shows that---as Ryan pointed out---there must be some function limiting the number of nondeterministic/random inputs; unless it can be judged from other things without ambiguity:

We develop nondeterministic $\mathbf{NC}$ ($\mathbf{NC}$) circuits by uniformly adding guessing gates to families of $\mathbf{LOGSPACE}$-uniform $\mathbf{NC}$ circuits. Let $\mathbf{NNC}(f(n))$ be the class of languages accepted by $\mathbf{LOGSPACE}$-uniform families of $\mathbf{NC}$ circuits with $O(f(n))$ nondeterministic gates or guess gates, where $n$ is the length of the input. We will refer to a circuit from such a family as a uniform $\mathbf{NNC}$ circuit, and such a circuit accepts an input if it outputs a 1. The guessing gates give the circuit a set of guessing inputs, $y$, in addition to the ordinary inputs, $x$. Note that $|x|=n$ and $|y|=f(n)$. An $\mathbf{NNC}$ circuit is said to accept $x$ if and only if there is some string of guessing bits $y$ that causes the circuit to output a 1. Thus, $f(n)$ can be thought of as the maximum number of guess bits used in computations on inputs of length $n$.

[1] Wolf, M. J. 1994. Nondeterministic circuits, space complexity and quasigroups. Theor. Comput. Sci. 125, 2 (Mar. 1994), 295-313. DOI= http://dx.doi.org/10.1016/0304-3975(92)00014-I


Your example is not true, that's why you cannot prove it. If we assume your example is true (which we do using the sorry tactic), then we can prove false. The proof goes as follows. We first pick x to be 0 and p to be the property that a number n is equal to 0. So p x is p 0 is 0 == 0 which is obviously true. Your example now provides us with the proof that p holds for all numbers. We pick 1, which is a contradiction because 0 <> 1.

variables (A : Type) (p : A → Prop)

lemma lma (x : A) : p x → (∀ x', p x') :=
  assume H : p x,
  take x' : A,
  sorry

lemma inconsistent : false :=
  assert h : 0 == 0 → (∀ x, x == 0), from (lma num (λ n, n==0) 0),
  assert e : 1 == 0, begin
    refine (h _ 1),
    reflexivity
  end,
  show false, by cases e

The formula that you posted is also false in first order logic, even ∀ x, p x → (∀ x, p x) is not a true statement. Note that your example is different from the true statement (∀ x, p x) → (∀ x, p x).

The error message that you see stems from the fact that you are trying to use the hypothesis p x where the hypothesis p x' is expected (you are confusing the xes)


Follow-up work by Holm, Rotenberg and Thorup [1] showed that there exists a reachability oracle for planar graphs of size $O(n)$ and query time $O(1)$. This is optimal also for trees (e.g., if the input is a star graph, then you need to know the orientation of every one of the $n-1$ edges).

[1] Holm, Jacob, Eva Rotenberg, and Mikkel Thorup. "Planar reachability in linear space and constant time." 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 2015.


A simple decision problem whose decidability is not known

The Matrix Mortality Problem for 2x2 matrices.  I.e., given a finite list of 2x2 integer matrices M1,...,Mk, can the Mi's be multiplied in any order (with arbitrarily many repetitions) to produce the all-0 matrix?

(The 3x3 case is known to be undecidable.  The 1x1 case, of course, is decidable.)


Using nested dissections you can even solve a linear system (based on a planar graph) in $O(\sqrt{n^\omega})$. This was for example noted in a paper  I have with Günter Rote and Ares Ribó and in this paper by Alon and Yuster.

The former paper also contains an approach how to compute the pairwise resistances between vertices on a a common face in $O(\sqrt{n^\omega})$. This paper by Kenyon might also contain helpful ideas.


Type checking, Hypothetical judgments, meaning explanations and computational type theory

Part of the problem is we cannot say that we have a checker for categorical judgments, because these often reduce to hypothetical judgments. For instance, the categorical judgment $M\in A\to B$ reduces to a hypothetico-general judgment.

In practice, the way that you implement this kind of type theory is by formalizing rules for hypothetico-general equality & membership as a kind of sequent calculus, and then you can write tactics that automate as much of the work as possible. This is the technique used in Nuprl, JonPRL and RedPRL, which all implement type theories of the kind that you describe in your post.


clustering algorithm for non-dimensional data

If the distance function is a metric, then you can employ either $k$-center clustering (where the maximum radius of a ball is minimized) or $k$-median clustering (which minimizes the sum of distances to cluster centers). $k$-center clustering is easy: merely pick the $k$-farthest points, and you're guaranteed to get a 2-approximation via triangle inequality (this is an old result due to Gonzalez).

For $k$-median clustering, there's been a ton of work, too much to review here. Michael Shindler at UCLA has a nice survey of the main ideas.

Both these problems are NP-hard in general, and are hard to approximate to within an arbitrary factor. Note that if you drop the condition of being a metric, things get a lot worse in terms of approximability.

Another, more heuristic approach which might be ok for your application is to use a technique like MDS (multidimensional scaling) to embed your distance matrix in a Euclidean space, and then use one of many different Euclidean clustering methods (or even $k$-means clustering). If you are sure that your distance function is a metric, then you can do a slightly more intelligent embedding into Euclidean space and get a provable (albeit weak) guarantee on the quality of your answer.

Ultimately, as with most clustering problems, your final choice depends on the application, your data size, and so on.