CNF encoding of set cover - NExpTime-completness Notation: given a CNF formula A over variables X, we write $[A(X)]$ for the set of valuations $v: X \to \{0,1\}$ such that $A(X/v)$ is true, i.e. the set of valuations that makes formula A true.
I suspect that the following problem is NExpTime-complete:
-given two CNF formulas $A(X)$ and $B(Y,X)$, and an integer $K=2^k$, determine if there exist $K$ valuations $v_1,v_2,...,v_K : Y \to {0,1}$ such that $[A(X)] \subseteq \bigcup_{v=v_1,v_2,...,v_K} [B(Y/v,X)]$, i.e. are there K valuations of the variables in Y such that all the valuations that makes $A(X)$ true are covered by valuations that makes $B(Y/v,X)$ true.
So this can be seen as a succinct encoding of the set cover problem using CNF formulas. My guess is that this result should be a consequence of the NP completness of set cover and some general results about succinct encodings of problems using CNF formulas. Unfortunately, I was not able to locate such a result in the literature...

As I suspected in my question, they are useful results in the literature that can be exploited to characterize the complexity of the problem. There is a reduction from the dominant set problem for graphs succinctly defined using CNF formulas to the problem that I have described. The dominant set problem is known to be NExpTime complete [1] for graph succinctly defined using CNF formulas.
An instance of DominantSet^{2^n}{CNF} is defined by an CNF formula E(X,Y) over X={x_1,x_2,…,x_n} and Y={y1,y2,…,y_n}, two sets of n Boolean variables, and an integer K (encoded in binary) . The formula E(X,Y) succinctly defines the following graph: the set of vertices is the set of all Boolean valuations over n variables: 2^n, so any valuation v for the set of variables X, or for the set of variables Y, defines a vertex. Let v_1 and v_2 be two such valuations, then there is an edge={v_1,v_2} in the graph iff E(v_1,v_2) is true or E(v_2,v_1) is true.  An instance is positive, if there exists a set of K valuations V={v_1,v_2,…,v_K} such that \cup{v \in V} { v’ | E(v,v’) \lor E(v’,v) }=2^n (i.e. all vertices are adjacent to a vertex in V).
We can reduce in polynomial time this problem to our succinct set cover problem as follows:
Define (U) to be the empty CNF formula over the set of n variables U (which is equivalent to true) and so [A(U)]=2^n. Then define B(Z,U) to be the CNF equivalent to E(Z,U) \lor E(U,Z). This last formula has a size which is polynomial in the size of the CNF E that defines the graph. Keep K unchanged.
Then it is direct to see that the instance of succinct set cover is positive iff the DominantSet instance is positive. Indeed, there is a set V of K valuations for the variables in Z such that \bigcup_{v \in V} { v' | B(v,v') } covers 2^n iff V is a dominant set.
[1] Patrick Schafenacker. Problems on succinctly encoded graphs. PhD dissertation. Universität Ulm 2017.


A few questions about ISWIM I recently read Landin's paper "The Next 700 Programming Languages".  But I was a bit confused by ISWIM.  In particular, are functions first-class objects in ISWIM?  It seems not because every function must occur under some name and there is no $\lambda$-like construct in the language to construct an anonymous function.  Landin even explicitly claimed in the first footnote that "a not inappropriate title would have been Church without lambda".  Anybody knows the reason behind this choice?  Is ISWIM less expressive than a language with $\lambda$?

The wikipedia page for ISWIM says that it is a higher-order language, and that ISWIM is syntactic sugar for the $\lambda$-calculus.

Although it seems to have no explicit $\lambda$ construct, thereby making it impossible to have anonymous functions, one achieves the same expressive power by combining lexical scoping and first-class functions: Define a new name  for a function locally; pass function as value to higher-order function.


An easy case of SAT that is not easy for tree resolution Is there a natural class $C$ of CNF formulas - preferably one that has previously been studied in the literature - with the following properties:

$C$ is an easy case of SAT, like e.g. Horn or 2-CNF, i.e., membership in $C$ can be tested in polynomial time, and formulas $F\in C$ can be tested for satisfiability in polynomial time.
Unsatisfiable formulas $F\in C$ are not known to have short (polynomial size) tree-like resolution refutations. Even better would be: there are unsatisfiable formulas in $C$ for which a super-polynomial lower bound for tree-like resolution is known.
On the other hand, unsatisfiable formulas in $C$ are known to have short proofs in some stronger proof system, e.g. in dag-like resolution or some even stronger system.

$C$ should not be too sparse, i.e., contain many formulas with $n$ variables, for every (or at least for most values of) $n\in \mathbb{N}$. It should also be non-trivial, in the sense of containing satisfiable as well as unsatisfiable formulas.

The following approach to solving an arbitrary CNF formula $F$ should be meaningful: find a partial assignment $\alpha$ s.t. the residual formula $F\alpha$ is in $C$, and then apply the polynomial time algorithm for formulas in $C$ to $F\alpha$. Therefore I would like other answers besides the all-different constraints from the currently accepted answer, as I think it is rare that an arbitrary formula will become an all-different constraint after applying a restriction.

It sounds like you are interested in all-different constraints (and your last sentence is on the right track).  These are non-trivial instances of the pigeonhole principle, where the number of pigeons is not necessarily greater than the number of holes, and in addition some pigeons may be barred from some of the holes.

All-different constraints can be decided by matching in low-order polynomial time.

Jean-Charles Régin, A filtering algorithm for constraints of difference in CSPs, AAAI 1994, 362–367.
D. E. Knuth and A. Raghunathan, The problem of compatible representatives, SIAM J. Discrete Math. 5 422–427, 1992.  doi:10.1137/0405033

When all-different constraints are expressed (using one of several encodings) as SAT instances, then conflict-driven clause learning usually quickly finds a solution if it exists.  However, pure resolution for the PHP has to build a superpolynomially large set of clauses to show that the instance is unsatisfiable.  This bound clearly holds for this more general problem.  On the other hand, recall that Cook's encoding of the PHP allows polynomial-sized extended resolution refutations.

S. A. Cook, A short proof of the pigeon hole principle using extended resolution, SIGACT News 8 28–32, 1976.  doi:10.1145/1008335.1008338

Recent work along these lines is Chapter 5 of Sergi Oliva's thesis, which formed the basis of a paper with Alberto Atserias at CCC 2013.

I expect you are aware of Cook's classic result, so perhaps you meant to restrict the power of the proof system in your third condition?


(perfect fractional) matching in regular hypergraphs I have been looking in general for results on matching for regular hypergraphs that are not uniform, but I could not find any. Papers I found by internet search seem to focus on uniform hypergraphs (sometimes in addition to being regular). The relative scarcity of results on regular hypergraph matching is somewhat puzzling, since uniform and regular hypergraphs are duals of each other and one would expect that matching may have been studied for both kinds.

I would appreciate if someone can point me to any sources. Of most interest to me are necessary and/or sufficient conditions for existence perfect matchings and closed form expressions or bounds for fractional matchings. I am also curious to know explanations (conceptual, historical etc) for the lack of results of this kind for regular hypergraphs.

Edit: A matching is a collection of pairwise disjoint hyperedges; a perfect matching is a matching that covers all vertices.

You are asking many things in the question, and I can only answer part of it:

  necessary and/or sufficient conditions for existence perfect matchings

It is unlikely that a nice necessary and sufficient characterization is known, because deciding whether a given 3-regular hypergraph has a perfect matching or not is NP-complete.  Indeed, it is equivalent to the monotone 1-in-3 SAT problem, which is proved to be NP-complete by Schaefer [Sch78].  (In [Sch78], the same problem is called “ONE-IN-THREE SATISFIABILITY” without the word “monotone.”)  To see this equivalence, interpret each hyperedge as a variable and each vertex as a clause.

[Sch78] Thomas J. Schaefer.  The complexity of satisfiability problems.  In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pp. 216–226, May 1978.  DOI: 10.1145/800133.804350.


What, in simple terms, are the restrictions imposed by Elementary Affine Logic? The answer to my last question on the subject made several insightful points on how EAL could be used as the basis of a practical programming language, which, in turn, could be evaluated using the abstract part of Lamping's algorithm. I understand most of the practical remarks and they match my experimentation. I don't, though, understand, in a precise manner, the restrictions that I must follow in order to ensure my terms are EAL-typeable.

Those are the typing rules for EAL*, as presented here:

I have a vague understanding of what this is saying. I do understand functions can only be applied on terms without !s, and I understand there is a rule to introduce and remove those !s, but I don't fully grasp it. What, exactly, are the restrictions imposed by EAL? What means for a term to be "stratified"? What are those "boxes" about? I'd highly appreciate (non-PHD) resources to catch up with the understanding I'm missing here.

The terms "stratification" and "boxes" come from proof nets.  Elementary linear logic ($\mathbf{ELL}$) was originally introduced by Girard as a variant of light linear logic ($\mathbf{LLL}$) and its execution was formulated in terms of proof nets.  It is on proof nets that the elementary bound is satified, i.e., every $\mathbf{ELL}$ proof net $\pi$ may be reduced to its cut-free form in a number of steps bounded by
$$\left.2^{\vdots^{2^s}}\right\}d$$
where $s$ and $d$ are the size and the depth of $\pi$ (maybe the height of the tower is not exactly $d$, it is linear in $d$ I guess).

