What are the outstanding questions in purely functional data structures? This question is inspired by another question about what's new in PFDS since the publication of Okasaki's book in 1998.

I'll start with two questions I have:

Is there a purely functional set data structure that approaches the speed of hash tables? Tries aren't  there yet.
Are there purely functional finger trees with O(1) append? The best so far is O(lg lg n), devised by Kaplan and Tarjan.

What other purely functional data structure problems are open?

I'll interpret the question somewhat liberally. For Okasaki-style data structures, memoization is a form of implicit mutation that has a side effect on running time. Thus I'll take the question to concern persistent data structures in the strict sense rather than data structures with a purely functional implementation, which are a subset of the former. By strict I mean that you should able to access older versions of a data structure without penalty, the tree of versions can branch arbitrarily, etc.

In that context, I consider persistent UNION-FIND an important open problem. There's the Conchon-Filliâtre paper that was mentioned in the other thread. A commenter already brought up an issue with their so-called persistent array: it's really only semi-persistent. But suppose you replace it with a hash trie or some other truly persistent array that behaves better in the worst (and arguably average) case but worse in the best case. That still leaves an important issue open:

The paper gives a formal proof of correctness in Coq. But they fail to address the amortized complexity either formally or informally. It's very much not clear to me that the complicated behind-the-scenes mutation results in the expected amortized complexity in all cases. When I last thought about it, I felt somewhat confident I could construct a counterexample if I put effort into it. Even if I'm wrong about that last part, the lack of a proper analysis is a major gap; it's clear that Trajan's classical amortization analysis of UNION-FIND doesn't directly transfer.


Generating all instances of a regular language up to a certain length Given a fixed regular language R, what is the complexity of generating all members of R with length at most $n$?  Suppose some reasonable model (RAM with $n$-bit words?) and a write-only output tape.  The list should be in length-lexicographical order.

I'm interested in the answer in terms of the output as well as the input.  (If R = Σ* then you can't improve on $O(|\Sigma|^n)$ but it only takes time linear in the output.)

There are several recent papers that address your question, e.g.:

Margareta Ackerman and Jeffrey Shallit. Efficient Enumeration of Regular Languages. Conference on Implementation and Application of Automata (CIAA) , Lecture Notes in Computer Science, 4783, Springer-Verlag, Berlin Heidelberg, pp. 226-241, 2007.

Margareta Ackerman and Erkki Makinen. Three New Algorithms for Regular Language Enumeration, Computing and Combinatorics: 15th Annual International Conference (COCOON) , Lecture Notes in Computer Science 5609, Springer-Verlag, Berlin Heidelberg, pp. 178-191, 2009.

You can get these two papers from here.


Simple Constructions of Special Graph Families Consider the following definition, taken from Chung's 1978 paper:

  An $(n, m)$-concentrator is a graph with $n$ input vertices and $m$ output vertices,
  $n \ge m$, having the property that, for any set of $m$ or fewer inputs, a set of vertex-disjoint paths exists that join the given inputs in a one-to-one fashion to different outputs. If this graph is directed or acyclic, we call it a directed or acyclic $(n, m)$-concentrator, respectively.

The paper includes definitions for superconcentrators, generalizers, and non-blocking networks. One may also encounter other types of graphs, such as expanders and Ramanujan graphs in the literature.

These types of graphs are usually studied as "families of graphs." There are a number of papers (such as Pinsker [1], Valiant, Pippenger, and Gabber-Galil) which try to explicitly construct such families, while optimizing parameters like size, density, sparsity, and the like.

The problem is that while those papers are excellent for research, they don't help much pedagogically. Let's clarify: Consider a student who sees the definition of a concentrator (or any similar graph) for the first time. His best bet to understand the definition is to imagine it pictorially, or see an illustration of examples and non-examples of a concentrator.

I've been searching for such simple examples of Special Graph Families for quite a while, but didn't achieve much. So, the question is:

  Could you describe simple constructions of special graph families? Illustrations are much appreciated.

Note that the simple constructions need not be optimum in any sense, but they must not be trivial either (e.g. a complete graph is a trivial example for some graph families). I don't formalize the word trivial, and leave it to your judgement.

[1] M. S. Pinsker. "On the complexity of a concentrator", 7th International Teletraffic Conference, pages 318/1-318/4, 1973.

This is a family of expander graphs: let $p$ be a prime, let the vertex set be $\{ 0,\ldots,p-1\}$, connect vertex $x$ to $x+ 1 \bmod p$, to $x-1 \bmod p$ and to $x^{-1} \bmod p$. Each such graph is a cycle, plus a matching over $p-3$ vertices. (The multiplicative inverse is undefined for $0$, and is the element itself for $p-1$ and $1$.)

This is a picture of what it looks like for $p=59$

There is no known elementary proof that this a family of expanders, but the construction is very simple.


What are the limitations on formal proofs of Erlang systems? Well, today I just got my 15 minutes of fame, but now I think I am wrong on the point about formal proofs on Erlang systems.  The discussion on news.ycombinator.com suggests that Erlang code may or may not lend itself so well to formal reasoning (and it's certainly not pure a pure functional language), although a bit of google-fu turns up a fair number of peer reviewed articles on formal proofs on Erlang systems.

I'd like to get this right.  Can somebody here give a decent, in-depth explanation of the ins and outs of formal proofs on Erlang systems?

Erlang is a concurrent, higher-order programming language. To a decent approximation, this covers everything difficult about program verification.

When a language is higher-order, the control structure of the program is not evident from the source code, since code are values, and so the control structure depends on the data flow in the program. When a language is concurrent, this means you have to reason about interference -- the possibility that multiple processes are trying to act on the same data at once. As a result, you have to think through all the possible interleavings of thread executions.

Erlang is a reasonably clean language design, so it doesn't layer many  accidental difficulties on top of these two. But those two capabilities ensure that the essential difficulty is not easy.

In fact, it's fair to say that the general problem of how to verify concurrent higher-order programs is still open --  proofs still tend to be tour-de-force efforts, rather than a systematic application of a methodology. We're a lot closer than we were five or ten years ago, though.


Optimal comparison-based stable sorting in constant space For a comparison based sorting algorithm, it is desirable to:

Be stable
Run in $O(n\ \log n)$
Operate in $O(1)$ space

I can find algorithms that satisfy any two of these but I can't find any that satisfy all three. Does it exist? Is it proven not to exist?

Mergesort satisfies all three requirements (when merging is performed in place).
See Pardo, L.T., "Stable  sorting  and  merging  with  optimal  space  and  time
bounds", SIAM J. Comput. 6 (1977), 351-372.


Quantum PAC learning Background

Functions in $AC^0$ are PAC learnable in quasipolynomial time with a classical algorithm that requires $O(2^{log(n)^{O(d)}})$ randomly chosen queries to learn a circuit of depth d [1]. If there is no $2^{n^{o(1)}}$ factoring algorithm then this this is optimal [2]. Of course, on a quantum computer we know how to factor, so this lower bound does not help. Further, the optimal classical algorithm uses the Fourier spectrum of the function thus screaming "quantumize me!"

[1] N. Linial, Y. Mansour, and N. Nisan. [1993] "Constant depth circuits, Fourier transform, and learnability", Journal of the ACM 40(3):607-620.

[2] M. Kharitonov. [1993] "Cryptographic hardness of distribution-specific learning", Proceedings of ACM STOC'93, pp. 372-381.

In fact, 6 years ago, Scott Aaronson put the learnability of $AC^0$ as one of his Ten Semi-Grand Challanges for Quantum Computing Theory.

Question

My question is three-fold:

1) Are there examples of natural function families that quantum computers can learn faster than classical computers given cryptographic assumptions?

2) Has there been any progress on the learnability of $AC^0$ in particular? (or the slightly more ambitious $TC^0$)

3) In regards to the learnability of $TC^0$, Aaronson comments: "then quantum computers would have an enormous advantage over classical computers in learning close-to-optimal weights for neural networks." Can somebody provide a reference on how weight updating for neural nets and $TC^0$ circuits relate? (apart from the fact that threshold gates look like sigmoid neurons) (This question was asked and answered already)

I'll take a shot at your first question:

Are there examples of natural function families that quantum computers can learn faster than classical computers given cryptographic assumptions?

Well, it depends on the exact model and the resource being minimized. One option is to compare the sample complexity (for distribution-independent PAC learning) of the standard classical model with a quantum model that is given quantum samples (i.e., instead of being given a random input and the corresponding function value, the algorithm is provided with a quantum superposition over inputs and their functions values). In this setting, quantum PAC learning and classical PAC learning are basically equivalent. The classical upper bound on sample complexity and the quantum lower bound on sample complexity are almost the same, as shown by the following sequence of papers:

[1] R. Servedio and S. Gortler, “Equivalences and separations between quantum and classical learnability,” SIAM Journal on Computing, vol. 02138, pp. 1–26, 2004.
[2] A. Atici and R. Servedio, “Improved bounds on quantum learning algorithms,” Quantum Information Processing, pp. 1–18, 2005.
[3] C. Zhang, “An improved lower bound on query complexity for quantum PAC learning,” Information Processing Letters, vol. 111, no. 1, pp. 40–45, Dec. 2010.

Moving on to time complexity, using the same quantum PAC model, Bshouty and Jackson showed that DNFs can be quantum PAC learnt in polynomial time over the uniform distribution [4], further improved in [5]. The best known classical algorithm for this runs in $O(n^{\log n})$ time. Atici and Servedio [6] also show improved results for learning and testing juntas.

[4] N. Bshouty and J. Jackson, “Learning DNF over the uniform distribution using a quantum example oracle,” SIAM Journal on Computing, vol. 28, no. 3, pp. 1136–1153, 1998.
[5] J. Jackson, C. Tamon, and T. Yamakami, “Quantum DNF learnability revisited,” Computing and Combinatorics, pp. 595–604, 2002.
[6] A. Atıcı and R. Servedio, “Quantum Algorithms for Learning and Testing Juntas,” Quantum Information Processing, vol. 6, no. 5, pp. 323–348, Sep. 2007.

On the other hand, if you're interested in the standard classical PAC model only, using quantum computing as a post-processing tool (i.e., no quantum samples), then Servedio and Gortler [1] observed that there is a concept class due to Kearns and Valiant that cannot be classically PAC learnt assuming the hardness of factoring Blum integers, but can be quantumly PAC learnt using Shor's algorithm.
The situation for Angluin's model of exact learning through membership queries is somewhat similar. Quantum queries can only give a polynomial speedup in terms of query complexity. However, there is an exponential speedup in time complexity assuming the existence of one-way functions [1].
I have no idea about the second question. I'd be happy to hear more about that too.


"Checking equality for Kolmogorov complexity of two sequences" is computable? It is a known result that Kolmogorov complexity is not computable for every arbitrary sequence. I wonder whether the following problem is computable or not:

"Given $x$ and $y$ as two sequences, whether $K(x)\overset{+}{=}K(y)$, where $\overset{+}{=}$ means equality in Kolmogorov complexity sense."

