How are random numbers structure-less? I'm using random numbers for simulations. The main reason is to have an input sequence where no (simulation) algorithm is going to lock on a pattern and introduce unwanted effects into the simulation. So it seems random numbers have irreversibly lost the structure and it's unlikely that an algorithm is going to "reverse-engineer" it.

Is there a formal way to quantify this, such that pseudo-random numbers come out as being very unstructured?

I've read something about Kolmogorov complexity, but strictly speaking there is a very simple algorithm which can generate (pseudo)random numbers?! So they are not complex in this sense?

I can give several answers to your question.

Algorithmic randomness. When should we call a sequence $x_1,\ldots,x_n$ of bits random? A priori, all sequences have the same probability, so it's not clear on what grounds we should single out one sequence or another as not being random. This is partly a philosophical question, but "applied philosophy" has given rise to several definitions of algorithmic randomness, detailed in the Wikipedia entry. These notions are actually for infinite sequences, but some of them can also be used for finite sequences, for example the notion of Kolmogorov-random sequence that you mention in your question. The trouble with these notions is that one cannot compute random sequences – that's a feature of the definitions.

Pseudorandomness. Complexity theorists and (theoretical) cryptographers prefer a more permissive notion of randomness. Suppose you need a random sequence to run algorithm A which belongs to complexity class C. A pseudorandom sequence is a sequence that "fools" algorithms of complexity class C – that is, it looks random to such algorithms. More formally, algorithms of class C cannot distinguish a small set of pseudorandom sequences from a truly random sequence. As joro mentions in their comment, for this definition to make sense, you need to look at a collection of pseudorandom sequences, since one sequence could always be distinguished from a random sequence (at least in non-uniform computation models).

There are no known pseudorandom sequences against complexity classes beyond some very weak ones, though there are constructions which work assuming some complexity assumptions. Such constructions are not necessarily useful for practical applications, for three reasons: (1) you are given a large set of sequences rather than one sequence, and you have to run your (decision) algorithm on all of them; (2) constructions in complexity theory tend to be impractical; the pseudorandom sequences are probably really hard to generate in practice, especially for realistic values of $n$ (the input size); (3) asymptotic analysis doesn't usually yield concrete bounds, so it would be hard for you to figure out what parameters to use; worse, if the security of the construction relies on some non-explicit complexity assumption (e.g. P$\neq$NP), the guarantee could be purely asymptotic, and not give any explicit bounds.

Practical randomness. Random numbers are used in practice in two kinds of situations: numerical simulations and cryptography. When using random numbers for numerical simulations, the "quality" of the numbers is not as important as the time it takes to generate them; in practice, even rather simple pseudorandom number generators seem to "work". A search of the relevant literature will reveal some modern examples. Some of the old pseudorandom number generators were indeed bad (in some situations), but the this threshold has been crossed, and from an engineering perspective the problem can be considered solved.

Random numbers used for cryptographic purposes need to be more secure, since now we're against somebody who's construction the algorithm for the express purpose of reverse engineering the random stream. In this case one needs to be a bit more careful and use a secure, industry standard stream cipher. Such ciphers are available, and I strongly urge against using anything else, especially anything which you designed yourself. For extra security, XOR the output of several stream ciphers using independent keys.


Find the cheapest cycle through two points on a rectangular grid I have a task, but I have no idea how to solve it.

We have to find a cycle going through $(1,1)$ and $(n,n)$ (X axis on the picture is indexed right to left) such that the sum of values in cells is minimized. A cycle can't contain a cell more than once.

Example:

Ok, here's a reduction from Hamiltonian cycles in grid graphs to your problem. It requires the grid graph to have vertices in the two opposite corners but that shouldn't be an obstacle to getting the details to work.


Space of Imperative Programs Consider the space of all imperative programs.

From the view of mathematical analysis, what kind of space is it?
Is it an algebraic structure?

Please also give references.

Editing of the question is welcome.

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

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

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

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


Finding maximum weight arborescence in an edge-weighted DAG Let $G$ be an edge-weighted DAG with a unique source $s$. The question is how to find out a maximum weight arborescence in $G$ rooted at $s$.