The size of a proof net is similar to the size of a $\lambda$-term.  The depth, on the other hand, is the maximum number of nested boxes in $\pi$. A box is basically a sub-proof net which may be duplicated or erased: remember that in linear logic there is no free contraction or weakening, which means that proofs in general may not be duplicated or erased; those that can must be marked with a special construct, called box.

Stratification refers precisely to the depth.  It is an informal word that people in the linear logic community use to describe the restricted cut-elimination dynamics that is typical of systems like $\mathbf{ELL}$.  In full linear logic proof nets, cut-elimination may completely alter the depth: if $\pi\to\pi'$ by means of a cut-elimination step and $a$ is a node of $\pi$ at depth $i$ which has a residue $a'$ in $\pi'$, the depth of $a'$ may be anything between $0$ ($a$ is "pulled out" of all boxes) and $2d$, where $d$ is the depth of $\pi$ ($a$ is at maximal depth and it "enters" inside a box which is also at maximal depth).  On the contrary, $\mathbf{ELL}$ proof nets, because of the structural constraints that define them, have the remarkable property that the depth is invariant under cut-elimination: in the above case, the depth of $a'$ is exactly $i$.  This stratification property is essential in proving the complexity bounds of light logics (elementary for $\mathbf{ELL}$ and polynomial for $\mathbf{LLL}$).

From the point of view of Lamping's algorithm, the depth corresponds to the integer label of fan nodes.  Stratification means that a sharing graph corresponding to an $\mathbf{ELL}$ proof net will need no brackets and croissants to be evaluated, because the labels of fan nodes do not change.

After Girard, people started applying the principles of light and elementary linear logic to define type systems for usual $\lambda$-terms (instead of proof nets) which would ensure interesting normalization properties.  The paper you mention falls in this line of work, which explains the terminology they use.  Informally, typing a simply-typed $\lambda$-term amounts to decorating it with "boxes", which is what their so-called pseudo-terms are for.

For the rest, $EAL^\star$ is just like any other non-trivial type system for $\lambda$-terms: there is no simple description of what a typable term looks like; the shortest description is its type derivation!


Redundancy and Structure of computational problems It is widely believed that some computational problems such as graph isomorphism can not be NP-complete because it does not possess enough structure or redundancy to be computationally hard (NP-hard). I'm interested in the different formal notions for structure of computational problems and redundancy measures.

What are the major results known about such formal notions for computational problems? A recent survey  of such notions would be very nice.

EDIT: Posted on MathOverflow

Actually, I think that the phenomenon here is that GI in some sense has too much structure. It is in some ways the group-theoretic nature of its witnesses which leads to the $\mathsf{coAM}$ algorithm for GI and is one of the pieces of technical evidence why people believe GI is not $\mathsf{NP}$-complete. My thinking here is that there is so much structure that the problem is "too rigid" to encode arbitrary $\mathsf{NP}$ problems.

Another way to capture this is the fact that the counting and decision versions of GI are equivalent, whereas for all known $\mathsf{NP}$-complete problems this is not the case unless the polynomial hierarchy collapses. This can also be viewed as capturing some aspect of structure/redundancy: for unstructured, general problems, counting solutions seems to be much harder than telling if one exists, whereas the extensive structure of GI allows one to show that counting and decision are equivalent.

(On the other hand, group isomorphism seems even more structured than GI, yet no counting-to-decision reduction is known for group iso. Perhaps this says that GI is in sort of a "just right" level of structure - too structured to be NP-complete, but unstructured enough to allow a counting-to-decision reduction.)


Reference request: pi-calculus with simultaneous events I am interested in using the $\pi$-calculus as a basis for modeling workflows, and came up with an extension that proved useful in my modeling, namely the ability to specify that two or more channel communications should take place simultaneously. I can only imagine that a similar extension has been treated before, but I just cannot find it mentioned anywhere, most likely because I don't know what to search for.
I will describe the basic idea with a simplified variant of the calculus with only signal/query events (i.e. no passing of names over channels) but extended with a simultaneous events:
\begin{align}
\mathsf{Action}\quad \alpha ::={}&
   a && \text{query}
   \\
   {}\mid{} & \overline{a} && \text{signal}
   \\
   {}\mid{} & \alpha_1\& \alpha_2 && \text{simultaneous composition}
   \\
   {}\mid{} & \tau && \text{silent}
   \\
   \\
\mathsf{Sum}\quad S ::={}&
   \alpha.P && \text{prefix}
   \\
   {}\mid{}& S_1 + S_2 && \text{choice}
   \\
   {}\mid{}& 0 && \text{inert process}
  \\\\
\mathsf{Process}\quad P ::={}&
  P_1 \mid P_2 && \text{composition} \\
  {}\mid{}& \nu a\ldotp P && \text{new channel} \\
  {}\mid{}& !P && \text{replication} \\
  {}\mid{}& S && \text{synchronization}
\end{align}
We define the usual congruence relation $\equiv$ with scope extrusion on processes, and such that processes with composition forms a commutative monoid with neutral element $0$, and such that sums with choice form a commutative monoid also with neutral element $0$. Furthermore, actions with simultaneous also form a commutative monoid with neutral element $\tau$, and furthermore the submonoid generated by channel names $a$ has a group structure with $a^{-1} = \overline{a}$. For example, $a \& b \& \overline{a} \equiv b$.
The operational semantics has communication rule
\begin{align}
\frac{P \stackrel{\alpha_1}{\to} P' \quad Q \stackrel{\alpha_2}{\to} Q'}{P \mid Q \stackrel{\alpha_1 \& \alpha_2}{\to} P' \mid Q'}
\end{align}
and scoping rule
\begin{align}
\frac{P \stackrel{\alpha}{\to} P'}{\nu a\ldotp P \stackrel{\alpha}{\to} \nu a\ldotp P'}(\text{$a \not\in \alpha$})
\end{align}
The group structure on actions ensure that matching queries and signals cancel each other out. For example:
\begin{align}
  a\&\overline{b}\ldotp P \mid b\ldotp Q \mid c\&\overline{a}\ldotp R \stackrel{c}{\to} P\mid Q \mid R
\end{align}
But also:
\begin{align}
  a\&\overline{b}\ldotp P \mid b\ldotp Q \mid c\&\overline{a}\ldotp R \stackrel{a}{\to} P\mid Q \mid c\&\overline{a}\ldotp R
\end{align}

Milner defines the SCCS calculus in [1]. This is a generalization of CCS where the actions form an abelian group, and where the communication rule is defined as in my question.
[1] Milner, R. Calculi for synchrony and asynchrony. 1983. https://www.sciencedirect.com/science/article/pii/0304397583901147


Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis? As an undergraduate with limited understanding of QC and even the C-T thesis, I have problems figuring out why in questions such as Extended Church-Turing Thesis real-life quantum stuff is even given the time of day, because it's not relevant is it?
I have always thought of the C-T thesis as a statement, specifically a statement in theoretical computer science. A statement that reads, "There exists no computation model capable of recognising languages that a Turing Machine cannot". Even that is a bit messy for me. Is there a formal definition for a computation model? Finite alphabet, finite states, what exactly are we talking about here?
Whether provable or not is another story, but it's a statement that evaluates to some logical value or another. Some people say that the C-T is a statement, some actually say it's not. I have no authority in this, so I'm left as confused as ever.
And if it's not a statement, then great! It's not a problem anymore. At least from the mathematical side of things.
I have a couple of what I think are misconceptions. I've taken a look at the Chomsky Hierarchy of grammars, and at the very top lie all the so called Unrestricted Grammars which have been proven to be equally expressive as Turing Machines, apparently. Now I don't even know the formal definition for expressivity, all I have is an intuitive understanding. CFGs are more "expressive" than DFAs and CSGs are more "expressive" than CFGs etc etc, because they can recognise all the languages the prior construction can and more. Is this actually the commonly accepted definition?
Now Unrestricted Grammars specifically, allow production rules of the form $\alpha \to \beta$ where $\alpha$ is any non-empty string and $\beta$ is any string. Hence, unrestricted. How on earth could a computational model compete with something that is literally unrestricted? It makes me think of the C-T thesis as trivial, "of course" it's true.
This left me even more confused: What would it mean to disprove Church-Turing thesis?
The accepted answer to this question starts off with:

The Church-Turing thesis has been proved for all practical purposes.

Why is practicality suddenly worth anything in theoretical computer science?
Are there like two interpretations or more of the C-T thesis, one for "practical purposes" and one for "mathematics"?

I've written the following to talk about the connections between quantum computation and the (extended) Church-Turing thesis. Your question appears to have several other questions, which I don't address due to space (and time to write down this answer).

A statement that reads, "There exists no "reasonable" computational model capable of recognizing languages that a Turing Machine cannot"

This is essentially what the Church-Turing thesis states. It is not the extended Church-Turing thesis, which roughly takes the form:

All "reasonable" computational models can simulate each other with polynomial overhead