My next question is a generalisation of this one, i.e. whether the following is computable:

"Given $x$ and $y$ as two sequences, whether $K(x)\overset{+}{<}K(y)$, where $\overset{+}{<}$ means strictly smaller in Kolmogorov complexity sense."

I think of the following argument: if we can check whether two sequences have equal Kolmogorov complexity we can write a program that enumerates all sequences of length $\le N$ and divides them into equivalence classes.

We know that $K(x) \le |x|$. So, we have at most $N$ equivalence classes of sequences. One of this classes should be of size at least $2^{N+1}/N$. All the sequences in this class have Kolmogorov complexity at least $(N+1 - \log N) \ge N / 2$ (as we have at most $2^{n}$ sequences of Kolmogorov complexity $n$).

So, now we have a program that can generate a sequence of Kolmogorov complexity at least $N/2$ for any given $N$. But this program itself has some fixed length $L$. Choosing $N$ to be greater than $2(L + \log N)$ leads to contradiction.

The same argument should work for $\overset{+}{<}$.

(I omited an additive constant that depends on the description language we choose to define $K(x)$.)


Strengthenings of submodularity A set-function $f$ is monotone submodular if for all $A,B$,
$$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B). $$

A stronger property is
$$ \begin{multline*} f(A) + f(B) + f(C) + f(A\cup B\cup C) \geq \\f(A\cup B) + f(B\cup C) + f(A\cup C) + f(A \cap B \cap C). \end{multline*}$$
Taking $C = A\cup B$, this property implies monotone submodularity.

  Is this property known?

Background

This property came up while trying to characterize coverage functions. Given some weighted universe $U$ (all weights are non-negative) and a family $X$ of subsets of $U$, the coverage function $f(S)$ is defined for $S \subseteq X$ as the total weight of elements covered by sets in $S$. The function $f$ is always monotone and submodular. The converse isn't true.

The property in question implies that $f$ is a coverage function in the case $|X| = 3$. Similar, more complicated properties work for larger $X$. All these properties are satisfied by coverage functions, so this is a complete characterization.

There is a complete characterization of coverage functions in terms of such equations. For |X|>3 there are more equations than the ones pointed. Each of these equations can be thought as a constraint on discrete $k^{th}$ derivative.

Monotone increase function if and only if first order discrete derivative is +ve. i.e. $f(B)-f(A)\ge 0$  when $A\subseteq B$.

Submodularity if and only if second order discrete derivative is -ve. i.e. $(f(A\cup B)-f(B))-(f(A)-f(A\cap B))\le 0$.

Similarly if you have conditions on the next $n$ derivatives you get coverage functions. (I think the signs need to be +ve for even order derivative and -ve for odd order derivative)

Something similar was already known in probability. A coverage function can also be thought as a probability measure (upto a scaling constant). The only reference I was able to dig up was page 439 from Feller's book on probability.


Trampoline that automatically balances heap and stack While working through Fogus' Functional Javascript, I came across the trampoline function, which can be used to make safe recursive functions that don't blow up the stack. In Fogus' words, "Of course there is no free lunch, even when using trampolines. While I’ve managed to avoid exploding the call stack, I’ve just transferred the problem to the heap."

On top of moving this problem to the heap, the trampolined version of the function is slower.

Is it possible to make a "smart" trampoline function that takes two forms of a function, a trampolined version and a non-trampolined version, and chooses (or predicts) the most efficient strategy?*

Ref: https://github.com/funjs/book-source/blob/master/chapter06.js#L195

*(or better yet combines both strategies (is this possible?) that uses fewer trampoline "bounces", where each bounce is almost the maximum number of computations that can be performed recursively using the stack strategy)

Is it possible to make a "smart" trampoline function that takes two forms of a function, a trampolined version and a non-trampolined version, and chooses (or predicts) the most efficient strategy?*

Yes, it's possible to do things like this, but if you control the compiler, it's usually faster and easier to do something else. The main exception is when you are writing parallel code.

Trampolining style essentially does two things.

First, you do a continuation-passing-style transformation to make the continuation explicit as a data structure. However, if you directly represent continuations as functions, the standard calling conventions mean that you will blow the stack. This is because programs in CPS never directly return -- they always pass control to their continuation.
So instead of representing continuations as functions, you represent continuations as resumptions. A resumption is a data structure representing a computation, which lets you evaluate a bit at a time until it is finished. That is, resumptions may be seen as a datatype declaration such as:

type 'a resumption = Done of 'a | Wait of (unit -> 'a resumption)

So a value of type t resumption is either a value Done v containing a value v of type t, representing a finished computation, or it is a value Wait thunk, where thunk is a function that will do some work and hand you back a new resumption representing a bit more progress towards the answer.
Once you represent continuations as resumptions, you can write a scheduler which runs in a while-loop, and incrementally forces the resumption. Since the scheduler runs in a loop, it won't automatically blow the stack. I call this loop a scheduler because precisely the same approach of using resumptions is used in implementations of green/lightweight threads.

Implementing resumptions naively is slow, because the continuations in most programming languages are used in highly stylized ways. That is, in most languages you can implement continuations as a single imperatively-updated stack, and the overhead of trampolining simply arises from the fact that a linked list of thunks is a less efficient representation than a mutable stack. So compiler writers often use resumption-based intermediate forms, but implement them using better data structures. (And as a programmer, you can often use an optimized continuation representation "by hand".)

Papers you might want to look at:

Ganz, Friedman and Wand's 1999 ICFP paper, Trampolined Style

This is probably the best survey paper on trampolining and how it works.
Wand's 1980 JACM paper, Continuation-Based Program Transformation Strategies

This is one of the fundamental papers on using custom data structures to represent continuations, and how it can make algorithms radically more efficient. The notation is kind of old-fashioned and clunky, but once you get past that, it's extremely accessible and mind-blowing. Highly recommended!
Hieb, Dybvig and Bruggeman's 1990 PLDI paper, Representing Control in the Presence of First-Class Continuations

This paper gives a nice example of just how far compiler writers will go to implement continuations efficiently.
Appel's 1993 book, Compiling with Continuations

EDIT: This is not out of print, and if you can afford it, it's a book-length explanation.
Abramsky's CONCUR 1996 paper, Retracing Some Paths in Process Algebra

This paper gives a theoretical introduction to the application of resumptions to concurrency.
Acar, Charguéraud, and Rainey's 2011 OOPSLA paper, Oracle scheduling: controlling granularity in implicitly parallel languages

This paper implements your suggestion of using two versions of the same function, in the context of parallelizing divide-and-conquer algorithms. Basically, the idea is that the optimal point to switch from spawning new tasks for subproblems to doing it sequentially depends a lot on details like the amount of parallelism in your hardware, the cost of thread spawning, and how much work each recursive call will do. So if you write a function to the scheduler can use to estimate how much work is left, it can automatically choose the best point to switch.


Shortest string in the intersection of a context-free language and a regular language For a language $X$, define $ss(X) = \min_{x\in X} |x|$, the length of the shortest string in $X$. For simplicity, we define $ss(\emptyset)=0$.
Let $L$ be a context-free language generated by a context-free grammar with $k$ non-terminals. (assuming all context-free grammars are in Chomsky normal form.)
Let $R$ be a regular language recognized by an NFA of $n$ states.

  What is $ss(L\cap R)$, the length of the shortest string in $L\cap R$?

A naive upper bound is $2^{kn^2}$: find a context-free grammar for $L\cap R$ with $kn^2$ non-terminals.

Motivation: Answer to the above question can lead to a better bound for the following problem.

Let $L$ be a fixed context-free language. Let $\mathcal{R}_n$ to be all the set of all regular languages that can be recognized by an NFA of $n$ states.

Define $f_L(n) = \max_{R\in \mathcal{R}_n} ss(L\cap R)$.

  What can we say about the asymptotics of $f_L(n)$?

Using the naive bound, we know $f_L(n) = O(2^{n^2})$.

Thank you very much for posting this question!

I am very enthusiastic about these kinds of research problems.  Although I don't have a precise answer, I think that the following will be of help.

The Input Format Matters

A context-free language can be represented as CFG or a PDA.  Given that there is a polynomial blow-up in converting from one form to another, we have to be particular about whether $n$ denotes the number of non-terminals from the CFG or the number of states from the PDA.

Similarly, for regular languages, $n$ could denote the length of the regular expression or the number of states from the DFA.

Given that I am personally more comfortable with automata, I will assume that the inputs are given as automata and $n$ will denote the number of states from the larger (or largest) automaton.

A More General Problem

  Consider that we are given a PDA $P$ and $k$ DFA's $D_1, D_2, ..., D_k$.

  If we are promised that the intersection of these automata is non-empty (that is, $L(P) \cap \bigcap_{i\in [k]} L(D_i)$ is non-empty), then in terms of $n$ and $k$, what is the length of the shortest string in the intersection?

Now, you may ask, in the worst case, how large can this shortest string be?  It turns out that there is a constant $c \leq 1$ such that it is always possible to construct a PDA $P$ and DFA's $D_1, D_2, ..., D_k$ so that the shortest string in the intersection has length $2^{n^{c \cdot k}}$.

Note: You will see where $c$ comes from below, but you can probably make it close to $1$.  Maybe even $1 - \varepsilon$?

Construction

  Disclaimer: This is one possible construction although, it might not be the
  preferred construction nor is it necessarily optimal.  One interesting thing about the construction is that there is only one string in the intersection.  The
  construction is inspired by Cook (1971).

Let a number $n$ be given.  Consider an auxiliary pushdown automaton.  That is, a state machine with a stack and a bounded work tape.

If we have $k\log(n)$ bits on the work tape, then we can represent any integer from $1$ to $n^k$.  You can use this integer to represent a stack height.  Now, it is possible to design an auxiliary pushdown automaton with only $k\log(n)$ bits of memory on the tape that counts from $1$ to $2^{n^k}$ and then accepts.  It does this by enumerating through every single configuration of the stack of height at most $n^k$ where the current height is always stored in the $k\log(n)$ bits on the work tape.

  Please let me know if you need more detail in the preceding description.  Otherwise, we will continue our construction.

Now that we have an auxiliary pushdown automaton with only $k\log(n)$ bits on the work tape that runs for $2^{n^k}$ steps before accepting, we can construct $P$ along with $D_1, D_2, ..., D_k$.  This construction is inspired by Kozen (1977) and related works.

The idea is to build the PDA and DFA's to read in a string that encodes a computation of the auxiliary pushdown automaton.  The computation is accepting if and only if the PDA and DFA's all accept its encoding.

The computation is a sequence of configurations.  Each configuration can be encoded by a string so that all of the strings concatenated together make up the computations encoding.  Then, the DFA's each are assigned to a $\log(n)$ length chunk of the work tape and verify that the computation for their respective chunk of the work tape carries on correctly.  Finally, the PDA pushes, pops, and peeks, as is instructed by the configurations and simultaneously verifies that what is on the stack actually matches what the configuration says is on top of the stack.  They accept if both their respective verification is successful and the accepting configuration is reached.

Because the auxiliary pushdown automaton requires a computation of length $2^{n^k}$, the smallest string in the intersection has length at least $2^{n^k}$.  And, although it wasn't discussed in detail, the automata can be built to have polynomial in $n$ states.  The smaller the degree of the polynomial, the closer that $c$ can be made to 1.

Other Works

There is a great master's thesis by Thomas Ang on the length of the
shortest string in the intersection of regular languages.
Also, I made a small contribution to a paper with D. Chistikov, W.
Czerwinski, P. Hofman, and M. Pilipczuk where we show that the
shortest string accepted by a one counter automaton has length at most $c
   n^2$ for an appropriate constant $c$ (the previously known upper bound was $n^3$).

Dmitry and I have been discussing for a couple years about what the upper bound is for the shortest string accepted by a PDA.  You can get a lower bound of $2^n$ and an upper bound of $2^{n^2}$, but can you improve either of these bounds?  Even just a small improvement on the upper bound to $2^{\frac{n^2}{\log(n)}}$ would be a breakthrough.

Sorry for such a long reply and for excluding many details.  Feel free to shoot me an email if you would like to discuss offline.  Thank you and I hope you have a great week!


On Graph Isomorphism Complete Problems I am interested to study Graph Isomorphism (GI) complete problems.

In the Paper " Problems Polynomially Equivalent to Graph Isomorphism" by Kellogg S. Booth, (1979), proved that many basic problems are GI complete by using Edge replacement techniques, Composition techniques etc.

I would like to learn some more techniques which are used in recent papers.

Can some one suggest me some recent papers which are more concentrated in proving some graph class is GI complete.

Graph Isomorphism Completeness for Perfect Graphs
and Subclasses of Perfect Graphs
C. Boucher D. Loker (2006)

  In this paper, we prove that deciding
  isomorphism of double split graphs, the class of graphs exhibiting a 2-join, and the class of
  graphs exhibiting a balanced skew partition are GI-complete. Further, we show that the GI
  problem for the larger class including these graph classes–that is, the class of perfect graphs–is
  also GI-complete.


Paths of length $p$ in a Graph, $p$ a prime I came across the following decision problem, for which I wondered whether anybody of you came across a similar problem and can give me some insight on its nature/complexity.

Given as input a directed labeled graph $G = (V, E)$ and nodes $s,t \in V$, the question is whether there exists a path $\pi$ between $s$ and $t$ whose length equals some prime $p$ (in $\pi$, we allow repetition of vertices so that a self-loop answers this question trivially with yes.)

Thanks!

The problem (let me call it $s$-$t$-prime-connectivity) is in P; more precisely, it is NL-complete.
NL-hardness is clear: we can reduce plain $s$-$t$-connectivity to $s$-$t$-prime-connectivity just by making sure that every vertex has a self-loop. Then, if there is any path from $s$ to $t$, there are paths of arbitrary lengths $\ge n$, and in particular, of prime lengths.
In order to check $s$-$t$-prime-connectivity in NL, we may use the following characterization, based on an idea of Yonatan N from the comments above:

Theorem. For any directed graph $G=(V,E)$ of size $n=|V|$, and $s,t\in V$, the following are equivalent:

There is a path from $s$ to $t$ of prime length $p>n$.

There are a simple cycle $C$ of length $d\le n$, and a path $P$ from $s$ to $t$ of length $a$ coprime to $d$ that intersects $C$.

There are $C$ and $P$ as in 2, where $a\le2dn\le2n^2$.

There is a path from $s$ to $t$ of prime length $p>n$, $p=n^{O(1)}$.

Proof:
$1\to2$: Let $P$ be a prime-length path from $s$ to $t$. If it has length $p>n$, it includes a simple cycle $C$; clearly, the length of $C$, being $\le n$, is coprime to $p$.
$2\to3$: Let $u$ be a vertex common to $P$ and $C$. Write $P$ as the concatenation of paths $P_0$ from $s$ to $u$, and $P_1$ from $u$ to $t$. It suffices to show that there is a path $P'_0$ from $s$ to $u$ whose length is at most $dn$, and congruent to the length of $P_0$ modulo $d$; and similarly for $P_1$.
This can be shown by the pigeonhole principle: if the length of $P_0$ is $\le dn$, we are done. Otherwise there are two occurrences of the same vertex in $P_0$ whose positions in $P_0$ modulo $d$ are the same; in other words, $P_0$ includes a cycle whose length is a multiple of $d$. We may delete this subcycle from $P_0$. We repeat this process until the length of the path drops below $dn$.
$3\to4$: We may assume $a>n$. By Linnik’s theorem, the arithmetic progression $a,a+d,a+2d,\dots$ contains a prime $p$ of magnitude polynomial in $n$; $p$ is the length of a path from $s$ to $t$ consisting of $P$ and several repetitions of $C$.
$4\to1$ is trivial.
QED
Condition 4 gives directly an NL-algorithm for $s$-$t$-prime-connectivity: nondeterministically guess a prime $p\le n^c$ (where $c$ is the implied constant), and a path from $s$ to $t$ of length $p$.
In fact, already condition 2 gives an NL-algorithm: nondeterministically choose to either guess a prime $p\le n$ and a path from $s$ to $t$ of length $p$, or: $d\le n$, a vertex $u$, a cycle of length $d$ starting from $u$, and a path from $s$ to $t$ passing through $u$, of length coprime to $d$. The space required by the algorithm consists of a constant number of vertices, the number $d$, and the length of the path being guessed modulo $d$; these all fit in $O(\log n)$ bits.


Open access journals With the advent of internet (and common sense) there is more and more demand for open-access research. Several researchers (including me) find it frustrating that published peer-reviewed research articles are behind paywalls. I am looking for journals and conferences (related to theoretical computer science, graph theory, combinatorics, combinatorial optimization) that make all accepted publications freely available to everyone.

Some such journals are Theory of Computing, The Electronic Journal of Combinatorics, Logical Methods in Computer Science

If you know more such journals (or) conferences, please mention them in your answers.

EDIT : As suggested by David Eppstein in his answer, I am adding one more constraint. Please write only those journals/conferences that do not charge authors exorbitant fees to publish.

Conferences with proceedings published in the LIPIcs series:

STACS
FSTTCS
CCC (since 2015)
TQC (Theory of Quantum Computation, Communication and Cryptography)
ICALP
APPROX/RANDOM
SoCG
SWAT
ESA
MFCS


Checking if all products of a set of matrices eventually equal zero I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix.

This means exactly what you think it does: we will say the set of matrices $\{A_1, \ldots, A_k\}$ has the property that all of its products eventually equal zero if there does not exist an infinite sequence $i_1, i_2, i_3\ldots$, all in $\{1, \ldots, k\}$, such that $$ A_{i_1} A_{i_2} \cdots A_{i_l} \neq 0$$ for all $l$.

Has the problem of deciding whether every product eventually equals zero been studied before? Is it decidable?

Seems like it might be related to matrix mortality, which is undecidable, but I do not see a clear connection.

Your question is equivalent to whether $A_1, \dotsc, A_k$ generate a nilpotent algebra, which in turn is equivalent to each of the $A_i$ being nilpotent. Hence not only is it decidable, but in $\tilde O(n^{2 \omega})$ time where $\omega$ is the exponent of matrix multiplication.

Let $\mathcal{A}$ be the associative algebra generated by the $A_i$: that is, take all linear combinations of the $A_i$ and all finite products thereof. $\mathcal{A}$ is called nilpotent if there is some $N$ such that every product of $N$ elements of $\mathcal{A}$ is zero.

First, let's see why your condition implies that $\mathcal{A}$ is nilpotent. This follows from Konig's Lemma (compactness): every string of length $n$ over the alphabet $\{1, \dotsc, k\}$ corresponds to a product of $A_1, \dotsc, A_k$ of length $n$ in an obvious manner. Consider the infinite $k$-ary rooted tree, whose nodes are naturally in bijective correspondence with strings over $\{1, \dotsc, k\}$. Consider the sub-tree $T$ consisting of those nodes where the corresponding product of the $A_i$ is nonzero. Konig's Lemma says that if $T$ is infinite, then it has an infinite path (exactly violating your property), hence $T$ is finite. We can then take $N$ to be the maximum length of any string in $T$. So your property implies that $\mathcal{A}$ is nilpotent.

The converse is also true, since every element of $\mathcal{A}$ is a linear combination of products of the $A_i$.

Next, note that $\mathcal{A}$ is a subalgebra of $n \times n$ matrices, and hence is finite-dimensional.

Finally: a finite-dimensional associative algebra in characteristic zero has a basis of nilpotent elements (commuting or not - this is the part that contradicts Yuval's answer) iff it is nilpotent (see, e.g., here).

Thus, to solve your problem, find a basis for the associative algebra generated by the $A_i$ (by the linear-algebra version of breadth-first search) and check that every matrix in the basis is nilpotent. The upper bound $\tilde O(n^{2\omega})$ comes from solving a system of linear equations in $n^2$ variables in the breadth-first search. As $\dim \mathcal{A} \leq n^2$ the BFS can't last very long, and because these are $n \times n$ matrices to check if a matrix $A$ is nilpotent one needs only check that $A^n = 0$.


Smoothed Analysis: If a Problem has Pseudopolynomial Complexity, is it in Smooth P? I have been facinated by the extraordinary explosion in Smoothed Analysis and was struck by a assertion in the paper Smoothed Analysis of Integer Programming. This stated that Integer Linear Programming is in Smoothed P if Polynomially Bounded. This was essential true by the virtue that Integer Programming is Pseudo-polynomial!

The question therefore is:

  Does this carry over to other problems universally? In particular what are the constraints?

Integer programming is strongly NP-hard, thus integer programs can in general not be solved in pseudo-polynomial time. The result of Röglin and Vöcking is that, provided that the range of integers that the variables can assume is polynomially bounded, (randomized) pseudo-polynomial solvability is equivalent to polynomial smoothed complexity. Thus, general integer programs do not have polynomial smoothed complexity.

The statement "randomized pseudo-polynomial complexity = polynomial smoothed complexity" is not known to be true in general. For instance, the flip heuristic for Max-Cut runs in pseudo-polynomial time, but it is unknown if a local optimum w.r.t. the flip heuristic can be found with polynomial smoothed complexity (cf. Etscheid and Röglin, SODA 2014).


What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$? We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n)$. We also know that $\mathsf{polyL} \neq \mathsf{P}$ because the latter has complete problems under logarithmic space many-one reductions while the former does not (due to the space hierarchy theorem). In order to understand the relationship between $\mathsf{polyL}$ and $\mathsf{P}$, it may help to first understand the relationship between $\mathsf{L}^2$ and $\mathsf{P}$.

What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

What about the stronger $\mathsf{L}^{k} \subseteq \mathsf{P}$ for $k>2$, or the weaker $\mathsf{L}^{1 + \epsilon} \subseteq \mathsf{P}$ for $\epsilon > 0$?

The following is an obvious consequence:
$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ would imply $\mathsf{L} \subsetneq \mathsf{P}$ and therefore $\mathsf{L} \neq \mathsf{P}$.

By the space hierarchy theorem, $\forall \epsilon > 0: \mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon}$ .
If $\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ then $\mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$.


