Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons Is there a comparison-based sorting algorithm that uses an average of $\mathrm{lg}(n!)+o(n)$ comparisons?

Existence of a worst-case $\mathrm{lg}(n!)+o(n)$ comparison algorithm is an open problem, but the average case suffices for a randomized algorithm with expected $\mathrm{lg}(n!)+o(n)$ comparisons for every input.  The significance of $\mathrm{lg}(n!)+o(n)$ is that it is $o(n)$ comparisons from optimal, wasting an average of only $o(1)$ comparisons per element.

Since I already have such an algorithm, I am including it as an answer (using Q/A format), but I welcome additional answers, including other algorithms, whether such an algorithm was already known, improving $o(n)$, and worst-case $\mathrm{lg}(n!)+o(n)$.

Prior work:
Merge sort uses $\mathrm{lg}(n!)+ Θ(n)$ comparisons (even in the worst case).
Merge-insertion sort (also known as Ford–Johnson sort) also uses $\mathrm{lg}(n!)+ Θ(n)$ comparisons but with a much smaller constant in $Θ(n)$.
Improved Average Complexity for Comparison-Based Sorting (by Kazuo Iwama and Junichi Teruyama) — their (1,2)Insertion algorithm resembles a portion of my answer below.

Update:  I expanded this answer into a paper Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons.

Yes, such an algorithm exists.  I will only prove the $\mathrm{lg}(n!)+o(n)$ bound, but under a likely randomization assumption we also get $\mathrm{lg}(n!)+O(n^{1-ε})$.  I will also describe an attempt for $n^{0.5+o(1)}$ and $O(n^{0.5-ε})$.

We can assume that all elements are distinct, by annotating them if necessary; the average case uses distinct elements in random order.  We can compute the average number of comparisons by adding the entropy loss for each comparison relative to using a fair coin.

The starting point is insertion sort with a binary search to decide where to insert the next element into the sorted subset $S$.  When $(1-ε)2^m ≤ |S| ≤ 2^m-1$, an insertion uses at most $m$ comparisons, which (in terms of entropy) is optimal up to an $O(ε)$ additive factor (and for average-case complexity, $2^m ≤ |S| ≤ (1+ε) 2^m$ also works).  Now, when $|S|$ is not close to a power of 2, insertion of an element $A$ is suboptimal (even in the average case and regardless of how we balance each query), but if wasting $o(1)$ comparisons, we could steer $A$ to an approximately uniform distribution over an interval of $S$ of length close to a power of 2, we get the desired optimality.

We achieve this by adding elements in batches, and sometimes efficiently comparing elements of the batch with each other, such that the interval of $S$ corresponding to an element $A$ decreases in a quasi-random manner (and with the probability distribution of $A$ inside the interval nearly uniform), and when the interval length is close enough to a power of 2, doing the binary search to insert $A$.

Common constructs

We will keep a subset $S$ of sorted elements, and for each unsorted element $A$, we will keep track of the minimal interval $I_A$ of $S$ where $A$ is known to be located.  $|I_A|$ is the length of $I_A$; $I_A=I_B$ is by the identity of the intervals.

Let $\mathrm{Compare}(A,B)$ be: Compare $A$ with $B$, and then (in random order) compare $A$ and $B$ against corresponding elements of $S$ until their intervals are disjoint (or have length 1).  The element of $S$ is chosen (in a consistent manner) to make the probabilities for the comparison as close to 1/2 as possible, assuming that when $\mathrm{Compare}$ is called, $(A,B)$ is  uniformly distributed on $I_A⨯I_B$.  Because of the disjointness in the end, $\mathrm{Compare}$ preserves the uniformity assumption.

The following sections can be read independently of each other.

A $\mathrm{lg}(n!)+o(n)$ algorithm

Given:  A sorted list $S$, and a batch of $m$ unsorted elements; $m∈ω(1)∩o(|S|)$; the unsorted elements are random relative to $S$.

Repeat (1)-(3) while possible:
1. Pick two elements $A$ and $B$ from the batch with $I_A=I_B$ (any choice will work).
2. Run $\mathrm{Compare}(A,B)$.
3. If $|I_A|$ is close enough to a power of 2,(note 1) remove $A$ from the batch (without forgetting $I_A$); and do similarly with $B$.
Finally:  Insert all elements into $S$ and complete the sort.

Note 1: For "close enough", any $o(1)$ relative error (as a function of $m$) works as long as $m-o(m)$ elements will be removed in step (4) (possible by note 2).  Under a conjectured randomization assumption, using $c \log \log m / \log m$ relative error captures $m(1-\log^{-Θ(c)}m)$ elements, allowing a $\mathrm{lg}(n!)+O(n \log \log n / \log n)$ average comparison sorting algorithm.

Note 2: Because the same sequence of comparisons leads to the same bounding interval, almost all elements will go through step (1) $Ω(\log m)$ times (unless removed in step 4).  In the beginning, if $A < B$ and we pick $A$, we compare $A$ against element $S[≈(1-1/\sqrt{2})|S|]$, and each application of step (3) to $A$ has $O(1)$ probability of reducing $|I_A|$ in $≈1/(1-1/\sqrt{2})$ times.  Now for every ratio $a>1$ that is not a rational power of 2, we have $∀ε>0 ∀d>0 ∃m,n∈\mathbb{N} \,\, 1-ε < \frac{a^m}{d2^n} < 1+ε$, and so we get the $o(n)$ bound.

A likely $\mathrm{lg}(n!)+O(n^{1-ε})$ algorithm

Modulo a randomization assumption, we can achieve $\mathrm{lg}(n!)+O(n^{1-ε})$ average comparisons as follows.

Randomly shuffle the items, and sort the first half into a list $S$, while keeping the second half as an unsorted batch.
Repeat until the batch is empty:
Randomly choose $A∈\text{batch}$.  Let $G = \{ B∈\text{batch}: |P(A < B) - 0.5| < n^{-0.51ε} \}$.  If $G$ is empty, remove $A$ from the batch and insert into $S$. Otherwise:

If there is $B∈G$ such that with probability $Θ(1)$ (say ≥0.05), $\mathrm{Compare}(A,B)$ makes $|I_A|$ within $n^{-ε}$ relative error of a power of 2, run $\mathrm{Compare}(A,B)$ and if successful (i.e. $|I_A|$ is within $n^{-ε}$ relative error of a power of 2), remove $A$ from the batch and insert into $S$.
If there is no such $B∈G$, run $\mathrm{Compare}(A,B)$ for a random $B∈G$.

If our randomization assumption works out (i.e. the distribution of interval lengths and positions is random enough), then throughout much of the process, a typical $A$ can be efficiently compared with a choice of $n^{Θ(1)}$ elements (with $n^{Θ(1)}$ different interval lengths). Thus, we can typically choose a comparison for (1) above, and if we are unlucky with the comparison result, we still get $Θ(\log n)$ chances, thus achieving (if $ε$ is small enough, say 0.01) a $\mathrm{lg}(n!)+O(n^{1-ε})$-comparison algorithm.  With some changes and approximations, the total compute can be made quasilinear:  Given an element $A$, compute promising interval lengths, and then look up $B$s with the right approximate center and interval lengths.

There are a number of ways to optimize comparisons, but the obstacle is that each comparison may end up being unlucky and we have a limited number of comparisons.  If after optimization, $\mathrm{Compare}(A,B)$ does an average of 4 comparisons and 'succeeds' with 1/4 probability, we get $ε≈(1-ε)/4/\log_{4/3} 2 ≈ 0.09$.

A perhaps much better approach is to wait until an interval is close to a power of 2, controlling not the individual interval lengths but the distributions of lengths.

An attempt at a $\mathrm{lg}(n!)+n^{0.5+o(1)}$ algorithm

Suppose that $|S|=n$ and we are given an unsorted batch of $n$ elements with the intervals $I_A$ also given, with $|I_A|$ typically $n^{1-o(1)}$ and with $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$ distributed uniformly (up to a random error, and holding with sufficient precision even if conditioned on $A < S[i]$).  Then, we can sort the items wasting an average of $n^{0.5+o(1)}$ comparisons as follows:
(*) Insert all elements in the order of their initial $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$.  This way all elements are inserted when their interval length is close to a power of 2.

The sorting algorithm will be: Randomly shuffle the list and sort the first half $S$. To insert the second half, make the distribution right, and do the (*) above.

To make the $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$ distribution right, we can make a 'random' distribution, and then withhold the right fraction of the elements for each $|I_A|/2^{\lfloor \mathrm{lg} |I_A| \rfloor}$ while randomizing the rest (repeating if necessary).  However, while this should correct $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$ globally, we do not know whether it can be controlled locally with the required precision (hence the word "attempt" above).

To make a 'random' distribution, we can randomly use $\mathrm{Compare}(A,B)$ with $P(A < B)≈0.5$, except that with the initial $I_A$ all identical, we do not expect randomization at a sublogarithmic depth (i.e. with $I_A$ long enough).  However, I conjecture that we get randomization at a sublogarithmic depth using generalizations (probably any reasonable choice will work) of $\mathrm{Compare}$ to $k=ω(1)$ elements: If we keep $k=ω(1)$ elements entangled (i.e. connected using comparison results), we should have about $k$ noncommuting choices for each comparison with $S$.  This should allow $O(\log_k n + \log k)$ randomization depth, as desired (assuming that $k$ is not too large as we need depth $Θ(\log k)$ to distentangle the elements).  I expect that the compute can be made quasilinear if using a small enough $k$.

Since a comparison with $1/2+n^{-0.5}$ yes probability only wastes $O(1/n)$ entropy, the initial randomization and the slight nonuniformity of the elements in their bounding intervals should only need $n^{o(1)}$ entropy waste.  If the distribution shaping succeeds well enough, the entropy waste stems primarily from interval length mismatches during (*) (hence the $n^{0.5+o(1)}$).