Of course, what "reasonable" means must itself be pinned down. For example, if you let $\mathsf{Halt}$ be an oracle to the halting problem, then the computational model $\mathsf{TM}^{\mathsf{Halt}}$ of Turing Machines equipped with halting oracles can compute strictly more than that than that of simply Turing machines.
So if $\mathsf{TM}^{\mathsf{Halt}}$ is viewed as "reasonable", then the CT thesis is already false.
For this reason, "reasonable" is usually phrased as "hypothetically realizable in the real world". As there is no proposed mechanism to create a universal $\mathsf{TM}^{\mathsf{Halt}}$ machine in the real world, this computational model would not be considered "reasonable".
What does this mean for the extended CT thesis, and quantum computation? The complexity class $\mathsf{BQP}$ is the class of problems solvable (with bounded error) by a quantum computer efficiently. You should view it as a quantum analogue of $\mathsf{P}$ (more properly of $\mathsf{BPP}$, or "two-sided error, randomized $\mathsf{P}$", but still).
If quantum computers (which can compute arbitrary problems in $\mathsf{BQP}$) are physically realizable, the extended Church-Turing thesis posits that they can only get a polynomial speedup over "traditional" models of computation. If this is the case, the extended Church-Turing thesis still holds, and quantum computing is in a certain sense "more boring".
Preliminary evidence suggests that this is not the case though. There are a variety of problems which are known to have exponential speedups on quantum computers, famously factorization and the discrete logarithm problem via Shor's algorithm.
While these are large "practical" reasons for investigating quantum computation, they are actually not the theoretically most compelling reason.
Both factorization and discrete log are in $\mathsf{NP}\cap\mathsf{coNP}$, and therefore unlikely to be $\mathsf{NP}$-hard unless the polynomial hierarchy collapses.
This means that "Shor's algorithm leads to an exponential speedup for factoring and discrete log" isn't super interesting from a complexity theory point of view, as it's entirely consistent with current thoughts that both of these problems are actually in $\mathsf{P}$ (or $\mathsf{BPP}$).
There are problems which are more interesting to consider though.
In particular, the Boson sampling line of work posits a particular problem which is $\#\mathsf{P}$-hard, but is in $\mathsf{BQP}$.
This means that this particular problem is highly unlikely to be in $\mathsf{P}$, as this would collapse the polynomial hierarchy to the third level, which is thought to be unlikely by complexity theorists.
So the reason that people bring quantum computing up when discussing the (extended) Church-Turing thesis is that, if sufficiently "physically realized", it provides exponential speedups on practically important problems (factoring and discrete logarithm), as well as an exponential speedup on a problem which is "harder than $\mathsf{NP}$-complete". This would constitute a violation of the extended Church-Turing thesis.


Semantics of concurrent languages I've seen that the preferred way to specify the semantics of a concurrent language is to use a process calculus (e.g. pi calculus, join calculus). But in the paper presenting the F# asynchronous programming model the authors have a different approach: they first perform a CPS conversion to a core language, and then, define the semantics in terms of a transition system in which states are tuples of the form (A, Q, P), where A is the set of active computations, Q is the set of queued computations, and P is the set of pending computations--i.e. Waiting for an event. Each computation is of the form e@ctx, where ctx is a label corresponding to a synchronization context. Finally, they give transition rules for reduction (which uses the reduction rule of the core language), suspension of computations waiting on events, activation of computations (i.e. moving computations from Q to A), and event signaling.

I was wondering if this is an acceptable (i.e. accurate enough) way of specifying the semantics of a concurrent language.

EDIT: can anyone point me to papers that use a similar approach to the one taken in the F# paper?

Thanks.

Legally speaking, the term "calculus" is almost always used to describe a language, i.e., a piece of syntax, with added rules of calculation or reasoning.  Examples include the good old predicate calculus, lambda calculus, process calculi, various type theories and logics (e.g., Martin-Lof type theory and linear logic).  From a programming language point of view, a "calculus" is just a bare bones programming language, that we take to be fundamental in some way.

People with an engineering bent of mind often take calculi to be good enough for using as a foundation, and describe the "semantics" of other languages in terms of such calculi.  (Prominent examples of such people include Christopher Strachey, Robin Milner, and Tony Hoare to some extent.)  People with a logical/philosophical bent of mind regard such calculi as being inadequate on their own, and needing a proper "semantics".  (Prominent examples include Dana Scott, Gordon Plotkin, John Reynolds and again Tony Hoare to some extent.)  A true "semantics" then is expressed in terms of abstract concepts, rather than pieces of syntax.

From this point of view, the F# paper that you cite is doing the right thing by describing the semantics in terms of concepts.  It is indeed the preferred way of describing the semantics of programming languages (at least for those of us with a logical bent of mind).

[Additional note: See also the previous question What constitutes denotational semantics for related discussion, even though it is dealing with denotational rather than operational semantics.]


Multiplication of circulant matrices with a diagonal matrix Let $A_{i}$, $B_{i}$ be a sequence of circulant matrices of size $n \times n$.
We know that $\sum_{i=1}^{n}A_{i}B_{i}$ can be calculated in quadratic time (use FFT to diagonalize and add the diagonal matrices and apply IFFT).
Supposing $D$ is an arbitrary diagonal matrix (for simplicity, let $r$ be $n$th root of unity and consider the diagonal elements as all distinct powers less than $n$ of $r$).
What is the complexity of $\sum_{i=1}^{n}A_{i}DB_{i}$? I suspect it to be quadratic since I am including the same diagonal matrix($O(n)$ terms) in each term.
Consider $R$ a circulant matrix of size $n \times n$ with first row made of distinct powers less than $n$ of $r$. Let $X_{i}$ and $Y_{i}$ for $i=1\rightarrow n$ be full-rank diagonal matrices.
What is the complexity of $\sum_{i=1}^{n}X_{i}RY_{i}$? Again I suspect this to be quadratic.
The matrices $D$ and $R$ that are defined with respect to $r$ is artificial. I am looking for the case of general diagonal $D$ and general full-rank circulant $R$.

This problem is essentially equivalent to matrix multiplication. Let's look at $\sum_{i=1}^{n}X_{i}RY_{i}$ first, where $X_i$ and $Y_i$ are diagonal matrices. If $A$ is the matrix with the diagonal entries of $X_i$ as the $i$-th column, and $B$ is the matrix with the diagonal entires of $Y_i$ as the $i$-th row, then the entry-wise product of $AB$ and $R$ is equal to $\sum_{i=1}^{n}X_{i}RY_{i}$. If all entries of $R$ are non-zero (even if it should not be full rank), then $AB$ can be reconstructed from $\sum_{i=1}^{n}X_{i}RY_{i}$. Hence the computational complexity of this problem is identical to the computational complexity of matrix multiplication.

For the case $\sum_{i=1}^{n}A_{i}DB_{i}$, where $A_i$ and $B_i$ are circulant matrices, we first have to apply FFT to $A_i$, $B_i$ and $D$, to get back to the case $\sum_{i=1}^{n}X_{i}RY_{i}$. We need $2n+1$ FFTs of size $n$ for this, so this adds $n^2\log n$ to the complexity.
Also in this case, it can happen that the FFT of $D$ has only very few non-zero entries. In this special case, the complexity will be quadratic times the number of non-zero entries. This can happen, if the i-th entry on the diagonal of $D$ is $r^i$, where $r$ is the $n$th root of unity. But already when $D$ has the same entries but permuted arbitrarily, the FFT of $D$ will not be sparse (in general).


Ruzzo-Simon-Tompa oracle access mechanism In a paper on relativizing logspace computations, Ladner and Lynch construct an oracle relative to which $\mathsf{NL} \nsubseteq \mathsf{P}$. There are some
more pathological examples in this vein in the literature. I have been reading some papers on relativized small space classes, and one of the primary tools in this area is the Ruzzo-Simon-Tompa(RST) oracle access mechanism which demands that a non-deterministic space-bounded turing machine act deterministically while making queries to the oracle.

Now consider circuit families with oracle gates - say, $A^B$, where $A$ is a circuit complexity class containing logspace with oracle access to another class $B$, via oracle gates appended to the basis of $A$. Are there any pathological examples similar in spirit to the Ladner-Lynch paper, known for such classes? What would be a RST-like restriction necessary for such classes?
In case there are indeed such examples, am I right in guessing that a RST analogue would be to insist that $A$ be a logspace-uniform circuit family?

A definition of oracle access that works for small circuit complexity classes (the $AC^k$ and $NC^k$ hierarchies) as well as for logarithmic space classes, with the property that all known inclusions relativize, can be found in this paper:

Klaus Aehlig, Stephen Cook and Phuong Nguyen: Relativizing Small Complexity Classes and their Theories, CSL 2007, Springer LNCS 4646


Complexity of matrix powering Let $M$ be a square integer matrix, and let $n$ be a positive integer. I am interested in the complexity of the following decision problem:

Is the top-right entry of $M^n$ positive?

Note that the obvious approach of iterated squaring (or any other explicit calculation) requires us to potentially handle integers of doubly exponential magnitude, i.e., having exponentially many bits. However the problem is easily seen to be in Allender et al.'s "PosSLP" class ("On the Complexity of Numerical Analysis", SIAM J. Comput. 38(5)), and therefore in the fourth level of the counting hierarchy.

1) Is it possible to place this matrix powering problem in a lower complexity class?

2) If not, could it conceivably be PosSLP-hard?