Ladner's Theorem vs. Schaefer's Theorem While reading the article "Is it Time to Declare Victory in Counting Complexity?" over at the "Godel's Lost Letter and P=NP" blog, they mentioned the dichotomy for CSP's.  After some link following, googling and wikipeding, I came across Ladner's Theorem:

  Ladner's Theorem:  If ${\bf P} \ne {\bf NP}$, then there are problems in  ${\bf NP} \setminus  {\bf P}$ that are not ${\bf NP}$-complete.

and to Schaefer's theorem:

  Schaefer's Dichotomy Theorem: For every constraint language $\ \Gamma $ over $\{0, 1\}$, if $\  \Gamma $ is Schaefer then ${\bf CSP}(\Gamma)$ is polynomial time solvable.  Otherwise, ${\bf CSP}(\Gamma)$ is ${\bf NP}$-complete.

I read this to mean that, by Ladner's, there are problems that are neither ${\bf P}$ nor ${\bf NP}$-complete, but by Schaefer's, problems are either ${\bf P}$ and ${\bf NP}$-complete only.

What am I missing?  Why don't these two results contradict each other?

I took the condensed version of the above theorem statements from here.  In his "Final Comments" section, he says "Thus, if a problem is in ${\bf NP} \setminus {\bf P}$ but it is not ${\bf NP}$-complete then it can not be formulated as CSP".

Does this mean ${\bf SAT}$ problems miss some instances that are in ${\bf NP}$?  How is that possible?

You need  to understand that $\mathsf{CSP}$  problems have a structure that generic $\mathbf{SAT}$ problems do not have. I will  give  you  a  simple example. Let $\Gamma=\{\{(0,0),(1,1)\},\{(0,1),(1,0)\}\}$.   This language is  such that  you can only  express equality  and inequality between   two  variables.  Clearly any such set of constraints is solvable in polynomial time.

I  will  give  you  two  arguments  to  clarify  the  relation  between
$\mathsf{CSP}$ and clauses. Notice that all that follows assumes $\mathbf{P}\not=\mathbf{NP}$.

First: constraints have a fixed number  of variables,  while  the encoding  of intermediate problems may need  large clauses. This is not  necessarily an issue when such large constraints can  be expressed as a conjunction  of small ones  using auxiliary  variables.  Unfortunately this is not always the case for general $\Gamma$.

Assume $\Gamma$ to just contain the $\mathsf{OR}$ of five variables.  Clearly you  can express the $\mathsf{OR}$ of less variables   by  repeating   inputs.  You   cannot  express   a  larger $\mathsf{OR}$  because the  way  to do  it  using extension  variables requires  disjunctions  of positive  and  negative literals.  $\Gamma$ represents relations  on variables,  not on literals.  Indeed when you think  about 3-$\mathbf{SAT}$ as  a $\mathsf{CSP}$ you  need $\Gamma$ to contain four relations of disjunction with some negated inputs (from zero to three).

Second: each relation in $\Gamma$ can be expressed as a batch of clauses with (say) three literals.  Each constraint must be a whole batch of such   clauses.  In   the  example   with equality/inequality   constraints    you   cannot   have    a   binary $\mathsf{AND}$ (i.e. relation ${(1,1)}$) without enforcing a binary negated  $\mathsf{OR}$   (i.e.  relation  ${(0,0)}$)   on  the  same
variables.

I hope this illustrates to you that $\mathbf{SAT}$ instances obtained from $\mathsf{CSP}$s have a very peculiar structure, which is enforced by the nature of $\Gamma$.  If the structure is too tight then you cannot express hard problems.

A corollary of Schaefer Theorem is that whenever $\Gamma$ enforces a structure loose enough to express $\mathbf{NP\backslash P}$ decision problems, then the same $\Gamma$ allows enough freedom to express general 3-$\mathsf{SAT}$ instances.


Maximum item in data stream I have N elements and need to find the maximum of these elements. At each time tick, exactly one of the N elements is updated and I need to determine the new max element (more specifically, the index of the max element). How can I do this by accessing as little "state" as possible?

The naive approach is to store all N elements and in each tick read the N elements and determine the max element. Here the amount of "state" accessed corresponds to N elements.

Is it possible to determine the max element by maintaining lesser state -- specifically state that grows sub-linearly as N increases? Essentially I do not want to make a pass on the entire set of N elements. Assume N is a fixed number.

It seems like this problem has the flavor of data streaming algorithms like the count(-min) sketch. We have N buckets -- items being streamed in update the count of one of these N buckets -- and wish to perform some query on these N buckets with sub-linear space usage.

I understand how sketches can be used to query the value of the Nth bucket, but do not understand if it can be extended to obtain an estimate for the max value (and specifically, the index of the max element). The heavy hitters problem outputs items above a certain frequency, but I am interested only in the item with the maximum frequency.

Am I over-thinking this problem? Is there a far simpler solution?

In the streaming model, any constant approximation of the maximum requires $\Omega(N)$ space. Showing this for a small enough constant approximation follows by an easy reduction from the disjointness problem in two-party communication complexity. This is now very standard, but I will describe it below anyways.

Recall that in the disjointness problem Alice is given a binary string $x \in \{0, 1\}^N$, and Bob is given a string $y \in \{0, 1\}^N$, and they want to decide whether $x$ and $y$ have disjoint support. It is a classic result that this task requires that Alice and Bob exchange at least $\Omega(N)$ bits, even if they share random bits and only want to succeed with probability $2/3$ over the choice of randomness.

Assume there is a randomized streaming algorithm $A$ with space complexity $S$, which with probability $2/3$ computes a number $a$ such that $\frac{a}{F_\infty} \in (\frac{2}{3}, \frac{4}{3})$, where $F_\infty$ is the true maximum frequency of the $N$ elements. This gives a protocol for the disjointness problem with $S$ bits of communication, and therefore $S = \Omega(N)$. In the reduction, Alice simulates the algorithm $A$ and feeds it a stream which increases the frequency of element $i$ by $1$ for each $i$ such that $x_i = 1$. Then Alice takes the memory state of $A$ (which has only $S$ bits) and sends it to Bob, who then simulates $A$ starting from the state he received from Alice and feeds it a stream which increases the frequency of $i$ by $1$ for each $i$ s.t. $y_i = 1$. Then Bob decides that $x$ and $y$ have disjoint support if the output $a$ of $A$ is at most $4/3$.

For more information, see Alon, Matias, and Szegedy's beautiful paper, which introduced the streaming model and proved the first lower bounds.


Semantic distance between excerpts of text. I'm wondering how far along the natural language processing is in determining the semantic distance between two excerpts of text.

For instance, consider the following phrases

Early this morning I got up and washed my car.
I cleaned my truck up this morning.
Bananas are an excellent source of potassium.

Clearly (to the human reader) the first two statements are much more similar to one another than they are to the third statement.  Does there exist any theory that would allow a computer to draw the same conclusion?  What about if we allow longer excerpts such as new articles?

Meta info: this is my first post here, so feel free to direct me to a better forum for asking such a question if this isn't where I should be.  Also, feel free to retag my question with anything more appropriate.

You are looking for "lexical cohesion". Try searching for this term and you will get tons of literature. After constructing the so-called "lexical chains", well-known graph partitioning and information retrieval algorithms can be used to group them into semantic classes. There is in fact a lot of theory and algorithms behind this "post-processing". Dictionary of synonyms and antonyms is often used to construct these chains. I worked on such extraction algorithms during my undergraduate days, about 10 years back. So this field must be more advanced now.


Streaming derandomization Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been cited for use in stream algorithms thus far:

$k$-wise independent PRGs like the 4-wise independent family used by Alon/Matias/Szegedy for the original $F_2$ estimation problem, and generalizations for 2-stability-based methods for (say) $\ell_2$ sketching
Nisan's PRG that works in general for any kind of small-space problem.

I'm particular interested in methods that can be implemented. On the face of it, both of the above approaches seem relatively easy to implement, but I'm curious if there are any others out there.

Some streaming algorithms use expander graphs. This is a somewhat extreme form of de-randomization though (no random bits, in principle).


Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion? Let $f: \{-1,1\}^n \rightarrow \{-1,1\}$ be a Boolean function.

The Fourier expansion of $f$ is
$$f(T) = \sum_{S \subseteq [n]} \widehat{f}(S)\ \chi_S(T)$$
where $\widehat{f}(S)$ are real numbers and $\chi_S(T)=\Pi_{i \in S} T_i$ is a parity function.

Let $d$ be the degree of the the Fourier expansion of $f$, i.e.
$d= \max_{\widehat{f}(S)\neq 0} |S|$.

By Parseval's identity we have
$$\sum_{S \subseteq [n]} \widehat{f}(S)^2=1$$

I am looking for a bound on
$$\sum_{S \subseteq [n]} |\widehat{f}(S)|$$

I think it is bounded by $d$.
But I have neither a proof nor a counterexample for this claim. Can someone provide a proof or give a counterexample?

It is a standard fact that if $f:\{-,1,1\}^n \to \{-1,1\}$ is a function of Fourier degree $d$, then its Fourier coefficients are multiples of $2^{-d+1}$. In particular, every non-zero coefficient must be at least $2^{-d+1}$ in absolute value. Therefore, by Parseval, there are at most $2^{2(d-1)}$ non-zero coefficients, and so the spectral norm of $f$ is at most
$$\sum_{S}|\hat{f}(S)| \leq \sqrt{2^{2(d-1)}}\sqrt{\sum_{S}\hat{f}(S)^2} = 2^{d-1}$$.

This bound is tight. For example the complete binary decision tree of depth $d$ has spectral norm $2^{d-1}$. This can be shown, e.g., by induction on $d$.
The address function has also maximal possible spectral norm.


What automorphisms on a Markov Chain imply a uniform limiting distribution? Consider an irreducible aperiodic Markov chain $M$, modeled as a connected directed graph with weighted edges. The existence of certain (graph) automorphisms on this Markov chain imply various symmetries regarding the limiting distribution. What properties can be demanded of an automorphism or set of automorphisms on $M$, in order for the limiting distribution to be uniform?

This is perhaps a nearly trivial observation, but I couldn't think of another general property just of the automorphisms that would ensure the limiting distribution is uniform.

If the automorphism group of the corresponding weighted directed graph is vertex-transitive, then the limiting distribution must be uniform, since then no vertex can be distinguished from any other.


What is computational complexity of calculating the Variance-Covariance Matrix? I am using a calculation of the Variance-Covariance matrix in a program I wrote (for Principal Component Analysis), and am wondering what the complexity of it is. While obviously the Eigenvector decomposition is causing the largest performance hit, I am wondering how much of that hit is caused by the Covariance Matrix computation.

