"A simple linear time algorithm" by Klawe I try to implement the algorithm described in "A simple linear time algorithm for concave one-dimensional dynamic programming" by Maria M. Klawe, 1989.

However, right at the beginning there is possibly a typo:

i ← 0; r ← 0;
While i < 2^⎡log(n + 1)⎤ and r < i do;
    If i = 2^⎡log i⎤ - 1 then do;
...

because of the "r < i" the while loop immediately terminates. Also, the "if" condition should be taken right in the first loop (from what I understood).

Please, does anyone know if there is a typo indeed and eventually what should the initialization look like?

Edit

I hope it's ok if I post here the whole algorithm. I honestly don't know what the practice on posting such things online is - if it's not ok, I apologize and I (or the moderator) will delete it.

i ← 0; r ← 0;
While i < 2^⎡log(n + 1)⎤ and r < i do;
    If i = 2^⎡log i⎤ - 1 then do;
        SMAWK M(0 : i, i + 1 : min(2(i + 1) - 1, n));
        * a square has been treated *
        i ← i + 1;
        end;
    else if M(r, 2^(⎣log(i + 1)⎦ + 1) - 1) < M(i, 2^(⎣log(i + 1)⎦ + 1) - 1)
        then i ← i + 1;
        * a slice has been treated *
        else r ← r + 1;
        * the region M(r, 2^(⎣log(i + 1)⎦ + 1) - 1 : n) has been treated *
end;
* The algorithm has now treated rows 0, ..., i - 1. *

It works like this: there is a triangular matrix, which the algorithm extracts larger and larger squares from (that's the first branch). The algorithm then breaks the remaining lines under the square into "slices".

PS: The initialization is just one problem. The another is that for some input the second branch M(r, ...) < M(i, ...) starts to increase only r which causes the while loop to exit prematurely because of r < i

There is also pseudocode for this algorithm given on p. 14 of Aggarwal and Tokuyama, "Consecutive interval query and dynamic programming on intervals." Discrete Applied Math 85 (1998). It starts out:

1: i=0;
2: r=min{n,2^(i+1)};

and has other differences from the pseudocode that you posted; at first sight, the Aggarwal and Tokuyama pseudocode seems quite a bit clearer. So it seems likely there was a typo in the original. Hopefully, this second paper gets the pseudocode correct. It certainly gives a good enough explanation of the algorithm for me to understand it and see why it works.

UPDATE: (Twice, now): The first update gave the response to questions in the comments. In the second update I corrected the restriction for when you can evaluate a cell. Here's what is going on (with possible fencepost errors in my explanation).

If you search A[j,j;n,n], you never have to search another square, you're done. That's what "5.2.3: Exit" means. You're not exiting the loop; you're exiting the program.

Why do you need to search A[j,j,n,n]? You have just found the minima of columns 2^i to r over rows 1 ... 2^i+1. Here 2^i + 1 <= j <= 2^(i+1). Because of the entries you've looked at in column r and the monotonicity of the matrix, you can conclude that you've already found the minimum in columns 1 through j-1, and the minimum in columns j..r is either the one you've already found or is in the matrix A[j,j;n,n]. Thus, you have to search A[j,j;n,n], and for the columns between j and r, you need to compare the minimum you find in A[j,j;n,n] with the minimum you've already found for that column (this comparison is step 5.2.2.1).

You can't evaluate an entry A[s,t] until for every column 1..s, you know the minimum in that column. Thus, in order to evaluate an entry A[s,t] when you're searching A[j,j;n,n], you first need to find the minimum in column s. This is why you need to run 5.2.1 and 5.2.2 concurrently. This means you can stop the concurrent 5.2.2 process when you reach column r. (You can see this because 5.2.2.1 says "j <= t <= r".)

So I guess this means that as soon as you find the minimum in column t in 5.2.1, you have to pass it to 5.2.2, do the comparison of the two candidate minima in column t, and now that you know the minimum in column t, you can use it to evaluate entries in row t. Technically, you could do this comparison any time between the point at which you know the minimum of column t in A[j,j;n,n], and the first point at which you need to evaluate a cell in row t. Offhand, I don't see any reason not to do it as soon as you learn the minimum of column t in A[j,j;n,n].


Is clique-width preserved under edge contractions? Let $G$ be class of graphs with bounded clique-width. In each graph in $G$ some edges are contracted (e.g. randomly). Is now the clique-width still bounded?

In case it is (in general) no longer bounded, I would be very interested in a counter-example.

This recent paper finally proves that edge contractions do not preserve the property that a set of graphs has bounded
clique-width.


Are lambda calculus and combinatory logic the same? I am currently reading "Lambda-Calculus and Combinators" by Hindley and Seldin.  I'm not an expert, but have always taken an interest in lambda calculus because of involvement with functional programming (starting with Lisp and SICP, and now with R and Haskell).

In "Binary Lambda Calculus and Combinatory Logic", John Tromp states:

  CL may be viewed as a subset of lambda calculus...the theories are largely the same,
  becoming equivalent in the presence of the rule of extensionality.

Under what conditions would one use combinatory logic instead of lambda calculus?

Any references would be appreciated.

What distinguishes combinatory logic is that it is variable free.  This is sometimes useful in metamathematics and philosophical logic, where the status of variables is tricky.

It may also be useful in implementations, since managing variables can be a headache.  Cf., e.g., Hughes, 1982, Super-combinators: A new implementation method for applicative languages


Compiling einstein sums optimally Einstein summation is a convenient way to express tensor operations which has found its way in tensor libraries like numpy, torch, tensorflow, etc.
Its flexibility lets us represent the product of three matrices, $X$, $Y$, $Z$  of dimensions $(a,b)$, $(b,c)$, $(c,d)$ as
X.Y.Z = einsum('ab,bc,cd->ad',X,Y,Z)

However, the above compiles to something like
for a_ in range(a):
  for d_ in range(d):
     res[a_,d_] = 0
     for b_ in range(b):
        for c_ in range(c):
           res[a_,d_] += X[a_,b_] * Y[b_,c_] * Z[c_, d_]

This native is quadratic in the size of the matrices when simply doing
einsum('ac,cd->ad',einsum('ab,bc'->'ac', X, Y), Z)

Would be merely cubic.
There are roughly three levels of optimization we can imagine a smarter implementation of einsum to perform.

Decompose an einsum of tensors $(x_1, \ldots, x_n)$ into an einsum of pairs of tensors $x_1, x_2$, $e(x_1, x_2), x_3$, etc to optimize computation time.

Rely on associativity (where applicable) to pick those pairs judiciously (this is a classic dynamic programming problem) and construct the appropriate intermediary tensors.

Discover Strassen-like formulas for the specific tensor computation

While 3 seems clearly out of reach, 1 and 2 seem like they could be achievable exactly with a reasonably straightforward algorithm. Are such algorithms known for generic einstein summations? Have they been studied?

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


What is worst case complexity of number field sieve? Given composite $N\in\Bbb N$ general number field sieve is best known factorization algorithm for integer factorization of $N$. It is a randomized algorithm and we get an expected complexity of $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$ to factor $N$.

I looked for information on worst case complexity on this randomized algorithm. However I am unable to locate information.

(1) What is the worst case complexity of Number field sieve?

(2) Also can randomness be removed here to give a deterministic subexponential algorithm?

The number field sieve has never been analyzed rigorously. The complexity that you quote is merely heuristic. The only subexponential algorithm which has been analyzed rigorously is Dixon's factorization algorithm, which is very similar to the quadratic sieve. According to Wikipedia, Dixon's algorithm runs in time $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$. Dixon's algorithm is randomized.

All (heuristically) known subexponential algorithms require randomization. Dixon's algorithm needs to find integers $x$ such that $x^2 \pmod{n}$ is smooth (can be factored into a product of small primes) and "random", and the number-field sieve has similar but more complicated requirements. The elliptic curve method needs to find an elliptic curve modulo $n$ whose order modulo some factor of $n$ is smooth. In both cases it seems hard to derandomize the algorithms.

The nominal worst-case complexity of all these algorithms is infinity: in the case of the quadratic sieve and the number-field sieve you might always be generating the same $x$, while in the elliptic curve method you may always be generating the same elliptic curve. There are many ways around this, for example running an exponential time algorithm in parallel.


Morgenstern's Theorem Morgenstern proves a $\Omega(n\log n)$ lower bound for Fourier transform in the bounded coefficient model.

Let $x=[x_1,x_2,\ldots,x_n]'$ be given vector and $F$ be Fourier transform matrix.

It is not known if $F(x)$ needs $n\log n$ operations in the unbounded coefficient model when $x_i$'s are treated generically as variables.

Supposing each $x_i$ is an integer bounded by $2^b$, can one show computing $F(x)$ still needs $n\log n$ arithmetic operations in the unbounded coefficient model?

Added:
The reason I posted was a few fold. Some questions in the bounded integer $x_i$ model are:

1) We cannot use bit level manipulation on variables $x_i$. However we can do bit level operations on integers $x_i$. Are bit level operations considered valid arithmetic operations when counting the $\Omega(n\log n)$ arithmetic operation?

2) Does one multiplication operation on a word that scales as $O(n)$ bits still count as $1$ arithmetic operation?

3) Is division a valid arithmetic operation?

Of course if you show a lower bound of $\Omega(n \log n)$ for your question, it would imply the same lower bound for the unrestricted model, which is not known.

On the other hand, you are asking whether it is possible to compute the Fourier transform where each $x_i$ is known within $b$ bits of precision using $\ll n \log n$ arithmetic operations. If true, by the fact that the Fourier transform is a unitary operation (and thus, perfectly conditioned), we would be able to compute Fourier transform of any vector within $b$ bits of precision much faster than FFT, which is certainly not known either.


Is modal $\mu$-calculus "equivalent" to bisimulation? I know that propositional modal $\mu$-calculus $L\mu$ is bisimulation-invariant.  However, I'm curious to what degree it captures bisimulation.

Q1:  Given two labeled transition systems $T_1$, $T_2$ that are not bisimilar, is there an $L\mu$ formula which has $T_1$ as a model but not $T_2$?

Q2 (stronger):  What is a maximal class $\mathcal{C}$ of labeled transition systems such that given any $T \in \mathcal{C}$, there exists an $L\mu$ formula which has $T$ as its unique model in $\mathcal{C}$?

I hope this makes sense!  Basically I'm wondering to what degree I could replace discussion of transition systems with modal mu calculus formulas.  Thanks! :)