3) I am especially interested in the matrix powering problem for low-dimensional matrices, i.e. up to and including 6x6 matrices. Might the complexity be lower for such matrices?

For matrices of sizes $k = 2,3$ the Matrix Powering Positivity Problem is in $\mathsf{P}$ (cf. this paper to appear in STACS 2015)


Properties about verticies in Delaunay Triangulations I'm working on my thesis dealing with pathfinding over Delaunay triangulations. I have an algorithm that has running time in time proportional to the degree of a vertex. Are there any properties or upper bounds on the degree of vertices in a Delaunay (or Constrained Delaunay) triangulation?

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


Algorithm to transform an arbitrary MIP problem into the corresponding formulation for PSO Is there an algorithm to transform an arbitrary Mixed Integer Programming problem into the corresponding formulation for Particle Swarm Optimization? I have found some information related to the use of penalty functions to avoid violation of constraints, but not a well defined procedure to convert the objective function and each of the constraints as required for a PSO solution.

Ok, I have found how to do this by reading Introduction to Mathematical Optimization: From Linear Programming to Metaheuristics. Chapters 7 and 10 clearly explain the possibilities, essentially the penalty method and the use of Lagrange multipliers coupled with Kuhn-Tucker conditions if necessary.


Is there any link between TCS and Sustainable Energy research? Does anybody know of any work that links Theoretical Computer Science and Cheap/Sustainable Energy? i.e is there any work in TCS with the application being in Cheap/Sustainable Energy.

Kirk Pruhs is a leader in the area of "green computing", the study of algorithms that treat energy as an expensive resource. Take a look at these slides and  this survey by Sandy Irani and Pruhs.


Which areas of TCS are better for a math bachelor? I am graduating from mathemetics bachelor program and I've been accepted for masters degree in mathematics. But I am not sure to pursue math, hence I am looking for other field I can do research. I am going to study potenial theory in the masters degree in math so I am good at analysis, particularly in measure theory. I also took some statistics courses, java and matlab. Moreover, I really like computers so I educated myself on some other stuff(I do some game modding and photoshop)

Some friends of mine suggested machine learning but they are undergrad and they don't really know the subject well. So my question is what fields/areas of computer science I can work on for PhD and what should I learn.

Or in this respect can I work on CS(Phd) as a math grad?

(I've read the similar questions but they are only similar. So I appreciate any help.)

Edit: In Math M.S program I only have one none-technical elective and I will get some undergrad CS lectures(additional). So, as @RB suggested, I am asking for the areas that require realtively less CS and more math. But note that I am willing to study/work hard.

It had been argued that Theoretical Computer Science is a branch of mathematics, so it seems to me that any answer to this question would necessarily be primarily opinion-based. That said, in your place (and this is an uninformed opinion) I would steer clear of subfields in which a tremendous volume of technical work has been done, and in which coding plays a greater role. The barrier to entry in such subfields will be quite high for a math major. So for example, I would be cautious of anything related to computer vision and speech recognition. I would also be cautious of subfields in which the objective is perhaps a bit fuzzy, such as AI and machine learning. More controversially, I think that perhaps you should steer clear of quantum computation for this reason.

Conversely, subfields in which the objective is well-defined and in which coding plays a lesser role have a lower entry barrier for a math major. For example, complexity theory, graph algorithms, information theory (perhaps especially for you!), concurrency, cryptography, and maybe even things like clustering and compressed sensing.


Clique Enumeration Algorithm I am reading an old paper of M.C. Golumbic about EPT (edge intersection of paths in a tree) graphs. In the paper it is shown that the number of maximal cliques of an EPT graph instance is polynomial. It concludes that if an oracle reports that a graph $G$ is an EPT graph, then  it is possible to find the maximum clique with a standard clique enumeration algorithm.

First of all, what are these standard clique enumeration algorithms? If there are more than one, can we say that if the number of maximal cliques of a graph is polynomial then can we use any of these enumeration algorithms? Or should we derive a special algorithm from a generic algorithm which uses some special structures of the graph class?

Thanks in advance.

There are several output-sensitive algorithms to enumerate all maximal cliques in polynomial time per output.  One of the earliest algorithms was developed by Tsukiyama, Ide, Ariyoshi, and Shirakawa (1977).

Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, Isao Shirakawa: A New Algorithm for Generating All the Maximal Independent Sets. SIAM J. Comput. 6(3): 505-517 (1977)

This means that if you know your graph has at most polynomially many maximal cliques, then the total running time of their algorithm will be polynomial in the input size.


How is duality of types defined? In Wadler's Recursive Types for Free! [1], he demonstrated two types, $\forall X . (F(X) \rightarrow X) \rightarrow X$ and $\exists X . (X \rightarrow F(X)) \times X$, and claimed they are dual.  In particular, he pointed out that the type $\exists X . X \rightarrow (X \rightarrow F(X))$ is not the dual of the former.  It seems the duality in question here is different from De Morgan duality in logic.  I wonder how the duality of types is defined, specfically for the three types mentioned, why the second is dual of the first while the third is not.  Thanks.

[1] http://homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt

In this context the duality refers to taking the least fixed point in one case and the greatest fixed point in the other. We should try to understand in what sense $L = \forall X . (F(X) \to X) \to X$ and $G = \exists X . (X \to F(X)) \times X$ are the "least" and "greatest" solutions of recursive equation $F(X) \cong X$.

First of all, $L$ and $G$ are indeed fixed points (under certain technical assumptions which restrict the nature of $F$) because the comparison maps $v : F(L) \to L$ and $w : G \to F(G)$ given by
$$v \, x \, X \, g = g \, (F (\lambda h : L \,.\, h \,X\, g)\, x)$$
and
$$w (X, (f, x)) = F (\lambda y : X \,.\, (X, (f, y))) \, (f x)$$
are isomorphisms. Notice that we used the fact that $F$ is a functor, i.e., it is monotone, when we applied it to functions.

Suppose $Y$ is any solution to $F(Y) \cong Y$ with a mediating isomorphism $u : F(Y) \to Y$. Then we have canonical maps $$\alpha : L \to Y \text{  and } \beta : Y\to G$$ defined by
$$\alpha \, f = f\, Y\, u$$
and
$$\beta \, y = (Y, (u^{-1}, y)).$$
Therefore, $L$ is least because we can map from it to any other solution, and $G$ is greatest because we can map from any other solution to it. We could make all this more precise by talking about initial algebras and final coalgebras, but I want my answer to be short and sweet, and cody explained the algebras anyhow.

In practice the least solutions are eager datatypes and the greatest solutions are lazy datatypes. For example, if $F(X) = 1 + A \times X$ then in the first case we get finite lists of $A$'s and in the second finite and infinite lists of $A$'s.


Multiplication of normal distributions Suppose X_1, ..., X_k are iid standard Gaussian variables, for some k > 1.

Then, what is the distribution of X := X_1 * ... * X_k ? Can it be approximated by a Gaussian, maybe for large k ?

The distribution of the multiplication of independent Gaussians is not close to a Gaussian.

There are various ways to convince yourself in this. E.g., compute the expectation and the variance of the product from the expectation and the variance of the individual variables.
This gives you a candidate Gaussian if there were a Gaussian approximation.
Now, think of some simple properties of the product (e.g., the probability it is 0) and see if your candidate is good enough as an approximation.


Why lower bounds for boolean Circuits does not imply arithmetic circuits lower bounds My question is why lower bounds for depth 3 Boolean circuits with gates "and" and "xor" for determinant does not imply the same lower bounds for arithmetic circuits over $\mathbb{Z}$?

What is wrong with the following argument: Let $C$ be an arithmetic circuit calculating determinant then by taking all variables mod 2 we will get Boolean circuit calculating determinant.

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.


On optimality of Grover algorithm with high success probability It is well-known that bounded error quantum query complexity of the function $OR(x_1,x_2,\ldots, x_n)$ is $\Theta(\sqrt{n})$. Now the question is what if we want our quantum algorithm to succeed for every input with probability $1-\epsilon$ rather than the usual $2/3$. Now in terms of $\epsilon$ what would be the appropriate upper and lower bounds?

It is immediate that $O(\sqrt{n} \log(1/\epsilon))$ queries suffices for this task by repeating the Grover algorithm. But from what I recall this is not at all optimal as even plain Grover algorithm if run carefully, i.e. for appropriate number of iterations, can achieve something like $\epsilon=O(1/n)$ with just $O(\sqrt{n})$ iterations. And hence using that one can get an improvement for all $\epsilon$'s. On the other hand, I don't expect that $\Omega(\sqrt{n})$ be the right answer for very small $\epsilon$'s.

But I am interested to see what one can show in terms of $\epsilon$-dependent upper and lower bounds for different ranges of $\epsilon$ especially when $\epsilon$ is very small say $\epsilon= \exp(-\Omega(n))$ or $\epsilon=1/n^k$ for large $k$'s.

(To give some context, the general phenomenon I am getting at is the amplification in context of quantum query complexity. )

For the sake of completeness, here's an answer.

Let $Q_\epsilon(f)$ denote the $\epsilon$-error quantum query complexity of computing a function $f$ and $\mathsf{OR}_n$ be the OR function on $n$ bits, defined as $\mathsf{OR}_n(x_1,\ldots,x_n)=\bigvee_{i=1}^n x_i$. (Note that this is different from the problem where you are promised that the input has exactly one 1 and the objective is to find that 1. That problem can be solved with no error in $\Theta(\sqrt{n})$ queries.)

Then we have for all $\epsilon \in [2^{-n},1/3]$,

  $Q_\epsilon(\mathsf{OR}_n) = \Theta(\sqrt{n\log(1/\epsilon)})$.

This follows from Bounds for Small-Error and Zero-Error Quantum Algorithms.

In fact, we know something more general. For all symmetric functions $f$, which are functions that only depend on the Hamming weight of the input, we have that for all $\epsilon \in [2^{-n},1/3]$,

  $Q_\epsilon(f) = \Theta(Q_{1/3}(f)+\sqrt{n\log(1/\epsilon)})$.

This was shown in A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions.


CTL and LTL logic difference I am trying to understand these subtle differences between LTL and CTL logic and one thing I simply don't have an idea how to understand.

Formula

AG AF p

in CTL and a formula

GF p

in LTL. Why aren't they equivalent? Can you give me an example, please? I tried finding and drawing things, but I simply can't find a counter example and there is no explanation in the lecture materials I have.

There are already some rather good related answers regarding LTL versus CTL. In a nutshell, LTL is first and foremost a logic of traces, and an LTL formula is true for a transition system $S$ if and only if it is true for each trace of $S$. CTL, on the other hand, is a branching-time logic, which can in a sense talk about multiple paths at the same time.

One standard example here (not the one you give, about which more below) is a labelled transition system $S=(Q,T,q_0,L)$ with set of locations $Q=\{q_0,q_1,q_2\}$, set of transitions $T=\{(q_0,q_0),(q_0,q_1),(q_1,q_2),(q_2,q_2)\}$, and labelling given by $L(q_0)=L(q_2)=\{p\}$, $L(q_1)=\emptyset$. This system satisfies $FGp$, but not $AFAGp$, which can be seen as follows.

$FGp$ means that for every path $\pi=s_1,s_2,\dots$ in a given system, there is some point after which $p$ is always satisfied, i.e. there is some $i$ such that for all $j\geq i$, $p\in L(s_i)$. This is satisfied by $S$ since every path in $S$ either remains in $q_0$ forever (such that $p$ is always satisfied) or eventually gets to $p_2$ (after which $p$ is always satisfied).

On the other hand, $AFAGp$ means that every path $\pi=s_1,s_2,\dots$ eventually reaches a state satisfying $AGp$, i.e. a state such that on every path $\pi'$ starting there, $p$ is always satisfied. Formally, this means that there is an $i$ such that for all $\pi'=s_1',s_2',\dots$ with $s_1'=s_i$ and all $j$, we have $p\in L(s_j')$. But in $S$, for the path which always remains in $q_0$, the transition to $q_1$, where $p$ is not satisfied, is always available, so that at no point of that path $AGp$ holds; therefore $AFAGp$ is not satisfied by $S$.

