Consequences of $NP=coNP$ and $P\ne NP$?

To me, one of the most basic and surprising consequences of $\mathsf{NP}=\mathsf{coNP}$ is the existence of short proofs for a whole host of problems where it is very difficult to see why they should have short proofs. (This is sort of taking a step back from "What other complexity implications does this collapse have?" to "What are the very basic, down-to-earth reasons this collapse would be surprising?")

For example, if $\mathsf{NP}=\mathsf{coNP}$, then for every graph that is not Hamiltonian, there is a short proof of that fact. Similarly for graphs that are not 3-colorable. Similarly for pairs of graphs that are not isomorphic. Similarly for any propositional tautology.

In a world where $\mathsf{P} \neq \mathsf{NP} = \mathsf{coNP}$, the difficulty in proving propositional tautologies isn't that some short tautologies have long proofs - because in such a world every tautology has a polynomially short proof - but rather that there is some other reason that we are unable to find those proofs efficiently.


Is there a tool for finding Nash equilibria in parametric games?

Is there a tool which solves parametric games?

Not that I am aware of (I am a co-author of GTE and help with Gambit).

The best suggestion I have if you don't find such a tool (and I doubt one exists) is to do a parameter sweep and solve a bunch of individual instantiations and see what the resulting sets of equilibria say about $EQ()$. Gambit is very tightly integrated with python, so you can easily define your game as a python function with the parameters as arguments and solve a set of instances via a parameter sweep.


What's the difference between an invariant and an "inductive" invariant?

I don't know anything about the topic, so let me try to give a very simple example and let's see what others say.

Program:

Initialise: $x \gets 2$.
Iterate: $x \gets 2x - 1$.

Now "$x > 0$" is an invariant. It certainly holds initially and after each iteration.

However, it is not an inductive invariant: merely knowing that $x > 0$ before an iteration is not sufficient to guarantee that $x > 0$ after the iteration. After all, if $x > 0$ is all that we know, then we might have $x = 0.1$ before an iteration and thus $x < 0$ after the iteration.

On the other hand, something like "$x > 1$" is an invariant and also an inductive invariant. It is easy to check that if $x > 1$ before an iteration, then also $x > 1$ after the iteration.


I would write this as a comment, but there was a limitation on the number of characters. So I'll put it here.

The paper title is "Relativized Polynomial Hierarchies Extending Two Levels." When you do not have access to an article, your best bet is to search for books/articles that reference your indented paper. The best place, IMO, is Google Scholar and Google Books.

The Complexity Zoo attributes the proof that "There exist oracles relative to which EXP = NP = ZPP" to this paper. Yet this is incomplete, since other references cite the following papers as well [off-topic: I updated Zoo to cover the new references as well]:

Heller, H. 1984. On relativized polynomial and exponential computations. SIAM J. Comput. 13, 4 (Nov. 1984), 717-725. DOI= http://dx.doi.org/10.1137/0213045
Heller, H. 1986. On relativized exponential and probabilistic complexity classes. Inf. Control 71, 3 (Dec. 1986), 231-243. DOI= http://dx.doi.org/10.1016/S0019-9958(86)80012-2

There's also the following paper:

 Kurtz, S. A. 1985. Sparse sets in NP-P: relativizations. SIAM J. Comput. 14, 1 (Feb. 1985), 113-119. DOI= http://dx.doi.org/10.1137/0214008

cited by several references as having influence on the relativized ZPP = EXP result (see for instance "Comparing Notions of Full Derandomization" by Lance Fortnow).

Specially, while the paper you cited only proves the existence of an oracle $B$ such that

${(\Sigma _1^p)^B} \subset {(\Sigma _2^p)^B} = (\Pi _2^B)$,

The paper #1 above continues by proving:

${(\Sigma _2^p)^B} = (\Pi _2^B) = \mathbf{EXP}^B = \mathbf{NEXP}^B$

and paper #2 above completes it by showing the relations between relatizied EXP and (if I'm not mistaken) RP.

Joining forces, the relativized BPP = NEXP is deduced.

PS: Please provide me with an email address of yours. I want to send you some docs.


Is it in NP to check if the convex hull contains the unit ball?

The problem is NP-hard; see my answer at mathoverflow. Thus there is no polynomial-size certificate that the unit ball is contained in the convex hull of given points unless $\text{NP} = \text{co-NP}$ (if $\text{NP} = \text{co-NP}$ then the polynomial hierarchy collapses).


(An earlier version of this question asked if anyone has shown Portal 2 to be NP-hard.)

Yes, someone has done this.  Portal 2 is at least NP-hard.

My friend created a proof-of-concept map showing that the ability to beat a Portal 2 level implies the ability to solve 3SAT instances:

http://steamcommunity.com/sharedfiles/filedetails/?id=73499175


Minimal encoding of a set (unordered collection of elements)?

What you're looking for is called a "succinct" or "implicit" dictionary. The best solution I know of is Backyard cuckoo hashing, by Arbitman et al from FOCS 2010, which "guarantees constant-time [insert, delete, lookup] operations in the worst case with high probability" while using $B + o(B)$ bits, where $B$ is the lower bound you mention.

If you need updates, I don't know if you'll be able to beat $O\left(\sqrt{B}\right)$ redundancy, given the lower bounds in Brodnik et al.'s "Resizable Arrays in Optimal Time and Space".


Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?

Li and Liu's algorithm is incorrect (see below).  Ueno et al.'s algorithm is correct, and a similar algorithm can be found in Furst et al. 1.  Both algorithms reduce the problem to the polynomial-solvable matroid parity problem [3].

Its reduction from VC ensures the NP-hardness for degree-6 bounded graph!  As VC is already NP-hard on cubic graphs. Speckenmeyer has claimed that his thesis [4] contains the proof of NP-hardness of FVS on planar graphs of maximum degree four, but it's very hard to find (I'll greatly appreciate if who have access to his thesis can send me a copy). Fortunately, a new proof of
the NP-hardness of degree-four bounded graphs can be found in 2:

Remarks on 2:
 - In fact, he proved that the problem is APX-hard, but it is easy to verify
that his reductions are also valid for the proof of NP-hardness of the problem.
 - Its reduction does NOT apply to planar graphs.

Merrick L. Furst, Jonathan L. Gross, and Lyle A. McGeoch, “Finding a maximum-genus graph imbedding,” Journal of the ACM, vol. 35, no. 3, pp. 523–534, 1988. 10.1145/44483.44485
Rizzi, R.: Weakly fundamental cycle bases are hard to find. Algorithmica 53(3), 402-424 (2009) 10.1007/s00453-007-9112-8
László Lovász, “The matroid matching problem,” in Algebraic Methods in Graph Theory, ser. Colloquia Mathematica Societatis János Bolyai, vol. 25, Szeged, Hungary, 1980, pp. 495–517.
Ewald Speckenmeyer, “Untersuchungen zum feedback vertex set problem in ungerichteten graphen,” PhD thesis, Universität-GH Paderborn, Reihe Informatik, Bericht, 1983.


Definition of fractional in theoretical CS

The most common use of 'fractional' is when you're solving an integer program. You relax it by dropping the constraints that the solution be integers, thus yielding a linear program in which the variables can take fractional values (fractional comes from fraction). Later, you can convert the fractional values into integers via a process called 'rounding'.


See the following paper. The two problems are equivalent more or less. To see that, assume that the points are on the unit sphere centered at the origin, and observe that if your NN query $q$ is on the sphere, then the far neighbour for the antipodal point $-q$ is the NN to $q$. There might be a full version written somewhere on the web...

http://dblp.org/rec/conf/soda/GoelIV01

Yep, here is a postscript of the full version:

http://web.stanford.edu/~ashishg/papers/reductions.ps

(Postscript is a file format used in the 20th century to ensure that future generations would not be able to read the content of the file.)


Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?

It is actually possible to make use of random restrictions to prove lower bounds for threshold circuits.

In particular in the paper Size-Depth Tradeoffs for Threshold Circuits, Impagliazzo, Paturi, and Saks use random restrictions to prove a superliner lower bound (on the number of wires) for constant depth threshold circuits computing the parity function.

With regards to proving superpolynomial lower bounds for $\mathsf{TC}^0$
 circuits then yes, the natural proof concept is of relevance since there are constructions of pseudo-random function generators in $\mathsf{TC}^0$.


First, the permanent of an $n\times n$ integer matrix with $O(n)$-bit coefficients is an integer with $O(n^2)$ bits, hence if we know it modulo an integer with $\Omega(n^2)$ bits (with the implied constant depending on the constant in the input bit size), we know it outright.

Your problem with $p$ allowed to have $O(\log n)$ bits is PP-hard under polynomial-time Turing reductions: in order to compute permanent, just compute it modulo every prime below $cn^2$, and use the Chinese remainder theorem to find its value modulo the product of these primes, which is roughly $e^{cn^2}$. By the above, this provides the true value of the permanent for suitable $c$.

There is a serious obstacle to using your problem for primes with $\omega(\log n)$ bits: any reduction to this problem must in particular produce a prime number, and we know of no provably correct deterministic way of computing large primes significantly faster than brute force.

But if you allow randomized reductions, or say, reductions with free access to solutions of the search problem “given $x$, find a prime $p$ such that $x\le p\le2x$”, then you can reduce the number of oracle queries in the reduction of permanent I gave above by using a smaller number of larger primes: if you allow primes $p$ with $m(n)$ bits, you can do away with about $n^2/m(n)$ oracle calls.

For $m(n)=n^\alpha$ with constant $\alpha$, you can use padding to reduce the number of queries to $1$, i.e., to get a randomized many-one reduction: given the input $n\times n$ matrix $M$, find a prime $p$ of at least $n^2$ bits, and let $M'$ be the matrix $M$ padded with diagonal $1$s to dimension $n'\times n'$, where $n'^\alpha\ge\log p$. Then ask for the permanent of $M'$ modulo $p$.


Problems that are easy on unweighted graphs, but hard for weighted graphs

In the world of approximation algorithms there is the capacitated vertex cover problem.
Given $G=(V,E)$ and integer capacities $c(v)$ for each $v \in V$ the goal is to find
a minimum sized vertex cover for $G$ where the number of edges covered by $v$ is at most $c(v)$. This problem has a constant factor approximation in the unweighted case (that is, we want to minimize the size of the vertex cover) while it is $\Omega(\log n)$-hard (unless $P = NP$) in the weighted case (each vertex has a weight $w(v)$ and we want to minimize the weight of the cover).


Long-term data encoding, Phoenix Mars DVD

Ordinarily, I'd think this was out of scope. However, there's an interesting series of papers involving Madhu Sudan, Brendan Juba and Oded Goldreich on what they call universal semantic communication (or how to talk with aliens). The papers are here: one, two, three.


The AKS Primality testing algorithm may be a good candidate, where the best algorithm currently known version of the algorithm has $\tilde{O}(n^6)$ running time.  See Primality testing with Gaussian periods (Lenstra and Pomerance).


This problem is very very difficult.  We could simplify it to make it easier, as follows.