For Q1, the answer is yes if we consider image-finite systems: for all node $t$ and label $a$, the number of $a$-successors of $t$ must be finite. In this case you don't even need fixpoints of the $\mu$-calculus, only the fragment called Hennessy-Milner Logic to distinguish non-bisimilar structures [HM85]. This is known as the Hennessy-Milner Theorem. Intuitively, the non-bisimilarity can be seen in a finite amount of steps of the form "there exists an $a$-successor", or "for all $a$-successor".
For more general cases, the paper [FCM17] might be of interest, in particular it gives at the end an example of two non image-finite structures (actually two nodes in the same structure) which are not bisimilar, but cannot be distinguished with  HML formulas. I suspect this is still true for $\mu$-calculus formulas, but to be verified.
As for Q2, I'm not sure there is a clear "maximal class". A class $\mathcal C$ with your conditions must at least satisfy the following requirements:

at most one element per bisimulation equivalence class
$\mathcal C$ is countable

But then you have some room, since starting from such a class you can always replace one element by another which is bisimilar to it.
It is not even true that $\mathcal C$ must only contain finitely describable elements, since you can always take $\mathcal C=\{T\}$, where $T$ is any structure, and complete it to a maximal class, and it would satisfy the requirements (although artificially). You probably have other conditions in mind for such a class, that would rule out the above example.
A natural such class is the set of regular ranked binary trees (where successors are ordered). Here "regular" means that the number of distincts subtrees is finite, even though the tree can be infinite.
[HM85] Matthew Hennessy & Robin Milner (1985): Algebraic laws for nondeterminism and concurrency. Journal of the ACM, doi:10.1145/2455.2460.
[FCM17] Ferlez, J., Cleaveland, R. and Marcus, S., 2017. Bisimulation and Hennessy-Milner Logic for Generalized Synchronization Trees. arXiv preprint arXiv:1709.00827.


Multiplying n polynomials of degree 1 The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time.

You can do $O(n \log^2 n)$ time by applying FFT in a tree fashion. Can you do $O(n \log n)$?

Warning: This is not yet a complete answer. If plausibility arguments make you uncomfortable, stop reading.

I will consider a variant where we want to multiply (x - a_1) ... (x - a_n) over the complex numbers.

The problem is dual to evaluating a polynomial at n points. We know this can be done cleverly in O(n log n) time when the points happen to be nth roots of unity. This takes essential advantage of the symmetries of regular polygons that underlie the Fast Fourier Transform. That transform comes in two forms, conventionally called decimation-in-time and decimation-in-frequency. In radix two they rely on a dual pair of symmetries of even-sided regular polygons: the interlocking symmetry (a regular hexagon consists of two interlocking equilateral triangles) and the fan unfolding symmetry (cut a regular hexagon in half and unfold the pieces like fans into equilateral triangles).

From this perspective, it seems highly implausible that an O(n log n) algorithm would exist for an arbitrary set of n points without special symmetries. It would imply that there is nothing algorithmically exceptional about regular polygons as compared to random sets of points in the complex plane.


Why was Schönfinkel's work on eliminating "bound variables" in logic so crucial? AFAIK, The first evidence of using higher order functions goes back to Schönfinkel's 1924 paper: "On the Building Blocks of Mathematical Logic" - where he allowed one to pass functions as arguments to other functions.

That seems interesting. However, everything that I've been reading about his work (and Curry's by extension) seems to allude to one thing in some form or the other: [higher order functions]...this eliminates the need for bound variables...

What I haven't been able to wrap my head around is - what's the big deal? Why did logicians and mathematicians of that time care about this? And do we as theoreticians, care about this today? Why was it "groundbreaking" to get rid of bound variables and what impact did (or does) it have on computing (theoretically) as we know it?

PS: I'm aware of how his work paved way for $\lambda$-calculus and the impact of "it" on computing and functional programming in general. My question is mostly directed to the time "prior" to the creation of $\lambda$-calculus and "after" Schönfinkel's paper. The fact the Curry independently picked up that line of work, which was later known as "combinatory logic" too alludes to the importance of Schönfinkel's work.

TL;DR. The metamathematics of binding are subtle: they seem trivial but aren't — whether you deal with (higher-order) logics or -calculus. They're so subtle that binding representations form an open research field, with a competition (the POPLmark challenge) some years ago. There are even jokes by people in the field about the complexity of approaches to binding.

So, if you care about metamathematics (and most mathematicians don't), you need to deal with binding. But many mathematicians can safely treat the formalization of binding as if it were a "foundational" problem.

Another point is that binding was the only "new" problem in languages with higher-order functions, because the theory of languages with binding is just algebra (for constants) + binding. Mitchell's "Foundations of Programming Languages" actually presents things in this order and is rather enlightening.

  I'm aware of how his work paved way for λ-calculus and the impact of "it" on computing and functional programming in general. My question is mostly directed to the time "prior" to the creation of λ-calculus and "after" Schönfinkel's paper.

I must be missing something, but this remark seems to make no difference. Binding in higher-order logics and binding in λ-calculus seem as hard, so as long as people cared about higher-order logics, they had to deal with binding. I'm biased by using Curry-Howard-isomorphism-based theorem provers that implement logic by simply implementing a type theory (where types are formulas and programs are proof terms), so that I just deal with binding once.

On the other hand, IIRC, at the time indeed few cared about Schönfinkel's work — partly because of how he (didn't) publish it — the papers were mostly written by colleagues based on the research he did (see here, page 4); Curry then rediscovered the theory independently.

Caveat: I'm not an historian, but a PhD student in PL, so mine is a modern (and hopefully accurate) perspective on the topic.

EDIT:

Why is binding subtle, a bit more concretely

There are two facets to it — first, implementing it is hard. Secondly, metamathematics is the mathematics of proof manipulation: this manipulation is typically automatic, that is, it's an algorithm — so essentially, you face all the difficulties of implementation, plus making proofs about them. Below I give examples. The examples have a modern perspective — they are about actually formalized proofs. However, some of the difficulties would extend to accurate manual proofs — as long as you don't cheat on details.

This shows that Schönfinkel simply gave the first solution to this problem, but this was far from definitive.

Implementing it is subtle because of shadowing

The basic problem in implementation is shadowing. Usually one doesn't reuse the same name for different bound variables. But you can't avoid it in lambda calculus, at least because  functions (and their bound variables) are duplicated: $(\lambda f. f~1 + f~2) (\lambda x . x)$ reduces to $(\lambda x . x)~1 + (\lambda x . x)~2$. This isn't a problem yet, but starting from $(\lambda f x. f (f x))\ (\lambda g y . g~y)\ z$ gives you $(\lambda g y . g~y)\ (\lambda g y . g~y)\ z$ and then $(\lambda y . (\lambda g y . g~y)~y)\ \ z$: now you need to deal with shadowing. You can avoid this, at the cost of complicating the beta-reduction rule.

Once you have different variables with the same name, you also need to prevent capture. The simplest example of capture is that applying the function $\lambda x y. x$ (return first argument) to $y$ must not give $\lambda y. y$ (the identity function), but $\lambda y'. y$ (a constant function).

What's worse is that the counterexamples to naive algorithms are hard to construct when you know the problem already, let alone when you don't. Bugs in almost correct algorithms often lie undetected for years. I hear that even good students typically fail to come up  (on their own) with the correct definition of capture-avoiding substitution. In fact, PhD students (me included) and professors aren't exempt from these problem.

That's one reason why some (including one of the best textbooks on programming languages, Types and Programming Languages by Benjamin Pierce) recommend nameless representation (not quite combinatory logic, even though it has been used, but rather deBrujin indexes).

Proofs about it are subtle

It turns out that proofs about binding are no simpler than the implementation, as mentioned above. Of course, correct algorithms exist, and proof about them exist — but without advanced machinery, for each language using binding you need to repeat the proofs, and those proofs are simply very big and annoying if you use the definitions for binding on pen and paper.

To exemplify algorithms involved in metamathematics, consider the deduction theorem in logics, that allows composing a proof of $B$ assuming $A$ and a proof of $A$ to get a proof of $B$. To prove that theorem, you actually exhibit an algorithm that works on the syntax of the two proofs involved and produces the syntax for a proof of $B$. This algorithm needs to deal with binding.