As for your example, this is actually a case where two formulas are equivalent. This does happen. The proof is a little involved, but I can add it if you are interested.


Defining primitive recursive functions over general data types The primitive recursive functions are defined over the natural numbers. However, it seems as if the concept should generalise to other data types, allowing one to talk about primitive recursive functions that map lists to binary trees, for example. By analogy, partial recursive functions over the natural numbers generalise nicely to computable functions on any data type, and I'd like to understand how to make the same kind of generalisation for primitive recursive functions.

Intuitively, if I were to define a simple imperative language that allowed basic operations on, say lists (such as concatenation, taking the head and tail, comparison of elements) and a form of iteration that requires knowing in advance how many iterations will occur (such as iterating over the elements in an immutable list), then such a language should at most be able to compute the primitive recursive functions over lists. But how can I understand this formally, and more specifically, how would I go about proving that my language computes all primitive recursive functions over lists and not just a subset of them?

To be clear, I'm interested in understanding primitive recursive functions as a well-defined class of functions (if indeed they are), rather than just in the operation of primitive recursion itself, which seems straightforward. I'd be interested in pointers to anything that's been written on primitive recursion over general data structures, or indeed in any context other than the natural numbers.

update: I may have found an answer, in a paper called Walther Recursion, by McAllester and Arkoudas. (Proceedings of CADE 1996.) This seems to contain a generalised version of primitive recursion as well as the more powerful Walther recursion. I intend to write a self-answer once I've digested this, but in the meantime this note might be helpful to others with the same question.

In general, in a language with datatypes (like lists, trees, etc) it's easy to describe a language of functions which behave exactly like we expect primitive recursion to behave.

For example if the datatype is $D$, and the constructors $c_1,\ldots, c_n$ have type

$$ c_i : T_1^i\rightarrow T_2^i\rightarrow \ldots\rightarrow T_{k_1}^i\rightarrow D\rightarrow\ldots\rightarrow D$$

then the recursor $\mathrm{rec}_D^O$ for output type $O$ will have type

$$\mathrm{rec}^O_D:(T_1^1\rightarrow\ldots T^1_{k_1}\rightarrow D\rightarrow \ldots\rightarrow D\rightarrow O\rightarrow \ldots\rightarrow O)\rightarrow\ldots\rightarrow D\rightarrow O$$

and the operational semantics will be:

$$\mathrm{rec}^O_D\ f_1\ \ldots\ f_n\ (c_i\ t_1\ldots t_{k_i}\ d_1\ldots d_m)\rightarrow\\ f_i\ t_1\ldots t_{k_i}\ (\mathrm{rec}^O_D\ f_1\ldots\ f_n\ d_1)\ldots (\mathrm{rec}^O_D\ f_1\ldots f_n\ d_m) $$

for each $i$.

Something of a mouth-full! At least for natural numbers, we indeed get
$$\mathrm{rec}_{\mathbb{N}}^O:(\mathbb{N}\rightarrow O\rightarrow O)\rightarrow O\rightarrow\mathbb{N}\rightarrow O $$

$$\mathrm{rec}^O_{\mathbb{N}}\ f_0\ f_1\ 0 \rightarrow f_1\ 0$$
and
$$\mathrm{rec}^O_{\mathbb{N}}\ f_0\ f_1\ (S\ n)\rightarrow f_0\ n\ (\mathrm{rec}^O_{\mathbb{N}}\ f_0\ f_1\ n)$$

as hoped for (note that the zero constructor has zero arguments!).

If now we allow for constant functions and projections, and allow arbitrary uses of $\mathrm{rec}^O_D$ for non-function types $O$, then you have exactly primitive recursion.

Reassuringly, if all the $T^j_i$s are non-functional as well, then the usual Gödel encoding of the datatype gives the same primitive recursive functions.

It would be nice to have a more elegant description of this process though. That's were Carlos' answer comes in: these datatypes can be described more elegantly in category theory as the initial algebras of certain functors, often called polynomial functors. The recursor is then just (a variant of) the initial morphism of this algebra, sometimes called a catamorphism by people trying to confuse things. This morphism exists by construction of the initial algebra.

A paramorphism is just the particular variant I described above.


Finding intersections of numerically implemented 1-dimensional curves on a 2-dimensional plane Question summary: what are the known efficient algorithms to find the intersections of 1-dimensional curves living on a 2-dimensional plane?

Detail: I have a set of 1-dimensional curves on a 2-dimensional plane. Each curve in reality is a set of points connected by straight lines (therefore more like a polygon), and is the numerical solution of a given differential equation. I want to find all the intersection points of the 1-dim curves.

Here are what I tried so far.

Method 1. Use interpolating functions & root finding algorithms.

1.1 For each object C_n, cut it into subobjects C_(n, i) at inflection points of C_n, i.e. at dx/dy = 0 and at dy/dx = 0 when we consider the 2-dim plane as the x-y plane.

1.2 For any two subobjects C_(n, i) and C_(m, j) check if they have a common x- and y-domain. If they have, find interpolating function for each of them, y = f_(n, i)(x) and y = f_(m, j)(x), and find roots of f_(n, i)(x) - f_(m, j)(x) = 0.

Method 2. Use a hash table.

2.1 Consider the 2-dim plane as a hash table, where each element is a square bin of a small size, comparable to the resolution of the 1-dim curves.

2.2 Run along each C_n, and when it hits a bin at (i, j), record the hit in the table with (i, j) as a key and {n} as its element.

2.3 Retrieve keys with more than one element.

A Practical issue with Method 1 is there are many things to consider case-by-case when using interpolation and root-fiding algorithms, especially when there are nearly horizontal/vertical curves and when there are more than one root for a given pair of subobjects.

For Method 2, a big issue is that the physical size of the hash table gets big easily, for example I need about 10GB of RAM to deal with my current research project even at its elementary stage.

I suspect there should be previous studies for similar problems, but my background & research area is theoretical physics and I don't know much about such studies. I tried googling but was not successful so far.

On a side remark, I think that a generalization of this problem, i.e. finding intersections of numerically implemented n-dimensional objects in an m-dimensional space may be quite interesting, and I wonder if there is any previous study about such a problem.

Thank you very much in advance.

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.


Trade off between time and query complexity Working directly with time complexity or circuit lower bounds is scary. Hence, we develop tools like query complexity (or decision-tree complexity) to get a handle on lower bounds. Since each query takes at least one unit step, and computations between queries are counted as free, time complexity is as at least as high as query complexity. However, can we say anything about the separations?