We can add the assumption that the angle sum about every vertex of the polytope $P$ is a rational multiple of $\pi$.  This gets rid of most "polytopes" but there are still many interesting possibilities: for example, the platonic solids.
We can assume that the polytope is not truly three-dimensional, but instead is the "double" of a polygon; this looks a bit like a pillowcase. We can simplify even further and suppose that the polygon has equal and parallel sides; for example a square, as in the game Astroids.

If we make both of these assumptions then there is a large theory.  (Finding an $O(\log(\ell))$ algorithm for the square is a difficult exercise involving the continued fraction expansion of the angle of Mario's path.  To achieve a similar result for the regular octagon is possible but harder.  The solutions for the square and the octagon involve thinking about how to efficiently encode a "cutting sequences for a geodesic on a translation surface".  Most other rational polygons will quickly lead to open problems.)  An initial reference, which includes a further reference to Caroline Series's discussion of the square torus, are these talk slides by Diana Davis.

If we do not assume rationality, but do assume that the polytope is the double of a polygon, then we are discussing the theory of "cutting sequences in irrational billiards".  It seems that essentially nothing is known here; for example see the final sentence of this talk by Corinna Ulcigrai.

If we make neither assumption, well, I can't think of anything in the literature.

Finally - I'll guess that there is an $O(\log(\ell))$ solution to the Super Mario Galaxy problem for the platonic solids.  This is a good problem for a graduate student getting started in rational billiards.  For example, the case of the dodecahedron "should" follow from Diana Davis's thesis.  (But start with the tetrahedron - that will follow from an analysis of cutting sequences for the hexagonal torus.)


What is the smallest class of reductions under which there is a $\mathsf{P}$-complete problem?

It is easy to show that the Circuit Value Problem is complete for $\mathsf{P}$
under $\mathsf{AC^0}$ reductions (see  András's comment below).

For an easier example consider
$$A = \{\langle M,x,y\rangle \mid \text{$M$ accepts $x$ in $|y|$ steps} \}$$

If a class of reductions $C$ contains constant functions, pairing of strings, and functions where the size of their output can bound any polynomial;
then $A$ is complete for $\mathsf{P}$ w.r.t. $C$.


What is the computational complexity of integer multiplication?  Arguably, this question dates back at least to the the 'duplation and mediation' algorithm for integer multiplication described in the Rhind Mathematical Papyrus, which was written circa 1650 BC, but claims to be a copy of a significantly older document.

Admittedly, the Rhind papyrus did not explicitly consider the complexity of is algorithm.  So maybe a better answer is What is the complexity of solving systems of linear equations?  Research into efficient algorithms for solving linear systems dates back at least to Liu Hui's commentary, published in 263 AD, on The Nine Chapters on the Mathematical Art.  Specifically, Liu Hui  compares two variants of what is now recognized as Gaussian elimination, and counts the number of arithmetic operations used by each, with the explicit goal of finding the more efficient method.

Both of these questions are still targets of active research.


Natural Transformations and Parametricity

Unfortunately, the remark of Wadler is too cryptic for me to tell what use he wanted to make of "lax natural transformations".  Here is a guess.  Relation-preservation squares can often be recast as lax commutative squares.  This is how they used to be written in old automata theory papers/books.  See paragraph 1.2 in my Notes on Semigroups.  To do this kind of thing, you have to mix up relations and morphisms and pretend that they are the same.  I am also not sure that it buys you anything new.  It is just uglier notation for saying the same thing as relation-preservation.

Please feel free to explore the connection, but I am not confident that you will find anything new by doing it.


Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs

We can reduce Boolean matrix multiplication to this problem by a three level construction, where the edges from the first level to the second level are determined by the first matrix and the edges from the second level to the third level are determined by the second matrix, and we query with $V'$ equal to the first level.
This reduction for $n \times n$ matrix produces an instance with $|V'| = n$, $A = O(n)$, and $m = O(n^2)$, so an $O(|V'|A + m)$ time algorithm would imply an $O(n^2)$ time algorithm for Boolean matrix multiplication. While I don't think that this has been conjectured to be impossible, it would be a breakthrough result: Best algorithms for Boolean matrix multiplication have the same time complexity as general matrix multiplication, and no "combinatorial" algorithms with $O(n^{3-\epsilon})$ time complexity are known. (see e.g. the intro of [1] for references).
An algorithm with time complexity $O(|V|^\omega \log(|V|))$, where $2 \le \omega < 2.373$ is the matrix multiplication exponent can be given by computing the transitive closure of the DAG with matrix multiplication.
[1] https://acris.aalto.fi/ws/portalfiles/portal/40881045/1.9781611975482.31.pdf


Is it possible to prove that, for a given problem, no optimal greedy algorithms exist?

Yes, there is such work. Allan Borodin with coauthors developed a theory where they formalize the notion of greediness and obtain results which approximation ratios can be reached with them. They introduce a class of priority algorithms, which generalizes greedy algorithms. Their first work on this topic is
the paper "(Incremental) Priority Algorithms".

P.S. The previous paragraph answers on a different question: Is it possible to prove that, for a given problem, no greedy algorithms exist with approximation ratio less than some $1+\epsilon$? What concerns the question I suppose it is assumed there that optimal means exact so the question relates to problems in P (I assume greedy algorithms have polynomial complexity though I guess this is not necessary) which are known to have solution by other methods than greedy ones. And I don't know the answer on this question.

To ivotron: if you didn't mean my first interpretation I will delete this answer.


Paritioning a graph into clique and independent set

Question (1) is easy polynomial time. As Juho has already mentioned in comments, the graphs that can be partitioned into a clique and an independent set are the split graphs. They can be recognized and partitioned in polynomial time, and all valid partitions (if there are more than one) differ by only a single vertex and can also be found in polynomial time (see the Wikipedia article for details). So you simply test whether any of these partitions satisfies your additional constraint.

As for Question (2), it seems you already know that HALF-CLIQUE is NP-complete, so taking an n-vertex hard instance for this problem and adding another n independent vertices produces a hard instance for your problem. That is, the answer is that it is indeed NP-complete.
One could more-or-less mechanically compose this with the hardness reduction for HALF-CLIQUE to get a reduction from a SAT-like problem, but why is that an interesting or useful thing to do?


Natural examples of context-sensitive languages from practice

There are two ways your question can be interpreted: the complexity
theorist view and the application programmer view, which is a bit caricaturing the
situation, but should get my meaning across.

People in complexity theory will mainly wonder whether an actual
problem, practical or theoretical, can be encoded into CSL
recognition.  As noted in the comments of Marzio De Biasi and of user
vzn, a large number of real world problems may be encoded as CSL, as
CSL are recognized by non-deterministic linear bounded automata (LBA), and
conversely . It means that all these algorithms belong to the powerful
class of problems solvable non-deterministically in linear space.

But I strongly doubt that a single one of them is actually solved in
this way for practical purposes. Which brings us to the other view.  I
guess everyone knows that context-free (CF) or regular languages are
used as theoretically defined for various purposes, such as the syntax
of programming languages, or string pattern matching. Since it is also
known that CF and regular languages are context-sensitive languages
(CSL), they do stand as excellent answer to the question.

But since you must have known that, I must conclude that this is not
the answer you were looking for. And the alternative is a more
restrictive question: whether the theoretical formalisation of CSL is
actually used as such for some "real-world" purpose.

Actual use of a formalism in the real world usually entails 2
properties:

the formalism must be perspicuous, and express appropriately the
structural properties of the problem for which it is used.
the formalism must be computationally tractable (in a pragmatic sense).

My impression is that neither is an obvious characteristic of CS
languages. I am no expert on this, and you should not trust me too
much, but there does not seem to be structural organisation that can
be associated to all CSL, like parse-trees can be associated to
strings of CFL, or like regular expressions, even though many closure
properties are known for CSL (which are AFLs). Also, the associated
automaton, the LBA, is not the most obvious computing device to use as it is
non deterministic, and probably too powerful to be simulated
efficiently in specific application. But I insist this is just informal
intuition, not hard facts.

The fact is that many problems, like CF and regular languages, do not
need the full power of CSL and can be better dealt with more
specialized formalism, computationally easier to use, and expressing
more closely the problem at hand.

A typical example is in natural language processing. There are
linguistics structures (such as cross-serial dependency) that are not
naturally expressed with CF languages. Thus scientists have been
defining more powerful syntactics formalisms, such as tree-adjoining
grammar (TAG), Combinatory categorial grammars, ..., and the whole hierarchy
of linear context-free rewriting system (LCFRS), sometimes called
collectively mildly context-sensitive languages.

Another way to venture into context-sensitivity is to use a
context-free backbone and attach to the non-terminals various
attributes that must satisfy equations associated with rules.  This
lead to the attribute grammar formalism in compiler technology, and to
the use of so called feature structures in formalisms like lexical functional
grammar.

In other word, people do venture in the realm of context sensitivity,
but with specialized formalisms that are well adapted for expressing
the problems adressed. Actually, the two form of venturing into
context sensitivity described above can be combined and are combined.

Natural and programming languages are not the only application. For
example TAGs and equivalent formalism have been considered in biology
the explain DNA structures related to specific types of folding of DNA or RNA strands.

So the answer is yes, context-sensitivity is used, both in the
complexity sense and in real applications.  But no, it is not, as far
as I know, by direct use of the CSL formalism.

Note: Marzio De Biasi pointed to a genetics article that claims to
use a context sensitive grammar.  This is probably to be taken
informally as "more powerful than context-free". Indeed, the claim
later concerns "a context-sensitive deterministic grammar", which is
both undefined and significantly restrictive. Later description shows
that it seems actually a minimal extension of CFL, probably less powerful
than the use of TAGs (but I would need more work to see precisely
where it stands: it may just be CF in power).


How is this graphical representation of SAT/CSP instances called?

This has been called the microstructure complement when the edges represent the forbidden partial assignments.  I personally prefer the term clause structure.  The clause structure of a constraint satisfaction problem instance is obtained by applying the direct encoding of the instance to SAT, where each possible value $a$ of variable $v$ is represented by a literal $(v,a)$, the forbidden partial assignments are SAT clauses involving these literals, and a clause $\{(v,a),(v,b)\}$ is added for every variable $v$ and any values $a\ne b$.  (These clauses force a solution to be a function, assigning at most one value to each variable.)

If the edges represent the allowed partial assignments (with non-edges denoting forbidden partial assignments), this is called the microstructure.  This representation doesn't require the extra clauses.  However, one has to be careful of the semantics of missing edges.  One must decide whether only edges of a particular arity are covered by the stipulation that missing edges are forbidden, or whether the microstructure should contain all consistent partial assignments.  The semantics of the clause structure is much more straightforward.

The early work in constraint satisfaction only considered arity 2, when the microstructure and the clause structure are graphs.  But the definition was general (or unspecific) enough that it applies for any arity.

David A. Cohen, A New Class of Binary CSPs for which Arc-Consistency Is a Decision Procedure, CP 2003, 807–811.  doi:10.1007/978-3-540-45193-8_57
Eugene C. Freuder, Eliminating Interchangeable Values in Constraint Satisfaction Problems, AAAI 1991, 227–233.
P. Jégou, Decomposition of Domains Based on the Micro-Structure of Finite Constraint-Satisfaction Problems, AAAI 1993, 731–736.
András Z. Salamon and Peter G. Jeavons, Perfect Constraints Are Tractable, CP 2008, 524–528.  doi:10.1007/978-3-540-85958-1_35


Symbolic Execution is a case of Abstract Interpretation?

I am not aware of a paper concerned with the comparison between symbolic execution and abstract interpretation. Nor do I think one is needed. Reading the original descriptions of these two techniques should be enough.

King, Symbolic Execution and Program Testing, 1976
Cousot, Cousot, Abstract Interpretation: a Unified Lattice Model for Static Analysis of Programs by Construction of Approximation of Fixpoints, 1977

(Conversely, if there would be some unexpected connection, then that would be worth describing. But I very much doubt this is the case.)

The main idea of symbolic execution is that, at an arbitrary point in execution, you can express the values of all variables as functions of the initial values. The main idea of abstract interpretation is that you can systematically explore all executions of a program by a series of over-approximations. (I can hear several AI enthusiasts groaning at the previous approximation.)

Thus, at least in the original formulation, symbolic execution was not concerned with exploring all possible executions. You can see this even in the title: it includes the word ‘testing’. But here's more from Section 8: "For programs with infinite execution trees, the symbolic testing cannot be exhaustive and no absolute proof of correctness can be established."

In contrast, abstract interpretation aims to explore all executions. To do so, it uses several ingredients, one of which is very similar to the main idea of symbolic execution. These ingredients are (1) abstract states, (2) joining and widening (hence, ‘lattice’ in the title).

Abstract states. The concrete state of a program at a particular point in time is basically a snapshot of the memory content (including the program code itself and the program counter). This has a lot of detail, which is hard to track. When you analyze a particular property, you may want to ignore large parts of the concrete state. Or you may want to care only whether a particular variable is negative, zero, or positive, but not care about its exact value. In general, you want to consider an abstract version of the concrete state. For this to work out, you must have a commutativity property: If you take a concrete state, execute a statement, and then abstract the resulting state, you should obtain the same result as if you abstract the initial state, and then execute the same statement but on the abstract state. This commutativity diagram appears in both papers. This is the common idea. Again, abstract interpretation is more general, for it does not dictate how to abstract a state -- it just says there should be a way to do it. In contrast, symbolic execution says that you use (symbolic) expressions that mention the initial values.

Joining and Widening. If program execution reaches a certain statement in two different ways, symbolic execution does not try to merge the two analyzes. That is why the quote above talks about execution trees, rather than dags. But, remember that abstract interpretation wants to cover all executions. Thus, it asks for a way to merge the analyses of two executions at the point where they have the same program counter. (The join could be very dumb ({a} join {b} = {a,b}) such that it amounts to what symbolic execution does.) In general, joining itself is not sufficient to guarantee that you'll eventually finish analyzing all executions. (In particular, the dumb join mentioned earlier won't work.) Consider a program with a loops: "n=input(); for i in range(n): dostuff()". How many times should you go around the loop and keep joining? No fixed answer works. Thus, something else is needed, and that is widening, which can be seen as a heuristic. Suppose you went around the loop 3 times and you learned that "i=0 or i=1 or i=2". Then you say: hmmm, ... let's widen, and you get "i>=0". Again abstract interpretation does not say how to do widening -- it just says what properties widening should have to work out.