Next, I looked up my best example of "what goes wrong if you try formalizing the standard definition". Russell O’Connor (who's on this site) formalized the first Gödel's incompleteness theorem in Coq (a theorem prover of the kind mentioned above) — and that theorem involves a logic (with all the relevant algorithms) in another logic (with the syntax of the first logic coded as numbers). He used the definitions which are used on paper and formalized them directly.
Search for "substitution" or "variable" and count how often they appear in reference to problems to get an impression.
http://r6.ca/Goedel/goedel1.html

I never use those definitions in my work, but each alternative approach has some downside.


Computed circuit complexity of decision problems Has anyone explored what is the circuit complexity of classic decision problems such as Primes or Graph-Isomorphism for small input size $N$?

While most people are interested in the how the scaling goes as $N \to \infty$, I think it would also be interesting to see how this grows for small N. Sure, we now know Primes is in P, but it would be neat to see how it grows, and maybe even sharp changes in the growth rate of the graph as the inputs get large enough that a different algorithm becomes more efficient.

There is even the (unlikely) possibility that someone could extract from a sequence of circuits a general algorithm.

It seems like this approach could answer different questions than are usually asked about $N \to \infty$.  With the advances of algorithms knowledge (SAT solvers, etc.) and super computing power, concrete answers could be obtained for small $N$.

Are there any references or lists of results for people explicitly computing circuit complexity of decision problems for small $N$?

If there are people working on this, what algorithms do they currently use to solve the minimal circuit problem (given a boolean function and set of gates, output a circuit using the minimal number of gates necessary)?

Yes, this is a natural idea and people have thought about it. In short, the problem is that even the state-of-the-art SAT/QBF-solvers allow to find very small circuits only (with about 10–12 gates), not to say about proving that there is no small circuit. Some references:

Ryan Williams, Applying practice to theory (2008):

  Our knowledge of Boolean circuit complexity is quite poor. <…>  One good reason why we don’t know much about the true power of circuits is that we don’t have many examples of minimum circuits. We don’t know, for example, what an optimal circuit for $3 \times 3$ Boolean matrix multiplication looks like.

  One good reason why we don’t know much about the true power of circuits is that we don’t have many examples of minimum circuits. We don’t know, for example, what an optimal circuit for $3 \times 3$ Boolean matrix multiplication looks like. <…> Might we benefit from an Encyclopedia of Minimum Circuits? For example, what do the smallest Boolean circuits for $10 \times 10$ Boolean matrix multiplication look like? Are they regular in structure? It is likely that the answers would give valuable insight into the complexity of the problem. The best algorithms we know of reduce the problem to matrix multiplication over a ring, which is then solved by a highly regular, recursive construction (such as Strassen’s [Str69]). Even if the cataloged circuits are not truly minimal but close to that, concrete examples for small inputs could be useful for theoreticians to mine for inspiration, or perhaps for computers to mine for patterns via machine learning techniques. The power of small examples cannot be underestimated.

  Experiments with QBF solvers have not yet revealed significant new insight. So far, they have discovered one fact: the optimal size circuit for $2 \times 2$ Boolean matrix multiplication is the obvious one. Well, duh. What about the $3 \times 3$ case? This is already difficult! The sKizzo QBF solver [Ben05] can prove that there is no circuit for $3
\times 3$ that has 10 gates, but nothing beyond that. Even when we restrict the gates to have fan-in two, the solver crashes on larger instances.

Together with Evgeny Demenkov, Arist Kojevnikov, and Grigory Yaroslavtsev we managed to use SAT-solvers to improve upper bounds on the circuit size of symmetric functions. Details can be found in the following two papers: Finding Efficient Circuits Using SAT-solvers (2009), New Upper Bounds on the Boolean Circuit Complexity of Symmetric Functions (2010). Still, we do not know the exact circuit complexity for many elementary functions: for example, $2.5n \le C(MOD_3) \le 3n$, $2n \le C(AND,OR,XOR) \le 2.5n$.

Exercises 477–481 in Section 7.2.2.2: Satisfiability of TAOCP Volume 4 by Don Knuth (2015) discuss ways of finding optimal circuits with the help of SAT solvers. From the solution to exercise 481:

  It’s true for $n \le 5$. Here’s a 12-step computation when $n=6$ and $a=0$, found in 2014 by Armin Biere: <…> The case $n=6$ and $a \neq 0$, which lies tantalizingly close to the limits of today’s solvers, is still unknown.


Delaunay Triangulation of Parallelepiped Given $n$ linearly independent vectors $v_1, v_2, \ldots, v_n$ in $n$-dimensional space. Let $V$ be the set of $2^n$ points of the form $x_1 v_1 + x_2v_2 + \ldots + x_nv_n$, in which $x_i$ can be $0$ or $1$. $V$ is the set of vertices of an n-dimensional parallelepiped. Is there any way to find the Delaunay triangulation of $V$ using subexponential space with respect to $n$? I understand that the size of the output is big, and we can't store the whole output. But is there any way to output the Delaunay edges one by one without storing the previous result?

Testing whether a pair of points $p_i$ and $p_j$ are the endpoints of a Delaunay edge can be solved as a linear programming feasability problem: Lift each point to one higher dimension by making its last coordinate be the sum of squares of the other coordinates. Then look for a hyperplane passing through $p_i$ and $p_j$, such that all the other points are on one side of it. This can be represented in linear inequality constraints by seeking a vector $v$ and scalar $c$ such that the dot product of $v$ with each point is at least $c$, and is exactly $c$ in the case of $p_i$ and $p_j$.

So for any set of points in any dimension, it's possible to find the Delaunay edges one by one, by solving a number of linear programs that is polynomial in the number of points. The reason Delaunay triangulation is hard is not because of the edges, it's because there may be too many higher-dimensional features.


Space alternating hierarchy It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions).

In the same paper, Immerman state that the logspace alternating hierarchy collapses, this means that $\Sigma_j{\rm SPACE}(\log)={\rm NSPACE}(\log)$ (the definition of the bounded alternating turing machine and of what is a hierarchy can be found on wikipedia).

Is there any paper about the alternating space hierarchy  for  $f=\Omega(\log)$ ? I asked last week to Immerman who did not remember reading anything like that. In english I would want to know if there is any written proof that using any language that can be decided by a Turing Machine with $j$ alternations can also be decided by a non deterministic turing maachine with the same space bound.

My question is really about finding a reference, because I think I figured out the proof; but I guess that it may already be known.

Maybe I should state what I think are the two main problems. First if $f=O(n)$, let's say $f=\log^2$, then it is impossible to compose to $SPACE(f)$ TM to obtains a $SPACE(f)$ TM, which we could do with $\rm{LOGSPACE}$ TM. Secondly, there is one argument for the case $f=O(n)$ and one for $f=\Omega(n)$ but there is still some problem for fonction which are neither $O(n)$ nor $\Omega(n)$.

More generally, the Immerman-Szelepscényi method gives that $ALTSPACE(a(n),s(n))$ is in $NSPACE(a(n)s(n))$.  The proof idea is: Calculate the number of reachable configurations in the first alternation; from each such reachable state, calculate the number of reachable configurations in the second alternation; and iterate $a(n)$ times backtracking in the "obvious" fashion.  Each iteration uses only $s(n)$ space to store the counts of reachable configurations.

Combining this with Savitch's theorem gives the following results:

Corollary: $ALTSPACE(\log n, \log n)$ is in $SPACE((\log n)^4)$.  More generally, a language computable in polylogarithmic space with polylogarithmically many alternations is computable in deterministic polylogarithmic time.

Corollary: Similarly, a language computable in polynomial space with polynomially many alternations is in deterministic polynomial space.

I don't know any references for these $ALTSPACE$ results or whether they have been noticed before, or even for the notation.  Leonard Berman[B] used the notation "$STA$" for "Space/Time/Alternation" classes.

[B] L. Berman, "The Complexity of Logical Theories", Theoretical Computer Science 11 (1980)
71-77.


What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover? It is known that computing $(\sqrt 2 -\epsilon)$-approximation for VC is NP-hard and that UGC implies that even a $(2 -\epsilon)$-approximation is hard.

There is also a parameterized algorithm for computing a $\alpha$-approximation of VC (for $\alpha\in[1,2]$).

Considering the standard (non-parameterized) problem and non-polynomial algorithms:

What is the fastest known algorithm for computing a $1.99$-approximation?

I think for getting 1.99-approximation algorithm this paper by Manurangsi and Trevisan, has the current fastest algorithm.


Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices.
In general case, it is exponential.
I am trying to determine whether the number of maximal cliques in a $(2C_4, C_5,P_5)$-free graph with respect to the number of vertices.
In a $(2C_4, C_5,P_5)$-free graph, the largest induced cycle is of length 4, and no two induced 4-cycles are edge-disjoint.
Is there a paper that mentions such result?

The famous graph (the complement of the disjoint union of $n/3$ triangles) with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ as an induced subgraph.
https://doi.org/10.1007/BF02760024


description of continuous probability distribution The minimum description length of the realization of a random variable $x$ is given by the entropy of its probability mass function. It can be asymptotically communicated at this rate with an optimal coding. But that's for just one $x$ from the optimal coding table. How do we cover the whole support efficiently? (Of course, we'll have issues with quantization of real valued $x$-s in our code table, however optimized it's going to be.)

Viewing it differently, entropy of the representation of a generic probability distribution with CDF $F(x)$, where $F(x) \sim p(F(x))$ on some space of distributions $D$, seems to be bounded from above by entropy of uniform $p$ on space $D$: $-\int_D{p(F(x))\ln{p(F(x))}dF(x)}$. But this is clearly not a sharp maximum description length bound (probably need to introduce some reasonable restrictions).

Looks like I'm missing something obvious, any ideas would be appreciated...

Oh, and this has nothing to do with differential vs discrete entropy, the same question can be posed for the latter case.

[Updated after Peter Shor's comments; also cleaned up language and formulations a bit.]

You're confusing the Shannon entropy of a discrete probability distribution with the differential entropy of a continuous probability distribution. The minimum distribution length is only given by the Shannon entropy for discrete probability distributions.

What the fact that the differential entropy is 0 for this probability distribution means is that for large $k$, you can approximate this random variable with an expected error of $1/2^k$ using $k$ bits. If the differential entropy were $\ell$, you could approximate it with an error of $1/2^k$ using $k+\ell$ bits.


Does Conway's PRIMEGAME generate all prime powers of 2? Most sites I have visited reading on this interesting topic state something along the lines

  "the only powers of two (other than 2 itself) that occur in this sequence are those with prime exponent" (MathWorld)

or

  "After 2, this sequence contains the following powers of 2: [...] which are the prime powers of 2." (Wikipedia)

These careful formulations would imply that the set of powers of 2 generated in the sequence is a subset of prime powers of 2.

However, the OEIS seems absolutely certain that the two sets are equal: http://oeis.org/A034785

This result is also cited on other sites I do not consider very reliable for exact wording, like
http://esolangs.org/wiki/Fractran.

Honestly, I have not understood the internal mechanics of PRIMEGAME enough to answer my own question yet. However, I think it makes a significant difference in the interestingness of PRIMEGAME. Why would sites like MathWorld not state the full fact?

Yes, PRIMEGAME outputs $2^k$ if and only if $k$ is prime.

Conway's original paper is well worth reading if you can track it down.  You can also find a very clear exposition in Richard Guy's paper Conway's prime producing machine (Mathematics Magazine 56(1):26–33, 1983), including the wonderful cartoon below. (Yes, that's Conway with the Alexander horns, referring to a famous drawing by Simon Fraser.)  Conway himself posted a concise proof on the math-fun mailing list.  There's also a brief explanation at the OEIS blog.


Complexity of type-checking in relation to complexity of normalization In order to verify that a terminating program terminates, one thing that can be done is to actually run the program. That may take a lot of time. If the program is typed in a total type-system, we can instead just type-check the program. That will take some time too, sometimes "a lot" too.

I'm looking for results that formalize the relation of the complexity of type-checking to the complexity of normalization for a various type-systems, i.e. possible speedup ratios. Is that relation always well defined? I'm not sure.

But we can give some lower bounds by demonstrating families of typed terms.

I'm interested mostly in any of the well known type systems such as System F, predicative variants of system F, including 'Rank 1' variant and Calculus of constructions.  'Intersection types' are particularly interesting case since they characterize the family of normalizing lambda terms.

The relationship that you're looking for is indeed well-defined, but IMO it's not quite the right thing to look at. For example:

Type checking for terms in the simply-typed lambda calculus is linear time, but normalizing terms in the STLC exceeds any fixed tower of exponentials (i.e., $O(2^{2^{2^{\ldots n}}})$.
Type checking for System F is linear time, but normalization takes as long as any function definable in second-order arithmetic.
For $F^\omega$, typechecking exceeds any tower of exponentials (since you have to normalize simply-typed lambda-terms to do typechecking), but normalization is complete for higher-order arithmetic.
Type inference for rank-1 types (basically, ML-style types) is EXPTIME-complete, but normalization time is somewhere in between the STLC and System
F.
Type inference for intersection types is undecidable (because they characterize halting).

What's going on here is that once you add enough type annotations, typechecking gets easy. If you have to do inference, then the problem gets much harder. This hints that there's a connection between program analysis and evaluation, and the ability of intersection type disciplines to characterize normalization further hints that the key place to look is linear logic.

A good place to get an intuition is from David Van Horn and Harry Mairson's papers Flow Analysis, Linearity, and PTIME and Relating complexity and precision in control flow analysis.

These papers show that for a linear calculus, program analysis and evaluation coincide, because linearity makes the approximation of flow analysis exact.
So by taking a linear calculus and then carefully controlling how much contraction you have via intersection types, you can gain a rather fine control over the complexity of normalization. As you might expect, there is an awful lot of work in this space from the intersection types community.

So rather than trying to summarize it all and missing important references, I'll pick out one line of work I particularly like  (and thereby miss important references on purpose :). This is the work of Damiano Mazza on redoing classical complexity theory in a higher-order implicit complexity framework. Here are three papers I particularly like:

Church meets Cook and Levin. This re-does the famous Cook-Levin proof (that SAT is NP-complete) in an implicit complexity style. The key idea is that you can use affine lambda terms as a kind of "higher-order circuit", and then approximate regular lambda-terms using them.
This idea is explored further in Non-linearity as the Metric Completion of Linearity, which focuses just on this idea (apparently implicit in Girard).
Most recently at POPL this year, Mazza (with Luc Pellissier and Pierre Vial) showed how most linear intersection type systems arise from a general framework for refinement types introduced by Noam Zeilberger and Paul-André Melliès, in their paper Polyadic Approximations, Fibrations and Intersection Types.

I want to emphasize that this is not comprehensive -- chase the references in these papers!


Capacitated multiple vehicle routing problem with handovers I'm looking for literature about a variant of the capacitated vehicle/fleet routing problem (a.k.a. VRP, CVRP, etc.) that takes into account the possibility of handovers between multiple vehicles, i.e. the ability to drop off an item from a vehicle and let another one pick it up.

Put otherwise, we could say we are allowing an item to be transported (sequentially) by more than one vehicle, e.g.:

at time $T^u$ vehicle $V_1$ takes the item from the pick-up location $P^u$
at time $T^d_1 \geq T^u$ vehicle $V_1$ drops it off at an intermediate point $P_1$
at time $T^u_1 \geq T^d_1$ vehicle $V_2$ picks it up from the intermediate point $P_1$
at time $T^d_2 \geq T^u_1$ vehicle $V_2$ drops it off at the intermediate point $P_2$
...
at time $T^u_{n-1} \geq T^d_{n-1}$ vehicle $V_n$ picks it up from intermediate point $P_{n-1}$
at time $T^d \geq T^u_{n-1}$ vehicle $V_n$ delivers it to the final destination $P^d$.

In the VRP overviews I found this variant is not mentioned so I was wondering if anybody knew if it has been investigated at all.

note: the term handover is something I came up with to describe the problem: it may not be the one commonly used to denote this kind of variant. The intended meaning, w.r.t. the example above is that e.g. when vehicle $V_1$ drops off the object $O_1$ at $P_1$ and $V_2$ picks it up we could say that "$V_1$ hands over object $O_1$ to $V_2$ in $P_1$".

update: Reworded to clarify that I'm talking about multiple vehicles (it was just kind-of implicit in the original wording).

These problems are studied but with different terminology such as drop-off. See below and references therein.

The Finite Capacity Dial-A-Ride Problem,
M. Charikar and B. Raghavachari,
in Proceedings of the 39th Annual IEEE Conference on Foundations of Computer Science (1998)

Algorithms for Capacitated Vehicle Routing
M. Charikar, S. Khuller and B. Raghavachari,
in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (1998).

Dial a Ride from k-forest
ACM Transactions on Algorithms, 6(2):2010
Anupam Gupta, MohammadTaghi Hajiaghayi, Viswanath Nagarajan, and R. Ravi


Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space A dynamic predecessor data structure supporting findPredecessor, insert, and delete over unique ordered keys in an unbounded universe in $O(\lg n)$ worst-case time can be stored contiguously using only $O(1)$ extra words of storage in addition to the storage for the keys themselves:

"Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees", Franceschini and Grossi

The structure is complex (IMHO).

Storing $n$ keys in an array that can grow dynamically requires at space for at least $\Theta(\sqrt{n})$ additional keys:

"Resizable Arrays in Optimal Time and Space", Brodnik et al.

Given the latter constraint, is there a simpler dynamic predecessor data structure that uses contiguous space for $n + O(\sqrt{n})$ keys?

There were many implicit ($O(1)$ extra words) dynamic predecessor data structures that predate the result of Franceschini and Grossi:

"Implicit Data Structures for the Dictionary Problem", Frederickson

"Searchability in merging and implicit data structures", Munro and Poblete (does not support delete)

"Developing Implicit Data Structures", Munro

I'm wondering if it is possible to simplify even these structures by using $\Theta(\sqrt{n})$ extra space. I am hoping to find a structure supporting all three operations in $o(n^\varepsilon)$ time.

Pat Morin demonstrates a structure with $O(\sqrt{n})$ extra words of space and $O(\log^2 n)$ insert, delete, and predecessor search in his notes for his advanced data structures class.


Policy Adjustment in Markov Decision Process I was using MDP on my work to make optimal decision. I used discrete time, finite state MDP. I assumed that I will have an initial parameters, like the Reward/Cost, state transition probabilities and actions, to make the optimal decisions. Then, I used the value iteration algorithm to find the expected values for each possible state under the given MDP configuration.

Here is my problem. As I understand, after getting the optimal policy from Value Iteration Algorithm, the policy will stay valid under the initial MDP configuration. However, I believe the policy must be adjusted whenever there is change on MDP configurations (specifically change in Reward/Cost and Transition probabilities). So, I am looking for the best solution that adjust the policy instead of recalculating the policy again using VIA under the new MDP configuration.

My work assumes the states and action doesn't change, only the cost and transition probability changes. Please suggest me any solution or reference to similar works. Thanks.

The set of optimal policies for one MDP may be completely different than for another MDP even if the two MPDs differ only in the rewards and/or transition probabilities.

One thing you might try in order to save resources in some cases when you change the MDP (e.g. when the set of optimal policies does not change too much) is to use policy iteration to find optimal policies and to start it for the new MDP from an optimal policy for the old MDP. Theoretically, you should bear in mind that there are exponential time examples for policy iteration that start and finish at policies that differ in only one action, but these are pathological examples that will almost certainly not arise in practice.

You may find some relevant information if you search for "sensitivity analysis" or "perturbation analysis" for MDPs.


3-colourability of Eulerian maximal planar graph The following paragraph is from this answer by David Eppstein (emphasis mine).

A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single odd vertex requires four colors, and if it is Eulerian then a 3-coloring may be obtained by coloring a triangle and then extending the coloring in the obvious way to adjacent triangles).

(A maximal planar graph is a graph with a planar embedding such that every face is a triangle).
I don't quite understand how emphasized part works as a proof. Let $G$ be a maximal planar graph. If $G$ is 3-colourable, then the 3-colouring is unique (upto swapping of colours) because in every diamond subgraph of $G$, both degree-2 vertices of the subgraph should get the same colour. I suppose this suggests an algorithmic method for testing 3-colourability of $G$ namely (i) pick a triangle, (ii) give a 3-colouring to it arbitrarily, (iii) repeatedly extend it to adjacent triangles (assuming there is no inconsistency), and (iv) finally verify that the assignment is indeed a 3-colouring. If there is a vertex of odd degree, we will not succeed in assigning colour to all vertices. My question is this:-
How can we guarantee that the assignment will be consistent provided all vertices have even degree?
Note: I don't see how Eulerian property (aka all vertices having even degree) ensures consistency of the assignment. I am asking this as a new question rather than a comment to the linked answer because he was answering a different question.

When you make deductions in this coloring problem you are following paths in the dual graph to the triangulation. Any inconsistency could be described by a cycle in the dual graph (a cycle of triangles linked edge-to-edge in the given maximal planar graph) such that, when you color one of the triangles (it doesn't matter which one or which coloring) and then propagate information around the cycle you come back to something different.
If you have a dual cycle that surrounds only a single primal vertex, then it's a wheel, and it's inconsistent if and only if it's an odd wheel.
If you have a dual cycle that surrounds more than one primal vertex, you can draw a dual path inside it that splits it into two dual cycles that each surround fewer primal vertices (this is where we use the fact that the triangulation is on the plane and not on a higher-genus surface). If both smaller cycles are consistent you could glue together consistent colorings of both to get a consistent coloring of the whole thing. So by induction on number of primal vertices contained, when the graph is Eulerian, all dual cycles are consistent.


Level $k$ bounds in Analysis of Boolean functions In Ryan O'Donnell's book Analysis of Boolean functions, following Corollary 9.25 the following appears:

If $f\colon \{-1,1\}^n \to \{0,1\}$, and we have $\mathbb{E}[f] = \alpha$, then for any integer $k$ at most $2\ln \frac{1}{\alpha}$, we have $W^{\leq k}[f] \leq \rho^{-k}\alpha^{2(1-\rho)}$. He then deduces the following corollary:

  If $\epsilon > 0$ and $k_\epsilon = 2(1-\epsilon)\ln \frac{1}{\alpha}$, then
  $W^{\leq k_\epsilon}[f] \leq \alpha^{\epsilon^2}$

My question is isn't this bound meaningless?

Indeed, we have

$W^{\leq k_\epsilon}[f] \leq \lVert f\rVert_2^2 = \alpha \ll \alpha^{\epsilon^2}$

Just posting an answer in order to close the question.

See the helpful comments to the question which contain all the info;

Yes it is vacuous, but if you use the stronger bound you get something nontrivial for large $\epsilon$, of course for fixed $k$ you also have interesting things, it's just the estimates in the book lose too much.
Better bounds are known (thanks ot Yuval) : http://drops.dagstuhl.de/opus/volltexte/2019/10829/pdf/LIPIcs-CCC-2019-7.pdf


Automata : Language Containment, Minimality & Graph Homomorphism Given two DFAs $A$ and $B$ defined on the same alphabet, a (graph) homomorphism $h:A \rightarrow B$ from $A$ to $B$ is a mapping of the states of $A$ into the states of $B$ such that :

if the state $x$ is initial (resp. final) in $A$ then $h(x)$ is initial (resp. final) in $B$
if there is a $\lambda$-transition from the state $x$ to the state $y$ in $A$ then it is also the case from $h(x)$ to $h(y)$ in $B$

Let $A$ and $B$ be two DFAs and $L_A$ and $L_B$ their respective languages,
if there exists a (graph) homomorphism from $A$ to $B$ then $L_A \subseteq L_B$. But the converse does not necessarily hold.

My question : What are the requirements on $A$ and $B$ to get the equivalence between (graph) homomorphism and language containment ? And if the equivalence is possible, what are the properties of such (graph) homomorphism ?

I conjecture that we get the equivalence with the minimality of both automata : if $A$ and $B$ are minimal then there exists a (graph) homomorphism from $A$ to $B$ iff $L_A \subseteq L_B$.

I also suspect this (graph) homomorphism $h:A \rightarrow B$ to be unique. Indeed, because of the determinism, any path in $A$ can be found only once in $B$.

I found very few informations (papers, lecture notes, books, tutorials) about this relationship between (graph) homomorphism and language containment and I would really appreciate any references or any answers regarding this problem.

Thank you very much, Luz :-)