I am curious about work in the classical, or quantum literature, but provide examples from QC since I am more familiar.

Some famous algorithms such as Grover’s search and Shor’s period finding, the time complexity is within poly-logarithmic factors of the query complexity. For others, such as the Hidden Subgroup Problem, we have polynomial query complexity, yet polynomial time algorithms are not known.

Since a gap potentially exists between time and query complexity, it is not clear that an optimal time complexity algorithm has to have the same query complexity as the optimal query complexity algorithm.

  Are there examples of trade-offs between time and query complexity?

Are there problems where the best known time complexity algorithm has a different query complexity than the best known query complexity algorithm? In other words, can we perform more queries to make the between-query operations easier?

Or is there an argument that shows that there is always a version of an asymptotically optimal query algorithm having an implementation with asymptotically best time-complexity?

Here's an attempt at creating an artificial function with the following property:

The problem can be solved with $O(\log n)$ queries, but requires $\exp(n)$ time.
The problem can be solved with $O(n)$ time but that requires $O(n)$ queries

Let the input size be $n + \log n$. Let the first $\log n$ bits (let's call this string x) encode the input to a problem complete for EEXP. The next $n$ bits (let's call this string y) have the property that they are all zero if and only if x is a NO instance of the EEXP-complete problem.

In words, the first $\log n$ bits encode a hard problem, and the next $n$ bits give you a clue about the solution of the problem. However, to figure out the solution by looking at the $n$ bit string you make $\Omega(n)$ queries.

So this problem can be solved by either reading only the first $\log n$ bits and spending exp(n) time or by reading $n$ bits and using only linear time.

The same function goes through for quantum query complexity.. insert square root signs where necessary.


Graph that maximizes minimum hitting time? Let $G$ be some connected bidirectional (or undirected) graph. We define a random walk as a walk that begins at a vertex chosen uniformly at random, and at each step proceeds to one of its current vertex's neighbors uniformly at random. The expected hitting time for a vertex $v$ is the time it takes, on average, for the walk to reach $v$.

For what family of graphs is the minimum of all expected hitting times as large as it can be?

It is well known that a barbell graph (two cliques of size $n/3$ connected by a path of length $n/3$) has average hitting time $\Omega(n^3)$, but I believe the same applies to minimum hitting time (for uniform or stationary distribution). Whatever vertex you choose as the one that you think is easiest to hit, you have constant probability of starting in the far clique from that vertex, after which it will take $\Omega(n^3)$ time in expectation before you traverse the connecting path to your chosen vertex.


Is public-key spread-spectrum communication possible? Alice wants to get a message to a large number of people living under a censorship-happy government, run by Eve.
The traditional way of doing this is samizdat, but that process requires each person passing a message to take a certain risk. It would be nice of there were some way of doing this directly.

Spread-spectrum communications are resistant to jamming. However, this method assumes a shared secret key. It is implausible for this to remain secret when distributed to the audience, and when Eve obtains the key, she can jam the channel.

So, the question is: Is it possible to device a communications method like spread-spectrum, which does not require a shared key?

To be specific: A solution would require resistance to jamming, and that the
receivers can authenticate that the message was sent by Alice. Secrecy is not a requirement (and is implausible anyway).

More formally: Alice wants to send a message m over the radio spectrum. Alice has a public/private key pair, and uses it to encode the message into a cyphertext C, (we can take C to include the details of how the message is modulated for transmission). Alice can only transmit at some power level Ap. Eve only knows the public key. Alice's recipients only know the public key.  Eve can transmit a jamming signal, presumably at a much higher power level than Alice, although not without limit (especially on areas of the spectrum already being used for, say, TV channels). In a solution, Alice's followers will still be able to decode the message using only the private key.

Additionally, Alice would like to be able to repeat the exercise without having
to circulate a new public key. Suppose that the system worked on the first message, but that Eve was able to obtain the cyphertext C. Then, if the system does not vary over time, Eve will be able to jam the channel using the C. So either the system must vary with time, or Eve must not be able to obtain the cyphertext.

Some authors have described public-key steganography schemes, eg [1]. considers active attacks that attempt to break the secrecy or authenticity  of the scheme, by sending additional messages, but not than ones which perturb existing messages. [2] Does consider these kind of attacks, but their scheme is not obviously applicable to spread spectrum (to me, at least): It only copes with a limited amount of perturbation, and in doing so reduces the bandwidth of the channel a great deal.

Fingerprinting and covert channel schemes do consider 'jamming' type attacks, but I am not aware of them using public key crypto to counter such attacks.

[1] "Public-key steganography with active attacks", Michael Backes and Christian Cachin

[2] "On the limits of Steganography", Anderson and Peticolas

Google reveals that the System Security Group at ETH have done work on "jamming-resistant radio broadcast communication without shared secret keys". Perhaps this would be a good place to start?


Maximum Treewidth of a Graphs with $m$ Edges What is the maximum treewidth of a graph with $m$ edges? In other
words, what is the correct growth for the following function?

$\alpha(m) = max\{\mathrm{treewidth}(G): G \mbox{ has $m$ edges}\}$.

Clearly $\alpha(m) = \Omega(\sqrt{m})$, which is attained
by cliques with $\Omega(\sqrt{m})$ vertices and by
by $\Omega(\sqrt{m})\times \Omega(\sqrt{m})$ grids.

Is this also the maximum?

There are bounded degree (in fact even cubic i.e. 3-regular) expanders on $m$ vertices with treewidth at least $\epsilon \cdot m$, for some constant $\epsilon > 0$. See Section 2 in:

Martin Grohe, Dániel Marx:
On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99(1): 218-228 (2009)

Basically, they prove something much stronger: large vertex expansion is the only reason on why the treewidth can be as much as linear (in the number of vertices, but bounded degree graphs have linear number of edges).


Minimum-area orthogonal rectangle coverage Suppose there are N orthogonal rectangles on the planes, overlapping or not.

I want to cover them with exact K orthogonal rectangles, overlapping or not. Each input rectangle must be completely covered. More specifically:

An input rectangle can be covered by more than one covering rectangles.
An input rectangle may be partially covered by a covering rectangle.

The target is to minimize the sum of the area of the covering rectangles.

Here is an example:

http://i.stack.imgur.com/VLz63.png

The input consists of 3 rectangles as shown in the show. When k=1,2,3, the solutions are shown below. There are 2 possible solutions for K=3, depending on whose area is smaller. Note that an input rectangle can be partially covered by a covering rectangle.

I tried to google this, but not sure about the name of this problem. I got many results about the problem to decompose rectilinear polygons into rectangles, where the target is to minimize the number of covering rectangles used. That is not my case, I don't require that the covering rectangles are disjoint, and I want to minimize the area fixing the number of the covering rectangles instead of the opposite way.

I guess this is NP-Hard or similar, so I don't even expect a good approximation. Any heuristic idea would be appreciated.

Thanks!

See the paper by Aronov, Ezra and Sharir. They handle the case for points. For rectangles it is not even immediately obvious that an LP relaxion is easy to do, since there might be a chaining effect, and as such the number of candidate rectangles might be large (i.e., $O(n^k)$).

A solution with $O(k \log k)$ rectangles with the same area as the optimal solution, should follow by using BSP (binary space partition) and dynamic programming in polynomial time. So searching on the web would give you refs to papers using this scheme (I dont remember the ref, sorry).

http://www.cims.nyu.edu/~esther/Publications/AronovEzraSharir.pdf


Efficient encoding of integers with constant digit sum How can a large set of integers all with a known constant digit sum be encoded?

Example of integers in base 10, with digit sum 5:

14, 41, 104, 113, 122, 131, 140, 203 ....

The most important factor is space, but computing time is not completely unimportant.

Just omit the last digit.

(Extra text to get over the 30-chaacter minimum.)


How can I show a Gap-P problem is outside #P There are a number of problems in combinatorial representation theory and algebraic geometry for which no positive formula is known. There are several examples I am thinking of, but let me take computing Kronecker coefficients as my example. Usually, the notion of "positive formula" is not precisely defined in combinatorics, but it roughly means "a description as the cardinality of seem reasonably explicit set". Recently, I've been talking to Jonah Blasiak, and he's been convincing me that the right definition of "positive formula" is #P. I'm going to assume that, on this site, I don't need to define #P.

Buergisser and Ikenmeyer show that Kronecker coefficients are #P hard. (They are also always positive, because they are tensor product multiplicities.) But I am reasonably sure that no one knows a way of computing them which even gets them into #P.

So, suppose that I were to actually make an attempt at proving Kronecker coefficients aren't in #P. I assume that what I would do is assume some complexity theoretic conjecture and then reduce Kronecker product to some other problem which is known to be complete for a class larger than #P.

  What conjecture might I assume, and what problem might I try to reduce to?

ADDED: As has been pointed out in the comments, Buergisser and Ikenmeyer show that Kronecker coefficients are in Gap-P, which is pretty close to #P. So it sounds like the questions I should be asking are (1) What are some Gap-P-complete problems I could plausibly reduce to and (2) what are the prospects of showing that Gap-P is not #P? I guess (2) should break up into two parts (2a) do experts believe these classes are different? and (2b) are there any likely strategies to prove it?