A possible $\mathrm{lg}(n!)+O(n^{0.5-ε})$ combination:  If the distribution shaping works well enough and we make the batch size equal $|S|+n^{0.5+ε}$ and selectively reject $≈n^{0.5+ε}$ elements in (*) (above), we can insert all but these $≈n^{0.5+ε}$ elements with entropy waste $n^{0.5-ε/2+o(1)}$ as follows.  Split $S$ into $n^ε$ nearly equal intervals, and when during insertion, $I_A$ settles on an interval, reject (i.e. cancel the insertion) if the interval is too long, thus reducing the variation in the lengths of these intervals $Θ(n^{ε/2})$ times, which in turn reduces the length variations of random length $n^{1-o(1)}$ intervals in $n^{ε/2-o(1)}$ times, as needed.  Now, we can use the above $\mathrm{lg}(n!)+O(n^{1-ε})$ algorithm to insert the remaining elements with $O(n^{0.5-ε'})$ waste if $ε$ is small enough.

Worst-case complexity of sorting:  Most likely, there is a sorting algorithm with $\mathrm{lg}(n!)+o(n)$ worst-case comparisons.  For finding median, there is a linear gap between the average case ($1.5n+o(n)$ comparisons) and the worst case (at least $(2+ε)n-O(1)$ comparisons).  However, for sorting, there is plenty of freedom for arranging comparisons and for finding new sorting algorithms.


Is there any quantum analog of the VP vs. VNP problem? From Wikipedia:

$\mathsf{VP}$: The class VP is the algebraic analog of P; it is the class of polynomials $f$  of polynomial degree that have polynomial size circuits over a fixed field $K$.
$\mathsf{VNP}$: The class VNP is the analog of NP. VNP can be thought of as the class of polynomials $f$ of polynomial degree such that given a monomial we can determine its coefficient in $f$ efficiently, with a polynomial-size circuit.

There have been attempts to implement polynomials $f$ using quantum circuits, cf. arXiv:1805.12445. So does there exist any quantum analog of the $\mathsf{VP}$ vs. $\mathsf{VNP}$ problem? Is there any paper on this topic?
P.S: I've asked a very related question on the Quantum Computing site.

This is not quite an answer, but some observations that are too long for a comment. I've thought about this question before, but not being an expert in quantum I was never really able to resolve it. The thing you want for this is a polynomial $f$ (really, a family of polynomials $f_n$, one for each $n$) such that $f = (f_n)$ is in some sense complete for $\mathsf{BQP}$ (resp., $\mathsf{QMA}$). While there are many problems on polynomials that show up in quantum classes, they are typically more of the form "Given some input graph G, compute (the coefficients of, or the evaluation of) some polynomial $f_G(x)$ at some point $x$". For example, a natural thing to think of here is the Jones polynomial. Given a link, approximating its Jones polynomial at a root of unity is $\mathsf{BQP}$-complete. Evaluating the Jones polynomial given a link in general is $\mathsf{\# P}$-hard (see references e.g. here). So there are two issues here in using this to define "$\mathsf{VBQP}$": the first is that the Jones polynomial in general is $\mathsf{\# P}$-hard, so if you tried to use it you might end up with $\mathsf{VNP}$ again. Second, it's not just a single family of polynomials, it's a question of the above form (given an input object $G$, compute $f_G$, rather than evaluate $f_n(G)$ which is what we'd want).

Another approach you might try is to consider the amplitudes of the output of a quantum circuit as a polynomial in their inputs. But these amplitudes can be permanents, so again we quickly seem to run into $\mathsf{\# P}$- or $\mathsf{VNP}$-completeness.

Yet another approach you might try is to somehow mimic the "universal circuit" constructions for $\mathsf{VP}$-complete problems (those by Burgisser and then Raz, see, e.g., Mahajan's survey or the references in Section 5 of Mahajan-Saurabh) with universal quantum circuits. Here we run into the issue that there seems to be somewhat of a mismatch between quantum circuits and algebraic circuits. In particular, a quantum circuit on n qubits maintains $2^n$ amplitudes, whereas an algebraic circuit maintains a single ring element on each wire, so a total number which is polynomial in the size of the circuit (linear if you measure size by number of wires or have bounded fan-in). Quantum circuits that maintain much less information than this - e.g. stabilizer circuits or linear-optics circuits - seem not to capture the full power of $\mathsf{BQP}$.

On a related noted, $\mathsf{BPP}$, $\mathsf{MA}$, $\mathsf{BQP}$, and $\mathsf{QMA}$ are all semantic classes with no known syntactic characterization (see, e.g., this or this). My first instinct is that this is related to the fact that algebraic complexity classes like $\mathsf{VP}$ are syntactic, but I'm not sure that's right. At any rate, I don't think we know of any such semantic class with an algebraic analogue.

This is not to say that all of these approaches can't work, just to share some thoughts on them. I hope someone can get it to work!


Algebraic (or numeric) invariants of complexity classes I hope this question isn't too naive for this site.

In mathematics (topology, geometry, algebra) it is common for one to distinguish between two objects by coming up with an algebraic or numerical invariant, and proving the two objects have different values. I'm wondering to what extent this has been tried with complexity classes (or if it has, why I haven't ever heard about it). Algebraic structures show up a lot in theoretical computer science as a whole (cf Uses of algebraic structures in theoretical computer science), so why not in complexity theory?

In my naivete I can imagine a notion of equivalence of two languages: the existence of a polynomial-time reduction which is also reversible (or a bijection on the strings). I can also imagine that this notion is unsuitable: no finite languages of differing cardinality could be considered equivalent, even though we're more often interested in infinite languages.

Are there any other, weaker notions of isomorphism of languages that have yielded interesting results? Are there other kinds of numerically-flavored invariants that have been used to distinguish complexity classes?

First of all, the relation you defined is usually called polynomial-time isomorphism ($\cong^p$). Although isomorphism is an interesting notion that has been studied, the (weaker) relation that is more frequently of concern in complexity is polynomial-time equivalence: $A$ and $B$ are equivalent ($A \equiv_m^p B$) if there are polynomial-time many-one reductions (aka Karp reductions) from $A$ to $B$ and vice versa, but those reductions need not be inverses to one another, and need not even have polynomial-time inverses. Sometimes we also care about equivalence under polynomial-time Turing reductions rather than many-one ($\equiv_T^p$), aka Cook reductions. For example, either of these notions of equivalence is "good enough" for $P$ vs $NP$ (that is, you don't need to consider isomorphism classes).

From the perspective of polynomial-time equivalence, there is partial "good reason" that you don't hear about numerical invariants: they can't work in general. A theorem in Andrew Marks's thesis states that $\equiv_T^p$ is complete for countable Borel equivalence relations (the introduction of his thesis gives a good overview of Borel equivalence relations and their significance). In particular, this implies that there is no Borel function $f: 2^{\mathbb{N}} \to \mathbb{R}$ such that $A \equiv_T^p B$ iff $f(A) = f(B)$.

The reason I say this is only partially a good reason is that there still might be a Borel function $f:2^{\mathbb{N}} \to \mathbb{R}$ such that if $f(A) \neq f(B)$ then $A \not\equiv_T^p B$. Or there might be a non-Borel function that does the job, but if there is we're a little unlikely to find it...

But classifying all equivalence classes is also stronger than what we usually care about, since the number of equivalence classes that show up as natural complexity classes is comparatively small (despite the forbidding size of the complexity zoo). However, there are other "numerical" invariants we can associate to languages. One such is their density: the density of a language $A$ is the function $d_A(n) :=$ number of strings in $A$ of length $\leq n$. Note that density is preserved, up to a polynomial change, by poly-time isomorphisms, but not necessarily by polynomial-time equivalences (e.g. all languages in $P$ are polynomial-time equivalent, but they can have wildly different densities).

We know things like: if $A$ is polynomially sparse ($d_A(n) \leq poly(n)$) then $A$ cannot be $NP$-complete unless $P=NP$ (Mahaney's Theorem). There are lots of other results about sparse languages and their relation to complexity classes. For good surveys, see Cai and Ogihara "Sparse Sets versus Complexity Classes" in Complexity Theory Retrospective II (available online - just Google) and Hemaspaandra and Glaßer's pair of articles "A Moment of Perfect Clarity I,II" in SIGACT News.

As mentioned by @SureshVenkat, you can kind of view Geometric Complexity Theory in the light you're talking about. However, the algebraic objects used there - namely representations - are more akin to general properties of a language than to numerical properties per se, but at least they are properties of an algebraic flavor.

Finally, in algebraic complexity theory one numerical property that's worth mentioning, but probably won't work to resolve the big questions, is degree. (As in the degree of a polynomial.) Strassen's degree bound is still the only known super-linear lower bound on unrestricted algebraic circuits. Degree also gets used e.g. in Razborov-Smolensky and many other areas of low-level (Boolean) circuit complexity.


Problem that is in P only if P!=NP Are there any problems that are solvable in polynomial time only if P!=NP, and otherwise solvable in (say) $O(2^n)$ time?

A simple example would be: If P!=NP, compute a primality test for a random n-bit number, otherwise, evaluate a random worst-case position in generalized chess of a nxn board with 2n pieces on each side. That seems kinda hacky though. Are there any more natural examples?

If we knew a specific computable language $L$ such that we could prove $L\in\mathrm P\iff\mathrm P\ne\mathrm{NP}$, this would make $\mathrm P\ne\mathrm{NP}$ equivalent to a $\Sigma^0_2$ sentence. While $\mathrm P\ne\mathrm{NP}$ is $\Pi^0_2$, it is not known to be $\Sigma^0_2$, and this is outright false in the relativized world (see https://cstheory.stackexchange.com/a/16644).


Drawing graphs of bounded crossing number Fáry's theorem says that a simple planar graph can be drawn without crossings so that each edge is a straight line segment.

My question is whether there is an analogous theorem for graphs of bounded crossing number.  Specifically, can we say that a simple graph with crossing number k can be drawn so that there are k crossings in the drawing and so that each edge is a curve of degree at most f(k) for some function f?

EDIT: As David Eppstein remarks, it is readily seen that Fáry's theorem implies a drawing of a graph with crossing number k so that each edge is a polygonal chain with at most k bends.  I'm still curious though whether each edge can be drawn with bounded degree curves.  Hsien-Chih Chang points out that f(k) = 1 if k is 0, 1, 2, 3, and f(k) > 1 otherwise.

If a graph has bounded crossing number it can be drawn with that number of crossings in the polyline model (i.e. each edge is a polygonal chain, much more common in the graph drawing literature than bounded-degree algebraic curves) with a bounded number of bends per edge. It's also true more generally if there is a bounded number of crossings per edge. To see this, just planarize the graph (replace each crossing by a vertex) and then apply Fáry.

Now, to use this to answer your actual question, what you need to do is to find an algebraic curve that is arbitrarily close to a given polyline, with degree bounded by a function of the number of polyline bends. This can also be done, fairly easily. For instance: for each segment $s_i$ of the polyline, let $e_i$ be an ellipse with high eccentricity that is very close to $s_i$, and let $p_i$ be a quadratic polynomial that is positive outside $e_i$ and negative inside $e_i$. Let your overall polynomial take the form $p=\epsilon-\prod_i p_i$ where $\epsilon$ is a small positive real number. Then one component of the curve $p=0$ will lie a little outside the union of the ellipses and can be used to substitute for the polyline; its degree will be twice the number of ellipses, which is linear in the number of crossings per edge.


Reference for fundamental theorem on tree rotations Two binary search trees are said to be linearly equivalent when they agree in their in-order traversals. The following theorem explains why tree rotations are so fundamental:

Let A and B be binary search trees. Then A and B are linearly equivalent if and only if they are connected by a sequence of tree rotations.

I noticed this result when I was first learning about data structures long ago and wanted to understand the special status of tree rotations more deeply.

The proof is simple and intuitive: Rotate the least element up to the root position along the leftward spine. By the order invariant, this rearranged tree cannot have a left subtree. Now recurse on the right subtree. The result is a normal form for testing linear equivalence.

While it's a basic theorem, I've never come across it in the literature. I would greatly appreciate a reference for the next time I need to use this result.

(Bonus brain teaser: What's the best algorithm for finding the shortest sequence of tree rotations that connect two linearly equivalent binary search trees?)

An early paper that made this observation explicitly -- that rotations preserve inorder traversals -- is (in Figure 2 of) Sleator and Tarjan's 1983 Self-adjusting binary search trees.  The move-to-root heuristic was studied in Allen and Munro's 1978 Self-Organizing Binary Search Trees paper.


Simplest proof of NP-completeness The only first-principles "proof" that a problem is NP-complete I encountered is from Introduction to algorithms, and deals with the circuit-satisfiability problem. According to the authors, many details in the proof are omitted.

What is the simplest first-principles proof that a problem is NP-complete that thoroughly presents all the technical details?

What about { (M,$1^t$) : M is a turing machine that, run on a blank tape, accepts within t steps} ?

The proof of NP-completeness is a simple exercise from the definition.


Algorithm for finding heavy hitters in a weighted stream The problem of finding heavy hitters in a stream is defined as follows: given a $N$ sized stream of elements, return a set $\mathcal D$, such that every item which arrived at least $N\theta$ times appear in $\mathcal D$, and no element with frequency lower than $N(\theta-\epsilon)$ belongs to $\mathcal D$. $\epsilon$ and $\theta$ are constant thresholds given as input.

The problem is well studied, with many algorithms developed for it, such as Sticky Sampling, Lossy counting, Batch decrement, and Space Saving. The last two are optimal, in the sense that they require $O(\frac{1}{\epsilon})$ counters and have constant runtime.

I'm looking for an algorithm for a weighted variant of the problem:

Every item in the stream is of a tuple $(id, weight)$, and the goal is the return the elements with the highest weight. All weights are in $(0,1]$.

Formally, a weighted heavy hitters algorithm is required to return all elements whose sum of weights is at least $W\theta$, and no element with weight lower than $W(\theta-\epsilon)$, where $W$ is the sum of weights of the stream elements.

  Are there known (preferably deterministic) algorithms for this problem that use $O(\frac{1}{\epsilon})$ counters and have $O(1)$ runtime?

Batch Decrement and Space Saving does not seem to have a simple generalization to the weighted case, as both maintain a data structure that allows finding the minimum counter in constant time, which might not be doable in the weighted setting.

Here's a generic randomized solution. (Do we even have deterministic solutions in the unweighted case? Don't Space Saving and Batch Decrement both need hash maps?)
This is probably not the ideal solution, but it's a start.

Weighted Heavy Hitters Algorithm.
Input: $S=\{(\text{id}_i,\text{weight}_i)\}_{i=1}^N$ a weighted stream.

1. Create an unweighted stream $S'=\{\text{id}_j\}_{j=1}^{N'}$ as follows. For every weighted update $(\text{id}_i,\text{weight}_i)$ in $S$, include the unweighted update $\text{id}_i$ in $S'$ independently with probability $\text{weight}_i$.

2. Apply an unweighted heavy hitters algorithm (i.e. Space Saving or Batch Decrement) to $S'$ and output the heavy hitters for $S$.

Clearly this algorithm has $O(1)$ update time. To verify that this algorithm is correct we must prove the following claim.

Claim. With high probability, for every $\text{id}$, the count of $\text{id}$ in $S'$ is close to the sum of the weights of $\text{id}$ in $S$.

Let $w_\text{id}$ be the "true" weight of $\text{id}$ in $S$ and $W_\text{id}$ the weight of $\text{id}$ in $S'$. Let $w=\sum_\text{id} w_\text{id}$ be the total weight of $S$ and $W=\sum_\text{id} W_\text{id}$ be the total weight of $S'$.

Our claim is that $|W_\text{id}-w_\text{id}| \leq \varepsilon w$ for all $\text{id}$ with high probability.

Clearly $\mathbb{E}\left[W_\text{id}\right]=w_\text{id}$. It remains to show concentration bounds. To this end, we use the following result.

Bernstein's Inequality. Let $X_1, \cdots, X_n \in \{0,1\}$ be independent random variables. Then $$\mathbb{P}\left[ \left| \sum_{i=1}^n X_i - \mathbb{E}\left[X_i\right] \right| > t \right] \leq 2 \cdot \exp\left(-\Omega\left(\frac{t^2}{t+\sum_{i=1}^n \mathsf{Var}\left[X_i\right]}\right)\right)$$ for all $t > 0$.

Thus  $$\mathbb{P}\left[ \left| W_\text{id}-w_\text{id} \right| > \varepsilon w \right] \leq 2 \cdot \exp\left(-\Omega\left(\frac{\varepsilon^2 w^2}{\varepsilon w+w_\text{id}}\right)\right) \leq 2 \cdot \exp\left(-\Omega\left(\varepsilon^2 w\right)\right).$$

Note that if $w_\text{id}=0$, then $W_\text{id}=0$. So we need only consider the $\text{id}$s that appear in the stream. In particular, we can take a union bound over at most $N$ $\text{id}$s:

If $w \geq O\left(\log(N)/\varepsilon^2\right)$, then the weights in $S'$ are close to the weights in $S$ with high probability and the claim is verified.

What about when $w \leq O\left(\log(N)/\varepsilon^2\right)$? Then we can first repeat each weighted update $T$ times. This increases the weight to $Tw$. The good news is that $S'$ is only length $O(Tw)$ and transforming $S$ into $S'$ takes $O(1 + Tw/N)$ (amortized) time per update with high probability. So we just need to find a $T$ with $ O\left(\log(N)/\varepsilon^2\right) \leq Tw \leq O(N)$.


The Goemans-Williamson algorithm in the $SOS$ framework If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, where $L = I - A/d$, equals $4E(S,\bar{S})/d$. So trying to maximize $\langle x,Lx \rangle$ over $x \in \{1,-1\}^{|V|}$ maximizes the number of edges crossing across the cut, $(S,\bar{S})$.

With this set-up the Goemans–Williamson algorithm is stated in the sum-of-squares (SOS) literature as the claim that there exists a polynomial-time algorithm such that one can output a vector $z \in \{ \pm 1 \}^{\vert V \vert }$ such that $\langle z,Lz \rangle \geq 2n(1-f_{GW}(\epsilon))$ where $f_{GW}(\epsilon) \leq 10\sqrt{\epsilon}$ provided one is given a degree-2 pseudo-distribution such that $\tilde {\mathbb{E}} [x_i ^2] =1, \tilde {\mathbb{E}} [\langle x, Lx \rangle ] \geq 2n(1-\epsilon)$

So naturally the question arises as to from where does one get such a degree-2 pseudo-distribution? The implicit claim seems to be that there exists a "degree-2 SOS algorithm" which when run on these constraints $\{ x_i^2 =1, \langle x, Lx\rangle = 2n(1-\epsilon)\}$ will generate this "degree-2 pseudo-distribution". This apparently seems to be set up to be a semidefinite programming (SDP) question and hence one basically has to solve a SDP to get this pseudo-distribution!

So what is the advantage of the SOS point of view here if one has to anyway run a SDP to get this degree-2 pseudo distribution?
Also can someone point out an explicit reference about what exactly is this "degree-2 SOS algorithm" which will run on these constraints to give me the "degree-2 pseudo-distribution"?

Looking at the Goemans–Williamson algorithm in the SOS framework yields no technical advantages: it is exactly the same algorithm and the same ideas are used in the analysis.
The only advantages in doing so are:

Arguably the algorithm seems less "magical" in that viewpoint, though of course that's a matter of taste.
It's a good basic case to get intuition for the SOS framework, and so understanding this algorithm will help in understanding more complicated uses of it.

As Sasho Nikolov points out, a degree 2 pseudo-distribution is simply a positive semidefinite (PSD) matrix, and so finding such a matrix satisfying any particular linear constraints can be done via semidefinite programming. In particular, for any pseudo-distribution $\{ u_i \}_i$ of degree at least 2, the matrix $X_{i,j} = \tilde{\mathbb{E}} u_i u_j$ is PSD.

Given an $n\times n$ PSD matrix $X$, one can find a Gaussian distribution $y\in\mathbb{R}^n$ such that $\mathbb{E} y_iy_j = X_{i,j}$ for all $i,j$ and hence the distribution $\{ y_i \}_i$ matches the second moments of the pseudo-distribution represented by $X$. (One can obtain $y$ by sampling a standard Gaussian vector $z$ and letting $y=X^{1/2}z$.)

The rounding algorithm is to obtain a distribution $w$ over $\{\pm 1\}^n$ by letting $w_i = \textrm{sign}(y_i)$. This is exactly equivalent to the standard description of "hyperplane rounding" whereas one takes vectors $v_1,\ldots,v_n$ such that $X_{i,j} = \langle v_i,v_j \rangle$ and lets $w_i = \textrm{sign}(\langle v_i , z\rangle)$ where $z$ is a random Gaussian vector.

Now we want to compare the value of the pseudo-distribution, which (up to scaling) is the same as the sum of $-X_{i,j}$ over all edges $(i,j)$, with the expected value of our rounded solution $w$, which will be the sum of $- w_iw_j$. So now we want to calculate the probability that the edge will be cut by $w$ as a function of $X_{i,j}$. It all boils down to figuring out the following calculation: if $w_i$ and $w_j$ are two Gaussian random variables with $\mathbb{E} w_i^2 = \mathbb{E} w_j^2 = 1$ and  $\mathbb{E} w_i w_j = \rho$, what would be the probability that their signs agree? I personally think that the most interesting regime for Max-Cut is when the objective value is close to $1$. One nice thing in that regime is that you can get some qualitative insight by showing that if $\rho = -1 +\epsilon$ then their signs agree with probability at most $O(\sqrt{\epsilon})$. However, if you are interested in figuring out the approximation ratio (or more generally figure out the precise trigonometric function behind this $O(\cdot)$ term) then Goemans–Williamson's analysis exactly resolves this calculation.


Algorithms in preprocessed universe In celebrated paper Clustered integer 3SUM via additive combinatorics by TM Chan and M Lewenstein one of the provided algorithms is the one for preprocessed universe.   They were able to provide an algorithm with running time $O(n^{13/7})$ for solving 3-Sum on the subset of the universe of size $n$, assuming some preprocessing was allowed.

What other examples of such algorithms in preprocessed universe do you know?

As Ricky Demer said in his comment, many search problems can be sped up with sorting or building some other index structure
Lowest common ancestor queries can be answered in constant time with linear preprocessing.
Lots of text problems can be sped up with some preprocessing, e.g. building a suffix array


What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages? It is unknown whether $P\subseteq CSL$ or $P\not\subseteq CSL$, where

$P$ is the set of all languages decidable in polynomial time on a deterministic Turing machine, and
$CSL$ is the class of context-sensitive languages, known to be equivalent to $NSPACE(O(n))$, the languages decided by linear-bounded automata.

For many open questions, there is a tendency towards one answer (a la "most experts believe that $P\neq NP$"). Is there something like this for this question?

In particular, would either answer have unexpected consequences? I can only see expected (but unproven) consequences:

If $P\subseteq CSL$, then $P\subseteq NSPACE(O(n))\subsetneq NSPACE(O(n^2))$ (space hierarchy theorem), hence $P\subsetneq PSpace$.
If $P\not\subseteq CSL$, then there is a language $l\in P\setminus NSPACE(O(n))$ and therefore $l\in P\setminus NL$, hence $NL\subsetneq P$.

(Acknowledgement: The second consequence of these two was pointed out by Yuval Filmus at https://cs.stackexchange.com/questions/69614/)

If $\mathrm{P\subseteq CSL}$, then $\mathrm{P\subseteq DSPACE}(n^2)$. By a padding argument, this implies
$$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}\bigl(t(n)^\epsilon\bigr)$$
for every superpolynomial well-behaved function $t(n)$ and every $\epsilon>0$. I believe such a strong advantage of space over time is not expected to be true. The best currently known result in this direction is
$$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}(t(n)/\log t(n)),$$
due to Hopcroft, Paul, and Valiant.


Relationship between shift-reduce parsing and delimited continuations? Has anyone formalized the relationship between shift-reduce parsing techniques and delimited continuations?

When constructing a bottom-up parser (eg, LR parsers), we take a grammar and then represent parse states as sets of items: augmented productions of the form $A \to \alpha \bullet \beta$, where $\alpha$ and $\beta$ are sequences of terminals and nonterminals. The marker $\bullet$ represents how far the parser has gotten into the string, with $\alpha$ representing what has been seen so far, and $\beta$ representing a prediction of what yet may be parsed.

A shift action in a transition of the LR parse automaton matches a prefix of the stack against $\alpha$, and replace it with $A$. Such a deep manipulation of the stack resembles the effect of a control operator, but this is just a qualititative observation.

Has anyone studied the connection between shift-reduce parsing and delimited control operators such as shift/reset?

I believe that the following paper explores some of this connection, mostly by using continuations to backtrack when things happen in parsers.  But there's definitely more to do here.

  Modular rollback through control logging: A pair of twin functional pearls

  Olin Shivers, Aaron Turon, ICFP 2011.


The SQ argument in Balazs Szorenyi's paper I am asking about the proof in Theorem 5 (page 6) of this paper,
http://www.inf.u-szeged.hu/~szorenyi/Cikkek/sq_d0_ext.pdf
Quite a few things about this short argument seem unclear to me,

Towards the bottom of page 3 when the SQ oracle was defined it seemed that for a tolerance parameter of $\tau$ and the true concept being $f^*$ and a query concept of $h$ the SQ oracle is guaranteed to return a $c$ s.t $\vert c - \langle f^*,h \rangle \vert \leq \tau$. Now in the proof of Theorem 5 (page 6) there is no $f^*$ that has been mentioned! So is there an implicit assumption about what this $f^*$ is?
Are we assuming that this $f^*$ is a part of this uncorrelated set, $\{f_1,f_2,..,f_d\}$?

The argument in Theorem 5 seems to assume that the adversarial oracle can return $c=0$ always. But why should this be a consistent option given that the oracle is forced to satisfy the condition, $\vert c - \langle f^*,h \rangle \vert \leq \tau$. If $c=0$ has to always be a consistent oracle reply then we need it to be true that all queries $h$ being made are such that it satisfies the equation, $\vert\langle f^*,h \rangle \vert \leq \tau$. But now this is a new constraint that the queries $h$ have to be of somewhat low correlation with the truth $f^*$!. But this wasnt specified anywhere!
At this point it seems that the algorithm could be lucky and it could send to the Oracle the query $h = f^*$ and then if $c=0$ has to be a valid adversarial reply we need $\tau \geq 1$ and that doesnt make sense!

Lastly what else is the SQ algorithm allowed to do apart from making $(h,\tau)$ SQ-queries? Are we forcing it to work s.t after it receives $c=0$ as the Oracle reply all its allowed to do is to eliminate from its set of probable outputs those functions in the set $\{f_1,..,f_d\}$ which are more than $\tau$ correlated? Why is it that the SQ algorithm never seems to consider that there could be functions in ${\cal F}$ outside this uncorrelated set which are also more than $\tau$ correlated to the query $h$?

This is a standard adversary argument, not very different from adversary arguments taught in undergraduate algorithms courses. If you are unfamiliar with such arguments, then you can check out these notes by Jeff Erickson.

The idea for the proof is that the SQ oracle is controlled by an adversary, and the adversary does not have to initially commit to a specific $f^*$. Instead, the adversary always makes sure that some $f^*$ is consistent with the oracle answers. In Szorenyi's paper, the adversary will make sure that there is always some $f_i$ which is consistent with all of the query answers. More precisely, let $\cal G$ be the set of all $f_i$ which are consistent with answering $0$ to all queries so far. If no queries have been answered yet, then $\mathcal{G} = \{f_1, \ldots, f_d\}$. Szorenyi shows that answering a new query by $0$ decreases $|\cal G|$ by at most $2d/(d\tau^2 - 1)$, so as long as $|\mathcal{G}| > 2d / (d\tau^2-1)$, the adversary can keep answering queries by $0$ and $\cal G$ will remain non-empty. Moreover, while this is true, the algorithm cannot stop and output an answer, because any possible concept it outputs will have correlation less than $\tau$ with $|\mathcal{G}| - d / (d\tau^2-1)> 0$ many concepts in $\mathcal{G}$. But any concept in $\mathcal{G}$ could be $f^*$, and the algorithm would output the wrong answer for at least one such possible $f^*$.

Another way to see the last point is the following. Suppose that the algorithm outputs something while $|\mathcal{G}| > 2d / (d\tau^2-1)$. Then take an element of $\cal G$ that has correlation less than $\tau$ with the algorithm's output, and call it $f^*$. Rerun the whole process again with the oracle always outputting $0$: all the oracle answers are consistent with $f^*$ (by the construction of $\cal G$) and the algorithm would produce the same output, but that output would be incorrect for $f^*$. Note that this assumes that the algorithm is deterministic.

One detail he doesn't mention is that once $|\mathcal{G}| \le 2d / (d\tau^2-1)$, the adversary can pick some $f^* \in \mathcal{G}$ and answer new queries in any way consistent with $f^*$. This doesn't matter much in the proof because it can only happen once $(d\tau^2 - 1)/2$ queries have been made.


Is there a good notion of non-termination and halting proofs in type theory? Constructive type theory with its basic interpretation under the curry howard correspondence consists only of total, computable functions. In the literature, some has been said on using "computational type theory" in order to represent non-termination in functional programs, yet in the papers I have come across, this does not seem to be the major motivation for the theory (For example Benton mentions non-determinism, continuations, and exceptions, without going into much detail on non-termination), so I have yet to find a paper giving a robust interpretation of non-termination using computational type theory.

Specifically, what I am looking for is a way that given a type representing a possibly non terminating computation of type $A$, $T(A)$, there should be some notion of proofs that $x : T(A)$ terminates of type $H(x)$, such that given $x:T(A)$ and $p:H(x)$, we can construct a term $\tilde x : A$.

My motivation for this is, I'd like to eventually be able to more formally relate notions in computational complexity theory to constructive type theory. Specifically, I am interested in what power as a formal theory constructive types gain with access to a halting oracle, and in order to do so, I of course need to actually have a formal notion of possible non-termination, and proofs of halting to go along with it inside a type-theoretic framework.

Because one of the principal applications of Type Theory in formalizations has been to study programing languages and computation in general, a lot of thought has gone into ways of representing possibly non-terminating programs.

I won't make a complete survey here, but I'll try and give pointers to the main thrusts of different directions.

The "relational" approach: you can define your hypothetical programs as relations say, $F\ x\ y$ which holds iff $f$ is defined at $x$ and $f(x)=y$. This is usually what is done with the Kleene T-predicate. This works just as well in type theory formalizations as it does in classical logic, (though of course you can't prove $\forall x (\exists y, F\ x\ y)\vee (\neg\exists y, F\ x\ y)$).

A more sophisticated way to do this is the "Bove-Capretta" method (see Modelling Recursion in Type Theory, which for each recursive function, defines an "accessible predicate" which encodes the fact that a given computation is finite. The function definition takes an extra argument which is a proof that the given inputs are accessible. To define the function without this extra predicate, you need to prove that every possible combination of inputs is accessible.
The "coinductive" approach: this is possibly the most explored approach, and what Andrej's comments refer to. A computation of type $A$ is defined as the inductive type (from Andrej's link, by Capretta, Altenkirch & Uustalu:

codata Delay A =
| Now : A -> Delay A
| Later (Delay A)

This codes a possibly infinite stream of Later tokens ("ticks" of computation) maybe ending with a result Now a. Non-termination is equivalent to being bisimilar with the program

loop = Later loop
and termination can be defined by an inductive predicate over Delay A:

data Terminates : Data A -> Prop =
| Term_now : forall x, Terminates (Now x)
| Term_later : forall d, Terminates d -> Terminates (Later d)

I think the agda-istas have a lot to say about this which they call the partiality monad (see e.g. Danielsson).
The "partial type theory" approach: this is a bit more experimental (the theory is still being worked out), but there are some type theories that are being developed to cope with the fact that there are essentially two types of functions we want to write in type theory: the proof terms and the programs. It turns out to be tough to get a reasonable theory of these things (and retain consistency of the theory), but a serious attempt is made here by Casinghino et al, and a similar effort by Kimmel et al.

I'm sure there are other approaches I'm not aware of, and I'd be happy if someone wants to complete this list.

I should probably note that adding a termination oracle to a (consistent) type theory is a lot like adding a truth oracle for $\Pi^0_1$ sentences, with relatively well understood consequences.

There are other, quite fruitful interactions between type theory and complexity theory, usually under the umbrella of implicit computational complexity.


Partition refinement in transition state systems (bisimulation contraction) I am trying to understand bisimulation contraction of Kripke models.

I have read these lecture slides and this Wikipedia page, but I still don't fully understand it.

I can understand that the two models below are bisimilar

In the lecture slides, the partition refinement algorithm is given as

I do understand that from the graph on the left in the first picture, the initial partition becomes

initial_partition = {
  'p': ['n1', 'n2'],
  'q': ['n3', 'n4']
}

because two of the nodes have $p$ and the two remaining nodes have $q$.

But now I need to understand the second step in the algorithm. It seems to me that I should first loop through each of the two blocks in the initial partition, and for each node check its relations to nodes in the other blocks in the initial partition.

Can someone give me an example of a larger model (more nodes), and show me the steps in reducing the larger model to a smaller model, or give me a hint on where to find literature about it where it is described more easy?

Edit

What I mean is that the model in the middle of this picture

shows the first partition, but I don't know what the next partition look like, and why I can suddenly remove two of the nodes.

From both states in $\{n_1,n_2\}$, action $\pi_1$ takes you to $n_2$, while action $\pi_2$ takes you to states in $\{n_3,n_4\}$.  Hence no refinement of that block takes place.  The second block doesn't refine either; therefore the partition refinement terminates.

At this point you have proved that $n_1$ and $n_2$ are bisimilar and $n_3$ and $n_4$ are bisimilar.  You have computed the maximal bisimulation relation on the states of the given structure.  You then proceed to build a quotient structure, with one state for each equivalence class of the bisimulation relation.

This seems to be the part that puzzles you, but it's really simple: it's just another step in the procedure.  The upper state of the result represents the equivalence class $\{n_1,n_2\}$.  Unsurprisingly, action $\pi_1$ takes you back to that state, and so on.  In general, all states in one block of the partition agree on the block containing the destination state of transitions labeled by a certain action.  Hence constructing the quotient structure is straightforward.

A state of the quotient structure is an initial state if and only if at least one state of its equivalence class is initial.  Then, the structure you build is bisimilar to the one given.

Note that I've used "bisimilar" in two related, but slightly different ways here: bisimilar states, and bisimilar structures.  In this example, first we compute a bisimulation relation on the states of the original structure, then we build a structure that is guaranteed to have the following property: the maximal bisimulation on the states of the two structures matches each initial state of one structure to at least one initial state of the other structure.  A structure with this property is said to be bisimilar to the original one.


What else (besides the usual) can be said about a Scott Information System if the constructed domain is required to be Hausdorff? As per subject, if a Scott domain with $T_2$ topology is to be constructed from a Scott information system, then what besides the usual definitional requirements, e.g., https://en.wikipedia.org/wiki/Scott_information_system , does the information system have to satisfy?

Information systems are more completely discussed in (Scott's original paper) https://www.researchgate.net/publication/220897586_Domains_for_Denotational_Semantics (note: the original paper is followed by a three-page bibliography missing from this pdf) containing a section "Topological Considerations" starting on page 586, where "Hausdorff" is briefly mentioned on page 588 with respect to (what Scott calls) "total elements", $Tot_A$, assuming no unique top. But the domain itself, what Scott calls $\mid A\mid$, is still $T_0$ in general. And I'm asking for additional definitional requirements so that $\mid A\mid$, when contsructed from the corresponding information system, is "automatically" $T_2$.

Since the least element $\bot$ of any Scott domain is a compactification point $-$ the only open set containing it is the whole space $-$ the Scott topology is never Hausdorff, unless it is trivial.

An information system $(A,Con,\vdash)$ induces a trivial domain iff it is itself trivial: $Con = \{\emptyset\}$.  Otherwise, there exists at least one point above $\bot$.

The total elements of the Scott domain can indeed be given their own topology sometimes, which may be $T_2$ or even metrizable.


Lower bounds for linear satisfiability problem In SODA 1995, Jeff Erickson showed lower bounds for linear satisfiability (checking if a some $r$-subset of $n$ real numbers satisfies a linear equation on $r$ variables). The proof method uses infinitesimals and Tarski's transfer principle.

Could someone explain the intuition behind the route taken to prove this bound ? What is the difficulty in coming up with a direct proof like this: "Given a decision tree which takes real numbers, here's how we can construct an adversarial input" ?

I strongly suggest reading the more recent followup paper by Ailon and Chazelle, which avoids the whole infinitesimal issue entirely.  If you want to stick with my paper, please read the journal version (Chicago J Theoretical Computer Science 1999).  The SODA version has a major bug in Section 5, and (I think) the journal version explains the main proof much more clearly.


Minimize a datalog program We can consider a datalog program as a set of clauses. Some of them allow to derive others. For instance from:

A(x) :- B(x), C(x).
B(x) :- D(x).
C(x) :- D(x).

We can derive:

A(x) :- D(x).

Given a datalog program, a minimal equivalent datalog program is a subset of the given program with the smallest number of clauses that allows to derive the full datalog program. Minimal equivalent datalog program is not unique at least in the presence of cycles. Finding any of them is enough; I don't need to find them all.

The clauses contain no disjunctions, only an implication and an atom in the head. Alternate definition: clauses are composed by disjunctions (no conjunctions) and there is only one non-negated predicate. All predicates are unary or binary, and contain variables or constants. There may be recursion, and it may be limited to unary predicates.

I'm searching for an algorithm that allows to find this minimal datalog program for a given program, but I could not find it. It may just be a matter of not using the correct terms, or maybe my confusion is deeper. In any case this seems a fundamental problem when working with datalog and my guess is that it was solved decades ago.

Do you know any algorithm for this? Should I use a different terminology?

Thank you.

PD: a more enticing example that allows greater optimization:

A(x):- I(x).        B(x):- P(x,y).      P(x,y):- T(x,y).
A(x):- C(x).        G(x):- L(x).        P(x,z):- T(y,x).
A(x):- R(x,y).      H(x):- P(x,y).      P(x,z):- U(y,x).
A(x):- R(y,x).      H(x):- T(x,y).      P(y,x):- T(x,y).
D(x):- A(x).        I(x):- J(x).        P(z,x):- R(y,x).
D(x):- T(y,x).      I(x):- T(x,y).      R(x,y):- T(x,y).
E(x):- I(x).        C(x):- K(x).        R(y,x):- T(x,y).
E(x):- R(x,y).      C(x):- R(x,y).      S(x,z):- T(x,y).
F(x):- A(x).        C(x):- T(y,x).      S(x,z):- R(x,y).
F(x):- H(x).        C(x):- U(x,y).      S(y,x):- T(x,y).
F(x):- R(y,x).      J(x):- K(x).        S(y,x):- U(x,y).
B(x):- D(x).        J(x):- R(x,y).      T(y,x):- U(x,y).
B(x):- C(x).        K(x):- U(x,y).      U(x,z):- R(x,y).
B(x):- J(x).        L(x):- R(y,x).      U(x,z):- P(x,y).
B(x):- L(x).

I was calculating the result manually, but I think I can do it with an algorithm, it's going to take a while.

PD: I found this: A. Pettorossi and M. Proietti, “Transformation of logic programs: Foundations and techniques,” The Journal of Logic Programming, vol. 19–20, Supplement 1, pp. 261–320, May 1994.

There does not seem to be a general algorithm.

Checking whether two Datalog programs are equivalent (in the sense of producing the same output database for every possible input database) is undecidable.  The containment problem, of checking whether one Datalog program always produces all the tuples of the other (plus possibly some others), is also undecidable.  So there is no general algorithm for verifying the output of your proposed minimization algorithm.  One can generate all syntactically valid Datalog programs up to the size of the input Datalog program, but there is no general way to check whether these are equivalent to or even implied by the original Datalog program.

Oded Shmueli, Equivalence of Datalog queries is undecidable, The Journal of Logic Programming 15(3) 231–241, 1987.  doi: 10.1016/0743-1066(93)90040-N

What you perhaps mean is minimization over all Datalog programs made up only of the terms that occur in the original program, such as the $A(x) \leftarrow D(x).$ example you provided above.  This is a restricted form of Datalog containment, since one only wants to check containment between syntactically closely related Datalog programs.  It is not obvious to me whether this restriction makes the problem decidable or not, although there may be some related work, perhaps in the rewriting systems or finite automata communities.

Restricting the problem somewhat, one can try to find an equivalent minimal non-recursive Datalog program.  Unfortunately checking for equivalence between a recursive and a non-recursive Datalog program requires time that is triply exponential in the size of the programs, and checking whether the recursive program is contained in the non-recursive one requires doubly exponential time.  Moreover, these algorithms require constructing exponential-sized tree automata, so are probably not feasible for actual implementation.

Surajit Chaudhuri and Moshe Vardi, On the Equivalence of Recursive and Nonrecursive Datalog Programs, JCSS 54(1), 61–78, 1997. doi: 10.1006/jcss.1997.1452 (preprint)

Finally, consider really simple Datalog programs, where there are only two unary predicates $T(x)$ and $F(x)$, such that $T(x) \equiv \lnot F(x)$.  In other words, each variable must take either the value "true" or "false".  Each such Datalog program then corresponds to a Horn formula, a universally quantified conjunction of Horn clauses.  The minimization problem for these highly restricted Datalog programs is still NP-hard, and also likely to be hard to approximate.

Amitava Bhattacharya, Bhaskar DasGupta, Dhruv Mubayi, and György Turán, On Approximate Horn Formula Minimization, ICALP 2010, doi:10.1007/978-3-642-14165-2_38 (preprint)

The authors mention some prior work on efficient algorithms for restricted cases, such as quasi-acyclic Horn formulas and for approximation in terms of the number of different variables in the formula.

You might also be interested in the literature on finding shortest implicants.


The complexity of checking whether two CNF have the same number of solutions Given two CNF, if they have the same number of assignments to make them true, answer "Yes", otherwise answer "No".

It is easy to see it is in $P^{\#P}$, since if we know the exact numbers of solutions to these two CNF, we just campare them and answer "Yes" or "No".

What is the complexity of this problem?

The problem is coNP-hard; you can easily reduce the UNSAT problem to this problem.

A more precise characterization is that the problem is C=P-complete.  In fact, one definition of the class C=P is that it is the class of problems which are polynomial-time many-one reducible to this very problem (usually this definition is stated in terms of GapP functions).  But since this does not tell much, let me define this class in another way.

Let C=P be the class of problems which are polynomial-time many-one reducible to the following problem: given a boolean circuit φ and an integer K (in binary), decide whether the number of satisfying assignments of φ is equal to K.  By a standard reduction which shows the #P-completeness of #3SAT, we can restrict φ to be a 3CNF formula without affecting the class.  The class C=P contains a class called US, which contains both UP and coNP.

With this definition, your problem is C=P-complete.  Actually, the C=P-hardness is easy to see from the definition of the class C=P (which uses 3CNF formulas).

To prove the membership in C=P, suppose that we are to decide whether two given CNF formulas φ1 and φ2 have the same number of satisfying assignments or not.  Without loss of generality we can assume that the two formulas have the same number of variables, say n.  Construct a boolean circuit φ which takes n+1 bits as input so that the number of satisfying assignments of φ is equal to c1 + (2n − c2), where c1 and c2 be the numbers of satisfying assignments of φ1 and φ2, respectively.  Then the number of satisfying assignments of φ is equal to 2n if and only if c1=c2.


Density of answers for NP complete problems? There is a result which goes along the lines of:

  Definition: For every language $L$, define $L_n = \{ w \in L \mid \text{length}(w) = n \}$, i.e. the subset of $L$ of words whose length is $n$.

  Theorem: If $\mathbf{P} = \mathbf{NP}$, then for every $\mathbf{NP}$-complete language $L$ there exists a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$ such that for every integer $n$ it is the case that $|L_n| \leq p(n)$.

The intuition of the theorem is that if $\mathbf{P} = \mathbf{NP}$, then $\mathbf{NP}$-complete languages have a polynomial density of solutions.

As we believe that $\mathbf{P} \neq \mathbf{NP}$, we should tend to believe the contrary, i.e. that $\mathbf{NP}$-complete problems do not have a polynomial density of solutions.

Example: For the case of 3-coloring, for large $n$ there are many 3-colorable graphs with $n$ nodes; in any case, the number of 3-colorable graphs is not bounded by a polynomial.

Does anyone recognise this result? What is the actual statement of the theorem? Any reference would be welcome!

You are defining what is known as sparse sets. Mahaney's theorem states that sparse $NP$-complete (under Karp reduction ) sets exist if and only if $P=NP$. So, your theorem is just one direction of that theorem.


General Induction Principle Let us suppose that we want to provide for each inductive type an axiom describing the associated elimination/induction principle. For example, given a definition for the naturals:

inductive nat : Prop ≝
  O : nat
| S : nat → nat.

We may provide for them the following definition of an elimination function:

$\texttt{let rec nat_ind(x) := }\\
\quad\forall Q:nat\to Prop. \\
\quad\forall C_1: (Q\; O). \\
\quad\forall C_2: (\forall x:nat. Q x \to Q (S x).\\
\quad\quad (\texttt{x}\equiv O\Rightarrow C_1) \\
\quad\quad  \vee (\exists y:nat. x\equiv S y \Rightarrow \Big(C_2\; y\; (\texttt{nat_ind(}y\texttt{)}\;Q\;C_1\;C_2)\Big)
$

Can this formulation be trivially extended for each constructor by simply adding a $C_i$ for an additional inductive case? If not, where can I look for a  general definition of the elimination axiom that can be applied to any inductive type expressible ine a CoC/CIC dependent type system extending $\lambda Pw$, from Falsehood to Leibniz Equality? I.e., how does a theorem prover generates the elimination for inductive types?

Can this formulation be trivially extended for each constructor by simply adding a Ci for an additional inductive case?

Yes. I can't provide a general nor a technical answer, but a while ago I was trying to solve a similar problem and someone helped me by providing a visualization of the general procedure. This helped me a lot, so I'll reproduce it here in the case it helps you too.

Generating the elimination principle

Given an inductive type of the form (using Agda syntax):

data Foo : (index_0 : I_0) -> ... (index_N : I_N) -> Set where
  ctor_0 : (field_0 : F_0) -> ... (field_N : F_N) -> ret_0
  ...
  ctor_N : (field_0 : F_0) -> ... (field_N : F_N) -> ret_N

Its elimination is, generally, in that form:

let Foo_match =

    -- Index arguments
    (index_0 : I_0) -> ...
    (index_N : I_N) ->

    -- Scrutinee
    (X : Foo index_0 ... index_n) ->

    -- Motive
    (P :
      (index_0 : I_0) -> ...
      (index_n : I_N) ->
      (witness : Foo I_0 ... I_N) ->
      Set) ->

    -- Constructor arguments
    (ctor_0 :
        (field_0 : F_0) -> ...
        (field_N : F_N) ->
        ret_0[Foo/P] (ctor_0 field_0 ... field_N)) ->
    (ctor_N :
        (field_0 : F_0) -> ...
        (field_N : F_N) ->
        ret_N[Foo/P] (ctor_N field_0 ... field_N)) ->

    -- Result type
    P index_0 ... index_N X

Where [Foo/P] means we replace the constructor type by the variable P in ret_N.

Example

If our type is:

data Vect : (A : Set) -> (n : Nat) -> Set where
  cons : (A : Set) -> (n : Nat) -> (x : A) -> (xs : Vect A n) -> Vect A (succ n)
  nil  : (A : Set)                                            -> Vect A zero

Then we get:

let Vect_match =

    -- Index arguments
    (A : Set) -> ...
    (n : Nat) ->

    -- Scrutinee
    (X : Vect A n) ->

    -- Motive
    (P : (A : Set) -> (n : Nat) -> Vect A n -> Set) ->

    -- Constructor arguments
    (cons :
        (A  : Set) ->
        (n  : Nat) ->
        (x  : A) ->
        (xs : Vect A n) ->
        P A (succ n) (cons A n x xs)) ->
    (nil :
        P A zero nil) ->

    -- Result type
    P A n X

Note: I've not included parameters, but they're trivial. They work like indices, except they're not included on the constructors. I've also not included the inductive argument, so this is not actually the elimination principle, just total pattern-matching. You can get induction by applying Foo_match recursively to sub terms. Problem is I don't remember out of my head its shape, but someone is welcome to edit in.


Recursively enumerable, non-recursive language without using Gödel's number I am trying to find out if there exists a language, which is recursively enumerable but not recursive, but which wouldn't also use Gödel's number or any other kind of Turing machine description in its definition. The language should be possible to somehow "easily" describe. ("Easily" being purely subjective, I know.)

But each one I try to construct is either recursive or not recursively enumerable.


What is the VC dimension of Turing machines with specified maximum size? Note by "maximum size" in the question I'm referring to the size of the Turing machine's state machine.

I chose Turing machines in the question to make the question concrete, but I'm also more generally interested in known VC bounds for Turing-complete languages with a limit on the program length (to avoid infinite vc dimension).

The closest I've seen is this article giving VC dimension for recurrent neural nets, which can be Turing complete, but have finite VC dimension in terms of the number of weights and the length of the inputs.

The exact VC bounds will depend on the alphabet size and the exact specification of the transition function (must it always move left or right, or can it stay put, etc). For fixed alphabet size, say 2, I think you can apply the DFA-VCdim analysis of

  Ishigami and Tani, VC-dimensions of finite automata and commutative finite automata with $k$ letters and $n$ states, Discrete Applied Mathematics 74 (1997), no. 3, 229-240

to show that the VC-dim of $n$-state TM's will be $\Theta(n\log n)$.

Those other VC bounds you mentioned in terms of the NN connection weights are more in the spirit of SVM bounds in terms of the norm of the separating hyperplane.

Update: Here's a proof sketch. For a fixed alphabet size (say, 2) and $n$ states, there are $n^{cn}$ transition functions from (state,letter) to (state,letter,head move), where $c$ is a universal constant. Taking logs gives you a VC upper estimate of $O(n\log n)$. The lower bound comes from the Ishigami-Tani analysis, since an $n$-state DFA can be realized as an $n$-state TM (plus $n$ additional bits to indicate which states are accepting, but this is negligible compared to the $n^{cn}$ factor).


Wikipedia-style explanation of Geometric Complexity Theory Can someone provide a concise explanation of Mulmuley's GCT approach understandable by non-experts? An explanation that would be suitable for a Wikipedia page on the topic (which is stub at the moment).

Motivation: I am "co-reading" Scott Aaronson's book Quantum Computing since Democritus with a friend of mine who is a researcher in string theory. In the preface of the book, Aaronson calls GCT "the string theory of computer science".
Being a string theorist, my friend got excited about this claim and asked me what GCT is. At that point I shamefully realized I didn't have a Wikipedia-ready answer for his question.

I'm not exactly sure what level is suitable for Wikipedia article (different articles seem to be aimed at different levels of expertise) or exactly what you're looking for. So here's a try, but I'm open to feedback.

Geometric complexity theory proposes to study the computational complexity of computing functions (say, polynomials) by exploiting the inherent symmetries in complexity and any additional symmetries of the functions being studied.

As with many previous approaches, the ultimate goal is to separate two complexity classes $\mathcal{C}_{easy}, \mathcal{C}_{hard}$ by showing that there is a polynomial $p$ which takes functions $f$ as inputs (say, by their coefficient vectors) such that $p$ vanishes on every function $f \in \mathcal{C}_{easy}$ but does not vanish on some function $g_{hard} \in \mathcal{C}_{hard}$.

The first key idea (cf. [GCT1, GCT2]) is to use symmetries to organize not the functions themselves, but to organize the (algebro-geometric) properties of these functions, as captured by polynomials such as $p$ above. This enables the use of representation theory in attempting to find such a $p$. Similar ideas relating representation theory and algebraic geometry had been used in algebraic geometry before, but to my knowledge never quite in this way.

The second key idea (cf. [GCT6]) is to find combinatorial (and polynomial-time) algorithms for the resulting representation-theoretic problems, and then reverse-engineer these algorithms to show that such a $p$ exists. This may be taken in the spirit of using Linear Programming (an algorithm) to prove certain purely combinatorial statements.

Indeed, [GCT6] suggests reducing the representation-theoretic problems above to Integer Programming problems, then showing that the resulting IPs are solved by their LP relaxations, and finally giving combinatorial algorithms for the resulting LPs. The conjectures in [GCT6] are themselves motivated by reverse-engineering known results for the Littlewood-Richardson coefficients, an analogous but easier problem in representation theory. In the case of LR coefficients, the Littlewood-Richardson combinatorial rule came first. Later Berenstein and Zelevinsky [BZ] and Knutson and Tao [KT] (see [KT2] for a friendly overview) gave an IP for LR coefficients. Knutson and Tao also proved the saturation conjecture, which implies that the IP is solved by its LP relaxation (cf. [GCT3,BI]).

The results of [GCT5] show that explicitly derandomizing Noether's Normalization Lemma is essentially equivalent to the notorious open problem in complexity theory of black-box derandomization of polynomial identity testing. Roughly how this fits into the larger program is that finding an explicit basis for the functions $p$ that (do not) vanish on $\mathcal{C}_{easy}$ (in this case, the class for which the determinant is complete) could be used to derive a combinatorial rule for the desired problem in representation theory, as has happened in other settings in algebraic geometry. An intermediate step here would be to find a basis for those $p$ that (do not) vanish on the normalization of $\mathcal{C}_{easy}$, which is by construction a nicer algebraic variety -- in other words, to derandomize Noether's Normalization Lemma for DET.

Examples of symmetries of complexity and functions

For example, the complexity of a function $f(x_1, \dotsc, x_n)$ - for most natural notions of complexity - is unchanged if we permute the variables $f(x_{\pi(1)}, \dotsc, x_{\pi(n)})$ by some permutation $\pi$. Thus permutations are symmetries of complexity itself. For some notions of complexity (such as in algebraic circuit complexity) all invertible linear changes of the variables are symmetries.

Individual functions may have additional symmetries. For example, the determinant $\det(X)$ has the symmetries $\det(AXB) = \det(X^{T}) = \det(X)$ for all matrices $A,B$ such that $\det(AB) = 1$. (From what little I picked up about this, I gather that this is analogous to the phenomenon of spontaneous symmetry-breaking in physics.)

Some Recent Progress [this section definitely incomplete and more technical, but a complete account would take tens of pages....I just wanted to highlight some recent progress]

Burgisser and Ikenmeyer [BI2] showed a $\frac{3}{2}n^2$ lower bound on matrix multiplication following the GCT program as far as using representations with zero vs nonzero multiplicities. Landsberg and Ottaviani [LO] gave the best known lower bound of essentially $2n^2$ on the border rank of matrix multiplication using representation theory to organize algebraic properties, but not using representation multiplicities nor combinatorial rules.

The next problem after Littlewood-Richardson coefficients is the Kronecker coefficients. These show up both in a series of problems that is suspected to eventually reach the representation-theoretic problems arising in GCT, and more directly as bounds on the multiplicities in the GCT approach to matrix multiplication and permanent versus determinant. Finding a combinatorial rule for Kronecker coefficients is a long-standing open problem in representation theory; Blasiak [B] recently gave such a combinatorial rule for Kronecker coefficients with one hook shape.

Kumar [K] showed that certain representations appear in the coordinate ring of the determinant with nonzero multiplicity, assuming the column Latin square conjecture (cf. Huang-Rota and Alon-Tarsi; this conjecture also, perhaps not coincidentally, shows up in [BI2]). Hence these representations cannot be used to separate permanent from determinant on the basis of zero vs nonzero multiplicities, though it still might be possible to use them to separate permanent from determinant by a more general inequality between multiplicities.

References
[B] J. Blasiak. Kronecker coefficients for one hook shape. arXiv:1209.2018, 2012.

[BI] P. Burgisser and C. Ikenmeyer. A max-flow algorithm for positivity of Littlewood-Richardson coefficients. FPSAC 2009.

[BI2] P. Burgisser and C. Ikenmeyer. Explicit Lower Bounds via Geometric Complexity Theory. arXiv:1210.8368, 2012.

[BZ] A. D. Berenstein and A. V. Zelevinsky. Triple multiplicities for $\mathfrak{sl}(r+1)$ and the spectrum of the exterior algebra of the adjoint representation. J. Algebraic Combin. 1 (1992), no. 1, 7–22.

[GCT1] K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput. 31(2), 496–526, 2001.

[GCT2] K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties. SIAM J. Comput., 38(3), 1175–1206, 2008.

[GCT3] K. D. Mulmuley, H. Narayanan, and M. Sohoni. Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. J. Algebraic Combin. 36 (2012), no. 1, 103–110.

[GCT5] K. D. Mulmuley. Geometric Complexity Theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether's Normalization Lemma. FOCS 2012, also arXiv:1209.5993.

[GCT6] K. D. Mulmuley. Geometric Complexity Theory VI: the flip via positivity., Technical Report, Computer Science department, The University of Chicago, January 2011.

[K] S. Kumar. A Study of the representations supported by the orbit closure of the determinant. arXiv:1109.5996, 2011.

[LO] J. M. Landsberg and G. Ottaviani. New lower bounds for the border rank of matrix multiplication. arXiv:1112.6007, 2011.

[KT] A. Knutson and T. Tao. The honeycomb model of $\text{GL}_n(\mathbb{C})$ tensor products. I. Proof of the saturation conjecture. J. Amer. Math. Soc. 12 (1999), no. 4, 1055–1090.

[KT2] A. Knutson and T. Tao. Honeycombs and sums of Hermitian matrices. Notices Amer. Math. Soc. 48 (2001), no. 2, 175–186.


Arithmetic circuits with $\min$, $\max$, and average over $[0,1]$ Consider a circuit that takes as inputs numbers in $[0,1]$, and has gates that consist of the functions $\max(x, y)$, $\min(x, y)$, $1 - x$, and $\frac{x+y}{2}$.
The output of the circuit is then also a number in $[0,1]$.

Does anyone know if this model, or a closely related model, has been studied?

Specifically, I'm trying to solve the satisfiability problem for this circuit, namely computing the maximum value that can be attained by this circuit (it indeed attains a maximum, as it represents a continuous function in a compact domain).

Remark: my study of this model is via weighted temporal logics, so any models that relate to the latter might also come in handy.

The satisfiability problem for these circuits  (i.e., given a circuit $C$ and $u\in[0,1]$, decide whether there is an input $x$ such that $C(x)\ge u$) is in NP, and therefore NP-complete by Neal Young’s comment and Peter Shor’s answer.

We can construct a nondeterministic reduction of the problem to linear programming in the following way. Let $\{a_i:i<m\}$ be all nodes of $C$ that are min or max gates (here $m\le n$, where $n$ is the size of the circuit), and let $b_i$ and $c_i$ be the input nodes of gate $a_i$. For every $i<m$, choose one of the two additional constraints $b_i\le c_i$ or $c_i\le b_i$ (there are $2^m$ possible choices in total). When such a choice is fixed, we can simplify the circuit by replacing each $a_i$ with $b_i$ or $c_i$ as appropriate, and the resulting circuit can be described by a system of $n$ linear equations whose variables are the original input variables of the circuit, and additional variables corresponding to nodes of the circuit.

We also include $m$ inequalities stating that the extra constraints are satisfied, inequalities bounding the original input variables to $[0,1]$, and an inequality stating that the output node has value $\ge u$. Then this is a linear program of size $O(n)$ depending on the choice of the extra constraints, and the circuit attains value $\ge u$ iff there exists a choice of the constraints such that the associated linear program has a solution. Since linear programming is in P, this shows that the problem is in NP.

Also note that the optimum value of a linear program is attained at a vertex of the polytope. This means that the denominator of the optimal solution can be expressed as a determinant of a square matrix of dimension $O(n)$ whose entries are constant-size integers, and there are only $O(1)$ nonzero entries in each row, and as such it is bounded by $2^{O(n)}$.

Reductions of this kind are often useful to give upper bounds on the complexity of satisfiability in propositional fuzzy logics (such as Łukasiewicz logic) and related systems. (In fact, the original problem is a minor variant of satisfiability in Łukasiewicz, which would correspond to circuits with $\min(1,x+y)$ instead of $(x+y)/2$.) An overview of related results can be found in Chapter X of the Handbook of Mathematical Fuzzy Logic, Vol. II.


What graph properties only consider neighbours of a node in their calculations? I'm looking for graph properties which only consider neighbours of a node and do not go beyond that. For example, nodes degree only considers neighbours or clustering coefficient also consider only neighbours, but shortest path considers all nodes in the graph. Are there any other property (except node degree and node coefficient clustering) which only considers neighbours of a node in its calculation?

There are several measures like clustering coefficients that sort of satisfy this, such as edge embeddedness. But this looks at the number of neighbours in common to two adjacent nodes.

The property of v being simplicial is an important structural property used in algorithmic graph theory, and is fully characterized by only the neighbourhood of v.

Notice that the two examples you gave are: (1) the number of nodes in v's neighbourhood, and (2) the number of edges in v's neighbourhood. Perhaps You might also be interested in the number of triangles in v's neighbourhood (i.e. the number of K4s that v is in) or perhaps the number of $P_3$s in v's neighbourhood, etc.

Perhaps you could loosen your requirement of locality, or else you will only be asking about properties such as "the number of _ in v's neighbourhood," which might be too limiting.

How about the number of connected components in v's neighbourhood? Something similar to this was used in a recent Kleinberg paper on predicting spouses by looking at Facebook egonets.


Random flows through fixed network A flow network is a directed graph in which each edge has a capacity. A flow through this network is an assignment of a value to each edge that is less or equal to the edge capacity, and such that the net incoming flow to every node balances with the net outcoming flux at that node. Two special nodes are exempted from this last restriction: the source (which can output a net non-zero flux) and the sink (which can receive a net non-zero flux).

There are algorithms to find the maximum net flow from source to sink in such a network (for example, Ford-Fulkerson algorithm).

I am looking for algorithms that generate pseudo-random admissible flows through such a network. Hopefully the space of admissible flows should be sampled as uniformly as possible. What methods are available here?

Not very practical, but you can sample from a the polytope of feasible flows using the well-known random walk techniques, see for example this classical paper by Kannan, Lovasz and Simonovits. These algorithms allow you to sample in polynomial time (in the dimension) from a distribution which is arbitrarily close to uniform in $L_1$ distance.


Definition of matrix-multiplication exponent $\omega$ Colloquially, the definition of the matrix-multiplication exponent $\omega$ is the smallest value for which there is a known $n^{\omega}$ matrix-multiplication algorithm. This is not acceptable as a formal mathematical definition, so I guess the technical definition is something like the infimum over all $t$ such that there exists a matrix-multiplication algorithm in $n^t$.

In this case, we cannot say there is an algorithm for matrix-multiplication in $n^{\omega}$ or even $n^{\omega + o(1)}$, merely that for all $\epsilon > 0$ there exists an algorithm in $n^{\omega + \epsilon}$. Often, however, papers and results which use matrix-multiplication will report their cost as simply $O(n^{\omega})$.

Is there some alternate definition of $\omega$ that permits this usage? Are there any results that guarantee that an algorithm of time $n^{\omega}$ or $n^{\omega + o(1)}$ must exist? Or is the usage $O(n^{\omega})$ simply sloppy?

The matrix multiplication exponent being $\omega$ does not guarantee that there is an algorithm that runs in time $O(n^\omega)$, but only that for each $\epsilon > 0$, there is an algorithm that runs in $O(n^{\omega+\epsilon})$. Indeed if you can find an algorithm that runs in time $O(n^2 \mathrm{polylog}(n))$, then this shows that $\omega = 2$.

You can find the formal definition in the book Algebraic Complexity Theory by Peter Bürgisser, Michael Clausen, Amin Shokrollahi.


Why use two separate tables in cuckoo hashing? I've been reading a number of papers on cuckoo hashing, including several that generalize it by talking about cuckoo hashing with multiple tables, cuckoo hashing with a stash, the (multi)graph-theoretic properties of the cuckoo graph, etc. However, I have not seen any papers discuss why cuckoo hashing typically separates out the slots into distinct tables rather than having one larger table with multiple hash functions indexing into it (though I did come across a set of lecture notes aimed at undergraduates where this simplification is used).

Is there any particular reason for this?

One reason is that when there is only one set of slots, there will be some keys such that $h_1(k) = h_2(k)$.


graph isomorphism given a partial isomorphism Is there an approach to graph isomorphism considering that we are already given a partial isomorphism ?
In particular, it would be interesting to have conditions on this partial isomorphism that makes the problem polynomial.

This question arises from automata theory, where one approach to testing equivalence of two NFAs on alphabet $A$ is to compute their syntactic semigroups $M_1,M_2$ (of exponential size) together with functions $h_1:A\to M_1$, $h_2: A\to M_2$. Testing semigroup isomorphism is hard in the general case, but here we can do it polynomially, because $h_1,h_2$ already give us a partial isomorphism for a set of generators, which is enough.

For graphs, an obvious sufficent condition for such a partial isomorphism to make the problem polynomial would be "containing a covering set" (in the sense each edge contains a vertex in it) . Maybe there are more subtle conditions that would still work ?

Only an extended comment: Lipton et al. proved [1] that if we have access to an oracle that given two graphs on $n$ vertices, reveals a partial map on at least $(3+\epsilon)\log n$ vertices (for some constant $\epsilon > 0$) which is part of an isomorpshism between the two graphs, then we can find the isomorphism in polynomial time.

The theorem deals with finding the isomorphism (the two graphs must  be  isomorphic), and the oracle is obviously called multiple times.

[1] Anna Gál, Shai Halevi, Erez Petrank, and Richard Lipton. 1999. Computing From Partial Solutions. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity (COCO '99). IEEE Computer Society, Washington, DC, USA, 34-.


How to shuffle cards with restrictions? I want as uniformly as possible to pick from all full shuffles such that this additional criterion applied.

For example, i would like to shuffle 4 decks of cards, and make sure:

Any consecutive 4 cards won't come from the same deck.

Surely I can do the fisher-yates-Knuth shuffling first and then filter out bad permutations, but if the restrictions are strong (e.g. any consecutive 2 cards won't come from the same deck), there will be too many failures.

If i don't mind that if it is slightly unbiased, (of course the less bias the better), how should I do?

One way of doing this is to, at each step, draw a random card from all the remaining decks that satisfy the constraints. I would suggest doing this by shuffling all the decks, and then taking the top card from one of the legal decks, picking a deck with probability proportional to the number of cards left in it.

This has the advantages that (a) in the case of no restriction, it is essentially Fisher-Yates-Knuth shuffling, and so gives a completely uniform permutation, and (b) since it favors decks with more cards, it leaves you with a reasonable chance of not ending with a bunch of cards in just one deck.

I suspect this is a reasonably good algorithm to use in practice, depending on what you want it for. However, it is not equivalent to the process of picking a uniform shuffle that satisfies the constraints, as I argue below.

Suppose you just have two decks, and you have $n/2$ cards in each deck for some large $n$. This question is equivalent to choosing a random way of tiling a length $n$ strip with alternating black or white tiles of length either $1$ or $2$, with the constraint that you have an equal area of black and white. We'll forget both the factor of two that comes from the fact that you can start with either a black or a white tile, and the restriction of equal areas of black and white, since for large $n$ these will contribute lower-order terms. The number of ways of tiling this strip is the $n$th Fibonacci number $F_n$, and the ratio of tiles of length $1$ to those of length $2$ is the golden ratio $\phi=\frac{\sqrt{5}+1}{2}$. You can see this because the last tile is either of length $1$ or length $2$, and for a length $1$ tile, there are $F_{n-1}$ ways of tiling the remaining strip, while for a length $2$ tile, there are $F_{n-2}$ ways. The ratio of the two lengths for the tile ending at position $n$ is thus $F_{n-1}/F_{n-2}$, which converges to $\phi$.

The process I sketched above, of choosing a random card from a legal deck, gives $1$ for this ratio of the number of runs of length $1$ do those of length $2$—a white card will be followed with equal probability by a white one (making a run of length $2$) or a black one (making a run of length $1$). Thus, it doesn't yield a uniform distribution among shuffles.

ADDED :

Here's an idea that will probably come pretty close to a uniform distribution over all allowed shuffles, although I can't analyze it. Suppose you just have two decks. Start by shuffling each deck. Choose a deck, say A, randomly to start the procedure. Take one card from deck A with probability $1/\phi$ and two cards from deck A with probability $1/\phi^2$. Then do the same for deck B. Keep this up, but adjust the probabilities so that the probability of one card from a deck is $1/\phi \pm \epsilon$, where $\epsilon$ is chosen so that you expect to exhaust the two decks at the same time. For more than two decks, or a restriction to no more than $k$ cards from each deck, you can use the same strategy, but you will have to figure out what the appropriate probabilities for choosing each allowed number of cards in the uniform distribution over allowed shuffles.


How to approximate minimum clique edge cover I'd like to take an undirected graph and express it (meaning all of its edges) using only cliques (ideally minimizing their sum cardinality).

It's clear that actually finding the minimum solution is at least as hard as the set-cover problem, but set-cover has good approximation algorithms.
Does anyone know a good approximation algorithm for this?

Particularly, if I start with each edge as its own clique and then arbitrarily choose two cliques from my list (whose union also forms a clique) and merge them and do this over and over until I can't merge any more, what's the worst case (as a ratio / the minimal solution)? Is there some heuristic I should use to determine what to merge next?

Here is a paper that deals with this problem:

John M. Ennis, Charles M. Fayle, and Daniel M. Ennis: Assignment-minimum clique coverings. Journal of Experimental Algorithmics 17(1), 2012.

It also gives some heuristics and experimental results. They don't give worst-case approximation ratios; minimizing the number of cliques instead of the sum of their sizes has only fairly weak approximation guarantees, so I guess it would be similar here.


Size bound on Büchi automaton for complement For a given Büchi automaton $\mathcal A = (A, Q, \delta, q_0, F)$ we define a congruence on $A^{\ast}$ by
$$
\begin{array}{llll}
 u \sim_{\mathcal A} v & :\Leftrightarrow & \mbox{for all }s,s' \in Q \mbox{ we have a path} \\
& & \mbox{from $s$ to $s'$ labeled by $v$ iff we have} \\
& & \mbox{such a path labeled by $w$ and} \\
& & \mbox{we have such a path which passes through a state from $F$} \\
& & \mbox{labeled by $v$ iff we have such a path labeled by $w$}.
\end{array}
$$
for $u, v \in A^{\ast}$. Now setting
$W_{ss'} := \{ w \in A^{\ast} \mid \mbox{there is a path labeled $w$ from $s$ to $s'$}\}$ and $W_{ss'}^{F} := \{ w \in A^{\ast} \mid \mbox{there is a path labeled $w$ from $s$ to $s'$ going through a state in $F$}\}$ we have
$$
 [w]_{\sim_{\mathcal A}} = \bigcap_{\substack{s,s'\in Q \\ w \in W_{ss'}}} W_{ss'} \cap \bigcap_{\substack{s,s' \in Q \\ w \in A^{\ast} \setminus W_{ss'}}} A^{\ast}\setminus W_{ss'}
 \bigcap_{\substack{s,s'\in Q \\ w \in W_{ss'}^F}} W_{ss'}^F \cap \bigcap_{\substack{s,s' \in Q \\ w \in A^{\ast} \setminus W_{ss'}^F}} A^{\ast}\setminus W_{ss'}^F.
$$
This equivalence is defined here and also in the the chapter Automata on infinite objects by Wolfgang Thomas in the Handbook of Theoretical Computer Science, Volume II. In this book it is said

  Let us consider the complexity of the complementation process and the equivalence test. Given a Büchi automaton with $n$ states, there are $n^2$ different pairs $(s,s')$ and hence $O(2^{2n^2})$ different $\sim_{\mathcal A}$-classes. This leads to size bound of $O(2^{4n^2})$ states for the complement automaton.

As in the above formula, for each set $W_{ss'}$ (and $W_{ss'}^F$) we can decide wether it occurs in the intersection (and hence determines if one complement $A^{\ast}\setminus W_{ss'}$ and $A^{\ast} \setminus W_{ss'}^F$ occurs) we have $2^{n^2}\cdot 2^{n^2}$ options (different then $|Q^{2^{2Q}}|$ which would be given by the identification of the classes with functions $f : Q \to 2^Q \times 2^Q$ in the wikipedia article).

  But why does this lead to a size bound of $O(2^{4n^2})$ for the complement automaton?

I do not see how to get a complement automaton such that this size bound could be easily seen?

Once you have the bound $2^{2n^2}$ on the number of classes, you can note that each state in the complement automaton corresponds to an $\omega$-regular language of the form $L_{f}L_{g}^\omega$, with $L_f$ and $L_g$ being functions from $Q$ to $2^Q\times 2^Q$.

Each such language is determined by $L_f$ and $L_g$, and there are $2^{2n^2}$ options for these functions, so you get a total of $(2^{2n^2})^2=2^{4n^2}$ options.

UPDATE FOLLOWING COMMENT:
The correspondence of the number $2^{4n^2}$ to the states of the constructed automaton is not exact. Observe that for every language $L_f$, we can construct a nondeterministic NFA $A_f$ (as is done in Theorem 1 in the Wikipedia link you posted). Moreover, the size of $A_f$ is polynomial in the size of the original NBW $A$. Thus, the size of an NBW for $L_fL_g^\omega$ is polynomial. You then take a union of $2^{4n^2}$ such automata, and obtain the complement NBW, so the size of the complement NBW is:
$$2^{4n^2}\cdot poly(n)=2^{4n^2 +\log poly(n)}=2^{O(4n^2)}$$
So it's a little less tight than $O(2^{4n^2})$, but it's still only singly exponential (perhaps there is a tighter analysis, but I'm not aware of one).


Lower bounds on 2-query locally decodable codes Does any one knows if there is a non-quantum proof of the fact that non-linear 2-query LDC must have exponential size?

Yes, there is.  Ben-Aroya, Regev and de Wolf in "A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs" (FOCS '08) provide a non-quantum proof of the exponential lower bound for 2-query LDC's, although there are similarities between the quantum and non-quantum proof techniques.

Here's a rough sketch of their proof.  Let $C: \{\pm 1\}^m \to \{\pm 1\}^n$ be a $2$-query LDC.  Then, for a given $x \in \{0,1\}^m$, set $M(x)$ to be the rank-1 matrix whose $(i,j)$'th entry is $C(x)_i C(x)_j$. $M$ is a matrix-valued function, and we can look at its matrix-valued Fourier coefficients: $\widehat{M}(\alpha) = \sum_{x} M(x) \prod_{i \in \alpha} x_i$.  But now, observe that $\widehat{M}(\{i\})$ computes the matrix whose $(j,k)$'th entry is the expected correlation of $x_i$ with $C(x)_j C(x)_k$.  Thus, if $C$ is a $2$-query LDC, we know that for every $i \in [m]$, many entries in $\widehat{M}(\{i\})$ are larger than some $\epsilon$.  This allows you to lowerbound the $p$-norm of $\widehat{M}(\{i\})$.  Finally, you can then apply their matrix-valued hypercontractive inequality, which is the main theorem of the paper, to get a lowerbound on $n$.


What is the probability of a virus spreading through a network given a virus source node? Model: Consider an infinite undirected connected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. At time $t=0$, a given virus node $s\in\mathcal{V}$ starts infecting the network $\mathcal{G}$. Specifically, for each edge $(u,v)\in\mathcal{E}$, if either $u$ or $v$ becomes infected, then the other uninfected node on the edge $(u,v)$ will be infected after a random time following an exponential distribution with rate $\lambda$. Assume the spreading times for each edge are independent and identically distributed.

Question: Now given a connected subgraph $G\subset\mathcal{G}$ ($s\in G$ ), what is the probability that all the nodes in $G$ are infected at time $t>0$?

I tried to find a mathematical model to track such an infection process on different kinds of networks (trees, grids, regular networks, etc.). However, after checking the classical epidemic models (SIS, SIR, etc.), I found these models often use the mean field approximation to find the percentages of population in different states (Suspicious, Infected, etc.) without considering the network structures. Thus I think they might not be useful in modeling the infection process described above.

Any insights or references to papers/books would be helpful and greatly appreciated.

there are many "spread" models, what you request does seem to have been studied. eg this paper builds a framework to analyze the difference & distinguish between random virus spreading and network- (graph-) based spreading.

Network Forensics: Random Infection vs Spreading Epidemic Milling, Caramanis, Mannor, Shakkottai

  Computer (and human) networks have long had to contend
  with spreading viruses. Effectively controlling or curbing an
  outbreak requires understanding the dynamics of the spread.
  A virus that spreads by taking advantage of physical links
  or user-acquaintance links on a social network can grow explosively
  if it spreads beyond a critical radius. On the other
  hand, random infections (that do not take advantage of network
  structure) have very different propagation characteristics.
  If too many machines (or humans) are infected, network
  structure becomes essentially irrelevant, and the different
  spreading modes appear identical. When can we distinguish
  between mechanics of infection? Further, how can this be
  done efficiently? This paper studies these two questions.
  We provide sufficient conditions for different graph topologies,
  for when it is possible to distinguish between a random
  model of infection and a spreading epidemic model, with
  probability of misclassification going to zero. We further
  provide efficient algorithms that are guaranteed to work in
  different regimes.


A problem that is in PSPACE but not known to be in PH? As we know Graph Isomorphism is in NP but it is not known to be NP-Complete or P-Complete. I was wondering if there are any problems that are known to be in PSPACE but not known to be PSPACE-Complete and not lie in PH?

The existential theory of the reals is known to be contained in PSPACE, but it is not known whether it is contained in PH. So take the existential theory of the reals, or any of the many equivalent problems.


PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem Problem 1
I have read "On Approximation of the Minimum-Cost k-Connected Spanning Subgraph Problem" (by A. Czumaj, A. Lingas), and even in the abstract are 2 statements "We present a polynomial time approximation scheme for Minimum-Cost k-Connected subgraph problem" and in the second paragraph of the abstract they state that there is no PTAS unless P=NP. I am sure there is a small difference between the tow problems, but I cannot see what it is. Could someone clarify for me what problem does not have a PTAS and how its different from the problem in the first paragraph of the abstract?
Problem 2
Because I didn't really get the paper from the first problem, I read "Polynomial Time Approximation Scheme from Euclidean TSP and other Geometric Problems" (by S. Arora), and I have the same problem here, he claims to give a PATS for euclidean TSP, but in the intro states "[...] showed that if P≠NP then metric TSP and many other problems do not have a PTAS". I see there some kind of contradiction, they are giving a PTAS, but say that some showed that there cannot be any. What am I missing?

Each of the papers shows that there is a polynomial-time approximation scheme (PTAS) for the problem it studies if the input instance is Euclidean and that there is no PTAS if the input instance is arbitrary (if P≠NP).