When all edge weights are positive then the required arborescence is also spanning and so we can use the directed minimum spanning tree algorithm (http://www.ce.rit.edu/~sjyeec/dmst.html)

What if negative weights are allowed?

The problem is NP-complete by a reduction from the set cover problem.

Set cover
Instance: A finite set U, a family C of subsets of U and k∈ℕ.
Question: Is there a cover D of U in C with at most k sets, that is, a subset D of C with |D|≤k such that the union of D is equal to U?

Given an instance (U, C, k) of the set cover problem, let U={a1, …, an} and C={S1, …, Sm} (n=|U|, m=|C|) and construct a DAG G with four layers of vertices:

The first layer consists of a single source s.
The second layer consists of m vertices x1, …, xm, each of which has an incoming edge from s with weight −1.
The third layer consists of n vertices y1, …, yn.  The vertex yi has an incoming edge from the vertex xj with weight 0 for each pair (i, j) such that ai∈Sj.
The fourth layer consists of n vertices z1, …, zn.  Each vertex zi has an incoming edge from the corresponding vertex yi with weight m.

Then it is easy to see that there is a cover of U in C with at most k sets if and only if the DAG G has an arborescence rooted at s with total weight at least nm−k.


What's the "real" reason that IP=PSPACE is non-relativizing? IP=PSPACE is listed as the canonical example of a non-relativizing result, and the proof for this is that there exists an oracle $O$ such that ${\sf coNP}^O \not\subseteq {\sf IP}^O$, while ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ for all oracles $O$.

However, I've seen only a few people give a "direct" explanation for why the ${\sf IP} = {\sf PSPACE}$ result does not relativize, and the usual answer is "arithmetization". Upon inspection of the proof of IP=PSPACE, that answer isn't false, but it isn't satisfactory to me. It seems that the "real" reason traces itself back to the proof that the problem TQBF - true quantified boolean formula - is complete for PSPACE; to prove that, you need to show that you can encode configurations of a PSPACE machine in a polynomial-sized format, and (this seems to be the non-relativizing part) you can encode "correct" transitions between configurations in a polynomial-sized boolean formula - this uses a Cook-Levin-style step.

The intuition that I've developed is that non-relativizing results are ones that poke around with the nitty gritty of Turing Machines, and the step where TQBF is shown to be complete for PSPACE is where this poking around happens - and the arithmetization step could've only happened because you had an explicit boolean formula to arithmetize.

This appears to me to be the fundamental reason that IP=PSPACE is non-relativizing; and the folklore mantra that arithmetization techniques don't relativize seems to be a byproduct of that: the only way to arithmetize something is if you have a boolean formula that encodes something about TMs in the first place!

Is there something I'm missing? As a subquestion - does this mean all results that use TQBF in some way also do not relativize?

Any answer to a question of the form, "What is the real reason that..." will necessarily be somewhat subjective.  However, for the particular case of IP = PSPACE, I think that a pretty good case can be made that arithmetization is indeed the key, by observing that while IP = PSPACE does not relativize, it does algebrize in the sense of Aaronson and Wigderson.  As they explain in their paper, roughly speaking, a complexity class inclusion ${\cal C} \subseteq {\cal D}$ algebrizes if ${\cal C}^A \subseteq {\cal D}^{\tilde A}$ for all oracles $A$ and all low-degree extensions $\tilde A$ of $A$.  In particular, they show that the inclusion PSPACE $\subseteq$ IP algebrizes, even though it doesn't relativize.

  The intuition that I've developed is that non-relativizing results are ones that poke around with the nitty gritty of Turing Machines

This is not a bad intuition, but I think that the Aaronson-Wigderson result shows that the IP = PSPACE proof pokes around in a rather limited way, and certainly not in a sophisticated enough way to prove P $\ne$ NP, since Aaronson and Wigderson also show that non-algebrizing techniques will be required to separate P from NP.


Analogies between VNP and NP Valiant introduced the class VNP with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as cited by Fortnow.

  What is the intuition that VNP and NP are similar/ analogous in some way? Is there analysis/ results since its introduction that point toward or away from this analogy? Has/ can the study of VNP lead to some insights on NP?

The basic idea is that summing over all Boolean strings (VNP) is like counting the solutions to an NP problem. Even from this perspective, one sees that VNP is more like #P than NP. This is also true as permanent is complete for both VNP and #P. Indeed, the Boolean part of VNP is essentially just #P/poly (it contains #P/poly and is contained in $\mathsf{FP}^{\mathsf{\# P}}/poly$ [Burgisser].

Valiant already observed that $\mathsf{P/poly} \neq \mathsf{NP/poly}$ implies $\mathsf{VP} \neq \mathsf{VNP}$ over $\mathbb{F}_2$, so separating VP from VNP is necessary on the way to proving that NP is not in P/poly. Not only is it a formally necessary first step, but because of the connection between VNP and counting solutions to NP problems, one could imagine that a better understanding of VNP would yield some insight into NP as well.


Error correction that adapts to different error rates Say we have $N$ bits that we'd like to store in an $M$-bit error correcting code, where $M > N$.  Given $\epsilon > 0$, as long as $N > N_0(\epsilon)$ we can recover the original bits as long as any $N(1+\epsilon)$ of the $M$ bits are correct.

Now say the bits are ordered in decreasing order of importance.  Can we pick a single $M$-bit code so that if $K > K_0(\epsilon)$ out of the $M$ bits are uncorrupted, we can recover the first $K(1 - \epsilon)$ original bits correctly?  Here the difference is that the code is independent of $K$.

This is impossible as stated.  Consider $M = N, K = N/2$.  Up to $\epsilon$, we're asking to be able to recover the whole input from the whole code, and the first half of the input from either the first half of the code or the second half.  But if we can recover the first half of the input from the first half of the code, this implies we can recover the second half of the input from the second half of the code, and vice versa.  Thus we can recover both halves of the input from the first half of the code, which is impossible.


Multi prover, verifier games and PCP theorem This question came up while I was going through Siu On Chan's paper on Approximation Resistance. My question is not really related to the paper though.  I also guess that this is more of a reference request kind of question (preferably some lecture notes or surveys). I hope what follows helps putting the question in perspective, so please bear with me.

I recently started studying up the literature on PCPs and inapproximability and my knowledge is small. I know the proof of PCP theorem. The proof I read is Dinur's proof as presented in Arora Barak. All the while, I saw the two contrasting views of the PCP theorem

(i) the prover, verifier view and,
(ii) the view related to a deciding a gap instance of a CSP (for some constant gap).

Now, my question is the following. While going through Siu's paper, I got the impression that 2 prover 1-verifier games are relevant to PCP literature. My current knowledge base is so shamelessly small that I do not really understand this. I just know the 2 views I described above and am not comfortable with the multiple provers view.

I mean, why is the value of a game with multiple provers even related to the PCP theorem where you have a single prover and a single verifier? Does the value of a game help you somehow argue about the soundness part?

Thanks

Let me sketch the relation between the PCP theorem and 2-provers 1-round game. For concreteness let's consider the MAX-3-SAT problem. In this problem we are given a 3-CNF formula, and our goal is to find an assignment that maximizes the number of satisfied clauses. This problem is NP-hard, and (the CSP view of) the PCP theorem says that given a satisfiable formula it is NP-hard to find an assignment that satisfies 99% of the clauses.

The 2-provers 1-round game view of PCP theorem says that if we are given a game as an input it is NP-hard to distinguish between the two cases:

YES case: The provers have a strategy that always satisfies the verifier.

NO case: In every strategy of the provers will satisfy the verifier with probability at most $1-\epsilon$ for some constant $\epsilon>0$.

Let us now translate the MAX-3-SAT problem into a 2-provers one round game. That is we show a reduction from MAX-3-SAT to 2P1R-game. The verifier chooses one clause from the formula and one variable from the clause at random. He sends the clause to the first prover, and the variable to the second prover. The first prover replies with an assignment to the three variables in the clause, and the second prover sends an assignment to his variable. The verifier then checks that the assignment of the first prover indeed satisfies the clause, and that the answer of the second prover is consistent with the answer of the first prover.

Now, what is left to show is that this reduction gives a gap problem for the 2-prover 1-round game.

YES case: If the given formula is satisfiable, then the provers have a strategy that will satisfy the verifier. This is easy, they just need to reply according to the satisfying assignment.

NO case: If the provers have a strategy that allows them to win with probability $1-\epsilon$, then there exists an assignment that satisfies at least $1-3\epsilon$ of the clauses. This part is also not hard to prove. Just look at the assignment of the second prover to the variables, and claim that it must satisfy at least $1-3\epsilon$ fraction of the clauses.

I hope it makes sense...


What is the space complexity of CTL model checking? What is the space complexity of the CTL model checking algorithm via labeling without fairness (see e.g. Model Checking by Clarke at al Section 4.1 or Principles of Model Checking by Baier et al Section 6.4) that has time complexity $O(\mathit{propertyFormulaSize} \cdot (\mathit{numberOfStates} + \mathit{numberOfTransitions}))$?

Is there a citable reference?

Details

Is the space complexity of this algorithm $\Theta(\mathit{numberOfStates} \cdot (\mathit{propertyFormulaSize} + \mathit{numberOfTransitions}))$ or smaller, e.g. $\Theta(\mathit{numberOfStates} \cdot (\mathit{propertyFormulaSize} + \mathit{ld}(\mathit{numberOfTransitions})))$ by smartly iterating over the transitions without storing them while sustaining time complexity $O(\mathit{propertyFormulaSize} \cdot (\mathit{numberOfStates} + \mathit{numberOfTransitions}))$?

In general, CTL model checking is P-complete. Since we think that $L\neq P$ (and moreover $NL\neq P$), it is unlikely that an algorithm with logarithmic space exists. It is also unlikely that a sub-polynomial space algorithm exists, for similar reasons of common belief.

I don't know of exact space-optimizations for the problem, but in general - yes, you need to mark each state with a formula, so naively you need the size you suggest. It may be the case that you can reduce the formula by encoding it more succinctly, but it hasn't attracted attention in research.

You can start from this survey for citations.


Formatting decision problems in LaTeX Is there a standard macro package, or just standard set of macros, for
  formatting decision problems in LaTeX?

A decision problem is presented via the data "problem name", "instance", and "question", with the latter always having a yes or no answer.  For example FACTOR has, as an instance, a pair of positive integers (n,p) and has, as its question, "Does n have a factor less that q and greater than one?".  Here is an attempt to format FACTOR in HTML.

FACTOR
Instance: $(n,q) \in \mathbb N \times \mathbb N$
Question: Does $n$ have a factor bigger than one and less than $q$?

In the interest of not reinventing the wheel, I asked google, and found some homegrown macros, each with their own spacing, choice of fonts, and layout.  Has anyone implemented a standard?  Say, a standard journal in complexity theory?

For quite old examples of formatting choices see Karp's classic paper Reducibility among combinatorial problems, starting on page 89 (using the page numbers in the book, not in the pdf file).  The book Computers and intractability by Garey and Johnson also gives many decision problems - see page 25 of the linked text.  I've seen more recent texts where the problem name is in small caps, and the boiler-plate on the instance and question lines is in italics.

For a more recent example, I found a macro written for use by students in a cs class - see lines 95 to 116.

Finally - I tried asking over at the TeX Stack Exchange site, but didn't get any answers.  I've deleted the question there, and moved it over here.

For some obscure reason everyone is answering in comments, so let me comment in an answer.

While I am not aware of any standard macros for this, I'm partial to the G&J format (which is basically the format you use in the question. Namely,

  PROBLEM NAME
  INSTANCE: description of instance
  QUESTION: description of problem


Covering a set of intervals (I was redirected from mathoverflow in asking this)

Hello,
I'm trying to determine if the following problem is solvable in polynomial time:  given a collection of $n$ half-open intervals $[s_i, t_i)$ having integer endpoints, is it possible, for given integers $k$ and $L$, to find a subset $S$ of these intervals that are "exactly" covered with $k$ half-open intervals of length $L$, with each of these $k$ "covering intervals" only covering one of the given intervals at any particular instant?  Put another way, by William Thurston, "given a finite set of half-open intervals, is there a subset of them so the sum of their characteristic functions can be expressed as a sum of characteristic functions of intervals of length $L$"?

For example, given the four intervals $[0,3), [2,4), [3, 6), [3, 8)$ with $k=2$ and $L=4$, we find that $[0,3)$, $[2,4)$, and $[3,6)$ can be exactly covered by the two intervals $[0,4)$ and $[2,6)$.  I hope I've stated this clearly.  One thing I've tried is a reduction via the subset-sum problem, but the fact that I'm dealing with intervals complicates it in a way I'm not comfortable with.  Thanks!

A clarification about "only covering one of the given intervals at any particular instant":  what I mean is that, for example, the interval $[0,5]$ could be said to cover either $(0,3)$ or $(0,4)$, but not both simultaneously.

You're right to look for a reduction from the subset-sum problem. The subset problem is to find a subset $S'$ of $S$ such that $\Sigma_{s' \in S'} s' = t$. But this can be reduced to your interval cover problem with intervals $\{(0, s) : s \in S\}$, $k = t$, $L = 1$. Therefore the interval cover problem is NP-hard.

PS Why don't you make all the intervals, input and output, half-open at the same end? That way you eliminate the finite set of points at which the sum of indicator functions is different.


Is there parallel algorithm for 3SAT Is there any parallel algorithms or approximation algorithms for 3SAT?

Take a look at this question for some pointers to SAT solvers. Specially, there's a link to SAT Competition, in which you can find parallel SAT solvers (like ManySAT or gNovelty2+).


Label-disjoint paths in directed graphs Checking if there are two edge-disjoint paths from $s$ to $t$
in a given undirected graph $G$ is in P via a standard solution based on maxflow.
I am interested in the complexity of the following edge-labeled version and
whether it is in P or not.

Input: An edge-labeled graph $G$ and two vertices $s$ and $t$ satisfying the following condition:

  every label in $G$ occurs exactly twice.

Output: are there two label-disjoint paths in $G$ from $s$ to $t$?

Two paths are label disjoint iff
the labels appearing in the respective paths are disjoint.

Example:
suppose $G$ is given by $(s, a, v1)$, $(v1, b, t)$, $(s, b, v2)$, $(s, c, v2)$, $(v2, a, t)$, $(v2, c, t)$. Then $s-a-v1-b-t$ and $s-c-v2-c-t$ are two label-disjoint simple paths from $s$ to $t$.

The problem becomes NP-complete ... this is a "graphical" :-) reduction from 3-SAT ... it should be self-explanatory (... if not let me know).

Two notes:

+X1a, -X1a, +X1b, -X1b,...,+X2a,-X2a, ...,dum1,...,dum4 are all distinct labels;
in the figure  each label appears $\leq 2$ times; but it is straightforward to make each label appears exactly 2 times adding some dum nodes+edges+labels to pair them up.


Is there a theory to answer "the simplest program to solve a problem"? To answer "what problems can be solved by computing", we developed the theory of computability. For the problems that are computable, is there a theory to answer the question "is the program I get the simplest one"?

I do not think computational complexity answer the question. I think it considers how long we need (though measured abstractly).

I am not sure whether algorithmic information theory answer the question. It seems that the theory talks about size, where the equivalence of minimal size and simplest is not obvious to me (well, at least they feel different to me).

I think the theory should at least define "simple" or "simpler than" relation.

I am now convinced that I should look into Kolmogorov Complexity. However, I would like to explain what was in my mind when I was asking the question.

When I improve a program, I try to reduce unnecessary connections between different parts of the program (maybe re-dividing parts so that there can be less or weaker connections). Since the connections are reduced, the program feels "simpler". Hence the choice of the word "simple" when I am phrasing the question. It is very likely the size of the program also decreases, but that is a good side effect, not the main goal. Obviousely, the improving process cannot go forever. There is a point that I should stop. If, only by considering the "structure" (sorry for another undefined concept) or "relation", can I convince myself that nothing more can be done?

Here contains better description of my notion of complexity.

Olaf Sporns (2007) Complexity. Scholarpedia, 2(10):1623

This problem is studied in Algorithmic Information Theory. What you're defining is called Kolmogorov-Chaitin complexity.

http://en.wikipedia.org/wiki/Kolmogorov_complexity

And it seems that the notion of simplicity that you're requiring can be formalized via the notion of complexity measure, which is formalized by Blum's axioms.

http://en.wikipedia.org/wiki/Blum_axioms