For inclusion, using your condition that non-final states can be mapped to final states does not work. Consider for instance that $A$ is a rejecting sink $p_0$, and $B$ is the minimal automaton for any non-trivial language with a transition $q_0\to q$. Then no such morphism can exist, because we must have $h(p_0)=q_0$, but also $h(p_0)=q$ because of the second condition, although $L(A)\subseteq L(B)$.

If you add the condition that nonfinal states are mapped to nonfinal states, it corresponds to language equality.
You actually just need $B$ to be minimal for the equivalence to hold, assuming all states of $A$ are reachable.

First, notice that the morphism is indeed unique, as you must map the initial state of $A$ to the initial state of $B$, and then the whole morphism (if it exists) is induced by your second condition, since all states of $A$ are reachable.

We can now prove the equivalence. First it is clear that if the morphism exists, then $L(A)=L(B)$, since accepting runs of $A$ are mapped to accepting runs of $B$ and vice-versa.

Conversely, assume that $L(A)=L(B)$, we have to show that the morphism $h$ exists. The only problem we could have when building $h$ in the forced way, is if two words $u,v$ lead to the same state in $A$ but two different states in $B$.
Since $B$ is minimal this means $u^{-1}L(B)\neq v^{-1}L(B)$. But  $u^{-1}L(A)=v^{-1}L(A)$ since both words reach the same state of $A$, we reach a contradiction with $L(A)=L(B)$.

As Andras Salamon mentioned, the minimal automaton is indeed defined as the DFA $B$ such that for any DFA $A$ for the same language, such a morphism $A\to B$ exists.


Time-entanglement phenomenon Please let me mention certain idea here, although it is probably vague (and new, at least as related to experiment mentioned below, as far as I know).

The general notion of algorithm is model of computation with finite number of steps which my be performed on device from "set of computational devices". Up to now "Set of Computational devices" consists of quantum and classical computers which both may be simulated on Universal Turing Machine. It means that Turing machine remains the most general model for computations ( which is in harmony with other notions of effective computable functions like lambda-calculus or recursive functions).

So let me explain motivation to as question at the end:

Turing Machine is in some way connected with notion of time (it is idealisation of computation by performing "one operation" at a time). As we discover new interesting phenomena ( famous discovery: http://arxiv.org/abs/1101.2565 mentioned also here http://www.technologyreview.com/blog/arxiv/26270/ ) probably it is time to ask what is the role of time in Turing Computation model and if it has rigorous enough definition.

Let's imagine a simple Gedankenexperiment: Imagine a class of TM for which initial Data and Result has to be at least 4 ( in general n - natural number) cells one after other - it looks like artificial idea, but when we refer to separation in time - it sound very natural. We use "separation in time" as very natural notion: in fact we require it - answer has to be obtained after question - right?. So, in a light of existence of phenomenon like time-entanglement - mentioned in references above - it is probably time for review... It is not clear for me if this phenomenon point on something new but it may...

Of course "notion of time" is not so important here at all, probably the notion of order is sufficient enough ( although I do not know how such change would result in quantum computations where time is important parameter I suppose, but we may say - in mathematical idelisation/model probably it may be not important).

The questions:

(1) Order dependency of TM - is it new idea?

(2) Is it interesting?

(3) Even for finite sets we still may use abstract concept of lattice to model order of algorithm steps. Is it useful for example for parallel computation model?

(4) It looks like Universal Turing Machine definition use strict order of algorithm steps. Why? If ten we change notion of time order in UTM to notion of abstract order, will that change notion of algorithm/Turing Machine definition? Was that analysed by someone?

(5) When we go to hypercomputational models: may we use continuous index as "time order" replacement? Are there any important consequences of such change?

(6) Was there any influence of time-entitlement on our computational model discussed?

Time-entanglement means that quantum information from the past may be teleported into the future without actually being present in the interval between. However, teleportation of one qubit requires two classical bits and one EPR pair, and these must exist in the interval, so there is no saving of space: you need to get half of the EPR pair and both classical bits into the future, and that requires a qubit's worth of quantum memory. So this process does not effect complexity classes.


Surprising Results in Complexity (Not on the Complexity Blog List) What were the most surprising results in complexity?

I think it would be useful to have a list of unexpected/surprising results.  This includes both results that were surprising and came out of nowhere and also results that turned out different than people expected.

Edit: given the list by Gasarch, Lewis, and Ladner on the complexity blog (pointed out by @Zeyu), let's focus this community wiki on results not on their list.  Perhaps this will lead to a focus on results after 2005 (as per @Jukka's suggestion).

An example: Weak Learning = Strong Learning [Schapire 1990]: (Surprisingly?) Having any edge over random guessing gets you PAC learning. Lead to the AdaBoost algorithm.

Here is the guest post by Bill Gasarch with help from Harry Lewis and Richard Ladner:
http://blog.computationalcomplexity.org/2005/12/surprising-results.html


An algorithm to efficiently draw a extremely large graph in real time Are there any algorithms to draw a billion node graph or to aggregate the information? The idea would be to allow for it to be parallelized using map reduce so it could be done in realtime

I was wondering if there were any other algorithms? A google search turned up nothing.

Very large graph drawing I have found are as follows

http://www2.research.att.com/~yifanhu/GALLERY/GRAPHS/

Below is a sketch of an algorithm I thought up.

Specifically one that you can pan around and zoom? I thought of the following algorithm.

Take a graph layout algorithm (a force directed layout algorithm)
Create a window of locality using a graph metric that you define
Draw everything in an epsilon of that graph metric.
Iterate the window throughout a n-dimentional space. Where n is defined as the amount of data points you have and a tag is a $S \in $ the set of strings. (vertex, edge, $tag_{1}$,  ...  $tag_{n})

--Begin amended algorithm--

Step 5 is due to @vzn answer: Add a visualization of local regions. Therefore we define a region as a set of points that are "close" due to some locality measure. Pagerank is an example so you have a pagerank of 2 you are in the region.

a billion node graphs have probably not been visualized much and are right on the edge of feasibility and an active area of research. the approach would generally have to depend on the unique data characteristics to reveal the features that are relevant/key for that dataset. assuming you mean in 3d. there are at least two roughly independent hard parts of your request

realtime visualization of large dataset
visualizing a very large graph (not nec realtime)

for realtime visualization of a very large graph one could use different approaches. you mention panning and zooming. you do not mention if you want to visualize only local regions. if you want global visualization, either some kind of aggregation method or high performance backend would be required (ie large distributed system).

a reasonable approach would be developing some method of aggregating mass "nearby/related" nodes into representative groups and then visualizing the connectivity of this "super graph" instead. here are some references

[1] Drawing Large Graphs by Low-Rank Stress Majorization Khoury, Hu et al

[2] Multilevel Agglomerative Edge Bundling for Visualizing Large Graphs Gansner, Hu et al

[3] Algorithms for Visualizing Large Networks by Hu

[4] Efficient and High Quality Force Directed Graph Drawing by Hu

[5] Interactive Visualization of Large Graphs and Networks by Munzer

[6] ZAME: Interactive Large-Scale Graph Visualization Elmqvist et al

here is a recent successful example/application/breakthrough discovery that primate brain connectivity (with about 10^10 neurons) follows a grid pattern, by Wedeen et al, based on enhanced MRI mapping/visualization

[7] NIH brain wiring study by Wedeen et al

[8] Spectacular brain images reveal surprisingly simple structure


Clustering of letters - what approach would give the best results? I am working on letter recognition program. I have a text and divide it into letters, every single letter is written to separate file.

