What's new in purely functional data structures since Okasaki?

New purely functional data structures published since 1998:

2001: Ideal Hash Trees, and its 2000 predecessor, Fast And Space Efficient Trie Searches, by Phil Bagwell: Apparently used as a fundamental building block in Clojure's standard library.
2001: A Simple Implementation Technique for Priority Search Queues, by Ralf Hinze: a really simple and beautiful technique for implementing this important datastructure (useful, say, in the Dijkstra algorithm). The implementation is particularly beautiful and readable due to heavy use of "view patterns".
2002: Bootstrapping one-sided flexible arrays, by Ralf Hinze: Similar to Okasaki's random-access lists, but they can be tuned to alter the time tradeoff between cons and indexing.
2003: New catenable and non-catenable deques, by Radu Mihaescu and Robert Tarjan: A new take on some older work (by Kaplan and Tarjan) that Okasaki cites (The most recent version of Kaplan & Tarjan's work was published in 2000). This version is simpler in some ways.
2005: Maxiphobic heaps (paper and code), by Chris Okasaki: Presented not as a new, more efficient structure, but as a way to teach priority queues.
2006: Purely Functional Worst Case Constant Time Catenable Sorted Lists, by Gerth Stølting Brodal, Christos Makris, and Kostas Tsichlas: Answers an outstanding question of Kaplan and Tarjan by demonstrating a structure with O(lg n) insert, search, and delete and O(1) concat.
2008: Confluently Persistent Tries for Efficient Version Control, by Erik D. Demaine, Stefan Langerman, and Eric Price: Presents several data structures for tries that have efficient navigation and modification near the leaves. Some are purely functional. Others actually improve a long-standing data structure by Dietz et al. for fully persistent (but not confluently persistent or purely functional) arrays. This paper also presente purely functional link-cut trees, sometimes called "dynamic trees".
2010: A new purely functional delete algorithm for red-black trees, by Matt Might: Like Okasaki's red-black tree insertion algorithm, this is not a new data structure or a new operation on a data structure, but a new, simpler way to write a known operation.
2012: RRB-Trees: Efficient Immutable Vectors, by Phil Bagwell and Tiark Rompf: An extension to Hash Array Mapped Tries, supporting immutable vector concatenation, insert-at, and split in O(lg n) time, while maintaining the index, update, and insertion speeds of the original immutable vector.

Known in 1997, but not discussed in Okasaki's book:

Many other styles of balanced search tree. AVL, brother, rank-balanced, bounded-balance, and many other balanced search trees can be (and have been) implemented purely functionally by path copying. Perhaps deserving special mention are:

Biased Search Trees, by Samuel W. Bent, Daniel D. Sleator, and Robert E. Tarjan: A key element in Brodal et al.'s 2006 paper and Demaine et al.'s 2008 paper.

Infinite sets that admit fast exhaustive search, by Martín Escardó: Perhaps not a data structure per se.
Three algorithms on Braun Trees, by Chris Okasaki: Braun trees offer many stack operations in worst-case O(lg n). This bound is surpassed by many other data structures, but Braun trees have a cons operation lazy in its second argument, and so can be used as infinite stacks in some ways that other structures cannot.
The relaxed min-max heap: A mergeable double-ended priority queue and The KD heap: An efficient multi-dimensional priority queue, by Yuzheng Ding and Mark Allen Weiss: These happen to be purely functional, though this is not discussed in the papers. I do not think the time bounds achieved are any better than those that can be achieved by using finger trees (of Hinze & Paterson or Kaplan & Tarjan) as k-dimensional priority queues, but I think the structures of Ding & Weiss uses less space.
The Zipper, by Gérard Huet: Used in many other data structures (such as Hinze & Paterson's finger trees), this is a way of turning a data structure inside-out.
Difference lists are O(1) catenable lists with an O(n) transformation to usual cons lists. They have apparently been known since antiquity in the Prolog community, where they have an O(1) transformation to usual cons lists. The O(1) transformation seems to be impossible in traditional functional programming, but Minamide's hole abstraction, from POPL '98, discusses a way of allowing O(1) append and O(1) transformation within pure functional programming. Unlike the usual functional programming implementations of difference lists, which are based on function closures, hole abstractions are essentially the same (in both their use and their implementation) as Prolog difference lists. However, it seems that for years the only person that noticed this was one of Minamide's reviewers.
Uniquely represented dictionaries support insert, update, and lookup with the restriction that no two structures holding the same elements can have distinct shapes. To give an example, sorted singly-linked lists are uniquely represented, but traditional AVL trees are not. Tries are also uniquely represented. Tarjan and Sundar, in "Unique binary search tree representations and equality-testing of sets and sequences", showed a purely functional uniquely represented dictionary that supports searches in logarithmic time and updates in $O(\sqrt{n})$ time. However, it uses $\Theta(n \lg n)$ space. There is a simple representation using Braun trees that uses only linear space but has update time of $\Theta(\sqrt{n \lg n})$ and search time of $\Theta(\lg^2 n)$

Mostly functional data structures, before, during, and after Okasaki's book:

Many procedures for making data structures persistent, fully persistent, or confluently persistent: Haim Kaplan wrote an excellent survey on the topic. See also above the work of Demaine et al., who demonstrate a fully persistent array in $O(m)$ space (where $m$ is the number of operations ever performed on the array) and $O(\lg \lg n)$ expected access time.
1989: Randomized Search Trees by Cecilia R. Aragon and Raimund Seidel: These were discussed in a purely functional setting by Guy E. Blelloch and Margaret Reid-Miller in Fast Set Operations Using Treaps
and by Dan Blandford and Guy Blelloch in Functional Set Operations with Treaps (code). They provide all of the operations of purely functional fingertrees and biased search trees, but require a source of randomness, making them not purely functional. This may also invalidate the time complexity of the operations on treaps, assuming an adversary who can time operations and repeat the long ones. (This is the same reason why imperative amortization arguments aren't valid in a persistent setting, but it requires an adversary with a stopwatch)
1997: Skip-trees, an alternative data structure to Skip-lists in a concurrent approach, by Xavier Messeguer and Exploring the Duality Between Skip Lists and Binary Search Trees, by Brian C. Dean and Zachary H. Jones: Skip lists are not purely functional, but they can be implemented functionally as trees. Like treaps, they require a source of random bits. (It is possible to make skip lists deterministic, but, after translating them to a tree, I think they are just another way of looking at 2-3 trees.)
1998: All of the amortized structures in Okasaki's book! Okasaki invented this new method for mixing amortization and functional data structures, which were previously thought to be incompatible. It depends upon memoization, which, as Kaplan and Tarjan have sometimes mentioned, is actually a side effect. In some cases (such as PFDS on SSDs for performance reasons), this may be inappropriate.
1998: Simple Confluently Persistent Catenable Lists, by Haim Kaplan, Chris Okasaki, and Robert E. Tarjan: Uses modification under the hood to give amortized O(1) catenable deques, presenting the same interface as an earlier (purely functional, but with memoization) version appearing in Okasaki's book. Kaplan and Tarjan had earlier created a purely functional O(1) worst-case structure, but it is substantially more complicated.
2007: As mentioned in another answer on this page, semi-persistent data structures and persistent union-find by Sylvain Conchon and Jean-Christophe Filliâtre

Techniques for verifying functional data structures, before, during, and after Okasaki's book:

Phantom types are an old method for creating an API that does not allow certain ill-formed operations. A sophisticated use of them can be found in Oleg Kiselyov and Chung-chieh Shan's Lightweight Static Capabilities.
Nested types are not actually more recent than 1998 - Okasaki even uses them in his book. There are many other examples that are not in Okasaki's book; some are new, and some are old. They include:

Stefan Kahrs's Red-black trees with types (code)
Ross Paterson's AVL trees (mirror)
Chris Okasaki's From fast exponentiation to square matrices: an adventure in types
Richard S. Bird and Ross Peterson's de Bruijn notation as a nested datatype
Ralf Hinze's Numerical Representations as Higher-Order Nested Datatypes.

GADTs are not all that new, either. They are a recent addition to Haskell and some MLs, but they have been present, I think, in various typed lambda calculi since the 1970s.
2004-2010: Coq and Isabelle for correctness. Several people have used theorem provers to verify the correctness of purely functional data structures. Coq can extract these verifications to working code in Haskell, OCaml, and Scheme; Isabelle can extract to Haskell, ML, and OCaml.

Coq:

Pierre Letouzey and Jean-Christophe Filliâtre formalized red-black and AVL(ish) trees, finding a bug in the OCaml standard library in the process.
I formalized Brodal and Okasaki's asymptotically optimal priority queues.
Arthur Charguéraud formalized 825 of the 1,700 lines of ML in Okasaki's book.

Isabelle:

Tobias Nipkow and Cornelia Pusch formalized AVL trees.
Viktor Kuncak formalized unbalanced binary search trees.
Peter Lammich published The Isabelle Collections framework, which includes formalizations of efficient purely functional data structures like red-black trees and tries, as well as data structures that are less efficient when used persistently, such as two-stack-queues (without Okasaki's laziness trick) and hash tables.
Peter Lammich also published formalizations of tree automata, Hinze & Patterson's finger trees (with Benedikt Nordhoff and Stefan Körner), and Brodal and Okasaki's purely functional priority queues (with Rene Meis and Finn Nielsen).
René Neumann formalized binomial priority queues.

2007: Refined Typechecking with Stardust, by Joshua Dunfield: This paper uses refinement types for ML to find errors in SMLNJ's red-black tree delete function.
2008: Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures by Nils Anders Danielsson: Uses Agda with manual annotation to prove time bounds for some PFDS.

Imperative data structures or analyses not discussed in Okasaki's book, but related to purely functional data structures:

The Soft Heap: An Approximate Priority Queue with Optimal Error Rate, by Bernard Chazelle: This data structure does not use arrays, and so has tempted first the #haskell IRC channel and later Stack Overflow users, but it includes delete in o(lg n), which is usually not possible in a functional setting, and imperative amortized analysis, which is not valid in a purely functional setting.
Balanced binary search trees with O(1) finger updates. In Making Data Structures Persistent, James R Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan present a method for grouping the nodes in a red-black tree so that persistent updates require only O(1) space. The purely functional deques and finger trees designed by Tarjan, Kaplan, and Mihaescu all use a very similar grouping technique to allow O(1) updates at both ends. AVL-trees for localized search by Athanasios K. Tsakalidis works similarly.
Faster pairing heaps or better bounds for pairing heaps: Since Okasaki's book was published, several new analyses of imperative pairing heaps have appeared, including Pairing heaps with O(log log n) decrease Cost by Amr Elmasry and Towards a Final Analysis of Pairing Heaps by Seth Pettie. It may be possible to apply some of this work to Okasaki's lazy pairing heaps.
Deterministic biased finger trees: In Biased Skip Lists, by Amitabha Bagchi, Adam L. Buchsbaum, and Michael T. Goodrich, a design is presented for deterministic biased skip lists. Through the skip list/tree transformation mentioned above, it may be possible to make deterministic biased search trees. The finger biased skip lists described by John Iacono and Özgür Özkan in Mergeable Dictionaries might then be possible on biased skip trees. A biased finger tree is suggested by Demaine et al. in their paper on purely functional tries (see above) as a way to reduce the time-and space bounds on finger update in tries.
The String B-Tree: A New Data Structure for String Search in External Memory and its Applications by Paolo Ferragina and Roberto Grossi is a well studied data structure combining the benefits of tries and B-trees.


Are lambda calculus and combinatory logic the same?

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

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


Samson Abramsky and I wrote a paper about the proof theory of compact categories with biproducts.

  Abramsky, S. and Duncan, R. (2006) "A Categorical Quantum Logic",
  Mathematical Structures in Computer Science 16 (3).
  10.1017/S0960129506005275

The ideas were later developed a bit further in this book chapter:

  Duncan, Ross (2010) "Generalised Proof-Nets for Compact Categories
  with Biproducts" in Semantic Techniques in Quantum Computation,
  Cambridge University Press, pp70--134 arXiv:0903.5154v1

The full details are there, but the short version is that your logic is inconsistent, because you have a zero proof for every implication, and the rest of your proofs are equivalent to "matrices", where the matrix entries are the proofs in the biproduct-free part of the logic.  Speaking without the caveats required to make this precise, the resulting category of proofs is the free biproduct category on some category of axioms.


What technique is used to implement type checking for CoC?

May I have a reference to why η expansion is invalid for CoC?

It's not invalid. It's up to choice whether $\eta$-conversion for functions (or other types) is included. The original CoC paper seems to omit it, but as you see ATAPL includes it. I'm not certain, but $\eta$ may have been omitted from the original source because it was difficult to handle in the strong normalization arguments, back in the days. Nowadays normalization proofs are more likely to be based on NbE themselves, and have no issues with $\eta$-rules. Modern Coq definitely has $\eta$ for functions, and it is generally considered a highly useful basic feature.

The rules QA-NABS-1, QA-NABS-2 seem to be implementing η expansion for stuck terms? Why do these rules not describe NBE?

They do specify $\eta$ for functions. It's not really NbE though. ATAPL only describes how to compare weak head normal forms for conversion in an iterated fashion, it does not say how to efficiently compute to whnf. The essential part of NbE is the separation of syntax and values; this is missing from the ATAPL exposition.

Indeed, normalization by evaluation has a number of characteristics that make it only suitable for certain theories: it η-expands expressions as many times as possible

This is incorrect. NbE is not necessarily type-directed, and does not necessarily include $\eta$-expansion. If you look at QA-NABS-1, QA-NABS-2 and the other rules in ATAPL, they can be adapted to a conversion checking algorithm on NbE values, which is a) purely syntax-directed b) does not require $\eta$-expansion in evaluation c) decides $\eta$-conversion for functions.

Is there a name for the rules given in ATAPL to implement type checking for CoC? They seem ad-hoc to me, and I don't understand how I would come up with them.

I'm not aware of any rigorous and generic way for specifying conversion checking algorithms. I would summarize the rules of thumbs as follows.
The specification of values is obtained from the specification of syntax by replacing binders with metalanguage functions or closures. Evaluation goes from syntax to values and performs $\beta$-reduction (but not necessarily $\eta$-conversions). Then, conversion checking can be implemented on values, proceeding purely structurally, except where we want syntax-directed $\eta$-checking in the manner specified in ATAPL.


Is bounded-width SAT decidable in logspace?

Indeed, using the resultss in Elberfeld-Jakoby-Tantau-2010 one can
show that SAT can be decided in logspace on formulas whose incidence graph has bounded treewidth. Here is a sketch of how the main steps of the proof of this claim go.

The notions of tree-decomposition and treewidth can be generalized to arbitrary relational structures. See for instance sections 2 and 3 of
this paper by Dalmau, Kolaitis and Vardi.
Courcelle's theorem states that MSO logic can be decided in linear time on relational structures of constant treewidth.
A theorem of Bodlaender implies that if a relational structure has treewidth $t$, then a tree-decomposition of such structure can be found in time $f(t)\cdot n$. In other words, such a decomposition can be found in linear time on graphs of constant treewidth.
One can define suitable relational structure $\tau$ which can be used to encode a formula $F$ together with its incidence graph $I$. The treewidth of $\tau$ is at most a constant plus the treewidth of $I$.
The set of relational structures $\tau$ which encode satisfiable formulas + their incidence graphs is MSO definable.
Therefore, by Bodlander+Courcelle's theorem, one can decide whether a formula of constant treewidth is satisfiable in linear time.
Elberfeld-Jakoby-Tantau-2010 show that "linear time" can be replaced by "logarithmic space" on both Bodlaender and Courcelle's theorem.
Therefore, for each MSO formula $\varphi$, and each relational structure $\tau$, one can determine in logarithmic space whether $\tau$ satisfied $\varphi$.
In particular, SAT can be determined in logspace on graphs of constant treewidth.


You are right: formally P includes only decision problems. But many decision problems have corresponding optimization problems: find the size of the largest matching in a graph, find the length of the shortest path from s to t in a graph, etc.

Often, these can be reduced to decision problems by instead asking: "Does the graph have a matching using more than k edges?" or "Is there an s->t path of length less than k?"

Obviously, if you can solve the optimization problem, you can solve the decision problem. The converse is also often true, up to logarithmic factors. If you want to know the size of the largest matching in a graph, for example, you can make repeated calls to your algorithm for the decision problem "Does the graph have a matching using more than k edges?" and do binary search on the value "k". In this way, you will require at most log(m) calls, where m is the number of edges. For most problems there is an analogous reduction.


About estimating escape time of gradient Langevin dynamics

Observe that the following event contains your event $E$: either (1) for some $i$, $\|\xi_{i,2}\| > C_{\zeta}$ (in which case $x_{i+1}$ and $x_{i+1}'$ are no longer the same), or (2) for some $i$, $x_i'$ leaves the ball. It might be easier to see containment (in the opposite direction) of the complement events: if for all $i$ both $\|\xi_{i,2}\| \le C_{\xi}$ and also $x_i'$ is inside the ball, this surely means that $x_i=x_i'$ for all $i$ and hence also $x_i$ is always inside the ball.

The union bound should now be clear.


Comparison of Hashing and Modular Exponentiation

Hashing is much cheaper than modular exponentiation, so much so that it is often taken as "free" in efficiency analysis that uses modular arithmetic. My suggestion would be to do a rough comparison, like you said: protocol 1 uses m hashes, protocol 2 uses n exponentiations.

If n>m, protocol 1 is much faster.
If m>a*n, I wouldn't start investigating further until a gets to be around 10^2 or 10^3. It seems unlikely that protocol 1 would use this many, unless if it is using a hash tree or similar data structure requiring lots of hashes.

There is no quick rule because the speed of an exponentiation at this level of scrutiny is dependent on the underlying group. Elliptic curves will be much faster than the integers mod p, and elliptic curve speed will depend on the type of curve.

Similarly, the speed of the hash function depends on how long the input message is. Does it fit into a single block, or does the hash need to iterate over it?

As one ballpark figure, a 100MHz FPGA can do about 100 ModExps (1024 bit with 160 bit subgroup) in one second, while it can hash about 5000 message blocks (SHA256) in a second.


I recommend the following books:

Khalid Sayood "Introduction to DATA COMPRESSION"
Khalid Sayood "Lossless Compression Handbook"
David Salomon "Handbook of Data compression"

And a little more specific, but also good books in this field:

Timothy Bell "Text compression"
Donald Adjeroh, Timothy Bell, Amar Mukherjee "The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern
Matching"


On partitioning a collection into equivalence classes

See the paper

Varunkumar Jayapaul, J. Ian Munro, Venkatesh Raman, Srinivasa Rao Satti (2015), "Sorting and Selection with Equality Comparisons",
Proc. WADS 2015, LNCS 9214, pp. 434–445, doi:10.1007/978-3-319-21840-3_36

It is exactly about the problem you ask, finding the equivalence classes of an equivalence relation by querying the equivalences of pairs of elements. For an input with $n$ elements and $c$ equivalence classes, the naive algorithm you describe will take time $O(nc)$, but they give a more precise bound for this same algorithm in terms of the sizes of its equivalence classes (Theorem 3) and similarly analyze another algorithm for the same problem that works better when the equivalence classes have unevenly distributed sizes (Theorem 4).


Complexity of the edge-disjoint cycle covers

The problem is polynomial-time solvable.

Say that a vertex is balanced if its in-degree equals its out-degree.

Note that a directed graph is Eulerian iff every vertex is balanced and its underlying undirected graph is connected. Now, a directed graph is a vertex-disjoint union of Eulerian graphs iff every vertex is balanced. So, the problem amounts to deleting a smallest number of arcs so that each vertex becomes balanced. In Theorem 2 of the following paper, this problem is solved in polynomial time using network flows.

Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter:
Parameterized Complexity of Eulerian Deletion Problems. Algorithmica 68(1): 41-61 (2014).


Best known algorithm for a common problem.

This is the set cover problem.

The universe $\mathcal{U}$ corresponds to the rows of the matrix $M$, and each member of $\mathcal{S}$ corresponds to each column. The entry $m_{i,j}$ is true if and only if the $i$-th element of $\mathcal{U}$ belongs to the $j$-th member of $\mathcal{S}$.


Here's a partial list of collections of open problems in TCS, broadly construed. Note that a collection of "major open problems" exists already on this site: http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science/251#251.

In Computer Science (Wikipedia): https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science
Sublinear time algorithms: http://sublinear.info/index.php?title=Main_Page
Analysis of Boolean Functions: http://lanl.arxiv.org/abs/1204.6447
Computational geometry: http://cs.smith.edu/~orourke/TOPP/
Exact algorithms: http://faculty.cs.tamu.edu/chen/courses/cpsc669/2011/notes/ww1.pdf
Formal languages, etc.: https://www.student.cs.uwaterloo.ca/~cs462/openproblems.html
Parameterized complexity: http://fpt.wikidot.com/open-problems
Topological graph theory: http://www.cems.uvm.edu/~darchdea/problems/problems.html
Embeddings of finite metric spaces: http://kam.mff.cuni.cz/~matousek/metrop.ps
Lambda calculus, proof theory, semantics, and programming languages: http://tlca.di.unito.it/opltlca/
Perfect graphs: http://www.aimath.org/WWN/perfectgraph/
Real analysis in computer science: https://simons.berkeley.edu/sites/default/files/openprobsmerged.pdf
Fine-grained complexity: http://duch.mimuw.edu.pl/~malcin/opl.pdf
Communication complexity: https://sublinear.info/index.php?title=Workshops:Banff_2017
Erdős problems: http://www.math.ucsd.edu/~erdosproblems/All.html


Is there an algorithm for minimizing an NFA with respect to bisimilarity rather than language equivalence?

Yes, see for example here:

Johanna Högberg, Andreas Maletti, Jonathan May,
Backward and forward bisimulation minimization of tree automata,
Theoretical Computer Science 410(37), 2009, pp. 3539-3552,
https://doi.org/10.1016/j.tcs.2009.03.022


An interesting variant of maximum matching problem

(As it seems that the connection is not completely obvious, I will write an extended version of the above comments as an answer.)

I will focus on the case of $c = 2$. In that case, the problem can be rephrased as follows:

Let $G = (V,E)$ be a graph. The task is to find a maximum-size $M \subseteq E$ such that the following constraint is satisfied: for each $\{u,v\} \in M$, either $u$ is incident to at most $1$ edge in $M$, or $v$ is incident to at most $1$ edge in $M$, or both.

Equivalently:

The subgraph induced by $M$ has to have the property that all neighbours of a non-leaf node (degree > 1) are leaf nodes (degree = 1).

Equivalently:

The subgraph induced by $M$ consists of node-disjoint stars.

In what follows I will interpret unmatched nodes (nodes not incident to any edge in $M$) as stars with 0 edges. Hence a feasible solution partitions the set of nodes into node-disjoint stars.

Now if the number of such stars is $k$, then the number of edges in $M$ is exactly $n-k$: there are $n-k$ leaf nodes that are connected to a star center. Therefore maximising the number of edges in $M$ is equivalent to minimising then number of stars.

Now it is straightforward to see that we have a solution with $k$ such stars iff we have a dominating set of size $k$:

Assume that we are given $k$ such stars. Then we can find a dominating set of size $k$: simply take the centers of the stars (in a star with 1 edge you can pick a node arbitrarily).
Assume that we are given a dominating set $D$ with $|D| = k$. Then we can simply connect each node in $V \setminus D$ to one node in $D$. These edges form a family of $k$ stars.

Therefore solving the problem optimally in a certain graph family $F$ is exactly as hard as finding a minimum dominating set in the same graph family $F$. In particular, the problem is NP-hard even in the case of bipartite graphs.

(However, (in)approximability results related to dominating sets cannot be directly applied here. In essence, we have changed the objective function from $\min |D|$ to $\max n-|D|$.)


Sorting a programs instructions until it works

This can be done by running all the $n!$ permutations in parallel and wait for one of them to output $1,2,6,24$ on inputs $1,2,3,4$.

(Of course, that does not guarantee that you found the correct permutation for input 5.)

Specific running time estimates may depend on the programming language being used. For instance, in BASIC each line is supposed to start with a line number which makes this solvable in polynomial time.


Time complexity of derivative-based regex matchers

In Theorem 5.2 of his paper, Brzozowski shows that every regular expression has a finite number of dissimilar derivatives, where two regular expressions $r$ and $r'$ are similar if they are ACU-equivalent at the outermost level. That is, consider the equivalence relation generated by the following equivalences:

$$
\array{
r \vee r & \equiv &  r \\
r \vee r' & \equiv & r' \vee r \\
(r \vee r') \vee r'' & \equiv & r \vee (r' \vee r'') \\
r \vee \bot & \equiv & r \\}
$$

(Notice the absence of congruence rules in this definition -- in particular, $a\cdot(r \vee r') \not\equiv a\cdot(r' \vee r)$.) It turns out there are at most $O(2^{|r|})$ many dissimilar word Brzozowski derivatives. So the worst case of matching with Brzozowski derivatives is the same as any other method.

A nice proof of this fact takes a detour through Antimirov partial derivatives. The one-character Antimirov derivative function is defined as follows:

$$
\array{
a_c(\bot) & = & \emptyset \\
a_c(r \vee r') & = & a_c(r) \cup a_c(r') \\
a_c(\epsilon) & = & \emptyset \\
a_c(c')        & = & \emptyset \\
a_c(c)         & = & \{ \epsilon \}  \\
a_c(r_1 \cdot r_2) & = & \{ r'_1 \cdot r_2 \;|\; r'_1 \in a_c(r_1) \} \\
                   &   & \cup \; (\mbox{if}\;\mbox{nullable}(r_1)\;\mbox{then}\; a_c(r_2) \;\mbox{else}\;\emptyset) \\
a_c(r\ast) & = & \{ r' \cdot r\ast \;|\; r' \in a_c(r) \}
}
$$

Basically, instead of returning a single derivative, the Antimirov derivative returns a set of partial derivatives, whose union adds up to the Brzozowski derivative. Now, we can make the following observations:

Up to similarity, the union of the set of Antimirov partial derivatives of a regular expression and the Brzozowski derivative are one and the same.
It's also easy to prove that given a regular expression $r$, the number of Antimirov word derivatives is linear in the size of $r$.
Since a Brzozowski derivative is formed from a union of Antimirov derivatives, there can be at most $O(2^{|r|})$ possible Brzozowski derivatives of a regular expression (up to similarity).

As defined, the Antimirov derivative doesn't work with intersection.     Pascal Caron, Jean-Marc Champarnaud and Ludovic Mignot had a LATA 2011 paper, Partial Derivatives of an Extended Regular Expression, which extended this approach to cover extended regular expressions. Their idea is to define a new partial derivative operation returning a set of sets of partial derivatives (corresponding to DNF), and they show that this has a worst-case exponential size. Intuitively, this corresponds to the fact that implementing intersection on automata uses a product construction.

Anyway, the takeaway (IMO) should be that derivatives are not alternatives to the standard automata-theoretic constructions, but rather are a conceptual explanation of them.


First, note that nothing turns on the presence or absence of the empty type: if you have a nonlinear calculus with function types and unrestricted recursive types, then it is inconsistent. Indeed, your derivation works regardless of the type of the answer -- the very same term you have works for $\mu a.\; a \to X$ for any $X$.
This is known as Curry's Paradox, and is also known as the Y combinator. There is a nice discussion of this in Greg Restall's paper Curry's Revenge: the costs of non-classical solutions to the paradoxes of self-reference.

Next, your observation that the fixed point combinators rely upon contraction is astute. Curry's paradox depends on all three of contraction, unrestricted recursive types, and a function space, and removing any one of them suffices to block it.
For example, I asked a very similar question here a few years back, and learned that multiplicative-additive linear logic with recursive types is not Turing-complete. This is called the "Small Normalization Theorem" (Theorem 4.22) in Girard's original paper on linear logic.

You can still construct models of this language (with or without units) using domain theory. The main technical difficulty is the interpretation of recursive types. I don't know a good introduction to how to solve recursive domain equations. I learned it from Plotkin and Smyth's The Category-Theoretic Solution of Recursive Domain Equations, but that was really not a good tutorial for me: I needed a fair amount of help to understand it. The critical intuitions are all there, but it's quite dense. Maybe Abramsky and Jung's handbook chapter might be more accessible? I don't really have any great suggestions.


reference for a special modular decomposition

Indeed this concept exists. Two vertices $u,v$ that have the same neighbors are often called twins. They are called true twins if they are also connected, and false twins otherwise. In your definition, all vertices of $X$ are true twins.

It looks like there are several other names in the literature for these concepts. See e.g. this MO question. In FPT algorithms we sometimes call the number of twin classes into which a graph can be partitioned the neighborhood diversity of the graph, see e.g. here (warning: self-citation!), and here for the related notion of twin-cover.


http://www.cseblog.com/
CMU - The Puzzle Toad
Tanya Khovanova’s Math Blog

And the links therein.


Bounds on the size of NFA for $r$-skip $k$-distinct language

I detail the comment below, as you could be interested in this answer.
I don't know about NFA, but if your goal is to represent this language with a small automaton,  you could use the model of alternating automata, or AFA.

Intuitively, DFA are with $0$ player: the run is updated automatically, NFA are with $1$ player who has to choose a good run, and AFA are played by two players: one tries to accept, the other to reject. The word is in the language if the "good" player (who wants to accept) has a winning strategy on this word. This does not increase the expressive power of automata.

Here, you have an AFA with essentially $kr (\log n)^k$ states:
At one point the opposite player can guess that some letter with same position modulo $r$ will be equal to the current one.
Then the "good" player guesses $k$ bit positions of the current letter (this requires $(\log n)^k$ memory) : one which will be different for each later equivalent position. Then we just have to check that one of these bits is indeed different every $r$ positions.


What paradigm of automated theorem proving is appropriate for Principia Mathematica-style formalization?

Several points:

As far as I know, Principia Mathematica uses essentially a formalization of set theory using a typed first order logic. It would therefore be tempting to use a first-order automated theorem prover like Prover 9 or possibly ACL2 to formalize your statements. However, I am seeing several set-theoretic constructions (like $\in$, $\cap, \subset$) in there, which usually don't play very well with first order ATP.
Any modern interactive proof assistant will surely have the expressiveness to formalize and prove your statements, as Andrej has suggested. In fact, since there seem to be some statements including arithmetic, it would be wise to use a system like Isabelle, Coq or HOL which already have extensive theories to treat statements of arithmetic. My emphasis on modern is not a coincidence: great strides in usability have been made since Automath, and I honestly think you would be doing yourself a disservice by using anything that hasn't been actively developed since the 90's (if you could even get one to work!)
Finally, ITP and ATP have rather challenging learning curves, and you shouldn't expect to be able to enter these theorems into such a system as if you were writing a $\LaTeX$ proof. Expect severe frustration and lost time, especially in the first months (yes, months). You definitely need to work through some tutorials at first before getting to the main formalization.


Name of the problem to find the maximum number of characters covered by a set of strings

This sounds like the maximum cover problem which is NP-hard.


What you are looking for is a one-bit extractor for two independent sources: a function $E:[N]\times [N]\to \{0,1\}$, such that, provided X,Y are random variables with min-entropy 0.499*log(N), E(X,Y) is almost balanced.

It's a notorious hard problem. For the parameters you want, I believe it was solved by Bourgain. See here:
http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf


My exact divide-conquer algorithm for counting antichain in a poset?

Counting antichains in an $n$ element poset is equivalent to counting independent sets in a comparability graph on $n$ vertices. The problem of counting the independent sets in an $n$ vertex graph has an $O(1.2461^n)$ time algorithm, see Fürer and Kasiviswanathan http://eccc.hpi-web.de/report/2005/033/ .


Complexity of counting matchings in a bipartite graph

The problem of counting such "imperfect" matchings in bipartite graphs is #P-complete.
This has been proved by Les Valiant himself, on page 415 of the paper

  Leslie G. Valiant
  The Complexity of Enumeration and Reliability Problems
  SIAM J. Comput., 8(3), 410–421


algorithms to split data into roughly equal sized quantiles

It is possible to find the quantiles in $O(N)$ using a straightforward modification of the selection algorithm based on quicksort (see http://en.wikipedia.org/wiki/Selection_algorithm).


Collision Attacks, Message Digests and a Possible solution

I will attempt an answer, which hopefully interpretes the question correctly and if not, will at least lead to some clarification.

Let's say the hash has an output of size $2^{N}$ and we are hashing messages only of length exactly $2^{M}$.

The last question is the best place to start: what is the probability of a collision with a randomly selected hash? A common analogy used when talking about collisions is balls and bins. The question addresses the scenario where we randomly throw (definition of the hash) $2^{M}$ balls (message space) into $2^{N}$ bins (output space).

I am not clear on the exact question: is it, what is the probability of at least one bin having more than one ball? Or is it, what is the probability that given I just threw a ball into a particular bin that another ball is thrown into the same bin?

The former is simply the birthday problem while the latter is:

$p=1-(1-\frac{1}{2^{N}})^{2^{M}-1}$

Now as the ratio $N/M$ increases, $p$ decreases. We cannot change $2^N$. Any method that lowers $2^M$ will have an effect. This includes restricting messages from any M-bit string to only M-bit strings from a language. Say there are $2^{L}$ admissible strings, $L \leq M$, then just substitute in ${L}$ for $M$ in the equation.

As for the first question of adding the length of the message as a suffix, one can still find a collision of a different length as long as the new collision ends with a suffix equivalent to it's (new) length. This makes finding collisions moderately harder but does not "solve" the collision problem by any means. It is not effective at enforcing the length remains the same, without some outside knowledge of what the length should be.

If the length is known, then this adding the length as a suffix adds redundant information and does not increase $M$ in the above equation.

Finally, I don't know anything about X.509 whitespace.


Infinite $\beta \eta$-reduction sequence implies infinite $\beta$-reduction sequence

As usual, the bible knows all, and Lemma 3.3.8 (p 66) gives the detailed proof of commutativity of $\beta$ and $\eta$ reductions.

Trying to reproduce it here would be tedious and wouldn't do it justice, so I'll include a picture:

You had the main idea right, it just takes a bit of practice to generalize from the specific examples.


Is any related work to this m-trails problem ?

What is $f$? I seems that you're asking for a one-to-one mapping between a power set over a power set of edges and the edges - which would surely be possible only if there's no more than one edge.


Algorithmic advantages of pathwidth over treewidth

It is shown that [1] the Mixed Chinese Postman Problem (MCPP) parameterized by pathwidth is $W[1]$-hard, even if all edges and arcs of the input graph $G$ have weight $1$ and is FPT with respect to treedepth. This is the first problem are aware of that has been shown to be $W[1]$-hard with respect to treewidth but FPT with respect to treedepth. Note that the pathwidth of a graph lies between its treewidth and treedepth.

The Steiner Multicut problem, which asks, given an undirected graph $G$, a collection $T = \{T_1, . . . , T_t\}$, $T_i ⊆ V(G)$, of terminal sets of size at most $p$, and an integer $k$, whether there is a set $S$ of at most $k$ edges or nodes such that of each set $T_i$ at least one pair of terminals is in different connected components of $G \ S$.

Node Steiner Multicut, Edge Steiner Multicut, and Restr. Node Steiner Multicut are $W[1]$-hard for the parameter $k$, even if $p = 3$ and $tw(G) = 2$ [2].

[1] https://core.ac.uk/download/pdf/77298274.pdf

[2] http://drops.dagstuhl.de/opus/volltexte/2015/4911/pdf/11.pdf


Computational complexity of quantum optics

With respect to your third question, Aaronson and Arkhipov (A&A for brevity) use a construction of linear optical quantum computing very closely related to the KLM construction. In particular, they consider the case of $n$ identical non-interacting photons in a space of $\text{poly}(n) \ge m \ge n$ modes, starting in the initial state
$$
\left|1_n\right>=\left|1,\dots,1,\ 0,\dots,0\right>\quad (n\text{ 1s}).
$$
In addition, A&A allow beamsplitters and phaseshifters, which are enough to generate all $m\times m$ unitary operators on the space of modes (importantly, though, not on the full state space of the system). Measurement is performed by counting the number of photons in each mode, producing a tuple $(s_1, s_2, \dots, s_m)$ of occupation numbers such that $\sum_i s_i = n$ and $s_i \ge 0$ for each $i$. (Most of these definitions can be found in pages 18-20 of A&A.)

Thus, in the language of the table, the A&A BosonSampling model would likely best be described as "$n$ photons, linear optics and photon counting." While the classical efficiency of sampling from this model is, strictly speaking, unknown, the ability to classically sample from the A&A model would imply a collapse of the polynomial hierarchy. Since any collapse of PH is generally considered extremely unlikely, it's not at all a stretch to say that BosonSampling is very probably not efficiently and classically simulatable.

As for BQP-universality of the A&A model, while linear optics of non-interacting bosons alone is not known to be universal for BQP, the addition of post-selected measurement is enough to obtain full BQP universality, via the celebrated KLM theorem. The acceptance probability of the postselection in the KLM construction scales as $1/16^\Gamma$, where $\Gamma$ is the number of controlled-Z gates that appear in a given circuit. Whether that is enough to conclude that the postselected linear optics model of BQP is efficient or not is thus a matter of what one defines to be efficient, but it is universal.

Aaronson explores the postselected linear optics case more in his followup paper on the #P-hardness of the permanent. This result was earlier proved by Valiant, but Aaronson presents a novel proof based on the KLM theorem. As a side note, I find that this paper makes a very nice introduction to many of the concepts that A&A use in their BosonSampling masterpiece.


Abstract definition of universal computation

Have a look at the work of Alex Heller and Robert di Paola on dominical categories. There should be further references there to older work.


Original proof that "almost all decision problems are uncomputable"?

So the answer to my original question is the following: Because the statement is a corollary of the two facts that

every program (Turing machine) is a finite binary string, i.e., a natural number,
every decision problem is a function $f: \mathbb{N} \to \{0,1\}$ and hence corresponds to a number $x \in [0,1)$ (and every such $x$ indeed encodes a meaningful decision problem, see Sasho Nikolov's first comment above)

the question about the original author / paper of this simple corollary is not that much interesting. (And the origins of the mentioned facts themselves I can trace back, of course.)

EDIT: I add here that this is the answer modulo the objection by Damiano Mazza (see in the comments above), which I need to check/think about first.


Faithful functors vs forgetful functors: exact category-theoretic defs?

you should have a look at http://ncatlab.org/nlab/show/forgetful+functor. As the nLab article says, in its common usage there is no precise definition of forgetful functor, though there are some typical examples (such as a functor $U : Alg \to Set$ forgetting some kind of algebraic structure, which will typically have a left adjoint $F : Set \to Alg$ corresponding to the construction of free algebras). And in another (useful) sense, every functor may be regarded as a forgetful functor, and classified according to how much it forgets.  There is no requirement that a functor be unfaithful for it to be called "forgetful", and many common examples of forgetful functors are faithful (such as the forgetful functor $Grp \to Set$ from groups to their underlying sets), while others are not (such as in general the functor $cod : C^\to \to C$ from the arrow category of $C$, forgetting everything about an arrow except its codomain).


Local updates in weight-balanced search trees

Section 3 of Brodal et al.'s "D$^2$-Tree: A New Overlay with Deterministic Bounds" shows how to update a weight-balanced tree in $O(1)$ amortized time, but the worst-case time is still $\Omega(\lg n)$.


Featherweight Generic Java formalization in Coq

I guess somewhat more realistic task would be to find Coq's formalisation of FJ itself (probably with some extensions, but not necessarily FGJ). The one which I googled easily is:

  Encoding Featherweight Java with Assignment and
  Immutability using The Coq Proof Assistant by Mackay et al. (2012)

[the paper, PDF],
[Coq sources, ZIP].

Seems a little bit more recent than the one you mentioned. They also mention Delaware et al. (your reference) in Related work section.


Low rank approximation of matrix under $l_2$ norm

This is the median k-flat problem. Feldman wrote some papers on this and related problems. See for example  http://arxiv.org/abs/1106.1379 .


Suppose $H$ has at least two vertices. The family of all $H$-free graphs is hereditary on induced subgraphs and the property of being $H$-free is non-trivial, where a property is non-trivial if it is true for infinitely many graphs and it is false for infinitely many graphs. Thus, the result of Lewis and Yannakakis [1] applies, showing that for all $H$ with at least two vertices, the problem is NP-complete.

[1] John M. Lewis, Mihalis Yannakakis: The Node-Deletion Problem for Hereditary Properties is NP-Complete. J. Comput. Syst. Sci. 20(2): 219-230 (1980)


Theoretical explanations for practical success of SAT solvers?

I am assuming that you are referring to CDCL SAT solvers on benchmark data sets
like those used in the SAT Competition.
These programs are based on many heuristics and lots of optimization.
There were some very good introductions to how they work at
Theoretical Foundations of Applied SAT Solving workshop at Banff in 2014
(videos).

These algorithms are based on DPLL backtracking algorithm which
tries to find a satisfying assignment by setting values to variables
and backtracks when it finds a conflict.
People have looked at how much impact these heuristics have. E.g. see

Hadi Katebi, Karem A. Sakallah, and Joao P. Marques-Silva, "Empirical Study of the Anatomy of Modern Sat Solvers", 2011

It seems that the efficiency of these SAT solvers on the benchmarks comes mainly from two two heuristics (and their variants):

VSIDS heuristic fir selecting which variable to branch on next.
CDCL: conflict-driven clause learning heuristic which learns a new clause from a conflict.

It is well-known that DPLL proofs correspond to proofs in resolution.
Without CDCL the only resolution proofs we can get are tree resolution proofs
which are much weaker than general resolution proofs.

There are results that show with CDCL we can get any general resolution proof.
However there are caveats, they need many artificial restarts, artificial branching, and/or particular preprocessing,
so it is not clear how close these are to what these programs do in practice.
See e.g. the following paper for more details:

Paul Beame and Ashish Sabharwal, "Non-Restarting SAT Solvers With Simple Preprocessing Can Efficiently Simulate Resolution", 2014

CDCL is essentially cutting branches from search space.
There are various ways of deriving a new learnt clause from a conflict.
Ideally we would add a set of minimal clauses which implied the conflict,
but in practice that can be large and can be expensive to compute.
Top SAT solvers often delete learned clauses regularly and
that helps in practice.

The other heuristic VSIDS essentially maintains a score for each variable.
Every time there is a conflict,
all scores are adjusted by multiplying them with a value $\alpha$<1 and
adding a constant to those which were "involved" in the conflict.
To see what this means think about the sequence $F(v,i)$ which is 1
if variable v was "involved" in the $i$th conflict.
Let $0<\alpha<1$ be a fixed constant.
The score of variable $v$ at time $n$ is then:
$$\sum_{i<n} F(v,i)\alpha^{(n-i)}$$

Intuitively one can say that this tries to emphasize variables which were
consistently involved in recent conflicts.
You can also think of it as a simplistic but extremely cheap way
of predicting which variables will be involved in the next conflict.
So VSIDS branches first on those variables.
One can claim that the algorithm is essentially a fail-fast algorithm,
find conflicts fast.
Fast is related to smaller number of variables set,
which means blocking large subtrees of the search tree.
But this is mostly intuition,
afaik no one has formalized it very careful to test it on SAT data sets.
Running a SAT solver on one of these data sets is not cheap,
let alone comparing it with the optimal decisions
(smallest extension of the current assignment to variables which would violate one of the clauses).
VSIDS also depends on which variables we bump as each conflict,
there are various ways to define when a variable is involved in a conflict.

There are results that show particular implementation of these ideas
correspond to a time-weighted centrality of vertices in dynamic graphs.

There are also suggestions that excluding adversarial instances like those based on NP-hard problems and crypto primitives and random instances
(which CDCL SAT solvers are not good at)
the rest of instances come from very well structured things
like software and hardware verification and
somehow these structures are exploited by CDCL SAT solvers
(lots of ideas have been mentioned like backdoors, frozen variables, etc.)
but afaik they are mostly ideas and
do not strong theoretical or experimental evidence to back them up.
I think one would have to fist rigorously define the properly and
show that the instances on which these algorithms work well
have the property and
then show that these algorithms exploit those properties.
What happens in practice is that people are mostly interested in
faster algorithms and if someone comes up with an algorithms
that is somehow got inspired by one of these ideas and
that algorithms beats other algorithms they go with the claim.

Some people keep insisting that the clause ratio and
thresholds are the only game in the town.
That is definitely false as anyone who is slightly familiar with
how industrial SAT solvers work or
has any knowledge of proof complexity would know.
There are lots of things that make a SAT solver work well or not
on an instance in practice and the clause ratio is just one of the things
that might be involved.
I think the following survey is a good starting point to
learn about the connections between proof complexity
and SAT solvers and perspective:

Jakob Nordstrom, "On the Interplay Between Proof Complexity and SAT Solving", 2015

Interestingly even the threshold phenomenon
is more complicated than most people think,
Moshe Vardi stated in his talk
"Phase transitions and computational complexity"
that the median running time of GRASP remains exponential
for random 3SAT formulas after the threshold
but that the exponent decreases
(afaik, it is not clear how fast it decreases).

Why are we studying SAT solvers (as complexity theorists)? I think the answer is the same as for other algorithms: 1. compare them, 2. find their limitations, 3. design better ones, 4. answer fundamental questions of complexity theory.

When modelling a heuristic we often replace heuristic with nondeterminism. The question then becomes is it a "fair" replacement? And here by fair I mean how close is the model in helping us answer the question above.

When we model a SAT solver as a proof system we are partly showing it limitation because the algorithm will be inefficient for statements which have lower bounds in the proof system. But there still is a gap between what the algorithm actually finds and the optimal proof in the proof system. So we need to show that the reverse as well, i.e. the algorithm can find proofs that are as good as those in the proof system. We are not close to answer that question, but the amount of heuristic that is replace by non-determinism defines how close the model is to the proof system. I don't expect that we completely drop the replacement of heuristics with nondeterminism, otherwise we would get automatizability results which have consequences on open problems in crypto, etc. But the more nondeterminism the model has the less convincing it is in explaining the behaviour of the SAT solver.

So the question when looking at a model becomes: how much does the models help explain why SAT solver A is better than SAT solver B? How helpful are they in developing better SAT solvers? Does SAT solver find proofs in practice that are close to optimal proofs in the model? ... We also need to model the practical instances.

Regarding the intuition that CDCL SAT solvers "exploits the structure of practical instances" (whatever that structure is) is generally accepted intuition I think. The real question is to give a convincing explanation of what that means and demonstrate that it is indeed true.

See also Jakob Nordstrom's own answer for more recent developments.


Problems with exponential lower computational complexity bound

Given a Turing machine $T$ and an a number $n$ encoded in unary, decide whether $T$ halts in time $2^n$. There is an $O(C^n)$ algorithm for this, and there's an almost matching $\Omega(c^n)$ lower bound (where $c < C$). See the proof of the Time Hierarchy Theorem.

If you're looking for more natural problems, Wikipedia has a list of EXPTIME-complete problems, such as evaluating positions in certain generalized versions of board games, and problems involving succinct circuits.


You can enumerate exactly the decidable languages. I've given this question as a homework problem so I'll just give a hint here: You can modify a TM $M$ to a machine $M'$ such that if $M$ is total (halts on all inputs) then $L(M')=L(M)$ and if $M$ is not total then $L(M')$ is finite.

By request I'm burning the homework question and putting in the full proof. I heard the problem from someone else (don't remember who) so this isn't original.

Define $M'(x)$ to accept if $M(x)$ accepts and $M(y)$ halts for all $y$ with $|y|\leq |x|$. Note $M'$ has the property mentioned above.

Let $M_1,M_2,\ldots$ be a standard enumeration of Turing machines. The enumeration $M'_1,M'_2,\ldots$ is an enumeration of Turing machines such that $D=\{L(M'_1),L(M'_2),\ldots\}$ is exactly the set of decidable languages.

DECIDABLE is contained in $D$: If $L$ is decidable then $L=M_i$ for some total $M_i$ so $L(M'_i)=L(M_i)=L$.

$D$ is contained in DECIDABLE: If $M_i$ is total then $L(M'_i)=L(M_i)$ is decidable. If $M_i$ is not total then $L(M'_i)$ is finite and thus decidable.


Find a largest cube contained in the union of cuboids

Well, here is an first try silly answer... Take a plane through each face of of the rectangular boxes. This form a grid of size $O(n^3)$. It is not hard to compute for each such grid cell whether its inside the union or outside. Now, from each grid vertex, grow a cube (having this vertex as a vertex) trying to make it as large as possible. Doing it in the most naive way, this takes $O(n^3 \log n)$ time per vertex, but probably using orthogonal range searching magic, one should be able to do it in $\log^{O(1)} n$ per vertex. So $O(n^3 \log^{O(1)} n )$ should be possible...

A second try: Compute the union. In this specific case, this can be done in $O( n \log n)$ time (by sweeping planes). Now, observe that you just need to compute the $L_\infty$ voronoi diagram of the boundary of the union. Using the result: http://vw.stanford.edu/~vladlen/publications/vor-polyhedral.pdf, this can be done in $O(n^{2+\varepsilon})$ time, for an arbitrary small constant $\varepsilon > 0$.

Breaking the $O(n^2)$ running time bound here would be interesting, IMHO.


Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm?


In your reference [2], Barendregt shows that the rule

$$ \frac{\Gamma\vdash N:\alpha\quad M\rightarrow^* N\quad \alpha\equiv \beta}{\Gamma\vdash N:\beta} $$

is indeed admissible for Pure Type Systems, as (a trivial consequence of) Corollary 5.2.16.

However there is an issue with your original rule already: the rule should read

$$ \frac{\Gamma\vdash N:\alpha\quad\alpha\equiv \beta\quad {\bf \Gamma\vdash\beta : s}}{\Gamma\vdash N:\beta} $$
for some sort $s$, otherwise you may introduce ill-formed types into your typing judgement, like $(\lambda x y. y)\ \Omega\ (\alpha\rightarrow\alpha)$.

This can be a problem for your extended rule, as usually you only allow well-formed types into your context, with a rule along the lines of

$$ \frac{\Gamma\vdash \alpha:s}{\Gamma,x:\alpha\ \ \mathrm{wf}}$$

If you add the relevant well-formedness requirements ($\Delta\ \mathrm{wf}$ and $\Delta\vdash\beta:s$), and restrict the term level to reduction rather than conversion, then your sophisticated rule becomes admissible.

This is a not completely trivial induction, using the following Lemma:

  If $\Gamma\vdash t:\alpha$, $\Gamma\equiv\Delta$ and $\Delta\ \mathrm{wf}$ then $\Gamma\vdash t:\alpha$

The lemma is proven by induction using an application of the conversion rule at the variable case. The theorem is then proven using the above lemma to discharge the conversion case.

You could adopt the opposite point of view of keeping your more general conversion rule and weakening the context formation rule to

$$ \frac{\Gamma\vdash \beta:s\quad \beta\equiv \alpha}{\Gamma,x:\alpha\ \ \mathrm{wf}}$$

then you get a system with possibly ill-formed types, but no additional typeable terms, though I think this is a very non-trivial result.


What if a problem is both in $\Pi_2^p$ and $NP$-hard?

The answer is "no".

In fact, in addition to the general argument pointed to by Tsuyoshi, there are a number of well-studied complexity classes which contain NP, but are contained in $\Pi_2^P$.

Two interesting containment chains are:

$NP \subseteq \Delta_2^P \subseteq S_2^P \subseteq \Sigma_2^P \cap \Pi_2^P \subseteq \Pi_2^P$

and

$NP \subseteq MA \subseteq BP \cdot NP = AM \subseteq \Pi_2^P$

To help clarify the letter soup, see Wikipedia's article on the Arthur-Merlin protocol and $S_2^P$. There's also of course the complexity zoo for descriptions of these various classes.

Also take a look at this question asking about canonical $\Delta_i^P$-complete problems.


Graduate studies (PhD) in CS Theory vs. Applied Math

My two cents are that in my university we've had both mathematics PhD students working on computer science questions (and faculty in the math department with interests in computer science), as well as some computer science students working primarily on purely combinatorial problems.

You might be right that it's sometimes easier to work on CS questions as a math student, rather than on pure math questions as a CS student. Keep in mind that at least in the first two years these two kinds of programs might be fairly different in content. As a math student you will be expected to take core math courses as real analysis, complex analysis, topology, algebra, etc. Combinatorics is usually not part of this core. For a CS program there will be a core CS requirement, which usually involves taking some mix of theoretical and more applied courses. While the core in a math program is fairly standard and strictly enforced, the core in a CS program tends to depend a lot on the program, and the requirements might be more flexible.

However, all that is not really of primary importance (although it will be loads of work) and is all over within the first two years. I understand it's hard to know what you want to work on before you're in grad school, and many students change  their fields. Nevertheless, I would encourage you to look at the faculty pages of schools you are considering, see what professors are working on, and write several emails to faculty and students. PhD level studies are much more about personal relationships and personal drive than they're about a program as a whole. Good programs at the PhD level in my view are distinguished by a strong faculty, and an energetic research culture, rather than by curriculum. You should inquire from faculty and current students about questions like the level of collaboration between math and CS departments. And you should really try to find faculty that have a mix of interests that appeals to you. It's a good idea to write to them to express your interest as well.

As far as industry jobs, I'm not sure there is a huge difference between a CS theory degree and an applied math  degree. But I am not very knowledgeable about this.


"Checking equality for Kolmogorov complexity of two sequences" is computable?

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)$.)


Intersection of two unsorted sets or lists

In the algebraic decision/computation tree models, your problem has an $\Omega(n\log n)$ lower bound, even if you know in advance that one of your lists contains the integers $1$ through $n$ in sorted order, and you only need to check whether the second list is a permutation of the first.

  Proof (for algebraic computation trees): The set of points whose coordinates are permutations of $(1,2,\dots,n)$ has $n!$ components. Ben-Or proved that for any algebraic computation tree of height $h$, the set of points in $R^n$ that reach YES leaves has at most $2^h 3^{n+h}$ components. Solve for $h$.

If you are restricted to equality tests, an $\Omega(n^2)$ lower bound follows from a straightforward adversary argument.


The solution is here, I hope that it helps somebody.. The link given also in the question itself contains a useful pdf from geometrictools.com

Sorry, the question was really not that hard, but it is somehow quite popular and there's still a lot of confusion about "all faces of a planar embedding of a graph"


You can defiintely cook up promise problems where RAM is much stronger.  Of course it's weird because you have to actually phrase your problems in terms of comparisons. suppose your memory is initialised into a permtuation, i.e. with memory registers x(1), ..., x(n) taking on the values 1, .., n exactly once each.    The problem is to compute the # of i s.t. x(i) < x(1).


Is there a normalizing (or perpetual) reduction strategy for untyped combinators?

SKI combinators were used as the implementation technique for Miranda, a lazy functional language developed by David Turner. The reduction strategy you are after is
simply to perform the reductions left to right (aka normal order or call-by-name reduction). This is called SKI combinator reduction, and it's naturally lazy. If a normalising reduction sequence exists, then this reduction strategy will find it.

One problem with SKI combinators is that they have the unfortunate property of resulting in an exponential blowout in code size during reduction.

See:

D.A. Turner. A new implementation technique for applicative languages. Soft. Pract. and Exper., 9, pp. 31-49, 1979.
Lambda-Calculus and Combinators: An Introduction, Second Edition by J. R. Hindley and J. P. Seldin


Closure of Recognizable Languages under Kleene Star: Algebraic Proof?

For a pointer on concatenation-like operations (including Kleene star) and their impact on the algebraic structure, you can look to Schützenberger products (see here [1] for instance).

[1] Pin, Jean-Éric. "Theme and variations on the concatenation product." International Conference on Algebraic Informatics. Springer, Berlin, Heidelberg, 2011, https://www.irif.fr/~jep/PDF/ThemeVariations.pdf


Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

Could you post the original Japanese title/reference?
Also, you might consider just writing to the author - assuming it's the same guy he is a professor at the University of Tokyo:
http://www.it.k.u-tokyo.ac.jp/~kunihiro/
and almost certainly would reply.
Sorry to post this as an answer, it should be a comment but I don't have the rep for that yet apparently...
EDIT:  So, I took a look at the original Japanese.  As a preface, I am currently a PhD student in the EE department at U. Tokyo, originally from the U.S., and I do technical JA->EN translation as a part-time job. However, this topic area is well outside my comfort zone so please take my opinion with a grain of salt!
Basically the conclusion (4) says:

べき乗剰余演算を行う量子回路を提案した。提案方式は、右向きbinary methodを採用し、Montgomery Reductionを採用するという特徴を持っている。従来の方式よりも、回路の構成要素が少ないという特徴を持っている。qubitが多く必要となるという欠点は持つが、より少ない計算時間で計算ができると期待される。
[In this paper] We proposed a new quantum circuit for computing modular exponentiation. The proposed method utilizes an LR binary method, and is also characterized by use of the Montgomery Reduction.  Compared with previous methods, the proposed method requires fewer components to construct the circuit.  The proposed method does however, have the drawback of requiring a large number of qubits, but we are confident that it will be computationally efficient ( lit: require very little computation time ).

I tried searching for related follow-up papers in both English and Japanese but was unsuccessful.   My guess is that the approach proved unsuccessful, or the professor got busy with something else (looks like this was around when he switched universities).
I think that your best bet at this point, assuming you want to follow up the rest of the way and get a concrete answer, is to write professor Kunihiro directly (in English!)


Sub-exponential algorithm for Hamiltonian cycle problem on cubic planar graphs?

Actually, you don't need to exploit the "Catalan structure" in planar graphs to get a $2^{O(\sqrt{n})}$ time bound as Saeed suggests. Cygan et al. show you how to detect a Hamiltonian Cycle in $\operatorname{poly}(n)4^{\operatorname{tw}(G)}$ time even in general graphs, and in the final version of the paper they also describe how this can be improved to $\operatorname{poly}(n)3^{\operatorname{tw}(G)}$ time in cubic graphs.

The above algorithm is randomized. If you insist on a deterministic one, this is also possible with a slightly larger base constant, see Bodlaender et al.


Why would a TCS researcher need funding?

This is purely US-centric: other countries have different funding models. This is also from the perspective of an academic with a Ph.D, rather than a graduate student

As Jamie and Peter point out, the primary purpose of funding is to support graduate students. A secondary purpose is to support yourself during the summer. It's not widely known, but most US-based academics aren't paid for the 3 months of summer, and use grant money as salary for those months (I'll not discuss the limitations of NSF vs DARPA etc etc).

So you say, "I don't need students, I'll just work with colleagues". Great ! but then you need money to visit them. Without grant money, you have to wait your turn for whatever meager departmental funds might be available for travel (usually minimal).

So you then say "Fine ! I'll use skype and email to collaborate". Great ! but then you need to travel to a conference to give a talk. How do you fund that ?

So you say "Fine ! I'll just publish in journals and on the arxiv, and the brilliance of my research will shine through". Um, yeah....

If you're a junior academic, not getting funding can also affect your ability to retain your job itself. Funding is a major income source for most American universities.

None of this is ideal. But that's how the system is currently structured, dating back to Vannevar Bush, the founding of the NSF, and the mutation of the university into a research-generating enterprise.


In this context, the graph nodes have some sort of unique identifier (a hash or checksum), right? So you don't need to do any kind of subgraph isomorphism testing, you just need a list of the nodes that differ between your two versions, and the edges aren't really useful at all for this step. My SIGCOMM 2011 paper "What's the difference? Efficient set reconciliation without prior context" (with Goodrich, Uyeda, and Varghese) considers exactly this problem: it turns out that you can determine the identities of the nodes that are held by one but not both of the two communicating servers, using an amount of communication that is proportional only to the number of changed nodes and using only a single round-trip. Once you have that information, it's easy to pull the changes themselves in a second round-trip, again with optimal communication.


Dependence of decidability on the encoding of Turing machines

For a given computable $f$, the decidability of $L_f$ is independent of the encoding of Turing machines if and only $f$ is eventually injective (i.e., there exists a finite $X\subseteq\def\N{\mathbb N}\N$ such that $f\restriction(\N\smallsetminus X)$ is injective, or equivalently, $\{\def\<#1>{\langle#1\rangle}\<n,m>:n\ne m,f(n)=f(m)\}$ is finite).

If $f$ is computable and eventually injective, then $L_f$ is undecidable for any encoding.

Assume for contradiction that $L_f$ is decidable. Then
$$\{m\in\N:\exists n\in\N\:(f(n)=m\land n\notin L_f)\}$$
is r.e., hence it is accepted by infinitely many Turing machines; in particular, using the assumption, it is accepted by a TM $M$ such that $f(n)\ne f(\<M>)$ for all $n\ne\<M>$. Then
$$\<M>\in L_f\iff M\text{ accepts }f(\<M>)\iff\<M>\notin L_f,$$
a contradiction.

If $f$ is not eventually injective, then the decidability of $L_f$ depends on the encoding.

As shown in Aryeh’s answer, $L_f$ is undecidable under the standard encoding, hence it suffices to exhibit an encoding that makes $L_f$ is decidable. Let $\{M_m:m\in\N\}$ be any enumeration of TMs, and define $X\subseteq\N$ by
$$n\in X\iff|\{m<n:f(n)=f(m)\}|\text{ is even.}$$
We define a new enumeration $\{M'_n:n\in\N\}$ by
$M'_n=M_{m(n)}$, where $m(n)$ is defined by induction on $n$:
$$m(n)=\begin{cases}
  \min\bigl\{m\in\N\smallsetminus\{m(i):i<n\}:M_m\text{ accepts }f(n)\bigr\},&\text{if }n\in X,\\
  \min\bigl\{m\in\N\smallsetminus\{m(i):i<n\}:M_m\text{ does not accept }f(n)\bigr\},&\text{if }n\notin X.
\end{cases}$$
To see that $\{M'_n:n\in\N\}$ indeed enumerates all TMs, assume for contradiction that $m$ is least such that $m\ne m(n)$ for all $n\in\N$. Since $f$ is not eventually injective, there are $n<n'$ such that $f(n)=f(n')$ and $\{0,\dots,m-1\}\subseteq\{m(i):i<n\}$. We may assume $n'>n$ is smallest such that $f(n')=f(n)$, which implies
$$n\in X\iff n'\notin X.$$
Thus, either $n''=n$ or $n''=n'$ satisfies
$$M_m\text{ accepts }f(n'')\iff n''\in X,$$
which implies $m(n'')=m$ by the definition of $m(n'')$, a contradiction.
Thus, we may define an encoding of TM by $\<M'_n>=n$, and then it follows from the definition that
$$L_f=X,$$
which is decidable.

The answer above assumes that an encoding of TM has to be injective; this is not specified in the OP, but I suppose this is just an omission, as I fail to see how something that assigns the same code to two different TM can be considered an “encoding” of TM.
Anyway, if we allow non-injective encodings, the answer is that the decidability of $L_f$ depends on the encoding for every $f$: it is undecidable under the standard encoding by Aryeh’s answer, while it is trivially decidable (because finite) for the constant encoding $\<M>=0$.


Finding intersections of numerically implemented 1-dimensional curves on a 2-dimensional plane

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

(Or open any standard book on Computational Geometry).

For practical implemented algorithms, see CGAL http://www.cgal.org/

If your main problem is numerical issues, then this can be challenging in practice. A lot of practical work on this problem was done by Dan Halperin in Tel-Aviv University.


What you need for a Markov chain to converge to an equal distribution over all possible sequences of balls is that it is reversible: the probability of moving from sequence $i$ to sequence $j$ is the same as moving in the opposite direction. I thus propose that you use the following moves (with some fixed probability distribution to choose which type of move to make) to perform a Markov chain on all possible sequences. In the following, a "run" is a maximum-length consecutive subsequence of balls of the same colour. This Markov chain relies on there being at least three colours.

Pick two runs at random. If you can exchange them and still have a legal sequence, do so.
Pick two adjacent runs. If you can exchange them and still have a legal sequence, do so.
Pick two runs of the same colour. Redistribute the balls in them randomly among legal possibilities (so if the maximum number of balls in a single run was 3, and you had 5 balls total in the two chosen runs, the first one is equally likely to get 2 or 3 balls; if there were 3 balls total, the first is equally likely to get 1 or 2; if there were 4 balls total, 1, 2, and 3 are all equally likely).
Pick some colour $C_i$ at random. Consider the sequence $S'$ of balls with all balls of colour $C_i$ removed. Now, pick at random two points in $S'$ where adjacent balls of different colours touch.

a. If there are two runs of colour $C_i$ at these two points in the original sequence $S$, and neither is maximum length, move a ball from one to the other, with each direction chosen with probability ½.

b. If there are two runs of colour $C_i$ at these two points in the original sequence $S$, but one is maximum length and the other is not, move a ball from the maximum length run to the shorter one with probability ½.

c. If there is just one run of colour $C_i$ at one of these two points in $S$, with probability ½ move one ball from the run to the other point.

d. If there is no run of colour $C_i$ at either of these points, or if there are runs of maximum length at both of these points, do nothing.

If my analysis is right, this is a reversible Markov chain that eventually converges to a uniform distribution of legal sequences of coloured balls, so if you run this chain for long enough, you will get very close to this uniform distribution.

How can you tell when this has converged? I would suggest watching the entropy of this sequence, and stop when it stops increasing. How do you compute the entropy? There are two main terms in the entropy calculation: the distribution of run lengths, and the sequence of colors each run has. For the distribution of run lengths, assume that there are $n_{i,k}$ runs of colour $i$ with length $k$. The contribution of these to the entropy is
$$ \sum_i \ \log_2 \ { \sum_k n_{i,k} \choose n_{i,1}\ n_{i,2}\ \ldots \ n_{i,r} }, $$
where $r$ is the maximum permissible length of a run. Now, let us consider the contribution of the colour sequence to the entropy. Suppose there are $m_{i,j}$ places where a run of colour $i$ is immediately followed by one of colour $j$ (so $m_{i,i}=0$). The contribution of this to the entropy is
$$ \sum_i \ \log_2\  { \sum_j m_{i,j} \choose  m_{i,1}\ m_{i,2}\ \ldots \ m_{i,c} }, $$
where $c$ is the number of colours.

(In the interest of accuracy, let me note that we are leaving out a number of contributions to the entropy, including the colour of the first ball, but these are lower order terms which should be safe to neglect.)

UPDATE:

There should be ways of speeding this up. I believe that for steps c and d, you can use analysis to perform both these steps over all runs of one color at once. For steps a and b, this is equivalent to the question of finding a random sequence of colored balls with the constraint that no two balls of the same color touch. There should be some good way of doing the mixing for this problem. Then you just have to alternate a/b steps with c/d steps, where each step mixes over those two moves completely. I think this should converge quite fast, although I don't have any rigorous analysis for this Markov chain.


Is partitioning a multiset into two multisets with equal averages NP-complete?

One NP-hard variant of the PARTITION problem is as follows:

  INSTANCE: $2k$ positive integers $a_1,\ldots,a_{2k}$ with $\sum_{i=1}^{2k}a_i=2A$
  QUESTION: Does there exist an index set $I\subseteq\{1,\ldots,2k\}$ with $|I|=k$ so that $\sum_{i\in I}a_i=A$?

Take the integers $a_1,\ldots,a_{2k}$ together with two copies of the integer $100kA$. It is straightforward to see that these $2k+2$ numbers allow a partition into two sets with equal averages, if and only if the original instance of PARTITION has answer yes.


If you have notions of linear logic, you might want to have a look at the article Soft Linear Logic and Polynomial Time [1] that describes a variant of linear logic (some of the deduction rules have been modified) whose formulas are only provable by proof that are polynomial-time algorithm.

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.1196

Abstract: We present a subsystem of second order Linear Logic with restricted rules for exponentials so that proofs correspond to polynomial time algorithms, and vice-versa.


The polynomial languages and ordered syntactic monoids

The relation $pu^{k+1}q\in L\Rightarrow pu^k vu^kq\in L$ is true for any $p,q$, $k$ big enough and $v$ with $alph(v)\subseteq alph(u)$.

Let call $a$ the first letter of $u$ and $b$ the last letter.
Let $v$ with $alph(v)\subseteq alph(u)$, and $v'=uvu$.

Then by using the relation above with $v'$, we get that for any $p,q$ and $k$ big enough, we have $pu^{k}q\in L\Rightarrow pu^k vu^kq\in L$, which is the definition of $u^kvu^k\leq_L u^k$. In particular, for $n$ big enough, we get $u^{n!}vu^{n!}\leq_L u^{n!}$, which is the wanted equation.


About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

There is a lot of recent work on these questions spurred by interest in deep learning and other non-convex optimization tasks. If the objective is differentiable and smooth (i.e. if the gradient is Lipschitz), then you do not need to assume bounded gradients and there are quite a few assumptions on the noise you can adopt, and they are reviewed (with convergence results) in Khaled and Richtárik (2020) (conflict of interest: I'm a coauthor of this paper).

If the objective is not smooth, then all the analysis of SGD I know of assumes bounded subgradients possibly in addition to other regularity properties (see Davis and Drusvyatskiy (2019) and Zhang et al. (2020), although the latter does not analyze the vanilla SGD per-se). Note that if you enforce some sort of iterate normalization mechanism, feedforward ReLU networks do have bounded subgradients.

Unfortunately, even neural networks with differentiable losses are not globally smooth. For Adam and AdaGrad, it turns out that you do not need global smoothness as Défossez et al. (2020) show. There are a lot more results specifically for neural networks, but I will refrain from mentioning them since your question was about general assumptions.


Have any generalizations of maximum weight matching been studied?

There are several extensions of the problem to more general structures.  For instance:

Matroid matching (lecture notes, Matroid matching and some applications, Matroid Matching: the Power of Local Search)
Path-matching (Path-matching problems, Matching, matroids, and extensions)
Hypergraph matching (Can't find any good references)

Generally, these extensions are NP-hard.


Fast approximate middle of points in a metric space?

There's a rather large literature on this problem. In brief, the problem you're looking at is called the $1$-median problem for a metric space. Since you're allowing for things "near" the middle, I'll assume approximations are ok. I also don't know what you mean by space less than $n^2$, since the input size itself is $n^2$.

Having said that, for an arbitrary metric space you can get a "sublinear" approximation (i.e one that runs in $o(n^2)$ time. Specifically, Piotr Indyk showed that you can get a $(1+\epsilon)$ approximation in time linear in $n$ and polynomial in $1/\epsilon$.

For structured spaces you can also do quite well. In Euclidean space, core-set techniques for the $k$-median problem (of which the 1-median is a special case) give you similar bounds (linear in n) to get arbitrarily good approximations. The caveat in this case is that the solution you get might not be one of the input points.


Single author papers against my advisor's will?

As a department chair, I can say you aren't alone. These situations come up all too often.

Please do reach out to your department chair, graduate program director or grad student ombudsperson if your institution has one. We want to know when our faculty are behaving badly and often we can help.


It doesn't sound hopeful in general.

For example, let $P$ be the statement "all vertices have degree 0 or 1". Let $p=1/n$ and $n$ even. Then conditioned on the event of being regular, with high probability the graph is 0-regular or 1-regular, so $P$ holds with high probability. Also $P$ is preserved by removing edges. But it is certainly not the case that $P$ holds with high probability under $G_{n,p}$.

Even in other situations (say, fixed $p$ as $n\to\infty$), I would expect that there are events $P$ of the form "maximum degree less than $d$" which satisfy your 1. and 2. but don't hold w.h.p. for $G_{n,p}$.

So something more than just the two properties you wrote down will be needed....


NP-intermediate problems with efficient quantum solutions

Graph isomorphism is not known to be in BQP. There has been a lot of work done on trying to put it in. A very intriguing observation is that graph isomorphism could be solved if quantum computers could solve the non-abelian hidden subgroup problem for the symmetric group (factoring and discrete log are solved by using the abelian hidden subgroup problem, which in turn is solved by applying the quantum Fourier transform on abelian groups).

One of the ways people have tried to solve graph isomorphism was by applying the quantum Fourier transform for non-abelian groups. There are algorithms for the quantum Fourier transform for many non-abelian groups, including the symmetric group. Unfortunately, it appears that it may not be possible to use the quantum Fourier transform for the symmetric group to solve graph isomorphism; there have been quite a few papers written about this which show that it doesn't work, given various assumptions on the structure of the algorithm. These papers are probably what you find when you google.


What algorithm on a PRAM computes the connected components of a graph with least time complexity?

As Jeff suggested, I moved my comment to the answer section:

On the CRCW PRAM, achieving  $O(\log n)$ time is fairly easy (see J. v. Leeuwen, Handbook of TCS, Chapter 17).

On the EREW PRAM, Chong, Han and Lam (JACM, Vol 48(2), 2001) give an $O(\log n)$ algorithm for MST on an EREW PRAM. This should also solve the CC problem. Alternatively, use Reingold's logspace algorithm for undirected connectivity and standard simulation methods.


Estimate the maximum frequency of substring with given length in a very long character stream

If $D$ has high min-entropy, then there's a "sharp cut-off" phenomenom: there's a value $l_0$ depending only on $n,B$ such that the value of $l$ is almost always very close to $l_0$, when $S$ is drawn randomly from $D^n$.

For a simple example, consider the case where $B=2$ and $D$ is the uniform distribution on $\Sigma$.  Then

$$l_0 \approx {\lg(n^2/2) \over \lg |\Sigma|},$$

due to the birthday paradox.

Thus, an algorithm can ignore the input string $S$, look only at $B,n$, compute the appropriate $l_0$, and output that.  This will be approximately correct, almost all the time.

That's why I say this can be treated as purely a mathematical question, not an algorithmic one.


Has ping based failure detector 'strong completeness' and 'weak accuracy'?

There is a lot that needs to be clarified about the model (ping) in which we want to evaluate. What are the processes IDs ? Is it IPs (IP network) ? Is the IPs permanent ? Can the IP change ? Are they connected point wise or there is a router/switch ? Can the switch fail ? Are the connections trusted or can a connection fail between two correct processes ?

I'll give counter examples assuming the TCP/IP model, where there are not permanent IPs (DHCP based IP configuration).

Strong completeness requires that every process that crashes is permanently suspected by every correct process.

Counter-example: Take process A and B, with IPs IP1 and IP2. Process A crashes permanently, releasing the IP. Process B makes a brief disconnection and acquires a new IP, which happen to be IP1.

Solution: We must assume IPs are strictly bound to each process, and can never change. Unless you identify processes with other application layer unique IDs.

Weak accuracy requires some correct processes are never suspected. Actually, if the switch/router fails for a few minutes, every process might suspect all other processes, even if all of them are correct.

The ping is delusive  because it is on the IP level. To avoid these complexities and be able to reduce the needed assumptions to a minimum, think about some level of abstraction, like an application-level failure detector. However if you will really get down to the details, there is a lot to consider in the physical layer (wifi, ethernet) and on other layers as well (TCP, UDP, NAT) etc.


Why lower bounds for boolean Circuits does not imply arithmetic circuits lower bounds

For arithmetic circuits over $\mathbb{Z}$ your argument is exactly right. The same argument works for arithmetic circuits over $\mathbb{Q}$ which don't use any fractions $a/b$ where $b$ is even.

However, the argument no longer works if you talk about arithmetic circuits over other rings, such as: general arithmetic circuits over $\mathbb{Q}$ (i.e. without the restriction above), $\mathbb{R}$, algebraic number fields, $\mathbb{C}$, or finite fields $\mathbb{F}_{q}$ with $q \neq 2$.

(This is essentially the same reason that in algebraic geometry $\mathbb{Z}$ is often considered of so-called "mixed characteristic," rather than characteristic zero.)

However, depth 3 Boolean lower bounds for circuits with {AND,OR,NOT} are less easily related to lower bounds for arithmetic circuits over $\mathbb{Z}$. (Yes, {AND,XOR} is a complete basis, but typically depth 3 circuits over {AND, OR, NOT} you consider NOT gates free, whereas implementing NOT with XOR you're then using an XOR gate, which you actually count. Similarly, although $a \vee b = \neg (\neg a \wedge \neg b)$, when you implement this single OR gate with AND and XOR, you get a little gadget of depth 3.)

The general statement is: let $f$ be a polynomial with coefficients in a ring $R$, and suppose $\varphi\colon R \to S$ is a ring homomorphism. By applying $\varphi$ to every coefficient of $f$ you get a polynomial with coefficients in $S$, which I'll denote $f_S$. Then a lower bound for computing $f_S$ by $S$-arithmetic circuits implies the same lower bound for computing $f$ by $R$-arithmetic circuits.


Rearranging strings to minimise storage in a trie

The problem I'm wondering about was tackled long ago (1977) by Douglas Comer and Ravi Sethi, in a paper entitled "The Complexity of Trie Index Construction". They show that the decision version of the above problem, as well as three other variants, are NP-complete.


Is $GCT$ necessarily a negative result program?

It depends a little what you mean exactly by "GCT". If you mean it more generally, the answer is certainly yes. If you mean it more specifically about multiplicity obstructions, this is a bit more of an open question.
If you mean GCT generally as applying algebraic geometry to complexity theory, or perhaps even slightly more specifically using geometry to cross the GCT chasm, as in this quote:

By geometric complexity theory, we mean henceforth any approach to cross the GCT chasm using asynthesis of geometry and complexity theory. -Mulmuley, GCT V arXiv

Then the answer is that algebraic geometry can certainly prove positive results in complexity theory. First in principle: $\mathsf{VNP} \nsubseteq \overline{\mathsf{VP}}$ if and only if there is a polynomial vanishing on the latter but not on the former - this is very basic algebraic geometry. Similar results hold whenever one considers the approximative/border/closure of a complexity class. Second, in history: border-rank methods are algebro-geometric, and have yielded new algorithms for matrix multiplication, as well as results relating the complexity of a polynomial to those of its factors Bürgisser (arXiv)
If, on the other hand, you mean more specifically separating complexity classes using multiplicity obstructions, then your question gets at the "converse" question in GCT: that is, it is a theorem that a multiplicity obstruction implies a separation of complexity classes, but is the converse true? In general for $G$-varieties this is almost certainly false (that is, given a reductive algebraic group $G$ like $GL_n$ acting algebraically on a vector space $V$, and two varieties $X,Y \subseteq V$ that are each unions of $G$-orbits, is it the case that $X \subseteq Y$ iff there are no multiplicity obstructions?). But for the particular varieties of interest in GCT, there is some chance that the converse might hold. A first indication of this is that the polynomials studied are characterized by their symmetries, which already tells you that the group action here is telling you more about these particular varieties than it would be for general $G$-varieties.
If the converse held, then one could in principle get a collapse of complexity classes by proving that there were no multiplicity obstructions. On the one hand, this seems quite hard. On the other hand, Bürgisser-Ikenmeyer-Panova (arXiv) proved that there were no occurrence obstructions (multiplicty zero in one class and nonzero in the other).
However, even if the converse didn't hold, knowing that there were no multiplicity obstructions would still, I think, yield significant insight into the relationship between these problems. Each representation of $GL_{n^2}$ appearing in the ring of (meta)polynomials (a polynomial ring in a number of variables that is equal to the number of monomials of degree $n$ in $n^2$ variables) corresponds to a $GL_{n^2}$-invariant property of (ordinary) polynomials. The isomorphism type of such a representation tells you how its defining equations transform under the action of $GL_{n^2}$. The multiplicity of a given isomorphism type (isotype) in the coordinate ring of one of these varieties $X$ thus tells you how many properties of that isotype the polynomials in $X$ have. Knowing that there were no multiplicity obstructions would still imply that these complexity classes share many more properties than one might initially think.


Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

Perhaps I found some relevant information in:

Jean-Michel Autebert, Jean Berstel, Luc Boasson; Context-Free Languages and Pushdown Automata; Handbook of Formal Languages; 1997, pp 111-174

DPDAs without $\epsilon$-transitions are known as realtime deterministic pushdown automata.

They are less powerful than DPDAs, for example

$L = \{ a^n b^p c  a^n \mid p,n > 0\} \cup \{ a^nb^pdb^p\mid p,n > 0 \}$

is deterministic and can be recognized by a DPDA, but cannot be recognized by any realtime DPDA.

What you can do is eliminate increasing $\epsilon$-transitions:

Proposition 5.4: For any DPDA it is possible to construct a DPDA recognizing the same language such that any $\epsilon$-rule is decreasing.


Hashing sets of integers for inclusion testing

(This answer was originally in comments but I'm moving it to a separate answer at Suresh's suggestion.)

For your application with very small sets you probably want the number of Bloom hash functions $k$ to be quite large to minimize the number of false positives. To save computation time I suggest the following variation of a Bloom filter. Assume you have three traditional hash functions $h_1$, $h_2$, $h_3$ for the elements that each produce $m$-bit strings. Hash each element to the bitwise and of these three hash functions. The resulting element hashes will be about $2^{-3}=1/8^{th}$ ones. Hash each set to the bitwise or of the hashes of its constituent elements. Because your sets have 3-8 elements the resulting hashes will be in the neighborhood of one-half ones, which is presumably what you want to best keep the false positive rate down.

The difference between the above scheme are the traditional Bloom filter is analogous to the difference between the classic $G_{n,p}$ Erdos random graph model and random $d$-regular graphs. The above scheme has the effective number $k$ of Bloom hashes vary a bit around its mean of $m/8$ but $m/8$ is pretty large so this difference shouldn't matter.


Good description of Calculus of Inductive Construction

You can try the Coq user manual, in particular this section is pretty nice (the server seems to be down at the moment though).

For meta-theory you can try some recent work of Benjamin Werner et al., see Proof-irrelevant model of CC with predicative induction and judgmental equality
 and On the strength of proof-irrelevant type theories for the most salient work.


Consequences of a $p$-optimal proof system for $\operatorname{TAUT}$

See the Wikipedia article for propositional proof complexity. p-simulation is similar to reductions between complexity classes. Existence of a p-optimal proof system is a well-known open problem in proof complexity.

It is statement 7 in Krajicek and Pudlak 1989. See page 1066 and 1067 for a list of statements implied/implying it. There are more statements that you can find by Googling.

There are experts who conjecture that extended Frege is an p-optimal proof system. Existence of a p-optimal proof system is a weaker statement than existence of a super proof system (which is equivalent to $\mathsf{NP}=\mathsf{coNP}$).

Jan Krajicek and P. Pudlak, "Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations", J. Symbolic Logic, 54(3), (1989), pp. 1063-1079.

Yijia Chen and Jörg Flum, "On optimal proof systems and logics for PTIME", 2010.

Zenon Sadowski, "On an optimal propositional proof system and the structure of easy subsets of TAUT", 2002.


Lower bounds on monotone space complexity

This not quite an answer, but rather an "extended comment".

To question (i): property (*) holds because of read-once, not because of the monotonicity, and this is why the argument fails in the read-many (even monotone) case: then the combined paths need not be PMs, they can be arbitrary graphs containing a PM.

In the read-once case, even the Exact PM (accept a graph iff it is a perfect matching) requires exponential size (by the same argument as yours). But if we allow negations, then EPM can be computed by a circuit of size $O(n^3)$: check if every node in A has degree at least one, and if every node in B has degree at most one. The resulting switching network is "almost read-once": every consistent path is read -once. Search term "null-path" here for more information.

To question (ii): I haven't understood what "it" here refers to? But as far as I know, the $n^{\Omega(\log n)}$ lower bound of Razborov (for monotone circuit size of PM) remains the strongest one. Even though monotone switching networks constitute a special case of monotone circuits (where one input of each AND gate must be a variable), no stronger lower bounds for PM are known here.


This can be solved by standard linear programming algorithms.  A set of weighted choices is described by variables $y_{ij}$, where $y_{ij}=w$ if we choose $a_i$ from the $j$th set with weight $w$.  To set this up, we use an additional variable $m$ which will represent the minimum number of times any variable is selected.  We then have four kinds of constraints:

for each $i$, $j$: $0 \le y_{ij} \le 1$ if $a_i$ is in the $j$th set;
for each $i$, $j$: $y_{ij} = 0$ if $a_i$ is not in the $j$th set;
for each $j$: $\sum_i y_{ij}=1$ [choosing a total of 1 element from the $j$th set];
for each $i$: $m \le \sum_j y_{ij}$ [$m$ is at most the number of chosen $a_i$'s].

We choose the $y_{ij}$'s to maximize $m$; the constraints and the objective function are linear.  (In the non-weighted case, we additionally require $y_{ij}$ to be integral; this makes the problem harder but integer linear programming packages are readily available.)

This formulation has the following geometric interpretation.  Identify $a_i$ with the $i$-th standard basis vector in $\mathbf{R}^n$.  For each set, say $\{a_{i_0},\ldots,a_{i_k}\}$, the collection of possible weighted choices from this set is the $k$-simplex with the given $a_{i_j}$'s as vertices.  The Minkowski sum of all these simplices is the convex polyhedron which contains precisely the possible vectors $(x_1,\ldots,x_n)$ of totals for the elements $a_1,\ldots,a_n$.  The linear programming formulation above seeks a point in this polyhedron which is as far from as possible from the nearest coordinate hyperplane.