Place n points in a box as far away from each other as possible

This seems to be equivalent to packing disks of max radius -- a very well studied problem, at least if your box is a square, see, e.g.,Circle packing in a square. For heuristics see, e.g., http://www.pack-any-shape.com/


Generalization of the Hungarian algorithm to general undirected graphs?

Edmonds's matching algorithm (also called Blossom Algorithm) solves the maximum matching on general graphs. Actually it is a generalization of alternating paths method. (I am not sure of the name of the method but it shoud be König-Hall method.) It basically finds augmenting paths (see wikipedia page: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm) to extend the current matching and stops if there is no more augmenting paths. In general graphs, the only problem occurs in odd cycles. In the Edmonds's matching algorithm odd cycles are contracted (blossoms) and expended back to have a solution.

There is also a correspondence between Blossom Algorithm and Primal Dual method.
Odd cycles cause fractional extreme points. Therefore we add so called blossom inequalities for each odd cycle.

Minimum weighted perfect matching and maximum weight matching problems could also be handled with this approach.

For details of the algorithm, see
http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm
http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf

For mathematical formulation and the corresponding primal-dual method, see
http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf


Papers on Prolog-like languages without closed world assumption (CWA)

Thank you for a great question! I am looking into papers on related subjects myself--I'll post anything worthwhile that I come across, and would appreciate if you would do the same. = ) Off the top of my head, you might be interested in ileanTAP, a Prolog theorem prover for intuitionistic logic (includes a short paper). Just so the term is not left undefined:

  Intuitionistic logic, or constructive logic, is a symbolic logic system
  differing from classical logic in its definition of the meaning of a statement
  being true. In classical logic, all well-formed statements are assumed to be
  either true or false, even if we do not have a proof of either. In constructive
  logic, a statement is 'only true' if there is a constructive proof that it is
  true, and 'only false' if there is a constructive proof that it is false.
  Operations in constructive logic preserve justification, rather than truth. (Wikipedia)

Have you read Kuhn on scientific paradigm shifts? The problem you have described is generally applicable to all of science: theories (and coherent theoretical domains) are abstracted axiomatic systems, and updating a scientific domain (as opposed to "filling out the missing bits" by using what's already established as "axioms") requires switching from one isomorphic system to another (two systems are isomorphic if they have identical or similar outputs for some narrow set of parameters, e.g. Newtonian physics and GR).


Short answer. Given a finite family of regular languages $\mathcal{L} = (L_i)_{1 \leqslant i \leqslant n}$, there is a unique minimal deterministic complete multi-automaton recognizing this family.

Details. The case $n = 1$ corresponds to the standard construction and the general case is not much different in spirit. Given a language $L$ and a word $u$, let $u^{-1}L = \{ v \in A^* \mid uv \in L \}$. Define an equivalence relation $\sim$ on $A^*$ by setting
$$
 u \sim v \iff \text{for each }L \in \mathcal{L},\ u^{-1}L = v^{-1}L
$$
Since the $L_i$ are regular, this congruence has finite index. Further, it is easy to see that each $L_i$ is saturated by $\sim$ and that for each $a \in A$, $u \sim v$ implies $ua \sim va$. Let us denote by $1$ the empty word and by $[u]$ the $\sim$-class of a word $u$. Let $\mathcal{A}_\mathcal{L} = (Q, [1], \cdot, (F_i)_{1 \leqslant i \leqslant n})$ be the deterministic multi-automaton defined as follows:

$Q = \{ [u] \mid u \in A^*\}$,
$[u] \cdot a = [ua]$,
$F_i = \{ [u] \mid u \in L_i\}$.

By construction, $[1] \cdot u \in F_i$ if and only if $u \in L_i$ and hence $\mathcal{A}_\mathcal{L}$ accepts the family $\mathcal{L}$. It remains to prove that $\mathcal{A}_\mathcal{L}$ is minimal. It is actually minimal in a strong algebraic sense (which implies that it has the minimal number of states). Let $\mathcal{A} = (Q, q_-, \cdot, (F_i)_{1 \leqslant i \leqslant n})$ and $\mathcal{A}' = (Q', q'_-, \cdot, (F'_i)_{1 \leqslant i \leqslant n})$ be two multi-automata. A morphism $f: \mathcal{A} \to \mathcal{A}'$ is a surjective map from $Q$ onto $Q'$ such that

