It is possible ;-)

It would give new circuit lower bounds.  Since you are making a pretty strong assumption this could follow from the seminal work by Impagliazzo, Kabanets, and Wigderson, I haven't checked.

If you use Williams' approach, tightened here, you get a lower bound of $n^{1+\Omega(1)}$ for a function on $n$ bits in the class E$^{NP}$.  (For this approach, a fast co-nondeterministic algorithm for satisfibility is sufficient, as you are postulating.)  Specifically, the latter paper shows that a lower bound for size $s$ follows from a satisfiability algorithm for circuits of size $O(s)$, which we can translate to a 3SAT instance with $O(s)$ variables by Cook-Levin.

It would not directly contradict ETH because that's for deterministic algorithms.


Understanding bounded-diameter decomposition of graphs for PTAS

Actually, the obtained subgraphs may not have bounded diameter, but they still have bounded tree-width. In order to see this, take one such subgraph $H$, and build $H'$ by adding a new vertex $u$ that is connected to each of the top-level vertices of $H$ (remember that $H$ was obtained as $k-1$ consecutive layers of a BFS tree). Then clearly $diam(H') \leq 2k$ since any vertex in $H'$ is at distance less than $k$ of $u$. We then know that $tw(H') = O(diam(H')) = O(k)$. Finally, $H$ is a minor of $H'$ so $tw(H) \leq tw(H')$, hence $tw(H) = O(k)$.


This is technically not in scope for this site, but we're friendly people here :), and your question is relatively well-formed.

It sounds like what you have is a directed graph where the strings are your vertices, and your two tables are storing the "forward edges" (a -> b) and the backward edges (a <- b). The question you're asking is whether there's a way to go from one vertex in this graph to another.

The answer is to do a graph traversal (breadth-first or depth-first) on this graph. Any basic textbook on algorithms (like this one) should help.


If $G$ has an isolated node, the permanent will be equal to 0.

If you know that permanent is 0, it tells extremely little about the number of vertex covers in $G$. You can take any graph $G$ and construct $G'$ by adding an isolated node; the number of vertex covers in $G'$ is exactly 2 times the number of vertex covers in $G$ – which can be virtually anything – while the permanent of $G'$ is 0.

Conversely, if you know the number of vertex covers, you can't tell if the permanent is 0 or not. For example, you can take any graph $G$ with a non-zero permanent and construct two new graphs: $G_1$ is $G$ + a triangle, and $G_2$ is $G$ + two isolated nodes. Both $G_1$ and $G_2$ have exactly 4 times as many vertex covers as $G$. However, $G_1$ will have a non-zero permanent while $G_2$ will have permanent 0.


In Model Checking Recursive Programs with Numeric Data Types, Hague and Lin presented a NEXP-complete language under logspace reduction, called $ \mathtt{SUCCINCT~0\mbox{-}1~KNAPSACK} $ composed by strings

\begin{equation*}
a^m \# a^k \# \theta,
\end{equation*} where $ \theta $ is a Boolean formula with variables $ x_1, \ldots, x_{m+k} $ satisfying that the string $ b \# a_1 \# \cdots \# a_{2^k-1} $ defined based on $ \theta $ (described below) is a member of $ \mathtt{KNAPSCAK} $, i.e. $ \sum_{i=1}^{2^k-1} a_i z_i = b $ for some $ z_1, \ldots,z_{2^k-1} \in \{0,1\} $, where $ b $ and each $ a_i $ are precisely $ 2^m $ bits (leading 0s permitted) binary numbers.

The string $ b \# a_1 \# \cdots \# a_{2^k-1} $ is defined based on $ \theta $ as follows. Let $ (i)_{2,k} $ be the $ k $-bit binary representation of $ i $.

The $ i^{th} $ bit of $ b $ is the value of $ \theta $ by setting $ x_1,\ldots,x_{k+m} $ to the digits of $ 0^k  (i)_{2,m} $ in order.
The $ i^{th} $ bit of $ a_j $ is the value of $ \theta $ by setting $ x_1,\ldots,x_{k+m} $ to the digits of $ (j)_{2,k}  (i)_{2,m} $ in order.

It is not hard to show that $ \mathtt{SUCCINCT~0\mbox{-}1~KNAPSACK} $ can be reduced to NP-Complete $ \mathtt{KNAPSCAK} $ via linearspace reduction.

Moreover, since any language in NEXP is logspace reducible to $ \mathtt{SUCCINCT~0\mbox{-}1~KNAPSACK} $, we can say that any language in NEXP is polyspace reducible to $ \mathtt{KNAPSACK} $. (Here we can combine logspace and linearspace reductions. Since the output string after logspace reduction can have polynomial length, we can use polynomial space overall.)


As you said, it is enough to point out a distribution (this could be any distribution) on which every deterministic algorithm fails. Now, if there is already a distribution given, and you can show that any deterministic algorithm fails on this one, then this provides also a lower bound for randomized algorithms. You can use any distribution in order to apply Yao's principle.


Energy cost of adiabatic quantum computation

Basically, the computation is reversible, so you are not actually using energy. However, the rate at which a computation progresses is generally proportional to the energy gap within the system. In the case of adiabatic quantum computation, the rate at which you can transition between ground states of the initial and final system is determined by the energy gap between the ground state and the low lying excited levels of the system. Thus the energy gap in the Hamiltonian (the total energy operator) is what determines the rate of computation, and so scaling up the energy levels involved allows the computation to be performed more quickly, even though the process does not actually consume the energy.

You might be interested in looking at the Margolus-Levitin theorem, which gives limits for the rate of computation by imposing a lower bound on the time taken for a system to transition to an orthogonal state in terms of the energy gap present in the system. This applies more generally than simply to adiabatic quantum computing.

In general, you tend to get a linear trade-off between energy scale and time. One way to see where this comes from is simply to think about the case of a constant Hamiltonian. In that case, the time evolution operator is $e^{-iHt}$. Clearly multiplying $H$ by some constant $k$ and dividing $t$ by $k$ leads to the same operator, and hence the same evolution of the system. You can do this more generally, with a potentially time dependent Hamiltonian by looking at the Schroedinger equation: $i \hbar \frac{\partial}{\partial t} \mid \Psi \rangle = H \mid \Psi \rangle$. Replacing $H$ with $kH$ and $t$ with $\frac{t}{k}$ we obtain the same equation.


Finding containing sets, within sets of sets

The problem you are trying to solve is called PARTIAL-MATCH: given a database of sets, and a query set, find all sets in the database that contain the query.

The most relevant paper is one by Charikar, Indyk and Panigrahy from ICALP 2002:
New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems

That's on the theoretical side. In practice, many simplifications can be made if one knows something about the sets and the query. For example if $|Q|$ is small, you might be able to get away with an inverted index.


Variable wire weights in DLOGTIME-uniform circuits

After re-reading Barrington et al., it seems that the case of $CC^0$ can be handled by using "group quantifiers", which allow for quantifiers to act over finite groups (i.e. $\mathbb{Z}/m\mathbb{Z}$) directly, while still using a binary representation under the hood so that the original definition of $DLOGTIME$-uniformity can still be used. With group quantifiers, wire weights (or any arbitrary constant-size function) can be simulated with a formula over the bits of the representation. I am still unsure how this might extend to a class like $TC^0$ that operates over an infinite monoid/group (or at least one that grows with $n$), but this answers the core of the question I had.


Semantic vs. Syntactic Complexity Classes

RP involves a promise, that either 0 paths accept or more than half accept, no matter what the input is. For PP, there is no such promise. If more than half the paths accept, then $x \in L$, otherwise, $x \notin L$. (PP can be defined so that the acceptance criteria are $\geq 1/2$ and $< 1/2$ respectively.)

Or in other words, if I give you a probabilistic TM claiming it is a PP machine deciding some language, you can be sure that it decides some language. Clearly, the language it decides is this one: Try input $x$. See if more than 1/2 of the paths accept (or more than 1/2 random strings cause it to accept). If so, $x \in L$. If not, $x \notin L$. So we've defined a language using this TM.

On the other hand, if I give you a probabilistic TM claiming it is a RP machine deciding some language, you can't even be sure that it decides any language. The problem is that when you observe only a few paths accepting, you don't know if $x$ is in $L$ or not. So if I give you a RP machine, you just have to take my word for it. Indeed, checking if this machine defines a language is uncomputable.

As for your second question, for syntactic classes usually there's an obvious complete problem, which is like "Given machine M, decide if it accepts in time T on input x." If you're given a nondeterministic machine, this problem is NP-complete, if it's a PP-machine, then it's PP-complete, etc. The obvious complete problem for semantic classes is undecidable, as I mentioned. So we don't get a complete problem for free for semantic classes. But a semantic class can have a complete problem. For example if P = BPP (as is widely believed), then BPP has a syntactic characterization.

EDIT: Since there's some discussion on how to define semantic and syntactic classes, I'd like to point out that Papadimitriou gives a definition in his book when talking about leaf languages. (See my question about leaf languages for some references.)

He says that syntactic classes are those for which there exists some language that defines the class using the leaf language technique. Semantic classes are those for which all such characterizations require promise problems. This is a rigorous definition, but only works for those languages that have leaf language characterizations.


What is the name of this type of directed graph problem?

As far as I know, the problem is sometimes called "nondecreasing paths", and was studied since the 50s.
See for instance this paper: G. J. Minty. A Variant on the Shortest-Route Problem, Operations Research, 6(6):882–883, 1958.

The version of the problem which asks for the nondecreasing path from $s$ to $t$ with minimum last edge weight is typically referred to as "earliest arrivals" (since the last edge weight is the arrival time in the itinerary application). There's a lot of work in the literature focusing on this version.


Finding the sparsest solution to a system of linear equations

Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$

Take an instance of this problem, $Ax=b$ where $A$ is a $n\times m$ matrix. Let $k=m+1$. Construct a new linear system $\tilde{A}\tilde{x} = \tilde{b}$, where $\tilde{A}$ is a $kn \times (kn+m)$ matrix, $\tilde{x}$ is now a $(kn+m)$ dimensional vector, and $\tilde{b}$ is a $kn$ dimensional vector:

$$\tilde{A} = \begin{bmatrix}
 A & I_n & &  & \\
 & I_n & -I_n & & \\
 & & I_n & -I_n & \\
 & & & \ddots &\ddots  \\
 & & & & I_n & -I_n \\
\end{bmatrix}, \tilde{b} = \begin{bmatrix} b \\ 0 \\ \vdots \\ 0 \end{bmatrix}$$
where $I_n$ is the $n \times n$ identity matrix.

Note that this system is always satisfied by the vector $\tilde{x} = \begin{pmatrix} 0 & b & b & \cdots &  b \end{pmatrix}^T$. In fact, the first $m$ entries of $\tilde{x}$ can be arbitrary, and there is some solution vector with that prefix.

I now claim that $\delta$ fraction of equations of $Ax=b$ are satisfiable iff there exists a sparse solution of $\tilde{A}\tilde{x}=\tilde{b}$ which has at least $\delta nk$ zeros. This is because every satisfied row of $Ax=b$ yields $k$ potential zeros when $x$ is extended to $\tilde{x}$

Thus, if we find the sparsity of the sparsest solution to $\tilde{A}\tilde{x}=\tilde{b}$, we have also maximized $\delta$, by dividing the sparsity by $k$.

Therefore, I believe your problem is NP-hard.


What would be the consequences of factoring being NP-complete?

As well as implying NP=co-NP, it would also imply that BQP contained NP.

It would also seem to imply that hard instances of NP-complete problems were easy to generate.


Is there a concept of "Lego complete"? If not, does it make sense to develop one?

A piece of Lego can be seen as a Polyomino: a plane geometric figure formed by joining one or more equal squares edge to edge.

In Tiling the Plane with a Fixed Number of Polyominoes [2009], Nicolas Ollinger proved that 5 polyominoes are enough to simulate any set of Wang tiles (the shapes of the polyominoes are quite complex and clearly depends on the set of Wang tiles to be simulated). And it is undecidable if a set of Wang tiles can tile the plane (see the link provided by domotorp in his comment).
So it is undecidable given a set of 5 "Lego pieces" (unlimited quantity of each) you can place them (theoretically) on an infinite Lego base and completely cover it (cover the plane).
In other words given a Turing machine, there is a set of 5 lego pieces such that you can cover the whole plane with them if and only if the Turing machine doesn't halt.
But even if you have only 3x1 Lego pieces, and a target object to recreate with them, it can be very hard to find the solution; indeed it is an NP-complete problem as proved in Danièle Beauquier, Maurice Nivat, Eric Rémila, Mike Robson; Tiling Figures of the Plane with Two Bars (1995).


What is the time complexity of increasing the precision of finding matrix eigenvalues?

I do not have a complete answer to your question but here are some thoughts and references. First of all, it is crucial to specify the model of computation and the representation of the input, I expect this post will clarify why. I know of essentially two cases:

the input matrix has coefficients that are algebraic numbers (*): then the eigenvalues are also algebraic numbers and can be determined effectively, one can also determine the multiplicities of the eigenvalues. There exists very good algorithms to get rational approximations of algebraic numbers such a [1] where the bit complexity is $O((b+n)n^2)$ (neglecting some log factors) where $b$ is the number of bits and $n$ is the degree of the polynomial that represents the algebraic number (which in turns depends polynomially on the heigh of the coefficient of the matrix).
the input matrix has coefficients that can be arbitrary real numbers but we can query arbitrary rational approximations of them: this fits into the theory of Computable Analysis and things get complicated. It is known that eigenvalues are uniformly computable (because they are roots of the characteristic polynomial) from the input coefficient [2], the algorithm runs in polynomial time (in the precision), probably using [1] it runs in linear time (if we ignore the cost of computing approximations of the input). However the eigenvectors are not computable nor are multiplicities, unless you known them in advance [3].
your do not care about the representation of numbers and assume all arithmetic operations have a unit cost: this is the BSS model and [4] gives a very precise arithmetic complexity that is logarithmic in the precision (ie $O(\log b)$ where $b$ is the number of bit). But of course this completely neglects the complexity of representing and operating on the numbers and assume that equality is a unit operation (whereas it is uncomputable in general). I personally find this model to be very inadequate to express the complexity of this problem.

Based on your question, I suspect your matrix has rational inputs (which are algebraic numbers of degree 1), thus it would fit in the first case. In this case, I think (but have not checked) that the bit complexity will be linear (maybe with polylogarithmic factors) in the precision, but the constant will depend on the size and numbers in the input matrix (most probably in a polynomial fashion).

(*) algebraic numbers can be represented exactly with a finite number of bits, all arithmetic operations (and more) on algebraic numbers can be performed effectively, however the complexity details on the height of the numbers, thus on field extension in which the coefficients of the input lie.

[1] Optimal and nearly optimal algorithms for approximating polynomial zeros, Pan, 1996

[2] Complexity Theory of Real Functions, Ko

[3] A Computable Spectral Theorem, Brattka and Ziegler

[4] The Complexity of the Matrix Eigenproblem, Pan and Chen


A possible error in the semantic chapter of the ISO standard for the Z specification notation

Firstly, in addition to the Standard from 2002, there is also Technical Corrigendum 1 (TC1) from 2007 which fixes a number of issues.  I don't know of any combined document.  Both documents are available free of charge and links to them are available on the Z notation Wikipedia page.  However, for this particular question, TC1 is not relevant.
Section 15 states that "only sentences of concern here are ones that are already known to be well-formed syntactically and well-typed.".  In a well-typed specification, the semantics in section 15.2.5.1 should not depend on $M$ applied outside its domain.  (Can a well-typed specification be written whose semantics depends on $M$ applied outside its domain?)  I believe this is the thrust of the comment about $\mathit{Model}$ in Table 27 that states "They are applied only to names in their domains, as guaranteed by well-typedness."


What is some important work in fractals?

Mark Braverman has written quite a bit about Julia sets. See, e.g. Computability of Julia Sets


Non-uniform hierarchy theorem for approximating functions

There are some fairly tight results known for tradeoffs between circuit size and theirapproximation, with which one can prove hierarchy theorems for approximating functions. I would start with the following reference:

Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim. Optimal Bounds for the Approximation of Boolean Functions and Some Applications. ECCC, 1995.


The classical reference is "Introduction To Automata Theory, Languages and Computation" (by Hopcroft, Motwani, and Ullman). Some people also recommend the much older "Formal Languages and Their Relation to Automata" (by Hopcroft and Ullman).

I, however, like "Introduction to the Theory of Computation" (by Sipser). It is very well written, and is a relatively new book.


The output number of paths may be $\Omega(2^N/n)$ (choose $s$ arbitrarily and then choose $t$ as the vertex that is the endpoint of the largest number of the $2^N$ walks from $s$) which requires $\Omega(N)$ bits to write down explicitly; this is exponential in the input size. On the other hand, the matrix powering approach has complexity polynomial in the sum of the input and output sizes. So that seems to place it squarely in the class of counting problems that have exponential-sized output and may be solved deterministically in time polynomial in their output size, whatever the notation for that class is (it's some sort of counting analogue for EXP, and definitely not #EXP which is more analogous to NEXP).


Kolmogorov complexity applications in computational complexity

Lance Fortnow has written an article on this topic: Kolmogorov Complexity and Computational Complexity

You should also check out An Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi, the definitive book on the subject.  In particular, chapter 6 "The Incompressibility Method" discusses a number of applications in complexity such as a Kolmogorov complexity proof of Hastad's switching lemma (from Circuit Lower Bounds à la Kolmogorov by Fortnow and Laplante).

And there are applications in communication complexity (e.g. Kolmogorov Complexity and Combinatorial Methods in Communication Complexity by Kaplan and Laplante).


Status quo of category theory and monads in theoretical computer science research?

There have been a number of developments with regards to the use of monads in the theory of computation since Eugenio Moggi's work. I am not able to give a comprehensive account, but here are some points that I am familiar with, others can chime in with their answers.

Specific examples of monads

You do not have to study super-general theory all the time. There are examples of monads that are very interesting and sufficiently complicated to fill an entire undergraduate thesis.

I like very much Dan Piponi's blog where he gives amazing examples of how monads can be used to mix functional programming and mathematics. Search for his work on knots and braid through monads, for example.

Another specific example of mondas worth studying was given by Martin Escardo and Paulo Oliva in the context of selection functionals, see their Selection Functions, Bar Recursion, and Backward Induction, or perhaps to get interested first read What Sequential Games, the Tychonoff Theorem and the Double-Negation Shift have in Common (associated Haskell and Agda files here).

Mathematical background

Monads come from category theory and are much older than Eugenio Moggi. You could study the background theory if you are mathematically inclined. For instance, you could attack Beck's monadicity theorem. A theoretical computer scientist can never know too much math.

Variations on a theme

You could look at something that is not strictly monads.

For instance, Connor McBride and Ross Paterson's Idioms: applicative programming with effects shows how one can generalize monads to something that is practically relevant and insightful.

Or you could look at how comonads are used to model computational effects. Someone should suggest some references for this topic, but a good start might be David Overtone's slides.

Modal type theory

In homotopy type theory, as well as in type theory in general, monads appear in the shape of modal type theory. Recently modal type theory has been considered in homotopy type theory because the truncation operators are examples of modal operators. And then there is cohesive homotopy type theory in which modal operators (which are monads) play an essential role.

Algebraic effects and handlers

[Disclaimer: partially blowing my own horn here.]

A while ago Gordon Plotkin and John Power obserrved that many computational effects are not just any monads, but special monads arising from algebraic theories. This lead to a whole new treatment of computational effects known as algebraic effects. Later Gordon Plotkin and Matija Pretnar introduced handlers and together with algebraic effects they form a very nice theory of computational effects. One advantage of this approach is that algebraic theories can be easily combined while monads cannot.

You could study how exactly algebraic effects relate to monads. You could look at how people implemented algebraic effects and handlers, say in the Eff language or in Haskell as a library. This is more or less current research.


Does your dual have to be of minimum genus? Because it's trivial to find a cellular embedding for any graph: just choose a circular ordering for the edges incident to each vertex, arbitrarily, and then determine the faces of the embedding as the sequences of edges consistent with the chosen orderings.

I like the GEM (graph-encoded map) representation of an embedding from the book Foundations of Topological Graph Theory by Bennington and Little. In this representation, an embedding is represented by a 3-edge-colored 3-regular graph with one vertex for every flag of the embedding (an incident triple of vertex, edge, and face) and one edge for every two flags that differ in only one of the elements of the vertex/edge/face sets that they represent. For instance, the image below from Wikipedia can be interpreted as a GEM of a regular dodecahedron, in which the red cycles represent its faces, the yellow cycles represent its edges, and the blue cycles represent its vertices; the edges may be colored according to the colors of their two incident faces.

Given a circular ordering of the edges of a graph G, its GEM can be found by making a cycle of 2d vertices for each degree-d vertex of G, two for each edge, with the pairs of vertex for each incident edge occurring in the cycle in the chosen circular order, and then for each edge e of G linking the two pairs of GEM edges for the two endpoints of e into a rectangle. If you want an oriented embedding the choice of how to link these four vertices into a rectangle should be consistent with the circular orderings, otherwise it can be arbitrary.

Then, the vertices, edges, and faces of the embedding of G are represented by cycles in the GEM that alternate between two of the three edge colors. The dual of G is represented by a GEM with the same underlying 3-regular graph but with two of its edge colors swapped. And the graph represented by a GEM can be formed by contracting all of its vertex cycles and merging pairs of parallel edges into single edges. So constructing a dual of G (as long as you don't care which dual) can easily be done in linear time.


Zero error randomized communication complexity vs deterministic communication complexity

Indeed, for distjointness of sets of size $\log(n)$ out of $n$ items, it is known that
the $0$-error randomized communication complexity is $\Theta(\log n)$, while the deterministic
complexity is $\Theta(\log^2 n)$.

Recall that there can be at most a quadratic gap since the $0$-error randomized complexity is bounded from below by the non-deterministic and co-non-deterministic complexities.

See: http://mirror.theoryofcomputing.org/articles/v003a011/v003a011.pdf


Truly random number generator: Turing computable?

I am joining the discussion fairly late, but I will try to address several questions that were asked earlier.

First, as observed by Aaron Sterling, it is important to first decide what we mean by "truly random" numbers, and especially if we are looking at things from a computational complexity or computability perspective.

Let me argue however that in complexity theory, people are mainly interested in pseudo-randomness, and pseudo-random generators, i.e. functions from strings to strings such that the distribution of the output sequences cannot be told apart from the uniform distribution by some efficient process (where several meanings of efficient can be considered, e.g. polytime computable, polynomial-size circuits etc). It is a beautiful and very active research area, but I think most people would agree that the objects it studies are not truly random, it is enough that they just look random (hence the term "pseudo").

In computability theory, a concensus has emerged to what should be a good notion of "true randomness", and it is indeed the notion of Martin-Löf randomness which prevailed (other ones have been proposed and are interesting to study but do not bare all the nice properties Martin-Löf randomness has). To simplify matters, we will consider randomness for infinite binary sequences (other objects such as functions from strings to strings can easily be encoded by such sequence).

An infinite binary sequence $\alpha$ is Martin-Löf random if no computable process  (even if we allow this process to be computable in triple exponential time or higher) can detect a randomness flaw.

(1) What do we mean by "randomness flaw"? That part is easy: it is a set of measure 0, i.e. a property that almost all sequences do not have (here we talk about Lebesgue measure i.e. the measure where each bit has a $1/2$ probability to be $0$ independently of all the other bits). An example of such a flaw is "having asymptotically 1/3 of zeroes and 2/3 of ones", which violates the law of large numbers. Another example is "for every n, the first 2n bits of $\alpha$ are perfectly distributed (as many zeroes as ones)". In this case the law of large numbers is satified, but not the central limit theorem. Etc etc.
(2) How can a computable process test that a sequence does not belong to a particular set of measure 0? In other words, what sets of measure 0 can be computably described? This is precisely what Martin-Löf tests are about. A Martin-Löf test is a computable procedure which, given an input k, computably (i.e., via a Turing machine with input $k$) generates a sequence of strings $w_{k,0}$, $w_{k,1}$, ... such that the set $U_k$ of infinite sequences starting by one of those $w_{k,i}$ has measure at most $2^{-k}$ (if you like topology, notice that this is an open set in the product topology for the set of infinite binary sequences). Then the set $G=\bigcap_k U_k$ has measure $0$ and is referred to as Martin-Löf nullset. We can now define Martin-Löf randomness by saying that an infinite binary sequence $\alpha$ is Martin-Löf random if it does not belong to any Martin-Löf nullset.

This definition might seem technical but it is widely accepted as being the right one for several reasons:

it is effective enough, i.e. its definition involves computable processes
it is strong enough: any "almost sure" property you may find in a probability theory textbook (law of large numbers, law of iterated logarithm, etc) can be tested by a Martin-Löf test (although this is sometimes hard to prove)
it has been independently proposed by several people using different definitions (in particular the Levin-Chaitin definition using Kolmogorov complexity); and the fact that they all lead to the same concept is a hint that it should be the right notion (a little bit like the notion of computable function, which can be defined via Turing machines, recursive functions, lambda-calculus, etc.)
the mathematical theory behind it is very nice! see the three excellent books An Introduction to Kolmogorov Complexity and Its Applications (Li and Vitanyi), Algorithmic randomness and complexity (Downey and Hirschfeldt) Computability and Randomness (Nies).

What does a Martin-Löf random sequence look like? Well, take a perfectly balanced coin and start flipping it. At each flip, write a 0 for heads and a 1 for tails. Continue until the end of time. That's what a Martin-Löf sequence looks like :-)

Now back to the initial question: is there a computable way to generate a Martin-Löf random sequence? Intuitively the answer should be NO, because if we can use a computable process to generate a sequence $\alpha$, then we can certainly use a computable process to describe the singleton {$\alpha$}, so $\alpha$ is not random. Formally this is done as follows. Suppose a sequence $\alpha$ is computable. Consider the following Martin-Löf test: for all $k$, just output the prefix $a_k$ of $\alpha$ of length $k$, and nothing else. This has measure at most (in fact, exactly) $2^{-k}$, and the intersection of the sets $U_k$ as in the definition is exactly {${\alpha}$}. QED!!

In fact a Martin-Löf random sequence $\alpha$ is incomputable in a much stronger sense: if some oracle computation with oracle $\beta$ (which itself is an infinite binary sequence) can compute $\alpha$, then for all $n$, $n-O(1)$ bits of $\beta$ are needed to compute the first $n$ bits of $\alpha$ (this is in fact a characterization of Martin-Löf randomness, which unfortunately is rarely stated as is in the literature).

Ok, now the "edit" part of Joseph's question: Is it the case that a TM with access to a pure source of randomness (an oracle?), can compute a function that a classical TM cannot?

From a computability perspective, the answer is "yes and no". If you are given access to a random source as an oracle (where the output is presented as an infinite binary sequence), with probability 1 you will get a Martin-Löf random oracle, and as we saw earlier Martin-Löf random implies non-computable, so it suffices to output the oracle itself! Or if you want a function $f: \mathbb{N} \rightarrow \mathbb{N}$, you can consider the function $f$ which for all $n$ tells you how many zeroes there are among the first $n$ bits of your oracle. If the oracle is Martin-Löf random, this function will be non-computable.

But of course you might argue that this is cheating: indeed, for a different oracle we might get a different function, so there is a non-reproducibility problem. Hence another way to understand your question is the following: is there a function $f$ which is non-computable, but which can be "computed with positive probability", in the sense that there is an Turing machine with access to a random oracle which, with positive probability (over the oracle), computes $f$. The answer is no, due to a theorem of Sacks whose proof is quite simple. Actually it has mainly been answered by Robin Kothari: if the probability for the TM to be correct is greater than 1/2, then one can look for all $n$ at all the possible oracle computations with input $n$ and find the output which gets the "majority vote", i.e. which is produced by a set of oracles of measure more than 1/2 (this can be done effectively). The argument even extend to smaller probabilities: suppose the TM outputs $f$ with probability $\epsilon >0$. By Lebesgue's density theorem, there exists a finite string $\sigma$ such that if we fix the first bits of the oracle to be exactly $\sigma$, and then get the other bits at random, then we compute $f$ with probability at least 0.99. By taking such a $\sigma$, we can apply the above argument again.


Generating Graphs with Trivial Automorphisms

At least the first naive approach one might think of does not work.  The approach I have in mind is to simply generate $G_1$ purely at random.  Since almost all graphs have no symmetries (that is, the proportion of graphs on $n$ vertices with no nontrivial automorphisms approaches 1 as $n \to \infty$), $G_1$ will have no nontrivial automorphisms with high probability, which is what we want.  However, the average-case version of graph isomorphism, where graphs are chosen uniformly at random, can be solved in linear time [BK], so this does not generate a distribution of hard instances.

But a second naive approach has a chance of working: generate a random regular graph (of non-constant degree, since constant-degree graph isomorphism is in P).  This also has no nontrivial automorphisms with high probability [KSV], but the Babai-Kucera result does not apply (as they point out in the paper).  Proving that this is an invulnerable generator obviously requires some assumptions, but one could imagine proving unconditionally that average-case regular graph isomorphism is as hard as worst-case graph isomorphism, though I don't know how likely this is.  (Note that worst-case regular graph isomorphism is equivalent to worst-case (general) graph isomorphism.)

[BK]. Laszlo Babai, Ludik Kucera, Canonical labelling of graphs in linear average time. FOCS 1979, pp.39-46.

[KSV] Jeong Han Kim, Benny Sudakov, and Van H. Vu. On the asymmetry of random regular graphs and random graphs. Random Structures & Algorithms, 21(3-4):216–224, 2002.  Also available here.


As you perhaps already know, a common metric on words is the Cantor metric, which is defined as:

$$
d(l, k) = \left\{ \begin{array}{ll}
                     0 & \mbox{if } l = k \\
                     2^{-n} & \mbox{where } n = \min\{i\in\mathbb{N} \;|\;l_i \not=k_i\}
                  \end{array}
          \right.
$$

Roughly speaking, if a string is a sequence of events, the distance between two strings is $2^{-n}$, where $n$ is the first time they differ.
This can be lifted to a metric on (nonempty) languages by using the Hausdorff metric. (If you allow infinite strings, you also have to ensure that the languages are Cauchy-complete.)

This metric shows up a lot in verification. The first reference to this that I know is Alpern and Schneider 1985, Defining Liveness. (Sorry for the absence of a link, but I couldn't find an online copy.)

Jean-Eric Pin has written a survey article, Profinite Methods in Automata Theory, in which he surveys some more general metrics, and also draws some connections to Stone duality.


Why do theoreticians in CS use multiple-letter variables?

Because we're computer scientists as well as mathematicians, and from the computer science side of the world we've learned the same thing the software engineers have learned about why not to use single-letter names for things other than the most local of variables: longer and more semantically meaningful names are easier to remember and keep straight, easier for others to read and understand, and using them helps avoid certain common errors such as using $k$ to mean three different things in overlapping parts of a paper.

(Actually, I suspect that for the specific case you had in mind, names of complexity classes, this reason is historically inaccurate. But I still believe it's a good reason for using longer names.)


Flow networks: Push flow on either edges but not both!

You can model the constraint of not using two edges (u,v) and (u,w) of capacity one simultaneously in a flow network by introducing a vertex u' and an edge (u',u) with capacity one, but I'm not aware of a more general way to do this without extending the concept of a flow network.

If your idea for reducing the maximum independent set problem to a network flow problem worked, you'd have the basis for a proof that P=NP, which is extremely unlikely.


Do we have any nontrivial uniform circuits?

Here are answers to your last two questions.

(5) Sorting networks are uniform circuits that sort as fast as the best RAM algorithms, but are definitely not just conversions of RAM algorithms (e.g. quicksort). [AKS83,G14]

(4) Yes, for any $s(n)=(1+\varepsilon) \cdot 2^n/n$ with $\varepsilon>0$, but for a silly reason: Every function is computed by a circuit of size $(1+o(1)) \cdot 2^n/n$. (Shannon proved this up to a constant and Lupanov got the optimal constant.) By the time hierarchy theorem, there exists a function $f$ with uniform time complexity between $\Omega(3^n)$ and $O(n \cdot 3^n)$. This gives a counterexample: $f$ has circuits of size $O(2^n/n)$ (which I think are computable in $2^{\mathrm{poly}(n)}$ time) but is not computable in $\tilde{O}(2^n/n)$ time. You should probably ask for $s(n) = o(2^n/n)$.

This is an interesting question; I hope someone can answer (1)-(3).


What are alternatives to the random oracle model for modelling hash functions?

(I am interpreting this question in the following way due to the comments.)  In implementations of cryptographic systems, hash functions like the SHA-256 are defined by a deterministic algorithm mapping arbitrary-length bit-strings to some fixed-length bit-strings.  This situation is troublesome for formal analyses (reductions) of these systems because, when modeled in the straightforward way, there is no obvious way to "assume" some important security notions like collision-resistance for such functions.  To be explicit, we might take a function $H:\{0,1\}^* \rightarrow \{0,1\}^{256}$ and say that

  $H$ is collision-resistant if no probabilistic poly-time algorithm outputs distinct $x,y$ such that $H(x) = H(y)$.

Under this definition, no function $H$ is collision resistant:  By the pigeon-hole principle such an $x,y$ exists, and there also exists a constant-time algorithm that outputs them.  (We're leaving aside the additional problem that "probabilistic poly-time" is ill-defined here.)  Most modifications of the definition, like asking for long $x,y$ or something, are unsatisfying.  Let me mention also that some properties are (I believe) achievable, such as when the $x$ is chosen at random and the adversary has to find a $y$ that collides.

But if one models the hash as a keyed function that take an additional key input, then these security notions can be plausibly assumed to be achieved.  Thus we often give security reductions where a keyed hash function is used and random hash key is chosen in the model.  Though this is incongruous with reality, it seems fine.

To better address this disparity, Rogaway in suggested that we forget about the formal assumption per se and instead focusing on the existence of an explicit reduction to doing something with the hash function.  This is exploiting the fact that we apparently don't "know" of an algorithm finding collisions in SHA-256, even though there is a "constant-time" algorithm for doing exactly that.

By the way, the random oracle model generally addresses a different issue:  sometimes we don't have any way to reduce security to any reasonable property of our (keyed or keyless) hash function, so we instead analyze the system in a model where the evaluations of the hash are replaced by evaluations of a random oracle (which everyone can access).  Incidentally, doing this also makes the hash appear to be keyless and thus superficially "closer to reality," but this is in fact not the case:  Now the entire function has become the key, and indeed an exponentially long key.


Can you point to where this example comes from? It might help.

I think the author is trying to express something a little different than what you're anticipating with this example. For instance, for a C programmer reading this introduction, this example would illustrate that "x 1" in the first line isn't like x(1) in C, it's more like (*x)(1) in C -- you're calling a function there, sure, you even know the type of the function you're calling, but you don't know which function. Certainly you are correct that in this example you can figure out "oh, it's either got to be the function associated with g or the function associated with h." But I posit that when you sort this out in your own head, what you're doing is just executing the program, which is of course the most straightforward way of "statically analyzing" any terminating code!

The example is small; any example that's going to be easy enough for you to straightforwardly understand is, almost by definition, going to be one where your brain can "statically" figure out the answer. The challenge that Control Flow Analysis tries to solve is working over potentially large programs, quickly and precisely.


Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed

There is a 1/2-approximation for Max-Cut with a given size k where k is part of the input. This is in a paper of Ageev and Sviridenko on pipage rounding. See below.
http://www.springerlink.com/content/r37k4302n7m17427/

The above problem is an example of submodular function maximization subject to a matroid base constraint. There has been much recent work on submodular function maximization subject to a variety of constraints.


What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes?

See the following paper by Khanna etal on syntactic vs computational views of approximability. MaxSNP is a syntactic class while APX is a computational class. dl.acm.org/citation.cfm?id=298507

Made comment into answer as per Suresh's request.


The question whether any fixed graph $H$ is an (induced) subgraph of $G$ is a first-order definable property, i.e., for every $H$ there is a formula $\varphi_H$ ($\psi_H$) such that $H$ is an (induced) subgraph of $G$ if and only if $G \models \varphi_H$ ($G\models\psi_H$).

It was formerly known that the model-checking problem is fixed-parameter tractable on classes of graphs that (locally) exclude a minor and on classes of (locally) bounded expansion. Recently, Grohe, Kreutzer and S. anounced an even more general meta-theorem, stating that every first-order property can be decided in almost linear time on nowhere dense classes of graphs.

For your question this implies the following. Let $H$ be a fixed rooted tree. Then it can be decided in linear time whether $H$ is an (induced) subgraph of an input (directed or undirected) graph $G$ if $G$ is planar, or more generally is from a class that excludes a minor or from a class of bounded expansion. The problem can be decided in almost linear time if $G$ is from a class that locally excludes a minor or from a class of locally bounded expansion or most generally, $G$ is from a nowhere dense class of graphs.


Does there exist polytime algorithm for this partitioning problem?

(This is about the problem in which $|\phi(\Phi^{-1}(i))|\geq 2$ instead of $|\Phi(\phi^{-1}(i))|\geq 2$. Read it too fast. On the bright side Dave fixes it in a comment to this message )

What about saying it computes a proper edge coloring of a regular graph ? This problem is NP-Complete, and amounts, given a graph as an entry, to find a partition of its edges into matchings.

Vizing's theorem says that to do that Delta (the maximum degree of your graph) or Delta + 1 colors are required, though deciding which is NP-hard.

In your case, I think setting $N$ to the be number of edges, and setting K to Delta would do the trick. You then want to split your $N$ edges into $K=\Delta$ classes, and N is a multiple of Delta (for example in 3-regular graphs, for which the problem is still NP-hard).

In order to ensure that the answer is a proper edge coloring, one can let $\phi_v$ (for each vertex $v$) be the function equal to $0$ when edge $e\in [N]$ is adjacent to $v$, and 1 otherwise. If each color class has at least two different images for each $\phi_v$, it means that each color class contains a edge incident to each vertex. As the graph is Delta-regular, it also means that all the edges around a vertex have different colors as there are only Delta edges around each vertex, and if a class had two it means one would have none.

If it's true it would mean that finding one answer to your question is hard, and sampling solutions too :-)

Nathann


Determining how n-tuples are sorted as you search them?

The problem can be slightly generalized as follows: given a set $I\subseteq\{1,\dots,n\}$ and a set $S$ of lists of $n$-tuples, find a permutation $\sigma:\{1,\dots,|I|\}\to I$  such that each $l\in S$ is sorted according to the lexicographical preorder that compares the $\sigma(1)^\text{th}$ component, and then the $\sigma(2)^\text{th}$ component, ..., and finally the $\sigma(|I|)^\text{th}$. I'll write $<_\sigma$ for this lexicographical order.

This new problem is easily solvable by recursion: If $I=\emptyset$, there is nothing to do. Otherwise, find some $i_0\in I$ such that in each $l\in S$, the $i_0^\text{th}$ component are increasing (and if no such $i_0$ exist, return an error). Define $I':=I\setminus\{i_0\}$ and $S'$ the set of lists you get by splitting each list every time the $i_0^\text{th}$ component changes. A recursive call with $I'$ and $S'$ gives you a bijection $\sigma':\{1,\dots,|I|-1\}\to I'$ and you can then simply return $\sigma$ defined by $\sigma(1)=i_0$ and $\sigma(i+1)=\sigma'(i)$.

This algorithm runs in $O(|I|^2 |S|)$ (where $|I|$ is the cardinal of $I$, and $|S|=\sum\limits_{l\in S}\operatorname{length}(l)$). In your case and with your notations, that would be $O(n^2N)$.

I think that a slight variation of this algorithm runs in $O(|I||S|+|I|^2)$. It is described at the end of this answers. The proofs concern the $O(|I|^2 |S|)$ version but should be (relatively) easy to adapt to the faster version.

Correctness

The invariant is that if the algorithm returns a permutation $\sigma$, then all the lists in $S$ are sorted according to $<_\sigma$.

The proof is by induction on $I$. The base case is trivial because all lists are sorted according to the neutral element for the lexicographical product: equality.

In the inductive case, take any $l\in S$ we know that the sublists $l_1,\dots,l_r$ that resulted from splitting $l$ at the points where the $i_0^\text{th}$ component changed (i.e. $l=l_1@\dots@l_r$ where $@$ is concatenation, for each $k\in\{1,\dots,r\}$ all elements of $l_k$ have the same $i_0^\text{th}$ component, and for any $k\in\{1,\dots,r-1\}$ $(l_k.last)[i_0]\not=(l_{k+1}.first)[i_0]$. Since we chose $i_0$ such that $l$ (and therefore $l_k$ for all $k\in\{1,\dots,r\}$) is sorted with respect to $<_{i_0}$, this induces that (A) $a<_{i_0}b$ iff $a\in l_k$ and $b\in l_{k'}$ with $k<k'$. By the induction hypothesis, (B) each $l_k$ is sorted with respect to $<_{\sigma'}$.

Let $a,b\in l$ such that $a$ appears before $b$ in $l$.

If $a$ and $b$ appear in the same $l_k$, by (A), $a~_{i_0}b$ (i.e. $a\le_{i_0}b$ and $b\le_{i_0}a$) and $a$ appears before $b$ in $l_k$ so that by (B) $a<_{\sigma'}b$. We therefore have $a(<_{i_0}\times_\text{lex}<_{\sigma'})b$.
If $a$ appears in $l_k$ and $b$ appears in $l_{k'}$ with $k<k'$, then by (A), $a<_{i_0}b$ and we therefore have $a(<_{i_0}\times_\text{lex}<_{\sigma'})b$.

We are done because $(<_{i_0}\times_\text{lex}<_{\sigma'})={<_\sigma}$.

Completeness

The invariant is that if every $l\in S$ is sorted according to some $<_{\tilde\sigma}$ then the algorithm will return $\sigma$ such that for any $l\in S$ and $a,b\in l$, $a<_\sigma b$ iff $a<_{\tilde\sigma}b$. This implies that a list in $S$ being sorted with respect to $<_\sigma$ is equivalent it being sorted with respect to $<_{\tilde\sigma}$. We prove this invariant by induction in $I$. The base case is trivial.

In the inductive case, suppose that $l\in S$ is sorted according to some $<_{\tilde\sigma}$. Defined $\tilde\sigma':\{1,\dots,|I'|\}\to I'$ by $\tilde\sigma'(i)=\tilde\sigma(i)$ if $i<i_0$ and $\tilde\sigma'(i)=\tilde\sigma(i-1)$ if $i>i_0$. Since each $l_k\in S'$ is sorted with respect to $\tilde\sigma$, it is also sorted with respect to $\tilde\sigma'$. By the induction hypothesis, we therefore have that for all $a,b\in l_k$, $a<_{\tilde\sigma'}b$ iff $a<_{\sigma'}b$.

Let $a,b \in l$.

If $a,b\in l_k$, $a<_{\tilde\sigma} b$ iff $a<_{\tilde\sigma'}b$ iff $a<_{\sigma'}b$ iff $a<_{\sigma}$.
If $a\in l_k$ and $b\in l_{k'}$ with $k<k'$, by (A), $a<_{i_0} b$ and we therefore have $a<_{\sigma}b$. Since $l$ is sorted with respect to $<_{\tilde\sigma}$, $a<_{\tilde\sigma}b$. So we indeed have $a<_{\tilde\sigma}b$ iff $a<_{\sigma}b$ (because both are true).

We can boost it a bit by keeping keeping $S$ as a list (such that $L:=\operatorname{flatten}(S)$ is an invariant) instead of a set. You also keep a list $J$ of integers such that $\forall k\in\{1,\dots,|I|\}$, the sublist $L[1\dots J[k]]$ is sorted according to $<_k$. Then, to test a candidate $i_0$, you only check that $L[J[i_0]\dots |L|]$ is sorted with respect to $<_{i_0}$ (where you would previously test that $L[1\dots |L|]$ is), and if it fails at some point, you update $J[i_0]$ to the greatest $j$ such that $L[1\dots j]$ is sorted according to $<_{i_0}$. The number of comparisons is then bounded by $O(|I||S|+|I|^2)$ because:

You only get a positive answer for a test once (because then, you remember it was positive with $J$ and never test it again) which amounts for $O(|I||S|)$ because $\sum\limits_{1\le k \le |J|}J[k]$ starts at $0$, increases by one after every positive test (if we update it after every comparison instead of just after a comparison with a negative answer), and is bounded by $\sum\limits_{1\le k \le |J|}|S|=|J||S|=|I||S|$.
There are at most $O(|I|^2)$ negative answers, because $|I|$ strictly decreases at each iteration of the outer loop, and in the worst case, the right $i_0$ is the last you try.

You could probably further optimize it by trying all possible $i_0$ in parallel, and picking one as soon as it's the only one left (instead of checking that the rest of the list is indeed sorted with respect to that index).


To keep things a little cleaner let's assume that the graph has a Hamiltonian cycle that's embedded along the spine so that each cell of the embedding lives within a single page. Also those spine edges are places where multiple cells meet so let's make them vertices as well.

Then, within each page of the book, the dual graph is a forest, with all vertices that are not adjacent to a leaf having degree three or more, and having the spine edge vertices as its leaves. So a book embedding with $p$ pages has a dual graph consisting of $p$ plane forests, sharing a common set of leaves in the same cyclic ordering as each other.

Whether this structure is useful for anything is a different question, of course.

As for your question about generalizations of planar graph decompositions into primal and dual spanning trees: I doubt something like that happens in book embeddings, but it can be generalized to embeddings of graphs onto non-planar manifolds. See my paper "Dynamic generators of topologically embedded graphs" (SODA'03).


Are there any open problems left about DFAs?

Here is one problem described in the book "A second course in formal languages and automata theory" by Shallit.

  Let $u$ and $v$ be two distinct words with $|u|=|v|=n$.  What is
  the size of the smallest DFA that accepts $u$ but rejects $v$, or vice versa?

Robson, in his paper "Separating strings with small automata" in 1989 proved an upper bound $O(n^{2/5}(\log n)^{3/5})$.  The best known lower bound in $\Omega(\log n)$.

For a survey see this.


Ramsey's theorem for collections of sets

Observed that the question is non-trivial only when k, K both larger than 1;
for the case k = 1 or K = 1, it is just the normal Ramsey theorem, which is true for all n.
Also, we only have to deal with the case that ${n \choose k}$ > K, otherwise the theorem is true since there is at most one ${n \choose k}$-subset of B' constructed by an n-subset A' of A.

First we prove the theorem is false for all k > 1, K > 1, and any n satisfies ${n \choose k}$ > K > $({n-1 \atop k})$.

In order to construct a counterexample, for any large N and A = [N], we have to construct a coloring function f such that for all n-subset A' of A, if B' consists of all k-subsets of A', some of the K-subsets of B' have different colors. Here we have the following observation:

  Observation 1. Under the conditions that k, K > 1 and ${n \choose k}$ > K > $({n-1 \atop k})$, any K-subset of B is a subset to at most one B' constructed by a n-subset A' of A.

The observation can be easily seem by representing as hypergraphs. Let A be nodes of the graph G, an n-subset A' of A is the node set of a complete n-subgraph in G. B' is the set of k-hyperedges in the complete subgraph (a 2-hyperedge is a normal edge), and K-subsets of B' are the every combinations (there are $({|B'| \atop K})$ in total, where |B'| = ${n \choose k}$) of K k-hyperedges. The observation states: any K-tuple of hyperedges in G belongs to at most one complete n-subgraph, which is obvious for ${n \choose k}$ > K > $({n-1 \atop k})$, since any two complete n-subgraphs intersect at most n-1 nodes, with at most $({n-1 \atop k})$ hyperedges.

Then we can assign different colors within K-subsets C' of a particular B' constructed by a n-subset A', since any element in C' will not occur as another K-subset of B'' constructed by a n-subset A''. For any K-subset of B not constructed by any n-subset of A, we assign random color on it. Now we have a coloring function f, with the property that no B' constructed by n-subset of A is monochromatic, that is, some of the K-subsets of B' have different colors.

Next we show that the theorem is also false for all k > 1, K > 1, and any n satisfies ${n \choose k}$ > K. Here the only difference is n may be chosen so large, that K > $({n-1 \atop k})$ is not true. But by another simple observation:

  Observation 2. If some B' constructed by an n-subset A' of A is monochromatic, then every B'' constructed by an n'-subset A'' of A' for n' < n is also monochromatic.

Hence we can assume the theorem holds on the larger n, apply the second observation, and concludes a contradiction by the first case, by setting n' satisfies $({n' \atop k})$ > K > $({n'-1 \atop k})$; such n' must exist by the fact that $({n \atop k})$ > K and K > $({k \atop k})$, n' must lie between n and k+1.


If I understand your question correctly the answer is yes. In the paper

"Majority Gates Vs. General Weighted Threshold Gates" (http://www.nada.kth.se/~johanh/majorityvsthreshold.pdf) by Goldman, Håstad, and Razborov

They show that anything that can be computed by a depth $d$ threshold circuit can be computed by a depth $d+1$ unweighted threshold circuit of poly size.

Your question seems to be a special case of this for $d=1$.


I'm glad you're interested in my IP with BQP prover problem!

Unfortunately, I'm not sure I understand your question.  If the function $f$ satisfies the Simon promise, then Merlin can easily convince Arthur of that by telling him the secret string $s$.  If, on the other hand, $f$ is one-to-one, then Merlin can convince himself of that (by using Simon's algorithm to look for $s$ and not finding anything), but the question is how he can convince Arthur.  It clearly won't do for Merlin to say, "Arthur, I looked for $s$, but I found nuthin'!"  For how would Arthur know that Merlin wasn't lying?

Now, it's a known theorem that, if Merlin wasn't around, then Arthur would need to make at least ~$2^{n/2}$ black-box queries to $f$, in order to decide with high probability whether $f$ was one-to-one or satisfied the Simon promise.

It's also known that, if Merlin had unbounded computational power (not just the power of BQP), then there is an interactive protocol by which Merlin could convince Arthur that $f$ is one-to-one.  Namely, Arthur picks a random $x$, evaluates $f(x)$, sends $f(x)$ to Merlin, and asks Merlin to tell him what $x$ was.  If $f$ is one-to-one, then Merlin---provided he has NP search powers---can always answer such challenges correctly.  But if $f$ is two-to-one, then Merlin must be wrong with probability at least $1/2$.

The case I asked about---the one where Merlin has BQP powers, but no more than that---is still open.

To answer your last question: no, one would not need to prove BPP≠BQP in order to solve this problem.  The reason is that this problem only concerns the relativized setting: the setting where the function $f$ is a black box, which Arthur and Merlin can learn about only by querying it.  And in the relativized setting---unlike the "real," unrelativized one---we can often prove unconditional separations between complexity classes!  Indeed, I already mentioned one example above: it's known that any classical randomized algorithm to solve Simon's problem has to make exponentially many queries to $f$.  That fact implies the existence of an oracle separating BPP from BQP.


Best lower bound for proof complexity of graph non-automorphism problem

If GNA is in CoNP, and by certificate you mean any string y such that x is in GNA iff xy is accepted by a deterministic turing machine in polynomial time, then a non-trivial lower bound on the certificate size would imply P!=NP. If P=NP, then CoNP=NP=P and there is a deterministic turing machine that accepts GNA without the need of a certificate, or with a certificate whose size is equal to zero.


Can Bencodes Be Described With a Context-Free Grammar?

The language of valid Bencoded values is not context-free—and nor is just the language of Bencoded strings. Let $L$ be the set of valid Bencoded values, and let $L'$ be the intersection of $L$ with the regular language [0-9]*:a*, i.e. the Bencoded strings with just the symbol a. If $L$ were context-free, so would $L'$, but $L'$ does not satisfy the pumping lemma.

Suppose $L'$ is context-free, the pumping lemma applies. Let $n$ be the pumping threshold and let $w = \mathrm{dec}(n):a^n$, where $\mathrm{dec}(n)$ denotes $n$ written in decimal. Then $w = \alpha\beta\gamma\delta\epsilon$, and $\alpha\beta^m\gamma\delta^m\epsilon \in L'$ for all $m$. The colon must appear in $\gamma$ (the other cases can easily contradicted). Then the number to the left of the colon grows exponentially in $m$ (since its length in decimal increases linearly), but the string to the right only grows linearly, so the number can't be equal to its length.

You said

  If you have a trivial function that converts the ASCII “5” into a unary value and all the other ASCII characters into a character then you have an equivalent structure.

but it turns out that this function is not trivial from the perspective of context-free grammars.


Reduction/transformation from MinCostSat to MaxSat

First thing to realize is that minimization can be rephrased as maximization of the negated literal (and vice a versa). So minimizing $x+y$ is the same as  maximizing $\lnot x + \lnot y$. So to get a partial maxsat problem you just add the unit clauses $\lnot x$, $\lnot y$ as soft clauses and the original clauses as hard. (partial MaxSAT is crucial here, weighted partial MaxSAT is needed if you have  coefficients in the minimization function)


Finite One-Way Permutation with Infinite Domain

The paper On constructing 1-1 One-Way Functions, by Goldreich, Levin and Nisan shows how to construct length preserving 1-1 functions with infinite domains and finite description. The hardness of inverting the functions is based on popular assumptions, such as hardness of inverting RSA or finding Discrete Logarithms.

Their construction is a twist of the straightforward idea of converting a family, $\{f_i\}_i$, of one-way functions into a single one-way function by setting $f(r,s) = f_i(x)$ where $r$ is the randomness used to pick the index $i$ and $s$ is the randomness used to select the input $x$ (given the index $i$).

The problem with the above idea is that $f(r,s)$ is not necessarily 1-1. They amend this problem by slightly modifying $f(r,s)$ and arguing that, under certain conditions on the family $\{f_i\}_i$, the new construction is indeed 1-1. They then go on to show that these conditions are satisfies by the RSA/Discrete-log based functions.


Cooperative Pathfinding to minimize global costs

This may be related to network formation games - games in which players try to find a path in a network, and collaborating along a path reduces the cost for both players (i.e. the cost is shared)
This paper may be of help.


Probabilistic and quantum analog of $FP$ and $FNP$?

I hope the following partially answers your question. I've never seen this  observation published anywhere (please correct me if I'm wrong).

First of all, FQMA - a quantum analog of FNP - was defined: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fqma

One of the compelling reasons to define the complexity class NP is that there is a decision to search reduction: polynomial access to an oracle that solves NP-Complete problems allows you to search for a solution of any problem in FNP in polynomial time.

A decision to search reduction is not known between QMA and FQMA . For example, access to an oracle for the Local Hamiltonian problem is not known to be sufficient to efficiently construct a ground state.

Another related (although, not directly related to your question) reduction which is known for many classical NP problems, but not for QMA problems is downward self reducibility:
A language L is downward self reducible if there is a cook reduction from L to itself such that the queries are shorter than the original input. For example, given a Local Hamiltonian H with m terms, decide whether its minimal energy is below a or above b (where b-a>1/poly) by asking questions regarding Hamiltonians which have m-1 terms or less. Many decision to search reductions have this additional property.


Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$

If I understand right what "average volume" means here, I don't think this is correct. For example, let's say you map $n$-bit strings (under uniform distribution) to $n$-bit strings as follows: Given an input $x$, if the first bit is 0, output $x$, and otherwise output "1".

The average volume would be $\frac{1}{2}(2^{n-1}+1)$, whereas the $2^{H(X|\hat{X})} = \sqrt{2^{n-1}}$.

The correct expression for the average volume should perhaps be the expectation $\sum p(\hat{x}) 2^{H(X|\hat{X}=\hat{x})}$.

You are right about p.d.f. vs p.m.f, this kind of mix-up of terminology is quite common (but shouldn't be).


Complexity Theory Consequences of $\mathsf{NP} = \mathsf{QP}$

We can prove $\mathrm{NP\ne QP}$ unconditionally: $\mathrm{QP}$ is closed under quasipolynomial-time reductions, whereas $\mathrm{NP}$ is not (a simple padding argument shows that the closure of $\mathrm{NP}$ under quasipolynomial-time reductions includes all languages computable in nondeterministic quasipolynomial time, and this class strictly contains $\mathrm{NP}$ by the nondeterministic time-hierarchy theorem).
As for consequences of the weaker assumption $\mathrm{NP\subseteq QP}$, see the question Is NP in $DTIME(n^{poly\log n})$?.


Complexity of the Fisher-Yates Shuffle Algorithm

I suspect that here, like in most algorithms work, the cost of reading and writing $O(\log n)$ bit numbers is assumed to be a constant. It's a minor sin, as long as you don't get carried away and collapse P and PSPACE by accident.


Various people are interested in proving this sort of thing. Neel Krishnaswami mentioned this particular theorem here. I’ve also seen Frank Pfenning give some cool examples for ordered logics. For example, if you have $A, x : [A], y : [A] \vdash e : [A]$, then in an ordered type system, $e$ must append the lists $x$ and $y$.

The short answer is that yes, we can prove your first example. In the context of lambda calculi, a logical relations-based approach is described in this paper. They would prove your theorem in two steps:

Define a relational interpretation of types and use it to prove a conventional free theorem completely ignoring linearity i.e. essentially using the same reasoning you see in, for example, “Theorems for Free!”. Given $\vdash f : \forall A . [A] \multimap [A]$, the usual free theorem tells us that $f$ returns a list which contains only elements that were present in the list it was given. Given a list of distinct free linear variables $x_1 \ldots x_n$, we deduce that $f [x_1, ..., x_n]$ evaluates to some list $[y_1, ..., y_m]$ where $\{y_1, \ldots, y_m\} \subseteq \{x_1, ..., x_n\}$.
Notice that free linear variables must be preserved under evaluation. This lets us take advantage of linearity. If $[y_1, \ldots, y_m]$ were not a permutation of $[x_1, ..., x_n]$, then it would imply that some $x_i$ were lost or duplicated during evaluation, which cannot happen.

But, these sorts of theorems get more interesting when we look at a language with effects and our ability to prove them for such languages is sadly limited. For example, consider the isomorphism $\tau \cong \forall A . (\tau \to A) \to A$ from System F. In a call-by-value setting, this isomorphism breaks when we add non-termination. We should be able to recover a similar isomorphism, though, with linear types: $\tau \cong \forall A . (\tau \to A) \multimap A$. Unfortunately, we do not have operational logical relations that can prove this.

That said, there are also syntactic methods that can prove both this isomorphism and your theorem. This seems to be a particularly useful approach in a linear setting, and is much less of a burden than setting up a logical relation for proving simple theorems.

Edit: Since you asked, here’s an example of a syntactic proof of a free theorem for the type $\forall A . (A \otimes A) \multimap A$ in a setting with a term $\bot$ that loops forever and is well-typed under any context at any type. The idea is to find a set of canonical terms of a type and use that to determine what the possible return values for a function are. We start with a soundness theorem for well-typed terms.

  Theorem (Canonicity). If $\Delta; \Gamma \vdash e : \tau$ then either

  $e \approx v$, which is a value such that $\Delta; \Gamma \vdash v : \tau$.
  $e \approx n$, a term which is stuck because it is trying to use a free variable in $\Gamma$, and $\Delta; \Gamma \vdash n : \tau$ OR
  $e \approx \bot$

Here, $\approx$ is your favorite notion of equivalence for the language and $\Delta$ is an environment containing free type variables. I will consider free variables $x$ to be values. For simple languages, a straightforward progress & preservation argument can be made to justify this theorem.

Now, given a value $\vdash f : \forall A . (A \otimes A) \multimap A$, we know that $f \approx \lambda x . e$ where $A; x : (A \otimes A) \vdash e : A$. From the type of e, we have a couple possible cases:

$e$ is equivalent to a pair $A; x : (A \otimes A) \vdash (v_1, v_2) : A$. This case is impossible since $v_1$ and $v_2$ must be values of type $A$, which is a free type variable. There are no such values because there are no variables in the context of type $A$.
$e$ is equivalent to a term which tries to use the free variable $x$.
$e$ diverges. This case gives us one possible value for $f$: $\lambda x . \bot$.

Since the second case is the only one left, we assume $e \approx\ \mathrm{let} (x_1, x_2) = x\ \mathrm{in}\ e’$ where $A; x_1 : A, x_2 : A \vdash e’ : A$. Thus far in the proof, we have established that $f \approx \lambda x . \mathrm{let }\ (x_1, x_2) = x\ \mathrm{ in }\ e’$. Finally, we apply our canonicity theorem one more time and find that $e’$ must diverge: the only values of type $A$ are variables but we have two variables in the context, so it cannot be the case that $e’ \approx x_i$.

Therefore, we have that the only inhabitant of $\forall A . (A \otimes A) \multimap A$ is $\lambda x . \bot \approx \lambda x . \mathrm{let }\ (x_1, x_2) = x\ \mathrm{ in }\ \bot$.

You asked for a reference for this sort of proof, but I’m not sure of a good one. This kind of reasoning is well-known in certain circles and goes back perhaps as far as Gentzen. I'm told that it is reminiscent of focused proof search for sequent calculus, but I don't know exactly what the connection is.

That said, I’m not aware of any modern published work that explains this relatively simple method well. Admittedly, it is a bit limited in its applicability to simpler languages. On the other hand, I think it has been overshadowed by “Theorems for Free!” et al and as a result even many senior researchers immediately think of logical relations when they hear the phrase “free theorem”, unaware that techniques like this can be a simpler alternative approach to such proofs (especially in the context of linear type systems).

As for your second example, I don’t think the free theorem you want actually holds. I could for example, instantiate $A$ with the integer type and then pass in a function that returns integers which are not in the list I give to $f$. Perhaps $\forall A. (\forall B. B \multimap (B, B)) \multimap [A] \multimap [A]$ is closer to the type you had in mind. But even then, no function of type $\forall B. B \multimap (B, B)$ exists since it would have to duplicate its input.


Approximately counting paths and cycles in a graph

Approximately counting all paths (or cycles) in polynomial time implies NP=RP. There is a very simple reduction to amplify the weight of the longest path/cycle. See https://doi.org/10.1016/0304-3975(86)90174-X, section 5.


Is there a FNP problem that's NP-hard but not FNP-hard?

I'm going to argue that the answer is probably "Yes", i.e.,

there probably are FNP problems that are NP-hard but not FNP-hard.

Warmup:  With respect to polynomially-closed reduction classes that can't solve all of FNPSPACE, FNPSPACE-hardness is different from NPSPACE-hardness.

Proof:        Let R be the relation given by xRy if and only if [x$\in$QBF$\hspace{.02 in}$ and y is the empty string].

QBF $\in$ PSPACE-complete $=$ NPSPACE-complete ,  so R is in FNPSPACE and NPSPACE-hard.

Let f and g form an arbitrary reduction from an arbitrary

relation S to R, and let x be an arbitrary instance of S.

x has an S-witness  $\implies$  f(x) has an R-witness  $\implies$

f(x) R empty_string  $\implies$  x S g(x,empty_string)  .

In other words, an arbitrary reduction from a search problem to R can be used

to solve the search problem.    Therefore R is not FNPSPACE-hard with respect

to polynomially-closed reduction classes that can't solve all of FNPSPACE.

Cryptographic Assumptions and sub-P reductions:

For each positive integer j, let R$\hspace{.02 in}$j be the relation given by  x R (C,v)  if and only if C is a circuit

and x is a CNF-SAT instace and  size(C) ≤ (number_of_variables_in_(x))$\hspace{.03 in}$j  and C(v) satisfies x.    Obviously, each R$\hspace{.02 in}$j is in FNP and NP-hard.    If they are all FNP-hard under non-uniform parallelizable reductions, then there can't even be a version of time-lock puzzles against

non-uniform adversaries that is otherwise very weak, namely, ones in which [the size of the

puzzle can be polynomial in the time for an honest user to solve it] and [there is no restriction

on the resources needed to create the puzzle] and [security only needs to hold infinitely often].  Furthermore, if there are efficiently-computable functions that are one-way against probabilistic

parallel adversaries then one can replace both instances of "non-uniform" with "probabilistic".

Probabilistic Polynomial-Time Reductions and handwaving:

(This is essentially tautological, but) If all NP-hard FNP problems are FNP-hard, then all

proof systems for SAT are "somewhat constructive", in the sense that any original instance can

be efficiently turned an equisatisfiable instance so that one will be able to go from any proof of

satisfiability of the equisatisfiable instance to a satisfying assignment of the original instance.

Non-interactive zaps are certainly not obviously "somewhat constructive" in that sense.


Minimizing residual finite state automata

Let the "DFA $\to$ NFA" problem denote the following: Given a DFA $A$ and an integer $k$, is there an NFA with at most $k$ states equivalent to $A$? Similarly, let "DFA $\to$ RFSA" denote the problem obtained from the above if we replace "NFA" with "residual finite state automaton".

Jiang and Ravikumar showed that the "DFA $\to$ NFA" problem is PSPACE-complete by a reduction from the "DFA union universality" problem. The latter problem has given a list of DFAs $A_1,A_2,\ldots,A_n$, and asks if $\bigcup_{i=1}^nL(A_i) = \Sigma^*$.

Their reduction goes by defining a language $L$ from these DFAs and a suitable integer $k$, such that a DFA accepting $L$ can be constructed in time polynomial in the size of the DFAs $A_i$. Then they show that every NFA (thus a fortiori every RFSA) accepting $L$ needs at least $k$ states in case $\bigcup_{i=1}^nL(A_i)$ is universal and at least $k+1$ states otherwise. Then they construct a $k$-state NFA $N$, which accepts $L$ iff $\bigcup_{i=1}^nL(A_i) = \Sigma^*$.

This proof was reconsidered later by Gruber and Holzer (Developments in Language Theory '06). They use the same reduction to show a slightly different result, which concerns the computational complexity of lower bound techniques for NFAs: An (extended) fooling set for a regular language $R$ is a set $S$ of word pairs $(x_i,y_i)$, such that for each $i$ holds $x_iy_i\in L$ but for all $i\neq j$ holds: $x_iy_j \notin R$ or $x_jy_i\notin R$.

For the above reduction, they show that there is an extended fooling set $S$ of size $k$ in case $\bigcup_{i=1}^nL(A_i)$ is universal. By inspecting the proof by Gruber and Holzer, one readily notes that each "left word" $x_i$ in the set $S$ is such that the NFA $N$ mentioned above can go from the initial state to only a single state $q_i$ on reading $x_i$. That is, the language accepted from state $q$ equals $x_i^{-1}L$, and thus $N$ is a residual finite state automaton.

If the above reasoning contains no mistakes, this yields a reduction from the DFA union universality problem to the "DFA $\to$ RFSA" problem, and thus it is PSPACE-hard. Membership in PSPACE follows along the same lines as for the DFA $\to$ NFA problem, so the "DFA $\to$ RFSA" problem is PSPACE-complete. Being more general but still in PSPACE, the "NFA $\to$ RFSA" problem is PSPACE-complete as well.

For those who want to reconstruct the above argument (please don't take it for granted, my writeup was a bit hasty), I recommend reading the proof of Theorem 15 in the ECCC report cited below. Especially, Figure 5 on page 18 depicts the automaton $N$ which I claim to be a RFSA.

T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on
Computing, 22(6):1117–1141, December 1993.

Hermann Gruber and Markus Holzer. Finding Lower Bounds for Nondeterministic State Complexity Is Hard. In Oscar H. Ibarra and Zhe Dang, editors, 10th International Conference on Developments in Language Theory (DLT 2006), Santa Barbara (CA), USA, volume 4036 of Lecture Notes in Computer Science, pages 363--374. Springer, June 2006.

Hermann Gruber and Markus Holzer. Finding Lower Bounds for Nondeterministic State Complexity is Hard. Technical Report ECCC TR06-027, Electronic Colloquium on Computational Complexity, 2006.


Is there any good literature on the computational complexity of function problems?

There is an article from Alan Selman: A taxonomy of complexity classes of functions

Please note, that i found this reference in an Answer (by Joshua Grochow) for this Question:

Complexity class when reducing decision problem to function problem

Note also the Comments from Kaveh:

  If you have a function you can look at the bit graph of the function which is a decision problem. If you can compute the function you can compute the bit graph easily from it. If you can compute the bit graph you can compute the function by simple computing the bits of the output one by one.

if i found more, i will add it here.


Is that particular case of the "minimum weight solution to linear equations" still NP-complete?

Here's a sketch of an NP-hardness proof. Exact cover by 3-sets is a natural generalization of the perfect matching problem to hypergraphs $G=(V,E)$ with all edges $e \in E$ containing 3 vertices (instead of 2) and $|V|$ is divisible by 3. The problem is to find a subset of the hyperedges such that each vertex is incident to exactly one of the selected hyperedges. Let $x_e$ be a 0/1 variable for each hyperedge $e$ indicating whether or not it is used. Clearly the system of equations

$\sum_{e \in E : v \in e} x_e = 1$    for all $v \in V$

has only non-negative coefficients and has a solution with at most $|V|/3$ positive coefficients if $G$ has an exact cover. The other direction, namely showing that this system has such a solution only if $G$ has an exact cover, is less trivial but still easy.


How difficult is it to work on mathematics problems as a computer science graduate student?

It's very common to move from maths to CS: for example, in my office of four people in CS, one is doing a PhD in CS after doing an undergraduate maths degree and another is a postdoc who just finished a PhD in maths. Moving from CS to maths seems much less common.

When you say "graduate student" it's unclear whether you mean master's or PhD. It sounds like you're interested in lots of areas of mathematics (you've mentioned geometry, topology, quantum mechanics and string theory in this and your other question), which doesn't seem focused enough for a PhD: for that, you need to pick one, fairly narrow area.  From what little I know about you, it seems that a master's in maths would be more appropriate, perhaps followed by a PhD in either maths or computer science if you find a particular subject whose computational aspects interest you.


Clique-width expressions with logarithmic depth

After a while I found an answer in the literature, so I'm posting it here in case it is useful to someone else.

It is in fact possible to re-balance clique-width expressions so that they have logarithmic depth. The result is given in the paper "Graph operations characterizing rank-width and balanced graph expressions" by Courcelle and Kanté, WG '08. I quote Theorem 4.4 from the paper:

"Every graph of clique-width or NLC-width $k$ is the value of a 3-balanced
clique-width expression of clique-width or NLC-width at most $k \times 2^{k+1}$"

The catch here is that the number of labels blows up exponentially in the balancing. It seems that for clique-width no better result is currently known. The same paper gives a similar result with only a constant blow-up for rankwidth, but this doesn't help, since the difference between clique-width and rankwidth can be exponential in the worst case.


Reducing space usage of st-connectivity with multiple passes?

It is a long standing open problem to find an algorithm for st-connectivity that runs in simultaneously sub-linear space and polynomial time, an easier task that what you are aiming at.  Such algorithms are known for the un-directed version, but even these require a large polynomial time (rather than O(km) time which would be implied by a k-pass algorithm).  See especially the reference to Tompa's paper on why the directed case seems hard.


If $\mathsf{NP} = \mathsf{PSPACE}$, this would imply:

$\mathsf{P^{\#P}} = \mathsf{NP}$That is, counting the solutions to a problem in $\mathsf{NP}$ would be polytime reducible to finding a single solution;
$\mathsf{PP} = \mathsf{NP}$That is, polynomial-time randomized algorithms with success probability arbitrarily close to 1/2 is polynomial-time reducible to polynomial-time randomized algorithms with one-sided error, where YES instances are accepted with arbitrarily small probability;
$\mathsf{MA} = \mathsf{NP}$That is, for any problem which is verifiable in polynomial time, randomization provides a polynomial-time speedup at best (but this is just a corollary of the polynomial-time hierarchy collapsing);
$\mathsf{BQP} \subseteq \mathsf{NP}$That is, any problem which is solvable by a quantum computer has easily verified certificates for its answers; this would be an important positive result in the philosophy of quantum mechanics, and would probably be helpful to the effort to construct quantum computers (for verifying that they are doing what they are meant to be doing).

All of these are due to containments of the classes on the left-hand sides in $\mathsf{PSPACE}$ (though we also have $\mathsf{BQP \subseteq PP}$).


In 2010 Hemmer et al. gave an exact algorithm for the Voronoi diagram of lines in $\mathbb{R}^3$. In their introduction, they state that the $\Omega(n^2)$ lower bound and $O(n^{3+\varepsilon})$ upper bound are still the best known on the combinatorial complexity of the resulting Voronoi diagram. Their algorithm runs in time $O(n^{3+\varepsilon})$, matching the upper bound on the combinatorial complexity.

As far as I know, theirs was the first (and still, only) exact algorithm for this problem, so I would guess that there haven't been any further improvements on the combinatorial complexity front either.


Examples of algorithms and proofs that seem correct, but aren't

2D local maximum

input: 2-dimensional $n \times n$ array $A$

output: a local maximum -- a pair $(i,j)$ such that  $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value.

(The neighboring cells are those among $A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$ that are present in the array.)  So, for example, if $A$ is

$$\begin{array}{cccc}
0&1&3&\mathbf{4}\\
\mathbf{3}&2&\mathbf{3}&1\\
2&\mathbf{5}&0&1\\
\mathbf{4}&0&1&\mathbf{3}\end{array}$$

then each bolded cell is a local maximum.  Every non-empty array has at least one local maximum.

Algorithm. There is an $O(n^2)$-time algorithm: just check each cell.  Here's an idea for a faster, recursive algorithm.

Given $A$, define cross $X$ to consist of the cells in the middle column, and the cells in the middle row.  First check each cell in $X$ to see if the cell is a local maximum in $A$.  If so, return such a cell.  Otherwise, let $(i, j)$ be a cell in $X$ with maximum value.  Since $(i, j)$ is not a local maximum, it must have a neighboring cell $(i', j')$ with larger value.

Partition $A \setminus X$ (the array $A$, minus the cells in $X$) into four quadrants -- the upper left, upper right, lower left, and lower right quadrants -- in the natural way.  The neighboring cell $(i', j')$ with larger value must be in one of those quadrants.  Call that quadrant $A'$.

Lemma. Quadrant $A'$ contains a local maximum of $A$.

Proof.  Consider starting at the cell $(i', j')$.  If it is not a local maximum, move to a neighbor with a larger value.  This can be repeated until arriving at a cell that is a local maximum.  That final cell has to be in $A'$, because $A'$ is bounded on all sides by cells whose values are smaller than the value of cell $(i', j')$.  This proves the lemma. $\diamond$

The algorithm calls itself recursively on the $\frac{n}{2}\times\frac{n}{2}$ sub-array $A'$ to find a local maximum $(i, j)$ there, then returns that cell.

The running time $T(n)$ for an $n\times n$ matrix satisfies $T(n) = T(n/2) + O(n)$, so $T(n) = O(n)$.

Thus, we have proven the following theorem:

Theorem. There is an $O(n)$-time algorithm for finding a local-maximum in an $n\times n$ array.

Or have we?


Probability of random (in)finite graphs being isomorphic

From the comment: in the mathematical field of graph theory, the Rado graph [1], also known as the random graph or the Erdős–Rényi graph, is the unique (up to isomorphism) countable graph $R$ such that for every finite graph $G$ and every vertex $v$ of $G$, every embedding of $G − v$ as an induced subgraph of $R$ can be extended to an embedding of $G$ into $R$. As a result, the Rado graph contains all finite and countably infinite graphs as induced subgraphs.

In this note you can find other details, in particular: ... if we produce two random infinite graphs, then, with probability 1, they both have the extension property. Hence they are isomorphic (and also isomorphic to the Rado graph); in other words, any two random countably infinite graphs are isomorphic ...

[1] Rado, Richard (1964), "Universal graphs and universal functions", Acta Arith. 9: 331–340.


Ensuring integral maximizer from integral linear program

Given an integral LP, you can use a LP algorithm to compute in polynomial time

the optimal value of the LP,

a vertex of the feasible region (polytope) of the LP where the optimal value is attained.

Thus, if you know that the polytope is integral (i.e., all the vertices are integral), then you can indeed compute in polynomial time an integral maximizer. In particular, this applies if the constraint matrix is totally unimodular.
However, as noted in the comments by Laakeri, it is in general NP-hard to compute an integral maximizer if you only know that one exists. This follows by reduction from the NP-complete problem of feasibility of ILP:

If you can compute integral maximizers of LPs that have them, you can also determine if a given LP has an integral maximizer:

Using an LP algorithm, compute the optimal value $v$.

Run the integral maximizer finder to compute a point $x$. (If the algorithm crashes, outruns its allotted time, etc., just fix $x$ as some garbage point.)

Check that $x$ is an integral point, it satisfies the inequalities of the LP, and it gives value $v$.

If this checks out, then $x$ is indeed an integral maximizer of the LP. Conversely, if the LP has an integral maximizer, the algorithm finds it by assumption.

An LP has an integral feasible point iff the constant $0$ objective function has an integral maximizer.


On the faces of the multicommodity flow polytope

This will be a bit long, but please bear with me.

First, let me clarify the terminology a bit. I think what you are interested in here are in fact the facets of the polytope (i.e., "the minimum set of irredundant valid inequalities" or the "maximal dimensional faces still distinct from the polytope itself") rather than the faces. Plus, as you write, the object you study is much better called the "aggregate-flow polytope" or, as some authors refer to it, the "demand polytope" or the "throughput polytope". Call this polytope $T$.

Here is what I know about $T$:

Associated with any capacitated graph $G$ and set of source-destination pairs $(s_k, d_k): k \in 1, \ldots, K$, there is an "aggregate-flow set" $T$.
This $T$ is a polyhedron and it is well-defined. You can see this for yourself by considering the following construction: take the multicommodity-flow polytope (i.e., the polyhedron of the feasible arc-flows or path-flows) and apply an affine mapping that to each commodity orders the sum of the individual flows. As affine maps of polyhedra are again polyhedra, you get the required result.
If $G$ is connected and the edge capacities $c$ are strictly positive, then $T$ is a full-dimensional, compact, convex polyhedron in $\mathbb{R}^n_+$ (so it  is in fact a polytope).
$T$ is down-monotone: $t \in T \Rightarrow \forall x \in [0, t]: x \in T$.
You can obtain all the valid inequalities that describe $T$ using the Japanese Theorem due to Onaga and Iri: for any non-negative weight set $w_{ij}: (i,j) \in E$ on the edges $E$ of $G$, the inequality:
$$\sum_{k=1}^K \beta_k . t_k \le \sum_{(i,j) \in E} w_{ij} c_{ij} $$
is valid for $T$, where $\beta_k$ denotes the shortest path distance from $s_k$ to $d_k$ for commodity $k$ over the weights $w$, $t_k$ is the aggregate-flow for the $k$th commodity and $c_{ij}$ is the capacity of edge $(i,j)$. In fact, you get all the valid inequalities for $T$ this way.
Any weight set that is not an extreme ray of the below projection cone $W$ generates redundant inequalities for $T$, where
$$W = \{(w,\beta): \forall k, \forall P \in \mathcal{P_k}: \sum_{(i,j) \in P} w_{ij} \le \beta_k, w \ge 0\}$$
where $\mathcal{P_k}$ denotes the set of all paths between $s_k$ and $d_k$. This sort of answers your second question.

Now, regarding the number of facets needed to describe $T$.

First, I believe your conjecture "for any $N$ there is a graph for which $T$ has more than $N$ facets" is not true. What we can show is that $T$ has finitely many facets, because the projection cone $W$ has only a finite number of extreme rays, and these generate all the facets (unfortunately, usually many more inequalities too). Note, however that this alone does not disprove your conjecture.

However, that this still allows the number of facets to be exponential, and curiously this is precisely the case. At least for directed graphs, I seem to have a proof somewhere that for the complete bipartite graph $K_{n,n}$ on $n$ nodes with $n$ distinct source nodes in one partition and $n$ distinct destination nodes in the other and capacities all equal to $1$, all the $\{0,1\}^n$ vectors $b$ except for the all-zero vector generate a facet $\sum_n b_n t_n \le q$ for some appropriate $q$, and this gives you $2^{n}-1$ facets. I don't know about the undirected case, the above may either hold or not hold.

For $K=3$ in particular, this gives 7 facets (plus the non-negativity conditions, but that's trivial) for $K_{3,3}$ in the directed case. As far as I can work it out now, the same applies to the undirected case as well. I have fairly good reasons to believe that this is in fact the upper bound for the directed case, but I may be completely wrong here.

You can find an awful lot of results on this topic in Schriver's heroic survey:

Alexander Schrijver: Combinatorial Optimization - Polyhedra and Efficiency, Volume 3, Part VII, Multiﬂows and Disjoint Paths

Should you have any comments, results, or further reading (apart from my own papers) on this topic, count me very very interested.


Quasipolynomial and polynomial time hierarchy

If $NP$ can be solved in quasipolynomial time, then $NP$ has quasi polynomial size circuit.
The second condition implies that the exponential time hierarchy collapses to the second level (as was shown in the paper of Buhrman and Homer). It was improved the collapse to $S_2^{exp}$ in a paper of Pavan et al.
As far as I know, these hypotheses do not easily imply a collapse of PH.


How is proving a context free language to be ambiguous undecidable?

We reduce from Post's Correspondence Problem. Suppose we can, in fact, decide the language $\{\langle G\rangle\vert G\textrm{ a CFG and }L(G)\textrm{ ambiguous}\}$.

Given $\alpha_1, \ldots, \alpha_m, \beta_1, \ldots, \beta_m$:
Construct the following CFG $G = (V,\Sigma,R,S)$:
$V = \{S, S_1, S_2\}$,
$$\begin{align}
R = \{S_{\phantom0}&\rightarrow S_1\vert S_2,\\
S_1&\rightarrow \alpha_1 S_1 \sigma_1 \vert \cdots \vert \alpha_m S_1 \sigma_m \vert \alpha_1 \sigma_1 \vert \cdots \vert \alpha_m \sigma_m,\\
S_2&\rightarrow \beta_1 S_2 \sigma_1\vert \cdots \vert \beta_m S_2 \sigma_m \vert \beta_1 \sigma_1\vert \cdots \vert \beta_m \sigma_m\}
\end{align}$$
(where $\sigma_i$ are new characters added to the alphabet, e.g., $\sigma_i = \underline{i}$).

If the language is ambiguous, then there is a derivation of some string $w$ in two different ways. Supposing, wlog, that the derivations both start with the rule $S\rightarrow S_1$, reading the new characters backwards until they end makes sure there can only be one derivation, so that's not possible. Hence, we see that the only ambiguity can come from one $S_1$ and one $S_2$ 'start'. But then, taking the substring of $w$ up to the beginning of the new characters, we have a solution to the PCP (since the strings of indices used after those points match).

Similarly, if there is no ambiguity, then the PCP cannot be solved, since a solution would imply an ambiguity that just follows $S\Rightarrow S_1\Rightarrow^* \alpha\tilde{\sigma}$ and $S\Rightarrow S_2\Rightarrow^* \beta\tilde{\sigma}$, where $\alpha = \beta$ are strings of matching $\alpha$'s and $\beta$'s (since the $\tilde{\sigma}$'s match).

Hence, we've reduced to PCP, and since that's undecidable, we're done.

(Let me know if I've done anything boneheaded!)


Is there any known work on generating random uniformly distributed DAGs given a set of path existence/absence constraints?

There is some work concerning random orders. Good and slightly outdated survey is $[1]$. In this survey you can find description for the basic models of random orders: uniform model, model of random graphs orders and model of random $k$-dimensional orders. It should be noted that these models are derived for arbitrary random orders and maybe you won't find there results on generation of random orders which are extensions of the given partial order.

Brightwell G. Models of Random Partial Orders. Surveys in combinatorics, 1993.


My name is Mike.  I'm a PhD student in the area of TCS.  I am self taught in many areas of Mathematics and Computer Science.  Many people would tell you NOT to do this, but when I was your age I bought a book on Analysis (Formal Version of Calculus) and read it cover to cover.  It took about 9 months to read with a continued supply of effort and motivation, but it helped transform my way of thought and gave me the skills to formally express concepts and create proofs on my own.  It also helped me to finally understand the concept of real numbers.

Here's a problem that you would face if you did this.  One, it's hard and you would likely be reading it on your own.  You can talk about it with your friends and parents, but most of them won't really understand.  Secondly, once you finish it, you will be much better at math, but you don't get any college credit and later on you may have to retake a simpler version of the class and be bored out of your mind.  I was able to avoid this by doing a summer program at a local university and afterwards enrolling there as a part-time student.  It took some confidence, effort, and luck to organize such an education, but it paid off.  It allowed me to continue to learn and get credit so that I could take the classes I should be taking when I got to college.

After telling that little story I decided to write up some options that I'd recommend:
(1) Get a good math book and read it
(2) Enroll in a college course at a local university (or summer program locally or not locally)
(3) Work on programing projects
(4) ** Participate in USAMTS ** - http://www.usamts.org/
(5) But, whatever you do, try not to do it all alone

Options for what you could be learning:
(a) Intro to Formal Mathematics: any book that includes proofs, sets and functions, basic number theory, inequalities, basic counting problems, and fun/interesting/challenging problems.
(b) Number Theory - I did well starting out with a few number theory books early on.
(c) Intro to Analysis - Formal version of Calculus and a study of real numbers.
(d) I myself didn't learn much graph theory until later on, but I don't think that would be an unreasonable subject to learn about especially since it's important for Computer Science and Computation in general.

You should know this as well.  For all those who are self teachers, be aware that communication with others is key.  It's important to develop the flexibility to take on new terminology, to be capable of verbally expressing complex concepts, and to take the time and energy to really focus and listen to others.

I wish you the best of luck with everything.  If you ever would like to talk further, please respond.  I am more than willing to chat with you every now and then.  :D

Ps. I would have started out by saying hi, but it didn't let me.


partition to min the max number of intersections

This is NP-hard, by reduction from 3-partition.

Given $\left[\hspace{.03 in}j_0,j_1,j_2,...,j_{(3\cdot k)-1}\hspace{-0.01 in}\right]$, $\:$ where $\; J = \operatorname{sum}\left(\left[\hspace{.03 in}j_0,j_1,j_2,...,j_{(3\cdot k)-1}\hspace{-0.01 in}\right]\right) \;$, $\;$ if there are

$k$ different stores, $\:J$ items, and $\:(3\cdot k)+(4\cdot J)\:$ customers,

with customer $i$ for $\:i\in [0,1,2,...,(3\cdot k)-1]\:$ interested in the obvious $j_i$ items

and four other customers interested in each one of the items,

then

the maximum can't be less than $\:\frac{4\cdot J}k+3\:$ and the partitions whose maximum is

$\frac{4\cdot J}k+3\:$ are exactly those corresponding to $3$-partitions of $\left[\hspace{.03 in}j_0,j_1,j_2,...,j_{(3\cdot k)-1}\hspace{-0.01 in}\right]$

.


Properties about verticies in Delaunay Triangulations

(In 2-space,) a Delaunay triangulation is a planar graph. All planar graphs have average degree at most 6. So, many (all?) operations that depend on vertex degree of a Delaunay triangulation will run in $O(1)$ expected time.


There's support for extensible type systems in JetBrains MPS (http://www.jetbrains.com/mps/). Basically it has a constraint solving engine which supports both equations (type equalities) and inequalities (subtyping). Extensions add new rules of adding constraints which are solved by the engine.

P.S. I think the question is more appropriate for stackoverflow than cstheory.