I hope that this much editing of the question is not frowned on.

I'd suggest looking at properties of #P functions that are different than Gap-P functions. For example, determining if a #P function is zero is in co-NP. If you could show determining whether the Kronecker coefficients is zero is UP-hard then you would have "Kronecker coefficients in #P implies UP in co-NP", an unlikely conclusion.


Distinguising between the cases of low or high cover number Is there a known result saying that for some constants $0 < a < b < 1$, it is NP-hard to distinguish a graph having vertex cover number at most $a \cdot n$ from a graph having vertex cover number at least $b \cdot n$? Here n is the number of vertices in the input graph. In other words, I want to know that (unless P = NP) there is no poly-time algorithm that accepts graphs with vertex-cover number at most $a \cdot n$, rejects graphs with vertex-cover number at least $b \cdot n$, and can return anything for a graph whose vertex-cover number is in between.

Proving hardness of this sort of gap problem is usually how hardness of approximation is proved. For vertex cover, Håstad's famous paper (Theorem 7.1.) showed what you are asking for with $a=3/4$ and $b=7/8$.


Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph) Consider a random undirected graph on a set of $n$ nodes, say $\{1,2,\ldots,n\}$, such that the probability of edge between nodes $i$ and $j$ is $p_{ij}$ (we may assume $p_{ij}=o(1)$ for all $i,j$, i.e., $p_{ij}\rightarrow 0$ as $n\rightarrow \infty$, if it makes things simpler). We define Bernoulli r.v. $X_{ij}$ such that $X_{ij}=1$ iff edge $(i,j)$ exists. We also assume that $X_{ij}$'s are independent r.v.'s (so the existence of edges are independent events).

We consider a random instance of the graph and define $Z_d=$ number of nodes that are reachable from node 1 via paths of length at most $d$ (we can assume $d=O(\log n)$). Then

$Z_d \leq H_d = \sum_{i\neq 1}X_{1i}+\sum_{i,j\neq 1}X_{1i}X_{ij}+\sum_{i,j,k\neq 1}X_{1i}X_{ij}X_{jk}+\ldots$ (till $d$ levels).

I wanted to know if it is possible to get a concentration inequality for $Z_d$, like

$P(Z_d>cE[H_d]\log n)\leq P(H_d>cE[H_d]\log n)\leq c'n^{-1}$,

where $c,c'$ are constants? ($\exp(-c''n)$ in place of $c'n^{-1}$ would be desirable)

(whether $P(H_d>cE[H_d]\log n)\leq c'n^{-1}$ is possible or not is the concentration inequality for function of independent Bernoulli r.v.'s that I am interested in)

In general, it seems that you cannot get the concentration you want without  more constraints on the probabilities.

Consider the following graph on $n$ vertices. Let vertices $C = \{2,\ldots,n\}$ form a clique such that for all $i,j \in C$, $p_{ij} = 1$. Let vertex $1$ be connected to this clique via only one edge, with $p_{1,2} = 1/\log(n)$, and $p_{1,j} = 0$ for all $j \in C$ with $j \neq 2$. Then with probability $1/\log(n)$, all $n$ vertices are reachable from $1$ with 2 hops, and with probability $1 - 1/\log(n)$ none are. So the expected number of reachable vertices is $n/\log(n)$, but with probability $1/\log(n) \gg n^{-1}$, it is $n$, larger than its expectation by a $\log(n)$ factor.

In fact, since you are interested in paths of length $\log n$, all that we require is that the realized edges in $C$ form an expander, not a clique, with high probability. This can be accomplished with $p_{ij} = o(1)$ as well, so this condition does not save you.

The essence of the problem is this: since you can have a group of vertices $C$ that are highly connected with high probability, how many vertices vertex $1$ is connected to can depend only on whether it is connected to $C$ or not, which can depend on only a single edge. You can't expect something depending on only a single Bernouli random variable to be well concentrated.


How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$? How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$?  A polynomial time nondeterministic algorithm would immediately imply this because $P \neq EXPTIME$ but no one believes $NP = EXPTIME$.  If I've done the algebra right (see below) the time hierarchy theorem would still give the $P \neq NP$ implication for $O(2^n/f(n))$ running times for any superpolynomial $f(\cdot)$, but for all I know there are complete problems with efficient reductions that allow slower algorithms to give the result.  Are there EXPTIME-complete problems where we know something like $2^n/n$ or $2^n/n^2$ with nondeterminism is enough?

Clarification of the "algebra": $P = NP$ implies $EXPTIME=NEXPTIME$ by a padding argument, so a nondeterministic $2^n/f(n)$ algorithm for an EXPTIME-complete problem would also be one for a NEXPTIME-complete problem.  For superpolynomial $f(\cdot)$ this would contradict the nondeterministic time hierarchy theorem since we could reduce using some $L \in$ NTIME$(2^n)$.

I think its easier to turn it around.

If $\mathsf{P}=\mathsf{NP}$, then $\mathsf{NTIME}(T(n)) \subset \mathsf{DTIME} ((T(n))^c)$
for some constant $c$, and any $T(n) > n$.
Since $\mathsf{DTIME} ((T(n)^c)$ does not contain
$\mathsf{DTIME}(T(n)^{c}\log T(n)) \subset \mathsf{DTIME}(T(n)^{c+1})$,
this means we cannot solve, say all problems in $\mathsf{DTIME}(2^n)$ in
$\mathsf{NTIME} (2^{\epsilon n})$ for some $\epsilon$.
So a non-deterministic time $2^{o(n)}$ algorithm for a problem complete for
$\mathsf{DTIME} (2^n)$ under quasi-linear reductions would be enough to prove $\mathsf{P} \neq \mathsf{NP}$.


Optimal algorithm for finding the girth of a sparse graph? I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity.

I thought about some modification on Tarjan's algorithm for undirected graphs, but I didn't find good results. Actually I thought that if I could find a 2-connected components in $O(|V|)$, then I can find the girth, by some sort of induction which can be achieved from the first part. I may be on the wrong track, though. Any algorithm asymptotically better than $\Theta(|V|^2)$ (i.e. $o(|V|^2)$) is welcome.

Here's what I know about the girth problem in undirected unweighted graphs.
First of all, if the girth is even, you can determine it in $O(n^2)$ time- this is an old result of Itai and Rodeh (A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM J. Computing, 7(4):413–423, 1978.). The idea there is: for each vertex in the graph, start a BFS until the first cycle is closed (then stop and move on to the next vertex); return the shortest cycle found. If the girth is even the shortest cycle found will be the shortest cycle. In particular if your graph is bipartite this will always compute the girth. If the girth $g$ is odd, however, you'll find a cycle of length $g$ or $g+1$, so you may be off by $1$.

Now, the real problem with odd girth is that inevitably your algorithm would have to be able to detect if the graph has a triangle. The best algorithms for that use matrix multiplication: $O($ min{$n^{2.38}, m^{1.41})$ time for graphs on $n$ nodes and $m$ edges.
Itai and Rodeh also showed that any algorithm that can find a triangle in dense graphs can also compute the girth, so we have an $O(n^{2.38})$ time girth algorithm. However, the runtime for the girth in sparse graphs is not as good as that for finding triangles. The best we know in general is $O(mn)$. In particular, what seems to be the hardest is to find a $o(n^2)$ time algorithm for graphs with $m=O(n)$.

If you happen to care about approximation algorithms, Liam Roditty and I have a recent paper in SODA'12 on that: Liam Roditty, V. Vassilevska Williams: Subquadratic time approximation algorithms for the girth. SODA 2012: 833-845.
There we show that a $2$-approximation can be found in subquadratic time, and some other results concerning additive approximations and extensions. Generally speaking, because of a theorem of Bondy and Simonovits, when you have densish graphs, say on $n^{1+1/k}$ edges, they already contain short even cycles, say roughly $2k$. So the denser the graph is, the easier it is to find a good approximation to the girth. When the graph is very sparse, the girth can be essentially arbitrarily large.


What's a good news source for Computer Science? If I want to be aware of the lastest discoveries in the Computer Science area, what's a good source of information? (preferable online)

Theory of Computing Blog Aggregator for theoretical computer science


Is there a example of Iterative Rounding in Approximation Algorithms for vertex weighted Graphs? I am referring to the "Iterative Rounding" technique used by Kamal Jain for Steiner Network problem to obtain $2$ approximation factor algorithm. Is there any example where this technique is used for vertex weighted graphs? I have only seen examples for weighted edges or edge connectivity problems that use this paradigm. The nearest i have seen is degree bounded networks that use this paradigm. Also, i would like to get some intuition that when is this method probably applicable (or what could be the underlying difficulty that it is not yet applied to vertex weighted scenarios).

The simplest node-weighted network design problem is the node-weighted Steiner tree problem. Klein and Ravi considered this problem and obtained an $O(\log k)$-approximation (here $k$ is the number of terminals). They also showed that the Set Cover problem reduces to it in an approximation preserving fashion and hence we should not expect any better approximation. It is not hard to show that iterated rounding is not helpful for the  Set Cover problem. Consider the following example. We have $n$ elements $\{e_1,\ldots,e_n\}$ and $n$ sets $S_1,\ldots,S_n$ where $S_i$ contains all elements except $e_i$. If you look at the natural LP with a variable $x_i$ for set $S_i$ then a basic feasible optimal solution is to set $x_i = 1/(n-1)$ for each $i$. From this one can see that iterated rounding in the plain vanilla fashion won't give a good bound. Note that the integrality gap of the LP is $O(\log n)$. This example for Set Cover can be extended to the node-weighted Steiner tree problem.


Does the Cook-Levin theorem relativize? My only motivation for asking this question is long-standing curiosity, but I am interested in seeing a proof (or disproof) that the Cook-Levin theorem relativizes.  If you have a proof that the theorem does indeed relativize, please supply an explanation of how relativization impacts the proposition, i.e., what does the relativized version of the statement look like when an oracle A is added?  Also, please explain what happens to the proposition when a TQBF oracle is added to the computation model.

From the comment above: there are two interpretations to your question:

1) The Cook-Levin theorem does not relativize in this sense: there exists a language $L$ and an oracle $A$ such that $L \in NP^A$ but $L$ is not polynomial-time many-one reducible to $3SAT$ even if the polynomial time Turing machine that performs the reduction is allowed to access the same oracle $A$ (i.e. $L \nleq_m^A 3SAT$). The proof is a standard exercise (see for example Arora and Barak, Computational Complexity); hint: play a little bit with the oracle that separates P from NP, the only difference here is that you must "fool" polynomial-time oracle Turing machines that output 3SAT formulas instead of deciders that output yes/no (let me know if you need the full proof);

2) The Cook-Levin theorem does relativize in this sense: you  can extend the circuit model with oracle gates, i.e. $k$-inputs gates in which the inputs are ordered and the output bit is the result of the associated oracle on the query formed by the ordered input bits (there is also a variant in which every bit of the query is represented by two input bits, in order to allow queries shorter than $k$). With this extended oracle circuit model you can build in polynomial time a polynomial-size oracle circuit $C^A$ that "simulates" - in a similar way of the Cook-Levin theorem - the computation of an oracle polynomial time machine $M^A$ and on input $x$ evaluates to 1 if and only if $M^A(x)=1$. So, if