$f(q_-) = q'_-$,
for $1 \leqslant i \leqslant n$, $f^{-1}(F'_i) = F_i$,
for all $u \in A^*$ and $q \in Q$, $f(q \cdot u) = f(q) \cdot u$.

Then for any accessible deterministic multi-automaton $\mathcal{A}$ accepting $\mathcal{L}$, there is a morphism from $\mathcal{A}$ onto $\mathcal{A}_\mathcal{L}$. To prove this, one  first verifies that if $q_- \cdot u_1 = q_- \cdot u_2 = q$, then $u_1 \sim u_2$. Now $f$ is defined by $f(q) = [u]$ where $u$ is any word such that $q_- \cdot u = q$. Then one can show that $f$ satisfies the three required properties.

The end is a bit sketchy, let me know if you need more details.


What do you do when you cannot make progress on the problem you have been working on?

Is this a common situation that a researchers notices that her idea is
  not going to work after considerable amount of work?

Yes. But as you get more experienced, you're able to "fail fast" - learn how to test the idea quickly to see if it passes a 'smell test'.

  What do you do when you realized that an approach you had in mind is
  not going to work and the problem seems too difficult to solve?

It depends. Sometimes the best thing to do is put the problem away for a while and work on something else. Sometimes the failure suggests a different question.

  What advice would you give to a student in my situation?


How to state the adequacy of an encoding of lambda calculus in itself?

As pointed out by others, the obvious definition of an "adequate" coding is that it is equitranslatable with any standard one.  The question is therefore to characterize such codings in terms of more elementary properties.

(Historical note.  Smullyan studied this question in the context of combinatory logic.  When I was a student, Henk Barendregt suggested Smullyan's conjectures to me as a research problem -- which led to my first scientific publication.)  See

http://drops.dagstuhl.de/opus/volltexte/2011/3249/
$\newcommand{\code}[1]{\overline{#1}}$

To summarize, given a map $\code{\cdot} : \Lambda \to \Lambda$, we consider whether there exist combinators satisfying certain properties.  The most significant ones are:

$A\, \code{M}\, \code{N} = \code{MN}$
$B\, \code{M} = \code{\code{M}}$
$P_i\, \code{M_0 M_1} = \code{M_i},\quad i \in \{0,1\}$
$Z_b\, \code{M} = \begin{cases} \lambda x y.x &M \equiv b \in \{I,K,S\}\\
\lambda xy.y &otherwise
\end{cases}$
$\Delta\, \code{M}\, \code{N} = \begin{cases}
\lambda x y. x &M \equiv N\\
\lambda x y.y &otherwise
\end{cases}$
$U\, \code{M} = \code{M}^s$, where $\code{\cdot}^s$ is some standard coding
$U^{-1}\, \code{M}^s = \code{M}$

It is easy to see that any adequate coding has these properties.  The main result of the paper (Corollary 14) is that, for an adequate coding, one of the following suffices:

$A + \Delta$;
$U^{-1} + \Delta$;
$U^{-1} + P_i + Z_b$;
$P_i + Z_b + $ "the range of $\code{\cdot}$ is contained in a recursively enumerable set and there is a combinator that decides whether a given element of this set is in the range or not".


How do you get a "Physical Intuition" for results in TCS?

Like many scientific fields, it can take years to build intuition, but it can take only one new idea to tear that intuition down (and hopefully something nice gets rebuilt in its place).

There are some basic exercises you can use to try to build intuition for some paper you're reading and can't seem to penetrate. Here's one that I still do from time to time. Start with a proof that you don't understand but would really like to, which is very long. As you read each paragraph of the proof, try to write a sentence in your own words about what you think the paragraph is saying, in the margins. Hopefully the proof is written well enough that there are well-defined "parts" to the proof ("do X, then define a new function f, then apply X to f, ..."). If not, then from your sentences, separate the proof into your own parts.

Now for each part, try to write a sentence (in your own words) about what each part is doing. At this point, it could be that you find your earlier sentences are not quite accurate or don't fit well together (your intuition was "off"), so you may refine them so they fit logically together. Now you have a few sentences summarizing the whole proof. Then (now this last part is from my advisor, Manuel Blum) try to think of one word or phrase for the whole thing. This phrase would be the key idea that, in your mind, is what gets the whole argument started. (For example, most existence proofs via the probabilistic method can be summed up by: "PICK RANDOM". In the case of $MA \subseteq AM$, I would say something like "MAKE ARTHUR SPEAK MORE". But maybe something else in the proof feels to be the "key" idea to you, which is perfectly fine. It's your intuition!)

I guess my suggestion may be useful for most mathematics, but I found it very useful for TCS, where many proofs really do boil down to 1-2 really new ideas, and the rest is a synthesis of that idea with what was already known.


Distance of arbitrary vectors to Hadamard code

What you are asking is the covering radius of the Hadamard code. I am not sure what the answer is but the covering radius of the punctured Hadamard code is at least $\frac{N}{2} - \frac{\sqrt{N}}{2}$, i.e. any Boolean vector is at most $\frac{N}{2}-\frac{\sqrt{N}}{2}$ Hamming distance away from some code word of the punctured Hadamard code. The $O(\sqrt{N})$ advantage over $\frac{N}{2}$ is optimal for any set of $O(N)$ points in $\{0, 1\}^N$.

The punctured Hadamard code maps $x \in \{0,1\}^n$ to the sequence $(\langle x, u\rangle\bmod 2)_{u \in \{1\}\times\{0, 1\}^{n-1}}$. It's not hard to see that the distance of the code is still $N/2$ as in the Hadamard code, but the number of codewords is $2N$. If we map each code word to a vector in $\{-1, 1\}^N$ by mapping $1$ to $-1$ and $0$ to $1$ we get vectors $v_1, \ldots, v_N, -v_1, \ldots, -v_N$ such that $\langle v_i, v_j \rangle = 0$ for any $i \neq j$. Taking any $x \in \{0, 1\}^N$ and mapping it to $u := 1 - 2x$ in the same way, we see that $x$ is Hamming distance $d$ away from a codeword if there exists an $i$ such that $|\langle v_i, u\rangle| = N-2d$. In other words, it's enough to show that for any $u \in \{-1, 1\}^N$ there exists an $i$ such that $|\langle v_i, u\rangle| \geq \sqrt{N}$. But this follows from the properties of the $v_i$:
$$
\max_i |\langle v_i, u\rangle|^2 \geq \frac{1}{N}\sum_{i = 1}^N{|\langle v_i, u\rangle|^2} = \sum_{i = 1}^N{u_i^2} = N.
$$
The inequality is by averaging and the first equality is true because $\frac{1}{\sqrt{N}}v_1, \ldots, \frac{1}{\sqrt{N}}v_N$ is an orthonormal basis of $\mathbb{R}^N$.

The fact that no set of $O(N)$ points in $\{0, 1\}^N$ can cover $\{0, 1\}^N$ with radius $\frac{N}{2} - \omega(\sqrt{N})$ is equivalent to the fact that for any $v_1, \ldots, v_M \in \{-1, 1\}^N$, $M = O(N)$, there exists a vector $u \in \{-1, 1\}^N$ such that $|\langle v_i, u\rangle| = O(\sqrt{N})$ for all $i$. This is a restatement of Spencer's "Six Standard Deviations Suffice" theorem from discrepancy theory.


What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper

QMA is defined as the set of problems for which there is a polynomial quantum "verifier" circuit. So I guess the "circuit problem" refers to deciding whether such a verifier circuit has an accepting input. QMA-completeness of the $k$-local Hamiltonian problem is typically proven by encoding this circuit in a Hamiltonian (i.e., "by reduction from the circuit problem"). In this paper instead they prove QMA-completeness of 2-local Hamiltonians by reduction from 3-local Hamiltonians (hence, "not from the circuit problem").


Techniques for Reversing the Order of Quantiﬁers

Reversal of quantifiers is an important property that is often behind well known theorems.

For example, in analysis the difference between $\forall \epsilon > 0 . \forall x . \exists \delta > 0$ and $\forall \epsilon > 0 . \exists \delta > 0 . \forall x$ is the difference between pointwise and uniform continuity. A well known theorem says that every pointwise continuous map is uniformly continuous, provided the domain is nice, i.e., compact.

In fact, compactness is at the heart of quantifier reversal. Consider two datatypes $X$ and $Y$ of which $X$ is overt and $Y$ is compact (see below for explanation of these terms), and let $\phi(x,y)$ be a semidecidable relation between $X$ and $Y$. The statement $\forall y : Y . \exists x : X . \phi(x,y)$ can be read as follows: every point $y$ in $Y$ is covered by some $U_x = \lbrace z : Y \mid \phi(x,z) \rbrace$. Since the sets $U_x$ are "computably open" (semidecidable) and $Y$ is compact there exists a finite subcover. We have proved that
$$\forall y : Y . \exists x : X . \phi(x,y)$$
implies
$$\exists x_1, \ldots, x_n : X . \forall y : Y . \phi(x_1,y) \lor \cdots \lor \phi(x_n, y).$$
Often we can reduce the existence of the finite list $x_1, \ldots, x_n$ to a single $x$. For example, if $X$ is linearly ordered and $\phi$ is monotone in $x$ with respect to the order then we can take $x$ to be the largest one of $x_1, \ldots, x_n$.

To see how this principle is applied in a familiar case, let us look at the statement that $f : [0,1] \to \mathbb{R}$ is a continuous function. We keep $\epsilon > 0$ as a free variable in order not to get confused about an outer universal quantifier:
$$\forall x \in [0,1] . \exists \delta > 0 . \forall y \in [x - \delta, x + \delta] . |f(y) - f(x)| < \epsilon.$$
Because $[x - \delta, x + \delta]$ is compact and comparison of reals is semidecidable, the statement $\phi(x, \delta) \equiv \forall y \in [x - \delta, x + \delta] . |f(y) - f(x)| < \epsilon$ is semidecidable. The positive reals are overt and $[0,1]$ is compact, so we can apply the principle:
$$\exists \delta_1, \delta_2, \ldots, \delta_n > 0 . \forall x \in [0,1] . \phi(\delta_1, x) \lor \cdots \phi(\delta_n, x).$$
Since $\phi(\delta, x)$ is antimonotone in $\delta$ the smallest one of $\delta_1, \ldots, \delta_n$ does the job already, so we just need one $\delta$:
$$\exists \delta > 0 . \forall x \in [0,1] . \forall y \in [x - \delta, x + \delta] . |f(y) - f(x)| < \epsilon.$$
What we have got is uniform continuity of $f$.

Vaguely speaking, a datatype is compact if it has a computable universal quantifier and overt if it has a computable existential quantifier. The (non-negative) integers $\mathbb{N}$ are overt because in order to semidecide whether $\exists n \in \mathbb{N} . \phi(n)$, with $\phi(n)$ semidecidable, we perform the paralel search by dovetailing. The Cantor space $2^\mathbb{N}$ is compact and overt, as explained by Paul Taylor's Abstract Stone Duality and Martin Escardo's "Synthetic Topology of Datatypes and Classical Spaces" (also see the related notion of searchable spaces).

Let us apply the principle to the example you mentioned. We view a language as a map from (finite) words over a fixed alphabet to boolean values. Since finite words are in computable bijective correspondence with integers we may view a language as a map from integers to boolean values. That is, the datatype of all languages is, up to computable isomorphism, precisely the Cantor space nat -> bool, or in mathematical notation $2^\mathbb{N}$, which is compact. A polynomial-time Turing machine is described by its program, which is a finite string, thus the space of all (representations of) Turing machines can be taken to be nat or $\mathbb{N}$, which is overt.

Given a Turing machine $M$ and a language $c$, the statement $\mathsf{rejects}(M,c)$ which says "language $c$ is rejected by $M$" is semidecidable because it is in fact decidable: just run $M$ with input $c$ and see what it does. The conditions for our principle are satisfied! The statement "every oracle machine $M$ has a language $b$ such that $b$ is not accepted by $M^b$" is written symbolically as
$$\forall M : \mathbb{N} . \exists b : 2^\mathbb{N} . \mathsf{rejects}(M^b,b).$$
After inversion of quantifiers we get
$$\exists b_1, \ldots, b_n : 2^\mathbb{N} . \forall M : \mathbb{N} . \mathsf{rejects}(M^{b_1}, b_1) \lor \cdots \lor \mathsf{rejects}(M^{b_n},b_n).$$
Ok, so we are down to finitely many languages. Can we combine them into a single one? I will leave that as an exercise (for myself and you!).

You might also be interested in the slightly more general question of how to transform $\forall x . \exists y . \phi(x,y)$ to an equivalent statement of the form $\exists u . \forall v . \psi(u,v)$, or vice versa. There are several ways of doing this, for example:

Skolem normal form,
Herbrand normal form,
Gödel's functional interpretation.


How to find the set of edges for the directed graph associated with a partial order?

As Yury already mentioned, the output size can be too large to hope for subquadratic time, when measured as a function of the input size $n$. But even when the output size is small, very little can be done. In particular, suppose that the input is a partial order with a single comparable pair, chosen uniformly at random among all such partial orders. Then the output size is $O(1)$ but nevertheless it takes $\Omega(n^2)$ queries to find the comparable pair. This is true regardless of whether you're considering only deterministic algorithms or whether you're doing expected case analysis of randomized algorithms.


Assistance in showing computational equivalence between software and hardware computing systems

These issues are clearly and accessibly covered in Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach, specifically in the chapters "The computational model and why it doesn't matter", "NP and NP completeness", and "Boolean circuits" (respectively chs. 1,2,6).

Very generously, an on-line draft of this book has been provided by the authors ... this has been a big help to me in my own researches!

From the viewpoint of complexity theory, the various theorems and proof technologies in Arora and Barak's exposition provide little grounds for  "divorcing the process of computation from the agent of computation"  (in the phrasing of the question).

From a regulatory perspective, however, it is well to keep in mind the legal maxim:

  "Justice is the tolerable accommodation of the conflicting interests of society, and I don't believe there is any royal road to attain such accommodation concretely."

  --  Judge Learned Hand

In real-world medical practice, and in many other regulatory contexts such as aircraft safety, commonly it is legally and practically necessary to distinguish between hardware and software, even though all parties recognize that the mathematical foundations for this distinction are highly imperfect.


I believe it's NP-hard, by a reduction from min-balanced cut.  Given a graph $G=(V,E)$ and integer $\ell$, min-balanced cut asks whether there is a cut that is balanced (has $|V|/2$ vertices on each side), and cuts at most $\ell$ edges.  Given $G$ and $\ell$, construct the following instance of your problem.  For each vertex $v$, create a set $S_v$ containing the edges incident to $v$.  Take $k=|V|/2$.  Then the (minimal) $k$-good partitions are partitions of the sets into two equal-size groups, corresponding to the balanced cuts of $G$, and your (unweighted) cost for such a solution equals $|E|$ plus the number of edges cut.  Unless I'm mistaken :-).

EDIT: Similarly you can reduce the following problem to yours: given a graph $G=(V,E)$ and integer $\ell$, color the vertices of $G$ so that each color class has at most $k$ vertices, minimizing the number of edges whose two endpoints have the same color.  (The reduction: make a set $S_v$ for each vertex $v\in V$, containing the pairs $\{v,w\}$ not in $E$.)


Find the most/least repeated group of N-members in given draws

First, count the occurences of each number overall, and call it C(x):

1: 2
2: 0
3: 1
4: 2
etc ...

Next, we want to find the most common pairs. We know that any pairs C(x, y) <= Min(C(x), C(Y)). Using this we can find the Y "most likely" pairs. We then run through the sequences and count these most likely pairs. As long as the C(most likely pair) is greater than the estimate for the Y'th most likely pair, we know we have found the most common pair. If it isn't, we generate the next Y most likely pairs and then count those as well.

We can extend this to sets of three: C(x, y, z) <= Min(C(x, y), C(x, z), C(y, z)). So for this to work, we need to keep calculating the most common pairs until we find three pairs that we can chain into a triplet. We then need to keep going until we prove that all other triples must have a lower count, following the same logic as used by pairs.

It's basically a heuristic guided search of the possible solutions.


What is the initialization time of a link-cut tree?

Many thanks to Hsueh-I Lu, my teacher in National Taiwan University, who provides the following solution.

It turns out that the answer is rather simple; in the initialization of a data structure, we don't have to construct the structure by the queries and operations it supports. Of course, we cannot perform queries during the construction like we usually do if we build the tree by link operation; but in this separator decomposition application we don't need it.

That is to say, in the application to the separator decomposition, when we have to construct the link-cut trees L(T) for the spanning tree T on input graph G, instead of computing the structures and values of the trees L(T) by link operation, we directly compute the heavy-light path decomposition of the tree T, and construct the corresponding binary tree structure for each paths, and gluing the binary trees according to the path decomposition. All the steps can be done in linear time.

For each necessary values on the nodes of L(T), since each value can be compute from T in linear time (in this application), instead of assigning values on binary tree structures and updating when gluing the trees, we assign the precomputed values directly onto the nodes of the final link-cut trees L(T). There are only a constant type of values need to be assigned, and again this can be done in linear time.


Nearly Optimal Sparse Walsh-Fourier Tranform

As the quoted paper itself summarizes in its introduction,

  The past two decades have witnessed significant advances in sublinear sparse Fourier algorithms. The first such algorithm (for the Hadamard transform)

(which is what you are looking for)

  appeared in KM91 (building on GL89). Since then, several sublinear sparse Fourier algorithms for complex inputs were discovered [Man92, GGI+02, AGS03, GMS05, Iwe10, Aka10, HIKP12].

Some of the quoted papers (e.g. Aka10) give similar results for Fourier transforms over all Abelian groups.


Canonical way of coloring graphs (individualization) for isomorphism purpose

Typically the way individualization goes is this. You're trying to decide if two vertex-colored graphs $G$ and $H$ are isomorphic in a way that respects the colors (sends vertices of color $c$ in $G$ to those of the same color $c$ in $H$). You pick a vertex $v$ in $G$ and assign it a new color, say $c$, that has not been used before. This is called "individualization." Then for each vertex $w \in V(H)$ you will, in turn, try coloring $w$ with $c$ and see if there is an isomorphism $G \to H$ that respects this new coloring. (This incurs a multiplicative cost of $|V(H)|$, so you don't want to do this too often.) In other words, you are guessing the vertex $v$, and then trying to see which vertices of $H$ it can possibly map to.

To aid in this quest, frequently individualization is followed by a process called (Weisfeiler-Lehman) refinement. What happens here is that you assign new colors to each vertex according to the multi-set of colors of its neighbors. Then you do this again. Then you do this again. And you keep doing this until the partition of vertices by color does not change.

An isomorphism-invariant coloring of graphs is a method of assigning colors to vertices so that if two graphs are isomorphic, then there is an isomorphism between them that sends vertices of color $c$ to vertices of color $c$. Some authors will call this coloring canonical - and indeed, in the paper you cite, it may be that all they need is a canonical coloring in which each color class has bounded size. (Other authors might say that a canonical coloring is an isomorphism-invariant coloring in which each vertex receives a color that is distinct from that of all other vertices. In this way, if we can compute a canonical coloring of two graphs $G,H$, then there is only one possible isomorphism between them (namely, the one that respects the colors), and it is easy to check whether this is actually an isomorphism.)

Combined with individualization, one can talk about a coloring that is canonical relative to the individualizations that have been made previously. That is, it may not be canonical with respect to isomorphisms of the original graphs, but given the vertices that have been colored so far it is canonical. (In this sense individualization is a form of "partial brute-force search," in which you keep track of how the guesses you've made so far constrain your future search.)


Which model of computation to simulate to prove universality?

There's a comprehensive treatment of different Turing-complete computation models and proofs of their equivalence in Martin Davis, Computability and Unsolvability. Some of the most popular systems are described, including Turing-Machines, Post problems and general recursive functions.


A Lambda calculus for invertible (r-Turing computable) functions

I am not very familiar with the area, but there is some recent work from the programming languages community that might interest you, based on the idea of restricting to a language of type isomorphisms.  In particular, you could have a look at

Fractional Types by Roshan P. James, Zachary Sparks, Jacques Carette, and Amr Sabry

as well as various related publications which you can find on Amr Sabry's website.


Can you assign a type to any term of the λEA-calculus?

For question 1, the answer is no, and is no for almost any type discipline (except certain intersection types): the fact that a term is (strongly or weakly) normalizable does not imply in general that it is typable.  Typability implies termination, not the other way around.

The specific case of of $\lambda EA$, however, brings up another issue which may be the object of confusion, so let me discuss it.  Let us start with a counter-example for your question 1: the term
$$[M]_{\lambda x.N=y,z}$$
is not typable. This is because the construct $[M]_{P=y,z}$ represents contraction of variables $y$ and $z$ in $M$ (i.e., $y$ and $z$ are morally equated in $M$ and $P$ is "plugged in" on them), so for such a term to be typable $P$ must have type $!A$, i.e., it must be duplicable. Now, in my example, $P$ is an abstraction and can never receive type $!A$ (its type will always have the form $B\multimap C$).

There are many more examples like this in $\lambda EA$.  Intuitively, typability ensures more than termination: it also avoids "clashes", i.e., a term may stop its reduction because it "gets stuck".  Typically, this happens when a destructor of a certain form meets a constructor of a different form (e.g., a head::tail pattern that is matched, i don't know, against a binary tree).  For example, in the above case, the constructor matching the destructor $[M]_{P=y,z}$ is $!(-)$, not $\lambda$, i.e., if $P$ ever reduces to something with a constructor at the root, one expects $P=!(N)[\ldots]$, not $P=\lambda x.N$.

In truth, typability is orthogonal to termination. There may be a misunderstanding about this because, in the context of the pure $\lambda$-calculus, which is the one used for showcasing type disciplines to a beginner, there are no "clashes" (there is only one constructor and one destructor), so clash-avoidance is completely hidden and only termination shows up.  But as soon as one spices things up a bit, adding more constructors and destructors, the distinction between termination and clash-avoidance arises, and types are seen to actually ensure the latter more than the former (for instance, PCF is a typed language which does not terminate, as is every real-world functional programming language).  Mor precisely, types always ensure clash-avoidance and might, in many cases of interest, also ensure termination.

Regarding your question 2, I am guessing that by "same characteristic" you mean the fact that the untyped calculus terminates?  In this case, it may not be very common for the programming languages one considers in practice, but it is not very hard to come up with examples, which must not necessarily have anything to do with linearity (for instance: consider any programming language with no gotos and having a distiction between "for" and "while" loops; eliminate while loops; the language you obtain terminates, whether you have types or not). The interest of $\lambda EA$ is not that it terminates but that it does so with an interesting complexity bound (elementary).


Near-Sort quicksort algorithm faster than O(nlgn)

You can't do it. Suppose you start with an array where everything is sorted to distance $k$. Then, you can use a modified QuickSort to sort this array in time $n \log k$.

  First, choose pivot elements every $k$ elements. Now, sort the array so everything is in place with respect to these elements. (You can do this in time $O(n)$ using a modified version of Quicksort. First, put everything to the left of the first pivot element on the correct side of this pivot element. This takes $O(k)$ time. Next, put everything between the first and second pivot elements on the correct side of the second pivot element. Repeat for the rest of the pivot elements, from left to right.) Finally, sort each of the sublists between the pivot elements.

This will take total time $O(n \log k)$. Now, if you could take an arbitrary array to a nearly-sorted array in time less than $o(n\log n - n \log k)$, we would sort in time $o(n \log n)$. We can't do this.

Thus, there is an $\Omega(n \log \frac{n}{k})$ time bound on near-sorting.


On-policy/Off-policy Offline/Online Evaluation: Which would be an example of Online Off-Policy Evaluation?

Online/Offline learning

Whether your algorithm learns online or offline is governed by when the agent's experience is able to contribute to its learning.

For example, consider value iteration algorithms for action values. If you use Monte Carlo methods to calculate your value updates, then you'd be performing offline learning as the agent will have to reach the end of an episode to calculate the full MC return for any action value. The full Monte Carlo return and the action value definition (expected return) is given by

$G_t = R_{t+1} + γ R_{t+2} + γ^2 R_{t+3} + … + γ^{T-t-1} R_T$, and

$ q(s,a) = E[R_{t+1} + γ R_{t+2} + γ^2 R_{t+3} + … + γ^{T-t-1} R_T \ |\ S_t = s, A_t = a]$

where $T$ signifies last time step of the episode, and $\gamma$ is the discount factor

On the other hand if you use Temporal Difference methods, the action values can be updated right away by bootstrapping to already calculated values, making the learning online. We use the recursive definition of return to get recursive definition of value (expected return) in TD methods.

$G_t = R_{t+1} + γ G_{t+1}$, and

$ q(s,a) = E[R_{t+1} + γ\ q(S_{t+1}, a') \ |\ S_t = s, A_t = a]$

On-policy/Off-policy learning

This depends on the update function you're using to move your state/action value estimates towards the real expected return of the defintion.

For example, in case of SARSA (update action values to evaluate behavior policy) with 1-step TD updates, we have the update function as

$Q_{t+1}(S_t, A_t) = Q_t(S_t, A_t) + α (R_{t+1} + γ\ Q_t(S_{t+1}, A_{t+1}) - Q_t(S_t, A_t))$

Since this method uses the action value for that action which is actually performed in the next state ($a' = A_{t+1}$ for $q(s,a)$ estimate), the estimates will converge to action values for the behavior policy, and not for the optimal policy. Hence, it is a form of on-policy learning.

Now if you consider Q-learning, the update function is

$Q_{t+1}(S_t, A_t) = Q_t(S_t, A_t) + α (R_{t+1} + γ\ max_{a'} Q_t(S_{t+1}, a') - Q_t(S_t, A_t))$

Here, we don’t need to know what action is to be taken from the next state, $S_{t+1}$.
We use the maximum q-value across all actions for the next state to calculate our estimate ($a' = argmax_{a'} Q_t(S_{t+1}, a')$ for $q(s,a)$ estimate).
Because of this, the agent learns q-values for the optimal or greedy policy, regardless of the one it is following currently ($A_{t+1}$ doesn’t affect the q-value update). Hence, it is an example of off-policy learning.

Given this information, an example of On-policy/offline evaluation would be simple Monte Carlo learning, where action values are calculated as the average of Monte Carlo returns over multiple episodes.

And an example of Off-policy/online evaluation would be Q-learning with 1-step TD updates. Because of bootstrapping in TD updates, it is online, and due to the nature of the update function (given above), it estimates optimal values.


Concatenative binary lambda calculus/combinatory logic

As per @cody's comment above, if we require only that "the concatenation of any two programs is a valid program" then I believe that Iota, Jot and Zot (semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html) are examples of a).

However, IMO the more interesting question part of the question is b)...


The standard well-formed-related predicate can be relatively easily extended to handle untyped PHOAS.  The main subtlety is how to handle reduction at the type level.  Here's a start of a two-place relation for well-typed in Coq:

Require Import Coq.Lists.List.
Reserved Infix "@" (left associativity, at level 11).
Local Open Scope list_scope.

Inductive expr {var : Set} : Set :=
| Var (v : var)
| U : expr
| Pi (s : expr) (d : var -> expr)
| Abs (tx : expr) (f : var -> expr)
| App (f x : expr).
Declare Scope expr_scope.
Delimit Scope expr_scope with expr.
Infix "@" := App : expr_scope.

Inductive wf {var1 var2} : list ((@expr var1 (* t1 *)) * var1 * (@expr var2) (* t2 *) * var2) -> @expr var1 (* t1 *) -> @expr var1 -> @expr var2 (* t2 *) -> @expr var2 -> Prop :=
| wf_Var {G t1 v1 t2 v2} : List.In (t1, v1, t2, v2) G -> wf G t1 (Var v1) t2 (Var v2)
| wf_U {G} : wf G U U U U
| wf_Pi {G s1 s2 d1 d2}
  : wf G U s1 U s2
    -> (forall v1 v2,
           wf ((s1, v1, s2, v2) :: G)
              U (d1 v1) U (d2 v2))
    -> wf G U (Pi s1 d1) U (Pi s2 d2)
| wf_Abs {G s1 s2 d1 d2 f1 f2}
  : wf G U s1 U s2
    -> (forall v1 v2,
           wf ((s1, v1, s2, v2) :: G)
              (d1 v1) (f1 v1) (d2 v2) (f2 v2))
    -> wf G (Pi s1 d1) (Abs s1 f1) (Pi s2 d2) (Abs s2 f2)
| wf_App {G s1 d1 s2 d2 f1 x1 f2 x2}
  : wf G (Pi s1 d1) f1 (Pi s2 d2) f2
    -> wf G s1 x1 s2 x2
    -> wf G (App (Abs s1 d1) x1) (App f1 x1) (App (Abs s2 d2) x2) (App f2 x2)
| wf_App_nd {G s1 d1 s2 d2 f1 x1 f2 x2}
  : wf G (Pi s1 (fun _ => d1)) f1 (Pi s2 (fun _ => d2)) f2
    -> wf G s1 x1 s2 x2
    -> wf G d1 (App f1 x1) d2 (App f2 x2).


Number of bits required for encoding variables with fixed sum?

Answer to question 1: $\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode the variables.

Proof: Count how many ways there are to choose $y_1,\ldots,y_r$ such that $y_i \ge 0$ and $\sum y_i = M-r$. There are exactly $\binom{M-1}{r-1}$ such ways (see e.g. here). Now, if there are only $k$ possible values for a variable, then $\lceil \log k \rceil$ bits suffice to encode that variable. Therefore, $opt=\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode our input.

Answer to question 2: This is a bit more tricky. The best approach is to check the literature on succinct rank-select or other succinct data structures: I suspect you can match the results for succinct rank-select, so to get something like $opt+o(M)$ space and $O(\log M)$ running times for all operations. If you're interested, tell me in the comments and I'll try to look it up and tell you my best guess on what's possible. You might also want to check out Dodis-Patrascu-Thorup for some ideas.


General definitions for mixed graphs? (degrees, connectivity, etc)

The definition I found in Zhang, On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias (Section 2.1) is:

  A mixed graph is a vertex-edge
  graph that can contain three kinds of
  edges: directed ($\rightarrow$), bi-directed
  ($\leftrightarrow$) and undirected ($-$), and at most
  one edge between any two vertices.

  ...

  Two vertices are said to be
  adjacent in a mixed graph if there is an edge (of any kind) between them.
  Given a mixed graph $G$ and two
  adjacent vertices A,B therein, A is a
  parent of B and B is a child of A if A $\rightarrow$ B is in $G$; A is called
  a spouse of B (and B a spouse of
  A) if A $\leftrightarrow$ B is in $G$; A is called a
  neighbor of B (and B a neighbor of A) if A $-$ B is in $G$.

  ...

  A directed path from $V_{0}$
  to $V_{n}$ in $G$ is a sequence of distinct vertices
   such that for 0
  $\leq$ i $\leq$ n-1, $V_{i}$ is a parent of
  $V_{i+1}$ in $G$. A is called an
  ancestor of B and B a descendant of A if A = B or there is a directed path from A to B.

Richardson and Spirtes give another nice and simple definition of mixed graphs in Ancestral Graph Markov Models (Section 2.2).

  Note that the three edge types should be considered as distinct symbols, and in particular

  A $-$ B $\neq$ A $\leftrightarrows$ B $\neq$ A $\leftrightarrow$ B.

However, none of them defines in and out degree.


What is the expected depth of a randomly generated tree?

I think there is a concentration result about $e \log n$, but I haven't filled in the details yet.

We can get an upper bound for the probability that node $n$ has $d$ ancestors not including $0$. For each possible complete chain of $d$ nonzero ancestors $(a_1,a_2,...,a_d)$, the probability of that chain is $(\frac{1}{a_1})(\frac{1}{a_2})\cdots (\frac{1}{a_d}) \times \frac{1}{n}$. This corresponds to $\frac{1}{n}$ times a term of $(1+\frac{1}{2} + \frac{1}{3}+ \cdots \frac{1}{n-1})^d$ where the terms are ordered. So, an upper bound for this probability is $\frac{1}{n (d!)} H_{n-1}^d$ where $H_{n-1}$ is the $n-1$st harmonic number $1 + \frac{1}{2} + ... + \frac{1}{n-1}$. $H_{n-1} \approx \log (n-1) + \gamma$. For fixed $d$ and $n \to \infty$, the probability that node $n$ is at depth $d+1$ is at most

$$\frac{(\log n)^d}{n (d!)} \left(1+o(1)\right)$$

By Stirling's approximation we can estimate this as

$$ \frac{1}{n\sqrt{2\pi d}} \left( \frac{e \log n}{d} \right)^d. $$

For large $d$, anything much larger than $e \log n$, the base of the exponential is small, so this bound is small, and we can use the union bound to say that the probability that there is at least one node with $d$ nonzero ancestors is small.

See

Luc Devroye, Omar Fawzi, Nicolas Fraiman. "Depth properties of scaled attachment random recursive trees."

B. Pittel. Note on the heights of random recursive trees and random m-ary search trees.
Random Structures and Algorithms, 5:337–348, 1994.

The former claims the latter showed the the maximum depth is $(e+o(1))\log n$ with high probability, and offers another proof.


Known and described subclasses of Context-Free Grammars class

Density might be interesting concept for you. The density function is defined as
$$\delta_L(n) := |L\cap \Sigma^n|,$$

where $\Sigma^n$ denotes the set of all strings of length $n$ over $\Sigma$.

Your first language seems to have density values of only 0 and 1 while the second goes up to 3. So the first is 1-slender, the second is not following the terminology of  Lucian Ilie's work.


Category theory, computational complexity, and combinatorics connections?

Dave Clarke's comment is quite important. Generally fusion doesn't change the O(-) efficiency.  However, of particular interest is Liu, Cheng, and Hudak's work on Causal Commutative Arrows. Programs written with them are necessarily optimizable, in part through stream fusion, to a single loop free of dynamic memory allocation and intermediate structures: http://haskell.cs.yale.edu/?post_type=publication&p=72


(I have posted this answer as a comment on the question, but I am reposting it with a little more detail.)

This problem is NP-hard as follows.

As is usual in a proof of NP-hardness, suppose that a natural number K is also given as part of input, and consider the yes/no problem of deciding whether at least K customers are satisfied.  Then this problem is NP-complete, even if it is restricted to the case where X=1, m=3K and each customer wants to buy exactly three goods.  (Note that if X=1, the value of Y is irrelevant as long as Y>0.)  In this case, the problem is equivalent to the NP-complete problem called Exact Cover by 3-Sets.

See Garey and Johnson for more on complexity theory and NP-completeness, including the definition of the Exact Cover by 3-Sets and the proof of its NP-completeness.


Reusing 5-independent hash functions for linear probing

One potential issue is when reading from a hash table, the elements should not be read in the order of the slots if all hash tables use the same hash function. This is because those elements, in that order, can cause the insert procedure on a smaller hash table with the same hash function to go quadratic, assuming that the max fill factor is over $1/2$. See:

https://issues.cloudera.org/browse/IMPALA-2653
https://github.com/rust-lang/rust/issues/36481


What is known about the hardness of the chromatic index for restricted graph classes?

Here's one very relevant looking result:

Koreas, Diamantis P. (1997), "The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3", Appl. Math. Comput. 83 (1): 13–17.

The title is self-explanatory.


Exact version of matroid, given the input weight is in unary.

This problem appears to be considered in "Random pseudo-polynomial algorithms for exact matroid problems", P. M. Camerini, G. Galbiati and F. Maffioli, Journal of Algorithms
Volume 13, Issue 2, June 1992, Pages 258-273.

They give a randomized polynomial time for the problem, but they seem to be assuming that the input matroid is representable over the reals, rather than allowing arbitrary matroids. They also state that it is unknown whether it is solvable in P.

However, if all elements of M have weight 0 or 1, then it is easy to solve as a matroid intersection problem.


The search technique simulated annealing is inspired by the physical process of annealing in metallurgy.

Annealing is a heat treatment where the strength and hardness of the substance being treated can change dramatically. Often this involves heating the substance to an extreme temperature and then allowing it to cool slowly.

Simulated annealing avoids local minima/maxima in search spaces by incorporating a degree of randomness (the temperature) in the search process. As the search process proceeds, the temperature gradually cools, which means that the amount of randomness in the search decreases. Apparently it is quite an effective search technique.


Let $k$ be the finite number of agents you're allowed to choose. If there are no critical services, finding the set of $k$ agents that maximize the number of non-critical services provided is equivalent to Max-$k$-Cover, which can't be approximated better than $1-1/e$ unless P=NP. So for an exact solution, you'll have to use something capable of solving NP-hard problems.

If you'd be happy with an approximation, you're in luck. The constraint that you have to choose $k$ agents such that there are sufficiently many of them providing each service is a matroid constraint. This paper shows how to achieve a $1-1/e$ approximation on set cover problems under a matroid constraint.

If you want something simpler to implement, the matroid greedy algorithm gives a $1/2$ approximation on submodular set functions. So you just need to repeatedly choose the agent that provides the most new non-critical services, after at each step removing from consideration any agent whose choice would prevent you from providing enough of each critical service before reaching $k$ agents. If each agent provides unique non-critical services, you're just maximizing a weight function over a matroid, so the greedy algorithm gives an exact solution.


Finding a 5-cycle in a sparse graph efficiently.

To add to Mihai's answer:

Indeed, 5-cycle (and in general $k$-cycle) in sparse graphs can be solved much faster than $O(mn)$ time using the high degree / low degree trick. You need only look at another paper of Alon, Yuster and Zwick:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4120

For example, a 5-cycle can be found in $O(m^{1.67})$ time, without any dependence on matrix multiplication. See Theorem 3.4 of the above linked paper.

Also, while it is not too hard to reduce 5-cycle detection to Boolean matrix multiplication (with constant factor overhead), a reduction in the opposite direction does not appear in the color-coding paper. A tight reduction (which preserves the runtime complexity) from Boolean matrix multiplication to 5-cycle detection is not known.


Why must QMA complete problems be promise problems?

On the second question: http://arxiv.org/abs/0905.4755v2 gives a classical QMA-complete eigenvalue problem related Markov chains.


Complexity status of the Edge Deletion problem to bounded degree graphs

Equivalently, your problem may be stated as follows: You are looking for a subgraph, in which every vertex degree lies in the interval $[0,d]$ and that contains as many edges as possible.

This problem is well-known to be solvable in polynomial time.
For instance, it is discussed in Chapter 10 (and in particular in Exercise  10.1.4) of the book

  M.D. Plummer and L. Lovász:
  Matching Theory
  Volume 29 of Annals of Discrete Mathematics, Elsevier, 1986.


Is it possible to design an efficient approximation algorithm for one NP-complete problem based on Shor's algorithm?

There are ways to see that either the answer is probably no, or that the question means more than one thing and has a negotiable answer.   On the one hand, the PCP theorem says that many, but not all, NP-hard problems are still NP-hard to approximate.   The standard belief is that Grover's search algorithm, which gives you a quadratic speedup but no more than that, is the best quantum algorithm for the hardest NP-hard problems.  This leaves fairly little wiggle room to expect any quantum algorithm to have any special relation to approximation to NP-hard problems in general.

Some NP-hard problems are easier to approximate than the ones amenable to the PCP theorem.   However, the difficulty of approximation is then highly variable.

Meanwhile Shor's algorithm does something very specific:   It finds the period of a periodic function on the integers or on $\mathbb{Z}^n$.   This problem is also in the complexity class SZK, for example.   Maybe you could cook up an approximation problem to an NP-hard problem that lands you in SZK or period-finding, but I suspect that there aren't any known, natural examples of that.


No. Knowing $x$ and $y$ to within multiplicative error bounds of $1\pm\varepsilon$ does not give you a multiplicative error bound on $x-y$. In particular, if $x=y$, being allowed only multiplicative error means that an FPRAS for $x-y$ would have to return exactly zero with probability at least $\tfrac34$, whereas you could end up returning any value $v$ such that $|v|\leq 2\varepsilon\cdot |x|$.


Are there any known implementations for quantum computing constructs?

At this stage progress on experimental quantum computing is relatively slow, but there are now a wide variety of systems that can be used to implement one or more qubits.

At the moment the most developed systems as

Ion traps
Liquid state NMR
Linear optics quantum computing
Superconducting qubits

There has also been a lot of recent work with defects in solid state, solid state NMR, endohedral fullerenes, neutral atom traps, atom chips, etc.

The highest numbers of qubits tend to be in ion traps and NMR, though linear optics is doing well too.

As regards significant experiments, that really depends what constitutes progress to you. There was a very nice experiment back in 2007 where two separate ion traps were coupled optically, and some nice recent work on segmented ion traps, which demonstrate ways of scaling ion trap computation beyond 10 or so qubits. There has also been some very nice implementations of measurement based computation using optics, which is also important for scalability. If you have a better idea of the type of experiments you have in mind it would make the task of answering much easier.

The US quantum computing roadmap, available here, provides an excellent, though slightly dated overview of the state of the art circa 2004.


Multiple subset sum where subsets have complementary cardinality

This is a reduction (attempt :-) from this slight variant of SUBSET SUM (which should be NPC) to prove that E2CSS is NP-complete:

Given integers $A = a_1,a_2,...,a_n\;; a_i > 0$ (with the additional constraint that n is even) and a target sum $b$. Does exist $X \subseteq A$ such that $|X|=2m, m \geq 1$ (i.e. $|X|$ is even and greater than or equal to 2) and $sum(X)=b$?

Reduction: suppose that $2^k > b+\sum_{i=1}^n |a_i|$; then we expand $A$ adding a dummy solution

$A' = A \cup \{ -2^k, 2^k + b\}$

If $X$ is a solution for the original problem, then  $X, Y= \{ -2^k, 2^k + b\}$ are two distinct solutions for $A'$ and target sum $b$. Now we can further expand $A'$ to $|A''|$ adding padding pairs of integers that do not affect the sums but can be used to "pad" $X$ and $Y$ up to $|X|+|Y|=|A''|$. We have
$|A'|=n+2$, so we add $n/2-1$ pairs $\{2^{k+i},-2^{k+i}\}$, $i=1..n/2-1$:

$A'' = \{a_1,...,a_n,-2^k, 2^k + b, 2^{k+1},-2^{k+1},...,2^{k+n/2-1},-2^{k+n/2-1}\}$, $|A''|=2n$

Using all the $n/2-1$ padding pairs we can build a set $Z$ such that $sum(Z)=0$ and $|Z|=2(n/2-1)=n-2$.

We can notice that using the dummy solution and the padding pairs we can build a set $Y'=Y \cup Z$, $sum(Y')=b$, $|Y'|=n$ (which is half the size of $A''$). So in order to get another different solution we  must use two or more of the $a_i$ plus some padding pairs.

In the figure a binary expansion of the elements of $A''$:

The above reduction works for any fixed $k$: just start with the (NP-complete) subset sum variant in which $k$ divides $n$ and $|X|\geq k$, then add $k-1$ dummy solutions (each dummy solution made with $k$ elements) and $(n/k-1)$ padding k-tuples.

If $k$ is part of the input (EkCSS), we have a simple generalization of the E2CSS problem and its NP-hardness follows immediately by the NP-completeness of E2CSS; the reduction is trivial: given an instance $A'',b$ of the E2CSS problem, just transform it to $A'',b,k=2$ which is a valid instance of the EkCSS problem. So EkCSS is NP-complete.

(Very informally) The EkCSS-diff should be NP-complete, too and the reduction from EkCSS is: "attach" to every $a_i$ a group of elements $T_i$ of size $m_i=(i+1)*n$:

$T_i= \{ a_i+1*2^u, 2*2^u,3*2^u,....,(m_i-1) 2^u,-2^u*\sum_{j=1}^{m_i-1} \}, |T_i|=(i+1)*n$

The first element of $T_i$ which replaces $a_i$, contains two detached "bit components" the original $a_i$ and $1*2^u$; but the only way to "clear" $1*2^u$ is to include the other elements of $T_i$ and the final one that is the only negative element (it "clears" all the previous $2^u$ components).

Every $T_i$ have distinct values for $u$ (and choosen in such a way that the sums don't interfere with each other and with the sum of the original $a_i$s).


Literature for Generalized Load Balancing

Appreciable literature is available in this standard book on Approximation Algo by Vazirani
http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf

Refer to chapter 10 for details.


Sampling a uniformly random satisfying assignment

Yes.

(backup links in case that one goes down: 1 2 3 4)

Back up reference, in case all those links go down: Bellare, Mihir, Oded Goldreich, and Erez Petrank. "Uniform generation of NP-witnesses using an NP-oracle." Information and Computation 163.2 (2000): 510-526.


Examples of Computer-Found Optimal Strategies in Games

The best known example is probably checkers (also known as draughts), which has been solved recently in 2007 (the game is a draw). Other examples are listed in the Wikipedia page on solved games; notable among them are connect four and nine men's morris. Additionally, several chess endgames have been solved.

This perhaps doesn't seem like an answer to your question, but if an expert (such as Marion Tinsley) loses to a computer program, then the computer must have found a "more optimal" move.


Conditional results implying difficulty of improving upper/lower bounds for permanent

An upper bound of $O(2^{n^{\epsilon}})$ may not be possible for any $\epsilon<1$ unless the Exponential Time Hypothesis (ETH) is false, see

Holger Dell, Thore Husfeldt, and Martin Wahlén.
Exponential time complexity of the permanent and the Tutte polynomial.
Full paper at ECCC TR10-78. http://eccc.hpi-web.de/report/2010/078/

That is, if your embedding of the $n\times n$ permanent into a determinant of size $O(2^{n^{\epsilon}})\times O(2^{n^{\epsilon}})$ is fast enough, you could

Transform a 3SAT-instance to a permanent as in the paper above

Transform the permanent to a determinant over the larger matrix

Compute the determinant to find the number of solutions to the
original 3SAT-instance.

The running time for an $n$-variate 3SAT instance would be $O(2^{n^{\epsilon'}})$ for some $\epsilon'<1$ depending on $\epsilon$ if step (2) is fast enough (say polynomial in n for each entry of the larger matrix). This would contradict the ETH.


NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

The paper [HP06] is in the spirit of your idea, although in a different direction, in the context of infinite words.
It can be adapted more easily to finite words.

In the powerset construction, we simultaneously keep track of all possible runs of the $n$-state automaton, by moving around $n$ tokens.  But we could decide to follow only $k<n$ runs, and do a partial powerset construction.
In general this will yield a non-deterministic automaton, that is not really more useful than the original one.

But it could be that building $k$ runs with a certain deterministic strategy is always enough to obtain an accepting one, if one exists. Think for instance of a big automaton where the only non-determinism is to guess whether the last letter is an $a$ or a $b$, and then branching towards two deterministic automata. Then two tokens suffice, and a $2$-powerset construction works, where subsets have size at most $2$, i.e. the resulting automaton has $\dfrac{n(n+1)}{2}$ states.

We can define the "width" of a non-deterministic automaton as the number of tokens needed to deterministically build an accepting run. The powerset construction actually assumes that we are in the worst case, i.e. width equal to number of states.
The case where the width is $1$ corresponds to the notion of good-for-games (GFG) automaton, introduced in [HP06], and further studied in [BKKS13,KS15].

We have that a NFA has width at most $k$ if and only if its $k$-powerset construction is GFG.
On finite words, it is in P to detect whether an automaton is GFG, and in this case it actually means that it is deterministic with some additional useless transitions.
This means we could increment $k$ until the resulting $k$-powerset construction is GFG, prune the useless transitions, and we get a deterministic automaton. This corresponds to emphasizing space-saving, since instead of building the big deterministic automaton and then minimizing it, we try to approach it "from below", hoping we won't have to do the full powerset construction.

[HP06]  Solving games without determinization, Henzinger, Piterman, in CSL 2006

[BKKS13]  Nondeterminism in the presence of a diverse or unknown future, Boker, Kuperberg, Kupferman, Skrzypczak, in ICALP 2013

[KS15]   On Determinisation of Good-for-Games Automata, Kuperberg, Skrzypczak, in ICALP 2015


Why is non-determinism (Push-down automata) necessary?

I'm not quite sure which flavour of "why" you are looking for. One reason for the increase in power when allowing nondeterminism can be seen in the following example:

Let $L$ be the set of palindromes $w\bar{w}$ over some alphabet (of at least two symbols), where $\bar{w}$ is the reverse of $w$. An NPDA for this language can just keep pushing symbols onto its stack, and then at some point guess that it has reached the middle of the input and gradually empty the stack. Note that the acceptance condition is purely existential - it is enough that there is a correct guess for the word to be accepted.

A deterministic PDA would have to choose the position it considers the middle in some way that only depends on the current prefix. Assume $A$ is such a DPDA. For any $k\in\mathbb{N}$, let $u_k=ab^{2k}a$; let $v_0$ be the empty word, and $v_{k+1} = v_ku_kv_k$. This is a sequence of palindromes, each a prefix of the next, so that $A$ must be in an accepting state $q_k$, with the stack empty, after reading $v_k$. By the pigeon hole principle, there must be some $k,l$ such that $k\neq l$ and $q_k=q_l$ (there is a finite number of states, and so some must be 'reused' as there are an infinite number of $k$s). But then $A$ cannot distinguish $v_ku_kv_k$, which is a palindrome, from $v_lu_kv_k$, which isn't.


It seems that the general problem of finding the optimal contraction order is NP-hard [1]. A recent paper on approximately optimizing the contraction order, and containing relevant references, is [2].
[1] Chi-Chung, Lam, P. Sadayappan, and Rephael Wenger. "On optimizing a class of multi-dimensional loops with reduction for parallel execution." Parallel Processing Letters 7.02 (1997): 157-168.
[2] Schindler, Frank, and Adam Jermyn. "Algorithms for tensor network contraction ordering." Machine Learning: Science and Technology (2020).


Well, we wrote a paper on it, so now it's definitely known:
https://arxiv.org/abs/2010.09886


Consequences of lower bounds for $\epsilon$-nets on approximation

If a range space has $\epsilon$-net of size $f(1/\epsilon)$, then the integrality gap of the fractional hitting set (or set cover) is $f(1/\epsilon)/(1/\epsilon)$. See the work by Philip Long (here [The Even etal. work is later than this work, and rediscover some of his stuff]). See also the slides 13-16 here.

In short, having non-linear $\epsilon$-nets, indicates that approximating the relevant hitting-set/set cover problem within  better than a constant factor is going to be very challenging.


Matrix multiplication in $O(n^2 \log n)$

I came across this paper about a year ago, but have not gotten around to reading it closely. I can tell you that the approach is not believed to be correct. On page 36 of the same paper, there is an attached comment by Don Knuth, who points out what looks to be a serious shortcoming of the approach.

To understand this paper, you will need to learn about group algebra and representation theory. It will be tough if you haven't seen that kind of material before.


Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?

A bit overkill, but:
this paper shows (among other nice things) that non-deterministic Hennie transducers realize exactly the class of non-deterministic MSO-definable transductions. The latter have regular domains.


"right" uniformity condition for Nick's Class

You can use $\mathsf{DLogTime}$ for uniformity of $\mathsf{NC}$ and $\mathsf{NC^2}$. There is no problem and the classes uniform $\mathsf{NC^k}$ remain the same and equal to $\mathsf{ATimeSpace}(O(\lg^k n),O(\lg n))$ (for $k\geq1$).

Generally, the only case that we need to be more careful is $\mathsf{NC^1}$ case where one should be careful about what needs to be in decidable in $\mathsf{DLogTime}$. If you use extended connection language description of circuits then everything works even in $\mathsf{NC^1}$ case.

For more on uniformity see:

Walter L. Ruzzo, "On Uniform Circuit Complexity", Journal of Computer and System Sciences, vol. 22 (1981), pp. 365–383.


Finding a path with certain properties in a directed graph

If all partitions contain only a single vertex and you're given all of them as your initial set of $k$ vertices then the path you seek must be a Hamiltonian path. So it's NP-complete.

However, it's fixed-parameter tractable when parametrized by $t$ — it can be turned into a reachability problem on a larger graph where each vertex is a pair $(S,v)$ of a set $S$ of the partition sets whose valid point has already been passed and a vertex $v$ of the original graph. So the time is $O(\binom{t}{\le k}(m+n))=O(2^t(m+n))$.


In the spirit of your comment about "pretty good but not necessarily optimal," I present the following idea with absolutely no guarantee of optimality!

For completeness, here is the pseudocode that you referred to (Remark: the algorithm linked assumes edge capacities are integers between 1 and C and that flow and residual capacity values are integral):

Scaling-Max-Flow(G, s, t, C) {
   foreach e ∈ E f(e) ← 0
   Δ ← smallest power of 2 greater than or equal to C
   G_f ← residual graph

   while (Δ ≥ 1) {
      G_f(Δ) ← Δ-residual graph
      while (there exists augmenting path P in G_f(Δ)) {
         f ← augment(f, C, P)
         update G_f(Δ)
      }
      Δ ← Δ / 2
   }
   return f
}

Observe that when $\epsilon$ = 1 ($\epsilon = \Delta$ in the psuedocode), you're just finding paths in shortest to longest order, and when $\epsilon$ is large, you're finding paths in (more or less) fattest to slimmest order. In fact, depending on the instance, the capacity-scaling algorithm finds paths in shortest to longest order within "buckets" of "enough flow."

Then, add another input parameter $0 \le \rho \le 1$ that represents how much you care about "fatness" vs "shortness." In order to ensure we're not massively affecting the runtime, we further require that $\rho$ is a rational number.

Then, each time $\epsilon$ is assigned a value, we additionally take the $\rho$-weighted arithmetic mean (I hope that's the correct term..) between 1 and its current value. That is,

$\epsilon \leftarrow (\rho)\epsilon + (1-\rho)$

For $\rho = 0$, we end up with a pure shortest path algorithm; for $\rho = 1$, we get a pure fattest path algorithm; and for $0 < \rho < 1$ we get something in between. In particular, for some middle value, $\epsilon$ will converge to $\le 1$ more quickly, so you'll get more shortest paths, and fewer fattest paths.


For which families of graphs is Generalized Geography in $P$?

Generalized Geography (GG) is PSPACE-complete even on planar directed bipartite graphs,
but, as reported in:

Hans L. Bodlaender, Complexity of path-forming games, Theoretical Computer Science, Volume 110, Issue 1, 15 March 1993, Pages 215-245

GG (and some other PSPACE-complete variants) are linear-time-solvable in graphs of bounded treewidth.

SIDE NOTE: one of the Generalized Geography variants that has recently been proved to be PSPACE-complete is Tron (Light Cycles game): given an undirected graph, two players pick two different starting vertices, and then take turns, by moving to an adjacent vertex from their respective previous one in each step. The game ends when both players cannot move anymore. The player who traversed more vertices wins (it was conjectured to be PSPACE-complete in 1990 by Bodlaender and Kloks).
Tillmann Miltzow, Tron, a combinatorial Game on abstract Graphs (2011)

Edit: I made a small program to test the game on small $n \times m$ rectangular solid grid graphs (undirected), and the result suggests that it is polynomial time solvable also for this class of graphs (assuming that the first node picked by player A is the top-left node):

               Width n
           1 2 3 4 5 6 7 8
         1 A B A B A B A B    Winning matrix up to 8x8
         2   B B B B B B B
         3     A B A B A B
Height m 4       B B B B B
         5         A B A B
         6           B B B
         7             A B
         8               B

Curiously, the same matrix is obtained if player A can choose an arbitrary starting node.

As said in the comments, I think that the complexity of deciding if there is a winning strategy when GG is played on solid grid graphs (with arbitrary shapes, but without holes) is not known and probably it is not so easy to prove something about it (indeed the - somewhat related - problem of deciding if a solid grid graph has an Hamiltonian path is still open, though deciding if a solid grid graph has an Hamiltonian cycle is polynomial time solvable).

A final trivial note: GG is polynomial time solvable also in complete graphs.


Dimensionality reduction in machine learning

Information Geometry is a rigorous framework which combines statistical inference, information theory and differential geometry.

Several open problems in statistics (and geometry) have found a new formulation and solution.
Specificaly the concept of dual connections and dualy-flat spaces. It has been shown that various statistical inference methods (e.g maximum likelihood, EM algorithm etc.) can be formulated in terms of dualy-flat spaces in a statistical manifold (reference "Methods of Information Geometry", Amari, Nagaoka). The new formulation allows a unified view of previously un-related methods and algorithms.

The problem of dimensionality reduction and PCA has been formulated information-geometricaly as follows (with emphasis on information):

"Information-Geometric Dimensionality Reduction"
"An Information Geometric Framework for Dimensionality Reduction"
"The e-PCA and m-PCA: Dimension Reduction of Parameters by Information Geometry"


As the OP pointed out in an update above, the second question about computing $\Delta_{|V|}$ is answered in this question.

The first question is about computing the parity of the number of vertex covers. This problem is $\bigoplus$P-hard even for planar 3-regular graphs.  See Section 4.1 of this paper (particularly Corollary 4.2).

First, the notation for the corresponding Holant problem is Pl-$\bigoplus$Holant$([0,1,1]|[1,0,0,1])$.  Since there is a 1-to-1 correspondence between vertex covers and independent sets, sometimes people also refer to the Holant expression for independent set (in this case, $\bigoplus$Holant$([1,1,0]|[1,0,0,1])$) as though it were the vertex cover problem.

Second, I don't know why they called this problem $\bigoplus$3/2-Bip-VC (that is, why "3/2-Bip").  As I said above, this Holant expression is for the counting of vertex covers (equivalently, independent sets) in 3-regular graphs.


NP is ofter characterized as a proof system in which the prover sends a polynomial-length proof to a deterministic polynomial-time verifier, and after which there is no interaction. The class of recursively enumerable languages can be characterized similarly by replacing "polynomial" with "finite".

Also, since the class of recursive languages R is the intersection of RE and coRE, you can characterize R as a proof system in which an all-mighty prover can convince a finite time verifier both in the validity of correct claims and in the invalidity of false claims.

The class EXP has a characterization in terms of a proof system with "competing provers" - i.e., a proof system in which there is a prover that tries to convince the verifier that the claim is true and a refuter that tries to convince the verifier that the claim is false. See the paper "Making games short" of Feige and Kilian for more details.


Concurrent algorithm for strongly connected components (SCCs)

This answer might come late, but there's a work by Gavin Lowe: "Concurrent Depth-First Search Algorithms", Proceedings of TACAS 2014, p. 202--216, Volume 8413 of LNCS, Springer that has descriptions for parallel algorithms for computing strongly connected components, lasso-shaped paths and finding nodes that are part of a cycle.


Balls & Bins: A punishment and reward game

Here's an argument that it's polynomial for $k=2$.

If $k=2$, each bin can only be connected to two other bins, and thus the graph falls into paths and cycles. We can thus just worry about a cycle. In fact, we can guess which bin is capped first. Since there are only a polynomial number of guesses, we can try all of them, and reduce the problem to the case where the graph is a path.

Now, whether a bin can be capped only depends on whether or not you've capped its neighbors. That is, for bin $1$, we have one of the following constraints:

bin $1$ can be capped only before you've capped bin $2$,
bin $1$ can be capped only after you've capped bin $2$,
bin $1$ can be capped any time,
bin $1$ can never be capped.

For case 1, you might as well cap bin $1$ as the first thing you do. Now, you have a path of length $n-1$, and you can use recursion.

For case 2, you might as well cap bin $1$ as the last thing you do. Now, you have a path of length $n-1$, and you can use recursion.

For case 3, capping bin $1$ will either add or subtract balls from bin $2$. If it adds them, make it the first bin you cap. If it subtracts them, make it the last bin you cap. In either case, you've reduced the problem to a path of length $n-1$.

For case 4, you've solved the problem: it's impossible to win.

This gives an algorithm of time $O(n^2)$. For a cycle of length $n$, we need to test $n$ different paths, breaking the cycle in every possible place. And for a path of length $n'$, in constant time, we can convert the problem to the same problem on a path of length $n'-1$.


Practical applications of the Theory of Equality with Uninterpreted Functions (EUF)

Most automatic theorem provers handle EUF in some form. In particular, provers based on the Nelson-Oppen architecture do so. For big systems, however, EUF is usually not enough. One needs specialized decision procedures for arithmetic, arrays, bit vectors, and so on to get better performance. Take a look at SMT solvers. If you follow the links to solvers and where they are used you'll find many applications to real world problems. For example, Z3 is used in VCC, which in turn is used to fully verify Microsoft's (baby) hardware simulator Hyper-V.


I think the best way is to make a recursive algorithm. You could divide your input in half (approx), and keep out the central element. Then you recursively build a tree with the left subarray which will be the left child of the central element, and equivalently the tree resulting from the right subarray will be the right child.

By induction you can prove that the resulting tree is balanced since you are building trees of the same size at each side (+/- 1 node). Also is easy to prove that the result is a binary search tree, by construction.

With respect to the complexity, every node in the recursive execution tree takes constant time. Since you have a number of nodes proportional to the number of elements in your input, then the algorithm is O(n).


Is the feasible region of this SDP polyhedral?

No, even if there is a finite number of feasible rank-1 matrices, the feasible region of an SDP does not have to be polyhedral.

A spectrahedron you see all the time in applications is $S_n = \{X: X \succeq 0, X_{11} = \ldots = X_{nn} = 1\}$, i.e. the set of Gram matrices of $n$ unit vectors. This is, for example, the feasible region for the Goemans-Williamson SDP relaxation for MaxCut. There can be no more than $2^n$ rank-1 matrices in $S_n$, because $xx^T \in S_n$ implies $x_i^2 = 1$ for all $i$, and therefore $x \in \{-1, 1\}^n$.

Now let's look at $S_3$. Write

$$
X = \left(
\begin{array}{ccc}
1 & x & y\\
x & 1 & z\\
y & z & 1
\end{array}
\right)
$$

By Sylvester's criterion, $X \succeq 0$ if and only if all principal minors are non-negative. This gives the following inequalities:
$$
\begin{align}
 x^2, y^2, z^2 &\leq 1\\
x^2 + y^2 + z^2 &\leq 1 + 2xyz
\end{align}
$$
The first three inequalities come from writing the 2-by-2 minors, and the last comes from writing the determinant of $X$.

It's now easy to see this set is not polyhedral. For example, let the set $T$ be the projection of $S_3$ onto the free variables $x, y, z$, and consider $U = T \cap \{(x, y, z): z = 0\}$. Polyhedral sets remain polyhedral after orthogonal projection and intersection with halfspaces, so if $S_3$ is polyhedral, then $U$ is as well. But $U = \{(x, y, 0): x^2 + y^2 \leq 1\}$ is a disc.

In fact there is also a direct geometric argument that $U$ is a disc. If $X$ is the Gram matrix of the vectors $u, v, w$, then setting $z = 0$ means $v \perp w$, and $(x, y)$ are the coordinates of the projection of $u$ onto the plane spanned by $v$ and $w$, expressed in the orthonormal basis given by $v$ and $w$. Since $u$ can be any unit vector, $(x,y)$ can be any vector of length at most $1$.

For illustration, here is the set $T$:

And here you can see that $U$ is a disc:


Computing input length on a one-tape Turing machine

It cannot be computed in time $o(n\lg n)$.

Let $M$ be a machine which
given an input string $x$
halts with the size of $x$
written in binary on the tape.

We can add a simple (zero-space linear-time) DFA to $M$
to check if the size of the input is a power of two:
just check that the first bit is 1 and the rest is zero.

Let's assume that $M$ runs time $o(n \lg n)$.
Then we can decide in time $o(n \lg n)$ that
the size of input is a power of two.
In other words, the following language is
decidable in $\mathsf{DTime}(n \lg n)$.
$$L = \{ 0^i \mid \exists k \ i = 2^k\}$$
It follows from $\mathsf{DTime}(o(n \lg n)) = \mathsf{Reg}$
that $L$ should be regular.
But it is easy to check that the language is not regular.
So $M$ cannot run in time $o(n \lg n)$.


Consider this variation: we want to find number of paths which goes from $(1,1)->(n-2,n)$ in $(n-2)\times n$ solid grid, this can be done in almost $2^{n(n-2)}$ possible ways. Then is simple to convert it to your case. Just go up one step, then go left $n$ steps, again up one step and then right $n$ steps. That path covers all of that $k$ edges, and these are just restricted versions, that means independent to $k$, the upperbound is big : $2^{O(n^2)}$.


Unique games conjecture - edge permutations

These permutations represent the constraints on the labeling. for each edge, there is some set of labellings for the edge's vertices which is legal. Since we are talking about unique games, these legal labellings are limited in the following way: if (u,v) is an edge, then for any possible labeling of u, there exist a single legal labeling of v. This means that we can represent the legal labellings of any edge's vertices by a permutation $\phi :[k] \to [k]$ where $[k]$ is the set of labels.


Is there research on algorithmic design patterns?

There are many general techniques and meta-theorems. Unlike software engineering, in TCS we don't want to repeat things similar to what the others did, we want to create something new or solve an unsolved problem, so it's not as easy as using lazy propagation in software development. Here I provide some examples but it's surely way far from the complete list.

Parametrised complexity: kernelization, iterative compression, bidimentionality, ...
Approximation algorithms: randomised rounding, scaling, ...
In graph theory, based on structural hierarchies of graphs like bounded tree width graphs/excluded minor graphs/ bounded expansion graphs / nowhere dens graphs, there are different tools (like decompositions) and meta theorems (like Courcelle theorem).


I worked on a very similar problem on my Masters thesis, in which I studied the non-Markovian dynamics of a driven qubit in a dissipative environment. My interest was in checking that the master equation I obtained was completely positive, but this is just one side of your problem. The question turned out to be very non-trivial if no RWA is made, but I was able to get some results using Ref. [J Mod. Opt. 54, 1695 (2007)] and exploiting the fact that the qubit is weakly coupled to the environment. I'll beat my drum and also give the Ref. to an article where I present some of these results, [P. Haikka and S. Maniscalco, Phys. Rev. A 81, 052103 (2010)], you may find it useful.


There's a very recent survey paper available on Alias Analysis for Object-Oriented Programs.

It will be published in April in the LNCS state-of-the-art volume (gratuitous advertising alert): Aliasing in Object-Oriented Programming:
Types, Analysis and Verification. Lecture Notes in Computer Science, Vol. 7850. Dave Clarke, Tobias Wrigstad, James Noble (Eds.)


Looks like the best bound known (for multitape Turing machines) is logarithmic.

Suppose $\delta\log n$ bits of binary worktape is enough to decide whether any $n$-bit CNF formula is satisfiable, for all large enough $n$.
By the standard simulation, a TM with $q$ states that uses at most $s$ bits of space can be simulated by a TM that has at most $qns2^s = 2^{s+\log n + \log s + \log q}$ different configurations.
Whenever the machine accepts, there is a sequence of (nondeterministic) moves reaching an accepting state that is at most as long as this number of configurations.
When $s = \Omega(\log n)$, this is at most $2^{s(2+o(1))}$ (note that $q$ remains the same for all input lengths $n$).
On a separate counter tape, $M$ can first write this quantity in unary, then at each step of the simulation erase one of the symbols of the counter, and terminate the computation if it ever runs out of counter symbols.
This creates a constant factor of overhead (something like 3), which is absorbed by the $o(1)$ term in the exponent.
Hence $2^{s(2+o(1))}$ steps are sufficient.

By assumption $s \le \delta\log n$, so the time-space product is at most $\delta\log n2^{\delta\log n(2+o(1))} = n^{\delta(2+o(1))}$.

Rahul Santhanam showed in 2001 (see doi:10.1016/S0020-0190(00)00227-1) that the space-time product for a Turing machine deciding SAT must be at least $\Omega(n^{2-o(1)})$; his argument applies also to nondeterministic machines.
Hence $\delta \ge 1$, and at least $\log n$ bits of binary worktape are needed.

More generally, additional worktapes and a larger worktape alphabet change the exponent by a constant factor.  This ultimately reduces the factor $\delta$, but the space lower bound is still $\Omega(\log n)$.


Bisecting a set of points into two optimal subsets

If you insist on precise partition, then you need to compute all the balanced partitions of a set of points in the plane by a line (the optimal partition is a Voronoi partition, so the two point sets are separated by a line). Such partitions are known as $k$-sets. The fastest algorithm currently known for this work in $O(n^{4/3} \log n)$ for computing these partitions in the dual [i.e., the $k$-level of a set of $n$ lines, for $k=n/2$]. Once you have all the possible partitions, you just need to check each one of them. Using standard tricks, this can be done in constant time for each partition.

(Update: Proving that the optimal partition is realized by a $k$-set, for $k=n/2$, is not completely trivial. I would leave it as a cute exercise for the interested reader. Hint: Consider the line passing through the two optimal centers, and the direction perpendicular to it.)

If you do not care about the exact solution, then an easier approach would be to use a coreset for $k$-means clustering. This would result in $O( \epsilon^{-2} \log n)$ weighted points in this case, with total weight $n$. Then, you just need to solve the problem on the weighted point-set. The easiest solution would be to generate then a set of candidate locations for centers, and trying all pairs on the weighted points. The coreset construction, and generating the candidate centers is described in this paper:

http://sarielhp.org/p/03/kcoreset/


I'll try to show this, hope I interpreted the question correctly.

Let $A_k=\{0,1\}^k.$ If $f(n)\leq n+\log n$ for $n$ large enough this implies $$\max\{\ell(c(x)):x \in A_1 \cup A_2\cup \ldots \cup A_k \}\leq k+ \log k,$$ for $k\geq N$, for some finite $N$, where $\ell(c(x))$ is the length of the codeword $c(x)$ assigned to $x.$ So this means that
$$
\sum_{N\leq k ~~} \sum_{x \in A_1\cup A_2 \cup \ldots \cup A_k} 2^{-\ell(c(x))}\geq \sum_{N \leq k~~} \sum_{x \in A_1\cup A_2 \cup \ldots \cup A_k} 2^{-(k+\log k)}
$$
which is equal to
$$
\sum_{N\leq k} |A_1 \cup A_2 \cup \ldots \cup A_k|~ 2^{-(k+\log k)}=
\sum_{N\leq k} (2^{k+1}-1)~ 2^{-(k+\log k)}
$$
which is equal to
$$
\sum_{N\leq k} 2^{1-\log k} - 2^{-(k+\log k)}=2 \sum_{N\leq k} \frac{1}{k} - \sum_{N\leq k}\frac{2^{-k}}{k}=2 \left(\sum_{N\leq k} \frac{1}{k}\right) -\ln 2
$$
which is unbounded, since the harmonic series diverges.


How intrinsic is the $d^d$ term in the running time for constructing $\varepsilon$-nets in range spaces of VC-dimension d?

If you are ok with a randomized algorithm, then you can just randomly sample $O((d/\epsilon) \log (d/\epsilon \delta))$ points, and this will be an $\epsilon$-net with probability at least $1-\delta$.

For the deterministic algorithm, I believe the $d^{O(d)}$ term comes from the following reason.  You first partition your full set into subsets of size about $s = O((d/\epsilon) \log (d/\epsilon))$ where $s$ is the size of the $\epsilon$-net you hope to get in the end.  Then you merge two such subsets and reduce to half that size.  (Basically, this is repeated until one set is left.)  The reduction step essentially considers all interesting ranges of the merged set of size $2s$.  By VC-bounds there are about $O((2s)^d)$ ranges, and you need to "check" each of these to see if it has been hit.  The $s^d$ has a $d^{O(d)}$ in it.  The $d$ in the $s$ term is needed.  So to reduce this bound, using this deterministic framework, you would somehow need to implicitly "check" all ranges without explicitly enumerating them.   This seems difficult to do deterministically, but I am not sure I know an explicit lower bound - most work in this arena assumes $d$ is constant and abuses this heavily.


In the adjacency matrix model, there is a lower bound of $\Omega(n)$ on the query complexity of testing whether an $n$ vertex graph consists of two isomorphic copies of some $n/2$-vertex graph (see Introduction to testing graph properties - Goldreich for a survey).

Also, there are many lower bounds that depend on $n$ for testers with one-sided error, e.g.: testing $\rho$-Clique,$\rho$-Cut, and $\rho$-Bisection (see Property testing and its connection to learning and approximation - Goldreich, Goldwasser, Ron)

Moreover, in the bounded degree graph model, testing 3-Colorability requires $\Omega(n)$ queries, whereas testing 2-Colorability (i.e., Bipartiteness) requires $\Omega(\sqrt n)$ (see Property testing in bounded degree graphs - Goldreich, Ron).


Number of minimal DFAs of size at most $m$?

According to Ishigami Y., Tani S. (1993) The VC-dimension of finite automata with $n$ states,
http://link.springer.com/chapter/10.1007/3-540-57370-4_58
,
the VC-dimension of the concept class of $n$-state DFAs over an alphabet of size $k$ is
$$ d=d(n,k) := (k-1+o(1))n\log_2 n.$$
It follows that there are at least $2^d$ distinct $n$-state automata on a $k$-letter alphabet. The upper bound on the number such automata follows from a simple counting argument (given in the paper), and is at most $2^d$.


Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

For one, proving $BPP \subseteq NP$ would easily imply that $NEXP \neq BPP$, which already means that your proof can't relativize.

But let's look at something even weaker: $coRP \subseteq NTIME[2^{n^{o(1)}}]$. If that is true, then polynomial identity testing for arithmetic circuits is in nondeterministic subexponential time. By Impagliazzo-Kabanets'04, such an algorithm implies circuit lower bounds: either the Permanent does not have poly-size arithmetic circuits, or $NEXP \not\subset P/poly$.

I personally don't know why it looks "out of reach" but it does seem hard to prove. Certainly some genuinely new tricks will be needed to prove it.


I don't consider this an answer. I'm abusing the answer box to pretty print a comment.
There is a strict sense in which Euclid's GCD algorithm, Gaussian elimination, Buchberger's algorithm and Knuth-Bendix form a strict sequence of generalisations and are all instances of what is called a completion algorithm. There is also a close relationship between these algorithms and resolution in logic. I do not know a good reference for this but I have seen the fact mentioned very often. These might help.

History and basic features of the critical-pair/completion procedure, Bruno Buchberger, 1987
Canonical Reduction Systems in Symbolic Mathematics, Franz Winkler. Springer Link

Let me know if you find better references.


Is it possible to MAC a quantum state with a classical key under reasonable assumption?

Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, Alain Tapp. "Authentication of Quantum Messages", FOCS 2002.

http://www.cse.psu.edu/~ads22/pubs/PS-CSAIL/BCGST02-focs-final.pdf

As with encryption, there is a protocol that requires no computational assumptions. It uses a key of length about 2n+2k to authenticate n qubits with security level 2^{-k}.


Probabilistic (randomized) algorithms before "modern" computer science appeared

This is discussed a bit in my paper with H. C. Williams, "Factoring Integers before Computers"

In a 1917 paper, H. C. Pocklington discussed an algorithm for finding sqrt(a), modulo p, which depended on choosing elements at random to get a nonresidue of a certain form.  In it, he said, "We have to do this [find the nonresidue] by trial, using the Law of Quadratic Reciprocity, which is a defect in the method.  But as for each value of u half the values of t are suitable, there should be no difficulty in finding one."

So this is one of the first explicit mentions of a randomized algorithm.


Isolation in Turing-complete reversible cellular automata

The conjecture is not only false, but false for standard and seemingly-minimal models of reversible CA. Specifically, in Margolus' billiard ball model (with the Margolus neighborhood), suitably aligned large blocks of live cells act as barriers and mirrors, isolating anything beyond them.


Statistical query model with Gaussian noise?

We know something close to what you want.

If you look at Ke Yang's "Honest Statistical Queries" -- there is no noise at all, but only "sampling error".   In this model, you pass in a parameter $t$, and the Oracle takes $t$ samples, honestly evaluates the passed-in function (onto {0,1}), and returns the average value of the function on the samples.

In effect, this estimates the expected value of the function.  It is easy to see that this Oracle samples from the Binomial distribution $B(t, E_{x \sim D}(f(x))$.  For small skew and large $t$, this is approximated by the Normal.  We extended this to explicitly consider variance here.

The punchline, basically, is that SQ lower bounds still hold in this non-adversarial noise setting.  Actually the SQ lower bounds are even harsher because they work for sample sizes $t=1$, where the algorithm sees the result of its function evaluation on every random sample (and can average or do anything by itself).


Extended version of the paper "Consistent Hashing and Random Trees" with proofs

Answering my own question.

I found that the authors never published an extended version with proofs.

The closest thing to an extended paper is,

  Rina Panigrahy. Relieving hot spots on the worldwide web. 1997. 1

which was the Master's thesis of Rina Panigrahy (under Prof. Karger & Prof. Smith), who's also a co-author of the paper under discussion.  It is a good, detailed reference to the original paper with all the proofs I needed.


Problems that are decidable but cannot be verified in polynomial time

The most important thing to realize from a theoretical standpoint is that NP is actually a relatively small class of all decidable languages. That said, many of the interesting problems in computer science lie within NP so they get a lot of attention.

It's conjectured that $NP \subsetneq PH \subsetneq PSPACE \subsetneq EXP \subsetneq NEXP$.

The classes PH, PSPACE, and EXP contain many of the "interesting" problems in $R \setminus NP$, which is what I assume you're asking about in this question. So far NEXP has gotten all of the attention because $NP \subsetneq NEXP$ is the only proper containment that we can prove (by the nondeterministic time hierarchy theorem, as I mentioned above).

Here are some interesting concrete examples of problems in some of these other classes:

Determining if a player has a winning strategy in chess or Go (adapted to n x n boards) is EXP-complete.
MAJ-SAT, the problem of determining whether over half of the assignments to the variables in a boolean formula satisfy that formula, is in PSPACE. It is also complete for the smaller class PP.
EXACT-CLIQUE, the problem of determining whether the largest clique in a graph is of size exactly k, is in $\Sigma_2^P$, part of the second level of the polynomial hierarchy.


Research papers regarding disinterval analysis

You could give a shot at Ermedahl & Sjodin: Interval analysis of C-variables using Abstract Interpretation.


Is there a book/survey-paper outlining language class hierarchies, closure properties, etc

Not standard topics, no. And sorry, I have no general overview.

However, I would have a look at the PhD thesis of Klaus Reinhardt for at least a picture of the various families that live in this area. See page 64 for a diagram of the zoo. Motivated by Petri Nets with inhibitor arcs Reinhardt studies priority multicounters with restrictions on when to do zero tests. Non-trivial.

By the way, your last example question was discussed in this forum by user Sam Jones. Another Ibarra reference.


What's the meaning of "input size" for 3-SAT?

In complexity theory, $n$ is the length in bits of the input the algorithm has been given.

In particular, it is not the "number of bits required to represent the input" because that would be very hard to reason about — you'd have to prove that you'd chosen the most efficient possible coding.  If my input to 3-SAT is the formula consisting of 276 repetitions of the clause $X\vee \neg Y \vee \neg Z$, then $n$ is however many bits it took me to express that input; it is not, for example, the number of bits it would have taken me to express the equivalent formula that has just one copy of the clause.

Now, in practical terms, complexity is often expressed in terms of other measures.  For example, the running time of algorithms in graph theory is often given as a function of the number of vertices and/or edges; in satisfiability, the number of variables and/or clauses is often used.  In terms of describing algorithms, it's often more intuitive to give the bounds that way: it's a higher-level view of a graph as a set of vertices and edges, rather than the "machine-code" view of representing that as a string of bits.  In terms of complexity theory, we're often only interested in broad questions like, "Is there a polynomial-time algorithm?" or "Does it need exponential time?"  Because these questions are insensitive to polynomial factors, $n$ is sometimes used to mean other things.  For example, in 3-SAT, a formula in $N$ variables can be coded using $n=4N^3$ bits (see below).  Anything that's polynomial in $n$ is polynomial in $N$ and vice-versa so, for that kind of question, it doesn't really matter which you use.

Here's how to code a 3-CNF formula with $N$ variables in $4N^3$ bits.  Every clause has either 0, 1, 2 or 3 negations; we may permute so that the negated literals appear first in any clause. Now, fix an enumeration (say, lexicographic) of all the $N^3$ possible 3-tuples of variables. For each kind of clause (0, 1, 2 or 3 negations), make a list of $N^3$ bits such that the $i$th bit is 1 if, and only if, the $i$th 3-tuple is a clause with that number of negations. The input is those four lists.  The first thing any algorithm using this input format would do is check that its input length is $4N^3$ for some $N$.  If it isn't, the input doesn't code anything, so it doesn't code a satisfiable formula, so the algorithm rejects.

Note that even the above coding still has some redundancy, since the clause $X\vee Y \vee Z$ appears in six permutations.  If $n$ were the minimum number of bits required to code the input, we'd be forced to use a coding that avoided that redundancy. Worse, if we were reasoning about 3-SAT over random inputs selected from some distribution, the minimum number of bits required to express some input would involve something like Huffman coding the inputs according to that distribution, and it would be a total nightmare. So it's just the length of the input you were given.


Matching on bipartite graph - multiple edges

According to the comments above, the problem can be reduced to a weighted bipartite matching / assignment problem.

If $f(p)$ specifies the limit of matches for a node in $P$, we replace each $p$ by $f(p)$ nodes.
To assure $|S| = |P|$ we can add dummy nodes to $S$.

Now we can solve the problem by a standard algorithm. E.g. Hungarian Method.


The complexity of finding a Borsuk-Ulam point

Papadimitriou showed that a version of this problem is PPAD-complete in the paper introducing that class, "On the complexity of the parity argument and other inefficient proofs of existence".

His formulation of the problem is:

  Borsuk-Ulam. Given an integer n and a Turing machine computing for each
  point $P=(x_1,\dots,x_d)$ with $-n\leq x_i\leq n$ and $\max_{|x_i|}=n$ (the surface of the $L_1$ sphere), a function $f(p)$ with $f(p) \leq \frac{1}{Kn}$. Find an $x$ with $|f(x) - f( - x)| \leq \frac{1}{n^2}$.

(Sidenote -- many times when you see a fixed-point type of theorem, PPAD is a good guess for the complexity of finding it...)


What arithmetical theorems can plain $\lambda \Pi$ reason about?

As Andrej notes, $\lambda\Pi$ is a conservative extension of first-order logic which means:

  Adding the axioms of PA to $\lambda\Pi$ gives exactly the same arithmetic theorems as PA.

However, because of the more expressive system, it is possible to finitely axiomatize induction using the following (encoding of) this axiom:

$$ \forall P: {\mathbb N}\rightarrow \mathrm{Type}, P\ 0 \rightarrow (\forall n, P\ n \rightarrow P\ (S\ n))\rightarrow \forall n, P\ n$$

Note that you need a single Martin-Löf universe to be able to state this. Adding equality and the other PA axioms (definitions for $+$, $\times$, injectivity of $S$) in a similar manner, one might ask if this axiomatization is conservative over PA, or rather HA, since we don't necessarily want the Excluded Middle.

The answer is yes, though this is quite a non-trivial thing! The proof involves some somewhat deep ideas from the field of realizability.

Finally, though this is a fine axiomatic system, it may be frustrating to note that $+$ and $\times$ (and equality, I guess) do not have the computational behavior one might expect in a dependently typed theory, as one would in a system like Coq or Agda.

This is where Martin-Löf's inductive families comes in: one can give a computational content to the induction axiom, which allows one to define addition and multiplication, as well as prove injectivity of $S$ if enough power is given to the type-level computation rules (this point is probably a story for another time).

And finally one can even define existential quantifiers and equality itself using these families, which is a quite remarkable observation from the theory of inductive families.

Note that Twelf seems to frown upon these last 2 steps, preferring to keep $\beta$ equality alone in its computation, and having predicates for everything else. They have their reasons, I guess.


Minimal number of hyperplanes needed to separate sets of points from one other set

Your problem is NP-complete, even in the following two highly restricted cases:

The dimension $d$ is part of the input, and the question is whether you can separate set $B$ from set $G$ by $k=2$ hyperplanes.
The dimension is $d=2$ (and the number $k$ of separating hyperplanes is part of the input).

This has been proved in:

  Nimrod Megiddo
  On the Complexity of Polyhedral Separability
  Discrete and Computational Geometry 3, pp 325-337, (1988).


Solving a system of sums-of-powers polynomials

I think your question is closely related to the set reconciliation problem, which is solved in this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.5338

The problem of set reconciliation is to given two sets $A, B \subseteq [n]$ find $A \backslash B$ and $B \backslash A$ with as less communication as possible. If $B = [n]$, then you just need to find $\bar A$. Authors provide an algorithm with $O(k \log n)$ communication complexity.

Basic idea of the algorithm is to find small prime number $p$ greater than $4n$ and compute next two polynomials $\chi_A(x) = \prod_{a\in A} (x - a)$ and $\chi_B(x) = \prod_{b \in B} (x - b)$ in $\mathbb{F}_p$ on $2 \cdot k$ different points.

It can be easily shown that $$\frac{\chi_A}{\chi_B} = \frac{\chi_{A \cap B} \cdot \chi_{A \backslash B}}{\chi_{A \cap B} \cdot \chi_{B \backslash A}} = \frac{ \chi_{A \backslash B}}{ \chi_{B \backslash A}}.$$

If you compute these polynomials in non-zero points (for example, greater than $n$), then you obtain $2 \cdot k$ equations of the form
$$
\chi_{A \backslash B}(x_i) \cdot b_i = \chi_{B \backslash A} \cdot a_i,
$$
where $a_i$ and $b_i$ are corresponding values of $\chi_A$ and $\chi_B$ at $x_i$.

System of $2k$ equations with $2k$ variables over field $\mathbb{F}_p$ can be easily solved. The last thing is to factorize polynomials. The authors provide easy algorithm for this case.

Turning back to your first question $\chi_{\bar S}(x)$ can be expressed with your $s_i$'s for $i$ from $0$ to $k$.


Belief propagation for approximate real 3LIN?

In coding theory, Belief Propagation is heavily used as a good heuristic for decoding (either explicit or randomly generated) LDPC codes in various settings (e.g., for the erasure channel, you want to satisfy all constraints more quickly than Gaussian elimination. For noisy channels, you want to find the "best fit", etc). I think techniques used there are directly relevant to your question. You may want to have a look at the book "Modern Coding Theory" by Urbanke and Richardson for an extensive discussion.