Now I want to apply a clustering algorithm to these images to divide letters into classes. Ideally each cluster would correspond to single letter (this is not possible, because some letter patterns like "ri" or "ff" are classified as one letter by my text-dividing algorithm, but I'll address that later). The images contain some noise, as the text is scanned and also not every letter is at the center of the image: some are slightly shifted.

I am quite new to machine learning. Could you advise me on the choice of clustering algorithm? Which would give the best results in this case?

PS.: I am using python for this project, so any algorithms that have implementation in python (even partial) are of particular interest to me.

Check my project ImSim at sf.net: http://sourceforge.net/projects/imsim Actually it's just a very short, simple and single script in Python. It can be adjusted for the purpose of clusterizing very easily.
P.S. Remove resizing from it -- I guess you need not it.
P.P.S. Surely you know PIL library.


Complexity of finding the largest induced subgraph with all even degrees What is the complexity of the following problem?

Instance: Simple, undirected graph $G$, and a positive integer $k$.

Question: Does $G$ have an induced subgraph on at least $k$ vertices, such that all vertices have even degree within the subgraph?

Remark. It is similar to the problem known as Maximum Eulerian Subgraph, which is is NP-complete. However, in Maximum Eulerian Subgraph, beyond the even degrees, it is also required that the subgraph is connected. It is not clear whether dropping the connectivity requirement makes the task easier, or it still remains NP-complete.

The problem is NP-complete. We'll make a series of reductions from max-cut to show this.

Problem 0 (your problem): Given a graph $G$, does G have an induced subgraph with at least k vertices, such that all vertices have even degree within the subgraph?

Problem 1: Given a graph $G$ and subset $A$ of vertices, does $G$ have an induced subgraph with at least $k$ vertices in $A$, such that all vertices have even degree within the subgraph?

Problem 2: Given a graph $G$ and subsets $A, B$ of vertices, does $G$ have an induced subgraph with at least $k$ vertices in $A$, such that all vertices in $B$ have even degree within the subgraph?

Max-cut: Given a graph $G$, does there exist a cut $C \subset V$ of size $|\delta(C)|$ at least $k$? (where $\delta(C)$ is the set of edges in $E$ with exactly one endpoint in $C$)

We'll reduce max-cut to problem 2, problem 2 to problem 1, and finally problem 1 to problem 0, proving that your problem is NP-complete.

First we reduce the max-cut problem to problem 2. Given graph $G = (V, E)$ and $k$, we'll construct $G' = (V', E')$ and $A, B$ such that $G$ has a cut of size at least $k$ if and only if $G'$ has an induced subgraph with at least $k + |E|$ vertices in $A$, where every vertex in $B$ has even degree.

For every $v_{i} \in V$ we'll have a node $v_{i}'$ in $V'$. For every edge $e_{i} = (v_{x_{i}}, v_{y_{i}}) \in E$ we'll have nodes $e'_{i, 0}, e'_{i, 1}$ in $V'$, and edges $(e'_{i, 0}, e'_{i, 1}), (e'_{i, 0}, v'_{x_{i}}), (e'_{i, 0}, v'_{y_{i}}), (e'_{i, 1}, v'_{x_{i}}), (e'_{i, 1}, v'_{y_{i}})$. We'll set $A = B = \bigcup_{i = 1}^{|E|} \{e'_{i, 0}, e'_{i, 1}\}$.

Now, note that if we have exactly one of $v'_{x_{i}}$ or $v'_{y_{i}}$ in our subgraph, we can have both of $e'_{i, 0}$ and $e'_{i, 1}$. However, due to the degree constraint, if we have both or neither of $v'_{x_{i}}, v'_{y_{i}}$, we can have at most one of $e'_{i, 0}$ and $e'_{i, 1}$.

Take a cut $C \subset V$ in $G$ of size $k = |\delta(C)|$. We'll build $C' \subset V'$ s.t. $|C' \cap A| = |E| + k$, and every vertex in $B$ has even degree in the subgraph induced on $C'$. We set $v'_{i} \in C'$ iff $v_{i} \in C$, $e'_{i, 0} \in C'$ for all $i$, and $e'_{i, 1} \in C'$ for $e_{i} \in \delta(C)$. This construction has the claimed properties.

Next take $C' \subset V'$ s.t. $|C' \cap A| = |E| + k$, and and every vertex in $B$ has even degree in the subgraph induced on $C'$. Then we'll build a cut $C \subset V$ of size at least $k$. To do this, just set again $v_{i} \in C$ iff $v'_{i} \in C'$. Now since $|C' \cap A| = |E| + k$, there are at least $k$ edges $e_{i}$ s.t. both $e'_{i, 0}$ and $e'_{i, 1}$ are in $C'$. But for those $i$ we have $e_{i} \in \delta(C)$, hence $|\delta(C)| \geq k$ as desired.

Next we reduce problem 2 to problem 1. Given graph $G = (V, E), A, B$ and $k$, we'll construct $G' = (V', E')$ and $A'$ s.t. $G'$ has an induced subgraph with at least $2k$ vertices in $A'$ where every node has even degree in the induced subgraph if and only if $G$ has an induced subgraph with at least $k$ vertices in $A$ where every node in $B$ has even degree in the induced subgraph.

To build $G'$, We'll make two copies of $G$: for every node $v_{i} \in V$ we'll have nodes $v'_{i, 0}$ and $v'_{i, 1}$ in $G'$, and for every edge $e_{i} = (v_{x_{i}}, v_{y_{i}})$ in $E$ we'll have edges $e'_{i, 0} = (v'_{x_{i}, 0}, v'_{y_{i}, 0})$ and $e'_{i, 1} = (v'_{x_{i}, 1}, v'_{y_{i}, 1})$ in $E'$. Additionally, for every $v_{i} \in B^{c}$, we'll add a new vertex $m'_{i}$, and the edges $(v'_{i, 0}, m'_{i})$ and $(v'_{i, 1}, m'_{i})$. We set $A' = \{v'_{i, 0}, v'_{i, 1} \mid v_{i} \in A\}$.

Take a subgraph $C \subset V$ such that $|C \cap A| = k$ and vertices in $B$ have even degree in the graph induced on $C$. We'll build $C'$ s.t. $|C' \cap A'| = 2k$ and every vertex has even degree in the graph induced on $C'$. To do this, set $v'_{i, 0}, v'_{i, 1} \in C'$ if and only if $v_{i} \in C$. Then, for $v_{i} \in B^{c}$ with odd degree in the graph induced on $C$, we add $m'_{i}$ to $C'$. Now every vertex has even degree in the graph induced on $C'$, since vertices in $B$
have the same degree as in the graph induced on $C$ (hence even degree), we made vertices in $B^{c}$ have even degree, and since $C'$ is the same in both copies of the graph, every vertex $m'_{i}$ has degree $2$ or $0$. Clearly $|C' \cap A| = 2k$.

Now take any subgraph $C' \subset V'$ s.t. $|C' \cap A'| \geq 2k$, and every vertex has even degree in the graph induced on $C'$. We'll construct $C$ s.t. $|C \cap A| \geq k$, and every vertex in $B$ has even degree in the graph induced on $C$. To do this, we first build $C_{0}, C_{1}$, where $v_{i} \in C_{0}$ iff $v'_{i, 0} \in C'$, and $v_{i} \in C_{1}$ iff $v'_{i, 1} \in C'$. Note that $|C_{0} \cap A| + |C_{1} \cap A| = |C' \cap A'| \geq 2k$, hence WLOG $|C_{0} \cap A| \geq k$, and we set $C = C_{0}$. If some vertex $v_{i}$ in $B$ had odd degree in the graph induced on $C$, then $v'_{i, 0}$ would have odd degree in the graph induced on $C'$, hence $C$ has the claimed properties.

The reduction of problem 1 to problem 0 is by far the easiest, and I won't write a detailed proof here. The idea is to add for every vertex $v_{i}$ in $A^{c}$ the vertex $v'_{i}$ and the edge $(v_{i}, v'_{i})$, and finally subtract $|A^{c}|$ from $k$. Now every maximal solution includes one of $v_{i}$ and $v'_{i}$, but cannot include both, since then $v'_{i}$ would have odd degree, hence including $v_{i}$ no longer increases the size of the graph we're inducing on.


Is the value of $\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf}$ polynomially computable? For a graph $G$ on $n$ vertices, what is the value of following ratio:

$$\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf} ,$$

where $L_G=D_G-A_G$ is the laplacian matrix of $G$?

Is this parameter related to the spectrum of $G$?

Is this parameter polynomially computable?

Remark: Note that we have
$$\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{f^Tf} = \lambda_n(G),$$
where $\lambda_n(G)$ is the largest eigenvalue of $L_G$.

Without any further constraints, this expression will in general be unbounded, so the maximum won't exist.

Let $V$ be $\{v_1,\ldots,v_n\}$ with $n\ge 2$. Pick $i\neq j$ such that $v_i,v_j$ are not both isolated. The submatrix of the Laplacian for $v_i,v_j$ has the form $\begin{pmatrix}d_i & -a_{ij} \\ -a_{ij} & d_j\end{pmatrix}$ with $a_{ij}\in\{0,1\}$ and $d_i,d_j\ge a_{ij}$, and $d_i+d_j>0$.

For any $\varepsilon>0$, define a function $f_\varepsilon:V\to\mathbb{R}$ by $f_\varepsilon(v_i) = \sqrt{n}-\varepsilon, f_\varepsilon(v_j) = \varepsilon - \sqrt{n}$, and $f_\varepsilon(v) = 0$ for all other $v\in V$. With this, your expression becomes

$(d_i + d_j + 2a_{ij})\frac{n-2\varepsilon\sqrt{n}+\varepsilon^2}{2\varepsilon\sqrt{n}-\varepsilon^2}$.

$(d_i+d_j-2a_{ij}) \ge 1$ by the above, and for $\varepsilon\to 0$, the numerator and denominator of the fraction converge to $n$ and $0$ (from above); therefore, the expression goes to $+\infty$.


Automated theorem proving in linear logic Is automatic theorem proving and proof searching easier in linear and other propositional substructural logics which lack contraction?

Where can I read more about automatic theorem proving in these logics and the role of contraction in proof search?

Other resources could be found referenced in Kaustuv Chaudhuri's thesis "The Focused Inverse Method for Linear Logic", and you might be interested in Roy Dyckhoff's "Contraction-Free Sequent Calculi", which is about contraction but not about linear logic.

There are opportunities for efficient proof search in linear logic, but I don't think current work indicates that it's easier than proof search in non-substructural logic. The problem is that if you want to prove $C \vdash(A \otimes B)$ in linear logic, you have an extra question that you don't have in normal proof search: is $C$ used to prove $A$ or is $C$ used to prove $B$? In practice, this "resource nondeterminism" is a big problem in performing proof search in linear logic.

Per the comments, Lincoln et al's 1990 "Decision problems for propositional linear logic" is a good reference if you want to get technical about words like "easier."


Finding invariant elements of binary matrix from row and column sums Consider a m-by-n binary matrix A. Given only an m-dimensional vector of its row sums (R) and an n-dimensional vector of its column sums (C), is there an efficient (ie. polynomial time) algorithm that determines which elements of A must be 1 and which elements of A must be 0?

A trivial example: if R = {2,1,2} and C = {1,1,3}, then

$$
 A =
 \begin{bmatrix}
  ? & ? & 1 \\
  0 & 0 & 1 \\
  ? & ? & 1 \\
 \end{bmatrix}
$$

The answer is yes. The basic idea is to determine whether there is a matrix $A$ with $A_{i, j} = 0$ and one with $A_{i, j} = 1$. If both answers are yes, then $A_{i, j}$ cannot be determined. otherwise you will know what it is.

Consider such a problem: Given $r$ (row sum) and $c$ (column sum), how to determine whether there is a solution or not?

This problem can be solved by network flow algorithm. Imagine a bipartite graph $G$ whose two disjoint vertex sets are $S$ and $T$. Each vertex in $S$ corresponds to a row in $A$ (so $|S| = n$), and each vertex in $T$ corresponds to a column in $A$ (so $|T| = m$). The network $N$ can be constructed as follows:

Add edge between source and each $s_i$ in $S$ with capacity $r_i$.
Add edge $E_{i, j}$ between each node $s_i$ in $S$ and $t_j$ in $T$ with capacity $1$.
Add edge between each $t_j$ in $T$ and sink with capacity $c_j$.