$\text{Circuit-}SAT^A = \{ C \mid C $ is a boolean circuit equipped with oracle gates for $A$ and for which there exists $x$ such that $C(x)=1 \}$ you say that:

for every oracle $A$, $\text{Circuit-}SAT^A$ is $NP^A$-complete.

3) Finally with a TQBF oracle we have $P^{TQBF} = NP^{TQBF}$, so if we add a TQBF oracle to the polynomial time Turing machine that performs the reduction (interpretation 1) we give to it the power to solve the original problem directly, so we have: $NP^{TQBF} \leq_m^{TQBF} \{1\}$ i.e. every trivial set is $NP^{TQBF}$-complete under polynomial time many-one TQBF-oracle reductions (except $\emptyset$ and $\Sigma^*$ :-), so Cook-Levin theorem does relativize for the TQBF oracle (solve the source instance and output $(x_1 \lor x_2 \lor x_3)$ if it belongs to the language, output an unsatisfiable 3SAT formula otherwise).

Addendum: related to your question, it is interesting how the (old but great) Computational Complexity by C. Papadimitriou explicitly faces the problem of the relativization of another well known thereom, the Ladner's theorem, in this way (probably the oracle gates were introduced later):

[From Chapter 14]: ... "If $P^A \neq NP^A$, then there is a language in $NP^A - P^A$
which is not $NP^A$-complete". But when we say "$NP^A$-complete", do
we also allow the use of oracle in our reductions?
With a little reflection we may decide that the
right way to state the result is in terms of ordinary reductions...
..... There seems to be no reasonable definition of $SAT^A$.
To get around this difficulty, we must replace the usage of SAT
with an $NP^A$-complete problem. Such problem exist; for example:

$C^A = \{ (M^A,x) \mid $ nondeterministic  oracle machine $M^A$ accepts $x$ in time $|x|\}$


Sequent calculus for nonmonotonic/defeasible logics? Is it possible to construct sequent calculus for nonmonotonic/defeasible logic? If it is possible then those logics can be encoded in proof assistants which require sequent calculus for logic to be encoded (Isabelle, Coq).

I am aware of the several papers from the late nineties by Ana Teresa Martins et al. about sequent calculus for paraconsistent logics. the labelling of propositions (given and derived) is used in those papers. But those papers seems to be unpublished, although they contain bright ideas, the quality of language may be a bit higher. It seems to me that those ideas are not caught by others and developed futher.

There is a paper by Beyersdorff and Chew on the proof complexity of calculi for non-monotonic logic. In the references of this paper you will find links to the papers where these calculi are defined.


Given discrete rvs X,Y, find Z s.t. I(Z;X) is high and I(Z;Y) is low. -- known problem? Consider the following problem. Let $X$ and $Y$ be discrete random variables. The goal is to find a random variable $Z$ such that, informally, $I(Z;X)$ is high and $I(Z;Y)$ is low.

More precisely, either: $~\max_Z I(Z;X) ~\text{s.t.}~ I(Z;Y) \le c~$ or $~\min_Z I(Z;Y) ~\text{s.t.}~ I(Z;X) \ge c~$ (for some constant $c$).

This seems like a very natural, fundamental (if toy?) problem, so surely something is known about it. (I know that for $X,Y$ both with finite support, (large) linear programs can be written to solve for such $Z$, but I imagine there's a neater way.) Any pointers would be appreciated.

Thanks!

In one form, your question is actually a clustering question that is addressed by the information bottleneck method.

Roughly, $Y$ represents the rows of a joint distribution and $X$ represents the columns. The random variable $Z$ then represents a distribution over the rows ($Y$) that is highly compressed (because $I(Z;Y)$ is small) but represents the joint distribution well (because $I(Z;X)$ is large).

It's not clear to me that this can be solved using LPs. the underlying problem is not convex. But there's a simple EM-style alternating optimization scheme that can be used to solve it.


What's new in purely functional data structures since Okasaki? Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few:

IntMap (also invented by Okasaki in 1998, but not present in that book)
Finger trees (and their generalization over monoids)

There are also some interesting ways of implementing already known datastructures, such as using "nested types" or "generalized algebraic datatypes" to ensure tree invariants.

Which other new ideas have appeared since 1998 in this area?

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.


Finding a ranking which minimizes the number of conflicts Suppose that $k$ different voters have each produced a partial ordering of candidates $1,\ldots,n$. For example, if $k=3$ and $n=4$, the voters may have produced the partial orders

$1<2$
$2<1<3<4$
$2<3<1$

Our goal is to fuse all these into a single ranking of the candidates in a way that minimizes conflicts. The following seems like a natural way to do this. Given a total order $L$, let $C(i,j)$ be the number of the partial orders which rank $i$ and $j$ in the opposite way from $L$ (i.e., if $L$ ranks $i$ before $j$, $C(i,j)$ equals the number among the $k$ partial orders that rank $j$ before $i$).  We seek to find a total order $L$ which minimizes $\sum_{i<j} C(i,j)$.

This seems like it would be a well-studied problem, but I have been unable to find any references, likely because I'm not aware of the right keywords. Can any one point me towards papers where algorithms for this problem were considered?

This is a special case of metric $1$-medians, where the metric space is $S_n$ (the symmetric group on $n$ elements) with distance function number of inversions (i.e. the distance between two permutations is the number of pairs $i, j: i<j$ s.t. $i$ and $j$ are ordered differently). This distance metric is also known as Kemeny distance and is related to the weak Bruhat order.

This paper by Ailon, Charikar, and Newman considers this and related problems. The problem you're asking about is called Rank Aggregation in their paper. Look at their intro for more references. The problem is NP-hard. A simple 2-approximation is to pick the best of the given $k$ permutations (i.e. the permutation that minimizes the objective function). Here is a proof:

Let $\pi$ be the optimal permutation and $\pi_{j^*}$ the best of $\pi_1, \ldots, \pi_k$. For any $i, j \in [k]$, by the triangle inequality, $d(\pi_i, \pi) + d(\pi_j, \pi) \geq d(\pi_i, \pi_j)$. Sum over all $i, j$, and you get $2n\mathsf{OPT} \geq \sum_j{\mathsf{ALG}(j)}$, where $\mathsf{ALG(j)}$ is the cost of choosing $\pi_j$ as the solution, and $\mathsf{OPT}$ is the cost of the optimal solution. Since $\pi_{j^*}$ was chosen so that $\mathsf{ALG}(j^*)$ is minimum over all $\mathsf{ALG}(j)$ for $j \in [k]$, we have $\mathsf{ALG}(j^*) \leq \sum_j{\mathsf{ALG}(j)} /n$ and we have $\mathsf{ALG}(j^*) \leq 2\mathsf{OPT}$.

The paper I referred you to above has another, almost equally simple 2-approximation (but the proof is not that simple, though still not bad). They can show that the bad cases for the two approximation algorithms are different, and taking the better solution of the two gives 11/7 approximation factor.

Then there is also a PTAS by Mathieu and Schudy (Warren sometimes visits this site btw), by a reduction to weighted Minimum Feedback Arc Set in Tournamets (the same reduction is used in the previous paper, I think). Here is the link