theorems for universal set of quantum gates for SU(d)

I'm not aware of any proof that the Clifford group + any non-Clifford element gives a universal set of quantum gates. The closest related result that I know is that the Clifford group + any non-Clifford element densely generates an infinite group. (This is theorem 6.5 of Nebe et al. http://arxiv.org/abs/math/0001038v2). But this falls short of proving that the Clifford group + any non-Clifford element is universal, because it is possible you could densely generate a continuous group on $n$ qubits that is not all of $U(2^n)$. So I believe that proving this result remains open.
Note that in the case of the Clifford group on qubits, one can easily show that the Clifford group + any non-Clifford one-qubit gate is universal, using the representation theory of $SU(2)$. But the more general statement about adding arbitrary elements to the Clifford group is open.

Update: The answer to the first problem is known. In particular, the statement that the Clifford group + any non-Clifford element yields a universal gate set follows from two theorems of Nebe, Rains and Sloane. First, Theorem 6.5 of Nebe et al (http://arxiv.org/abs/math/0001038v2) shows that adding any element to the Clifford group renders it infinite. Second, Corollary 6.8.2 of Nebe et al. (Self-Dual Codes and Invariant Theory (Springer 2006)) states that any infinite group which contains the Clifford group contains all of $SU(d^n)$. Combining these shows that the Clifford group + any non-Clifford element is universal, in any local dimension $d$ (prime or composite). This was previously discussed on stackexchange here: Universal sets of gates for SU(3)?

With regards to rotations by irrational multiples of pi: it's not necessary for your gate set to contain a rotation by an irrational multiple of pi to be universal - for example the gate set $CNOT, H,T$ is universal where $T$ is a Z-rotation by $\pi/8$. All that's required for universality is that the gate set densely generates all rotations. A priori it's possible that even as you take longer and longer products of your gate elements, all the resulting rotations are by rational multiples of pi, but the gate is still universal as the rational rotations are dense in the reals.  So I don't believe one can argue that "the gate added to the Clifford group must generate an irrational rotation to be universal". We only know that "the gate added to the Clifford group must densely generate and irrational rotation to be universal".


Implicit Non-deterministic Buchi determinization

If I understand your model correctly, then it's enough for you that all runs either get stuck in accepting states, or get stuck in non-accepting states.
If this is the case, you can also use deterministic weak Buchi automata, which are more expressive than $satefy\cup co-safety$.


Graph isomorphism problem with invertible adjacency matrices

Isn't this graph just a collection of cycles? So we only need to compare that all the lengths in the two graphs match (which can be done by sorting the lengths).


Compendium of the Best Approximation and Hardness Results for NP optimization problems

When you refer to the Crescenzi-Kann compendium, I'm not sure if you're referring to the book or the website.  The book is out of date but the authors try to keep the website continuously updated.  It would seem that the logical starting point is to approach Crescenzi and Kann with your proposal.


In 2007, Princeton professor Arvind  Narayanan created the TOC Blog Aggregator.

In 2018, CSTheory.se Moderator Suresh Venkatasubramanian  (@SureshVenkat) stepped down from moderating here, but took over the aggregator:

  Apologies for the downtime this week. This is @random_walker handing over the aggregator code (and this Twitter account) to @geomblog. Thanks everyone for following and special thanks to @geomblog for taking things over.— TCS blog aggregator (@cstheory) November 23, 2018


Powerful Algorithms too complex to implement

Chazelle gave a linear time algorithm for triangulating a simple polygon. Skiena wrote (p.575, Algorithm Design Manual) that it's "sufficiently hopeless to implement that it qualifies more as an existence proof"


The textbook reduction from SAT to 3SAT, due to Karp, transforms an arbitrary boolean formula $\Phi$ into an “equivalent” CNF boolean formula $\Phi'$ of polynomial size, such that $\Phi$ is satisfiable if and only if $\Phi'$ is satisfiable.  (Strictly speaking, these two formulas are not equivalent, because $\Phi'$ has additional variables, but the value of $\Phi'$ doesn't actually depend on those new variables.)

No similar reduction from arbitrary boolean formulas into DNF formulas is known; all known transformations increase the size of the formula exponentially.  Moreover, unless P=NP, no such reduction is possible!


Does a non-constructive proof of bounds of a computable asymptotic complexity, with impossible fix, exist?

No (assuming $f$ is computable).  By $ω$-consistency, the $O(f(n))$ bound is correct, so some $c f(n)$ bound is correct, and we can add $c f(n)$ bound (which is $Π^0_1$) as an axiom to a constructive theory.


Areas of research and open problems in functional programming

The computational implications of homotopy type theory & higher type theory.

Homotopy type theory was invented and developed by a group of computer scientists and mathematicians as a new foundation of mathematics, and as a language to formalize math in, specifically with a view towards algebraic topology (& related fields). However, not much research is done in the computational content of homotopy type theory, i.e. HoTT/HTT as a functional programming language.

Can HoTT be a basis for a practical programming language? What kind of programs do HoTT/HTT enable us to write more easily? What constructs can we add to HoTT/HTT to facilitate programming? There is some research going on in this area, but definitely not enough.

In 2014, Cockx et al. developed a way to do dependent pattern matching without using Axiom K, which is inconsistent with univalence. Later, Sozeau added HoTT support to Equations, the dependent pattern matching plugin for Coq. This is an example of work done on HoTT as a programming language, i.e. to improve developer friendliness.

Also in 2014, Angiuli et al. showed how to do version control using HoTT by developing a Darcs-style "patch theory" in HoTT. This shows that HoTT is a promising tool for some practical programming applications; can we find more appropriate application areas which can benefit from HoTT?


Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs.
Information Processing Letters 27, 125–128 (1988)

Erwig, M.: The graph Voronoi diagram with applications. Networks 36(3), 156–163
(2000)

both references copied from

Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson, Ying Daisy Zhuo: Round-Trip Voronoi Diagrams and Doubling Density in Geographic Networks. Transactions on Computational Science 14: 211-238 (2011)


Fast algorithm for linear context finding

You can solve this in $O(n \lg^2 n)$ time.

Build a (balanced) binary tree with $n$ nodes, where the leaves are annotated with the values $x_1,x_2,\dots,x_n$, and $x_i$ is placed on the $i$th leaf from the left.  Annotate each internal node $v$ in the tree with the maximum value over all the leaves in the subtree rooted at $v$.  For instance, the root is annotated with $\max(x_1,x_2,\dots,x_n)$.  The tree and the annotations can be built in $O(n)$ time.

Next, note that, for any $j,k$, a sequence $x_j, x_{j+1}, \dots, x_k$ of consecutive leaves can be covered by some union of $O(\lg n)$ subtrees.  In particular, given any $j,k$, we can compute $\max(x_j,x_{j+1},\dots,x_k)$ in $O(\lg n)$ time, by traversing the tree and using the annotations on the internal nodes at the top of those $O(\lg n)$ subtrees.

Now, to compute $y_k$, we do a binary search to find the largest $j$ such that $\max(x_j,x_{j+1},\dots,x_{k-1})<x_k$ but $\max(x_{j-1},x_j,x_{j+1},\dots,x_{k-1})\ge x_k$.  Each iteration of the binary search takes $O(\lg n)$ time, and the binary search takes at most $O(\lg n)$ iterations, so this allows us to compute each $y_k$ in $O(\lg^2 n)$ time.

Finally, there are $n$ $y$-values that we want to compute, so the total running time is $O(n \lg^2 n)$.

This can be adjusted to work in an incremental/online/streaming fashion, with $O(\lg^2 n)$ running time per value of $x$ received, by tweaking the structure of the binary tree appropriately.

It's possible you might be able to get a slightly better solution by using 2-D range trees, where you store the $n$ points $(i,x_i)$ in the tree (for $i=1,2,\dots,n$).  However, I'm not certain.


The decision version of your problem is NP-complete. The NP-complete 3-Partition problem is reducible to your problem (input has only three boxes having the same volume with zero divisions of items).


Constructing a k-perfect permutations family

Here is a sketch on how to do almost what you want, but not quite.
It only proves a $k^{k+\operatorname{polylog}(k)}\log n$ bound.

Consider a set of size $m=n\log_2 k$ which we think of as $n$ groups on $\log_2 k$ elements each.

Next construct an $(m,k\log_2 k)$-universal set family $F$ of size $2^{k\log k+\operatorname{polylog}(k)}\log m$ using
the method of Naor, Schulman, and Srinivasan. We interprete each set in $F$ as a string on $n$ symbols from $[k]$ with one symbol for each group.

Now we turn each string into a permutation of $[n]$ in the following way:

We first think of the $n$ first positive integers divided in $k$ stacks $T_0$ throgh $T_{k-1}$ where $T_0$ contains the elements $1,...,n/k$ from top to bottom, $T_1$ contains $n/k+1,...,2n/k$, and so on.

We parse each string $s_1s_2...s_n\in F$ into a permutation by considering the symbols one at a time for increasing $j$, and on encountering symbol $s_j$ we pop the stack
$T_{s_j}$ from the top and put that number in place $j$ of the permutation.

Since the family $F$ was $(m,k\log_2 k)$-universal, we know that for every ordered set of $k$ of the $n$ groups, there is one string that maps the symbols $0$,$1$,...,$k-1$ to that ordered set. By the construction of the stacks, the elements fetched to the permutations preserve the order required.


You're right to think of hash functions in terms of "random bits produced".  So if you have a hash function that produces a 64 bit hash, you can treat is as 4 16-bit hashes (by splitting), and so on.

For the scheme described above (which should be attributed to Dillinger and Manolios;  Kirsch/Mitzenmacher just analyzed it), that means you're correct; if you have a single hash function with $2 \lg(m)$ bits, you should be fine.


Complexity of hidden polygon puzzle on square grids?

I thought of this weird reduction (chances that it is wrong are high :-). Idea: reduction from Hamiltonian path on grid graphs with degree $\leq 3$; each node of the planar graph can be shifted in such a way that every "row" ($y$ value) and every "column" ($x$ value) contains at most one node. The graph can be scaled and each node can be replaced by a square gadget with many points; horizontal links between the gadgets (the edges of the original graph) are made using pairs of points on distinct rows, vertical links using pair of points on distinct columns. Node traversals are forced using the "many points" of the square gadgets.

The node gadget is represented in the following figure:

It has 3 "interface points" $[W,N,E]$ (on distinct columns/rows), and an inner border of $C \times C$ points. A polyline that traverses the gadget from one interface point to another can have a number of corners that is proportional to $C$ (three traversals of the gadget are shown in the figure), in particular the number of corner points is between $2C$ and $2C+2$ (the total number of points of the gadget is $C \times C - 4 + 6$).
The gadget can be rotated to get other interface point combinations ($[N,E,S]$, $[E,S,W]$, $[S,W,N]$).

Now we can shift the planar grid graph in such a way that for every pair of nodes $(x_1,y_1), (x_2,y_2)$, $x_1 \neq x_2$ and $y1 \neq y_2$. See the following figure of a simple $4 \times 3$ grid. Next, we can scale the graph and replace each node with the gadget above. At this stage each gadget is "isolated": a polyline cannot go from one gadget to another.

Now we can simulate the edges of the original graph using pairs of points on the bottom or on the right, each pair on a separate row or on a separate column; see the following figure for two adjacent nodes linked horizontally (in a new bottom row two points are added one on the same column of interface point $E$ of the first gadget, the other on the same column of interface point $W$ of the second gadget).

On every gadget there can be max $4 + 2C$ corner points (1 generated by the enter interface point, 1 generated by the exit interface point, 2 generated by the extra turn on straight traversals and 2C on the inner zig-zag), the points used for the edges can generate max $2e$ corner points.

Suppose that the original graph has $n$ nodes and $e$ edges, if we pick $C > (4n+2e)$, and $k = 2Cn$ as the number of corner points that must be used, then we force the "hidden" polygon of the puzzle to traverse every gadget; but every gadget can be entered/exited exactly once (through a pair of interface cells); so the problem has a solution if and only if the original grid graph has an Hamiltonian path.


Separating Logspace from Polynomial time

Circuit depth lower bounds (equivalently, formula size lower bounds) are probably the most natural approach:  A Super-$\log^2(n)$ depth lower bound for a problem in $\mathsf P$ would separate $\mathsf P$ from $\mathsf L$, and the Karchmer-Wigderson communication complexity technique may be the natural one for that.


$NP$-completeness of recognizing the difference of two permutations

The restricted problem, where one of the permutations is the identity, is certainly in $\mathsf{P}$.  Construct the bipartite graph where each vertex $i \in V_1=\{1,2,\ldots,n\}$ is connected to the element(s) $j \in V_2=\{1,2,\ldots,n\}$ such that $|i-j|=A[i]$.  Then the desired permutation $\sigma$ exists if and only if the graph has a perfect matching (i.e., a matching with $n$ edges), which can be determined in polynomial time.


Does mathematical model for conccurent computations exist?

As already suggested above, process algebra or process calculus is the place to start. Quoting freely from the respective Wikipedia page,

  History

  In the first half of the 20th century, various formalisms were
  proposed to capture the informal concept of a computable function,
  with μ-recursive functions, Turing Machines and the lambda calculus
  possibly being the best-known examples today. The surprising fact that
  they are essentially equivalent, in the sense that they are all
  encodable into each other, supports the Church-Turing thesis. Another
  shared feature is more rarely commented on: they all are most readily
  understood as models of sequential computation. The subsequent
  consolidation of computer science required a more subtle formulation
  of the notion of computation, in particular explicit representations
  of concurrency and communication. Models of concurrency such as the
  process calculi, Petri nets in 1962, and the Actor model in 1973
  emerged from this line of enquiry.

  Research on process calculi began in earnest with Robin Milner's
  seminal work on the Calculus of Communicating Systems (CCS) during the
  period from 1973 to 1980. C.A.R. Hoare's Communicating Sequential
  Processes (CSP) first appeared in 1978, and was subsequently developed
  into a full-fledged process calculus during the early 1980s. There was
  much cross-fertilization of ideas between CCS and CSP as they
  developed. In 1982 Jan Bergstra and Jan Willem Klop began work on what
  came to be known as the Algebra of Communicating Processes (ACP), and
  introduced the term process algebra to describe their work.1 CCS,
  CSP, and ACP constitute the three major branches of the process
  calculi family: the majority of the other process calculi can trace
  their roots to one of these three calculi.


How to model degree variable in logic (new type of modal logic?)?

What semantics of the logical operators would you like to have? Two of the best studied semantics for degrees are (propositional) Łukasiewicz logic and Gödel-Dummet logic. The latter enforces the domain to be a linear order which would allow you to model them via the naturals. It is also axiomatizable, since it is equivalent to intuitionistic propositional logic with the axiom of linearity (A => B) \/ (B => A).

It also has a hyper-sequent calculus which is sound and complete (have a look at e.g. A. Avron "A Simple Proof of Completeness and Cut-elimination for Propositional Gödel Logic"), which you could implement in Prolog.


Usually I just cite the journal version. But (if the history is important) I would add a note to the same citation about earlier conferences or preprints.

I think this style is preferable to making one paper look like two citations, except possibly in cases where the conference and journal papers have other significant differences than completeness (such as changes to the author list or claimed results). It is also unrelated to whether the citation is to my own paper or someone else's.

For harvard-style Name (year) citations, it might also make sense to mention the earlier version in-text as Name (year, announced earlier-year), as well as putting the information in the actual reference.

[Converted from a comment to an answer at the suggestion of Kaveh]


Generalized Geography on graphs of bounded treewidth

The proof in my 1989 paper does not rely on the fact that the graph is undirected.

Directed treewidth is a different notion than the treewidth of the undirected graph obtained by changing each arc to an edge.


What's the difference between ADTs, GADTs, and inductive types?

Algebraic data types let you define types recursively. Concretely, suppose we have the datatype

$$
  \mathsf{data\;list = Nil \;\;|\;\; Cons\;of\;\mathbb{N} \times list}
$$

What this means is that $\mathsf{list}$ is the smallest set generated by the $\mathsf{Nil}$ and $\mathsf{Cons}$ operators. We can formalize this by defining the operator $F(X)$

$$
   F(X) == \{ \mathsf{Nil} \} \cup \{ \mathsf{Cons}(n, x) \;|\; n \in \mathbb{N} \land x \in X \}
$$

and then defining $\mathsf{list}$ as

$$
   \mathsf{list} = \bigcup_{i \in \mathbb{N}} F^i(\emptyset)
$$

A generalized ADT is what we get when define a type operator recursively. For example, we might define the following type constructor:

$$
   \mathsf{bush}\;a = \mathsf{Leaf\;of\;}a \;\;|\;\; \mathsf{Nest\;of\;bush}(a \times a)
$$

This type means that an element of $\mathsf{bush\;}a$ is a tuple of $a$s of length $2^n$ for some $n$, since each time we go into the $\mathsf{Nest}$ constructor the type argument is paired with itself. So we can define the operator we want to take a fixed point of as:

$$
  F(R) = \lambda X.\; \{ \mathsf{Leaf}(x) \;|\; x \in X\} \cup \{ \mathsf{Nest}(v) \;|\; v \in R(X) \}
$$

An inductive type in Coq is essentially a GADT, where the indexes of the type operator are not restricted to other types (as in, for example, Haskell), but can also be indexed by values of the type theory. This lets you give types for length-indexed lists, and so on.


Formalizing the "no formula for primes" intuition

[Certainly not a complete answer, but too long for a comment]

Testing whether a given DFA accepts the base-2 representation of at least one prime number is not known to be computable. If it were uncomputable, that's some kind of weak evidence that there's no "regular-ish" formula for primality. (I mean, we know the set of primes itself is not regular, but here it's about whether there's a formula that's sufficiently simple that you could use it to help decide whether a given DFA accepts any primes.)

In another direction, given that your conjecture is about the difference between cubic and quadratic, it might be reasonable to think about whether the problem is complete for cubic time under sub-cubic reductions (see Vassilevska Williams & Williams). It looks tricky, or even unlikely, since it's so different from the other "cubic-complete" problems, like all-pairs shortest paths, triangle detection, etc., but could be worth considering nonetheless. Their framework was in the context of deterministic algorithms, but it shouldn't be too hard to adapt to randomized...


Compare similar N-Dimensional vector in a database

What you're looking for is a procedure to do near-neighbor searching in a high dimensional Euclidean space, or do dimensionality reduction prior to doing such a near neighbor search.

There are two approaches that are likely to help:

Use a native near-neighbor search procedure that works in high dimensions. Locality-sensitive hashing is a popular choice in this regard.
Apply dimensionality reduction, and then use a technique that works for fewer dimensions. In this case, you should look at the ANN near-neighbor library, and also look into using the Johnson-Lindenstrauss transform for dimensionality reduction (or possibly even PCA to reduce dimensions).

(warning - self promotion alert: I have a paper that describes different implementations of Johnson-Lindenstrauss and how they compare)


Complexity of marriage matching problem?

I may have misunderstood the question, because my answer conflicts with Serge's. To my understanding, you're asking about the Linear Bottleneck Assignment Problem. This is known to be solved in O(n^2.5).

The most complete source of information is [1], although I really don't like the book's style. There's also a website: http://www.assignmentproblems.com/linearBNAP.htm

EDIT: To clarify, the we want an assignment such that the edge with maximal cost is minimized. The cost will be the maximal number of unassigned attributes for either the man or the woman that are matched.

EDIT2: I can only offer references from the book I cited. Three of them are:

G. Carpaneto and P. Toth Algorithm for the solution of the bottleneck assignment problem. Computing, 27:179-187m 1981
U. Derigs. Alternate strategies for solving bottleneck assignment problems - analysis and computational results. Computing, 33:95-106, 1984
U. Derigs and U. Zimmermann. An augmenting path method for solving linear bottleneck assignment problems. Computing, 19:285-295, 1978

You should try to get hold of the book, since lists some of the available algorithms.

[1] Assignment Problems by Rainer Burkard, Mauro Dell'Amico, Silvano Martello


L1 - embeddability of metrics supported on the Hypercube

In general there are all kinds of lower bounds for embedding an arbitrary metric on the hypercube into $\ell_1$. For example, the edit distance cannot be embedded with better than $\log n$ distortion. Note that the Hamming distance itself embeds isometrically in $\ell_1$, so you can't expect to prove any nontrivial lower bound over all metrics on the hypercube.

p.s I don't think the boolean-ness matters at all.


Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs

An (optimal) $r$-domination for $G$ is an (optimal) domination for the $r$th power $G^r$ and vice versa
($G^r$ is obtained from $G$ by adding new edges between distinct vertices of distance at most $r$).

The following facts are well known: (1) All powers of a strongly chordal graph are strongly chordal
(A. Lubiw, Master thesis; see also Dahlhaus & Duchet, On strongly chordal graphs,
Ars Combin. 24 B (1987) 23-30), and (2) Domination is solvable in linear time for strongly chordal graphs
(M. Farber. Domination, independent domination and duality in strongly chordal graphs,
Discrete Appl. Math., 7 (1984) 115–130). Hence $r$-domination is solvable in polynomial time for
strongly chordal graphs, in particular for trees ($r$ fixed or not).

Gurski & Wanke proved in this paper
that the clique-width of $G^r$ is at most $2\cdot (r+1)^{\text{tw}(G)+1}−2$, where $\text{tw}(G)$ is the tree-width
of $G$. Thus, for fixed $r$, the $r$th powers of bounded tree-width graphs have bounded clique-width.
Hence, for fixed $r$, $r$-domination is solvable in polynomial time for bounded tree-width graphs
(by Courcelle's theorem).


Complexity of finding a second solution given a correct solution to an NP-complete problem

The question seems to be solved while I was writing this answer, but let me post my answer anyway.

Yato and Seta [YS03] (both are my colleagues when I was a student) propose a general framework to prove the NP-completeness of this kind of problems, where they are called Another Solution Problems or ASPs, and prove the NP-completeness of the ASPs of many puzzles.  They consider a restricted notion of reductions between relation problems called ASP reductions, and show that the NP-hardness of ASPs is preserved under ASP reductions and show that many known reductions can be in fact viewed as or modified to ASP reductions between natural relation problems.

[YS03] Takayuki Yato and Takahiro Seta.  Complexity and completeness of finding another solution and its application to puzzles.  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003.


Finding subgraphs with high treewidth and constant degree

See the paper by Julia Chuzhoy and myself on Treewidth sparsifiers.
We show that one can obtain a subgraph of degree at most 3 with treewidth $\Omega(k/polylog(k))$ where $k$ is the treewidth of $G$.
https://arxiv.org/abs/1410.1016 The proof is shorter than the one
for grid minors but it is still not that that easy and builds on several previous
tools.

Suppose you settle for an easier target - degree 4 and treewidth $\Omega(k^{1/4})$ then you can get it much more easily via  result of Reed and Wood on grid-like minors. https://arxiv.org/abs/0809.0724

Another easy result you can obtain is the following which is a starting point for some of the more involved proofs. You can get a subgraph of degre  $\log^2(k)$
and treewidth $\Omega(k/\mathsf{polylog}(k))$. You can see the treewidth sparsifier paper for the argument to achieve this.


Are uniqueness rules converse to introduction rules?

Uniqueness is not converse to introduction. Uniqueness rules in type theory are
components of isomorphisms. If a type former is specified with an isomorphism, then

Constructors form one map
Eliminators form the inverse map
β-rules express elim ∘ con = id
η-rules (uniqueness) express con ∘ elim = id

For example, function types are given as Tm Γ (Π A B) ≃ Tm (Γ, A) B.

lam : Tm (Γ, A) B → Tm Γ (Π A B)
app : Tm Γ (Π A B) → Tm (Γ, A) B

For Σ types, we have that internal Σ is isomorphic to metatheoretic Σ.

pair  : Σ(t : Tm Γ A) × (Tm Γ (B[t])) → Tm Γ (Σ A B)
proj  : Tm Γ (Σ A B) → Σ(t : Tm Γ A) × (Tm Γ (B[t]))

In extensional type theory, the identity type is specified to be isomorphic to
metatheoretic equality:

refl    : t = u → Tm Γ (Id t u)
reflect : Tm Γ (Id t u) → t = u

Here reflect is equality reflection. If the metatheory has UIP, the object
theory inherits it via the β and η rules (omitted above). If the
metatheory does not have UIP, the object theory also does not have it!
So UIP is not like η-rules for other negative type formers. UIP is something
that we get if assume UIP in the metatheory and try to weaken the above rules
just enough to get decidable definitional equality.
In intensional TT, Id is specified differently, since in that case we do
not think of Id as a negative type (a terminal algebra, specified by an
isomorphism), but as a positive type (initial algebra).
Can we define terms of positive types with isomorphisms? What about sum types:

inj  : Tm Γ A + Tm Γ B → Tm Γ (A + B)
elim : Tm Γ (A + B) → Tm Γ A + Tm Γ B

elim is unfortunately not feasible in a constructive and proof-relevant
way. If we have a variable x : A + B in the context, we cannot decide whether
A is provable or B is provable. This only works in the empty context, where
everything computes to inj1 or inj2.
In other words, the problem is that positive types are categorically defined by mapping out (like (A + B) → C ≃ (A → B) × (A → C)), but in type theory, terms always map from the context into the type former.


Nondeterministic communication complexity of set disjointness?

$N^1(DISJ_n) \geq n$.

The fooling set technique actually provides lower bounds on the cover number. $C^1(f)$ is the minimum number of monochromatic rectangles needed to cover the $1$-inputs of $f$.  In the fooling set technique, you create a set of input pairs and show that each must lie in distinct monochromatic rectangles.

In this case, look at the set of input pairs $\{(A,\bar{A}) : A \subseteq [n]\}$.  It is not too hard to show that $(A, \bar{A}), (B, \bar{B})$ must lie in different monochromatic rectangles if $A,B$ are distinct.  Hence, to cover the $1$-inputs, we need at least $2^n$ monochromatic rectangles.

Using $N^1(f) = \log_2(C^1(f))$, we get that $N^1(DISJ_n) \geq n$.

(This example is Example 1.23 from Kushilevitz/Nisan)


Partitioning a rectangle without harming inner rectangles

NEW ANSWER: the following simple algorithm is asymptotically optimal:

  Stretch each of the rectangles $C_i$ arbitrarily, to the maximal extent possible such that the rectangles remain pairwise-disjoint.

The number of holes is at most $k-2$. This is asymptotically optimal, as there are configurations in which the number of holes is at least $k-O(\sqrt k)$.

The proofs are in this paper.

OLD ANSWER:

The following algorithm, while not optimal, is apparently sufficient for finding a rectangle-preserving partition with $N=O(n)$ parts.

The algorithm works with a rectilinear polygon $P$, which is initialized to the rectangle $C$.

Phase 1: Pick a rectangle $C_i$ which is adjacent to a western boundary of $P$ (i.e, there is no other rectangle $C_j$ between the western side of $C_i$ and a western boundary of $P$). Place $C_i$ within $P$ and stretch it until it touches the western boundary of $P$. Let $E_i$ (for $i=1,\dots,n$) be the stretched version of $C_i$. Let $P=P\setminus E_i$. Repeate Phase 1 $n$ times until all $n$ original rectangles are placed and stretched. In the image below, a possible order of placing the rectangles is $C_1,C_2,C_4,C_3$:

Now, $P$ is a rectilinear polygon (possibly disconnected), like this:

I claim that the number of concave vertices in $P$ is at most $2n$. This is because, whenever a stretched rectangle is removed from $P$, there are 3 possibilities:

2 new concave vertices are added (like when placing $C_1,C_4$);
3 new concave vertices are added and 1 is removed (like with $C_3$);
4 new concave vertices are added and 2 are removed (like with $C_2$).

Phase 2: Partition $P$ into axis-parallel rectangles using an existing algorithm (see Keil 2000, pages 10-13 and Eppstein 2009, pages 3-5 for a review).

Keil cites a theorem that says that the number of rectangles in a minimal partition is bounded by 1 + the number of concave vertices. Hence, in our case the number is at most $2n+1$, and the total number of rectangles in the partition is $N\leq 3n+1$.

This algorithm is not optimal. E.g, in the above example it gives $N=13$ while the optimal solution has $N=5$. So two questions remain:

A. Is this algorithm correct?

B. Is there a polynomial-time algorithm for finding the optimal $N$, or at least a better approximation?


Formalizing Homotopy Type theory in Idris

Here is a small, incomplete, and inconsistent formalization of HoTT in Idris. It shows that you can derive a contradiction in Idris just by postulating univalence. There are two barriers to formalizing HoTT in Idris at the moment.

Barrier 1:
Idris has heterogeneous equality and heterogeneous equality rewriting. From the HoTT perspective this means we have access to the following rewriting principle, which is inconsistent with univalence:
$$
 \prod_{P \,:\, X \to \mathsf{Type}}\ \prod_{x\,:\,X}\ \prod_{p \,:\, x = x}\ \prod_{a,\,b \,:\, P\, x} (\mathsf{transport}\ P\ p\ a = b) \to (a = b)
$$
With this principle, we can easily prove True = False.

Barrier 2:
The pattern matching in Idris is too strong for HoTT, as Neel Krishnaswami suspected in a comment above. We can derive Streicher's K. This leads to uniqueness of identity proofs, and is therefore incompatible with univalence. We can once again show True = False.


Boolean Functions Where Sensitivity Equals Block Sensitivity

Recently, I proved that s(f) = bs(f) for unate functions and read-once functions over the Boolean operators AND, OR and EXOR, and my paper including the results was accepted to TCS 2014.
(http://dx.doi.org/10.1007/978-3-662-44602-7_9)

You may be attacking this problem. If so, I feel sorry, but I started to attack the problem independently before the question was posted. A preliminary version of my paper was presented at a Japanese domestic meeting in Dec/2013 and the submission deadline was Oct/2013.
(http://www.ieice.org/ken/paper/20131220DBID/eng/)


There is a totally different algorithm due to Subramanian which uses a fixed point approach. The first idea is to represent the knowledge that we have at any given point in time using intervals, which represent which women each man is considering, and vice versa. Using ideas similar to Gale-Shapley, we keep shrinking the intervals. In contrast to Gale-Shapley, this algorithm is symmetric with respect to gender. Eventually a fixed point is reached, and we can read the man-optimal and woman-optimal matchings. Subramanian found a neat way to implement this using three-valued logic and comparator networks. Check out for example this paper.
Subramanian's approach was later elaborated by Feder.


What is the most efficient algorithm for deciding if an element is the least in its orbit?

For general equivalence relations, not those arising from permutation group actions, even finding lexicographically least is still "too" general. Finding the lexicographically smallest element in an equivalence class can be $NP$-hard (in fact, $P^{NP}$-hard) - even if the relationship has a polynomial-time canonical form [1].

However, for permutation group orbit problems as you describe, deciding whether two points lie in the same orbit is not likely to be $NP$-hard: it is in $NP \cap coAM$, and hence not $NP$-hard unless the polynomial hierarchy collapses to the second level.

A canonical form for graph isomorphism is also a special case of the second problem you state. The best known canonical form for graph isomorphism runs in time $2^{\tilde{O}(\sqrt{n})}$ [2].

Since you said in the comments that any canonical form will do, you might also be interested in my paper with Lance Fortnow [3]: in its currently generality, I think your question is related to our results. We show that if every equivalence relation decidable in $P$ has a canonical form in $P$, then "bad" consequences result, such as $NP = UP = RP$, which in particular implies that the polynomial hierarchy collapses down to $BPP$. On the other hand, the equivalence relations you're interested in may not be in $P$, but this result suggests that even if it lies in a higher complexity class other hard problems may still stand in your way.

So I think if you want some better upper bounds you really need the problem to be more specific.

[1] Andreas Blass and Yuri Gurevich. Equivalence relations, invariants, and normal forms. SIAM J. Comput. 13:4 (1984), 24-42.

[2] László Babai and Eugene M. Luks. Canonical labelings of graphs. STOC 1983, 171-183.

[3] Lance Fortnow and Joshua A. Grochow. Complexity classes of equivalence problems revisited. Inform. and Comput. 209:4 (2011), 748-763. Also available as arXiv:0907.4775v2.


Guessing a low entropy value in multiple attempts

Bob's best bet is to guess the $t$ values with largest probability.

If you're willing to use Rényi entropy instead, Proposition 17 in Boztaş' Entropies, Guessing and Cryptography states that the error probability after $t$ guesses is at most
$$ 1 - 2^{-H_2(\mu)\left(1-\frac{\log t}{\log n}\right)} \approx \ln 2 \left(1-\frac{\log t}{\log n}\right) H_2(\mu), $$
where $n$ is the size of the domain. Granted, the dependency on $t$ is pretty bad, and perhaps Boztaş was focused on a different regime of the entropy.

For the Shannon entropy, you can try to solve the dual optimization problem: given a fixed failure probability $\delta$, find the maximal entropy of such a distribution. Using the convexity of $-x\log x$, we know that the distribution $\mu$ has the form $a,b,\ldots,b;b,\ldots,b,c$, where $a\geq b\geq c$, $a+(t-1)b = 1-\delta$, and $c = \delta-\lfloor\frac{\delta}{b}\rfloor b$. We have $t-1+\lfloor\frac{\delta}{b}\rfloor$ values that get probability $b$. Conditioning on $s = \lfloor\frac{\delta}{b}\rfloor$, we can try to find $b$ which minimizes the entropy. For the correct value of $s$, this will be an internal point (at which the derivative vanishes). I'm not sure how to get asymptotic estimates using this approach.


Intuition: Odd-cycle transversal in triangle-free graphs

My intuition says it's probably true, and here's a matching lower bound (i.e. a graph of which you have to delete at least $\frac{n^2}{25}$ edges for it to become bipertite:

$G=(V_1\cup V_2\cup V_3\cup V_4\cup V_5, (V_1\times V_2) \cup (V_2\times V_3) \cup (V_3\times V_4) \cup (V_4\times V_5) \cup (V_5\times V_1))$
, $|V_1| = |V_2| = |V_3| = |V_4| = |V_5|$.

This graph is certainly triangle free, but if $x<\frac{n^2}{25}$ edges are to be deleted there will still exist a $C_5=v_1\to v_2\to v_3\to v_4\to v_5 \to v_1$  for some vertices $v_1\in V_1, v_2\in V_2, v_3\in V_3, v_4\in V_4, v_5\in V_5$.

As for the second question, it is well known that counting simple cycles of length $2k+1$ are $\#W[1]-hard$, with respect to $k$, and can't be computed in time $n^{o(k)}$ unless ETH fails.

There is, however, a possibility to approximate the number of such cycles in $O^*(2^{O(k)})$.


the halting problem does not seem to be studied much for nondeterministic TMs (there is no single obvious way to extend the halting problem to NTMs) and most problems associated with undecidability seem to be defined in terms of non-NTMs (ie DTMs). however here is one generalization that could be related to your question.

A Parameterized Halting Problem Yijia Chen and Jorg Flum

  The parameterized problem p-Halt takes as input a nondeterministic Turing machine M and a natural number n, the size of M being the parameter. It asks whether every accepting run of M on empty input tape takes more than n steps. This problem is in the class XPuni, the class “uniform XP,” if there is an algorithm deciding it, which for fixed machine M runs in time polynomial in n. It turns out that various open problems of different areas of theoretical computer science are related or even equivalent to p-Halt ∈ XPuni. Thus this statement forms a bridge which allows to derive equivalences between statements of differ- ent areas (proof theory, complexity theory, descriptive complexity, . . . ) which at first glance seem to be unrelated. As our presentation shows, various of these equivalences may be obtained by the same method.


Applicability of Church-Turing thesis to interactive models of computation

Here's my favorite analogy.  Suppose I spent a decade publishing books and papers arguing that, contrary to theoretical computer science's dogma, the Church-Turing Thesis fails to capture all of computation, because Turing machines can't toast bread.  Therefore, you need my revolutionary new model, the Toaster-Enhanced Turing Machine (TETM), which allows bread as a possible input and includes toasting it as a primitive operation.

You might say: sure, I have a "point", but it's a totally uninteresting one.  No one ever claimed that a Turing machine could handle every possible interaction with the external world, without first hooking it up to suitable peripherals.  If you want a TM to toast bread, you need to connect it to a toaster; then the TM can easily handle the toaster's internal logic (unless this particular toaster requires solving the halting problem or something like that to determine how brown the bread should be!).  In exactly the same way, if you want a TM to handle interactive communication, then you need to hook it up to suitable communication devices, as Neel discussed in his answer.  In neither case are we saying anything that wouldn't have been obvious to Turing himself.

So, I'd say the reason why there's been no "followup" to Wegner and Goldin's diatribes is that TCS has known how to model interactivity whenever needed, and has happily done so, since the very beginning of the field.

Update (8/30): A related point is as follows.  Does it ever give the critics pause that, here inside the Elite Church-Turing Ivory Tower (the ECTIT), the major research themes for the past two decades have included interactive proofs, multiparty cryptographic protocols, codes for interactive communication, asynchronous protocols for routing, consensus, rumor-spreading, leader-election, etc., and the price of anarchy in economic networks? If putting Turing's notion of computation at the center of the field makes it so hard to discuss interaction, how is it that so few of us have noticed?

Another Update: To the people who keep banging the drum about higher-level formalisms being vastly more intuitive than TMs, and no one thinking in terms of TMs as a practical matter, let me ask an extremely simple question.  What is it that lets all those high-level languages exist in the first place, that ensures they can always be compiled down to machine code?  Could it be ... err ... THE CHURCH-TURING THESIS, the very same one you've been ragging on?  To clarify, the Church-Turing Thesis is not the claim that "TURING MACHINEZ RULE!!"  Rather, it's the claim that any reasonable programming language will be equivalent in expressive power to Turing machines -- and as a consequence, that you might as well think in terms of the higher-level languages if it's more convenient to do so.  This, of course, was a radical new insight 60-75 years ago.

Final Update: I've created a blog post for further discussion of this answer.


I will offer a semantic perspective. The relationship between values and general computations may be expressed in terms of an adjunction between two categories:
\begin{align*}
F &: \mathcal{V} \to \mathcal{C} \\
U &: \mathcal{C} \to \mathcal{V} \\
F &\vdash U
\end{align*}
Here $\mathcal{V}$ is a category of values, $\mathcal{C}$ is a category of computations. The prototypical example comes from domain theory:

$\mathcal{V}$ is the category of predomains, i.e., $\omega$-chain complete posets which may not have a list element,
$\mathcal{C}$ is the category of domains, i.e., $\omega$-chain complete posets with a least element,
$F$ is the lifting functor
$U$ is the forgetful functor

This view is closely related to Paul Levy's call-by-push-value (CBPV).

The semantic picture suggests that we should not only distinguish values and computations, but also value types and computations types. Thus, instead of saying that there are terms of type $A$, some of which are values and others are computations, we say instead that there are two kinds of types: the elements of value types are always values, while the elements of computation types are always computations.

In CBPV languages the distinction is explicit. For instance $\mathtt{nat}$ is a value type and $42 : \mathtt{nat}$ while $F \mathtt{nat}$ is a computation type inhabited by computations such as $\mathtt{return}\;42$ and $(\lambda n . n \cdot n + 6) \; 6$.

From a theoretical point of view such a typing discipline is desirable, because the value/computation distinction becomes a proper mathematical concept, rather than a syntactic device that drives normalization algorithms. (I warned you that I will offer the semantic perspective.)

We may think about the distinction between values and computations for dependent types and other corners of Barndregt's cube. The semantic picture suggests that we should again distinguish value types from computation types. Thus, we really should replace the judgement $\Gamma \vdash A \ \mathrm{type}$ ($A$ is a type in context $\Gamma$) with two judgements:

$\Gamma \vdash A \ \mathrm{vtype}$
$\Gamma \vdash C \ \mathrm{ctype}$

Of course, the next step requires us to figure out precisely how to extend the above picture to the rather more complicated situation that arises through dependencies. This is a topic of current research, and a great deal of past research.

Now, as to whether something like $(\lambda T .  \mathrm{return}\,T) (\prod_{x : A} B(x))$ itself is a value or a computation can be phrased in terms of universes. There ought to be a universe of value types $\mathcal{U}_V$ and a universe of computations $\mathcal{U}_C$, each reflecting the two kinds of judgements above. We also have to decide whether $\mathcal{U}_V$ and $\mathcal{U}_C$ themselves are value or computation types (probably value types, with corresponding computation types $F \mathcal{U}_V$ and $F \mathcal{U}_C$). The typing rules would place $(\lambda T .  T) (\prod_{x : A} B(x))$ into one or the other universe (presumably in this case the universe of computations).

I do not really want to give a definitive answer here, I just want to place the question into a proper mathematical context that allows us to consider the mathematical possibilities rather than look for an answer based on experience with normalizing algorithms.


Parametrized complexity of sparse optimization

This may be related to what you have in mind: arxiv.org/abs/0804.4666


What is the role of predicativity in inductive definitions in type theory?

No, in this case, predicativity and monotonicity are not closely related.

The positivity check in Coq/Adga serves to ensure that you are taking the least fixed point of a monotonic thing, roughly.

Here's how to think of inductive types in terms of lattices and monotone operators. Recall that the Knaster-Tarski theorem says that on a complete lattice $L$, every monotone operator $f : L \to L$ has a least fixed point $\mu(f)$. Next, we can think of the types in a type theory as forming a lattice under provability. That is, type $S$ is below $T$ if the truth of $S$ entails that of $T$. Now, what we would like to do is to take a monotone operator $F$ on types, and use Knaster-Tarski to get out an interpretation of the least fixed point of this operator $\mu(F)$.

However, types in type theory aren't just a lattice: they form a category. That is, given two types $S$ and $T$, there are potentially many ways for $S$ to be below $T$, with one way for each proof $e : S \to T$. So a type operator $F$ also has to do something sensible on these proofs. The appropriate generalization of monotonicity is functoriality. That is, we want $F$ to have an operator on types, and also to have an action on proofs, such that if $e : S \to T$, then $F(e) : F(S) \to F(T)$.

Now, functoriality is preserved by sums and products (ie., if $F$ and $G$ are endofunctors on types, then $F+G$ and $F\times G$ (acting pointwise) are also functors on types (assuming we have sums and products in our algebra of types). However, it is not preserved by the function space, since the exponential bifunctor $F \to G$ is contravariant in its left argument. So when you write an inductive type definition, you are defining a functor to take a least fixed point of. To ensure that it is indeed a functor, you need to rule out occurences of the recursive parameter on the left-hand-side of function spaces --- hence the positivity check.

Impredicativity (in the sense of System F) is generally avoided, because it is a principle that forces you to choose between classical logic and set-theoretic models. You can't interpret types as sets in classical set theory if you have F-style indexing. (See Reynolds' famous "Polymorphism is Not Set-Theoretic".)

Categorically, F-style impredicativity says that the category of types and terms forms a small complete category (that is, homs and objects are both sets, and limits of all small diagrams exist). Classically this forces a category to be a poset.   Many constructivists are constructive because they want their theorems to hold in more systems than just classical logic, and so they don't want to prove anything that would be classically false. Hence they are leery of impredicative polymorphism.

However, polymorphism lets you say many conditions that are classically "large" internally to your type theory -- and positivity is one of them! A type operator $F$ is functorial, if you can produce a polymorphic term:

$$
\mathsf{Fmap} : \forall \alpha, \beta.\; (\alpha \to \beta) \to (F(\alpha) \to F(\beta))
$$

See how this corresponds to functoriality? IMO, this would be a very nice option to have in Coq, since it would let you do generic programming much more easily. The syntactic nature of the positivity check is a big hindrance to generic programming, and I would be happy to trade the possibility of classical axioms for more flexible functional programs.

EDIT: The question you are asking about the difference between Prop and Set arises from the fact that the Coq developers want to permit you think about Coq theorems in naive set-theoretic terms if you want, without forcing you to do so. Technically, they split Prop and Set, and then prohibit sets from depending on the computational content of Prop.

So you can interpret Prop as truth values in ZFC, which are the booleans true and false. In this world, all proofs of propositions are equal, and so obviously you should not be able to branch on the proof of a proposition. So the prohibition on sets depending on the computational content of proofs of Prop is totally sensible. Furthermore, the 2-element boolean lattice is obviously a complete lattice, so it should support impredicative indexing, since arbitrary set-valued meets exist. The predicativity restriction on Sets arises from the fact (mentioned above) that F-style indexing is degenerate in classical set-theoretic models.

Coq has other models (it's constructive logic!) but the point is that off the shelf it will never prove anything that a classical mathematician would be puzzled by.


K-fold Traveling salesman problem - A variant of TSP

There was a paper on the arxive last month, dealing with this generalization of the TSP:

  The multi-stripe travelling salesman problem
  Eranda Cela, Vladimir Deineko, Gerhard J. Woeginger
  (Submitted on 20 Sep 2016)
  https://arxiv.org/abs/1609.09796

The problem does not seem to have a particular name in the literature.


Set packing with maximum coverage objective

Optimization version of 3D matching is a special case of your problem. Approximating Maximum 3D Matching is $APX$-complete. However, it is approximable within 3/2$+\epsilon $ for any  $\epsilon >0$

References:

Hurkens, C. A. J., and Schrijver, A. (1989), On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems,
SIAM J. Disc. Math. 2, 68-72.

Kann, V. (1991), Maximum bounded 3-dimensional matching is MAX SNP-complete, Inform. Process. Lett. 37, 27-35.


Hamiltonian cycle on graphs without small cycles

This unpublished manuscript by Hougardy, Emden-Weinert and Kreuter in 1997
provided a simple proof for the following result which is much stronger than the result pointed out in
Kristoffer Arnsfelt Hansen's answer:

  For any given rational number $0\le r <1/2$, the Hamiltonian cycle probem remains NP-complete even if restricted to bipartite planar $n$-vertex graphs of maximum degree 3 and girth $\ge n^r$.

The manuscript contains also similar results for other problems such as Dominating set, Max cut, VFS, etc.


Is public-key spread-spectrum communication possible?

Google reveals that the System Security Group at ETH have done work on "jamming-resistant radio broadcast communication without shared secret keys". Perhaps this would be a good place to start?


What is $\mathsf{NP}$ restricted to linear size witnesses?

The class ${\cal C}$ you are proposing is probably not $NP$. (If ${\cal C} = NP$, then every $NP$ language would have linear-size witnesses, which would imply that every $NP \subseteq TIME[2^{O(n)}]$ and $NP \neq EXP$, among other things).

It is very natural to consider such classes; they arise in several settings. In this paper, Rahul Santhanam (implicitly) proposed the notation $TIGU(t(n),g(n))$ for time-$t(n)$ computation with $g(n)$-guess bits. Hence ${\cal C} = \bigcup_{k} TIGU(n^k,kn)$. In this paper, I defined an analogous class $NTIBI[t(n),b(n)]$. (NTIBI stands for "nondeterministic time and bits".) Also, Cai and Chen would call your class $GC(O(n), P)$ (GC stands for "Guess and Check", cf. L. Cai and J. Chen. On the amount of nondeterminism and the power of verifying. SIAM Journal on Computing, 1996). Finally, if you search for "bounded nondeterminism" you may find three more notations for the same class...


For all non-negative integers $n_0$,$n_1$,$n_2$ and random strings $r_0,r_1,r_2$

$n_0 \:\: = \:\: (n_0+n_1+n_2)-(n_1+n_2)$
$=$
$\operatorname{plaintextsum}(\operatorname{encrypt}(n_0,r_0),\operatorname{encrypt}(n_1,r_1),\operatorname{encrypt}(n_2,r_2))$

$- \: \operatorname{plaintextsum}(\operatorname{encrypt}(n_1,r_1),\operatorname{encrypt}(n_2,r_2))$

.

Therefore any such scheme would be completely insecure

if more than 2 non-negative integers are encrypted with it.


Bounds for maximum number of code-words in a ternary error correcting code with length n and distance d?

The exact answer is unknown in general. One standard upper bound for $q-$ary codes is the Singleton bound, which gives
$$|C|\leq q^{n-d+1},$$ and codes meeting this bound are called MDS.

A lower bound is the Gilbert-Varshamov bound, given by

$$|C|\geq \frac{q^n}{\mathrm{Vol}_q(d-1)}=\frac{q^n}{\sum_{k=0}^{d-1} \binom{n}{k}(q-1)^k}.$$
Using these keywords should get you started, there are many more results.


there are a bunch of algorithms that are "truly 2nd order" although usually not explicitly described in these terms.  Whenever we have sub-linear time algorithms, implicit is some kind of oracle access to the input, i.e. really treating the input as a function.

Examples:

(1) The Ellipsoid algorithms when working with a "separation oracle" (eg http://math.mit.edu/~vempala/18.433/L18.pdf )

(2) Submodular function minimization (eg http://people.commerce.ubc.ca/faculty/mccormick/sfmchap8a.pdf )

(3) The whole field of property testing is really of this form ( http://www.wisdom.weizmann.ac.il/~oded/test.html )

(4) Combinatorial auctions in the query model (eg  http://pluto.huji.ac.il/~blumrosen/papers/iter.pdf )


(I'm not in theory; please regard this as a placeholder answer.)

Is this a research-level question? You may have more luck at cs.stackexchange.com.
The reason you haven't found much relevant literature may be your choice of keywords. The terms  contract and communication often refer to describing patterns of interaction formed by message passing as a whole, usually abstracting away from the contents of the messages; your contracts, on the other hand, are limitations on the possible contents of individual messages. That subject is better known as validation, and indeed, grammars are routinely used for that purpose.
Your example uses HTML as the language to restrict, and introduces a BNF for describing it. Don't do that if you can avoid it; SGML and XML were invented for a reason.  They take away the need for you to describe how to recognize syntax trees in strings, so a grammar merely needs to describe a set of allowable trees. XML is a well-established and well-supported standard, and so are several grammar definition formalisms for XML-based languages: XML Schema, Relax-NG, DTDs, Schematron.
Your example also introduces a technique for describing entity encoding and decoding. SGML and XML come equipped with such a technique, and it is applied in HTML, so why not just use that? (Not that I'm happy with how that works, but it's standard: if you have an XML language, the mechanism is there for you to use.)
I'm puzzled by @Embeds{URI} - why isn't URI simply a nonterminal?  I can see that its grammar isn't that of HTML, but that of URIs, but XML has a way of dealing with that already: XIncludes and namespaces.  (Not that I'm happy with how that works, but it's standard: if you have an XML language, the mechanism is there for you to use.)
I don't understand your sanitizers or template context propagators. If you do need a more general annotation mechanism that can be used both to constrain syntax and to interpret it, have a look at stuff such as attribute grammars, affix grammars and definite clause grammars.  I'm not aware of a pendant for XML, but XSLT can be used in a similar way.
If the point of sanitizers and template context propagators really is to restrict the HTML language, why not just override the grammar for some nonterminals in the HTML grammar with your own, more restrictive definitions? Both XML Schema and Relax NG support this, although I must add that they don't provide any support for limiting such overrides to defining restrictions only.  An alternative is to use Schematron, in which syntactic constraints are a language construct.
HTML is an odd choice of language for an example - in a typical web application, there is no great need to constrain the HTML being sent (largely owing to the language being used for markup only and being SGML/XML-based) while it is imperative to put very clear constraints on the messages being accepted in the opposite direction, the HTTP requests. But those are usually simple and don't really use a standard language, unless you put something like SOAP on top. So I'm curious what sort of application you have in mind for this.

To summarize: yes, there is a lot of support for what you want to do (if I'm not too mistaken about your sanitizers and propagators), especially when the languages you use are XML-based.


Formal Representation of Haskell Data-Types

Unter the assumption, that lists simply represents arbitrary sets, the mathematical notation should probably read:

  An ARE is an element of the following set:

  $\{ (P, Q) \mid P \subseteq ARF \times ARF, Q \subseteq ARF \} $

But as you stated, lists in your domain are always finite, ordering is not important, but multiplicity is. Thus, I would model the lists as finite multisets. Using an explicit notation for mulitsets, a possible definition would be:

  An ARE is an element of the following set:

  $\{ (P_\chi, Q_\xi) \mid P \subseteq ARF \times ARF,
                           P~\text{finite},~
                           \chi \in (P \to \mathbb{N}^+),
                           Q \subseteq ARF, Q~\text{finite},~
                           \xi \in (Q \to \mathbb{N}^+) \} $

Here, the notation $P_\chi$ denotes a multiset with P being the underlying ordinary set and $\chi \in P \to \mathbb{N}^+$ being the multiplicity function of the multiset.


Decomposition of safety and liveness properties

Yes. The automata in question are often called "Looping" automata (so you have a keyword to start from).
A possible starting point is the following paper:
https://faculty.idc.ac.il/udiboker/files/MullerAutomata.pdf
A looping automaton can be described as $\left<Q,\Sigma,\delta,Q_0\right>$ where the components are states, alphabet, transition function $\delta:Q\times \Sigma\to 2^Q$ and $Q_0$ are the initial states. Then, the acceptance condition is that there exists a run on the word. That is, $w$ is accepted iff the automaton has some run on it.
It is easy to see (using
Kőnig's Lemma) that the acceptance condition can be equivalently described as follows: for a word $w\in \Sigma^\omega$, let $w_i$ be its prefix up to letter $i$, then $w$ is accepted iff $\delta^*(Q_0,w_i)\neq \emptyset$ for all $i\in \mathbb{N}$.
This shows that it's enough to track the subset construction in order to determine acceptance. What you end up is a deterministic automaton whose states are all accepting except for one, that corresponds to $\emptyset$.


Results in computer science via the Stepanov method

This may be too obvious, but the correctness proof of the Schwartz-Zippel randomized algorithm for polynomial identity testing uses essentially just this fact, plus induction.


hardness of approximating the chromatic number in graphs with bounded degree

As David pointed out, Khot's paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring", Theorem 1.6, says it is NP-hard to color $K$-colorable graph with $2^{\Omega((\log K)^2)}$ colors for graphs with degree at most $2^{2^{(\log K)^2}}$, for sufficiently large constant $K$. In other words, for graphs of degree $d$, it is hard to color $2^{\sqrt{\log\log d}}$-colorable graph with $\log d$ colors.

To get better degree bound, you can probably use ideas from Trevisan's paper "Non-approximability results for optimization problems on bounded degree instances". The key observation is that the graph produced by the FGLSS reduction is a union of complete bipartite subgraphs, and one can replace each of them with a bipartite disperser which is much sparser. Similar idea used in many result such as Chan http://eccc.hpi-web.de/report/2012/110/, Theorem 1.4 / Appendix D.

I think this should give you something like for $2^{\sqrt{c\log d}}$-colorable graphs of degree bounded by $d$, it is NP-hard to color it with $d^{c}$ colors for some constant $0<c<1$.

The degree bound in the paper Michael mentioned is similar to Khot's, namely exponential of the soundness case. Of course the above sparsification approach also improves this, but probably won't give better constant for your purpose.


Reduction of a language to a shorter equivalent

Think set theory.
We have for L1
$$ (A - {a}) \subset A^* $$
$$ A^*.(A-{a}).A^* \subset A^* $$
Then
$$ S1 = A^*.\{b\} $$
$$ S1 = A^*.(A)^*.A^*.\{b\} $$
$$ S2 =  (A^*.(A-{a})).A^*.\{b\} $$
$$ S1 - S2  = a^*b$$
Basically you removed everything from A* that does not have a, then you end up with a*.
Same argument goes for L2.
Then:
$$ L1.L2 = a*.b.b* = a^*.{b+b*} = a.b^+ $$
Note: This does not "reduce" the languages, but help you see how to arrive to the answer.
You may have to brush up on the operations of regular expressions, but the general logic should be a bit similar, if you realize that A* is a prefix closure and can be  written in many forms.


What is the problem in "closest pair problem" if all points share the same x-coordinate

Points with the same x-coordinate do not cause any substantial problem.  However, if you implement the divide-and-conquer algorithm carelessly, they may cause a problem.  One way to deal with them is by using symbolic perturbation.


Array-like data structure with O(1) worst-case concatenate/join?

I think Purely Functional Worst Case Constant Time Catenable Sorted Lists by Brodal et al. supplies what you want.


Is this generalization of context free grammars known and strict?

I think the answer to your question can be found in Theorem 3.1 of [1], where it is credited to Wechler [2]. An algebra is stable if it is closed under left quotient.

  A language is context-free iff it belongs to a finitely generated
  stable algebra.

[1] Berstel, J.; Boasson, L. Towards an algebraic theory of context-free languages. Fund. Inform. 25 (1996), no. 3-4, 217--239.

[2] Wechler, Wolfgang. Characterization of rational and algebraic power series. RAIRO Inform. Théor. 17 (1983), no. 1, 3-11.


This is equivalent to $LOGSPACE≠NP$ (which is obviously open). The proof of that equivalence relativizes (at least under the usual oracle models).
And there are oracles making $LOGSPACE = NP$ (the PSPACE-complete TQBF works) and making them not equal (the oracle separating P from NP works).


I tend to believe that c=3 is the right answer for the general case, and that it should be possible to give an example. I'll have to think more about that to know for sure.
It's a good question, and I don't know of existing work about it.

Research recently focused on which types of games have (best possible) c=1, mostly because of possible applications to amplification of unique games.

Barak et al generalized the counterexample of Raz to all unique games with SDP gaps.
Raz and Rosen showed that for expanding projection games c=1. There are also previous results by a super-set of those authors for free games.


How fast is an equivalent 2-tape TM compared to a $O(n^2)$ 1-tape TM?

Just an extended comment to underline how the question is (up to my knowledge) far from being solved (and easy).
First of all there are no "natural" quadratic lower bounds with respect to multi-tape Turing machines (see e.g. K.W.Regan, On Superlinear Lower Bounds in Complexity Theory). So the approach, find an $O(n^2)$ problem on a 1-tape Turing machine that cannot be solved faster on a 2-tape TM would imply a major breakthrough.
On the opposite direction, one should be able to find a "universal" way to speed-up the simulation of a 1-tape TM on a 2-tape TM, but there are some examples for which the task seems hard; for example a 1-tape TM can efficiently simulate a dynamic non-linear system such as 1-D cellular automata - CA - (steps are parallel and use local information); and it is conjectured that the only way to know the state of the system after $n$ steps is to evolve the system $n$ times according to the rules (see e.g the (famous? :-) computational irreducibility - CIR - conjectured by S. Wolfram and analyzed in H. Zwirn and J.P. Delahaye, Unpredictability and Computational Irreducibility).
For example for every 1-D CA $A$ there is an $O(n^2)$ 1-tape TM $M_A$ that solves the problem:

Given a configuration $x$, is the state of $A$ equal to $x$ after $|x|$ steps from a blank initial configuration?

in $O(|x|^2)$ time.
Just use an expanded alphabet to overlap the target (input) configuration $x$, the current step evolving configuration and the next step configuration, and an extra bit for a "distributed" counter to stop the evolution after  $|x|$ steps.
E.g.
x = 1 1 0 1 0 0 1  (target configuration)

x = [1 0 0 s ] [100s] [000s] [100s] [000s] [000s] [100s]
     | | | +-step counter
     | | +---next step CA configuration
     | +-----current step CA configuration
     +-------target configuration

The TM sweeps from left to right and apply the CA rules writing the new configuration in the "next step" bits. At the end of a sweep the role of the next/current bits are swapped. Furthermore, at every sweep it deletes an $s$, when no more $s$  it simply compares the current configuration to the target configuration.
There are not known ways to speed-up the simulation of a 1D CA on a k-tape TM, and (probably) such speed-up would imply that the Computation Irreducibility conjecture is false.


Computational complexity of classifying with an already-trained SVM

If you're classifying using SVMs, then the underlying metric space is always a Hilbert space. If your classifier is linear, then the running time of the classification is linear in the dimensionality of the data (or the number of features).

If the classifier (in general) involves some kernel, then the classifier is expressed in terms of the number of support vectors, and the classification is linear in the number of such vectors. Processing each vector takes time proportional to the kernel computation time (which could be constant, or linear in the data dimension, or something else)


Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

I think there is a number of hard problems that become easy for triangle-free graphs; especially those deal directly with triangles such as Partition Into Triangles (Does G have a partition into triangles?). Other less trivial examples include:

Stable Cutset Problem (Does G have an independent set S such that G-S is disconnected?). See:  On stable sutsets in graphs, Discrete Applied Math. 105 (2000) 39-50.
Intersection Graph Basis (Is G the intersection graph of subsets of a k-element ground set?). See: Problem [GT59] in: Garey & Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness.


Randomized and deterministic query complexity of symmetric functions

Ok, I found the answer in this survey: http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf

The sensitivity $s(f)$ of a (nonconstant) symmetric function $f$ is $s(f) \geq \lceil\frac{n+1}{2}\rceil$. However, $D(f) \geq s(f)$ and $R_{1/4}(f) \geq \frac{s(f)}{3}$...

There are other interesting results concerning symmetric functions in this survey (see Section 6.1).


Name of graph partition that balances edges between sets with edges remaining within sets

This is the Min-Disagreements version of the correlation clustering problem (on complete graphs), defined by Bansal, Blum, and Chawla (full version). They give a (huge) constant factor approximation for the problem and prove it's NP-hard. Charikar, Guruswami, and Wirth show the problem is APX-hard, and improve the approximation factor to 4 via region growing. There is a beautiful and simple combinatorial algorithm (a variant of QuickSort), due to Ailon, Charikar, and Newman, that gives a factor 3 approximation. I believe the current best known approximation ratio is due to Chawla, Makarychev, Schramm, and Yaroslavtsev, and is around 2.06.


Non-trivial applications of Bloom filters

Michael Mitzenmacher has a nice survey on Bloom filters where he outlines many applications. Maybe some of these might help.


The computational complexity of matrix multiplication

Classical work of Coppersmith shows that for some $\alpha > 0$, one can multiply an $n \times n^\alpha$ matrix with an $n^\alpha \times n$ matrix in $\tilde{O}(n^2)$ arithmetic operations. This is a crucial ingredient of Ryan Williams's recent celebrated result.

François le Gall recently improved on Coppersmith's work, and his paper has just been accepted to FOCS 2012. In order to understand this work, you will need some knowledge of algebraic complexity theory. Virginia Williams's paper contains some relevant pointers. In particular, Coppersmith's work is completely described in Algebraic Complexity Theory, the book.

A different strand of work concentrates on multiplying matrices approximately. You can check this work by Magen and Zouzias. This is useful for handling really large matrices, say multiplying an $n \times N$ matrix and an $N \times n$ matrix, where $N \gg n$.

The basic approach is to sample the matrices (this corresponds to a randomized dimensionality reduction), and multiplying the much smaller sampled matrices. The trick is to find out when and in what sense this gives a good approximation. In contrast to the previous strand of work which is completely impractical, sampling algorithms are practical and even necessary for handling large amounts of data.


Is there a formal proof that quantum computing is or will be faster than classical computing?

This is a question that is a little bit difficult to unpack if you are not familiar with computational complexity. Like most of the field of computational complexity, the main results are widely believed but conjectural.

The complexity classes typically associated with efficient classical computation are $\mathsf{P}$ (for deterministic algorithms) and $\mathsf{BPP}$ (for randomized). The quantum counterpart of these classes is $\mathsf{BQP}$. All three classes are subsets of $\mathsf{PSPACE}$ (a very powerful class). However, our current methods of proof are not strong enough to definitively show that $\mathsf{P}$ is not the same thing as $\mathsf{PSPACE}$. Thus, we do not know how to formally separate $\mathsf{P}$ from $\mathsf{BQP}$ either — since $\mathsf{P \subseteq BQP \subseteq PSPACE}$, separating those two classes is harder than the already formidable task of separating $\mathsf{P}$ from $\mathsf{PSPACE}$. (If we could prove $\mathsf{P \ne BQP}$, we would immediately obtain a proof that $\mathsf{P \ne PSPACE}$, so proving $\mathsf{P \ne BQP}$ has to be at least as hard as the already-very-hard problem of proving $\mathsf{P \ne PSPACE}$).  For this reason, within the current state of the art, it is difficult to obtain a rigorous mathematical proof showing that quantum computing will be faster than classical computing.

Thus, we usually rely on circumstantial evidence for complexity class separations. Our strongest and most famous evidence is Shor's algorithm that it allows us to factor in $\mathsf{BQP}$.  In contrast, we do not know of any algorithm that can factor in $\mathsf{BPP}$ — and most people believe one doesn't exist; that is part of the reason why we use RSA for encryption, for instance.  Roughly speaking, this implies that it is possible for a quantum computer to factor efficiently, but suggests that it may not be possible for a classical computer to factor efficiently.  For these reasons, Shor's result has suggested to many that $\mathsf{BQP}$ is strictly more powerful than $\mathsf{BPP}$ (and thus also more powerful than $\mathsf{P}$).

I don't know of any serious arguments that $\mathsf{BQP = P}$, except from those people that believe in much bigger complexity class collapses (which are a minority of the community). The most serious arguments I have heard against quantum computing come from stances closer to the physics and argue that $\mathsf{BQP}$ does not correctly capture the nature of quantum computing. These arguments typically say that macroscopic coherent states are impossible to maintain and control (e.g., because there is some yet-unknown fundamental physical roadblock), and thus the operators that $\mathsf{BQP}$ relies on cannot be realized (even in principle) in our world.

If we start to move to other models of computation, then a particularly easy model to work with is quantum query complexity (the classical version that corresponds to it is decision tree complexity). In this model, for total functions we can prove that (for some problems) quantum algorithms can achieve a quadratic speedup, although we can also show that for total functions we cannot do better than a power-6 speed up and believe that quadratic is the best possible. For partial functions, it is a totally different story, and we can prove that exponential speed ups are achievable. Again, these arguments rely on a belief that we have a decent understanding of quantum mechanics and there isn't some magical unknown theoretical barrier to stopping macroscopic quantum states from being controlled.


What are possible implementations of Haskell's type classes and what are their (dis)advantages?

JHC uses a different approach.  The compiler's intermediate language is a dependently typed lambda-calculus where there is no distinction between types and values.  JHC therefore can perform a case analysis on the type parameter of a function and call the correct overloaded function directly.

The JHC website goes into some depth on the implementation, as well as its advantages over the standard dictionary passing implementation.


75 years ago there were no computers around. So one had to explain very carefully the mathematical idea of a computer.

Today everybody knows what a computer is, and is probably carrying one around most of the time. This can be used very successfully in teaching because you can skip the rather outdated idea of a machine with a tape. I mean, who uses a tape? (I know, I know, you feel insulted and Turing was a great man and all that, and I agree with you).

You just walk into the class and ask: so it there anything your iPhones can't compute? This immediately gets you into questions about bounded resources. Then you say: well suppose your machine actually had unlimited memory, is there anything it couldn't compute? And you idealize a bit more and limit attention to number-theoretic functions (because you are not interested in Facebook at the moment). You'll have to explain a bit how computers work (as mentioned in the comments, it's good if the students know a programming language because you can use that instead of describing hardware), but after that you can use all the classical arguments of computability theory to derive results. It doesn't matter that your students' mental picture of a machine is iPhone. In fact, it matters: it makes it easier and more relevant for them to know that their iPhone can't do certain things.


Complexity analysis on a parameterized recurrence relation

First, if $k(n)$ and $T(n)$ are non-negative functions satisfying
$$T(n)=3T(n-1)-T(n-2)+T(n-k(n))+3^{k(n)}\tag{$*$}$$
for all sufficiently large $n$, it is easy to see that $T(n)$ cannot have a finite limit, and in particular, it cannot be decreasing. But if $T(n_0+1)\ge T(n_0)$, then $T(n+1)>T(n)$ for all $n>n_0$ by induction on $n$. Thus, $T$ is eventually increasing.

Second, proving bounds on $T(n)$ is inconvenienced by the presence of a negative term in $(*)$. We can fix this by defining a new function
$$S(n)=\begin{cases}T(\tfrac n2)&\text{$n$ even,}\\T(\tfrac{n+1}2)-T(\tfrac{n-1}2)&\text{$n$ odd,}\end{cases}$$
which (as we just proved) is also eventually nonnegative, and satisfies the recurrence
$$S(n)=\begin{cases}S(n-1)+S(n-2)&\text{$n$ even,}\\
S(n-1)+S(n-2)+S(n-k'(n))+3^{(k'(n)+1)/2}&\text{$n$ odd,}\end{cases}\tag{${*}{*}$}$$
where $k'(n)=2k((n+1)/2)-1$.

This makes it obvious that
$$S(n)\ge S(n-1)+S(n-2),\qquad n\gg0,$$
hence
$$S(n)=\Omega(\phi^n)\quad\text{and}\quad T(n)=\Omega(\phi^{2n}),$$
where $\phi=(1+\sqrt5)/2\approx1{.}618$ is the golden ratio.

I claim that a suitable choice of $k(n)$ gives a matching upper bound. The right choice is to make the two terms involving $k'$ approximately equal; since we are shooting for $S(n)\approx\phi^n$, this means
$$\phi^{n-k'(n)}\approx3^{k'(n)/2},$$
thus
$$k'(n)\sim\beta n,\qquad\beta=\frac{2\log\phi}{2\log\phi+\log3}\approx0{.}467$$
and $k(n)\sim\beta n$ as well. So, let us assume
$$\beta n+c\le k'(n)\le\beta n+d$$
for some constants $c,d$ (with some conditions on $c$ below). I claim that with this setting, any nonnegative solution of $({*}{*})$ satisfies
$$S(n)\le a\phi^n-b\psi^n\tag{${*}{*}{*}$}$$
for some constants $a,b>0$, where
$$\psi=3^{\beta/2}=\phi^{1-\beta}\approx1{.}29,$$
and consequently
$$T(n)=O(\phi^{2n}).$$

Pick $n_0>2$, $a,b>0$ such that $({*}{*})$ holds for $n\ge n_0$, and $({*}{*}{*})$ holds for $n\le n_0$ (there will be one more condition below). We want to show $({*}{*}{*})$ for all $n$ by induction. The induction step goes as follows:
$$\begin{align*}
S(n)&\le a(\phi^{n-1}+\phi^{n-2})-b(\psi^{n-1}+\psi^{n-2})+a\phi^{(1-\beta)n-c}+3^{(\beta n+d+1)/2}\\
&=a\phi^n-b(\psi^{-2}+\psi^{-1})\psi^n+(a\phi^{-c}+3^{(d+1)/2})\psi^n\\
&\le a\phi^n-b\psi^n.
\end{align*}$$
The last step is valid if
$$b(\psi^{-2}+\psi^{-1}-1)\ge a\phi^{-c}+3^{(d+1)/2}.\tag{${*}{*}{*}{*}$}$$
We can arrange this condition by observing that the other requirements on $a,b$ continue to hold if we increase both by the same amount; this will eventually make $({*}{*}{*}{*})$ true if $c$ is sufficiently large so that
$$\psi^{-2}+\psi^{-1}-1>\phi^{-c}.$$


Can it be determined if language L lies in NP?

No.  First, by Rice's Theorem, this is a property of TMs that depends only on the language they compute, so it cannot be computable.

But, more than that, it is known that the index set of $NP$ (that is, the set of TMs that compute languages in $NP$) is $\Sigma^0_3$-complete ($\Sigma^0_3$ in the arithmetic hierarchy of computability, not the polynomial hierarchy).

Questions like this were first investigated by Hajek.  For more, see e.g. this article by Ken Regan.

A few more great nuggets from Hajek's paper:

The index set of $P$ is $\Sigma^0_3$-complete.
$\{i : P^{L(M_i)} \neq NP^{L(M_i)}\}$ is $\Pi^0_2$-complete
There is a total Turing machine (halts on all inputs) $M_i$ such that $P^{L_i} = NP^{L_i}$ but the statement "$P^{L_i} = NP^{L_i}$" is independent (where $L_i = L(M_i)$).  Similarly for relativizations where $P \neq NP$.


How to solve an unification problem on $\mathbb{N}$?

I have concluded that one cannot add both + and × in the λProlog programming language with their arithmetic semantics since the decision problem is undeciable. Because if it was decidable then Hilbert's tenth problem would have a positive answer. See the Wikipedia page for Hilbert's tenth problem.


How do I construct an optimal affix code?

I really don't think that there is a known algorithm to be optimal. In fact, there is a major conjecture about how effective a set of code words can be, see: http://arxiv.org/abs/0709.2598
(the name I knew for affix code is fix-free code). If an algorithm was proved to be optimal, then most probably it would also solve (or disproof) this conjecture as well.


[This is more of a few extended comments than an answer.]

1) If $GI \notin \mathsf{P}$, then there is no fixed-polynomial bound on the time complexity of all $\Pi_{M}$, even for $M$ that only take time, say, $n^3$: If for all time-$n^3$ $M$, $\Pi_{M} \in \mathsf{DTIME}(n^k)$, then the following is a poly-time algorithm for GI. On input $(G, H)$, construct a Turing machine $M_{G}$ with a clock which ensures that $M_{G}$ never runs for more than $n^3$ steps on inputs of size $n$, and such that $M_{G}(1^{|V(G)|}) = G$, and then solve $\Pi_{M_G}(H)$ in time $O(n^k)$.

2) Since for any $M$, $\Pi_{M}$ is no harder than GI, one might think that the best result along the lines of "$\Pi_M$ seems not to be in $\mathsf{P}$" one could hope for is a GI-completeness result. However, it seems unlikely to me that any one $\Pi_M$ would be GI-complete, for at least the following reasons:

All the GI completeness results I know of are for rather large classes of graphs, rather than having a single graph of each size. Even if you drop the efficiency requirement entirely, I do not know of any list of graphs $G_1, G_2, \dotsc$ such that $|V(G_n)| = n$ (or even $poly(n)$) such that testing isomorphism to $G_n$ is GI-complete.
On a related note, most (all?) GI-completeness results are not merely many-one reductions, but have the following form: there is a function $f$ such that given an instance $(G,H)$ of GI, $(f(G), f(H))$ is instance of the other GI-complete problem. (These are just poly-time morphisms of equivalence relations, or what Fortnow and I called "kernel reductions.) We can easily show unconditionally that there is no such reduction from GI to any $\Pi_M$ (even if you modify the definition to allow $M$ to output multiple graphs). Hint: Get a contradiction by showing that any such $f$ must have its image completely contained in $\{G_{M,n}\}_{n \geq 0}$.

3) Even though one could construct $M$ based on a universal TM as suggested in the question, perhaps one can still construct an efficient tester, just not efficiently. That is, maybe for each $M$, $\Pi_{M}$ is in $\mathsf{P/poly}$?


Was the reduction in Shor's algorithm originally discovered by Shor?

I have to admit (surprising as it sounds) that I don't know really the answer. I either discovered or rediscovered this reduction myself.

I discovered the discrete log algorithm first, and the factoring algorithm second, so I knew from discrete log that periodicity was useful.  I knew that factoring was equivalent to finding two unequal numbers with equal squares (mod N) — this is the basis for the quadratic sieve algorithm. I had also seen the reduction of factoring to finding the Euler $\phi$ function, which is quite similar.

While I came up with the reduction of this question to order-finding, it's not hard, so I wouldn't be surprised if there was another paper describing this reduction that predates mine. However, I don't think this could be a widely known "folk result". Even if somebody had discovered it, before quantum computing why would anybody care about reducing factoring to the question of order-finding (provably exponential on a classical computer)?

EDIT: Note that order-finding is provably exponential only in an oracle setting; order finding modulo $N$ is equivalent to factoring $N$, and this had been proved earlier by Heather Woll, as the other answer points out.


Complexity of a certain leaf language with Prime & Composite number of accepting paths.

@Tayfun Pay, you are trying to get us to solve a problem for you!

As it turns out, you only need to apply primality on the count of the number of accepting paths and this count requires polynomial number bits to write down. But the concatenated string on the paths of the NP machine is exponentially long. It is as if the primality algorithm is run on a "padded/unary" version. So it is quite weak and runs within logspace and hence the whole things is within PSPACE.

Now, if you refer to the table (Figure 1) in this paper by [Jenner et al], (or directly to [Hertrampf et all 93]), you will notice that classes within PSPACE (ModP/PH etc) emerge only when the leaf language is a subset of regular languages such as solvable/aperiodic etc. But as is well known, unary PRIMES is not regular (by standard application of pumping lemma).

This much I know. Now to your question. I would suspect PSPACE is the right bound and the proof should not be too difficult, given the techniques from the papers quoted above. If you spend some time thinking, I am sure you will be able to prove the correct bound one way or the other. And especially if these are your first steps into research, I will say, go for it!


Avarage classes for PP (probabilistic polynomial time) and PPT machines running in expected polytime

(This is a more detailed version of my comment on the question.)

As for your question 1, your class is R, the class of decidable problems.  Expected polynomial time is not a useful resource restriction when you allow unbounded error.

To prove that your class contains R, consider a language L∈R.  Let M be a Turing machine for L which halts on every input.  Then we construct a probabilistic Turing machine M′ which runs in expected polynomial time as follows:

Simulate one step of M.  If M accepts, then accept.  If M rejects, then reject.  If M has not halted, continue.
Halt and accept with probability 1/4, halt and reject with probability 1/4, and go to step 1 with probability 1/2.

It should be easy to see that if M halts after t steps, then M′ surely halts before executing step 1 more than t times, and that the probability of error is at most 1/2−1/2t < 1/2.  The expected number of times step 1 is executed is 2(1−1/2t) < 2, and therefore M′ runs in expected constant time.

To prove that your class is contained in R, first note that finite expected running time implies that the probabilistic Turing machine halts with probability 1, and therefore your requirement implies that the machine halts with the correct answer with probability greater than 1/2.  Simulate the probabilistic Turing machine, accumulating the probability of acceptance p and the probability of rejection q.  Because the machine gives the correct answer with probability greater than 1/2, either p or q exceeds 1/2 eventually, and at this point we can stop the simulation and give the correct answer.  (For more details, see this answer by Karolina Sołtys.)


A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut

Let me see if I can clarify this, on a high level. Assume the UG instance is a bipartite graph $G = (V \cup W, E)$, bijections $\{\pi_e\}_{e \in E}$, where $\pi_e\colon \Sigma \to \Sigma$, and $|\Sigma| = m$. You want to construct a new graph $H$ so that if the UG instance is $1-\delta$ satisfiable, then $H$ has a large cut, and if the UG instance is not even $\delta$-satisfiable, then $H$ has only very small cuts.

The graph $H$ contains, for each vertex in $W$, a cloud of $2^m$ points, each labeled by some $x \in \{-1, 1\}^\Sigma$. The intention is that you should be able to interpret a long code encoding of the labels of $W$ as a cut of $H$. Recall that to encode some $\sigma \in \Sigma$ with the long code, you use a boolean function $f\colon \{-1, 1\}^\Sigma \to \{-1, 1\}$; in particular it is the dictator function $f(x) = x_\sigma$. Let's produce a cut $S\cup T$ (i.e. bi-partition of the vertices) from the long code encoding as follows. If $w \in W$ has a label encoded by the boolean function $f$, go to the the cloud of vertices in $H$ corresponding to $w$, and put in $S$ all vertices in the cloud that are labeled by some $x$ for which $f(x) = 1$. All others go to $T$. You can do this backwards to assign boolean functions to all $w \in W$ based on a cut of $H$.

In order for the reduction to work, you need to be able to tell only by looking at the value of a cut $S\cup T$ whether the boolean functions corresponding to the cut are close to a long code encoding of some assignment of labels to $W$ that satisfies a lot of the UG constraints of $G$. So the question is what information do we get from the value of a cut $S \cup T$. Consider any two vertices $a$ with label $x$ in the cloud corresponding to $w$ and $b$ with label $y$ in the cloud corresponding to $w'$ (in the reduction we only look at $w$, $w'$ in different clouds). We said that the cut can be used to derive boolean functions $f_w$ and $f_{w'}$. Now if there is an edge $(a,b)$ in $H$, then $(a, b)$ is cut if and only if $f_w(x) \neq f_{w'}(y)$. Therefore, using only the value of a cut to tell if the boolean functions it induces are "good" is the same as having a test that, given boolean functions $\{f_w\}_{w \in W}$, only asks for what fraction of some specified list of pairs $((w, x), (w', y))$ we have $f_w(x) \neq f_{w'}(y)$.

In other words, whenever Ryan says in the notes "test if $f_w(x) \neq f_{w'}(y)$", what he really means is "in $H$, add an edge between the vertex in the cloud of $w$ labeled by $x$ and the vertex in the cloud of $w'$ labeled by $y$". I.e. for every $v\in V$, every two of its  neighbors $w, w'$, and every $x,y \in \{-1, 1\}^n$, include the edge between the vertex in the cloud of $w$ labeled by $x\circ \pi_{v,w}$ and the vertex in the cloud of $w'$ labeled by $y \circ \pi_{v,w'}$, and assign the edge weight $(({1-\rho})/{2})^d(({1+\rho})/{2})^{n-d}$ where $d$ is the Hamming distance between $x$ and $y$. In this way the value of a cut divided by the total edge weight is exactly equal to the success probability of the test.


Reducing the bandwidth of non-symmetric matrix

The following article discusses various approaches to reducing the bandwidth of unsymmetric matrices.

J.K. Reid, J. A. Scott: Reducing the total bandwidth of a sparse unsymmetric matrix, SIAM Journal on Matrix Analysis and Applications 28(3):805–821.

The technical report version of the article is available here:

J. K. Reid and J. A. Scott, Reducing the total bandwidth of a sparse unsymmetric matrix, Technical Report RAL-TR-2005-001, STFC Rutherford Appleton Laboratory. http://www.numerical.rl.ac.uk/reports/rsRAL2005001.pdf


What functions can read-once branching programs compute?

Barrington's theorem shows that polynomial size, bounded width branching programs compute exactly the languages in $NC^1$. (Specifically, he shows this for branching programs with width at least 5, and a later result shows that 5 is necessary to capture $NC^1$). However, it's easy to see that any function is computable by an exponential size, read-once branching program (just take a decision tree which branches on every variable and outputs the truth-table of the function). If we wanted to focus on, say, polynomial size, read-once branching programs, then nothing is really known in terms of a standard complexity class. The "bounded replication" classes of branching programs (i.e. branching programs with a restriction on the number of times variables appear) don't really offer themselves well to such characterizations. Rather, the complexity classes for which we do have branching program characterizations are natural, given the model (i.e. like $L/poly$) or given via an algebraic approach, like Barrington's theorem or related results (e.g. this paper).

There is an excellent book by Jukna which studies different types of branching programs in depth.


Natural NP-complete problems with high density?

Comment => Answer.

In this paper, Posa shows that for some constant $c$, a graph chosen from the Erdos-Renyi random graph distribution $G(n, c \log n / n)$ has a Hamiltonian cycle with probability approaching $1$ as $n \rightarrow \infty$. If we encode the input to the Hamiltonian Cycle problem as simply a bit-string representing its adjacency matrix, the uniform distribution over $n$-vertex inputs would be exactly the $G(n,1/2)$ distribution (with some irrelevant self loops) -- much more dense than what's needed. Since the existence of a Hamiltonian cycle is a monotone property, the conclusion that the vast majority of graphs have a Hamiltonian cycle follows.

Possible approach to new question

My guess is that you get exactly that for the question of "does there exist a Hamiltonian cycle where $u$ is a neighbor of $v$". I'm not going to fully justify everything, but the reasoning may go roughly as follows.

Claim: For $G \sim G(n,1/2)$ and $u$ and $v$ designated uniformly at random, there is a Hamiltonian path starting at $v$ and ending at $u$ with at least some constant probability.

Take a random Hamiltonian cycle (many of which will exist with overwhelming probability in $G(n,p)$). We show how to transform this, with at least constant probability of success, into a Hamiltonian Path with endpoints $u$ and $v$. For simplicity, we ignore (immediately fail on) the $o(1)$ fraction of cases in which $u$ and $v$ are a distance less than $4$ apart (thus, their neighborhoods are disjoint and not adjacent in the cycle). An intuitive guess is that the two neighbors of $v$ in this cycle should have an edge with constant probability (close to $1/2$), as should $v$ to one or both of the neighbors of $u$ (probability close to $3/4$). If all this happens (probability close to $3/8$), there is a Hamiltonian Path starting at $v$, heading to a neighbor of $u$, continuing along the original Hamiltonian path in the direction away from $u$ (skipping over $v$ once we get to that point), and finally ending at $u$. $\square$

Thus, with some constant probability $c$, there should be a Hamiltonian path starting at $v$ and ending at $u$. The chance that they're adjacent is $1/2$, so with probability $c/2 = \Omega(1)$, there is a Hamiltonian cycle in which $u$ is a neighbor of $v$. Conversely, with probability at least $1/2$ the vertices $u$ and $v$ are not adjacent, so there can't possibly be a Hamiltonian cycle with $u$ and $v$ as neighbors. The conclusion follows.


Number of distinct enclosing circles for N points

An enclosing circle (by your definition) corresponds to a triangular face of the farthest point Delaunay triangulation, which is a triangulation of the convex hull of the input. For points in general position it always has exactly $h-2$ faces where $h$ is the number of convex hull vertices. Therefore the number of enclosing circles is also $h-2$.

They can be generated by constructing the farthest point Delaunay triangulation, in $O(n\log n)$ time.


There is a recent survey

Habib and Paul (2010). A survey of the algorithmic aspects of modular decomposition. Computer Science Review 4(1): 41-59 (2010)

that you should check out.


Resource / book for recent advances in statistical learning theory

I believe you would enjoy Theory of Classification: A Survey of Recent Advances by Boucheron, Bousquet, and Lugosi.  In particular, it starts by building up basic generalization theory via Rademacher complexities, introduces some useful tools (like the contraction principle, whose proof you can track down in Shai&Shai's notes referenced in the answer by Ashwinkumar, but (I believe?) originates in the probability book by Ledoux & Talagrand, which is not free), and applies these to standard classification methods (boosting and support vector machines are discussed, both due to their popularity, and since they are trained via ERM).  This text dates from 2005, so it also has some of the other somewhat recent topics you mentioned, for instance Local Rademacher Complexities, and there's even a tiny plug to chaining.  Lastly, while the manuscript is quite short, it has copious references which I believe you would find extremely useful.

Some of the other topics you mention are old enough to be in "A probabilistic Theory of Pattern Recognition" by Devroye, Györfi, and Lugosi (in particular, it has for more on packing than any other text I know).  Although it lacks some of the newer topics you mention, this is a standard book that everyone I've met in learning theory has carried on their shelves.  Maybe try to locate a table of contents and index for the book, and thumb through it.

Some of the other topics you mention I have not seen treated thoroughly in a book, but they have appeared in a number of course notes.  For instance, if you go to Sham Kakade's page at UPenn, you will find links to two learning theory courses (one was at TTI-C, with Ambuj Tewari), and you will see the topic links match some of the things you have discussed, and have not appeared in my answers or elsewhere.  There are plenty of good courses at various schools; Avrim Blum has excellent, extremely readable notes for his learning theory course (his analysis of winnow is the shortest, cleanest, and most intuitive I've ever seen!).

Some of these are maybe a little too new, though, and you'll have to go to the source material.  But if you are really just trying to pick up a grab bag of techniques, I think the survey up top and the lectures to a couple learning theory classes will serve you a long way.

Also, you sound like you're looking for advanced texts, but I'd also like to plug two introductory texts which people enjoy very much.  One is "an introduction to computational learning theory", by Kearns and (U.) Vazirani, which while old (for instance, boosting is presented only via Robert Schapire's original construction, and the emphasis is on PAC rather than agnostic learning), is presented well and has good intuition.  Personally, I got my basics in Introduction to statistical learning theory, by the same authors as the above survey (but appearing in the order Bousquet, Boucheron, Lugosi?); it has nice exposition and was the first time that generalization theory really started to click for me.