The asymptotic running time I estimate it to use is $O(N\cdot n^2)$ using a naive algorithm, because it has to take the means of all the data of size $N$ and then has to do it for every dimension (where $n$ is the number of dimensions) in a nested iteration, and thus producing a $n^2$ size matrix.

Is my assumption correct, or if not what is the asymptotic complexity?

Your conjecture is correct.

If $X\in \mathbb{R}^{N \times n}$ with $N$ as number of datapoints and $n$ being the number of features, then you can obtain the covariance matrix by $X^TX$ (apart from the mean subtraction which can be ignored from a complexity perspective).

Thus, covariance matrix computation is matrix multiplication which is naively indeed in $\mathcal{O}(Nn²)$ see here, since you have to do roughly $2N$ operations to fill every of the $n²$ positions in your covariance matrix $X$. In practice, matrix multiplication is speeded up to $\mathcal{O}(n^{2.73})$ for quadratic matrices (see the link).


Derandomizing Valiant-Vazirani? The Valiant-Vazirani theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an unsatisfiable formula - then NP=RP. This theorem is proved by showing that UNIQUE-SAT is NP-hard under randomized reductions.

Subject to plausible derandomization conjectures, the Theorem can be strengthened to "an efficient solution to UNIQUE-SAT implies NP = P".

My first instinct was to think that implied there exists a deterministic reduction from 3SAT to UNIQUE-SAT, but it's not clear to me how this particular reduction can be derandomized.

My question is: what is believed or known about "derandomizing reductions"? Is it/should it be possible? What about in the case of V-V?

Since UNIQUE-SAT is complete for PromiseNP under randomized reductions, can we use a derandomization tool to show that "a deterministic polynomial time solution to UNIQUE-SAT implies that PromiseNP = PromiseP?

Under the right derandomization assumptions (see Klivans-van Melkebeek) you get the following: There is a polytime computable $f(\phi)=(\psi_1,\ldots,\psi_k)$ s.t. for all $\phi$,

If $\phi$ is satisfiable then at least one of the $\psi_i$ has exactly one satisfying assignment.
If $\phi$ is not satisfiable then all of the $\psi_i$ are unsatisfiable.

You need k polynomial in then length of $\phi$. Probably can't be done for $k=1$.


Numerical stability of Simplex method The simplex algorithm is often treated either within real arithmetic, or in the discrete world with exact computations. However, it seems to be implemented most often with floating-point arithmetic.

This leads to the question whether the simplex algorithm should be regarded as a numerical algorithm, in particular how round-off errors affect the computation. I am not interested in practical implementations, but rather in theoretical foundations.

Are you aware of any research on this issue?

Yes, there is research on this issue.

The Simplex Method is Not Always Well Behaved, Wlodzimierz Ogryczak

retroLP, An Implementation of the Standard Simplex Method, Gavriel Yarmish and Richard Van Slyke

A Numerically Stable Form of the Simplex Algorithm, Philip E. Gill and Walter Murray

You might also be interested in the revised simplex method.  This method can take advantage of matrix sparsity; it doesn't keep a representation of the entire matrix.
This thesis was of great interest to me: A Comparison of Simplex Method Algorithms.


Optimal encoding of $k$-subsets of $n$ A colleague asks the following question:

  Let $S_k$ denote the subsets of $n$ of size $k$. Is there an optimal
  and efficient encoding of these subsets ? Namely, is there an function
  $f$ from $[0,1]^{\log \binom{n}{k}}$ to $S_k$ that can be computed
  efficiently (ideally in linear time).

This is a question of encoding and decoding constant-weight code. There are several possible efficient algorithms for that, that provide different efficiency benefits.

Here's a list of some papers on this field:

Tenkasi V. Ramabadran. A Coding Scheme for m-out-of-n Codes. IEEE Transactions on Communications, 38(8):1156–1163, August 1990.

Vitaly Skachek, Kees A. Schouhamer Immink: Constant weight codes: An approach based on Knuth's balancing method. ISIT 2011: 321-325

Chao Tian, Vinay A. Vaishampayan, Neil J. A. Sloane: A Coding Algorithm for Constant Weight Vectors: A Geometric Approach Based on Dissections. IEEE Transactions on Information Theory 55(3): 1051-1060 (2009)
and its followup
N. J. A. Sloane, Vinay A. Vaishampayan: Generalizations of Schöbi's Tetrahedral Dissection. Discrete & Computational Geometry 41(2): 232-248 (2009)

All three approaches are/seem to be efficient, but concrete approaches are very different. The first paper uses arithmetic decoding/encoding, the second paper generalizes Knuth's algorithm, and the third paper uses a geometric approach.


Matrix multiplication in $O(n^2 \log n)$ I was searching about Matrix multiplication, So I first visit wiki matrix multiplication algorithms, In references I found a paper which claim that uses $O(n^2 log(n))$ algorithm , I'd going to read article but it's complicated and will takes too many time to read it, but if there is anyone who reads this article or knows about this algorithm, Is this true? and are you knowing about the base Idea of this to describe it a little.

Thanks in advance, I know it's a bit general question but, if I found it's good approach I'll going to learn details.

I came across this paper about a year ago, but have not gotten around to reading it closely. I can tell you that the approach is not believed to be correct. On page 36 of the same paper, there is an attached comment by Don Knuth, who points out what looks to be a serious shortcoming of the approach.

To understand this paper, you will need to learn about group algebra and representation theory. It will be tough if you haven't seen that kind of material before.


Naive shuffle algorithm Let us have a "shuffle algorithm":

for i in range(len(vec)):
     swap(vec[i], vec[rand()%len(vec)])

Why the reshuffles we get using this algoritm for a number of times turn out to be biased (unequal)?

You can also try to get some intuition from the "correct" version, Fisher-Yeates / Knuth shuffle.

for i in range(len(vec)-1):
    swap(i, randint(i, len(vec)-1))

The idea is that, when we get to i, the previous elements are perfectly random, so let's leave them there and recursively shuffle the rest. In contrast, the naive algorithm will sometimes "reach backward" to make a swap.

Now I'm noticing that in the naive shuffle, elements which are below the current index i can only ever move forward from now to the end of the algorithm. Okay, so in particular, the last element only has two ways to end up in the first position: Either the first element can swap with him, and then nobody else ever swaps with him (this has about a $\frac{1}{n}\frac{1}{e}$ chance), or else nobody ever swaps with him until the last round, and then he swaps with whoever's in first (this has the exact same chance). So the last element should only end up first with probability about $\frac{2}{en} \approx 0.74\frac{1}{n}$ instead of $\frac{1}{n}$.

I simulated this in python with n=100 and 100,000 trials, and got 734 trials in which the last element ended up first, versus 992 trials using Fisher-Yeates.


What NP-complete problems are most similar to integer factoring? The exact complexity of factoring integers (the decision problem) is a major open question in TCS (with important implications, especially in cryptography because of the RSA algorithm), and is widely conjectured to lie "between" P and NP-complete (see the AKS algorithm and Shor's algorithm for two other key aspects of its significance).

Yet, there is so much diversity among the NP-complete problems, including some relating to factoring types of objects and problems in number theory.

  What are some of the "closest" or "nearest" NP-complete problems to integer factoring?

Optionally, an answer might indicate why such problems are thought not to be equivalent to integer factoring under polynomial time reductions (even circumstantial evidence would be appreciated).

The textbook of Computational Complexity: Modern Approach, by Arora and Barak gives such example:

They define the decision problem Integer Factoring on input of three positive integers,

$\text{Integer Factoring} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$.

They state that Alon and Kilian showed that if integer $p$ is not required to be prime number then the problem becomes $NP$-complete.


Maximum cliques of the transitive closure of a chordal DAG Let $G=(V,A)$ be a directed acyclic graph, for which the underlying
undirected graph is chordal (so that every induced cycle in the
underlying undirected graph is a triangle).
It is known that in a chordal graph the number of maximum cliques
is linearly bounded in the number $|V|$ of vertices.
Let $G'=(V,A')$ be the transitive closure of $G$, so that for
every directed path $p= (v_i,\ldots,v_j)$ from $v_i$ to $v_j$
in $G$, there exists a directed edge $(v_i,v_j)$ in $A'$.

Question: Is there any polynomial/linear bound on the number
of maximum cliques in the undirected graph that underlies $G'$?

I think you can extend Vinicius dos Santos' idea to show that no polynomial bound is possible.
Consider a graph on $n$ vertices divided into $d\geq 1$ groups of size about $n/d$ as follows:

Its transitive closure has about $(\frac{n}{d})^d$ maximal (undirected) cliques.


Does the 0-1 principle apply to merge networks? For sorting networks, the 0-1 principle says that if it can sort any sequence of 0's and 1's, then it can sort any list.

What if I want to build a comparison-swap network for merging two pre-sorted lists.  Can I still rely on the 0-1 principle to determine if my network is correct?

Note: If so, this means it's possible to determine whether a network is a merging network in polynomial time (since there are only polynomially-many pairs of sorted lists of zeros and ones)

$\def\et{\mathbin\&}$Yes, and this holds much more generally. Note that a comparator can be thought of as a pair of gates, one of which computes $\min\{x,y\}$, and the other $\max\{x,y\}$. A linearly ordered set is a distributive lattice with $x\land y=\min\{x,y\}$ and $x\lor y=\max\{x,y\}$. We have the following 0–1 principle:

Let $C$ be a circuit with $\land$ and $\lor$ gates, and $\phi(u_1,\dots,u_n)$ a property of values of nodes of $C$ expressible as a conjunction of quasi-identities in the language of lattices (i.e., implications of the form $t_1=s_1\et\dots\et t_k=s_k\to t_0=s_0$, where $t_i$ and $s_i$ are terms using $\land$, $\lor$, and the variables $u_j$).
If $\phi(u_1,\dots,u_n)$ holds whenever $C$ is evaluated in the $\{0,1\}$ lattice, then it holds whenever $C$ is evaluated in an arbitrary distributive lattice.

This is an immediate consequence of the facts that the $2$-element lattice generates the quasivariety of distributive lattices (i.e., every distributive lattice can be embedded in a direct product of $2$-element lattices), and that values of nodes of $C$ are lattice terms in values of the input variables.
Note that $t\le s$ is equivalent to $t\land s=t$, hence we can freely use inequalities instead of equalities in the statement above.
Now, if $C$ is a comparator network with inputs $x_1,\dots,x_n,y_1,\dots,y_n$ and outputs $z_1,\dots,z_{2n}$, it automatically computes a permutation of the inputs, hence the property that it correctly merges sorted lists can be expressed by the conjunction of the quasi-identities
$$x_1\le x_2\et\dots\et x_{n-1}\le x_n\et y_1\le y_2\et\dots\et y_{n-1}\le y_n\to z_i\le z_{i+1}$$
for $i=1,\dots,2n-1$, hence if it works for $0$–$1$ inputs, it also works over arbitrary linearly ordered sets.