It seems also that it is possible to generalise Kolmogorov's complexity to take
other complexity measures into consideration. See reference below. (Wikipedia's article on Kolmogorov complexity addresses this issue.)

Burgin1990- Generalized kolmogorov complexity and other dual complexity measures
Cybernetics and Systems Analysis Volume 26, Number 4, 481-490


Who said: "There is no central arbiter of truth in open distributed systems." Can anyone give me a reference to the origin of the statement "There is no central arbiter of truth in open distributed systems."

Possibly it was Carl Hewitt in "The Challenge of Open Systems" Byte Magazine. April 1985. Can anyone confirm this?

Thanks

The exact quotation seems to be:

  "Pluralism: There is no central arbiter of truth in the system."

See:

http://archive.org/stream/byte-magazine-1985-04/1985_04_BYTE_10-04_Artificial_Intelligence#page/n237/mode/2up

(p. 239, 2nd bullet point.)


Subset-sum-difference problem Consider the following problem:

SUBSET-SUM-DIFFERENCE: Let $S=\{s_1,\dots,s_n\}$ be a set of $n$ integers and $t$ be a "target" integer. Are there two disjoint subsets of $S$ (call them subsets $I$ and $J$) such that $\sum_{i \in I}s_i - \sum_{j \in J} s_j=t$.

The Meet-in-the-Middle algorithm will solve this problem in $\Theta(3^{n/2})$ time. Is there an exact and deterministic algorithm which solves this problem in $o(3^{n/2})$ time?

Maybe.

Becker, Coron, and Joux [EUROCRYPT 2011 describe an algorithm to solve random hard instances of Subset Sum (in fact, the more general Knapsack problem) in $\tilde{O}(2^{0.291n})$ time, beating the "meet in the middle" time bound $\tilde{O}(2^{n/2})$ by Shamir and Schroeppel [SICOMP 1981].  (Here, $\tilde{O}(f(n))$ is standard shorthand for $O(f(n)\operatorname{polylog} f(n))$.)

More recently, Dinur, Dunkelman, Keller, and Shamir [Crypto 2012], which establish better time-space tradeoffs (but do not improve worst-case running times) for a general class of cryptography problems that includes Knapsack.  Becker's techniques rely crucially on the observation that addition is both commutative and associative, but Dinur's techniques do not; for example, they also derive faster algorithms for solving random hard instances of permutation puzzles like the Rubik's cube.

It seems likely that Dinur's techniques would imply faster algorithms for (at least random hard instances of) your problem.


The Stalin compiler brutally optimizes, but how? J.M. Siskind's research statement states:

Stalin is an optimizing compiler for Scheme that performs whole-program static analysis and uses the results of that analysis to generate extremely efficient code. Stalin utilizes a large collection of static-analysis techniques. It performs a novel form of polyvariant flow analysis that uses iterated monovariant flow analysis to perform flow-directed splitting: cloning of specialized copies of procedures and per-call-site assignment of targets to such clones. It uses the results of flow analysis to perform life-time analysis, escape analysis, points-to analysis, and must-alias analysis. These analyses support a novel form of lightweight closure conversion that eliminates most closure slots, using techniques such as variable globalization and localization, compresses the static backchain, and usually eliminates most closures from programs. It also uses the above analyses to support flow-directed region-based storage management, where run-time garbage collection is replaced with static allocation and deallocation on a per-abstract-value and per-program-point basis. It also performs flow-directed lightweight CPS conversion, using extensions of the techniques pioneered with Screamer, to support extremely efficient first-class continuations. Finally, it supports flow-directed inlining and low-level representation selection to choose the implementation (or nonimplementation) of tags, tag checking, and tag dispatching on a per-abstract-value and per-program-point basis. This eliminates most run-time tags, tag checking, tagging, tag stripping, tag dispatching, boxing, and unboxing from programs. These analyses and optimizations allow Stalin to generate extremely efficient code that outperforms all other Scheme compilers by factors ranging between two and one hundred, particularly for numerically intensive code. Stalin often generates code that outperforms handwritten c and Fortran code.

I was able to find the following very interesting paper on closures/function calls implementation: Flow-Directed Lightweight Closure Conversion. I've also emailed the author to ask about the papers on the other topics, which are mentioned as to be written in the closure conversion paper:

Siskind, J. M. 2000a. Flow-directed lightweight CPS conversion. In preparation.
Siskind, J. M. 2000b. Flow-directed polyvariance. In preparation.
Siskind, J. M. 2000c. Flow-directed representation selection. In preparation.
Siskind, J. M. 2000d. Flow-directed storage management. In preparation

Unfortunately, he never got around to writing those papers. My question to you is: are there any alternative or related papers that cover these topics? I'm very interested to learn how Stalin (or other compilers) can compile such a high level language as Scheme that is garbage collected, dynamically typed, supports first class functions, and even first class continuations, can be statically compiled to such efficient code. Although papers on flow analysis are quite abundant, papers on using the results of such an analysis to do the optimizations mentioned above aren't.

The key is probably the fact that it uses whole program analysis and whole program optimisation. The more you know about a how a program behaves, the more you can specialise and inline and make performant.

The MLton compiler for Standard ML does a similar thing (http://mlton.org/). There is one presentation (at least) about it: http://mlton.org/pages/References/attachments/060916-mlton.pdf.

Earlier work was done by Craig Chambers and his group at the University of Washington (for example: http://www.cs.washington.edu/research/projects/cecil/www/pubs/jdean-thesis.html). This was done in the context of Self and later Cecil/Vortex.

There's probably more work in the Scheme/Lisp community. You probably want to consider googling "whole program optimisation".


APX Hardness implies no QPTAS? So, a quick search on the web led me to believe that "APXHardness implies that no QPTAS exist for a problem unless [some complexity class] is included in some [other complexity class]" and it is well known too! It seems like everybody knows this except for me. Unfortunately, no reference to support this statement is given. I have two questions:

What is the strongest version of this statement that is currently known?
A reference? Please?

Thanks in advance.

Chandra Chekuri's answer suggests that a $QPTAS$ for a $APX$-hard problem implies $NP\subseteq QP$. Can anyone explain why it is true, or preferably give a reference for that? In other words, why does quasi polynomial time approximability imply QP time solvability?

APX-Hardness implies that there is a $\delta > 0$ such that the problem does not admit a $(1+\delta)$-approximation unless $P=NP$. Clearly this rules out a PTAS (assuming $P \neq NP$). As for QPTAS, it will rule it out unless you believe that NP is contained in quasi-polynomial time. As far as I know, that is the only reason why APX-Hardness rules out a QPTAS.

Since a couple of people asked more details, here are some more. APX-Hardness for a minimization problem P implies that there is a fixed $\delta > 0$ and a polynomial-time reduction from 3-SAT to P such that a $(1+\delta)$-approximation for P allows one to decide whether the 3-SAT formula is satisfiable or not. If there is a QPTAS for P we can obtain for any fixed $\delta > 0$ a $(1+\delta)$-approximation in time say $n^{O(\log n)}$. But this implies that we can decide whether a 3-SAT formula is satisfiable in $n^{O(\log n)}$ time which in turn implies that NP is in QP.


state-of-the-art bit complexity of the determinant I'm trying to understand the full bit-complexity of computing the determinant of an $n\times n$ integer matrix, with each entry represented by $M$ bits.
I would like to know what is the state-of-the-art bit-complexity.
As far as I could find, the two possible candidates are:

(1) The low-depth circuits, due to Csansky [1976], and Berkowitz [1984], but these, despite having $log^2(n)$ depth, require some $n^4$ bit operations.

(2) The Bunch and Hopcroft [1974] algorithm, which takes any black-box algorithm for integer matrix multiplication, and produces an algorithm for the determinant using the same $\textbf{arithmetic}$ complexity.  Since any two $M$-bit integers can be multiplied in $M \cdot log^2(M)$ operations, and the largest value during the computation can be as large as $2^{M n}$, it seems that its bit-complexity is $\tilde{O}(M n^{\omega+1})$, where $\omega$ is the state-of-the-art matrix product coefficient $< 2.38$.

Is there a better upper-bound?

Storjohann designs a Las-Vegas algorithm with $\tilde O(n^\omega M)$ bit operations
http://dx.doi.org/10.1016/j.jco.2005.04.002

Prior to this, Kaltofen and Villard gave improved algorithms, see
http://lara.inist.fr/bitstream/handle/2332/850/LIP-RR2003-36.pdf%3Fsequence%3D1


Is there such a thing as control logic complexity classes? I am currently reading the paper "On the computational complexity of Algorithms" by J. Hartmanis and R. E. Stearns ( http://www.jstor.org/pss/1994208 )

It includes a proof that any $T$-computable sequence is also $\lceil kT \rceil$-computable, where $k$ is a computable, positive real number, $T$ a time-function and $\lceil kT \rceil$ denotes the smallest integer $m$ such that $m \ge kT$.

The proof idea is to use a (multitape) TM that has a head that can read 2 symbols at once, while storing internally the symbol to the left and right of that head, so that the new TM can simulate 2 steps of a normal (multitape) TM in only once step. By doing the same trick on the new TM using induction, one can prove 1/2k speed-up.

I have two questions, which revolve around the same thing:

First of all, can I extend this idea and use a head so large that reads the entire input at once? That would require to save a super-constant number of symbols internally in the TM. Would that be a violation of the model?
Reflecting to my first question, whatever the answer is : Are there "complexity" classes that restraint the TM's control logic somehow? e.g. allowing up to a specific number of states or for a specific structure of the automaton?

One should be careful about having a head that large. If your tape head can read the entire input, then technically speaking all inputs can be decided in one step. This is because "making a head so large you can read the input" is formally equivalent to making the tape alphabet so large that it contains all input strings. But if this is the case then your entire function can be encoded in the transition table of the Turing machine, so every input can be decided in one step. It makes perfect sense to have a superconstant number of symbols in the TM, but when you do that you are no longer talking about "uniform" computation (fixed-size programs) but rather "non-uniform" computation, where the size of the program can grow with the input length. In complexity theory, non-uniform computation is typically studied in the language of circuit complexity: having a polynomial-size Boolean circuit family for solving a problem is equivalent to having a "polynomial-size transition table" for solving a problem with a polynomial-time TM, and the general feeling is that circuits are more natural to reason about. But it's possible that the TM perspective could be useful too.
Allowing a specific number of states or specific structure probably will not change the definitions of the standard complexity classes. This is because there are universal Turing machines which have a small number of states and/or simple structures in the transition table, which can simulate arbitrary Turing machines with polynomial time overhead. (Sorry, don't have references at the moment.) Restricting yourself to these machines does not change the overall difficulty, up to polynomials in the running time.


Are there any applications of techniques in real analysis to theoretical computer science? I have looked far and wide for such applications and have mostly turned up short. I can find plenty of applications of topology and similar structures on countable (or uncountable) sets, but rarely do I actually find uncountable sets as the object of study by computer scientists, and therefore leading up to the need for techniques from analysis.

Here are two related courses:

Analytical methods in combinatorics and CS by Ehud Friedgut at University of Toronto (2009),
Analytical Methods in Combinatorics and Computer-Science by Irit Dinur and Ehud Friedgut at Hebrew University (2006).

Also check Ryan O'Donnell's notes for his book:

Analysis of Boolean Functions by Ryan O'Donnell.

and the links on the top right corner.


How efficient are DPLL-based SAT-solvers on satisfiable instances of PHP? We know that DPLL based SAT-solvers fail to answer correctly on unsatisfiable instances of $\mathrm{PHP}$ (pigeon hole principle), e.g. on "there is a injective mapping from $n+1$ to $n$":

$$\mathrm{PHP^{n+1}_{n}} := \left(\bigwedge_{i\in[n+1]} \ \bigvee_{j\in[n]} \ p_{i,j}\right) \wedge \left(\bigwedge_{i\neq i'\in[n+1]} \ \bigwedge_{j\in[n]} \ (\lnot p_{i,j} \vee \lnot p_{i',j})\right)$$

I am looking for results about how they perform on satisfiable instances of $\mathrm{PHP}$, e.g. on "there is a injective mapping from $n$ to $n$".

Do they find a satisfying assignment quickly on such instances?

On satisfiable instances of $PHP$, DPLL based SAT solvers will furnish a satisfying assignment in linear time.

To see why, observe how the CNF encoding of an unsatisfiable instance of $PHP$ with $n$ holes and $n + 1$ pigeons is sintactically identical to an instance of $k = n$ Graph Coloring, where the input graph is a clique of $n + 1$ vertices.

Similarly, the CNF encoding of a satisfiable instance of $PHP$ with $n$ holes and $n$ pigeons is sintactically identical to an instance of $k = n$ Graph Coloring, where the input graph is a clique of $n$ vertices.

Now, coloring a clique of $n$ vertices with $n$ colors is straightforward: scan the vertices, and assign to each of them one of the remaining colors (already assigned colors are automatically ruled out by the clique-ness of the graph, using unit propagation). Whatever of the remaining colors you choose, it will be good and will lead you to a satisfying assignment.

From the DPLL solver point of view: each time it will try to guess the boolean value of a variable $v_i$, such value will be right (whatever it is), because there will certainly be a satisfying assignment in which variable $v_i$ has the guessed value. Unit propagation will do the rest of the job, by guiding the solver along the satisfying path (in other words: by preventing it to guess wrong values).

The search then proceeds one variable after the other, linearly, each time making the correct guess.


Why is it important to prove that a problem is NP-complete? Am I correct in understanding that proving a problem NP complete is a research success? If so why?

Ali, good question.

Suppose you want to show that some problem P is computationally hard.  Now, you could conjecture that P is hard just based on the fact that we don't have any efficient algorithms for it yet.  But this is rather flimsy evidence, no?  It could be that we have missed some nice way to look at P which would make it very easy to solve.  So, in order to conjecture that P is hard, we would want to accumulate more evidence.  Reductions provide a tool to do exactly that!  If we can reduce some other natural problem Q to P, then we have shown P is at least as hard as Q.  But Q could be a problem from some completely different area of mathematics, and people may have struggled for decades to solve Q also.  Thus, we can view our failure to find an efficient algorithm for Q to be evidence that P is hard.  If we have lots of such Q's from many different problem domains, then we have a huge body of evidence that P is hard.

This is exactly what the theory of NP-completeness provides.  If you prove your problem to be NP-complete, then you have tied its hardness to the hardness of hundreds of other problems, each of significant interest to various communities.  Thus, morally speaking, you can be assured that your problem is indeed hard.


Chromatic number of planar graph with girth at least k The four-color theorem claims that, any loopless planar graph is 4-colorable. However, it is NP-Complete to determine the chromatic number of planar graphs, even for those 4-regular ones.

Girth is the length of the smallest cycle in a graph. Planar graph with girth at least 4, i.e., triangle-free, is 3-colorable, shown in paper.

Question:
Is it NP-Complete to find a 3-coloring of a planar graph with girth at least $k$, where $k$ is a fixed integer?  Is there any result about this topic?

I find another post "graph families which have polynomial algorithms for chromatic number" might be related.

This paper: http://www.mimuw.edu.pl/~kowalik/papers/grotzsch-full.pdf
gives an $O(n\log{n})$-time 3-colouring algorithm for triangle-free planar graphs, improving on Thomassen's $O(n^2)$-time constructive proof.

I'm not exactly sure, but does this answer your question?


Concepts in theoretical CS that would be approachable ages 8-14 Guessing it's unlikely a common question, but wondering if anyone has seen material that was clearly made to address this audience in a meaningful way.

Computer Science Unplugged addresses kids (and teachers) in primary school.


Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs) What are some examples of problems with quasi-polynomial time ($QP$) algorithms that could conceivably be in $P$. In other words, they are in $QP$ for no obvious reason other than no one has found a polynomial-time algorithm?

This question is motivated by the recent graph isomorphism result (which is a valid answer to this question)

Some non-examples are

Finding a clique of size $\log^{100} n$ in a graph
Finding a path of size $\log^{100} n$ in a graph
Solving k-sum for $k=\log^{100} n$
Minimum dominating set in a tournament

Any of these problems being in $P$ would violate the exponential time hypothesis (ETH).

Group Isomorphism! Although Ricky Demer gave lots (though certainly not all) details on this, there is an important point I want to highlight, esp. given the stated motivation for the question, namely:

  Putting Group Isomorphism into $\mathsf{P}$ is a key obstacle to putting Graph Isomorphism into $\mathsf{P}$

Group Isomorphism (when given by multiplication tables) reduces to Graph Isomorphism, so the above was technically always true. But when Graph Iso was way up at $2^{\tilde{O}(\sqrt{n})}$ it was so far from Group Iso's $2^{(\log n)^2}$ that there were clearly other obstacles in the way. If Graph Iso is in time $2^{(\log n)^{O(1)}}$, Group Isomorphism is then a much more immediately relevant obstacle to putting Graph Isomorphism into $\mathsf{P}$. In particular, this would suggest that Babai's algorithm handles much [1] of the combinatorics of GI, and the problem is now down to hard algebra. (Not that there's not hard algebra in GI, but GroupIso is by definition about algebra.)

[1] I won't say "all" of the combinatorics, because the exponent in Babai's algorithm is most likely $> 2$, which would still leave a gap between GI and GroupIso. Also because there may still be some combinatorics sitting inside the algebra of GroupIso...


Theoretical study of coordinate descent methods I'm preparing some course material on heuristics for optimization, and have been looking at coordinate descent methods. The setting is here a multivariate function $f$ that you wish to optimize. $f$ has the property that restricted to any single variable, it is easy to optimize. So coordinate descent proceeds by cycling through the coordinates, fixing all but the chosen one and minimizing along that coordinate. Eventually, improvements slow to a halt, and you terminate.

My question is: is there any theoretical study of coordinate descent methods that talks about convergence rates, and properties of $f$ that make the method work well, and so on ? Obviously, I'm not expecting fully general answers, but answers that illuminate cases where the heuristic does well would be helpful.

Aside: the alternating optimization technique used for $k$-means can be seen as an example of coordinate descent, and the Frank-Wolfe algorithm seems related (but is not a direct example of the framework)

(Edit notes: I reorganized this after freaking out at its length.)

Literature on coordinate descent can be a little hard to track down.  Here are some reasons for this.

Many of the known properties of coordinate methods are captured in umbrella theorems for more general descent methods.  Two examples of this, given below, are the fast convergence under strong convexity (hold for any $l^p$ steepest descent), and the general convergence of these methods (usually attributed to Zoutendijk).
Naming is not standard.  Even the term "steepest descent" is not standard.  You may have success googling any of the terms "cyclic coordinate descent", "coordinate descent", "Gauss-Seidel", "Gauss-Southwell".  usage is not consistent.
The cyclic variant rarely receives special mention.  Instead, usually only the best single choice of coordinate is discussed.  But this almost always gives the cyclic guarantee, albeit with an extra factor $n$ (number of variables): this is because most convergence analyses proceed by lower bounding the improvement of a single step,and you can ignore the extra coordinates.  It also seems difficult to say anything general about what cyclic buys you, so people just do the best coordinate and the $n$ factor can usually be verified.

Rate under strong convexity. The simplest case is that your objective function is strongly convex.  Here, all gradient descent variants have the rate $\mathcal O(\ln (1/\epsilon))$.  This is proved in Boyd & Vandenberghe's book.  The proof first gives the result for gradient descent, and then uses norm equivalence to give the result for general $l^p$ steepest descent.

Constraints. Without strong convexity, you have to start being a little bit careful.  You didn't say anything about constraints, and thus in general, the infimum may not be attainable.  I'll say briefly on the topic of constraints that the standard approach (with descent methods) is to project onto your constraint set each iteration to maintain feasibility, or to use barriers to roll the constraints into your objective function.  In the case of the former, I don't know how it plays with coordinate descent; in the case of the latter, it works fine with coordinate descent, and these barriers can be strongly convex.

More specifically to coordinates methods, rather than projecting, many people simply make the coordinate update maintain feasibility: this for instance is exactly the case with the Frank-Wolfe algorithm and its variants (i.e., using it to solve SDPs).

I'll also note briefly that the SMO algorithm for SVMs can be viewed as a coordinate descent method, where you are updating two variables at once, and maintaining a feasibility constraint while you do so.  The choice of variables is heuristic in this method, and so the guarantees are really just the cyclic guarantees.  I'm not sure if this connection appears in standard literature; I learned about the SMO method from Andrew Ng's course notes, and found them to be quite clean.

General convergence guarantee. What I know in this more general setting (for coordinate descent) is much weaker.  First, there is an ancient result, due to Zoutendijk, that all these gradient variants have guaranteed convergence; you can find this in the book by Nocedal & Wright, and it also appears in some of Bertsekas's books (at the very least, "nonlinear programming" has it).  These results are again for something more general than coordinate descent, but you can specialize them to coordinate descent, and then get the cyclic part by multiplying by $n$.

More specifically to cyclic coordinate descent, there's a paper by Luo & Tseng titled "On the convergence of the coordinate descent method for convex differentiable minimization".  These results require the infimum to be attainable. There are no rates here, only convergence guarantees, but these results have been applied to some more specialized settings to get rates; for instance, in boosting (in the special case that the infimum is attainable), Warmuth, Mika, Raetsch, and Warmuth ("on the convergence of leveraging") were able to show rates of $\mathcal O(\ln(1/\epsilon))$.

There are some more recent results on coordinate descent, I've seen stuff on arXiv.  Also, luo&tseng have some newer papers.  but this is the main stuff.

More convergence rates in the special case of boosting. Due to its importance, there has been other specialization in the case of boosting.  This is a pretty severe special case because your objective can be written $\sum_{i=1}^m g(\langle a_i, \lambda\rangle)$ where $g$ is a (convex) univariate function and the $(a_i)_1^m$ are fixed vectors ($\lambda$ is the optimization variable).  Bickel, Ritov, and Zakai ("some theory for generalized boosting algorithms") showed you can get $\exp(1/\epsilon^2)$ in general, and there are more recent results by other people showing $\mathcal O(1/\epsilon)$.  The difficulty in these is that the infimum is not assumed attainable.

The issue with exact updates. Also, it is very often the case that you do not have a closed form single coordinate update.  Or the exact solution may simply not exist.    But fortunately, there are lots and lots of line search methods that get basically the same guarantees as an exact solution.  This material can be found in standard nonlinear programming texts, for instance in the Bertsekas or Nocedal&Wright books mentioned above.

Vis a vis your second paragraph: when these work well.
First, many of the above mentioned analyses for gradient work for coordinate descent.  So why not always use coordinate descent?  The answer is that for many problems where gradient descent is applicable, you can also use Newton methods, for which superior convergence can be proved.  I don't know of a way to get the Newton advantage with coordinate descent.  Also, the high cost of Newton methods can be mitigated with Quasinewton updates (see for instance LBFGS).

Second, the place where these methods shine is where the presumed solution is sparse (in the $l^0$ sense).  Of course, there are NP-hardness issues with this kind of sparsity, but the point is that if you run $k$ iterations, you have $k$ nonzero entries.  These facts generalize to, say, using coordinate methods with SDP solvers, where each iteration you throw in a rank 1 matrix, thus with $k$ iterations you have a rank $k$ iterate.  There is a great paper on this topic, by Shalev-Shwartz, Srebro, and Zhang, titled "trading accuracy for sparsity in optimization problems with sparsity constraints".  Most specifically to the second paragraph of your question, this paper gives further properties on $f$ that allow fast convergence and good sparsity (true to its title).


Efficiently picking free position from array with uniform probability. For each array position it is known if position filled or not.

How efficiently pick one free position with uniform probability?

That task happen during implementation of AI by Monter-Carlo method for board game.

I have in mind:

uniformly pick random index of array and check position, repeat until success - this method is extremely bad for mostly filled arrays
count free positions, uniformly pick random number from 1 to count and scan for that free position - this method require 2 arrays scans

Is it possible uniformly pick free position with only one scan?

From my intuition this algorithm produce biased solution toward clustered arrays:

uniformly select index and scal to one side until find free position

What if for each free position picking generate random permutation without cycles and travel across all elements by uniformly choosing index and recursively applying permutation until free position was found? I don't know if this algorithm leads to uniform picking. I don't know how to represent computationally efficient subset of permutations. This way may produce one pass solution...

Reservoir sampling can be used to uniformly pick a "free position with only one scan".


Improved lower bounds or upper bounds on union-find structures since Tarjan? In 1979, Robert Tarjan published "A Class of Algorithms Which Require Nonlinear Time To Maintain Disjoint Sets", which proved an upper bound of $O(m \alpha(n))$ time on the time complexity of performing $m$ operations on a disjoint-set forest with union-by-rank and path compression, assuming there are $n$ nodes. He also proved a matching lower bound on any data structure for this problem in a pointer machine.

Since this paper was published, has anyone devised an data structure that runs in $o(m \alpha(n))$ for this problem? (Such a data structure would have to rely on techniques that don't work on a pointer machine.) Or are there any new lower bounds on non-pointer-machines?

There's a matching lower bound in the cell probe model (with a logarithmic number of bits per memory cell); see Fredman and Saks, "The cell probe complexity of dynamic data structures", STOC 1989.


How to estimate the probability of distribution of a variable in a Constraint Satisfication Problem Consider that we have a state space of n random variables, for simplicity, the variable value can be 0 or 1. Each variable has its probability distribution when it is not constrained, also for simplicity, it can be a uniform distribution (50% probability for 0 and 50% for 1). And there is a set of constraints over the variables, thus in the constrained state space, the actual probability distribution of each variable will skewed. For example, if we have two variables a,b and a constraint a=0->b=1, the actually probability that b=0 will be 1/3 compared to 0.5 when unconstrained.

I am wondering if there are any results on estimating the probability distribution of the random variables under a set of constraints. The golden answer of the probability distribution could be derived by using the SAT solver to get all the solutions and then computing the statistics, which is prohibitively computationally expensive. Thus I am wondering if there is any way to do a fair estimation on that.

If the SAT instance has a unique solution then you are asking for the actual solution. Given the Valiant–Vazirani randomized reduction from SAT to unique SAT, if there was a way of efficiently estimating the probability distribution of variables then you could use it to solve SAT.


What applications of Cantor space are there? Are there well-established applications of the Cantor space ($2^\omega$) in computer science, other than those connected with computable real arithmetic?

John Tucker's page Computation on Topological Data Types mentions applications of the general area in signal processing, 3d graphics, and semantics of process algebras: have these applications been fruitful?

It is used heavily in algorithmic information theory. For example, if you want to define random sequence with respect to a particular measure, you should first define this measure on Borel sets of cantor space.

Compactness of Cantor tree is used implicitly or explicitly in compactness arguments in combinatorics (in particular, it is used in the proof of compactness theorem for boolean functions).


Is this covering problem NP-hard? Given a rectangular region $R$ and a set $D$ of $n$ disks such that the union of all disks in $D$ cover the entire rectangular region $R$, the objective is to find the minimum cardinality set $D'$ subset of $D$ such that the union of all disks in $D'$ cover the entire $R$.
I believe that this problem is NP-hard, but did not find any reference. can somebody help me to find the one or reduction from an NP-hard problem.

If I arrange the disks into a spiral pattern then the problem is NP-hard. It may be even harder in your general case. This would be a variation on the polygon covering problem.

See https://en.wikipedia.org/wiki/Polygon_covering


Is there a generalization of the GO game that is known to be Turing complete? Is there a generalization of the GO game that is known to be Turing complete?

If no, do you have some suggestions about reasonable (generalization) rules that can be used to try to prove that it is Turing complete?  The obvious one is that the game must be played on an infinite board (positive quadrant). But what about in-game play and end game conditions?

Related:  Rengo Kriegspiel, a blindfolded, team variant of Go, is conjectured to be undecidable.

http://en.wikipedia.org/wiki/Go_variants#Rengo_Kriegspiel

Robert Hearn's thesis (and the corresponding book with Erik Demaine) discuss this problem.  They prove other problems undecidable through "TEAM COMPUTATION GAME", which is reduced directly from Turing machine acceptance on empty input (see Theorem 24 on page 70 of the thesis).  So it seems to me that such a reduction would imply Rengo Kriegspiel is Turing complete.

On the other hand, their discussion says that this reduction would be very difficult (see page 123). So while this is a potential avenue, it appears that it has been looked into previously.


Complexity class separations without hierarchy theorems Hierarchy theorems are fundamental tools. A good number of them was collected in an earlier question (see What hierarchies and/or hierarchy theorems do you know?). Some complexity class separations directly follow from hierarchy theorems.  Examples of such well known separations: $L\neq PSPACE$, $P\neq EXP$, $NP\neq NEXP$, $PSPACE\neq EXPSPACE$.

However, not every separation follows from a hierarchy theorem. A very simple example is $NP\neq E$. Even though we do not know if any of them contains the other, they are still different, because $NP$ is closed with respect to polynomial transformations, while $E$ is not.

Which are some deeper, unconditional, non-relativized complexity class separations for uniform classes that  do not directly follow from some hierarchy theorem?

I'd love to be shown wrong, but I don't think there are currently any uniform lower bounds that aren't ultimately based on one of the hierarchy theorems. Our current understanding of how to take advantage of uniformity is really quite limited in that sense.

On the other hand, there are many uniform lower bounds that don't follow directly from hierarchy theorems, but use a hierarchy theorem in combination with other clever tricks, techniques, and results, for example:

$\mathsf{CSL} \not\subseteq \mathsf{DTIME}(n)$ [Hopcroft-Paul-Valiant]. They prove that $\mathsf{DTIME}(n) \subseteq \mathsf{DSPACE}(n/\log n)$ (the non-diagonalization part of their proof), and then use the fact that $\mathsf{CSL} = \mathsf{NSPACE}(n)$ in combination with the space hierarchy. Their result + the space hierarchy also implies $\mathsf{DSPACE}(n) \nsubseteq \mathsf{DTIME}(n)$.
Time-space trade-offs for Satisfiability (see, e.g. the introductions of Buss-Williams and references therein)
$\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$ [Paul-Pippinger-Szemeredi-Trotter]. Uses a nontrivial simulation of any deterministic super-linear-time machine by a faster four-alternation machine, in combination with the deterministic time hierarchy.
Uniform lower bounds on the permanant [Allender, Allender-Gore, Koiran-Perifel]
$\mathsf{NEXP} \not\subseteq \mathsf{ACC}^0$ [Williams] (although technically this is a nonuniform lower bound, it uses a bunch of clever ideas in combination with the nondeterministic time hierarchy)


Motivating Talk on Foundations of Cryptography This question is in the same vein as inspirational talk for final year high school pupils. My Ph.D. advisor asked me to give an inspirational talk for new M.Sc. students. The subject is foundations of cryptography, which is best illustrated by Goldreich's book. The talk will take about one hour, and I want to familiarize the students to the main constructs (like one-way functions/permutations, pseudor-random generators, zero-knowledge proofs, encryption/signature schemes, etc.), and solved and unsolved problems in the field.

I want to keep the talk very motivating.
The main problem is two-fold:

Foundations of cryptography needs a very good understanding of the computational-complexity theory. Alas, the M.Sc. students have not passed any course related to this theory.
I need to present some problems as possible topics for an M.Sc. thesis. While there are a lot of unsolved problems in the field, most of them are too hard for an M.Sc. student.

Suggestions are most welcome. In addition, I'm very interested in pointers to similar talks.

Edit: I found the list of Goldreich's students extremely inspiring. I'll be searching for other such lists, but you can help me if you know any similar lists. See also: Demystifying the Master Thesis and Research in General: The Story of Some Master Theses.

Since you can't rely on a knowledge of complexity theory, you have to emphasize the change in paradigm from security by obscurity to security by intractability, by positing the idea that some problems are hard to solve efficiently. This of course elides the many problems associated with the Impagliazzo worlds of intractability, but it gives a flavor of the way modern crypto works.

for ZKP, which are truly awesome, there are many ways to convey the basic ideas intuitively. See for example my answer on MO, as well as the hilarious Ali Baba and the 40 thieves story. While these were originally designed for a younger crowd, they work well at all ages to convey the right intuition.


Representable functions on System T In Proof and Types by Girard et alii. Section 7.4.2, I think that the authors want to show that:

(1) The set of functions definable in System T coincides with the set of
recursive functions whose termination is provable in Peano arithmetic

I don't understand the arguments given to support this thesis.

  In particular, if t is a closed term of type $Int \to Int$ of T, it
  induces a function $|t|:\mathbb{N} \to \mathbb{N}$ defined by:

  $|t|(n) = m$ iff $t \overline{n} \leadsto \overline{m}$ $[\ldots]$

  The functions $|t|$ are clearly calculable: the
  normalization algorithm gives $|t|(n)$ as a function of $n$. So those
  functions representable in T are recursive. Can we characterize the
  class of such functions?

This is how I read this parragraph:

Regarding calculability of $|t|$: using the iff one computes $|t|(n)$ by computing $t \overline{n} \leadsto \overline{m}$. Then $\overline{m}$ syntax can be more complex that an integer  and in order to obtain $m$ one has to rewrite it into a normal form (which should be an integer by the term's type).
Regarding recursivity: I believe that they stress that the normalization begins with term $t \overline{n}$ and thus $|t|$ is indirectly "recursive" in its argument.

The next parragraph seems to confirm this view:

  $[\ldots]$ Seen as a partial algorithm, $|t|$ amounts to looking for
  the normal form, and, in the case where this succeeds, writing it. The
  normalization theorem is thus a proof of program guaranteeing
  termination of all algorithms obtained from $T$.

From here I get the idea that every function written in $T$ is terminating. The next parragraph comes as a surprise though:

  Now, what are the mathematical principles necessary to prove the
  reducibility of a fixed term t?

  to be able to express the reducibility of t and of its subterms: one must be able to write a finite number of reducibilities, which can be
  done in Peano arithmetic (PA)
  to be able to reason by mathematical induction on this finite number of reduciblity predicates; that can again be done in PA, modulo some
  awful coding without significant interest (Godel numbering).

  Summing up, the termination is provable in arithmetic: we say that
  $|t|$ is provably total in PA.

If every function was terminating in System T why would one want to prove in PA specifically?

My question is if you can solve the doubts I presented or if you have your own way of showing statement (1)?

If every term in system T terminates, then $t\overline{n}\leadsto\overline{m}$ for every numeral $n$, and it is easy to show that a normal form $\overline{m}$ in the empty context is a numeral as well (and cannot be more complex!). In addition, it is easy to show, if the term $t\overline{n}$ is normalizing, that computing the normal form $\overline{m}$ can be done by a Turing machine, which is to say that the function $|t|$ is recursive (the terminology is slightly confusing here). This is what is meant by the first paragraph you have quoted.

Furthermore, every fact stated above can be easily proven in $\mathrm{PA}$, except the normalization of an arbitrary term of system T. They go on to show that each individual term $t$ can be shown to be normalizing in $\mathrm{PA}$ wich they suggest implies that every term $t$ defines a function in $\mathrm{PA}$: for every term $t:\mathrm{Int}\rightarrow\mathrm{Int}$, there is a proposition $\phi_t(x,y)$ such that
$$\mathrm{PA}\vdash \forall x\exists! y\phi_t(x,y)$$

and

$$\mathrm{PA}\vdash\phi_t(\overline{n},\overline{m})$$
iff
$$|t|(n)=m$$

As the following pages explain, the other direction is provable as well, that is to every $\phi$ with the first property, there is some term $t$ in system T that corresponds to it.


Consequences of sub-exponential proofs/algorithms for SAT Would there be any major consequences if SAT had at most subexponential unsat proofs or even more strongly, SAT had subexponential-time algorithms?

If SAT had a subexponential-time algorithm, the you would disprove the exponential time hypothesis.

For fun consequences: if you showed that circuit SAT over AND,OR,NOT with $n$ variables and $poly(n)$ circuit gates can be solved faster than the trivial $2^n poly(n)$ approach, then by Ryan Williams' paper you show that $NEXP \not\subseteq P/poly$.


Approaching Number Theory conjectures through Graph Theory i try to find if there was an attempt to prove any famous Number Theory conjectures like Goldbach conjecture or Twin Prime conjectures through Graph Theory.
I have in my mind something like the approach to Fermat Theorem by Andrew Wiles through the Taniyama-Shimura conjecture.
Is there something like that (succesfull or not) using Graph Theory to attack Number Theory?

There are some results proven by graph theory, however I am not sure whether those results are good examples you want. Because number theory has offsprings by cross-breeding with some other fields, like arithmetic combinatorics and additive number theory

In number theory, Szemerédi's theorem that was formerly the Erdős–Turán conjecture is a good example proven by graph theory. (Although it is not necessary to prove by graph theory. Other proofs are using different approaches, e.g., Hillel Furstenberg uses ergodic theory, and Timothy Gowers uses both Fourier analysis and combinatorics)

And this result leads to Green–Tao theorem.


Hard problems on subclasses of planar cubic bipartite graphs Several hard graph problems remain hard on planar cubic bipartite graphs. They include Hamiltonian cycle problem and perfect P3 matching problem. I'm looking for a reference on interesting subclasses of planar cubic bipartite graphs. An interesting subclass contains infinite number of graphs and excludes infinite number of graphs.

More importantly, Which hard problems do remain hard on nontrivial subclasses of planar cubic bipartite graphs?

Hamiltonicity remains NP-complete for 2-vertex-connected cubic planar bipartite graphs, but this is not actually a restriction: every cubic planar bipartite graph is 2-connected. It is a well-known open problem whether 3-connected cubic planar bipartite graphs always have Hamiltonian cycles, but if they do not then the problem is NP-complete for them as well.

(One of my recent papers looked at some related connectivity classes of cubic planar bipartite graphs but not from the point of view of NP-hardness.)


Is the Chi-square divergence a Bregman divergence? Is the Chi-squared divergence $\sum_{i} \frac{(x(i)-y(i))^2}{x(i)}$ a Bregman divergence? I.e., can it be written as
$\phi(x) - \phi(y) - \langle\phi'(y),x-y\rangle$?

If so, what is the potential function $\phi(x)$ from which it is generated?
If not, does there exists a Bregman divergence which bounds Chi-square divergence from above?

$\chi^2$-divergence is not a Bregman divergence.

I'll show it for sample size $n=1$. We would have
$$
(x-y)^2/x=f(x)-f(y)-f'(y)(x-y)$$
If $y=0$ and $x>0$ this says
$$x=f(x)-f(0)-xf'(0),$$
$$1=\frac{f(x)-f(0)}x-f'(0).$$
Taking $x\to 0^+$ this gives the contradiction $1=0$.


Automated theorem proving via unsupervised approaches This question Where and how did computers help prove a theorem? considers some automated theorem proving successes.
However they seem to be mostly supervised approaches, such as with the 4 color graph theorem, the researcher did/does the hard conceptual, non-automatable work of narrowing the conjecture to a finite (but large) set of computer-checkable cases.
Also, in other cases/examples the computer may have found an "infinite" type proof but have been obtained largely by the researcher closely intervening/guiding the overall theorem proving process.

Are there any significant examples of what could be called unsupervised theorem proving successes?

This would generally come in two forms:

only the theorem statement/conjecture, which refers to infinite cases, is given to the computer and the computer manages to find it (ie prove it) without any human intervention/assistance.
the computer searches all theorems and lists "interesting" ones based on some algorithmic criteria/rating, and later after browsing through the list, the researcher recognizes "mathematically significant" proof(s) that are standard or can be found in the literature.

(Note: I have some possible example(s) of the above & depending on response may answer with them.)

Clarification on terminology

The theorem proving community does not use the terms supervised and unsupervised. They use the terms interactive theorem proving or automated theorem proving. If you give a conjecture to the prover and it always comes back with a yes or no answer, such a prover is a decision procedure for a logical theory or simply called a decision procedure.

Proving statements of an infinite nature

The intuition that a theorem that involves an infinite number of cases will be difficult for a machine is misleading. Consider the statement below.

  The sum of two even numbers is an even number.

If you were do prove this by enumerating even numbers, there are infinitely many cases to consider. This statement is expressible in Presburger arithmetic. Presburger arithmetic is the first-order theory of the Natural numbers with the constants zero, one, addition, and equality.  Presburger in his 1929 Masters thesis showed this theory to be decidable. There are other facts of an 'infinite' nature that can be expressed in Presburger arithmetic and proved algorithmically.

Fully Automatic Theorem Proving

In asking for a machine that works with no assistance, you are asking for a decision procedure. It does not make much mathematical sense to ask for a decision procedure for one conjecture. If the conjecture is either true or false, there is a a trivial decision procedure. What we do in practice is try to find a logic that can express a conjecture we care about and try to prove the logic is decidable.

There are many many logical theories that are known to be decidable. Presburger arithmetic is a standard example. Another famous example is the first-order theory of real closed fields. The axiomatization provided by Tarski and his collaborators is sufficient to express statements of Euclidean geometry without measurement of angles or trignometric functions. This theory is decidable though the complexity is non-elementary.

Observe again that the intuition that complexity of proving a statement depends on the cardinality of the underlying domain is quite misleading. The intuition that the complexity of automatically proving a statement corresponds with how late in our education we meet that idea is also misleading.

The theory of the natural numbers with addition and multiplication is undecidable. The first order theory of real-closed fields is decidable but the proof is quite complex. The first-order theory of algebraically closed fields, which includes facts about complex numbers is also decidable. The proof for algebraically closed fields takes one or two pages in logic textbooks.

To summarise, you are asking about decision procedures for logical theories. There are many of them.

Interest

Success of a tool and interest of the theorems are highly subjective. The value of a theorem changes over time. Theorems proved at a certain time are forgotten and rediscovered a few decades later when they are celebrated by the community. It is easy to claim a theorem significant in retrospect and put it in a textbook, but it is not easy to recognise the significance of a theorem when it is proved. There is also the matter of relevance. There is much in a model theory text book I find boring and much in an automated deduction book that a model theorist would find boring, even though we both work in the field of logic.

There are decision procedures that can prove statements in textbooks. Tarski's decision procedure can prove the statements in Euclid's Elements. There are some statements in elementary number theory and linear algebra that decision procedures can prove.

The company TheoryMine sells theorems. (Yes, you can now proudly go to a medieval market and barter two theorems about list reversal for a kilo of unwashed potatoes.) The techniques they use to identify interesting theorems may answer your question.

Success

There are many ways to define success of a theorem prover. If you're asking whether a fully automatic theorem prover has ever, entirely by itself, proved a statement that mathematicians wanted to prove, I believe there might be stray examples, but they are not considered major successes.

Asking if a piece of technology can achieve the same things a human being finds interesting misses the point. It's interesting for a human being to hike up a mountain but trivial for a helicopter.

The major success of automated theorem provers is proving theorems about machines. Reasoning about the correctness of a cache coherence protocol, a floating point multiplication algorithm, a device driver are all highly non-trivial problems of a scale and intricacy that our limited monkey brains cannot deal with.

There is a theorem prover in the production flow of an Intel chip. There is a theorem prover shipping with Windows 7 and Windows 8 device driver kits. These theorem provers and the theorems they prove save more money and affect the daily lives of more people than most of our manually derived proofs ever will. That reeks of success to me.

On The Capabilities of Theorem Provers

This is in response to a question about whether there is an automatically generated proof of the infinitude of the primes (automatic, not computer assisted).

I am not aware of such a proof. However, one should ask what the consequences of such a proof are. If a human being can prove this statement, I think we can conclude they know something about numbers and about proofs. The consequences of an automatic proof would be very significant. The automatic procedure would also be able to solve open problems in mathematics. The problem is that difficulty and capability are very different for human beings and for machines.

To summarise, we have absolutely no illusions about what can be proved completely automatically. The goal of the field is not to replace or compete with human mathematicians. It is not surprising that a machine cannot prove what a human being can prove. It is insightful to understand that the consequences of a human being proving something are quite different from a machine automatically proving something.


Complexity relative to the graph of the Busy-Beaver function This question is inspired by the comments made on this other question that I asked, and by an attempt to provide an explicit example of a complexity question beyond the Turing degree $\mathbf{0}$.  (And like the former question, I'm not sure whether this is more appropriate here or on MathOverflow.)
Let $\Gamma_{\mathrm{BB}}$ be the graph of the Busy-Beaver function, i.e., $\Gamma_{\mathrm{BB}}$ is the set of $(n,v)$ such that $v = \mathrm{BB}(n)$ (I hope the exact details of how the Busy-Beaver function is defined aren't relevant for the question I'm about to ask!  but let's say that $\mathrm{BB}(n)$ is the maximal number of execution steps that a Turing machine with $n$ states can take and eventually halt).  Now consider Turing machines with $\Gamma_{\mathrm{BB}}$ as an oracle: i.e., they are allowed to ask the question “is $v = \mathrm{BB}(n)$?” at any point in their computation.
Since $\mathrm{BB}$ is in the same Turing degree $\mathbf{0}'$ as the halting problem $H$, such machines can indeed solve the halting problem (given a machine $e$ having $n$ states, simulate its execution while, at each step $v$, asking $\Gamma_{\mathrm{BB}}$ whether $v = \mathrm{BB}(n)$, and stop whenever either the machine stops or we know we've run more steps than a machine with $n$ steps can possibly go through).
Now I am interested in the time complexity for such machines with $\Gamma_{\mathrm{BB}}$ as an oracle: clearly the algorithm I described has an enormous complexity (comparable to $\mathrm{BB}$ itself!).  So I am inclined to ask whether one can do better.
Specifically:

Question 1: Does the halting problem $H$ belong to any standard complexity class relativized to the $\Gamma_{\mathrm{BB}}$ oracle, like $\mathbf{P}^{\Gamma_{\mathrm{BB}}}$ (polynomial time), $\mathbf{EXP}^{\Gamma_{\mathrm{BB}}}$ (exponential time) or $\mathbf{PR}^{\Gamma_{\mathrm{BB}}}$ (primitive recursive in $\Gamma_{\mathrm{BB}}$)?

Note in particular that, if such is the case, once we can compute the halting problem, we can compute all computable sets in the same complexity (I mean, if $H$ is the halting problem, and $\mathbf{R}$ is the class of all computable sets, we have $\mathbf{R} \subseteq \mathbf{P}^H$ by letting the oracle do all the computational work, so a positive answer to question 1, say, for $\mathbf{P}$, would imply that $\mathbf{R} \subseteq \mathbf{P}^{\Gamma_{\mathrm{BB}}}$).

Question 2: Or, at the other extreme, is it perhaps true that $\mathbf{P}^{\Gamma_{\mathrm{BB}}} \cap \mathbf{R}$ (functions computable in polynomial time with $\Gamma_{\mathrm{BB}}$ as oracle, and which happen to also be computable without oracle) equals $\mathbf{P}$, i.e., that having access to $\Gamma_{\mathrm{BB}}$ as an oracle won't speed up the computation of any problem that's already computable?  (Or replace $\mathbf{P}$ by any standard complexity class like the ones mentioned in the previous question.)

Really nice question(s). I don't fully follow Denis’ answer, so I'm going to try my own.
For question 1, I’m going to assume that you are familiar with Kolmogorov complexity (otherwise I could write a proof heavily using Kleene’s fixed point theorem, but such proofs tend to look like black magic, while Kolmogorov complexity is rather natural). Assume for the sake of contradiction that $H$ can be computed from oracle $\Gamma_{BB}$ in computably bounded time, and let $f$ be a computable bound.
First, I claim that for all $n$, the first $2^{n+1}$ bits of $H$ form a string $x_n$ of Kolmogorov complexity at least $n$. Indeed, if we knew $x_n$, this would allow us to know which programs of size $\leq n$ halt, so we could run all of them and return a string different from all the outputs of terminating programs of size $\leq n$, hence of Kolmogorov complexity $>n$. In other words, we can computably transform $x_n$ into a string of complexity $>n$, which by conservation of complexity implies $K(x_n)>n$ (I ommit the usual additive constant).
On the other hand, by our assumption the first $2^{n+1}$ bits of $H$ can be computably obtained from the first $f(2^{n+1})$ bits of $\Gamma_{BB}$. But $\Gamma_{BB}$ is very, very, sparse hence in particular, for infinitely many $n$, the string $y_n$ consisting of the first $f(2^{n+1})$ bits of $\Gamma_{BB}$ is all zeroes except perhaps for the the first, say, $n/2$ bits, and thus $y_n$ must have Kolmogorov complexity less than $n/2$ (it suffices to specify the first $n/2$ bits), which contradicts the fact that the first $2^{n+1}$ bits of $H$ can be computably obtained from $y_n$.
Question 2 goes right into current research in computability theory. Fortnow proposed a little while ago the concept of `low for speed’. An oracle $X$ is low for speed if it does not alter any computational complexity class. More precisely, $X$ is low for speed if any computable language $L$  that can be computed from oracle $X$ in time $f$ can be computed without $X$ in time $poly(f)$. While we do not have a full characterization of low for speed oracles, we know that:

there exist non-computable ones, which can be taken to be recursively enumerable (Robertson Bayer. Lowness For Computational Speed. PhD thesis, University of California Berkeley, 2012)
that they form a measure 0 set (Bienvenu Downey, https://arxiv.org/abs/1712.09710) but they form a meager set if and only if $P \not= NP$ (Bayer, ibid)
that lowness for speed is not a Turing degree notion, but any $X \geq_T \emptyset’$ is not low for speed (Bienvenu-Downey, ibid)

From this last point, we know that $\Gamma_{BB}$ is not low for speed, so there is some computable language which can be computed much faster with $\Gamma_{BB}$ than without it. I'd have to think about it, but I believe we could cook up a language which is in $\mathbf{P}^{\Gamma_{BB}}$ but not in $\mathbf{P}$.


Büchi automata with acceptance strategy The problem
Let $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$.
We assume that $A$ has an acceptance strategy in the following sense : there is a function $\sigma:\Sigma^*\to Q$ which can be used to pilot runs of $A$. We formalize this by the following conditions :

$\sigma(\epsilon)=q_0$

for all $u\in\Sigma^*$ and $a\in\Sigma$, $(\sigma(u),a,\sigma(ua))\in\Delta$

for all $w=a_0a_1a_2\dots\in L$, the run piloted by $\sigma$ is accepting, i.e. the sequence $\sigma(\epsilon),\sigma(a_0),\sigma(a_0a_1),\sigma(a_0a_1a_2),\dots$ has infinitely many elements in $F$.

To subsume the conditions, $A$ can accept any word of its language without having to guess anything about the future.
Then, under these assumptions on $A$, is it true that $A$ can be determinized just by removing transitions ? In other words, can we always choose the next transition depending only on the current state and letter ? Is there any reference on the subject ? The same question can then be asked on co-Büchi automata, and more generally on parity automata.
What is known
Here are some partial results.
First, we can restrict $\sigma$ to nondeterminstic choices between states having the same residual. Indeed, if $L(q)$ is the language accepted from $q$, an accepting strategy cannot choose $q_1$ over $q_2$ at some point, if there is $w\in L(q_2)\setminus L(q_1)$.
Notice that the remaining choices do matter, so despite the intuition, this is not enough to get rid of the nondeterminism. This is because it is possible to stay ad infinitum in a good residual (i.e. the remaining of the word is in the residual), but reject the word because not infinitely many Büchi states are seen. This is the main difficulty of the problem : an infinite run can be wrong, without making any fatal mistake at some point.
Second, the problem is solved if $L=\Sigma^\omega$, i.e. all words are accepted by $A$. In this case, we can view $A$ as a Büchi game where Player I chooses input letters and Player II chooses transitions. Then we can use positional determinacy of Büchi games to extract a positional strategy for Player II. This arguments even works in the more general case of parity automata. The difficulty of this problem comes from the fact that some words are not in $L$, and in this case the strategy $\sigma$ can have any behaviour.
Third, here is a proof that under the assumptions, the language $L$ is in the class of deterministic Büchi languages, witnessed by an automaton with states $2^Q$.
Notice that this implies that $L$ cannot be any $\omega$-regular language, for instance  if $L=(a+b)^*a^\omega$, no strategy $\sigma$ matching the conditions can exist.
We start by restricting the transitions according to the first remark : the only choices we can make do not impact on the residual language. We only take successors with the maximum residual, they must exist because $\sigma$ exists.
Then, we build $A'=\langle \Sigma, 2^Q, \{ q_0\},F',\Delta'\rangle$ in the following way. $A'$ is the subset automaton of $A$, but every time a Büchi state $q$ appears in the component, all other states can be removed from the component, and we start again from the singleton $\{ q\}$. Then we can set $F'=\{\{ q\} : q\in F\}$. We can verify that $A'$ is a deterministic Büchi automaton for $L$.
Finally, by putting together the second and the third remarks, we can always obtain a finite memory-strategy $\sigma$, by using a positional strategy for Player II in the game $A\times A'$ where Player I chooses letters, Player II chooses transitions in $A$ and wins if $A$ accepts whenever $A'$ accepts.

It turns out the answer is no, some counter-examples can be found in this paper.
Also here is a more recent work showing that such Büchi automata can be recognized in polynomial time.


Kleinberg-consistency of spectral clustering Spectral clustering refers to a family of graph-based algorithms, which usually rely on a similarity function rather than a metric, though a metric $\rho(x,y)$ can always be converted to a similarity function, say $e^{-\rho(x,y)}$.

What I called Kleinberg-consistency is commonly referred to in the clustering literature as "Kleinberg's consistency axiom". A clustering algorithm takes a finite point set $S$ together with a metric $\rho$ as input, and returns a clustering $\mathcal{C}$ of $S$, which is just a nontrivial partition of $S$.

The clustering algorithm $A$ is consistent if it satisfies the following property: Run $A$ on point set $S$ with metric $\rho$, to obtain some clustering $\mathcal{C}$. Now take any $\rho'$ such that all $x,y\in S$ that fell into the same cluster $C\in\mathcal{C}$ satisfy $\rho'(x,y)\le\rho(x,y)$ while for all $x,y$ that fell into distinct clusters, we have $\rho'(x,y)\ge\rho(x,y)$. Consistency requires that if we run $A$ on $(S,\rho')$, we obtain the same clustering $\mathcal{C}$ as we did for $\rho$.

Question: Is there any specific natural spectral clustering algorithm that is known (not) to be Kleinberg-consistent?

NB: The question is explicitly not about the statistical consistency of spectral clustering, which has been addressed in the literature.

Answering my own question, with a hat tip to Misha Belkin (private correspondence). It is easy to see that the unnormalized mincut and the RatioCut algorithm (see here for precise definitions
http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Luxburg07_tutorial_4488%5b0%5d.pdf
) are Kleinberg-consistent. This is because the intra-cluster distances/similarity does not influence the objective function in any way.

The Ncut-based clustering algorithm, however, is not Kleinberg-consistent. This can be seen by making the similarity weights within some cluster sufficiently large that it is able to absorb nearby clusters with negligible extra charge.


Partition a graph into 2 connected subgraphs I'm stumped on a sub problem that I'm working on for my thesis. I need to be able to partition a graph into 2 connected subgraphs of almost equal size. So if there are $m$ vertices in $G$, subgraphs $G_{1}$ and $G_{2}$ should have

\begin{equation}
|V_{1}| + |V_{2}| = |V|
\end{equation}
\begin{equation}
(|V_{1}| - |V|/2)^{2} \leq \epsilon^{2}, (|V_{2}| - |V|/2)^{2} \leq \epsilon^{2}
\end{equation}

and $V_{1}$ and $V_{2}$ should be disjoint.

Anyone know a quick way to compute if this exists and what the partition should be? I know that partitioning in general is NP-hard but I didn't know if it was for this special case.

The problem you asked is the unweighted version of the Balance Connected 2-Partition ($BCP_2$).

For unweighted case, any 2-connected graph can be partitioned into two connected subgraphs whose numbers of vertices differ by at most one. A simple algorithm uses st-numbering. For any 2-connected graph, we can label the vertices by $[1...n]$ such that any vertex has simultaneously a neighbor with smaller label and a neighbor with larger label. Let $V_1=\{1...n/2\}$ and $V_2=V-V_1$. It can be easily shown that both $V_1$ and $V_2$ induce connected subgraphs.

However, when there are cut vertices, the problem is NP-hard because it is equivalent to the weighted $BCP_2$. The transformation is as follows. Let $v$ be a cut vertex and $H$ be the maximum connected component in $G-v$. We shrink all components other than $H$ into $v$ and the weight of $v$ is given by the weight of the vertices combined in $v$. Repeat this process and we can obtain a weighted 2-connected graph.

It can be easily realized that there exists a graph such that the minimum part contains only $n/3$ vertices in any 2-partition.

For $BCP_2$, the currently best approximation algorithm is due to Chlebikova (I hope that it is not out of date):

Approximating the maximally balanced connected partition problem in graphs, Information Processing Letters, 60:225--230, 1996. The approximation ratio is 4/3. For some special graphs, there are better results. For example, FPTAS for interval graphs and 5/4-approximation for grid graphs (further improved to 7/6).


Dominations under oracles which is closed under complement? Edited at 2010/11/29:

As John Watrous have mentioned, the class $\mathsf{C^O}$ may be not well-defined. After reading some early posts, I try to restate my question in an unambiguous way.

Let $\mathsf{O}$ be a complexity class that is closed under complement, i.e. $\mathsf{O} = \mathsf{coO}$. Also we assume that the logspace, $\mathsf{L}$, is a subset of $\mathsf{O}$.

  When does the equality $\mathsf{L^O} = \mathsf{O}$ hold?

We define $\mathsf{L^O}$ as languages accepted by logspace oracle machines with an $\mathsf{O}$ oracle, where queries are written on a separated oracle tape not restricted to the logspace bound, and after each query the tape is automatically erased.

We know that $\mathsf{NL} = \mathsf{coNL}$ by Immerman-Szelepcsényi Theorem, and we have $\mathsf{L^{NL}} = \mathsf{NL}$.
Before the era of Reingold, when nobody knows whether $\mathsf{SL} = \mathsf{L}$, Nisan and Ta-Shma have proved that $\mathsf{SL}$ is closed under complement. They also show that $\mathsf{L^{SL}} = \mathsf{SL}$ in the paper.

In the paper "Directed Planar Reachability Is in Unambiguous Log-Space" by Bourke, Tewari and Vinodchandran, they gave a claim in corollary 4.3 that $\mathsf{L^{UL \cap coUL}} = \mathsf{UL \cap coUL}$. Clearly $\mathsf{UL \cap coUL}$ is closed under complement, but is this equality holds so trivially?

Do we have any easy conditions to decide if $\mathsf{L^O}$ and $\mathsf{O}$ are in fact the same? For easy conditions it means we only have to check some properties about $\mathsf{O}$, then we can decide if they are equal, without using definitions of the classes to prove the inclusion $\mathsf{L^O} \subseteq \mathsf{O}$.

Another related question would be:

  Do we have any oracle $\mathsf{O}$ such that $\mathsf{L^O} \neq \mathsf{O}$?

For a given choice of complexity classes $\mathsf{C}$ and $\mathsf{O}$, by which we mean sets of languages and nothing else, the class $\mathsf{C}^{\mathsf{O}}$ is not well-defined: we need the definition of $\mathsf{C}$ to determine how oracle queries are defined.  Sometimes even then there could be ambiguities that need to be resolved, or the definition might not provide a reasonable notion of an oracle query at all.  (Attaching oracles to space-bounded complexity classes is one example in the first category, where the relativized classes we obtain are very sensitive to the exact capabilities of the oracle tape and whether we consider that it contributes to our space bounds.)

So, I don't think you can possibly say anything about $\mathsf{C}^{\mathsf{O}}$ without using the definitions of the classes, because if you don't use the definition of $\mathsf{C}$ you aren't working with a well-defined mathematical object.

If I have misunderstood your question, please clarify what sort of properties of $\mathsf{C}$ and $\mathsf{O}$ you permit to be used.


Enumerating all s-t paths with cost exactly k Is there a known algorithm for the following problem?  Given a simple weighted directed graph, a pair of vertices $s$ and $t$, and a real value $k$, enumerate all simple paths from $s$ to $t$ with cost exactly $k$.

I've heard of uniform search, but I'm not really sure if it can solve my problem.

I just read that finding one $s$-$t$ path with a given cost is NP-hard in general.  If all weights are $1$ and $k$ is one less than the number of vertices, this becomes the Hamiltonian Path Problem.

I've been struggling for long with two similar problems and you are just referring to the combination of them: finding the best $K$ solutions and the Target-Value search problem. Since you are asking for algorithms, let me give you the best bib references I am aware of.

First, let me reformulate the second problem:

Given a graph $G(V,E)$ and a couple of vertices $s\in V$ and $t\in V$ find the simple path $P^*$ whose cost is as close as possible to a given value $k$, i.e., if $P_{s-t}$ denotes the set of all (simple) paths from $s$ to $t$ and $g(P)$ is the cost of a path which is defined as the sum of the cost of all of its edges, then $P^* = argmin_{\pi\in P_{s-t}} \{|c(\pi)-k|\}$

This problem is known as the Target-Value search problem and was originally introduced in Lukas Kuhn, Tim Schmidt, Bob Price, Johan de Kleeer, Rong Zhou and Minh Do, Heuristic Search for Target-Value Path Problem. In case a path actually exists with a cost equal to $k$ then it simplifies to your problem. Note that while in the definition I said "simple paths" between parenthesis, the work cited above refers only to Directed Acyclic Graphs so that all paths are necessarily simple. Unfortunately, I am not aware of any generalization of this algorithm to Undirected (cyclic) graphs. An improvement over that paper was provided by much the same authors in Tim Schmidt, Lukas Kuhn, Bob Price, Johan de Kleer and Rong Zhou, A depth-first approach to target-value search

A different problem consists of computing the best $K$ solutions. This problem can not be solved with an A$^*$-like search algorithm because duplicate detection avoids re-expanding nodes while the second best solution might require going through the same node already considered in the best solution. One of the most influential works for this problem is David Eppstein, Finding the $k$ Shortest Paths. A recent contribution of the same problem is Husain Aljazzar, Stefan Leue, K$^*$: A heuristic search algorithm for finding the $k$ shortest paths

Now, how to combine these two problems is an unknown so that if you have any ideas ... :)


Turing Machine restrictions that render halting decidable If one restricts Turing Machines to a finite tape (i.e., to use bounded space $S$),
then the halting problem is decidable, essentially because after a number of steps (which can be calculated from the number of states $Q$, and $S$, and the alphabet
size), a configuration must be repeated.

  Are there other natural Turing Machine restrictions that render halting decidable?

Certainly if the state-transition graph has no loops or cycles, halting is decidable. Any others?

A fairly natural and studied variation is the Tape-Reversal Bounded Turing machine (the number of tape-reversals are bounded); see for example:

Juris Hartmanis: Tape-Reversal Bounded Turing Machine Computations. J. Comput. Syst. Sci. 2(2): 117-135 (1968)

Edit: [this variation is more artificial] the halting problem is decidable for a Non-erasing Turing machine that has at most two left instructions on alphabet $\{0,1\}$; see Maurice Margenstern: Nonerasing Turing Machines: A Frontier Between a Decidable Halting Problem and Universality. Theor. Comput. Sci. 129(2): 419-424 (1994)