Find the maxflow in $N$. All edges form source are full iff there is a binary matrix A whose row sum is $r$ and column sum is $c$. And flow in $E_{i, j}$ equals to the value of $A_{i, j}$. It can be found in poly time.

Consider how to find the answer when some $A_{i, j}$ is determined.

We can also construct a network $N$ as above and change the upper and lower bound of corresponding $E_{i, j}$. If you want to find whether there is solution with $A_{i, j} = v$, you can change the upper and lower bound to $v$. You should run this algorithm $2nm$ times to find whether each $A_{i, j}$ can be $0$ or $1$.

PS: The first problem can also be solved by a theorem called "Gale-Ryser Theorem". But I've no idea how to modify it to solve the second one.


What functions can System F not compute? In this wikipedia article on Turing Completeness it states that:

  The untyped lambda calculus is Turing complete, but many typed lambda calculi, including System F, are not. The value of typed systems is based in their ability to represent most typical computer programs while detecting more errors.

What is an example of a total computable function that is uncomputable by system F?

In addition, since hindley-milner is:

  A restriction of System F

because of the fact that:

  type checking is undecidable for a Curry-style variant of System F, that is, one that lacks explicit typing annotations.

Does this mean that the lambda calculus underlying hindley-milner type systems is not turing complete as well?

If this is true, since haskell is clearly turing complete and we know that it's basis is the lambda calculus and the hindley-milner type system, what features that are not present in the lambda calculus are added in order to make haskell turing complete?

System $F$ is quite expressive. As proved by Girard here, the functions of type $\mathbb{N}\rightarrow\mathbb{N}$ (where $\mathbb{N}$ is defined to be $\forall X.\ X\rightarrow (X\rightarrow X)\rightarrow X$) are exactly the definable functions ($\mathbb{N}\rightarrow\mathbb{N}$) in second order Heyting Arithmetic $\mathrm{HA}_2$. Note that this is the same as the functions definable in second order Peano Arithmetic.

You'll probably want to check Proofs and Types as a more readable reference. Note that this means that a lot of programs can be written in system F, from the Ackermann function to interpreters for Gödel's system $T$. As for any total programing language (with some mild conditions) system $F$ cannot implement a self interpreter, i.e. a function $\mathrm{eval}:\mathbb{N}\rightarrow\mathbb{N}$ which takes as input a code for a term $t$ of system $F$ and returns a (code for a) normal form for $t$. The proof involves a variant of the diagonalizing trick used for undecidability of the halting problem. Andrej explains it beautifully here.

To answer your other questions: The $\lambda$-calculus underlying Hindley-Milner (HM) languages is also not Turing complete. In fact it is significantly weaker than system $F$, closer in expressiveness to the simply typed $\lambda$-calculus.

Haskell is indeed Turing complete. The most distinctive feature enabling this (though there are others) is the presence of unrestricted recursion: the definition of any program (function) can refer to the program itself. This is similar to the addition of a $Y$ combinator, such as is done in the definition of PCF which is simply-typed but retains Turing-completeness with the $Y$ combinator.

Note there are other features which make Haskell Turing complete, but they are not usually taken to be part of the core language, e.g. references to functions, unrestricted datatypes, etc.