Does the physical Church-Turing thesis imply that all physical constants are computable? The physical Church Turing thesis is a conjecture that any physically computable algorithm can be computed by a Turing machine.

Let us create a machine that, for example, outputs the digits of the fine-structure constant. The Fine-structure constant is measurable, and does not depend on the units of measure.

This would seem to imply, via the physical Church Turing thesis, that the fine-structure constant is computable by a Turing machine! This seems unlikely, since only countable many numbers have that property.

You appear to be positing a universe where (a) the fine-structure constant has an exact value and (b) we can measure as many digits of it as we want. Thus, if a Turing machine cannot compute the exact value of the fine-structure constant, it cannot predict the outcome of an arbitrary experiment.

I don't believe (b) is the case. Generally, the way that constants are measured is by measuring the ratios of some physical quantity that we can measure directly, like time, and using this ratio to compute the constant. The smallest unit of time that exists is believed to be on the order of the Planck time, which is $5.39 \times 10^{ −44}$ s. The age of the universe is $4.32 \times 10^{17}$ s. Thus, if we constrain our experiment to take no more time than the age of the universe, we can measure time to at most 61 digits of accuracy, so this is the limit of accuracy for the fine structure constant. This constant can easily be hard-coded in a Turing machine.

Is (a) the case? That may be a matter for philosophers. If changing the 100th digit of a physical constant has absolutely no impact on the dynamics of the universe, does that constant really have an infinite nuber of decimal places?