(Sorry for this long answer: I really didn't have time to make it shorter.)


Asymmetry in converting Burrows-Wheeler transform to suffix array?

It's possible to build the suffix array of $s$ in linear time from $s$ and $BWT(s)$ in a somewhat easy way. You do need to build a rank-select data structure on $s$ in order to do this.

To see how to do this, look at Ferragina and Manzini's paper "The FM-Index". The LF mapping they describe also essentially computes the suffix array.


Source Coding Theorem: what happen when we go below N*H(x) bits?

It's not clear exactly what your question is. What the textbook is talking about is the strong converse to Shannon's source coding theorem, but rate distortion theory is another part of information theory relevant to this.

The strong converse says that if you try to compress information to fewer bits than the entropy, the probability that all of the information is restored correctly goes to zero as $N$ goes to $\infty$ (the theorem also gives you a bound on this probability).

Rate distortion theory answers the question: I have a signal that I want to compress to a length that is shorter than its entropy. How small an amount of distortion can I introduce into the signal to ensure that I can recover it with high probability? You can use this theory with an arbitrary formula for distortion (and there is a nice formula if the distortion is given by a single-symbol equation).

And of course, if you compress the source to $K$ bits, than you can choose $K/H(X)$ symbols of the original to keep and discard all the others.


Why use joint trees in Graphical Models?

My only background on this subject is a course I took as a grad student, so take my answer with a grain of salt:

The reason that some methods transform the DAG to a tree because some algorithms work on trees but do not work on graphs with cycles. For example, belief propogation is guaranteed to converge on a tree after every node received two messages. On general graphs, on the other hand, no general convergence theorem is known, and we know that convergence occurs only in some special cases. Intuitively, the reason is that on a general graph, a message that goes through a cycle can loop in it indefinitely, each time changing the information stored at the nodes.

Regarding under what circumstances it is recommended to transform the graph into a tree: In the process of transforming the graph into a tree, every node of the new tree is identified with a set of nodes of the original graph. The size of the maximal set with which a node is identified (in the best decomposition) is called the tree-width of the graph. Now, the complexity of belief propagation, as well as other algorithms, is exponential in the tree-width, so you want to transform the graph to a tree only if the tree-width is sufficiently small.

Unfortuantely, it is $NP$-complete to compute the tree-width of a graph exactly, but there are some approximation algorithms. You can read more about it in Shiva Kintali's blog:
http://kintali.wordpress.com/2010/01/28/approximating-treewidth/


Arithmetic complexity of matrix powering

It depends on the relationship between $m$ and $d$. If $m \geq 3$ is fixed, but $d$ is allowed to grow without bound, then the corresponding class of functions is exactly the same as functions with polynomial formula size [Ben-Or and Cleve]. (For $m=2$, it is not as powerful [Allender and Wang]). [Update: As far as I know, this is only true for iterated matrix multiplication $tr(M_1 M_2 \dotsb M_d)$, rather than matrix powering $tr(M^d)$. When $m$ is allowed to grow these two are essentially equivalent, but for fixed $m$, e.g. $m=3$ I don't know if $3 \times 3$ matrix powering is poly-formula-size-complete.]

If $m$ can grow but $d$ is fixed, then this is the same as matrix multiplication, up to $O(\log d) = O(1)$ factors. Since circuits for matrix multiplication can be converted to bilinear circuits with only a factor 2 blow-up in size, circuit and formula size here are essentially the same, and the question boils down to the classic open question of the exponent of matrix multiplication.

If both $m$ and $d$ can grow, then this is equivalent in power to the determinant (corresponding to the Boolean class $\mathsf{DET}$ and the algebraic class $\mathsf{VP}_{ws}$). So here the question becomes about the circuit/formula complexity of the determinant. Both of these are well-known open questions (obviously there are cubic circuits; the best known upper bound on formula size of the determinant is quasi-polynomial).

Most (perhaps even all) nontrivial algorithms for matrix multiplication use cancellations in a crucial way, so I would expect there is a difference between the monotone case and the unrestricted case. Also, note that the equivalence between matrix powering and determinant in the last case is necessarily non-monotone (since matrix powering is a polynomial with all nonnegative coefficients, but the determinant is not).


I guess the best answer to your question is to point out that there have been several "barriers" to proving the P vs NP problem which have been identified and which rule out a number of approaches to a proof.

The three main barriers identified are relativization, natural proofs and algebrization. All of these are described on the P vs NP Wikipedia page under the heading "Results about the difficulty of proof", here.

A more detailed explanation can be found in the papers outlining these barriers referenced on the same Wikipedia page.


"Learning" when test and train distributions don't match

In general, the results are pretty strongly negative --- fairly strong assumptions are needed for something like this to work. As an extreme case, suppose that training and testing distributions have disjoint supports, so that the training sample can be nearly uninformative regarding the test performance.

That having been said, there is a body of research on learning (with) changing target concepts/distributions. Here are four fairly representative samples; once you do a follow-up search of who cites them and who they cite, you'll pretty much span the space:

https://link.springer.com/chapter/10.1007/978-3-642-34106-9_13

https://link.springer.com/article/10.1023/A:1007604202679

https://dl.acm.org/citation.cfm?id=269812

https://link.springer.com/article/10.1023/A:1007666507971

Also potentially relevant: Transfer learning
https://en.wikipedia.org/wiki/Transfer_learning


Inversions are one way to measure "disorder" in a list:

  Let $A[1..n]$ be an array of $n$ distinct numbers.  If $i < j$ and $A[i] < A[j]$ then the pair $(i,j)$ is an inversion of $A$.

However, it's not the only such measure. In general, this concept is formalized in the notion of presortedness - roughly:

  An integer function on a permutation $\sigma$ of a totally ordered set that reflects how much $\sigma$ differs from the total order.

The survey papers by Mannila [1] and Estivill-Castro & Wood [2] might be good places to start.

The question How to measure "sortedness" is related.

[1] Heikki Mannila. "Measures of Presortedness and Optimal Sorting Algorithms." IEEE Transactions on Computers 34.4 (1985): 318-325.

[2] Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.


LP Approximation: Primal relaxation + rounding vs. Dual relaxation. Why is the latter better?

If one uses an ILP formulation and its LP relaxation then clearly it does not hurt to look at the dual. In many cases the dual helps to understand/interpret the lower/upper bound that the relaxations give. This can be exploited algorithmically in a direct fashion, or some times indirectly to provide intuition. Several classical combinatorial optimization results are based on min-max results where duality based analysis/interpretation is very direct and useful.

Making the comment an answer based on Suresh's suggestion.


What are the hardness results known for CSP over $\mathbb{F}_q$?

Here is a summary of what is known about approximability of $k$-CSP over a domain of size $q$:

The best known approximation algorithms for the problem give an $\Omega(q \max(k, \log q)/q^k)$ approximation [MM14 and MNT16].
For $k = \Omega(q)$, there is a matching hardness of $O(kq/q^k)$ by Håstad (UGC-hardness) and Chan (NP-hardness) [Chan13].
For $k$ between $c \log q  /  \log \log q$ and $q$, the best known NP-hardness result is $O(q^2/q^k)$ (follows from [Chan13]).
For $2 < k < c \log q  /  \log \log q$, the best known UGC-hardness is $2^{O(k \log k)} q \, (\log q)^{k/2}/q^k$ by Manurangsi et al. [MNT16].
For $k=2$, the best NP-hardness is $O(\log q/\sqrt{q})$ by Chan [Chan13], the best UGC-hardness is $O(\log q/q^k)$ by Khot et al. [KKMO07]

[Chan13] Siu On Chan. Approximation resistance from pairwise independent subgroups. In Proceedings of the Symposium on Theory of Computing, pages 447–456, 2013.

[KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproxima bility results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007.

[MM14] Konstantin Makarychev and Yury Makarychev. Approximation algorithm for non-Boolean Max $k$-CSP. Theory of Computing, 10(13):341–358, 2014.

[MNT16] Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan. Near-optimal UGC-hardness of approximating Max $k$-CSP$_r$ . In Proceedings of the Workshop on Approximation Algorithms for Combinatorial Optimization Problems (to appear), 2016.


Lower bounds on the period in integer factorization?

If $N=pq$, the period $r$ will always be a divisor of $\phi(N)=\mathrm{lcm}(p-1,q-1)$. If you choose $p-1=2p'$ and $q-1=2q'$ for $p',q'$ prime, then unless you are incredibly lucky, we will have $r \geq p'q' \approx N/4$. I also believe that we can efficiently find primes $p$ with $p=2p'+1$ by choosing candidates randomly and testing them (this is true if the events that $p$ and $p'$ are prime are roughly independent; I don't know whether this has been proven). Thus, by carefully choosing your primes, RSA will still be secure against attacks even with the additional hypothesis about easy factoring.

I suspect random numbers $N$ or random $N=pq$ are extremely unlikely to have $r \in O(\sqrt{N})$, but I don't have a proof of this offhand. The hypothesis $r\in O(\sqrt{N})$ is extremely strong, and I wouldn't be surprised if an efficient factoring algorithm were already known for this case.


Second order logic = PH. Do even higher order logics correspond to anything on complexity side of things?

As you move to higher-order logics, each new order gives you quantification over exponentially larger objects than before, thus you can simulate exponentially longer computations. Other than that, it works pretty much the same as in the second-order case.

More precisely, define the iterated exponential function $2_d^x$ by
$$\begin{align*}2_0^x&=x,\\2_{d+1}^x&=2^{2_d^x}.\end{align*}$$
Let $\Sigma^d_m$ denote in the usual fashion the class of $(d+1)$th order sentences that consist of $m$ alternating blocks of $(d+1)$th order quantifiers starting from existential, followed by a $d$th order formula. (Note that the superscript is off by one from the order. Don’t blame me for this historical peculiarity.)

Then:

For any $d,m\ge1$, the class of all $\Sigma^d_m$-expressible languages is exactly $\Sigma_m\text-\mathrm{TIME}\bigl(2_{d-1}^{\mathrm{poly}(n)}\bigr)$.
Thus, for any $d\ge1$, the languages expressible in $(d+1)$th order logic are exactly those from the $2_{d-1}^x$-time hierarchy: $\bigcup_m\Sigma_m\text-\mathrm{TIME}\bigl(2_{d-1}^{\mathrm{poly}(n)}\bigr)$. For example, second-order logic corresponds to $\mathrm{PH}$, and third-order logic to $\mathrm{EXPH}$.
Thus, the class of languages expressible in all of finite-order logic is $\mathrm{ELEMENTARY}$.

Reference:

[1] Leszek Kołodziejczyk: Truth definitions in finite models, Journal of Symbolic Logic 69 (2004), no. 1, pp. 183–200, doi: 10.2178/jsl/1080938836.


Algorithm for inverting a bijective function.

There have been papers on automatically converting algorithms for bijective functions into algorithms for the inverse function; my own first conference paper was one such. But the class of algorithms that can be inverted in this way is severely limited, as the other answers already suggest.


Create a new table with only one object i.e. object X
Execute all the queries on it.
Discard those which return nothing.
Remaining queries are the queries that match your object X.

This will be faster than searching in a big table.


It turns out that there is a simple answer: $O(k)$-composable $\frac kd$ compressor (in expectation) just returns $k$ random coordinates. The proof is trivial and can be found in Stich et al., "Sparsified SGD with Memory", Section A.1


Actual practical example of a prefix-free Turing-complete language

While not exactly what you want, esoteric languages Jot, Iota and Zot could be good starting points. They are all Turing complete.

In particular Iota language is defined as

syntax            semantic
F --> i           ^x.xSK
F --> *  F  F     [F][F]

So

  an Iota program is either an i, or a * followed by two Iota (sub-)programs

so it satisfies the prefix property. It's extension Zot adds input and output, where the input is the sequence of bits that follow the valid program description. By restricting Zot to programs with empty input you get a language that should satisfy your requirements. (Or alternatively adding just output to Iota.)

There is Haskell implementation of Zot.


Small circuits for circuit evaluation problem

I have learned from talking to Ryan Williams (who deserves the credit for my being able to post this answer) that it is known from Paul and Pippenger that Circuit Eval can be decided by a quasilinear time multitape TM and also that there are reductions from multitape TMs to circuits which give only a quasilinear size blowup. That is, Circuit Eval has circuits of size $(n+s)\log^{O(1)}(n+s)$, as per your formulation.

There is a proof of this here on page 6 (see Theorem 3.1 (Folklore)).


Algorithms for finding clique in bounded-degree graph

Eppstein, Löffler, and Strash modified the Bron-Kerbosch algorithm, obtaining an algorithm that lists all maximal cliques in $O(dn 3^{d/3})$ time, where $d$ is the degeneracy of the graph (note $d \le \Delta$).

The same idea can be extended for the maximum clique problem in $d$-degenerate graphs, and the runtime can be improved to $O^*(2^{d/4})$.


For which graphs is the DFS tree always a path?

This is equivalent to the property that you can construct a Hamiltonian path by greedily taking an arbitrary edge at every vertex. Searching for greedy Hamiltonian path turned up: Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests, Tankusa and Tarsib, doi:10.1016/j.disc.2006.09.031, which points to Randomly Traceable Graphs, Chartrand and Kronk, SIAM J. Appl. Math., 16(4), 696–700, doi:10.1137/0116056 as characterising these graphs as precisely the graphs you mention in the question.


Lower bounds for noncommutative arithmetic circuits with exact division?

To my knowledge, such a reduction is in fact known: Hrubes and Wigderson ITCS 2014 show how division gates can be eliminated from non-commutative circuits and formulas which compute polynomials.

They also provide exponential-size lower bounds for non-commutative formulas with division (not circuits) that compute any entry of the matrix inverse function $X^{-1}$.

Moreover, your main question about lower bounds for non-commutative circuits, is not known (while for formulas it is known as mentioned above), because non-commutative circuits in which each gate computes a polynomial (not a rational function) with division constitutes a class which is at least as strong as non-commutative circuits. But there is no known super-polynomial non-commutative circuit lower bound (see [Hrubes, Yehudayoff and Wigderson STOC 2010] on this).


Is there any result on approximating an arbitrary tree metric by an HST metric?

The distortion of embedding any $n$-point metric in  ultrametric is at most $n-1$, and on the other hand, the distortion of embedding the path metric $P_n$ in ultrametric is at least $n-1$.

Similarly, if you are interested in probabilistic embedding, then by Fakcharoenphol, Rao, and Talwar result mentioned above, any $n$-point metric space probabilistically embeds in ultrametric with distortion $O(\log n)$.
On the other hand, the distortion of probabilistically embedding $P_n$ in ultrametric is $\Omega(\log n)$.


Maximizing difference of a submodular and a modular function

To simplify life, let $\mathcal V = [n] := \{1,2,\ldots,n\}$. For $A \subseteq [n]$, define $h(A):=\sum_{i \in A}c_i$. Note that $h$ defines a modular (i.e additive) set function. Now, suppose there exists $\gamma \in [0, 1]$ such that $f$ is weakly $\gamma$-submodular, i.e such that

$$
\sum_{i \in B\setminus A}f(A \cup \{i\}) - f(A)  \ge \gamma (f(A \cup B) - f(A)),\;\forall A,B \subseteq [n].
$$

Then, greedy maximization produces a subset $A^G$  with $k$ elements such that

$$
f(A^G)-h(A^G) \ge (1-e^{-\gamma})f(A^*)-h(A^*),
$$

where $A^*$ is the $k$-element subset of $[n]$ which maximizes $f(A)-h(A)$.
This is a direct consequence of Theorem 3 of this ICML paper.


Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

Like many complexity-class separations, our best guess is that the answer is that BPP^{HSP} != BQP, but we can only prove this rigorously relative to oracles.  This separation was observed by Scott Aaronson in this blog post
where he observed that the welded-tree speedup of Childs, Cleve, Deotto, Farhi, Gutmann and Spielman was not contained in SZK.

On the other hand, BPP^{HSP} is contained in SZK, at least if the goal is to determine the size of the hidden subgroup.  This includes even the abelian HSP, although I'm not sure how exactly to find the generators of an arbitrary hidden subgroup in SZK.  The reason we can decide the size of the hidden subgroup is that if f:G->S has hidden subgroup H, and we choose g uniformly at random from G, then f(g) is uniformly random over a set of size |G|/|H|. In particular, f(g) has entropy log|G| - log|H|.  And entropy estimation is in SZK.


Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

It is NP-hard for $k=3$.
The reduction is from 3-SAT-(2,2), which means that every clause contains $3$ literals and every literal occurs in at most $2$ clauses.

First of all, for simplicity, let's admit honestly that this problem has not much to do with automata.
Your problem is equivalent to the following:
Given an edge-colored digraph where each color occurs at most $k$ times, is there an $st$ path that uses at most $n$ colors?

For the reduction, the graph starts from $s$ with a path of length $n$, where $n$ is the number of variables of the 3-SAT-(2,2) input.
Each edge of this path is present twice, and all $2n$ edges have a different color.
The colors used when traversing this path correspond to which variables are true.
After this path, there is another path whose length is the number of clauses.
Here every edge is thrice, where the colors correspond to the literals of the clause.
We can get to the end of this path using no extra colors (thus in total $n$) if and only if the 3-SAT-(2,2) input is satisfiable.


A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.
A linear language is a language generated by some linear grammar.
See also:  https://en.wikipedia.org/wiki/Linear_grammar

It is known that the regular languages form a proper subfamily of the linear languages, and that the linear languages form a proper subfamily of the context-free languages.
The language $\{a^kb^kc^nd^n|k,n\ge1\}$ is known to be context-free but not linear.

The text-book "Introduction to Automata Theory, Languages, and Computation" by John E. Hopcroft and Jeffrey D. Ullman (Addison-Wesley, 1979) states a pumping lemma for linear languages:

  Let $L$ be a linear language.
  Then there exists an integer $n$ such that for any word $p\in L$ with $|p|\ge n$, there exists a factorization $p=uvwxy$ with the following properties:

  $uv^iwx^iy \in L$ for all integers $i\in\mathbb{N}$
  $|vx|>0$
  $|uvxy| \le n$.


Relating functors to relational functors with the parametricity translation

$(F, F^R)$ is not necessarily a relational functor. Define $F : \text{Set} \to \text{Set}$ to be the identity functor on sets and functions, but let ${F_!}^R$ send all relations to the trivial relation. Then ${F_{\text{map}}^R}$ trivially holds (along with ${F_{\text{id}}^R}$ and ${F_{\text{comp}}^R}$ which always hold for any $F$, because of the proof-irrelevance of equalities), but $F^R$ does not preserve identity relations.
Going back to the linked question: if a functor is defined internally in a parametric type theory, we don't really care about whether identity extension is derivable: we always get it as part of the "free theorem" package, so every internal $\text{Type} \to \text{Type}$ functor is also a relational functor externally.


There are several possible notions of proof relevance. Let us consider three similar situations:

An element of a sum $\Sigma (x : A) . P(x)$ is a pair $(a, p)$ where $a : A$ and $p$ is a proof of $P(a)$.

An element of $\Sigma (x : A) . \|P(x)\|$, where $\|{-}\|$ is propositional truncation, is a pair $(a, q)$ where $a : A$ and $q$ is an equivalence class of proofs of $P(a)$ (where any two proofs of $P(a)$ are considered equivalent).

In set theory, an element of the subset $\{x \in A \mid \phi(x)\}$, where $\phi(x)$ is a logical formula, is just $a \in A$ such that $\phi(a)$ holds.

The first situation is proof relevant because we get full access to the proof $p$, and in particular we may analyze $p$.
The third situation is proof irrelevant because we get access just to $a \in A$ but have no further information as to why $\phi(a)$ holds, just that it does.
The second situation looks like proof irrelevance, but is actually a form of restricted proof relevance: we do not delete the proof of $P(a)$ but just control its uses with truncation. That is, from $q$ we may extract a representative proof $p$ of $P(a)$, so long as the choice of $p$ is irrelevant.
There is a cruicial difference between the third and the second situation, for having restricted access to $p$ is not at all the same as not having access at all. Here is a concrete example. Given $f : \mathbb{N} \to \mathbb{N}$, define
$$
Z(f) = \Sigma(x : \mathbb{N}) . \Pi (y : \mathbb{N}) . \mathrm{Id}(f(x + y), 0)
$$
An element of $Z(f)$ is a pair $(m, p)$ witnessing the fact that $f(n)$ is zero for all $n \geq m$. Given $f$ with this property, we want to define the sum $S(f) = f(0) + f(1) + f(2) + \cdots$, which of course should be a natural number since eventually the terms are all zero. But proof relevance matters:

We may define $S : (\Sigma (f : \mathbb{N} \to \mathbb{N}) . Z(f)) \to \mathbb{N}$ by
$$S(f, (m, p)) = f(0) + \cdots + f(m)$$

We may define $S : (\Sigma (f : \mathbb{N} \to \mathbb{N}) . \|Z(f)\|) \to \mathbb{N}$ by
$$S(f, |(m,p)|) = f(0) + \cdots + f(m),$$
where $|(m,p)|$ is the truncated witness of $Z(f)$. This is a valid definition because using a different representative $(m',p')$ leads to the same value (as we just end up adding fewer or more zeroes).

Imagining that in type theory we had proof irrelevant subset types
$$\frac{\vdash a : A \qquad \vdash p : P(a)}{\vdash a : \{x : A \mid P(x)\}}$$
we cannot define $S : \{f : \mathbb{N} \to \mathbb{N} \mid Z(f)\} \to \mathbb{N}$ because we have no information that would allow us to limit the number of terms $f(0), f(1), f(2), \ldots$ that need to be added. (There are other things we can do, but that is beside the point here.)

As long as one works in type theory, the only truly proof irrelevant judgements are judgemental equalities. We never define subset types, such as the one above, because that ruins many good properties of type theory (although it would be interesting to investigate this direction).
In the old days type theory did not have propositional truncation or any other form of quotienting, and so one was forced to work in a completely proof relevant way all the time. This is unsatisfactory because it fails to capture properly a great deal of mathematical reasoning. People invented setoids to deal with the problem, and later on introduced propositional truncation (and other forms of quotienting).
You ask wheter 1-categories are "proof relevant". Well, everything in type theory is proof relevant, the only question is how do we deal with having too much proof relevance. Concretely, in a 1-category $\mathcal{C}$, equality of morphisms $f, g : A \to B$ should be "irrelevant" in the sense that it never matter how $f$ and $g$ are equal, only that they are. In HoTT this is expressed by requiring that $\mathrm{Id}(f,g)$ have at most one element, which amounts to
$\mathrm{Hom}_\mathcal{C}(A,B)$ being an h-set.
In setoid-based formulations of category theory, one needs to account for this phenomenon in some other way, or else one is secretly doing something other than 1-category theory. But I never liked the setoid approach (or Bishop's notion of sets, for that matter), so I will let someone else explain why and how it all makes sense.


Is there a systematic method for constructing lambda calculus terms that can distinguish between inputs?

The Böhm-out technique can construct term contexts that can distinguish between terms iff they are distinct in the beta-eta theory (i.e., a term context $C[-]$ so that $C[s]=T$ and $C[t]=F$). See, e.g., http://www.di.unito.it/~dezani/papers/dgp.pdf - it is exceedingly systemtic.

If the terms are closed, as in your example, the context you construct using the Böhm-out technique will be a term M that you apply to the two terms (so $M s = T$, $M t=F$).  Otherwise the term context will include capturing substitutions so that it can work at the sites of the free variables.


I'd say we have no good reason to think BQP is in P/poly.  We do have reasons to think that BQP is not in P/poly, but they're more-or-less identical to our reasons to think that BQP≠BPP.  E.g., if BQP⊂P/poly then Factoring is in P/poly, which is enough to break lots of cryptography according to standard security definitions.

Also, as you correctly point out, there's no quantum analogue of Adleman's trick---indeed, there's no way to "pull the quantumness out of a quantum algorithm," analogous to how one can pull the randomness out of a randomized algorithm.  So I don't think anyone has a guess for what the P/poly advice for simulating a quantum computer should even consist of (any more than they have a guess, say, in the case of NP vs. P/poly).

A final note: my work with Alex Arkhipov (and the independent work of Bremner-Jozsa-Shepherd), can easily be adapted to show that if QUANTUM-SAMPLING is in P/poly (OK, in "BPP-SAMPLING/poly"), then P#P⊂BPPNP/poly, and hence the polynomial hierarchy collapses---in this case, I think, to the fourth level.  At present, though, we don't know how to adapt this sort of result from sampling problems to decision problems.


arithmetic circuits for polynomials (updated)

I assume that you mean $P_n(x)= \sum_{i=0}^n \frac{x^i}{i!}$.

Peter Bürgisser shows that if this problem is hard, then computing the permanent
is hard (http://link.springer.com/article/10.1007/s00037-009-0260-x).
To my best knowledge, your problem is open.


Deciding whether a unary context-sensitive language is regular

Alas, your problem is undecidable. The approach I stumbled upon (which might be overwrought, so anyone who has a more expedient approach should step up!) first uses a diagonal argument to demonstrate that there is a unary CSL $X$ which isn't regular (in contrast to the positive result for unary CFLs), and then reduces from the halting problem for Turing machines by, given a TM $M$, constructing a CSG $G$ which simulates $M$ on a length of tape shorter than the parse string $w$, recognising $X$ if $M$ halts without overstepping its bounds and failing to parse otherwise, so that $G$ successfully parses all $w \in X$ that are sufficiently long iff $M$ halts (so that $L(G)$ differs from $X$ on only finitely many strings and therefore cannot be regular), otherwise $G$ recognizes the empty language (which is clearly regular).

Key to this approach is the observation that CSGs are not merely concerned with grammatical matters such as phrase structure -- indeed, CSG derivation sequences can carry out arbitrary nondeterministic space-bounded computation (indeed there are $\mathbf{PSPACE}$-complete CSLs) before ever getting to the business of aligning with the parse string. This is most easily observed via standard conversions between CSGs and monotonic grammars (which continues to work when restricted to unary alphabets), and the use of simple monotonic productions to simulate Turing machine transitions on derivation strings which represent stages in a computation history. Throughout this answer I'm going to assume the reader can intuit most of the details when a CSG is required to simulate a given computation. (I assume the asker is comfortable with all of this, but I'm going over it for completeness. Nevertheless, feel free to request clarification in the comments.)

Firstly, we need our non-regular unary CSG. (EDIT: so, this was overkill -- non-regular unary CSLs can easily be exhibited e.g. via the pumping lemma on any language which exhibits the most basic of non-regularity. See the comments for examples. In hindsight, using a diagonal argument was like bringing a nuclear warhead to a knife fight. Peruse this construction if you're curious, otherwise skip to the reduction.)

Let $D_1, D_2, ... $ be an enumeration of DFAs over alphabet $\{1\}$, such that the number of states in $D_i$ increases in $i$. We describe a CSG $G_X$ in terms of its behaviour whilst parsing string $1^n \in \{1\}^*$:

Nondeterministically generate a string of $n$ "blank" non-terminals, which we think of as the "tape". One of the blank non-terminals should be a separate "blank + read-write head + start state" non-terminal. If the parse string isn't $1^n$ then this derivation will end up failing. We describe the rest of the process in terms of the deterministic computation simulated by the only possible derivation.
Print on the tape an encoding of $D_i$ followed by the number $i$ in binary, where $i = n - c$ and $c$ is chosen so that we always have enough space on our tape to do what we need to. (This is possible since the space required to encode both $D_i$ and $i$ grows logarithmically in $i$.)
Evaluate $D_i$ on input $1^i$. This doesn't require a representing $D_i$'s tape -- you can just store a single state, which you change according to the transitions of $D_i$ as you decrement $i$.
If $D_i$ rejects $1^i$, overwrite the entire tape with non-terminals which produce $1$. Otherwise fail.

We take $X = L(G_X)$. Clearly $X \ne L(D_i)$ for any $i$, since $1^{i+c} \in X \Leftrightarrow 1^{i+c} \notin L(D_i)$.

The next step is to design a reduction from the halting problem to the asker's problem. (If you skipped the above section, let $X$ be an arbitrary non-regular unary CSL generated by CSG $G_X$.)

Let $M$ be an arbitrary TM. We convert $M$ into a CSG $G$ which behaves as follows on parse string $1^n$:

Generate $n-2$ blank non-terminals, the leftmost one being the separate blank + read-write head non-terminal, and also generate a "boundary" non-terminal on each side. Again, if we generate the wrong number of non-terminals then we fail.
Simulate $M$ in the space between the boundary non-terminals. If $M$ ever shifts onto one of the boundary states, we terminate the simulation and assume that $M$ never halts.
If $M$ halts, behave like $G_X$. If we had to terminate the simulation, then fail.

Note that if $M$ manages to run forever within the boundaries then $G$ can never generate a parse string and so will fail. If $M$ halts, then there is some amount of space $n$ which suffices to contain $M$'s entire computation, hence $G$ parses $1^m$ whenever $m \ge n+2$ and $1^m \in X$, and hence $X$ is the union of $L(G)$ and a finite language, whence $L(G)$ is not regular. On the other hand, if $M$ never halts, then $L(G) = \varnothing$ is clearly regular.

An algorithm for deciding whether $L(G)$ is regular or not would determine whether or not $M$ halts on a blank tape, which is undecidable. It follows that the asker's problem is undecidable.


Are vertex colourings--in a sense--edge colourings?

By analogy with the line graph, I think you are asking the following:

  For every undirected graph $G = (V,E)$, does there exist an undirected graph $G' = (V',E')$ such that each vertex $v \in V$ corresponds to an edge $(v_1,v_2) \in E'$ and the edges corresponding to $u \in V$ and $v \in V$ share at least one endpoint if and only if $(u,v) \in E$?

The answer can be seen to be no. Consider the four-vertex tree $G$ with root $v$ having three children $x,y,z$. In $G'$, we must have four edges: $(v_1,v_2),(x_1,x_2),(y_1,y_2),(z_1,z_2)$. Further, it must be the case that either $v_1$ or $v_2$ is an endpoint of each of the other three edges (i.e., $\left| \{v_1,v_2\} \cap \{x_1,x_2\} \right| \geq 1$, etc). But this means that at least two of the other three edges must share a common endpoint, which violates our requirements since no two of $x,y,z$ are adjacent in the original graph.

I think the same graph will give you a counterexample for the matching question as well.


Closure ordinals for inductive types with function spaces

The answer to your question depends on several things, the most important of which is the size of your function spaces. I'll explain. Define
$$O_0 = nat $$
$$O_{n+1} = \mu X.\ 1+X+(O_n\rightarrow X)$$
As you noted in your answer, each $O_n$ can be considered internally to be the $n$-th regular cardinal of your system. In set theory, this datatype can be represented by an actual ordinal and is appropriately huge.

However, such constructions may be added to some version of type theory, and the question becomes: what ordinal is needed to give a set-theoretic interpretation to this construct? Now if we restrict ourselves to constructive semantics, a natural idea is to try to interpret each type by the set of "realizers" of this type, which is a subset of the set of $\lambda$-terms, or equivalently, the natural numbers $\mathbb{N}$.

In this case, it is easy to show that the ordinal is countable for any $O_n$, but that this ordinal grows very quickly. How quickly? Again, this depends on the amount of freedom you have when trying to build functions. The theory to building such ordinals is described in the theory of Large Countable Ordinals, of which Wikipedia has, surprisingly, a lot to say. In general it is easy to show that the ordinals in question are smaller than the Church-Kleene Ordinal, unless you allow non-constructive means of building functions (say $Beaver(n)$ that computes the busy beaver number for machines with $n$ states).

This isn't saying much though, except that in a constructive theory, you only require constructive ordinals to build interpretations. There is a bit more to say though. First, there is a very nice presentation by Thierry Coquand that details that in the absence of an eliminator for all other types but $nat$, you can build $O_1$ in exactly $\epsilon_0$ steps.

In general there seems to be a correspondence between the logical strength of a type theory, and the size of the largest ordinal that it can represent in this manner. This correspondence is the subject matter of Ordinal Analysis, which has been studied at great length since the late sixties, and is still under study today (with some amazing open questions). Warning though: the subject matter is as technical as it is fascinating.

Hope this helps.


It seems you're trying to PAC learn a language by only seeing positive examples.  This is called "learning from positive examples (only)."  But you also have the power to get some of your own made-up examples labeled: if the oracle were fully truthful, then these would be membership queries, so your model would be known as "learning from positive examples and membership queries."  In this framework, there are some results - for example, tree languages are learnable (not secure).  DFA are not due to crypto hardness results. (Also see this.)

Of course, your setting isn't quite this.  Your membership queries are more limited.  It seems that then the known intractability results would transfer to your setting from the model I described, but the learnability results would leave you with some work to do.  But Mr. X's scheme is secure or not depending on the "pattern" he uses.

Also - it seems like a strange requirement to be able to prove "Mr. X's passwords are inherently unpredictable."  Isn't it usually enough to just be able to generate a new valid password to break such a system? But this seems to be the query to Mr. Y's algorithm itself...


Is unbounded quantum fanout operation experimentally feasible?

There are two way to see your question :

Is unbounded fanout a reasonable approximation for realistic (quantum) circuits ?
Is there a realistic quantum architecture which is effectively equivalent to the quantum circuit with unbounded fan-out ?

Peter Shor essentially suggested the formulation 1. in his comment above, and I’ll let experimentalists answer this question.

The question 2. seems strange, but I bring it forward because its answer is positive : In a 2009 paper (arXiv:0909.4673, paywalled version), Dan Browne, Elham Kashefi, and Simon Perdrix showed that Measurement Based Quantum Computing (MBQC), is equivalent up to a classical side-processing of logarithmic depth, to the quantum circuit model augmented with unbounded fanout gates.

They basically recall that the unbounded parity gate is a Clifford gate and can be therefore be expressed as a measurement pattern of constant depth (arXiv,paywalled PRA) and show that a fanout gate is nothing else than a parity gate “sandwiched” between two layers of Hadamard gates, and can therefore be simulated in constant depth.

Therefore, your question

  Is there any experimental evidence to suggest whether such constant-latency quantum fanout unitary operations are feasible?

is equivalent to

  Is there any experimental evidence to suggest whether Measurent Based Quantum Computing is feasible?

I personally think the answer to the latter question is “yes”, but the opinions on the feasibility of a given quantum computing architecture tend to be subjective...


Proving lower bounds by proving upper bounds

One could turn the question around and ask what lower bounds aren't proved by proving an upper bound. Almost all communication complexity lower bounds (and streaming algorithm lower bound and data structure lower bounds that rely on communication complexity arguments) are proved by showing that a communication protocol can be constructively turned into an encoding scheme, with the length of the encoding depending on the communication complexity of the protocol, and the lower bound for the protocol follows from the fact that you cannot encode all n bit messages using n-1 bits or fewer.

The Razborov-Smolensky circuit lower bounds work by showing how to simulate bounded-depth circuits by low-degree polynomials.

A couple of candidates of lower bounds that are not proved with an upper bound could be the time hierarchy theorem (although, to get the tightest bounds, one needs an efficient universal turing machine, which is a non-trivial algorithmic task) and the proof of AC0 lower bounds using the switching lemma (but the cleanest proof of the switching lemma uses a counting/incompressibility/Kolmogorov-complexity)


Max-weight connected & co-connected subgraph problem

Problem:
  Given a graph $G=(V,E)$ and a weight function $w:V\to\mathbb{R}$, find
  a partition of $V$ into two parts $V_1$ and $V_2$, so that $G[V_1]$ and $G[V_2]$ are connected and so that $w(V_1)$ is maximized.

This problem is NP-hard, as follows easily from the following paper:

  Pim van 't Hof, Daniël Paulusma, Gerhard J. Woeginger:
  Partitioning graphs into connected parts. Theor. Comput. Sci. 410(47-49): 4834-4843 (2009)

The paper shows that the following problem is NP-hard: Given a graph $G=(V,E)$ and two vertices $s,t\in V$, is there a "good" partition of $V$ into two sets $V_1$ and $V_2$, so that $G[V_1]$ and $G[V_2]$ are connected and so that $s,t\in V_1$.

Take such an instance, and make $w(s)=w(t)=1$ and $w(x)=0$ for $x\in V-\{s,t\}$. If there exists a good partition, you can reach $w(V_1)=2$.
If there is no good parition, the best you can get is $w(V_1)=1$.
(This argument shows NP-hardness, and also in-approximability within a
factor of $2-\epsilon$.)


A matrix rank problem over finite fields: Is that a known problem?

When $p^q>3k$, then there is an easy randomized algorithm for this problem (with error probability zero and polynomial expected running time). The algorithm prints "IMPOSSIBLE" if there is $i$ such that $B|w_i$ has more than $n-|w_i|$ rows that consist entirely of zeroes. Otherwise, the algorithm prints "POSSIBLE". It then chooses uniformly random matrices $A$ until it finds one that satisfies the requirements. Below I'll prove that a random matrix $A$ satisfies these requirements with at least constant probability.

If the algorithm printed "IMPOSSIBLE" then it is easy to see that indeed there is no $A$ that satisfies the requirements. Now, consider the case that the algorithm printed "POSSIBLE".

A known result states that a random matrix over a field of size $|F|$ is full-rank with probability $\ge 1-2/|F|$. To see this consider the columns one by one, and compute the size of the linear subspace that they have to "dodge". Work from the last column to the first. You get that the chance that the matrix is full rank is $(1-1/|F|)\cdot(1-1/|F|^2)\cdot\ldots$. In fact, the same proof can be seen to work even if some of the entries are fixed to zero, as long as no entire row is fixed to zero. QED.


Average-case analogue of Small-bias Spaces

Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$.

In contrast, the best worst-case $\varepsilon$-biased spaces on $n$ bits have size $\tilde\Theta(n/\varepsilon^2)$. So you save a factor of about $n/\varepsilon$ by going from worst-case to average-case.

Unfortunately, as you will see, the construction is a bit silly. This explains why this primitive has not been studied.

Let $m=\lceil \log_2(1/\varepsilon) \rceil$. Let $S = \{0,1\}^m \times \{0\}^{n-m} \subset \{0,1\}^n$. That is, a random $x \in S$ consists of $m$ uniformly random bits, followed by $n-m$ zeros.

We have $|S| = 2^m = 2^{\lceil \log_2 (1/\varepsilon) \rceil} \ge 2^{\log_2(1/\varepsilon)} = \frac{1}{\varepsilon}$ and, similarly, $|S|
 < 2^{\log_2(1/\varepsilon)+1} = \frac{2}{\varepsilon}$.

Now let's analyse the average bias of $S$: $$\underset{\alpha \in \{0,1\}^n}{\mathbb{E}}\left[\left|\underset{x \in S}{\mathbb{E}}\left[(-1)^{\langle x , \alpha \rangle}\right]\right|\right] = \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{E}}\left[\left|\underset{x_0 \in \{0,1\}^m}{\mathbb{E}}\left[(-1)^{\langle x_0 , \alpha_0 \rangle}\right]\right|\right] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\le \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{P}} \left[ \alpha_0 = (0,0,\cdots,0) \right] \cdot 1 + \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{P}} \left[ \alpha_0 \ne (0,0,\cdots,0) \right] \cdot 0\\= 2^{-m} + 0 \le \varepsilon~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$$
The first line uses the fact that only the first $m$ bits are relevant and the second line uses the fact that $x_0$ is uniform.

Furthermore, we can show that $|S| \ge 1/\varepsilon$ is necessary -- a nearly matching lower bound. See this answer for the proof idea.


Consider the following reconstruction procedure $P(y)$: given $y$, output $x$ such that $\Pr[X = x \mid Y = y]$ is maximized. The probability that this procedure succeeds is $\max_x \Pr[x \mid Y = y]$. This is also $2^{-H_\infty(X | Y = y)}$, where $H_\infty(X \mid Y = y)$ is the min-entropy of the random variable $X$ conditioned on $Y = y$. We know that $H_\infty(X) \leq H_1(X)$, where $H_1(X)$ is the standard Shannon entropy of the random variable $X$. Now we just have to upper bound $H_\infty(X|Y = y)$ in terms of the mutual information $I(X:Y)$.

Write $I(X:Y) = H(X) - H(X|Y) = H(X) - \mathbb{E}_y[H(X \mid Y = y)]$. Using the inequality mentioned above, $I(X:Y) \leq H(X) - \mathbb{E}_y[H_\infty(X \mid Y = y)]$, or $\mathbb{E}_y[H_\infty(X \mid Y = y)] \leq H(X) - I(X:Y)$.

The probability that the procedure succeeds where $X$ and $Y$ are chosen randomly is $\mathbb{E}_y [2^{-H_\infty(X\mid Y = y)}]$, which by concavity is at least $2^{-\mathbb{E}_y[H_\infty(X \mid Y = y)]}$. Thus the probability the procedure succeeds is at least $2^{I(X:Y) - H(X)}$.

This procedure is optimal: given any randomness procedure $P$, the probability of success is $\mathbb{E}_y [ \sum_{x} \Pr(X = x \mid Y = y) \Pr(P(y) = x) ]$, which is maximized point-wise when $P(y)$ deterministically outputs the most likely $x$.


Counterintuitive results for undergraduates

For a general audience you have to stick to things that they can see. As soon as you start theorizing they'll start up their mobile phones.

Here are some ideas which could be worked out to complete examples:

There is a surface which has only one side.
A curve may fill an entire square.
There are constant width curves other than a circle.
It is possible to color the plane with three colors in such a way that every border point is a tri-border.

If you can rely on a bit of mathematical knowledge, you can do more:

There are as many odd numbers as there are natural numbers.
There is a continuous and nowhere differentiable function.
There is a function $f : \mathbb{R} \to \mathbb{R}$ which is discontinuous at all rational numbers and differentiable at all irrational numbers.
The Banach-Tarski "paradox".

For programmers you can try:

The impossible functionals: there is a program which takes a predicate p : stream → bool, where stream is the datatype of infinite binary sequences, and returns true if and only if p α is true for all streams α (that's uncountably many), and false otherwise.
It is possible to play poker by telephone in a trusted way which prevents cheating.
A group of people can calculate their average salary without anybody finding out any other person's salary.
There is a program which constructs a binary tree $T$ with the following properties:

the tree $T$ is infinite
there is no program that traces an infinite path in $T$


Suppose that there was a polynomial time algorithm $A$ for your promise problem, say with time complexity bounded by $const*|U|^a*m^b$.

Take an arbitrary instance of SET-PACKING (the original variant, not the priomise variant) and run algorithm $A$ on it for $2*const*|U|^a*m^b$ steps.
If $A$ does not terminate within this time bound, the answer must be NO.
If $A$ does terminate, verify whether the output produced by $A$ indeed is a feasible solution.

This would allow you to solve the original SET-PACKING problem in polynomial time.


Is there an efficient program for generating a Sidon sequence?

Consider a prime $p$ and let $g$ be a primitive root mod $p$. The set $ A= \{ (x,g^{x}), x=0,..,p-2\}$ is a Sidon set in $Z_{p-1} \times Z_{p}$. This is an explicit method.

Now, since $Z_{p-1} \times Z_{p}$ is isomorphic to $Z_{p(p-1)}$, then the natural isomorphism $\Phi$ maps $A$ in $\Phi(A)$, which is also a Sidon set in $Z_{p(p-1)}$, which is a Sidon set in $[1,p(p-1)]$.


I don't have a definite answer to your question, but "braid sorting" seems a possible candidate. According to this wikipedia entry we can define it as follows. Let $X$ be a group, and let $H$ denote the set of tuples $(x_1,\ldots,x_n) \in X^n$ such that $x_1 \ldots x_n = 1_X$. If we let $G$ be the braid group $B_n$ generated by the moves $\sigma_i$,  we can define an action of $B_n$ over $H$ by:

  $\sigma_i(x_1,\ldots,x_n) = (x_1,\ldots,x_{i-1},x_{i+1},x_{i+1}^{-1} x_i x_{i+1},\ldots,x_n).$

That is to say, $\sigma_i$ combines the effect of a swap and a conjugation at positions $i$ and $i+1$. It might be possible to solve this problem optimally in polynomial time, which would  answer to your question.


Axioms necessary for theoretical computer science

Yes, the topic has been studied in proof complexity. It is called Bounded Reverse Mathematics. You can find a table containing some reverse mathematics results on page 8 of Cook and Nguyen's book, "Logical Foundations of Proof Complexity",  2010. Some of Steve Cook's previous students have worked on similar topics, e.g. Nguyen's thesis, "Bounded Reverse Mathematics", University of Toronto, 2008.

Alexander Razborov (also other proof complexity theorists) has some results on the weak theories needed to formalize the circuit complexity techniques and prove circuit complexity lowerbounds. He obtains some unprovability results for weak theories, but the theories are considered too weak.

All of these results are provable in $RCA_0$ (Simpson's base theory for Reverse Mathematics), so AFAIK we don't have independence results from strong theories (and in fact such independence results would have strong consequences as Neel has mentioned, see Ben-David's work (and related results) on independence of $\mathbf{P} vs. \mathbf{NP}$ from $PA_1$ where $PA_1$ is an extension of $PA$).


When does BPP with a biased coin equal standard BPP?

1) Yes, but only because of your definition. Take a unary language $L\in EXP\setminus BPP$ (yeah, I know this might be empty, in that case just take something even bigger than $EXP$), that is very sparse in the sense that $n\notin L$ if $n$ is not a tower of $2's$, i.e., of the form $2^{2^{2^\ldots}}$. Define $p=\sum_{n\in L} 1/n$. This $p$ is not $BPP$-computable, but $p$ can be approximated in $P$ up to a small enough additive error that allows the simulation of a $BPP_p$ machine.

Had you defined $BPP$-computable such that you want to approximate $p$ up to an additive error of $1/n$ (instead of $1/2^n$) in polynomial time, things would be different.

Update. The below answer is for the case when the additive error we allow is $2^{-n}$ instead of $2^{-n-1}$.

2) Yes, because here you can forget about the polynomial restriction on the classes and by sampling $2^n$ times you can get the $n$-th bit of $p$ in $BPP_p$.


Are all computational models of quantum computing equivalent?

Now you've clarified your question, I can answer it. Assuming that the seminar was talking about universal quantum computational models (and there are universal computational models for all of these physical systems), then anything in BQP (quantum polynomial time w/ randomness) for one of these models is in BQP for all of these models. They might differ by smaller factors (e.g., since only nearby Josephson junctions can talk to each other, you might have to multiply run times by the diameter of the chip — but it won't be worse than that, and for many problems you can do much better).
There are non-universal models being considered for Rydberg atoms and for photons. The non-universal Rydberg atom models would be very good for simulating certain physical systems. This has been called analog quantum computation; you make the Rydberg atoms interact with the same dynamics as the system you're trying to simulate. Then even though you can't address Rydberg atoms individually, they still behave the same way as an interesting physical system, maybe even one that doesn't quite exist in nature. Systems like this may actually yield the first scientifically interesting results of quantum computation.
For photons, it's very hard to get two photons to interact, which means that there are proposals for building quantum computers that use photons to demonstrate quantum supremacy (i.e., that you can use quantum mechanics to solve a problem that a classical computer can't) without actually being able to use them for a universal quantum computer. It's not clear to me that these proposals will actually work in real life, because as far as I am aware, these proposals have only been proved to work in the case where the noise levels are very low (i.e., the optical components and photodetectors work almost perfectly). There are also proposals for universal quantum computation that use non-interacting photons, but these also have the problem that you need extremely good (but still finite) accuracy for all the optical components and photodetectors in your computer. You can't make universal quantum computation with linear optics,  but you can do it with single photon sources, linear quantum gates, and photodetectors — photodetectors and single photon sources aren't linear in this sense.


Number of permutations which have the same Kendall-Tau distance

This StackOverflow question answers your question. You might also be interested in this OEIS sequence.


What is the name of a function $f$ such that $f(x,y) \in L \iff x\in L \wedge y \in L$?

They are typically called AND-functions. (I'm not joking.) Indeed, this concept has been considered before, and that's what people call them. See, for example, the book by Kobler, Schoning, and Toran on Graph Iso, where they talk about AND- and OR-functions for GI. And, by the way, there is an OR-function for GI (ibid.).

The question of an AND-function for graph automorphism is, I believe, still open :) (as stated in the book above).

Based on your last paragraph, the type of reduction you are talking about can also be generalized to what are called "truth-table" or "tt" reductions. These are non-adaptive Turing reductions (the queries are fixed by the input, but cannot depend on the answer to previous queries). For example, the negation kind of reduction in your last paragraph is a 1-tt reduction (1=number of queries).


How to prove that a circular prop is uninhabited?

You should use False instead of 1>2 in the conclusion of the theorem. Using indirect ways of denoting an impossible proposition is an unnecessary complication. False is the impossible proposition used in the standard library.

In order to prove that ElProp R1 is uninhabited, you need to prove that ElProp R2 is uninhabited, and vice versa. You need induction over ElProp. The inductive property is that there is inhabitant of ElProp R1 or ElProp R2. (You can also work on proving that there is no way to construct an object with C1 or C2, but this is harder because they have different types.)

~(ElProp R1 \/ ElProp R2)

In order to perform induction over ElProp, you need to work in a generic inhabitant of ElProp. It has the type ElProp R for some R : El. What we want to prove is that for such an inhabitant, R cannot be R1 or R2. Here's a way to state this:

Lemma excircular : forall R, (R = R1 \/ R = R2) -> ~ElProp R.

Now let's prove the lemma. First, expand the ~ abbreviation for fun A => A -> False.

unfold not; intros.

We have a hypothesis of type ElProp R, perfect for induction.

induction H0.

First the C1 case; it's an inductive case: the property we're working on works for an ElProp R1 because it works for the parameter (which is of type ElProp R2), putting it all together with some straightforward first-order logic. We have a hypothesis of type R2 = R1 \/ R2 = R2; once we've applied IHElProp, the goal becomes R1 = R1 \/ R1 = R2. I'll leave doing that manually as an exercise. The built-in tactic tauto makes short work of this case, as well as the symmetric case for C2.

tauto.
tauto.

For the C3 case, we need to show that the hypotheses are contradictory. We have a single hypothesis R3 = R1 \/ R3 = R2. Each branch of the disjunction is an impossible equality because the constructors R1, R2 and R3 are distinct.

destruct H. discriminate. discriminate.
Qed.

Here's a shorter way of proving this lemma. All the intelligence we really need to provide is to use induction on the proper hypothesis, Coq can figure out the rest with some general hints.

Lemma excircular : forall R, (R = R1 \/ R = R2) -> ~ElProp R.
Proof.
  unfold not; intros.
  induction H0; firstorder discriminate.
Qed.

Now we can prove the desired goal. Expand out the ~ abbreviation, apply excircular and let Coq fill in the details.

Theorem excircular1 : ~ElProp R1.
Proof.
  intro. eapply excircular; eauto.
Qed.


Automated proving that a program doesn't halt

In contradiction with Gurkenglas' answer, there actually is a community of scientists who work on proving non-termination of programs in various language and formalisms.

An obvious approach would be to check for looping non-termination: for a given program $w$, pick an input $x$ and check to see if the same state is reached twice with the same data.

Non-looping non-termination is obviously more complex, but has been studied, e.g. in Emmes & al Proving Non-Looping Non-Termination Automatically or Endrullis & al Proving Looping and Non-Looping Termination by Finite Automata.


From this we can find the convergents
  of the fraction $j/2^q$ , the convergents
  are possible values of the order $r.$
  Here do we just try all the
  convergents $<N$ and if we don't find $r$
  as one of the convergents do we just
  start again?

You could; the algorithm works fairly fast if you do. If you want to reduce the expected number of quantum steps, you could also do some other tests; for example you should check whether $r$ is a small multiple of one of the convergents. But if you don't find $r$ after these extended tests, you need to start again.

  Also how does the probability for
  possible values $j$ differ? They way I
  see it they should all have the same
  probability but Shor's paper says this
  isn't the case?

I don't know whether I can help you more with this, because you haven't given me enough information for me to tell why you're confused. The probability for each value of $k$ in the fraction $k/r$ is (very nearly) the same. However, depending on exactly where $k/r$ falls between the adjacent values of $j/2^q$ and $(j+1)/2^q$, the probabilities of the specific values of $j$ differ.


A Combinatorial algorithm for trivalent graph isomorphism (except some small subclass)

Even higher-dimensional WL is known not to work in poly time on graphs of degree 4 (Cai-Furer-Immerman). I do not know if higher-dimensional WL might work on graphs of degree 3, but I also don't know of a result ruling this out either. Aside from Babai's general algorithm (which is quasi-polynomial, not polynomial), I do not know another algorithm for degree 3 other than the one you mention.


The question is not very clear, as equisatisfiability of individual clauses does not imply equisatisfiability of the whole formulas.

However, if you mean a construction where each XOR clause is replaced by a set of of Horn clauses—possibly using new variables—so that the satisfying assignments of the original clause are exactly the projections of the satisfying assignments of the new set of clauses, this is impossible. In other words, this would make the XOR clause pp-definable from a set of Horn clauses, but all Boolean relations pp-definable from Horn clauses have the binary conjunction operation as a polymorphism, whereas conjunction is not a polymorphism of any XOR clause in more than two variables.


Hm, its tough even to think of examples of claims about TCS that make it to the popular press.

One thing I have seen occasionally is the claim that factoring is NP-hard, when explaining cryptography. This is related to the less innocuous error of claiming that quantum computers can solve NP hard problems, but restricted to the context of cryptography, this is a relatively mild error. The point is just that we (users of cryptography) seem to believe that there is no efficient algorithm for solving the problem. The particular conjectures we use to justify this assertion are besides the point.


A topological space related to SAT: is it compact?

What you are doing is deriving a topological representation of a Boolean algebra. The study of representations of Boolean algebras goes back at least to Lindenbaum and Tarski who proved (in 1925, I think) that the complete, atomic Boolean algebras are isomorphic to powerset lattices.

There are however, Boolean algebras that are not complete and atomic. For example, the sequence $x_1, x_1 \land x_2, \ldots$, is a descending chain that has no limit in the Boolean algebra defined over formulas. The question of whether arbitrary Boolean algebras, such as the one you mention, also had set-based representations was solved by Marshall Stone, who put forth the maxim "always topologize" (Marshall H. Stone. The representation of Boolean algebras, 1938).

  Stone's Representation Theorem for Boolean Algebras Every Boolean algebra is isomorphic to the lattice of clopen subsets of a topological space.

The main idea is to consider what in your case are the satisfying assignments to a formula. In the general case, you consider  homomorphisms from a Boolean algebra into the two element Boolean algebra (the truth values). The inverse of $\mathit{true}$ gives you the sets of satisfying assignments, or what are called ultrafilters of the Boolean algebra. From these, one can obtain a topology called the spectrum or Stone space of a Boolean algebra. Stone provide the answer to your question too.

  The Stone space of a  Boolean algebra is a compact, totally disconnected Hausdorff space.

There have been several results that extend and generalise Stone's representation in various directions. A natural question is to ask if other families of lattices have such representations. Stone's results also apply to distributive lattices. Topological representations for arbitrary lattices were given by Alasdair Urquhart in 1978. Distributive lattices enjoy greater diversity in structure, compared to Boolean algebras and are of great interest. A different  representation for the distributive case was given by Hilary Priestley in 1970, using the idea of an ordered topological space. Instead of set-based representations, we can find poset-based representations and topologies.

The constructions in these papers have one remarkable property. Stone's construction maps not just Boolean algebras to topological spaces: structural relationships relating Boolean algebras translate into structural properties between the resulting topologies. It is a duality between categories. The entire gamut of such results is called Stone Duality. Informally, dualities give us precise translations between mathematical universes: the combinatorial world of sets, the algebraic world of lattices, the spatial world of topology and the deductive world of logic. Here are a few starting points that may help.

Chapter 11 of Introduction to Lattices and Order, by Davey and Priestley covers Stone's theorem.
Matthew Gwynne's slides  cover the theorem and give a proof of compactness. Matthew (in the comments) also suggests Introduction to Boolean Algebras by Paul Halmos.
In moving from propositional logic to modal logic, the Boolean algebra is extended with a join-preserving operator and topology with an interior.  Jónsson and Tarski's 1952 paper, Boolean Algebras with Operators is extremely readable and consistent with modern notation.
Chapter 5 of Modal Logic by Blackburn, de Rijke and Venema covers Stone's theorem and its extension to Boolean algebras with operators.
Stone Spaces by Peter Johnstone reviews such results for various other kinds of algebras.


Yes - it is known that there exist DFA's of $m$ and $n$ states, respectively, such that the minimal DFA for the concatenation of the corresponding languages has $m*2^n - 2^{n-1}$ states, which matches the known upper bound.

This was first observed by Maslov in 1970, and rediscovered by Yu, Zhuang, and K. Salomaa in their paper, "The state complexities of some basic operations on regular languages", TCS 125 (1994), 315-328.


The Lattice of Flow Diagrams, Dana Scott, Programming Research Group report 03, Oxford University, 1969.

Flow diagram = Control flow graph. Another viewpoint is of  imperative programs as generators of possibly infinite transition systems. The transition systems will form a coalgebra.

Introduction to Coalgebra. Towards Mathematics of States and Observation, Bart Jacobs.

Artem's comment and Neel's answer provide further possibilities. There are many answers to this question depending on what you mean by imperative program and what properties are of interest. Do you care only about syntactic objects or some underlying semantic notion? Even if you only care about, say, control flow graphs, there is a difference between arbitrary flow graphs and those generated by standard structured programming constructs (the latter are reducible). These properties in turn affect the mathematical structure of the space involved.


Finding k shortest Paths with Eppstein's Algorithm

It's been long enough since I wrote that, that by now my interpretation of what's in there is probably not much more informed than any other reader's. Nevertheless:

I believe that the description you're looking for is the last paragraph of the proof of Lemma 5. Basically, some of the edges in P(G) (the "cross edges") correspond to sidetracks in G (that is, edges that diverge from the shortest path tree). The path in G is formed by following the shortest path tree to the starting vertex of the first sidetrack, following the sidetrack edge itself, following the shortest path tree again to the starting vertex of the next sidetrack, etc.


minimum distance r-dominating set on tree

The problem is solved in the paper P. Slater. R-domination in graphs. J. ACM, 23(3):446–450, July 1976. It considers an even more general problem using dynamic programming.


What can be solved with semidefinite programming that can't be solved with linear programming?

A typical problem is MaxCut: output a cut in a graph that (approximately) maximizes the number of edges cut. Goemans and Williamson showed an SDP approximates the value of MaxCut to within a factor at least 0.878. Recently, Chan, Lee, Raghavendra, and Steurer showed that for a natural linear encoding of the MaxCut problem, all polynomial size LPs achieve approximation no better than 0.5.

It's hard to say concisely what kind of problems usually benefit from an SDP. A systematic approach to constructing SDP relaxations is through hierarchies, the most powerful of which is the Lasserre hierarchy: see Rothvoß's survey for a nice introduction. By now there are too many examples of successes of SDPs in optimization to list. Also, Raghavendra showed that one particular SDP gives the best approximation to all MaxCSP problems, if the Unique Games conjecture is true.

Check the books of Gaertner and Matousek, chapters 6 and 13 of Willimson and Shmoys' book, Lovasz's survey.


Solution 1: Find the $\Theta(n^2)$ perpendicular bisectors between pairs of points, and construct the arrangement of these lines. The arrangement has $\Theta(n^4)$ cells, within which the sorted order is constant. So build a point location data structure for the arrangement, and decorate each cell with the sorted order that is to be returned for points within that cell. The sorted orders between adjacent cells differ only in a single transposition, so you can use a persistent data structure to allow the representations of these sorted orders to share space. Total space is $O(n^4)$ and query time is $O(\log n)$.

Solution 2: Choose a random sample of $\Theta(n)$ of these same perpendicular bisectors, construct their arrangement, and partition each arrangement cell by vertical line segments through each crossing of two sampled lines. The resulting partition has $\Theta(n^2)$ cells, each of which with high probability is crossed by $O(n)$ unsampled bisectors. Decorate each cell of the partition by a valid sorted ordering of the points as viewed from some x within the cell. Total space is $O(n^3)$.

Now, to do a query, locate the query point in the partition, look up the ordering stored with the partition cell, and use the Cartesian tree comparison sorting algorithm of Levcopoulos & Petersson (1989) starting with this stored ordering. The time for this step is proportional to $\sum_i O(1+\log k_i)$ where $k_i$ is the number of points that are out-of-order with point $y_i$. But $\sum k_i$ is $O(n)$ (each unsampled bisector causes at most one out-of-order pair of points), so the query time $\sum_i O(1+\log k_i)$ is also $O(n)$.


bounded language complete for NSPACE(log n)?

$\mathsf{L}=\mathsf{NL}$. Yes, there is an analog of Mahaney's Theorem for log-space. If there is a sparse set that is hard for $\mathsf{NL}$ under logspace reductions, then $\mathsf{L}=\mathsf{NL}$:

J.-Y. Cai and D. Sivakumar. Resolution of Hartmanis’ conjecture for NL-hard sparse sets. Theoret. Comp. Sci. 240(2):257–269, 2000.

van Melkebeek extends this to logspace bounded truth-table reductions, which is quite close to the state of the art for extensions of Mahaney's Theorem in the polytime world as well:

D. van Melkebeek. Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets. J. Comput. Syst. Sci. 57(2):213-232, 1998.

(I think the reversed dates are simply because these are the journal publications rather than the corresponding conference publications.)