Is there any such thing as a non-nested hierarchy? (I didn't see any question like this on the CSTheory exchange -- apologies if it has already been answered.)
In a nested hierarchy, a higher level includes all levels below it.
The classic example of a "non-nested" hierarchy is military rank.  A general is not a lieutenant, so military rank is a non-nested hierarchy.
But here's my objection -- doesn't a general have all the skills a lieutenant has, plus more skills?  So in that sense, isn't every general a lieutenant?  He may not be called "lieutenant", but in reality he is a lieutenant-plus.
Thus, I am wondering... can we really say that any hierarchy is non-nested?

I think this question is more about the semantics of the english language than about cs theory. Unless this has a connection to some problem. I think generally speaking, hierarchy of things just means there is a well ordered relation of these things. And nested just means that the things are nested within each other. The relation is defined based on nesting. So the military ranks are a hierarchy, but not a nested one because the groups aren't nested within each other.


Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$? I am considering ideas about exact quantum algorithms. In particular, I am considering likely limitations of $\mathsf{EQP}$, which consists of languages exactly decideable by polytime-uniform quantum circuit families over an arbitrary finite gate set.

The quantum Fourier transform (QFT), given by
$$ F_N = {\frac{1}{\sqrt N} \begin{bmatrix} 1 & 1 & 1 & 1&  \cdots & 1 \\ 1 & \omega & \omega^2 & \omega^3 & \cdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \omega^6 &  \cdots & \omega^{N-2} \\ 1 & \omega^3 & \omega^6 & \omega^9 & \cdots & \omega^{N-3} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{N-1} & \omega^{N-2} & \omega^{N-3} & \cdots & \omega^{(N-1)^2} \end{bmatrix}} \quad\text{for $\omega = \mathrm e^{2\pi i/N}$},$$
is a celebrated part of quantum computational theory.
In the case of $N = 2^n$, there is well-known decomposition of $F_N$ into Hadamards, SWAP gates, and diagonal gates $$\mathrm{CZ}_{2^T} = \mathrm{diag}(1,1,1,\mathrm e^{2\pi i/2^T\!})$$ for various $T \geqslant 1$, which is due to Coppersmith. If $\mathsf{EQP} \smallsetminus \mathsf{P}$ is to contain any problems, one might hope that one of these would make use of the QFTs $F_{2^n}$, in which case one would require the family of operations $F_{2^n}$ to decompose into some particular finite gate set. Using the recursive decomposition of the QFT, this is equivalent to there being a decomposition of all gates $\mathrm{CZ}_{2^n}$ into a single finite gate set.

Obviously, by the Solovay–Kitaev theorem, we may approximate the gates $F_{2^n}$ or $\mathrm{CZ}_{2^n}$ arbitrarily well with any approximately universal gate set which is closed under inverses. What I would like to know is whether there is a finite gate-set which may exactly realise these families of operators — or, what I suspect is more likely, whether there is a proof that no such finite gate-set exists.

Question.
Is there either a decomposition of $\{ F_{2^n} \}_{n \geqslant 1}$ as a polytime-uniform circuit family on a finite gate-set, or a proof that this is impossible?

No, there is no decomposition of the entire family $\{F_{2^n}\}_{n\geqslant1}$ into a single finite gate-set. Here's why.

The QFTs involve only coefficients over $\overline{\mathbb Q}$, the complex algebraic closure of the rational numbers. In analogy to [Adleman+Demarrais+Huang–1997], if we involved any gates which included any transcendental numbers, we could choose a minimal set of transcendentals $\{\tau_1, \tau_2, \ldots\}$ and describe the gate-coefficients essentially as rational functions $\overline{\mathbb Q}(\tau_1, \tau_2, \ldots)$. To obtain the QFT as a product of such gates, we must arrange for all of the transcendental components to cancel (a similar thing must occur to ensure each of the gates are unitary); but then we might as well replace all of the transcendentals with $0$, so that all of the coefficients are algebraic. So we restrict ourselves to algebraic gate-sets without loss of generality.

The coefficients of a finite gate set over $\overline{\mathbb Q}$ can all be contained in a finite-degree extension of $\mathbb Q$, which one may construct by extending $\mathbb Q$ by those very coefficients. However, the gates $\mathrm{CZ}_{2^n}$ obviously have coefficients belonging to field extensions over $\mathbb Q$ of degree $2^{n-1}$, i.e. of unbounded degree.
Thus the family of QFTs of order $2^n$ does not decompose into any finite gate-set.

As a corollary, we cannot hope to have any algorithms in $\mathsf{EQP}$ which relies on QFTs over cyclic rings of unbounded size — note that the same problem occurs for any family of circuits which might use QFTs of arbitrary order.


Algebraic topology for termination proofs I'm reading about various ways in which termination proofs of software verifiers are built: ad-hoc methods that detect recursions, term-rewriting, synthesis of lexicographic orderings...
From the ad-hoc methods I came with the following intuitive idea. Is it possible to formalize termination with algebraic topology? The idea would be:

look at termination as the problem of finding loops in the code of the program.

look these loops as a fundamental group at some origin (a point in the source code)

test whether this fundamental group is simply connected (implying that this node is terminating)

Of course both problems are undecidable (the second one being testing the simple connectedness) but it seems to me theoretically feasible.
Has this been done before? You find it is not feasible?
Resources I find interesting (feel free to add)
Progress Measures and Finite Arguments for Infinite Computations, page 3.
Power domains and predicate transformers: A topological view (if I ever get access to it)
The topology of program termination.
Scott approach distance on metric spaces

As someone somewhat familiar with termination analysis, I'd say that the techniques are only as ad-hoc as the programs they aim to prove termination of, which is to say very ad-hoc indeed.
The crucial approach to scaling such analyses is modularity which allows decomposing the problem into sub-problems. Indeed this usually consists in identifying cycle-like things, typically either cycles in the control flow graph or the call graph, and decomposing it along it's strongly connected components (SCCs). We have very efficient algorithms to do this. No algebraic topology really required here AFAIK.
This is the easy part. The hard part is then identifying variants for each SCC. Here again you can do things in a modular manner, but it's more subtle. The most relevant fields as far as I can tell are constraint solving, and in particular linear programing and general combinatorial principles often related to Ramsey theory. Again, I'm not sure whether algebraic topology really has a role to play.

I will mention a connection between algebraic topology and rewrite theory though, if that can sate your curiosity: there is a strong analogy between homological algebra and confluence of rewrite systems. In particular, there is a connection between simply connected spaces, and (nice) rewrite systems in which every critical pair is closed (which implies confluence).
Here's some nice notes by Yves Guiraud, Eric Hoffbeck, and Philippe Malbos.
And Here's some really nice slides by Gershom Bazerman. Following the links to those papers should get you somewhere.


Categorical equivalent of higher order logic From Simply typed lambda calculus and higher order logic, I get the impression that HOL is STLC + equality + equality axioms. I was wondering if there is a particular kind of category modelling this.

The structure you want is due to Andy Pitts, and is called a tripos. It extends the notion of hyperdoctrine, which gives a categorical model for first-order logic, with enough structure to model higher-order logic.
However, much more of the work in this part of categorical logic focuses on toposes instead of triposes, which are just a little bit more expressive than HOL (basically you get to form sets by comprehension, too, giving a model of set theory with bounded quantifiers).
References:

Andrew M. Pitts, The Theory of Triposes
Andrew M. Pitts, Tripos theory in retrospect


Open problems on the frontiers of TCS In the thread Major unsolved problems in theoretical computer science?, Iddo Tzameret made the following excellent comment:

  I think we should distinguish between major open problems that are viewed as fundamental  problems, like $ P\neq NP $, and major open problems which will constitute a technical breakthrough, if solved, but are not necessarily as fundamental, e.g., exponential lower bounds on $ AC^0(6) $ circuits (i.e., $ AC^0+\mod 6 $ gates). So we should possibly open a new community wiki entitled "open problems in the frontiers of TCS", or the like.

Since Iddo did not start the thread, I thought I'll start this thread.

Often the main open problems of fields are known to researchers working in related fields, but the point at which current research is stuck is unknown to outsiders. The quoted example is a good one. As an outsider, it is clear that one of the biggest problems in circuit complexity is to show that NP requires super-polynomial size circuits. But outsiders may not be aware that the current point at which we are stuck is trying to prove exponential lower bounds for AC0 circuits with mod 6 gates. (Of course there could be other circuit complexity problems of similar difficulty which would describe where we are stuck. This is not unique.)
Another example is to show time-space lower bounds for SAT better than n1.801.

This thread is for examples like this. Since it is hard to characterize such problems, I'll just give some examples of properties that such problems possess:

Will often not be the big open problems of the field, but will be a big breakthrough if solved.
Usually not unbelievably hard, in the sense that if someone told you that the problem was solved yesterday, this would not be too hard to believe.
These problems will also often have numbers or constants that are not fundamental, but they arise because this happens to be where we are stuck.
The problem at the frontiers of a particular field will keep changing from time to time, as opposed to the biggest problem in the field, which will remain the same for many many years.
Often these problems are the easiest problems that are still open. For example we don't have exponential lower bounds for AC1 either, but since $AC^0$[6] is included in that class, it is formally easier to show lower bounds for $AC^0$[6], and thus that is at the current frontier of circuit complexity.

Please post one example per answer; standard big-list and CW conventions apply. If someone can explain what types of problems we're looking for better than I have, please feel free to edit this post and make appropriate changes.

EDIT: Kaveh suggested that answers also include an explanation as to why a given problem is at the frontier. For example, why are we looking for lower bounds against AC0[6] and not AC0[3]? The answer is that we do have lower bounds against AC0[3]. But then the obvious question is why do those methods fail for AC0[6]. It would be nice if answers could explain this too.

Here are three in shortest paths research:

$1$. Is there a linear time algorithm for single source shortest paths in directed graphs with nonnegative weights, at least in the word-RAM model of computation? Note that a linear time algorithm exists for undirected graphs (see Thorup's paper). Based on that, Hagerup has a runtime of $O(n+m\log w)$ for directed graphs with weights bounded by $2^w$. Is there a faster algorithm?

$2$. Is there an $O(n^\omega$ polylog $n)$ algorithm for all pairs shortest paths in unweighted directed graphs? ($\omega<2.376$ is the exponent of matrix multiplication) The current best runtime is $O(n^{2.575})$ by Zwick, and for undirected graphs the problem can be solved in $O(n^\omega$ polylog $n)$.

(Are the directed problems actually harder?)

$3$. Is there an $O(n^{2.9})$ algorithm for all pairs shortest paths in $n$-node graphs with weights in {$0,\ldots,n$}? Or, is there a reduction from the general all pairs shortest paths problem to this restriction?


NP complete graph problems about structural properties (This question is a bit of a "survey".)
I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural properties. The problem "feels" quite hard, and I fully expect it to be $\mathcal{NP}$-complete. For some reason I'm having a hard time even finding similar problems in literature.
An example of a problem that I would consider comparable to the one I'm dealing with:

Given a weighted tournament $G = (V,E,w)$, is there a feedback arc set in $G$ the edges of which fulfill the triangle inequality?

Note the difference to the traditional feedback arc set (DFAS) problem: I don't care about the size of the set, but I do care whether the set itself has a certain structural property.
Have you encountered any decision problems that feel similar to this? Do you remember whether they were $\mathcal{NP}$-complete or in $\mathcal{P}$? Any and all help appreciated.

I think there are lot of similar problems. Here are two in vertex version and one in edge version:

1) Does a given graph have an independent feedback vertex set? (we don't care about the size of the set).
This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in
Garey, Johnson & Stockmeyer.

2) Does a given graph have a vertex cover that induces a tree? (we don't care about the size of the set).
This paper
gives an NP-completeness proof for this problem (Theorem 2); even for bipartite graphs.

3) Does a given graph have a dominating edge set the edges of which form an induced $1$-regular subgraph?
(also known as dominating induced matching or efficient edge dominating; the vertex version is given in the
second answer by Mohammad.
Again, we don't care about the size of the set).
This problem is NP-complete (well-known, first proved here), even for planar bipartite graphs.

The first two problems are particular examples of the problem class called stable-$\pi$:
Let $\pi$ be a graph property. Does a given graph have a vertex cover satisfying $\pi$?
More NP-complete cases as well as polynomially solvable cases can be found in
this
and in this paper
(and the refs given there) .


What math courses should I take to prepare for a CS masters or PhD? I'm a self-taught professional programmer. I am pretty good at it (Ruby, Unix, Clojure, Java, Objective-C), but now I'm thinking of taking it to the next level by maybe applying for a masters or PhD program in CS. What topics in math should I study to prepare for this goal?

A generally high degree of mathematical maturity makes a lot of the formal aspects of (not necessarily theoretical) computer science much easier to understand. So doing a minor in mathematics along with your major in computer science would do more good than harm.


What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$? What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$? In other words, are problems that admit a polynomial time local search approximable? Do approximable optimization problems imply a local search algorithm in general?

If one wants to approximate the potential function, then yes, there even exists a fully polynomial-time approximation scheme (FPTAS). See

James B. Orlin, Abraham P. Punnen, Andreas S. Schulz: Approximate Local Search in Combinatorial Optimization. SIAM J. Comput. 33(5): 1201-1214 (2004).

For some settings though, this is not interesting. For example, for congestion games, where pure equilibria exist and their computation is PLS-complete, strategy profiles that approximate the potential function well may be very poor approximate equilibria. For some settings, constant-factor approximate equilibria can be computed in polynomial-time even when computing an exact equilibrium is PLS-hard, for other settings it is PLS-hard to compute an approximate equilibrium for any polynomial-time computable non-trivial approximation factor, as explained by the following announcement paper.

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik: Computing approximate pure Nash equilibria in congestion games. SIGecom Exchanges 11(1): 26-29 (2012).

Note PLS might be much easier than FNP.


Dealing with duplicates in Genetic Algorithm I'm using Genetic Algorithm to create a rota for home-care organisation. All the groundwork is complete, I'm getting the results, but results are not as good as expected.
If I calculate fitness for existing rota made by somebody, I get about £6000 (I measure fitness in money - great point for management).

When I run my GA, the best I manage to get is £8K after about 30K generations.
So I know the better solution exists and I'm trying to get better result.
I have tried different approaches - big population, small population, different number of crossover points, swap-mutation, random-mutation, hill-climber-mutation.
And nothing improved the results.

The resulting curve looks like this:

I can run GA much longer, but it does not give me any better results - the curve is just flat horizontal to the right.

I figured that I get quite a lot of duplicated individuals in final population. And that slows down the improvement of the solution.
I learned how to find duplicate individuals. But what do I do with them? I have tried replacing them with randomly created solutions, but usually their fitness is much worse then every body else in the solution space, so they get "killed" quite soon without giving any offsprings or other influence to the solution space.

Any ideas/suggestions/papers will be highly appreciated, as I've run out of ideas and research papers and almost no time left.

UPD: some description of the problem:
There are number of visits(shifts) that are located in different geographical places (distances between locations are known). Currently I work with 700 visits per week with durations from 30 minutes to 5hrs. There are workers with different levels of contractual arrangements: some have 0 contracted hours - relief workers, there are part-timers and full-timers.
I need to allocated workers for every shift in a best possible manner with this factors in mind:

Minimise travel distance for workers. When they have number of shifts in a day, the locations should be roughly in the same area
Workers should not do a lot of overtime hours
Workers should not work less than their contract says
Workers with 0-contracts should be allocated no or very limited working hours
Minimise waiting time between shifts. So no situations when somebody starts one visit at 9am to 10am, and next  visit is at 6pm.
There is a limit of total number of hours that can be worked per day
There is a minimum of working hours per day: nobody should be deployed for only 30-minute visit and no other visits per day.
At least 2 days off allocated for anybody, but can be more
At least 2 days off must be adjacent.

And other minor fitness function adjustments.
I hope this is sufficient for description.

What you've hit upon is the basic mechanism that drives GAs -- convergence to some fixed point that you hope is near optimal. In your case, clearly it isn't. So the name of the game is to try and balance this tendency to drive convergence with the competing interest of exploring the space looking for other solutions. There's no silver bullet for this problem -- you always end up tuning things to suit your particular problem.

In general, there are two ways to do this. One is to delay convergence for longer, thus giving the algorithm more time to find better solutions. You can switch to a weaker selection operator (binary tournament selection for example), you can increase your mutation rate, etc. The other option is to allow the algorithm to converge, but figure out a sensible way to restart the search (as you mentioned, putting random points in tends not to work because their fitness is too low to allow them to survive and contribute to the search).

I'll give an example of the latter approach. There is a relatively-little known algorithm called CHC (Eshelman 1991) that tends to work really well for a lot of problems. Unfortunately, one reason it's little-known is that the only way to access the original paper is to buy the printed proceedings of the first FOGA conference, but you can probably find a little bit of information online, hopefully enough to get you started. I can give you something of a quick overview though. In rough pseudocode, CHC looks like

delta = k/4               # k = chromosome length
while not done
    create new child population
    for i = 1 to n/2     # n = population size
        select p1, p2 from population without replacement
        if hamming_distance(p1, p2) > delta
            c1, c2 = HUX crossover(p1, p2)
            insert c1, c2 into child pop
        end if
    end for
    if child pop is empty
        delta = delta - 1
    else
        take best n individuals from union of parent and child populations as next population
    end if
    if delta < 0
        keep one copy of best individual in population
        generate n-1 new population members by flipping 35% of the bits of the best individual
        delta = k/4
    end if

The HUX crossover operator is like uniform crossover, but instead of choosing randomly between the parents independently for each bit, it exchanges precisely half the differing bits from the parents.

You then just keep running this loop until you decide to quit, either because you've found a good enough solution, you've exhausted the amount of time you have to spend on the problem, or whatever other criteria you desire.