UPDATE: The best you could hope for (and I don't believe physicists currently know how to do this) is an experiment that measured $k$ digits of the fine structure constant in time $2^k$. In this case, the strongest version of the physical Church-Turing thesis would imply that the fine structure constant is computable. But you would be able to simulate an experiment that took $2^k$ years to carry out by using an oracle that gave you $O(k)$ bits.


Size of BSP tree for a simple polygon? Is there a known bound on the size of a BSP tree for a simple polygon?  I am aware of the result by Toth which gives a tight $\Theta(n \log(n) / \log(\log(n)) )$ bound on the size of a BSP consisting of $n$ disjoint segments, but I wonder if it is possible to do better given some of the special properties of simple polygons.  For example, it is trivial to show that convex polygons can be represented by BSP trees using at most $O(n)$ nodes.  Is it possible to represent simple polygons in linear space as well?

No, simple polygons are not any easier than disjoint segments. Given any n disjoint segments, there is a simple polygon with O(n) edges that includes all of the input segments as sides of the polygon. Then, any BSP tree for the polygon forms a BSP tree for the segments.

One way to do construct a polygon for a set of segments would be to triangulate the planar straight line graph formed by the input segments, and then pick a spanning tree of the triangulation, which is necessarily non-crossing. Then form a simple polygon by walking around an Euler tour of the spanning tree, using each of the input segments the first time the Euler tour traverses that edge and a parallel segment near it the second time the tour traverses it.


Ladner's Theroem Proof I was reading up proof of Ladner's Theorem and I found this :

$$\mathrm{SATH} = \{ (x,\mathrm{pad}) \mid x \in \mathrm{SAT} \text{ and } |\mathrm{pad}|=|x|^{H(|x|)}\}.$$

If SATH is NPC (which implies that SATH not in P) and $H(|x|)$ goes to inﬁnity,
then SAT in P!

Proof: Suppose $f(x) = (x',\mathrm{pad})$, such that $|(x',\mathrm{pad})| \leq c|x|^c$. If $|x'|>|x|/2$,
then $|\mathrm{pad}| = |x',|x|^{H(|x|)} > c|x|^c$ (for long enough $x$). So $|x'|$ is
at most $|x|/2$.

Repeat to solve SAT.

What does it mean to repeat and solve sat? How does this make SAT in P.

Recap:

At this stage in the proof of Ladner's Theorem, it has already been shown that $H(n)$ tends towards $\infty$ as $n$ does. You are assuming that $\text{SAT}_H$is $\text{NP-complete}$ for the sake of contradiction. Equivalently: $\text{SAT} \le_p \text{SAT}_H$.

The mapping used in the reduction, $f(x)$, maps $\langle \varphi , pad \rangle$ to a $\langle \varphi' , pad \rangle$. Because of the polynomial time limitation, $\langle \varphi' , pad \rangle$ has to be, at most, of size $c\left|\langle \varphi , pad \rangle\right|^c$. If the size of $\varphi$ remains unchanged, then the length of the padding causes $\langle \varphi' , pad \rangle$ to be too large.

The only alternative is to assume that $f(x)$ somehow reduces the size of $\varphi$ to compensate for possible growth of the padding. It is pointed out that size of $\varphi'$ is less than or equal to $\left|\varphi\right|/2$.

The primary observation here is that $f(x)$ has significantly reduced the size of the $\varphi$ we need to consider in polynomial time.

Answer:

Take padding out of the picture completely and just consider instances of $\text{SAT}$ (with formula $\varphi$). Take a modification of $f$ to ignore padding and compose it $\text{log}_2(\left|\varphi\right|)$ times on our input $\varphi$. The result is a boolean formula, $\varphi^*$, of constant size that is satisfiable if and only if $\varphi$ is. The satisfiability of $\varphi^*$can trivially be determined in far less than polynomial time. So overall, this entire procedure must decide any $SAT$ instance in polynomial time.

Because this violates Ladner's assumption that $\text{P} \ne \text{NP}$, $\text{SAT}_H$ could not possibly be $\text{NP-complete}$.


Reservoir sampling of distinct values I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass through the data is possible.

In my case, the stream contains many duplicate values, and I need to make sure that my sample won't include any duplicate values. It is important to note the the number of distinct values in the stream is huge as well (to big to fit memory).

Standard reservoir sampling algorithms (e.g. Algorithm R) ensure that the probability of any index being sampled is equal or about equal. In my case however, I need to make sure that the probability of any value being sampled is equal, or about equal.

Is there any way to achieve this?

This is something that min-wise independent hashing is good for. (See a wikipedia explanation here.
The idea is to use a family $\mathcal{H}$ of hash functions so that when you pick a random function $h\in H$ from the family, for any set $S$ of $n$ elements, for any $x\notin S$,  $\Pr_{h\in \mathcal{H}}[h(x) < \min_{y\in S} \{h(y)\}] = \frac{1}{n+1}$. This means that every element in $S$ has the same likelihood of being the only one with the smallest hashed value.

As you scan the stream, keep track of the smallest hashed value that you have seen, and whichever element was mapped to that value is your sample. There are families of hash functions that are almost minwise independent families. For example a paper by Dahlgaard and Thorup  .
If you want to sample $k$ elements you could do this naively using $k$ hash functions, but you could also use ideas from bottom-$k$ sketching with only one function. See this paper by Thorup.


What is the counting complexity of random 2-SAT? Has any work been done on how the complexity of random instances of #2-SAT varies with the clause density? That is: how does the difficulty of counting satisfying solutions to a randomly generated instance of 2-SAT vary, as the clause density varies? In particular, are there any rigorous results known involving critical thresholds?

Of course, because  2-SAT ∈ P, the typical counting complexity depends partly on the probability with which an instance is satisfiable; instances whose clause density is above the critical threshold for SAT/UNSAT will typically have an easy counting complexity, as the answer is "zero" almost surely, in the limit n $\to \infty$. However, the counting complexity may still be easy for instances of 2-SAT having a density near to or just above the critical threshold for finite n: one might expect that a satisfiable instance will have only a small number of solutions, which might be easy to enumerate due to the tightness of the constraints.

For k-SAT with k ≥ 3, the difficulty of determining whether an instance is satisfiable or unsatisfiable  seems to be highest near the critical thresholds separating the SAT phase from the UNSAT phase, in part as one tries to determine whether there exists at least one satisfying solution. For #2-SAT, the difficulty cannot lie in determining whether at least one solution exists; so one should expect that the difficulty is likely to be in determining the number of solutions for satisfiable formulae of a significant but not large number of constraints — that is, where there are enough constraints to induce non-trivial dependencies between variables, but not so many as to over-determine the possible assignments.

Perhaps this paper can help you:

New Worst-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter by J. Zhou, M. Yin, C. Zhou (2010).

And this one that studies the structure of the set of solutions of a random 2-SAT instance: Satisfying Assignments of Random Boolean Constraint Satisfaction Problems: Clusters and Overlaps by G. Istrate (2007)


Practical limits of big-O performance scaling Lets imagine we have an algorithm made up of a set of operations. Let assume that it has three kind of operations and the time complexity is  $t(n) = An + Bn\log n + Cn^2$. This algorithm has asymptotic performance $O(n^2)$.

Now, on a real computer (or a more sophisticated abstract machine that doesn't assume infinite capacity, I guess), I eventually hit issues with the complexity of these operations (e.g. a garbage collector, memory paging, cache, ...) which cause $C$ which is a constant in the abstract model to become itself a function of $n$.

Is there a name for this? Is there a framework in which these kinds of issues can be placed?

Obviously from the question and the lack of jargon, I'm a practitioner, not a computer scientist (my PhD was in AI, not CompSci). But the issue is critically important for studying actual algorithm behavior, and so I'd appreciate any help in finding resources that put it into a less ad-hoc context.

While I'm not entirely sure what you're getting at, there are a number of frameworks that explicitly capture the cost changes that show up when we hit real resource limits. Three examples:

the external memory framework that emphasizes the expense of going to disk (idealized by setting main memory reference costs to 0, and disk reference costs to some fixed constant)
The cache-oblivious model that assumes an unknown cache size and performance hits for going beyond.
The streaming computational model in which only you're only allowed sublinear working storage.

Are these along the lines that you're thinking ?


Why is the Greedy Conjecture so difficult? I recently learned about the Greedy conjecture for the Shortest Superstring Problem.

In this problem, we are given a set of strings $s_1,\dots, s_n$ and we want to find the shortest superstring $s$ i.e. such that each $s_i$ appears as a substring of $s$.

This problem is NP-hard and after a long sequence of papers the best known approximation algorithm for this problem has a ratio $2+\frac{11}{30}$ [Paluch '14].

In practice, biologists use the following Greedy algorithm:

At each step, merge two strings that has maximum overlap over all pairs (the maximum suffix that is the prefix of another string), and repeat on this new instance until there is only one string left (which is a superstring of the all input strings)

A lower bound of $2$ in the approximation ratio of this Greedy Algorithm can be obtained from the input $c(ab)^k,(ba)^k,(ab)^kc$.

Interestingly, it was conjectured that this is the worst example i.e. that Greedy achieves a $2$-approximation for Shortest Superstring Problem. I was very surprised to see that such a natural and easy algorithm is so difficult to analyse.

Are there any intuitions, facts, observations, examples that suggest why this question is that challenging ?

Let me first try to summarize what is known about the Greedy Conjecture.

Blum, Jiang, Li, Tromp, Yannakakis prove that the Greedy Algorithm gives a 4-approximation, and Kaplan and Shafrir show that it gives a 3.5-approximation for the Shortest Common Superstring problem.
A version of the greedy algorithm is known to give a 3-approximation (Blum, Jiang, Li, Tromp, Yannakakis).
The Greedy Conjecture holds when all the input strings all of length at most $3$ (Tarhio, Ukkonen; Cazaux, Rivals) or $4$ (Kulikov, Savinov, Sluzhaev).
The Greedy Conjecture holds if the Greedy Algorithm happens to merge strings in some specific order (Weinard, Schnitger; Laube, Weinard).
The Greedy Algorithm gives a 2-approximation of the compression Tarhio, Ukkonen (which is defined as the total length of the input strings minus the length of the shortest common superstrting).
There is an extremely efficient implementation of the Greedy Algorithm Ukkonen.

I think that one of the reasons why it's hard to prove the Greedy Conjecture might be the following.
Most of the approaches to proving approximation guarantees of the Greedy Algorithm analyze the overlap graph (or, equivalently, the prefix graph) of the input set of strings. We know only some properties of these graphs (such as Monge and Triple inequalities), but these properties are provably not sufficient for proving the Greedy Conjecture (Weinard, Schnitger; Laube, Weinard).


Ownership types and Separation Logic Ownership types and Separation Logic seem to have similar goals, control over ownership and aliasing.  Perhaps, I should also add: the ability to write modular specifications.

What is known about the relationship between ownership types and Separation Logic?

The way I understand the difference is that ownership types constrain
the shape of the object graph, and substructural systems (like
separation logic) manage permissions to access the heap.

In the original work on ownership types, the idea is to maintain the
invariant of owners as dominators. An object $o$ is dominated by
an object $d$, if every path from the root set to $o$ contains $d$. So
$o$ is only reachable from $d$. So the system is designed so that
class declarations are parameterized by their owners, and then this
fact gives you a derived frame condition for $o$: its state cannot
change unless a method on its owner $d$ is invoked.

In contrast, substructural systems like linear types and separation
logic rely on the idea of resources. Each region of the heap is a
resource, and if you don't possess the resource you can't touch it.
This makes frame conditions very easy: they always hold.

One superficial difference (which nevertheless confused me for a long
time) was that ownership types were types, and separation logic was a
program logic. Luckily, while ownership types were born in a
type-theoretic setting, people have applied these ideas to program
logics as well.

The two main pieces of theoretical work I know on this are Kassios's
work on dynamic frames, which Bannerjee and Naumann (and their
students) systematically exploited in their work on regional logic.

As I understand it, their basic approach is to take Hoare logic, and
then:

Add a new type of region variables, which you use to associate objects and regions.
Add an effect system to Hoare logic to track the regions reads and writes touch.
Use the effects to determine if an assertion is frame-respecting or not.
If it is, you can frame it, and if it isn't, you can't.

Each approach has benefits and weaknesses.

Ownership makes frame properties significantly less convenient to
use than in substructural approaches, since you have to compute frame
conditions.
On the other hand, algorithms on DAGs support prettier inductive
proofs in an ownership style, since you can decouple the footprint
from the pointer structure. In a separation-style spec, the natural
thing is to give an inductive invariant on a spanning tree.  But if
the spanning tree the algorithm computes is ever different than the
one your invariant has, you're in for a world of hurt.

My general sense is that separation is easier to use than ownership,
since we need frame properties for nearly every command in an
imperative program. (Dave Naumann argues that region logic is more amenable to automation, since the assertion logic remains plain old FOL, and so
you can use off-the-shelf theorem provers and SMT solvers.)

EDIT: I just found the following paper by Matt Parkinson and Alex Summers, The Relationship between Separation Logic and Implicit Dynamic Frames, where they claim to give a logic unifying the two methods.


Difference between a cyclic and a left-recursive context-free grammar? I am currently reading a paper indicating that a cyclic CFG and a left-recursive CFG are different things:

  The original purpose of the LC transform is to allow
  simulation of left-corner parsing by top-down parsing,
  but it also eliminates left recursion from any noncyclic
  CFG.
  (from page 5 of http://research.microsoft.com/pubs/68869/naacl2k-proc-rev.pdf)

Note the second part of this quote:

  it also eliminates left recursion from any noncyclic
  CFG.

I though that a cyclic grammar and a left-recursive grammar go hand in hand? What's the difference?

Thanks for any hint on this!

A context-free grammar is cyclic if there exists a non-terminal $A$ and a derivation in one or more steps $A\Rightarrow^+ A$.  It is left-recursive if there exists a non-terminal $A$, a mixed sequence of terminals and non-terminals $\gamma$, and a derivation in one or more steps $A\Rightarrow^+ A\gamma$.

Hence cyclic implies left-recursive, but the converse does not hold.  Note that a cyclic grammar can have infinitely many parses for a single terminal string---that might be problematic---, while there is little interest in having cycles in the applications I know (natural language processing and programming languages syntax), thus they are usually removed.


Constrained shortest path problem Here is my problem:
I have an undirected graph (with loops). We have k different classes of vertices in the graph. You can think of class 1 vertex being colored green, class 2 vertices colored red and so on. There is also a special class of vertices colored white (more later).

Now, the user will specify a source vertex, a destination vertex, and a sequence of distinct vertex classes (non-white) eg.

We are given source vertex 10, destination vertex 40, and a sequence:
red->blue->black.

We have to find the shortest path such that the path starts from vertex 10, touches 1 red vertex followed by 1 blue and 1 black vertex and then reaches vertex 40. The path, however, can have as many white vertices as needed. It can also traverse a white vertex twice.

So a solution can be:
10->20(white)->35(red)->21(white)->22(white)->30(blue)->34(black)->40

Incorrect:

10->20(white)->30(blue)->21(white)->22(white)->35(red)->34(black)->40 (goes to blue before red)

We can modify Dijkstra's algorithm to solve this problem too. For each vertex, in Dijkstra's algorithm, we store the shortest path to that vertex obtained so far. Here, we store $r+1$ different shortest paths per vertex (where the required colour sequence is $c_1,c_2,\ldots ,c_r$). In each vertex, the first path corresponds to shortest path so far, containing only whites. And for $i=1,2,\ldots ,r$, $(i+1)^{th}$ path is the shortest path so far, that contains vertices of colours $c_1,c_2,\ldots ,c_i$ (in that order) mixed with white vertices.

While modifying shortest paths for the new node, we will modify all $r+1$ paths if it is white and if it is of a different colour $c$, only those $(i+1)^{th}$ paths are modified which have $c_{i+1}=c$. And when the algorithm ends, the $(r+1)^{th}$ path in each vertex gives the required shortest path to that vertex.

Complexity will be $r$ times the complexity of Dijkstra's. Note that we have not assumed the colours in the sequence to be distinct (so we can get shortest paths with required sequence as red-black-red-blue too). Also, we can easily modify this to allow multiple vertices of same colour to occur together (i.e., red-red-black-blue can be considered same as red-black-blue).


SDP relaxation of independent set I'm looking at page 28 of Lovasz "Semidefinite programs and combinatorial optimization" and it gives the following approximation of independence number of the graph

$$\max u' Z u$$
subject to
$$Z\succ 0$$
$$Z_{ij}=0 \ \forall ij\in E(G)$$
$$tr(Z)=1$$

Can I get independent set (or something close to an independent set) directly from the solution of SDP relaxation? Lovasz says that SDP is the only known way to solve this problem exactly for perfect graphs, is that still true?

Clarification: there's a similar SDP relaxation for the size of maximum cut, and I can get the full solution (the actual cut, rather than its size) by taking square root of Z and doing randomized rounding (Ch.6 of Williamson/Shmoys book). I'm wondering if there's a similar technique for this problem

I believe SDP is the only known technique to solve the maximum independent set problem on perfect graphs. To get the independent set, one could do the following. Guess if a vertex is in the independent set, delete it and solve the SDP. If it returns the same value, then there is an independent set without this vertex. So, make this vertex adjacent to all other vertices, and continue. This should give you an actual independent set.

Otherwise, we have identified one vertex of the independent set, and we can remove it and continue on the remaining graph.


Does polynomially bounded number of witnesses and polynomial time decidability imply polynomial time enumeration? Let us assume that $\text{P=NP}$.

Let $\#\Pi$ be a counting problem in $\#\mathrm{P}$ and let $\Pi$, the decision version that asks if the count is positive, be in $\mathrm{P}$.

In general, instances to a problem in $\#\mathrm{P}$ may have a count that is exponentially larger than the input size.  Suppose however that for any instance to $\#\Pi$, the count is bounded by some fixed polynomial of the input size.

Given these assumptions, can we enumerate all witnesses being counted by $\#\Pi$
in polynomial time when $\text{P=NP}$?

Yes, you can do this unconditionally in $\mathrm{FP^{NP}}$, which equals $\mathrm{FP}$ by your assumption.

The algorithm is a version of binary search: if the witnesses you want to count are binary strings of length $n^k$, then compute by iteration on $i\le n^k$ the list of all their prefixes of length $i$. This list has polynomial length during the computation since there are only polynomially many witnesses in total, and given a prefix of length $i$, we can check which of its extensions of length $i+1$ are prefixes of a witness by an $\mathrm{NP}$ query.


Computational Complexity of Computer Vision Problems What is the computational complexity of computer vision problems (reconstruction, detection, etc.)? Are these problems NP-complete? Are they NP-hard?

In most cases this will boil down to determining the computational complexity of the corresponding machine learning problem. Although generally the machine learning problem is approached statistically rather than combinatorially, I guess this is still pertinent.

Could you also point me to some literature which answers (or tries to answer) this question?

Computer vision is not well defined as a theory problem, but machine learning does have a nice theoretical framework called PAC learning in which one can try to address your question.

It is open whether learning is hard, i.e. whether there exists an class that is impossible to efficiently (PAC) learn.

Some results that indicate learning is probably hard:

Some classes (e.g. automata) are cryptographically hard to learn.
Some classes (e.g. k-term DNF) are NP-hard to properly learn.

Perhaps some good news?: we're unlikely to find an NP-Hardness of learning result unless the polynomial hierarchy collapses.


Suggested approach to cover data structure literature I am not sure if this question is odd topic or too broad, but I have been wondering about this for a long time, and I would very much appreciate any valuable inputs.

As a new grad student working on data structures (in this case, related to pattern matching literature), how would someone get through the huge amount of literature that needs to be covered? I have a reasonable understanding of basic data structures, but each time I open a research paper, there are heaps of new terms that I haven't heard before. In an effort to broaden my knowledge, I have been reading a few textbooks. For instance:

Advanced data structures by Peter Brass
Compact Data Structures A Practical Approach by Gonzalo Navarro (which is quite hard to get through)

Still, getting through the research papers seems like a never ending battle. What is a really good approach to get an overview of such huge volume of works done in the area?

If you're looking for data structures at a graduate level, my suggestion would be Erik Demaine's online course materials for his class "Advanced Data Structures" (video lectures and notes) available through MIT Open Courseware at https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/

Unfortunately I don't think there is really a good textbook on this material at this level; for this reason, in my own graduate data structures course, I use a collection of Wikipedia readings instead.


What is the complexity of decision tree complexity? Given a boolean function $f$ on $n$ bits, how hard is it to determine its decision tree complexity?
(I assume the decision tree is simple, i.e., the allowed questions are the bits of the input.)

If $f$ is given by an oracle, then this is surely exponential in $n$, still I wonder if it ever has been studied, if there are algorithms that run in $2^{O(n)}$.
I am even more interested in results about when $f$ is given in another way, by a polynomial over some field, or by a Turing-machine computing it.
Is there anything known about this?
Are there any hardness results?

If you have an oracle for $f$, you can compute the optimal decision tree for $f$ in $O(3^nn)$ time and $O(3^n)$ space. Consider a function $g$ that takes as input a partition of the variables into three sets $T$, $F$, $S$ and outputs the size of the smallest decision tree for $f$ when the variables in $T$ are restricted to $1$ and the ones in $F$ are restricted to $0$ (and the remaining ones, in $S$, are unset). The following recurrence holds for $g$:
$$g(T,F,S) = 1 + \min_{v \in S} g(T \cup {v},F,S\setminus \{v\}) + g(T,F \cup {v},S\setminus \{v\}).$$
The base case is that the function $f$ is constant with the given restriction, in which case $g$ is $0$. This recurrence directly leads to a dynamic programming algorithm. If, instead you are looking to compute the minimum depth of a decision tree then the following recurrence does the trick.
$$g(T,F,S) = 1 + \min_{v \in S} \max\big{[}g(T \cup \{v\},F,S\setminus \{v\}), g(T,F \cup \{v\},S\setminus \{v\})\big{]}.$$

On the lower bound side, if $f$ is given in $k$-CNF then deciding whether the decision tree complexity is non-zero amounts to checking satisfiability which is hard to do in time $2^{o(n)}$ assuming Exponential Time Hypothesis (ETH) and in $1.999^n$ time assuming the Strong ETH.


Non-CFL closure properties I was asked the following by a student, and couldn't come up with a complete answer:

Are there any closure properties for the class of languages that are not context free?

It's fairly easy to find examples that show that it is not closed under intersection and iteration (Kleene star operator), but how about union and concatenation? My guess is that it's not closed under either, so unless I'm way off, what I'm looking for are examples for two non-CFLs that their union or concatenation is a CFL.

There are probably few or no "interesting" and "natural" closure properties for the class of languages that are not context-free. In fact that's probably true of:

any class of languages that is defined by a specific automaton, grammar or computational model -- the regular languages, the cfl's, various subclasses of the cfls such as the linear languages and the deterministic cfl's, the context-sensitive languages, bounded languages, and so on.
classes actually defined by closure properties, like the least family containing, say, {$a^n b^n$} and closed under the regular operations and transduction. In fact, AFL theory was all about things like that.

The reason is that many if not most or all "interesting" closure properties have the ability to drastically simplify a language, for example map it down to finite sets or something equally simple. For example, you can always apply a constant homomorphism (h(a) = 0) to a non-context-free language and get the language of all strings of zeros, which is context-free (in fact regular). So if the very definition of the class entails that it is not very "simple" (like non-context-free), then closure takes you down to "simple" languages, that is, outside the class.

This might actually make an interesting research project, part of which, I would hazard a guess, would be to define "simple", "interesting" and "natural" in some suitable way, and also to find formal ways to deal with trivial and degenerate cases like the one I gave.

The union and concatenation operations would be one test of such a theory.  I'll conjecture that there are two non-cfl's which concatenate to $ \Sigma^*$ and others which union to that. I'd start with non-cfl's over a single letter, so you are really talking number theory and linear algebra.

Adendum -- here are two languages that definitely concatenate to $a^*$ and are almost certainly not context-free:

$\{a^{n-i}:i = \lfloor \sqrt n \rfloor\}$

$\{a^{n+i}:i = \lfloor \sqrt n \rfloor\}$

If for some reason, those turn out CF, use an even stranger function than $ \sqrt x $


How does the Multiplicative Weights Update method maximize entropy? "The Multiplicative Weights Update (MWU) method is known to maximize both utility and entropy". This is a comment by C. Papadimitriou on MWU. I understand that MWU maximizes utility as it solves linear programming, for example.

The question is how MWU maximizes entropy? Can you give some example/information on this point?

Here's one way to look at it, based on usul's comment.

Let the gains of each expert $i$ at time $t$ be given by $g_i^t$.

Then the expected gains of the algorithm are:

$$\sum_{u=1}^{t-1}\sum_i p_i^t g_i^u$$

We can then define the potential function

$$\Phi=\epsilon \sum_{u=1}^{t-1}\sum_i p_i^t g_i^u + \sum_i p_i^t \ln \left(\frac{1}{p_i^t}\right)$$

Where the right-hand term is the entropy and $\epsilon$ is a learning rate.

This function is maximized for

$$p_i^t = \exp\left(\epsilon \sum_{u=1}^{t-1} g_i^u-1\right)$$

We can find a similar expression that maximizes the function for $t+1$.

Taking the logarithms of these expressions and subtracting gives:

$$p_i^{t+1}=p_i^t \exp (\epsilon g_i^t)$$

Which is the MWU update rule.

Therefore, by applying this update rule we are maximizing a potential function of utility and entropy.


Is the Set of all Primitive Words a Prime Language? A word $w$ is called primitive, if there is no word $v$ and $k > 1$ so that $w = v^k$.
The set $Q$ of all primitive words over an alphabet $\Sigma$ is a well known language. WLOG we can choose $\Sigma = \{ a,b \}$.

A language $L$ is prime, if for every language $A$ and $B$ with $L = A \cdot B$ we have $A = \{\epsilon\}$ or $B = \{ \epsilon \}$.

Is Q prime?

With the help of a SAT solver I could show that we either have $\{a,b\} \subseteq A$ or $\{a,b\} \subseteq B$ as otherwise $\{ ababa, babab \} \subset Q$ cannot be factorized into $A$ and $B$, but have been stuck since then.

The answer is yes. Suppose we have a factorization $Q = A\cdot B$.

One easy observation is that $A$ and $B$ must be disjoint (since for $w\in A\cap B$ we get $w^2\in Q$). In particular, only one of $A,B$ can contain $\epsilon$. We can assume wlog (since the other case is completely symmetric) that $\epsilon\in B$. Then since $a$ and $b$ cannot be factored into non-empty factors, we must have $a,b\in A$.

Next we get that $a^mb^n\in A$ (and, completely analogously, $b^ma^n\in A$) for all $m,n>0$ by induction on $m$:

For $m=1$, since $ab^n\in Q$, we must have $ab^n = uv$ with $u\in A, v\in B$. Since $u\neq\epsilon$, $v$ must be $b^k$ for some $k\le n$. But if $k>0$, then since $b\in A$ we get $b^{1+k}\in Q$, contradiction. So $v=\epsilon$, and $ab^n\in A$.

For the inductive step, since $a^{m+1}b^n\in Q$ we have $a^{m+1}b^n = uv$ with $u\in A, v\in B$. Since again $u\neq\epsilon$, we have either $v = a^kb^n$ for some $0<k<m+1$, or $v=b^k$ for some $k<n$. But in the former case, $v$ is already in $A$ by the induction hypothesis, so $v^2\in Q$, contradiction. In the latter case, we must have $k=0$ (i.e. $v=\epsilon$) since from $b\in A$ we get $b^{1+k}\in Q$. So $u=a^{m+1}b^n\in A$.

Now consider the general case of primitive words with $r$ alternations between $a$ and $b$, i.e. $w$ is either $a^{m_1}b^{n_1}\ldots a^{m_s}b^{n_s}$, $b^{m_1}a^{n_1}\ldots b^{m_s}a^{n_s}$ (for $r=2s-1$), $a^{m_1}b^{n_1}\ldots a^{m_{s+1}}$, or $b^{m_1}a^{n_1}\ldots b^{m_{s+1}}$ (for $r=2s$); we can show that they are all in $A$ using induction on $r$. What we did so far covered the base cases $r=0$ and $r=1$.

For $r>1$, we use another induction on $m_1$, which works very much the same way as the one for $r=1$ above:

If $m_1=1$, then $w=uv$ with $u\in A, v\in B$, and since $u\neq\epsilon$, $v$ has fewer than $r$ alternations. So $v$ (or its root in case $v$ itself is not primitive) is in $A$ by the induction hypothesis on $r$ for a contradiction as above unless $v=\epsilon$. So $w=u\in A$.

If $m_1>1$, in any factorization $w=uv$ with $u\neq\epsilon$, $v$ either has fewer alternations (and its root is in $A$ unless $v=\epsilon$ by the induction hypothesis on $r$), or a shorter first block (and its root is in A unless $v=\epsilon$ by the induction hypothesis on $m_1$). In either case we get that we must have $v=\epsilon$, i.e. $w=u\in A$.

The case of $Q' := Q\cup\{\epsilon\}$ is rather more complicated. The obvious things to note are that in any decomposition $Q = A\cdot B$, both $A$ and $B$ must be subsets of $Q'$ with $A\cap B = \{\epsilon\}$. Also, $a,b$ must be contained in $A\cup B$.

With a bit of extra work, one can show that $a$ and $b$ must be in the same subset. Otherwise, assume wlog that $a\in A$ and $b\in B$. Let us say that $w\in Q'$ has a proper factorization if $w=uv$ with $u\in A\setminus\{\epsilon\}$ and $v\in B\setminus\{\epsilon\}$. We have two (symmetric) subcases depending on where $ba$ goes (it must be in $A$ or $B$ since it has no proper factorization).

If $ba\in A$, then $aba$ has no proper factorization since $ba,a\notin B$. Since $aba\in A$ would imply $abab\in A\cdot B$, we get $aba\in B$. As a consequence, $bab$ is neither in $A$ (which would imply $bababa\in A\cdot B$) nor in $B$ (which would imply $abab\in A\cdot B$). Now consider the word $babab$. It has no proper factorization since $bab\notin A\cup B$ and $abab,baba$ are not primitive. If $babab\in A$, then since $aba\in B$ we get $(ba)^4\in A\cdot B$; if $babab\in B$, then since $a\in A$ we get $(ab)^3\in A\cdot B$. So there is no way to have $babab\in A\cdot B$, contradiction.
The case $ba\in B$ is completely symmetric. In a nutshell: $bab$ has no proper factorization and cannot be in $B$, so it must be in $A$; therefore $aba$ cannot be in $A$ or $B$; therefore $ababa$ has no proper factorization but also cannot be in either $A$ or $B$, contradiction.

I am currently not sure how to proceed beyond this point; it would be interesting to see if the above argument can be systematically generalized.