Graph planar drawing, with each edge's length is known Assuming I have a graph $G$, with edges $E$ and vertices $V$, and the length of each edge is known, but the coordinates of vertices are not.

Further assume that this is a graph that can be embedded on a 2D plane, what is the algorithm that can create a "nice" drawing with no edge intersection?

Obviously there are many ways the graph can be drawn, and the definition of nice is a bit fuzzy (for practical purpose I would define it as something that is pleasing to the human eyes), but I would only need a good enough algorithm for this.

Note there could be many graphs with its embedding and I frankly don't care the algorithm gives me which, as long as it is pleasant looking enough and it has all the above constraint satisfied.

The motivation for this question is this: imagine that you have to design a circuit layout, the path that connects between two electronic components is $E$, and the vertex of each component is $V$, as a part of your engineering design you know that the distance between each component is pre-specified. As a designer, you would have to arrange the components on the board so that it looks nice. How can you design the circuit layout?

There is considerable work on the problem of finding planar embeddings with specified edge lengths. Survey and some results can be found in $[1]$.

Cabello, S. and Demaine, E.D. and Rote, G., "Planar embeddings of graphs with specified edge lengths," Graph Drawing, 283--294, 2004.


If $u\cdot v \in (z \cdot z')^*$ and $v \cdot u \in (z' \cdot z)^*$ then $u \in (z \cdot z')^* \cdot z$ I'm searching for a reference for the following property:

Fact.  Let $u, v \in A^*$.  Write $w$ for the primitive root of $u\cdot v$, i.e., $u\cdot v =  w^c$.  There are unique words $z, z'$ such that:

$w = z \cdot z'$
$v \cdot u = (z' \cdot z)^c$
$u \in (z \cdot z')^* \cdot z$ and $v \in z' \cdot (z \cdot z')^*$

Proof. Most of the statement is given by, e.g., Lothaire 83:

What is left to show is the last point.  From $u \cdot v = (z\cdot z')^c$, we obtain that $u = (z\cdot z')^k\cdot z_{\text{p}}$ and $v = z_{\text{s}}\cdot z' \cdot (z\cdot z')^{k'}$ where $z = z_{\text{p}}\cdot z_{\text{s}}$ (the case where $u$ ends with a prefix of $z'$ is similar).  Since $v \cdot u = (z' \cdot z)^c$, it holds that $$z' \cdot z = z_{\text{s}}\cdot z' \cdot z_{\text{p}}\enspace.$$
  As $z' \cdot z$ is primitive, all of its permutations are distinct, hence the right-hand side of the previous equation is not a permutation, that is, $z_\text{s} = \varepsilon$. $\square$

The full statement (including the last point) seems to follow directly from the proof of Proposition 1.3.3 in (Lothaire '83).  The last point is part of the proof: using the notation in the original post, the proof states that $u = (z \cdot z')^{k_1} \cdot z$ and $v = z' \cdot (z \cdot z')^{k_2}$ for some $k_1$ and $k_2$ such that $k_1+k_2+1 = c$.  Perhaps the proof of this proposition could be cited...?


Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$ I encountered the following result during my research.

  $$\lim\limits_{n\to \infty} \mathbb{E}\left[
\frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}
\right] = 1$$
  where $m=\omega(\sqrt n)$ and $a_1,\cdots,a_m$ are chosen at random from $[n]$.

I am looking for a reference/a direct proof.

Crossposted on MO

Assume as given that $m=\omega(\sqrt{n})$.

Fix any $\epsilon>0$. We will consider $r\in[1,n]$ with $r<(1-\epsilon)n$. The aim is to show that with high probability as $n\to\infty$, $r$ is included in the set of differences.

First consider the set $A=\{a_i:i<m/2\}\cap[1,\epsilon n]$. The number of $i$ with $i<m/2$ such that $a_i<\epsilon n$ is binomial with expectation around $\epsilon m/2$. So with high probability as $n\to\infty$, the number of such $i$ will be at least $\epsilon m/4$, which is $\omega(\sqrt{n})$. Then (claim, "left as exercise", not hard to show) with high probability as $n\to\infty$, the set $A$ has size at least $\sqrt{n}$. Let us write $G$ for this "good event", that $|A|\geq\sqrt{n}$.

Suppose that indeed $G$ holds, i.e. there are at least $\sqrt{n}$ distinct values of $a_i$ less than $\epsilon n$, for $i<m/2$. Note that for each such value, there is a value $k\in [1,n]$ which is precisely $r$ larger. Now consider the values of $a_i$ for $i\geq m/2$. These are independent and each one has probability at least $\sqrt{n}/n=1/\sqrt{n}$ of being at distance $r$ from an element of the set $A$. The probability that no difference $r$ is produced is then at most $(1-1/\sqrt{n})^{m/2}$ which goes to 0 as $n\to\infty$ since $m=\omega(\sqrt{n})$. So indeed, the probability that $G$ holds but no difference of size $r$ exists tends to 0 as $n\to\infty$.

So (uniformly in $r<(1-\epsilon)n$) the probability that $r$ is included in the set of differences tends to 1 as $n\to\infty$.
Hence using linearity of expectation,
$$
\liminf
\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}\right] \geq 1-\epsilon.$$
Since $\epsilon$ is arbitrary, the limit is 1 as desired.


Is JSON a Regular Language? I was wondering if the JSON spec defined a regular language.  It seems simple enough, but I'm not sure how to prove it myself.

The reason I ask, is because I was wondering if one could use regular expressions to effectively pars JSON.

Could someone with enough rep please create the tags json and regular-language for me?

No, it's not regular.  Since it allows arbitrary embedding of balanced delimiters, it must be at least context-free.

For example, consider an array of arrays of arrays:

[ [ [ 1, 2], [2, 3] ] , [ [ 3, 4], [ 4, 5] ] ]

Clearly you couldn't parse that with true regular expressions.


Effect of self loops on mixing time? Consider 2 graphs G1 and G2.
G1: Any non-regular graph.
G2: Same graph but with added self-loops such that degree of each node is the same (either some $\Delta$, or maximum '$n$', where $n$ is the number of nodes in the graph).
We run a lazy random walk on G1, such that the random walk at a node $v$ either stays at $v$  with probability $1/2$ or moves out to a neighbor with probability $1/2d_{v}$, where $d_{v}$ is the degree of the node $v$. Consider, $t_{mix}$ as the mixing time of this random walk. Additionally, we maintain a queue where the starting node of the random walk is added to a queue, and thereafter each time the random walk jumps to a neighbor, the node it jumps to is added to the queue. Let the queue contain $k$ nodes when the random walk has mixed $(k<= t_{mix})$. Note that since the graph is non-regular the stationary distribution that it converges to is non-uniform.
Now, consider another random walk on G2, which chooses each edge with probability $1/d_{v}$, where $d_v$ is the degree of node $v$ including the self-loops. Assume that this random walk exactly follows the previous random walk (on G1) in the sense that each time there is a jump to the neighbor, it jumps to the same neighbor as the previous walk, i.e., it will push the exact same nodes to its maintained queue. When we consider time, of course, this would be slower as, in low-degree nodes, the random walk would have to undertake many self-loops before being able to jump to a neighbor.  What I want to show that, is when the queue contains $k$ nodes or ($O(k)$ nodes), then this random walk has also mixed. Note that, as opposed to before, the stationary distribution here with respect to which we want the mixing is uniform (due to the added self-loops).
Is there any existing work that shows this? Or if not, what can be a good coupling argument to prove this? Any reference or help would be greatly appreciated.
(Observe that, the random walk on G2, can also be considered as another (biased) random walk on G1 where the random walk stays at the current node $v$ with probability $1-(deg(v)/n)$ and, with probability $1/n$, moves to a uniformly at random chosen neighbor.)

Your question is essentially covered by Cor 9.5 in [1]
which implies that as long as the ratio of self-loops to the original degree is bounded above and below, the mixing time of this modified walk is equivalent (up to constants) to the mixing time of the lazy walk on $G_1$.
[1]
Peres, Yuval, and Perla Sousi. "Mixing times are hitting times of large sets." Journal of Theoretical Probability 28, no. 2 (2015): 488-519.
https://www.dpmms.cam.ac.uk/~ps422/mix-hit.pdf


Logic with Linear Programming Can first-order logic be modeled/simulated as linear programming or integer programming?
What about other forms of logic (say second order)?

Update:  am actually not a theory person, but more on the applied side in machine learning and AI. suppose you define a set of variables and some implication rules. Can we model this as an LP/ILP?

In the following, I define a a set of implication rules. Then I define a problem for fixed variables, and I ask some question. I also give the desired answer to each question(based on logical implication). The question is, can we model this problem as an LP/ILP?

Here is an example. Suppose I define the following types:

A = CHILD
B = PARENT
C = SIBLING

And I define the implication rule:

R1: For any $(x,y) \in A $ (meaning that $x$ is child of $y$) $\Rightarrow $ $(y, x) \in B$ (meaning that $y$ is parent of $x$).
R2: For any $(x,y) \in B $ (meaning that $x$ is parent of $y$) $\Rightarrow $ $(y, x) \in A$ (meaning that $y$ is child of $x$).
R3: For any $(x,y) \in C $ (meaning that $x$ is sibling of $y$) $\Rightarrow $ $(y, x) \in C$ (meaning that $y$ is sibling of $x$).
R4: or any $(x,y) \in C $ (meaning that $x$ is sibling of $y$) and $(y,z) \in A $ (meaning that $y$ is child of $z$) $\Rightarrow $ $(x, z) \in A$ (meaning that $x$ is child of $z$).

Now suppose we fix the variables (i.e. a problem is given).

Problem 1:
We know three variables $x, y, z$. We know the following facts

F1: $(x,y) \in A$ (i.e. $x$ is child of $y$).

And we want to be able to infer the answer to the following question(s):

 - Does it imply $(y,x) \in B$? (Answer: yes)
 - Does it imply $(y,z) \in C$? (Answer: unknown)
 - Does it imply $(z,y) \in C$? (Answer: unknown)

Problem 2:
We know three variables $x, y, z$. We know the following facts

F1: $(x,y) \in A$ (i.e. $x$ is child of $y$).
F2: $(x,z) \in C$ (i.e. $x$ is sibling of $z$).

And we want to be able to infer the answer to the following question(s):

 - Does it imply $(y,x) \in B$? (Answer: yes)
 - Does it imply $(y,z) \in C$? (Answer: yes)
 - Does it imply $(z,y) \in C$? (Answer: no)

A nice book on this topic: "Optimization Methods for Logical Inference", V. Chandru, John N. Hooker, Wiley, 1999


Which complexity class does this number theory problem belong to? 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by=c$' is $\mathsf{NP}$-complete.

Which complexity class does 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by^2=c$' belong to?

Added later: As noted in the comments, the NP upper bound is trivial if a, b, and c are positive, as was asked.

Theorem 1.2 in this paper shows that deciding if a given diophantine equation in two variables has a solution is in NP.


Above #P and counting search problems I was reading the wikipedia article about the eight queens problem. It is stated that, there is  no known formula for the exact number of solutions. After some searching, I found a paper named "On the hardness of counting problems of complete mappings". In this paper there is a problem, shown to be at most as hard as #queens, which is beyond #P. Getting a glimpse at the numbers of the #queens counted exhaustively in the wikipedia article, they seem pretty much super exponential.

I want to ask, if there is a name for this class or if in general there are counting problems belonging to classes above #P (with decision not in PSPACE of course because it would be obvious).

Finally, I want to ask if there are any other known results for other search problems, like finding a three-colored point in Sperner's Lemma for example (PPAD complete).

If the function f is in #P, then given an input string x of some length N, the value f(x) is a nonnegative number bounded by $2^{poly(N)}$.  (This follows from the definition, in terms of number of accepting paths of an NP verifier.)

This means that many functions f lie outside of #P for uninteresting reasons---either because f is negative, or, in the case you mention, because the function grows faster than $2^{poly(N)}$.  But for the $n$-queens problem as modeled in the paper, this is just an artifact of the authors' decision to let the input value $n$ be encoded in binary.  If the expected input was the unary string $1^n$, then $f(1^n) :=$ (number of valid $n$-queen configurations) would certainly be in #P, by a simple NP verifier that checks validity of a given configuration.

If you want to explore some functions that (conjecturally) lie outside of #P for more interesting reasons, consider e.g. these:

UNSAT:  $f(\psi) := 1$ if $\psi$ is an unsatisfiable Boolean formula, otherwise $f(\psi) := 0$.  This function is not in #P, unless NP = coNP.  It is probably not in the more general counting class GapP, either; that is, UNSAT is probably not the difference f - g of two #P functions.  However, it lies in the more general counting complexity class $P^{\# P}$, which in fact contains the entire Polynomial Hierarchy by Toda's theorem.

You might not like that example because it is not a natural "counting problem".  But the next two will be:

$f(\psi(x, y)) :=$ the number of assignments to $x$ such that the Boolean formula $\psi(x, \cdot)$ is satisfiable for some setting to $y$.
$f(\psi(x, y)) :=$ the number of $x$ such that, for at least half of all $y$, $\psi(x, y) = 1$.

The latter two problems are not known to be efficiently computable even with oracle access to #P. However, they are computable within the so-called "counting hierarchy".  For some more natural problems classified within this class, see e.g. this recent paper.

Counting Nash equilibria is apparently #P-hard, see here.  Also, even problems where the search problem is easy can be #P hard to count, e.g. counting perfect matchings.


NP completeness of classes of spanning trees I am teaching a complexity course, and I want to give some examples of similar looking problems such that one is in P, and the other is NP complete.

This made me think of the following problem: does a given graph contain a spanning tree with a given degree sequence? This is obviously easy for the sequence $n-1,1,...,1$ and hard for $2,...,2,1,1$.  Is there a general answer?

Lemke has shown that it is NP-hard to decide whether a cubic graph on $n=2k$ vertices has a spanning tree in which $k+1$ vertices have degree $1$ and $k-1$ vertices have degree $3$.

  P. Lemke:
  "The maximum-leaf spanning tree problem in cubic graphs is NP-complete."
  IMA publication no. 428, University of Minnesota, Mineapolis, 1988.
  https://www.ima.umn.edu/Maximum-Leaf-Spanning-Tree-Problem-Cubic-Graphs-NP-Complete

Lemke's result implies the NP-completeness of deciding whether there exists a spanning tree without vertices of degree $2$.
A slight modification of Lemke's reduction shows that the following problem is NP-complete for every fixed integer $p\ge4$: Decide whether there exists a spanning tree, in which every non-leaf vertex has degree at least $p$.
The same modification shows that the following problem is NP-complete for every fixed integer $p\ge4$: Decide whether there exists a spanning tree, in which every vertex degree lies in $\{1,p\}$.


Using MSOL for solving BIDS problem From "Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width" (B. Courcelle et al)  we know that any problem that can be written on MSOL (Monadic Second Order Logic) has a linear algorithm that solves it on graphs with bounded clique-width. However the algorithm takes as input the K-expression of the graph and obtaining it is NP-Complete if K is not fixed.

In a later paper "Improved bottleneck domination algorithms" (T. Kloks et al), there is a description of several bottleneck problems, including the Bottleneck Independent Dominating Set (BIDS) which asks for an independent dominating set D such that maximum weight over the vertices in D is as small as possible.

In section 4.4 they give an algorithm with complexity $O(5^kk^3n)$ for the BIDS problem on graphs with clique-width bounded and where the k-expression is given.
As far as I know this problem can be written in MSOL and hence the first paper (which is earlier) gives a better result for the same problem.

Am I wrong? Is there any technical detail or concept that I am missing?

Thanks in advance

The $O(5^kk^3n)$ is linear in $n$ as well and $O(n)$ for bounded $k$.
The Courcelle, Makowski, Rotics paper does not give explicit/good upper bounds for the contants hidden in the big-O.  If you want to make the dependency on $k$ explicit as in $O(f(k)n)$, then additional work is required.

See "Faster Algorithms on Clique and Branch Decompositions" by
Bodlaender et al (MFCS 2010)  for recent algorithms for domination-style algorithms.


Calculating least fixed points in equations Given a set of relations/equations in some logic like LTL would it be possible to find a least fixed point for those equations?

For example take the equations in LTL

$$ P = Play ~\land X(P \cup S)\\
   S = Stop \land X(S)$$

These have a least fixed point with
$$ P = Play~ W~ Stop\\
   S = G~Stop $$

Are there any algorithms for finding fixed points or is this problem undecidable?

In general, we look at fixed-points of monotone functions over lattices, i.e. with some partial ordering over your elements.

If your lattice is complete (it has a least and greatest element, called a bottom $(\bot)$ and a top $(\top)$), and the function whose fixed-point you're trying to find is monotone, then the Knaster-Tarski Theorem says that a fixed-point always exists.

However, finding this fixed-point may be undecidable. For example, in Hoare logic, there is a function whose fixed-point is the weakest-precondition of a loop. But there's no guarantee that this fixed-point can be found, since finding weakest loop invariants is undecidable.

The basic algorithm, which might not halt, is as follows:

X := bottom
while (X =/= f(X):
  X = f(X)
return X

However, you can always find a fixed-point using iteration if you have the Ascending Chain Condition, which basically means that there are no infinite increasing chains in your partial order. When you have this, and your function is monotone, the above algorithm will always halt.

If you have some other "upper bound" on a solution size, then you can use it to ensure the above algorithm halts.

In your case, where you have multiple equations, you just make your lattice contain vectors, and find a fixed-point of a multi-dimensional function.


Finding a point outside of each of a set of polygons in a bounded space I know there are algorithms for finding a point inside a simple polygon.  Given a set of polygons inside a rectangle (think a bunch of polygons on a computer screen), is there an efficient algorithm for finding a point that is inside the rectangle but not inside any of the specified polygons?  (Note that these polygons don't overlap, but may share a common border (or part of a border).)

If the polygons can overlap, the problem can be solved in $O(n^2)$ time (where $n$ is the number of sides of the polygons in total) by constructing the arrangement of line segments and maintaining as you construct it the number of polygons that cover each cell of the arrangement. There are $O(n^2)$ cells, arrangements can be constructed in $O(n^2)$ time, and it takes constant time per cell to maintain the covering number because it differs by one from the number of any neighboring cell.

You are unlikely to solve the problem significantly faster than $O(n^2)$ because it is equivalent in difficulty to 3SUM — see the original paper on 3SUM hardness, "On a class of $O(n^2)$ problems in computational geometry", by Gajentaan and Overmars (CGTA 1995).

With your specification that the polygons cannot overlap, the same approach works in $O(n\log n)$ time using an output-sensitive arrangement construction algorithm.


Triangulating a Planar Polygon Are there by now simpler algorithms/proofs for triangulating a planar polygon in linear time? What is a good resource on the state of the art of this famous problem?

So far, the only improvement to Chazelle's juggernaut is the 2001 randomized linear-time algorithm by Amato, Goodrich, and Ramos.  Chazelle's algorithm is still the only deterministic O(n)-time triangulation algorithm known.


Estimate the maximum frequency of substring with given length in a very long character stream Suppose there is a very long string $S\in \Sigma^N$ with length $N$, where $\Sigma$ is a relatively small alphabet (for example, $\Sigma=\{'a', 'b', \ldots, 'z'\}$). Now, given a budget $B$, the goal is to find the solution of following problem:
$$
\begin{align*}
\min_{l\in\mathbb{N}} &\quad l \\
\text{s.t. }& \max_{s\subset S, |s|=l} \ \text{freq}(s) < B
\end{align*}
$$
i.e., I want to find a length $l_c$, such that for "any" substring $s\subset S$ with length $|s|>l$, it occurs no more than $B$ times.

Assume every character in $S$ obeys the same known distribution $D$: $S[i]\sim D, \forall i\in[N]$. Here we can allow some violations in the constraint, only requiring
$$
\Pr[\max_{s\subset S, |s|=l} \ \text{freq}(s) < B] > 1-\delta.
$$

Currently I'm using a brute force approach, testing each $l$ from small to large, where for each $l$ I scan through the whole string $S$ to determine if there is one substring occur too often. This is very inefficient since $|S|$ is huge.

So I want to know if there exists some sub-linear (w.r.t. $N$) algorithm that can estimate the maximum frequency of substrings with fixed length.

Maybe I didn’t make it clear. Here is my problem:

Given a constant $B$ and the length of the string $N$, I want to find the minimum length $l$, such that all $l$-long substrings occur no more than $B$ times. Is there a algorithm better than simply testing from small to large?
If it's expensive to determine the exact $l$, an approximated $l$ is also acceptable. Here "approximated" has two meanings: $l$ can be smaller than the true $l_c$ as long as there're not too many violating $l$-long substrings; or it can be larger that $l_c$, but not too far away.
Furthermore, if the distribution of input character is highly skewed (i.e., some characters occur far more often than others), can I find an approximate or exact $l$, such that all $l$-long substrings starting with some fixed character $s$ occur no more than $B$ times?

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

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

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

due to the birthday paradox.

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

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


What is the complexity of this submatrix selection problem? We have a $kn\times kn$ matrix $M$ made of $n^2$ many $k\times k$ blocks.
We want to find an $n\times n$ submatrix such that each row and column is from distinct window of size $k$ such that the sum of entries of sub matrix is maximized.

What is the complexity of this problem?

What is the complexity of this problem if there is an unique maximum?

EDIT: Added an answer meeting the unique-sum requirement.
Lemma 1. The problem is NP-hard by reduction from 3-CNF-SAT, even if the maximum is required to be unique.
Proof. Here's the reduction.  First we describe the reduction to the problem without the requirement that the maximum is unique.
Fix a 3-CNF-SAT instance $\phi$.  Assume WLOG that $\phi$ has more clauses than variables (if not, just duplicate clauses to make it so).  Let $n$ be the number of clauses.
The reduction outputs a $kn\times kn$ matrix $M$, where $k=3$.  $M$ will be a 0/1 matrix, and will have an $n\times n$ submatrix of the desired form and having (at least) $n$ ones iff $\phi$ is satisfiable.
Create $M$ as follows. For each variable $x$ in $\phi$, create a window of three columns: a column $c(x)$ for the literal $x$, a column $c(\bar x)$ for the literal $\bar x$, and one dummy column whose entries are all zero (just so the window has the necessary three columns). Add additional windows of all-zero columns to bring the number of column-windows to the desired number $n$.
For each clause, say $C=\ell_1\vee \ell_2 \vee \ell_3$, create a window of three rows, one for each literal. Name the three rows, respectively, $r(C, \ell_1)$, $r(C, \ell_2)$, and $r(C, \ell_3)$.  In each row, make just one entry 1: for row $r(C, \ell_1)$ the entry in column $c(\ell_1)$, for row $r(C, \ell_2)$ the entry in column $c(\ell_2)$, and for row $r(C, \ell_3)$ the entry in column $c(\ell_3)$.  Make all other entries zero.
This completes the reduction.  To finish we observe that there will be a submatrix of the desired form (with a row in each row-window and a column in each column-window) having (at least) $n$ ones if and only if $\phi$ is satisfiable.
First, suppose that $\phi$ has a satisfying assignment $A$.  Choose the submatrix of $M$ as follows.  Use the columns corresponding to literals that $A$ makes true (one for each variable), and one (all-zero) column from each padding column-window.  For each clause $C$, choose a literal $\ell_i$ in $C$ that $A$ makes true, and choose the row $r(C, \ell_i)$ in $C$'s row-window.  This defines the $n\times n$ submatrix.  Each of its rows has a 1, so the total number of 1's in the submatrix is $n$.
Conversely, suppose that $M$ has a submatrix $M'$ of the desired form with at least $n$ ones.  For each variable $x$, $M'$ uses either the column for the literal $x$, the column for the literal $\bar x$, or the dummy column in $x$'s column-window.  If $M'$ uses one of the two literal columns, assign $x$ the value that makes the literal true.  Otherwise assign $x$ arbitrarily.  This defines the assignment.
To see that it must be a satisfying assignment, recall that the submatrix has $n$ rows, and each row of $M$ has at most one 1, so reach row of the submatrix $M'$ must have exactly one 1.   By the construction of the row-windows in $M$, then, for each clause $C=\ell_1\vee \ell_2 \vee \ell_3$, there is a row $r(C, \ell_i)$ in the submatrix that has a 1, necessarily in the entry for row $\ell_i$ (as this is the only 1 entry in that row).  So column $\ell_i$ must be in the submatrix, so the assignment must make $\ell_i$ true.
EDIT: added the part below to handle the unique-sum requirement.
Hence, the reduction is correct.  Finally, to reduce 3CNF-SAT to the problem when the maximum is required to be unique, modify the previous reduction to output the matrix $M^*$ obtained from $M$ by adding a small perturbation to each entry, specifically, such that
$$M^*_{ij} = M_{ij} + \epsilon_{ij} \text{ where } \epsilon_{ij}=1/2^{nki + j+1}.$$
Because $M$ is a 0/1 matrix, the sum of the values in any sub matrix of $M$ is an integer. Also, for any sub matrix $M'$ of $M^*$, the sum of the perturbations $\sum_{ij\in M'} \epsilon_{ij}$ is less than 1 and is unique (as it uniquely identifies the set of indices of entries in $M'$).  It follows that the valid submatrix of $M^*$ with maximum sum is unique, and has sum at least $n$ iff the given 3-CNF-SAT instance $\phi$ is satisfiable.
(And note that the size of the encoding of $M^*$ is still polynomial in the size of $\phi$.)
$~~\Box$
Exhaustive search takes time polynomial in $k^n$, which is polynomial in the input size in the case that $n$ is constant (but $k$ grows).  So that case (fixed $n$) has a poly-time algorithm.
One could ask further about, say, hardness of approximation.  The above reduction can be done from MAX-3SAT to show that the problem has no PTAS.  But to me it looks like the problem generalizes a variant of Bipartite Densest Subgraph, so may be even harder to approximate.  (This assumes the matrix has non-negative entries.  If negative entries are allowed, it's easy to extend the above reduction so that the optimal value is 1 iff $\phi$ is satisfiable, and zero or negative otherwise, so approximating within any factor is NP-hard).


Classification of Typed/Untyped Lambda Calculi Can anyone explain briefly (if thats possible!) or refer me to a reference, summarizing the differences between untyped lambda calculus and the more common typed lambda calculi?
I'm particularly looking for statements of their expressive power, equivalences to logic/arithmetic systems or computation methods, and analogies to programming languages if applicable.
While I certainly intend to read, something like a reference table outlining the calculi and their equivalences/differences/place in the hierarchy would be a HUGE reference for helping me sort them out.
Not saying the below is correct, just trying to sketch together some of the impressions i have to see if they at least serve as a starting point (or something to correct!)

Untyped lambda calculus - eq. to first order logic - cannot do X
Simply typed lambda calculus - eq to ... logic, related to Lisp?
'Polymorphic' lambda calc -
etc.
Calculus of Constructions - intutionist logic?
Combinatory Logic - comparable to ??? typed lambda calculus, related to APL/J kind of languages

If this ties into the lambda cube and its three axes all the better.
While I'm familiar with the basics of lambda calculus and programming with functional languages, I have never wrapped my head around, or made any significant connections to, the type systems involved and different flavors of lambda (and maybe pi?) calculi.
When I attempt to research this i cant help but find myself sidetracked, opening up many browser tabs and branching in so many directions I never get into any of them with any depth!
I'm not sure if what I'm asking for is reasonable, but hopefully at the very least I've painted enough of a picture to suggest some reading that can explain what im looking for?

Your table is a bit confused; here's a better one.

Untyped lambda calculus -- no logical interpretation, as Andrej notes
Simply typed lambda calculus -- intuitionistic propositional logic
Polymorphic lambda calculus -- pure second-order logic (ie, without first-order quantifiers)
Dependent types -- generalization of first-order logic
Calculus of constructions -- generalization of higher-order logic

Type dependency is more general than first-order quantification, since it turns proofs into objects you can quantify over. Lambda calculi corresponding to ordinary intuitionistic FOL exist, but are not widely used enough to have a special name -- people tend to go straight to dependent types.

You can also relate the syntactic form of a calculus to logical systems, as well.

Combinator calculi (eg, SKI combinators) -- Hilbert-style systems
A-normal form -- sequent calculus
Ordinary typed lambda calculus -- natural deduction


How much memory is needed for counting distinct elements in a stream exactly with high probability Assume we know a parameter $n\in\mathbb N$, and then get to observe a sequence of elements $x_1,\ldots, x_n$, one at a time.

Our goal is to count the number of distinct elements in $x_1,\ldots, x_n$, and succeed with probability $1-\epsilon$.

A simple approach would be to compute a $\log\left({n\choose 2}\epsilon^{-1}\right)$ bits fingerprint of each element, and then count the number of distinct fingerprints.

Since the number of distinct elements is a most $n$, with probability of at least $1-\epsilon$, all fingerprints of distinct elements will be different.

This gives us a total of $\approx n\log (n^2\epsilon^{-1})-n$ bits of space.

But is this anywhere close to optimal? Can we perhaps use only $O(n\log\epsilon^{-1})$ bits for the problem? What would be a lower bound for this problem?

EDIT: I'm specifically interested in computing the number of distinct elements exactly, with high probability, and not in approximation algorithms.

In the paper An Optimal Algorithm for the Distinct Elements Problem, the authors give a $O(\gamma^{-2}+\log n)$ bits algorithm for computing a $(1+\gamma)$ approximation with high probability, and claim that this is optimal.

However, setting $\gamma<n^{-1}$ for getting exact count with high probability gives a $\Omega(n^2)$ bits algorithm, which seems worse than the $O(n\log n)$ proposed above.

They do not assume that $n$ is known in advance, which may explain this difference.

You can do $O(\log \frac n\epsilon)$ space if you only want an approximation.
The main idea is that you use the random hash function $h$ to do the same protocol as in the Goldwasser-Sipser Set Lowerbound (which you can find, e.g., in the Arora-Barak book).
So you pick a target $y$ and observe whether $h(x_i)$ holds for any $i$.
If the sequence is diverse, then whp. you can find such a $i$, otherwise you cannot.
To increase the probability of success, you can pick $O(\log \frac 1\epsilon)$ different $y$'s of length $O(\log n)$ and do the protocol for each.

If you want an exact answer, then more precise calculations are needed.
I think $O(polylog \frac n\epsilon)$ space might be still enough, but I might be wrong.


Counting reduction from #SAT to #HornSAT? Is it possible to find a counting reduction from #SAT to #HornSAT? I haven't found this question posted here, so decided to check if anyone has any answer to this. Let me explain what do I mean by counting reduction.

Suppose $f,g : \{0,1\}^* \to \mathbb N$ are two counting problems. For example, #SAT asks how many satisfiable assignments are there for a specific instance $\phi$, and $f,g$ are similar counting problems finding total number of witnesses. A weakly parsimonious counting reduction from $f$ to $g$ consists of a pair of polynomial time computable functions $\sigma : \{0,1\}^* \to \{0,1\}^*$ and $\tau : \{0,1\}^* \times \mathbb N \to \mathbb N$ such that $f(x) = \tau (x, g(\sigma(x)))$. In the case that $f(x) = g(\sigma(x))$, this is known as strongly parsimonious counting reduction.

I can see that if there is any such counting reduction from #SAT to #HornSAT, it must be weakly parsimonious reduction: a strong reduction would imply that the #SAT and #HornSAT instances will have zero or non-zero number of solutions together, and assuming that $\mathsf P \ne \mathsf{NP}$, this is impossible (as HornSAT $\in \mathsf P$ while SAT is $\mathsf{NP}$-complete).

So my question is: is there any weakly parsimonious counting reduction from #SAT to #HornSAT? If so, can anyone please give me some reference ?

This post discusses #P-completeness of #Monotone-2SAT under weakly parsimonious reductions. If you negate all literals in a monotone 2-CNF formula $\phi$, you obtain a Horn 2-CNF formula $\psi$ with the same number of satisfying assignments.


Any evidence that Linial, Shraibman lower bound on quantum communication complexity is not tight? As far as I know, the factorization norm lower bound given by Linial and Shraibman is essentially the only lower bound known for quantum communication complexity (or at least it subsumes all others).  Is there any evidence against this bound being tight?

The factorization norm bound (also called the $\gamma_2$ bound) I speak of is Theorem 13 of Linial, Shraibman 2008.  In fact, this bound follows from a reduction from quantum communication complexity to the bias in a 2-player XOR game Degorre, et al. 2008.  For this reason it could be expected to be a lousy bound since the XOR game doesn't even have anything to do with communication.  For the impatient, a brief overview is given in some slides by Troy Lee.

The introduction text of Jain, Klauck 2010 says that information theoretic techniques may offer some competition but it is not known whether these beat the $\gamma_2$ bound.  So it would seem that, at least as of a few years ago, $\gamma_2$ was the best technique.  But I would like to know if there is even a specific example of a function that is believed to have quantum communication complexity much greater than the $\gamma_2$ bound.

I don't know of any function with communication much higher than the $\gamma_2$ bound. However, my intuition of why it is not tight is because the $\gamma_2$-norm is also a lower bound for QCMA communication. See this paper by Klauck for the definition of QCMA communication.

To prove the lower bound on QCMA communication using the $\gamma_2$-norm you can use the same reduction to an XOR game as in the  proof of Theorem 14 of this paper. This will also hold for certain types of entanglement.


What are the consequences of solving XOR 3-SAT in Logspace? XOR Formulas

Consider boolean formulas with connectives $\wedge$ (AND) and $\oplus$ (XOR).  Such a boolean formula is a valid instance for XOR SAT if it is a conjunction of $\oplus$-clauses.  An $\oplus$-clause contains literals that are connected with $\oplus$.

Example Formula:

$(v_1 \oplus \bar{v_2} \oplus v_3 \oplus v_4) \wedge (\bar{v_1} \oplus v_2) \wedge (\bar{v_2} \oplus v_3 \oplus \bar{v_4})$

Decision Problem

  Name: XOR 3-SAT

  Input: A boolean formula that is a conjunction of $\oplus$-clauses where each clause contains three literals.

  Question: Does there exist an assignment to the variables that satisfies the formulas?

More Background

XOR SAT can be reduced to solving a system of equations over $\mathbb{Z}_2$.  This is because every $\oplus$-clause can be thought of as an equation.  As a result, XOR SAT is solvable in polynomial time using gaussian elimination.

Further, XOR 2-SAT can be reduced to solving reachability in an undirected graph.  This is because every $\oplus$-clause with two literals defines an edge in an undirected graph.  As a result, XOR 2-SAT is solvable in logspace because reachability in an undirected graph is solvable in logspace (because SL = L).

Question

  (1) Is XOR 3-SAT solvable in logspace?

  (2) Are there any known consequences of solving XOR 3-SAT in logspace?

  (3) For example, would this imply that XOR $k$-SAT is solvable in
  logspace?

Take a look at https://www.sciencedirect.com/science/article/pii/S0022000008001141 "The complexity of satisfiability problems: Refining Schaefer's theorem" by Allender et al. which answer your questions:

(1) Open

(2) $\oplus L = L$

(3) Yes


an efficient algorithm for mismatch profile We have M=10000 binary sequences of length N=1000.

given length L=15, for each pair of sequences, $S_1$ and $S_2$, we define the mismatch profile, mp($S_1$,$S_2$,$L$)[$m$], for m=0,1,...,L as following:

mp($S_1$,$S_2$,$L$)[$m$] = number of all substrings of length $L$ in $S_1$ and $S_2$ that exactly differ in m positions.

for example:

$\begin{array}{ccc}
L=5    \\
N=7    \\
S1='1010101' \\
S2='1011000'

\end{array}$

set of all L-mers in $S_1$ is { 10101, 01010, 10101} and
set of all L-mers in $S_2$ is { 10110, 01100, 11000}

All the pairs of L-mers (one from S1 and the other from S2) are (with the number of mismatches for each pair in the parenthesis):

$\begin{array}{ccc}
10101 & 10110 & (2) \\
10101 & 01100 & (3) \\
10101 & 11000 & (3) \\

01010 & 10110 & (3) \\
01010 & 01100 & (2) \\
01010 & 11000 & (2) \\

10101 & 10110 & (2) \\
10101 & 01100 & (3) \\
10101 & 11000 & (3)
\end{array}$

hence the mismatch profile for $S_1$ and $S_2$ for this example is:
mp($S_1$,$S_2$,$L$)[0]= 0
mp($S_1$,$S_2$,$L$)[1]= 0
mp($S_1$,$S_2$,$L$)[2]= 4
mp($S_1$,$S_2$,$L$)[3]= 5
mp($S_1$,$S_2$,$L$)[4]= 0
mp($S_1$,$S_2$,$L$)[5]= 0

what is a fast algorithm to calculate the mismatch profile for every pair of sequences. The trivial algorithm would be $O(N^2 M^2)$ . can we make this better ?

Upd: Space complexity improved to just $O(2^LML)$ which makes the solution much more practical.

The problem can be solved at least in $O(M^2NL + 2^L MNL)$ time and $O(2^L ML)$ additional memory as follows.

Let's denote by $S^j$ the prefix $s_1 s_2 \ldots s_j$ of $S$. First, for each binary string $s$ of length $L$ precompute mismatch profile $mp'(s, i, j, k) = mp(s, S_i^j, k)$ of that string with all prefixes of length $j$ of all strings $S_1, S_2, \ldots, S_M$. That will require $O(2^L MNL)$ memory to store and can be done in $O(2^L MNL)$ in straightforward way.

Then iteratively build mismatch profiles $mp_j(i,i',k)$ for each pair of $j$-prefixes of $S_1, S_2, \ldots, S_M$ for $j=L,L+1,\ldots,N$, so $mp_N(i,i',k)$ will be your desired answer. Let's denote by $end(S)$ the suffix of $S$ of the length $L$ (i.e. $S[(length(S)-L+1) \ldots length(S)]$). Notice that $$
\begin{align*}
mp_j(i,i',k) = &mp(S_i^{j-1},S_{i'}^{j-1},k) + mp(end(S_i^j), S_{i'}^{j-1}, k) + \\&mp(S_i^{j-1}, end(S_{i'}^j),  k) + mp(end(S_i^j), end(S_{i'}^j),k)
\end{align*}
$$ which is indeed
$$
\begin{align*}
&mp_{j-1}(i,i',k) + mp'(end(S_i^j), i', j-1, k) + \\ &mp'(end(S_{i'}^j), i, j-1, k) + mp(end(S_i^j), end(S_{i'}^j),k)
\end{align*}

$$

The first 3 terms of that sum are already computed and the last one can be computed in amortized $O(1)$ time (it is $O(L)$ but you need to compute it only once for all values of $k$ with fixed $j,i,i'$). Thus you can compute $mp_j$ using $mp_{j-1}$ and $mp'$ in $O(M^2L)$ time, which leads to $O(M^2NL)$ term in the total complexity.

Notice that you need values of $mp'$ only for a fixed prefix length on each iteration. Thus you can compute $mp'$ not all of a piece at the beginning but rather iteratively for $j=L,L+1, \ldots, N$ in between of $mp_j$ computations. That can be easily done in $O(2^LML)$ time per iteration (so total complexity does not change) but requires only $O(2^LML)$ additional memory.

The main issue of this solution is exponential in $L$ time.

P.S. If $L$ is too small ($2^L < N$) then the naive method can be improved to $O(M^2 4^L)$ time by calculating the number of occurrences of each string $s$ of length $L$ in $S_i$. This allows you to process all different substrings of $S$ of length $L$ in $O(2^L)$ time instead of $O(N)$ (you will need to precompute pairwise differences between all such substrings first).


Important papers and open problems in Boolean functions I am interested in Boolean function polynomial/rational exact/approximate/one sided approximate representation, relation to circuit/communication complexity, tools utilized to study Boolean functions (such as combinatorics, analysis, approximation theory, algebra etc).

What are some of the important references, lecture notes and key papers (including survey) in the field of Boolean functions for someone wanting to learn the growth of the area from 80s till today.

Even open problems in the area would be a good introduction as one can usually trace back the literature. One important open problem is sensitivity-block sensitivity conjecture.

Bryant's "Graph-Based Algorithms for Boolean Function Manipulation" introduced Reduced-Order Binary Decision Diagrams (ROBDDs) for representing and manipulating Boolean functions.  I believe these see a lot of use in CAD tools and circuit synthesis problems.  Bryant's paper is a good place to start a literature review for BDD.  He cites a few key earlier works and a lot of the more recent work grew out of, and cited, his paper.


What are some problems where we know we have an optimal algorithm? What are some non-trivial problems where we know the current algorithm we have is the asymptotically optimal one? (For turing machines)

And how is this proved?

Any algorithm which takes linear time and has to read its whole input must be asymptotically optimal. Similarly, as Raphael comments, any algorithm whose runtime is of the same order as output size is optimal.


Choosing a research topic using game theory This recent game theory question got me thinking (this is a tangent, of course): Is it possible to efficiently optimize a personal strategy for choosing research questions to work on using game theory?

In order to head towards a formalization of the question, I'll make the following (informally stated) assumptions:

I equally "enjoy" any particular problem available for me to work on (in order to avoid the "soft" (and correct!) answer of "Do what you like!").
I may or may not be successful at finding an answer to any given problem I choose to work on. For any given problem, I have some estimate of the probability of how good I will be at solving a problem (after investing time in it).
My goal is to maximize my payoff when being evaluated down the line (applying for a job, applying for tenure, applying for a fellowship, etc.), which is a function of how many problems I solve and how important or hard the problems are. I do not have a clear idea of the exact payoffs per problem, but I can make a reasonable estimate.
There is a loose inverse relationship between problem payoff and problem difficulty. Another statement of my goal is to "game" the differences (i.e. look for "low-hanging fruit").
An instance of this overall problem is specified by a list of research questions (possibly infinite in number), to which I firmly attach (at no computational cost; it's given as input) an estimate of the question's worth and the question's difficulty. I am playing this game against an adversary (the person evaluating me); nature decides, given the probability of me solving a given problem, whether I solve it successfully after I choose to attempt it.

In an effort to really formalize what's going on (and sidestep uninteresting or argumentative/discussion-type responses), I will view this problem as an extensive-form game with incomplete information with an infinite action set.

Question: I assume games of this type are not efficiently computable. However, is there a polynomial time algorithm to approximately maximize my payoff? What about a PTAS?

Or, alternatively, is there a more accurate game-theoretic model for this problem? If so, the same question holds: Can I (approximately) maximize my payoff efficiently? If so, how?

I'm going to try to answer you question by proposing an alternate model for the question.  I typically ask more questions than I answer on here, so I hope you'll be forgiving if my answer isn't optimal, although I'm doing my best.

I think that the way to phrase the question that would be optimal for allowing game theory to be useful would be to assume a more competitive scenario.  I.e., there needs to be competition among a variety of different actors.  So, I would assume the following:

There is a large but finite number n of other researchers attempting to pursue the same set of available research questions, which I call Q, that you are interested in.
Each research problem is defined by the following characteristics:

Time investment, or I, required to achieve visibility on whether or not you'll be able to solve the problem
Probability of success, or S, at solving the problem; once you reach the "moment of truth" and have invested enough time, Nature will decide randomly if you're going to be able to solve the problem or not
Benefit to your career, or U (as in utility), provided success is achieved

Each of these researchers have different levels of the following quantities:

Time available for investment in research, t
Talent at research, r
Interpersonal skills and other career-assisting qualities, l (as in likable), which will determine how well the researcher will capitalize on their research successes for their career advancement

Now, assuming no cooperation on any problem is possible, consider what I'm going to refer to as a "dynamic iterated game."  This is a game that is played repeatedly, but that changes slightly each time it is played.

Let M be the number of moves, or turns, in the game.  The initial manifestation of the game could be represented as a list that contains every actor (researcher) and every problem that they could work on, in addition to all of the values associated with each actor and each problem that I listed above.  (I'm assuming, of course, that every researcher knows everything presently known about all of the problems, and about all other researchers, making this a game of perfect information.)

During each iteration of the game, a given actor chooses a research question to work on.  Each actor is permitted to switch questions at any time, and if a problem is solved, the benefit to career U gets dropped to 0 for all other players.  If a player invests sufficient time and fails to solve the problem, then that particular player is prohibited from trying to solve that problem again...although any other player is allowed to continue working on the problem, and another actor may be able to solve it successfully.  The game ends after all M turns have been taken.

Each turn that a researcher has selected a problem will cause that player to get closer to reaching the "moment of truth," and possibly solving the problem, Nature permitting.  A problem, once solved, adds a certain benefit to the researcher's career based on l.  Research talent amplifies the probability of success, while free time amplifies the ability to make progress in a given turn.

I doubt that there is any polynomial time algorithm for solving this; I see no reason why researchers should be restricted to playing pure-strategy Nash equilibria, so the problem would involve mixed-strategy Nash equilibria and thus be at worst PPAD-complete, if you consider "solving the problem" to mean "finding a Nash equilibrium for the problem."  (One could imagine that if you are the most proactive researcher around, you might go ahead and calculate your favorite Nash equilibrium and then signal it to all other players...thus giving you some confidence that no one will change strategies away from the strategy profile you've signaled.)

At any rate, this is the most involved answer I've ever posted.  I hope it is of at least some value.  Please let me know if anyone has any response or to it or recommendations for improving it.


Formalization of simulation for Turing machines Right now I am trying to understand the concept of simulation in theoretical computer science, focussing on Universal Turing machines. All textbooks that I looked into only explain examples. They introduce one particular Universal Turing Machine and explain how it simulates other Turing Machines. But does there exist a rigorous theory/formalization behind simulations of Turing machines? Particular questions that I care about:

Given two Turing machines T and T', when can it be said that T simulates T'?
Is there a theory of "shortcuts" in simulations of Turing machines?
A random google search revealed the notion of Simulation preorder, see e.g.:
https://en.wikipedia.org/wiki/Simulation_preorder
Does something similar exist for Turing machines?

First, let's clearly settle what it means for a Turing Machine to compute a function.
Any specification of a deterministic TM $M$ implicitly defines, for each word $w \in \Sigma^*$, a (possibly infinite) sequence of configurations of $M$ when run on $w$ (the machine is said to halt if this sequence is finite). A configuration consists of the state of the TM, the position of its head, and the contents of its tape. This, in turn, defines a function
$$f_M: \Sigma^* \to \Sigma^* \uplus \{\bot\}$$
that the machine computes: for a word $w \in \Sigma^*$, if the sequence of configurations of $M$ when run on $w$ is finite, the function value $f_M(w)$ is the word $v$ that is on the tape in the last configuration of that sequence, and if the sequence is infinite, we set $f_M(w) = \bot$ (indicating that $M$ does not halt on input $w$).
Next, we need to recognize that TMs themselves can be encoded as words over $\Sigma^*$. Let's assume for simplicity that every word $w$ describes a TM $M_w$. Also, define for each TM $M$ the set of words that encode $M$, i.e.
$$ \operatorname{enc}(M) = \{w \in \Sigma^* \mid M_w = M\}.$$
Further, pairs of words $(w, v) \in \Sigma^* \times \Sigma^*$ can be canonically encoded as a single word $u \in \Sigma^*$ - denote this word by $\langle w, v \rangle$.
And now we're ready to rigorously define what we mean when we say that TMs simulate other TMs. We say that a TM $M$ simulates another TM $M'$, if for all $w \in \operatorname{enc}(M')$ and all words $v \in \Sigma^*$,
$$f_M(\langle w, v\rangle) = f_{M'}(v).$$
That is, given any description of $M'$, and an input $v$, $M$ outputs exactly what $M'$ would output, and if $M'$ doesn't halt, then $M$ also doesn't halt.
A universal TM is a machine that simulates all other machines, in the following sense: A TM $M$ is called universal, if for every pair $(w, v) \in \Sigma^* \times \Sigma^*$,
$$f_M(\langle w, v \rangle) = f_{M_w}(v).$$
That is, given any description $w$ of a Turing machine $M_w$, and an input $v$ for that machine, $M$ outputs exactly what $M_w$ would output when run on $v$, and if $M_w$ doesn't halt, then $M$ also doesn't halt.
Edit: Restructured answer to make it more readable.


Are there closed-form expressions providing the VC-dimension for the multi-class case for different classifiers? So far, I've only encountered the VC-dim for binary classifiers. I'm interested to learn how this notion can be extended to the multi-class case. Are there expressions that provide bounds on the out-of-sample error based on the VC-dim for multi-category classifiers? The learning machines I am interested in are: SVMs, Neural Networks, AdaBoost and k-Nearest neighbors. Thanks.

VC-dimension has multiple multiclass extensions:
pseudo dimension, Natarajan dimension, graph dimension.
See here for example:
http://math.huji.ac.il/~amitd/multiclass.pdf
http://jmlr.org/papers/volume8/guermeur07a/guermeur07a.pdf

There are also extensions to continuous-valued functions (fat-shattering dimension):
http://users.cecs.anu.edu.au/~williams/papers/P53.pdf


Reasons for which a graph may be not $k$ colorable? While reasoning a bit on this question, I've tried to identify all the different reasons for which a graph $G = (V_G,E_G)$ may fail to be $k$ colorable. These are the only 2 reasons that I was able to identify so far:

$G$ contains a clique of size $k+1$. This is the obvious reason.
There exists a subgraph $H = (V_H, E_H)$ of $G$ such that both the following statements are true:

$H$ is not $k-1$ colorable.
$\exists x \in V_G - V_H\ \forall y \in V_H\ \{x,y\} \in E_G$. In other words there exists a node $x$ in $G$ but not in $H$, such that $x$ is connected to each node in $H$.

We can see the 2 reasons above as rules. By recursively applying them, the only 2 ways to build a non $k$ colorable graph which does not contain a $k+1$ clique are:

Start from a cycle of even length (which is $2$ colorable), then apply rule 2 for $k-1$ times. Note that an edge is not considered to be a cycle of length $2$ (otherwise this process would have the effect of building a $k+1$ clique).
Start from a cycle of odd length (which is $3$ colorable), then apply rule 2 for $k-2$ times. The length of the starting cycle must be greater than $3$ (otherwise this process would have the effect of building a $k+1$ clique).

  Question

  Is there any further reason, other than those 2 above, that makes a graph non $k$ colorable?

$\ $
Update 30/11/2012

More precisely, what I need is some theorem of the form:

  A graph $G$ has chromatic number $\chi(G) = k + 1$ if and only if...

Hajós calculus, pointed out by Yuval Filmus in his answer, is a perfect example of what I am looking for, as a graph $G$ has chromatic number $\chi(G) = k + 1$ if and only if it can be derived from axiom $K_{k+1}$ by repeatedly applying the 2 rules of inference of the calculus. The Hajós number $h(G)$ is then the minimum number of steps necessary to derive $G$ (i.e. it is the length of the shortest proof).

It is very interesting that:

The question of whether there exists a graph $G$ whose $h(G)$ is exponential in the size of $G$ is still open.
If such $G$ does not exist, then $NP = coNP$.

You should check the Hajós calculus. Hajós showed that every graph with chromatic number at least $k$ has a subgraph which has a "reason" for requiring $k$ colors. The reason in question is a proof system for requiring $k$ colors. The only axiom is $K_k$, and there are two rules of inference. See also this paper by Pitassi and Urquhart on the efficiency of this proof system.


Implicit vs explicit subtyping This page asserts that

  many languages do not use implicit subtyping (structural equivalence), prefering explicit/declared subtyping (declaration equivalence)

I've mostly used programming languages which uses explicit subtyping. What are the advantages of implicit subtyping, as described in the notes above.

The short answer is "to verify additional properties of existing code".  Longer answer follows.

I am not sure "implicit" vs "explicit" is good terminology.  This distinction is sometimes called "structural" vs "nominal" subtyping.  Then there is also a second distinction in the possible interpretations of structural subtyping (described shortly).  Note that all three interpretations of subtyping really are orthogonal, and so it doesn't really make sense to compare them against each other, rather than understanding the uses of each.

The main operational distinction in interpreting a structural subtyping relation A <: B is whether it is witnessed by a real coercion with (runtime/compiletime) computational content, or whether it can be witnessed by the identity coercion.  If the former, the important theoretical property that has to hold is "coherence", i.e., if there are multiple ways to show that A is a substructural subtype of B, each of the accompanying coercions have to have the same computational content.

The link you gave seems to have the second interpretation of structural subtyping in mind, where A <: B can be witnessed by the identity coercion.  This is sometimes called a "subset interpretation" of subtyping, taking the naive view that a type represents a set of values, and so A <: B just in case every value of type A is also a value of type B.  It is also sometimes called "refinement typing", and a good paper to read for the original motivation is Freeman & Pfenning's Refinement types for ML.  For a more recent incarnation in F#, you can read Bengston et al, Refinement types for secure implementations.  The basic idea is to take an existing programming language that may (or may not) already have types but in which types do not guarantee all that much (e.g., only memory safety), and consider a second layer of types selecting subsets of programs with additional, more precise properties.

(Now, I would argue that the mathematical theory behind this interpretation of subtyping is still not as well understood as it should be, and perhaps that is because its uses are not as widely appreciated as they should be.  One problem is that the "set of values" interpretation of types is too naive, and so sometimes it is abandoned rather than refined.  For another argument that this interpretation of subtyping deserves more mathematical attention, read the introduction to Paul Taylor's Subspaces in Abstract Stone Duality.)


Information on k-SAT (Introduction, Bounds, Methods, etc.) I'd like to know where I can turn for a good, gentle introduction to k-SAT (this may be for mathematicians that may not have a good computer science background).  I'd also like to know papers that maybe survey or explain current methods used to solve k-SAT.  Finally, I'm interested in the best known methods for solving k-SAT.  I'd like to get an idea of the best average case and best worst case behavior.

In short, I'm looking for papers that will help someone in mathematics (not computer science) become much more of an expert in k-SAT.

From the Lecture Note reference thread, we have this document.


Functional Sparse-Matrix with good performance? While writing a Petri Net program, I was faced with a choice about data structures to represent the graph. Adjacency lists (i.e. lists enumerating the arcs into and out of individual places or transitions) are easy to implement, but while I was studying the theory of petri nets, I was taken with the beauty of the matrix-based state-equation approach - which would presumably require me to use sparse matrices.

Which led me to wonder - are there are any implementations of sparse matrices providing fast enumeration in both rows and columns? If not, are there alternatives that would allow me to construct and efficiently traverse a bipartite graph in a functional language such as Erlang?

FWIW - By 'efficiently', in this case, I mean fast at enumerating the arcs incident on a given transition or place. I'd be happier to trade space for time if there are trade-offs to be made. Since the graph will not be modified after construction, it need not be particularly efficient for insertions or updates.

TIA

Buluç et al. (2009) propose a storage format called compressed sparse blocks which does not favour rows or columns. A $n\times n$-matrix is subdivided into $\beta\times\beta$ blocks and the list of nonzero elements in each block is stored in Z-Morton order. To list the nonzeros in a row or column you can process the $n/\beta$ blocks containing it, recursively finding the nonzeros in each block in $O(\beta)$.


How are real numbers specified in computation? This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real numbers are specified as input.  E.g., when it's stated that LDT has certain polynomial lower bounds, how are the real numbers specified when they are treated as input?

I disagree with your accepted answer by Kaveh. For linear programming and Nash equilibria, floating point may be acceptable. But floating point numbers and computational geometry mix very badly: the roundoff error invalidates the combinatorial assumptions of the algorithms, frequently causing them to crash. More specifically, a lot of computational geometry algorithms depend on primitive tests that check whether a given value is positive, negative, or zero. If that value is very close to zero and floating point roundoff causes it to have the wrong sign, bad things can happen.

Instead, inputs are often assumed to have integer coordinates, and intermediate results are often represented exactly, either as rational numbers with sufficiently high precision to avoid overflow or as algebraic numbers. Floating point approximations to these numbers may be used to speed up the computations, but only in situations where the numbers can be guaranteed to be far enough away from zero that the sign tests will give the right answers.

In most theoretical algorithms papers in computational geometry, this issue is sidestepped by assuming that the inputs are exact real numbers and that the primitives are exact tests of the signs of roots of low-degree polynomials in the input values. But if you are implementing geometric algorithms then this all becomes very important.


Transactional partially-ordered message queuing I'm having a really hard time finding a solution to a practical programming problem, and I think raw CS might have an answer.

The requirement is for a familiar message queue for which there are multiple message Generators and multiple message Consumers.  Generators enqueue messages into a queue within the scope of an transaction.  Consumers dequeue messages within the scope of a transaction, and process the message successfully, removing it from the queue, or fail and roll back the transaction in which case the message remains on the queue.  The message may be left on the queue by the Consumer in an altered state - decrementing a retry-count, for example.

Adding to this the concept of a Sequence or Conversation - a partial ordering within the set of all messages in the queue.  Messages which are part of a Sequence are to be consumed in-order.  Sequences are unordered amongst Sequences.

Generators do not block other Generators unless the messages being enqueued are for the same Sequence.  Generators never block Consumers.  Consumers never block Generators.  And Consumers never block other Consumers.  That is, Enqueue() may block, Dequeue() never blocks.  Generators Enqueue a message exactly once.  Consumers successfully process each message exactly once.

It'd be nice if the implementation doesn't leave too much trash data around, but as long as old data can eventually be trimmed, that's fine.

It seems like this scenario should be possible, yet I cannot find or design correct rules on a common platform.  SQL Service Broker might match all of these criteria, but if it does, how does it?

Is such a protocol provably impossible?  If not, how might it be done/what properties must the underlying storage platform have to support it?

A standard RDBMS should be enough; this is a sketch of how it can be done in a RDBMS even without BEGIN TRANSACTION capabilities (a mix of SQL/pseudocode):

Create two tables with the following columns:

Table MESSAGES:
*MSGID            int not null auto_increment,  (primary key)
SEQID             int,
SEQORDER          int not null auto_increment,
RETRIES           int default 0,
MSGDATA           varchar(...)

Table SEQUENCES
*SEQID            int not null,  (primary key)
SEQLOCKED         int,
SEQHASH           varchar(256)

The Generators can simply insert into the MESSAGE table their requests (and optionally fill the SEQUENCES table):

For example suppose a Generator must insert a message with SEQID=120

1) INSERT INTO SEQUENCES VALUES (120, 0, MD5(RAND()) )
// if the SEQID is already present the previous query
// just fails, do not worry about it
2) INSERT INTO MESSAGES (SEQID, MSGDATA) VALUES (120, 'bla bla bla')
// the auto_increment option in columns will assign correct values for MSGID and
// SEQORDER

The Consumers can do their stuff without using BEGIN TRANSACTION in this way:

// retrieve the SEQID of an unlocked sequence that contains a message:
1) SELECT * FROM SEQUENCES s LEFT JOIN MESSAGES m ON  m.SEQID = s.SEQID
      WHERE SEQLOCKED = 0
      ORDER BY SEQORD LIMIT 1
// suppose we retrieve a sequence with SEQID=120 and SEQHASH='102f...'
// we first lock the sequence using a standard tecnique:
2) newhash = MD5(RAND())
3) UPDATE SEQUENCES SET (SEQHASH=newhash, SEQLOCKED=1)
     WHERE (SEQID=120 AND SEQHASH='102f...')
4) IF (records_updated() = 1)   // lock acquired
   // we pick the older message of the sequence
   4.1) SELECT * FROM MESSAGES s WHERE SEQID=120 ORDER BY SEQORD LIMIT 1
   4.2) .... if we get a message (suppose MSGID=1234) then process it ....
   4.3) IF everything is ok THEN
          DELETE MESSAGES WHERE MSGID=1234
        ELSE
          UPDATE MESSAGES SET (RETRIES = RETRIES+1) WHERE MSGID=1234
   // finally we must unlock the sequence
   4.4) UPDATE SEQUENCES SET (SEQLOCKED=0) WHERE SEQID=120

restart from step 1)


Efficient randomness reduction using k-wise independence Consider a randomized algorithm with runtime $n$, which succeeds with high probability. The algorithm uses $O(n)$ uniformly random bits.

Now it is given that we can replace these uniformly random bits by $k$-wise independent bits, where $k$ depends on $n$ (say $k = \sqrt{n}$). Can we then reduce the number of random bits to $\tilde{O}(k)$ while keeping a runtime $\tilde{O}(n)$?

Clearly we could use k-wise independent bit generators (such as a random polynomial). However, naively implementing this would cost $\tilde{O}(k)$ steps per call, potentially increasing the runtime to $\tilde{O}(n k)$.

Yes.  You can generate a random polynomial of degree $k$, then evaluate this polynomial at $n$ different points in $\tilde{O}(n)$ time using the DFT (the DFT lets you evaluate a polynomial of degree $n$ at $n$ different points in $\tilde{O}(n)$ time).


What limits the performance of evolutionary computing techniques? What limits the current performance of genetic algorithms and neural networks?
The principles underlying these techniques, at least the popular science presentation of these principles, suggests that with enough training they could be improved
as much as desired. It seems that this is not the case though.

What are the causes for this? Why can't better results be achieved simply with
more computing power? Are there fundamental theoretical reasons for this?

I realize this is a very broad question, but I'm sure some of the people here
push against these bounds in their work, and I'd like to hear what they have to say.

To bring this to something resembling theoretical computer science: In his PNAS 2008 paper A Mixability Theory of Sex in Evolution, Christos Papadimitriou has theorized that one limit on the power of genetic algorithms is that they do not optimize what you think they should be optimizing (the objective function you're using in the selection part of the algorithm) but rather they optimize "mixability" (a measure of robustness, the ability of genomes to be combined and still have a high objective function value).

So, if the space of solutions that you're trying to optimize has moderately-high plateaus of pretty good but not great solutions that combine well with each other, and a few steep spikes of high quality solutions that do not combine well, you'll be stuck on the plateaus.

Papadimitriou then uses this observation to make inferences about sexual reproduction in nature, but that's getting off-topic again.


Finding the closest pair between two sets of points on the hypercube Given two subsets of the $d$-dimensional hypercube (i.e., $M, N \subseteq \{0,1\}^d$), I am looking for an algorithm which retrieves the points $m\in M, n\in N$ s.t. the hamming distance (or $L_1$-distance on the hypercube) $d_H(m,n)$ is minimal. The naive algorithm which checks just each pair needs $|M|\cdot |N| \cdot d$ time, is there any better result known?

For simplicity we may assume that $|M|=|N|=d$.

Just realized that you are asking for the case that $|M|=|N|=d$. Then you can do matrix multiplication, right? Write $M$ is a row matrix $X$, $N$ as a column matrix $Y$, negate the entries of $Y$, and compute the matrix $Z=XY$. Clearly, the $z_{i,j}$ is the Hamming distance between the $i$th point of $M$ and the $j$th point of $N$. According to the last breakthroughs this has running time $O(d^{2.3727})$ (but I have a 50,000 pages manuscript that shows how to do this matrix multiplication in $O(d^{2.3726999999})$ time by a really simple algorithm).

You can get similar effect if the matrices are not squares. I think Uri Zwick has a paper about fast matrix multiplication in this case.

In some sense, this is not too interesting - we want to avoid the $O(|M| * |N|)$  term. The improvements in the $d$ term are kind of meh, meh...


Questions on unification theory (and its application to DAG isomorphism ) While looking looking for an efficient and simple algorithm for directed acyclic graph isomorphism, I stumbled upon this which points out the similarity between DAG isomorphism and unification.  After learning a bit on the subject, I still have many questions about the relationships between the subjects.

Unification is said to be efficient on first order logic term. How efficient is it, exactly?
In my first analysis, it seems like DAG isomorphism should be reducible to unification, yet unification is efficient and DAG isomorphism is not. What am I missing? (I am of course assuming that every DAG can be transformed "efficiently" into a valid set of first order logic "expressions"... Is that correct?)
Is there a reference where the relationship between the subjects are explored?
How far can semantic unification go while staying efficient? Associations? Commutativity? Something else? Are there any papers on a real word application?

To give some context, the DAGs I am looking into are basic blocks DAGs from MIPS assembly language (or something close). I am working on the custom instruction selection problem where the goal is pretty much to identify subgraphs of the basic block DAG which should be implemented in hardware. I need to check for isomorphism to avoid having two separate hardware units performing the same operation.

Given my use-case, can someone point me in the direction of the best "isomorphism framework" (DAG isomorphism, unification, something else, etc...) to use?

An excellent starting point for information on unification theory
with some information on unification of term dags is the survey
by Baader and Snyder.
http://www.cs.bu.edu/~snyder/publications/UnifChapter.pdf


What are the best possible time/error tradeoffs for approximate solution of linear programs? For concreteness consider the LP for solving a two-player zero-sum game where each player has $n$ actions. Suppose each entry of the payoff matrix $A$ is at most 1 in absolute value. For simplicity let's make no sparsity assumptions.

Suppose runtime $T$ is available to approximate the value of this game.

One technique for approximating this value is the multiplicative update method (known as no-regret learning in this context). This gives an error of $\tilde O(\sqrt{n/T})$, where $\tilde O$ hides log factors.

I don't know exactly what the error landscape for the best known interior point method looks like, but I'm guessing the error is something like $O(\exp(-T/n^3))$.

The multiplicative update methods give error that's an inverse polynomial in $T$. Interior point methods give error that's exponentially small in $T$. The error of the best of the two therefore slowly decreases for a while until interior point catches up, after which the error suddenly falls off a cliff. My instincts are against the best possible time/error tradeoffs behaving this way.

My question:

Is there an algorithm for approximate linear programming that smoothes out the corner of the time/error tradeoff curve? That is, an algorithm that does at least as well as the best of the two for any value of the available time parameter and has a relatively smooth time/error tradeoff. A more intelligent way to combine interior-point and multiplicative update techniques than taking the better of the two is one likely way to get such an algorithm.

References:

Multiplicative update in general:

http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

Multiplicative update for zero-sum games:

http://dx.doi.org/10.1016/0167-6377(95)00032-0

Multiplicative update for covering/packing LPs:

http://arxiv.org/PS_cache/arxiv/pdf/0801/0801.1987v1.pdf

The original interior point paper:

http://math.stanford.edu/~lekheng/courses/302/classics/karmarkar.pdf

Interior-point from an applied math perspective:

Bertsekas's Nonlinear Programming, section 4.1.1.

Perhaps this reference will be relevant to your question.

Grigoriadis M., Khachiyan L. A sublinear randomized approximation algorithm to matrix games// Oper. Res. Lett. 1995. V. 18. No 2. P. 53-58.

The algorithm therein is 1) randomized 2) the error is ADDITIVE, but 3) is sublinear (you need to check only tiny fraction of the input to find solutiom with high probability).

Sergey


Graph classes in which CLIQUE is known to be NP-hard? Given a graph $G$ and a positive integer $k$, the CLIQUE problem asks if $G$ contains a clique (complete subgraph) on at least $k$ vertices. This problem is long known to be NP-complete --- in fact, it was one of Karp's list of 21 NP-complete problems. My question is:

  For what restricted families of graphs is CLIQUE known to be NP-complete?

I could find one such graph class with Google's help: the class of $t$-interval graphs for any $t\ge 3$ (Butman et al., TALG 2010) [1].

Do you know of other graph classes where this problem has been shown to be NP-complete?

[1] Butman, Hermelin, Lewenstein, Rawitz. Optimization problems in multiple-interval graphs. ACM Transactions on Algorithms 6(2), 2010

It's NP-complete to find maximum cliques in claw-free graphs [Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics 164 (1–3): 87–147] and in string graphs [Jan Kratochvíl and Jaroslav Nešetřil, INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs, Commentationes Mathematicae Universitatis Carolinae, Vol. 31 (1990), No. 1, 85–93]. At least as of the 1990 paper it was open whether the problem remained hard for intersection graphs of straight line segments.

However, finding maximum cliques easy for planar graphs, for minor-closed graph families, or more generally for any family of graphs with bounded degeneracy: find the minimum degree vertex, search for the largest clique among its O(1) neighbors, remove the vertex, and repeat. It's also easy for perfect graphs and the many important subfamilies of perfect graphs.

Although maximum independent set is hard for many other interesting graph classes, that doesn't generally lead to interesting hardness results for clique, because the complement of an interesting graph class is not necessarily itself interesting.


Applications of topology to computer science I'd like to write a survey on the applications of Topology in Computer
Science. I plan to cover the history of topological ideas in Computer
Science and also highlight a few current developments.  It would be
extremely helpful if anyone could give input regarding any of the
questions below.

Are there any papers or notes that describe the chronology of the
use of topology in Computer Science?
What are the most important application of results in Topology to
Computer Science?
What are the most interesting areas of current work that use
topology to gain insight into computation?

Thanks!

Personally, I think the most interesting application of topology was the work done by Herlihy and Shavit. They used algebraic topology to characterize asynchronous distributed computation and gave new proofs of important known results and knocked out a number of long-standing open problems. They won the 2004 Godel prize for that work.

"The Topological Structure of Asynchronous Computation"
by Maurice Herlihy and Nir Shavit,
Journal of the ACM, Vol. 46 (1999), 858-923,


Total number of spanning trees of a set of graphs Given an undirected graph G with $n$ nodes, we can compute its number of spanning trees in polynomial time using Kirchhoff's matrix-tree theorem. Now consider a more complicated setting, in which each of the $n$ nodes in the graph has $m$ versions and each version has different connectivity with the other nodes of the graph. The connectivity between different versions of different nodes can be encoded with a 4-dimensional array A where A[i][k][j][l] is 1 iff the $k$-th version of node $i$ is connected by an edge with the $l$-th version of node $j$. Therefore we have $m^n$ different graphs. We want to compute the total number of spanning trees in these $m^n$ graphs. The brute-force approach that computes the number of spanning trees in each graph separately would require exponential time. My question is whether there is a polynomial-time algorithm.

Can't this problem be used to compute the permanent of a 0-1 matrix? Since permanent is a #P-complete problem (harder than NP), there is very unlikely to a polynomial-time algorithm.

Suppose you have an $n \times n$ matrix $M$ that you want to compute the permanent of. Construct a graph on $2n+1$ vertices, where there is a special vertex $v$ which has one copy, and $n$ of the vertices $x_1$ $\ldots$, $x_n$ have only one copy, while the remaining $n$ vertices $y_1$, $\ldots$, $y_n$, have $n$ copies each. On the $i$'th copy of vertex $y_j$, connect it to $x_i$. Connect the $i$'th copy of $y_j$ to $v$ if and only if the entry $M(i,j) = 1$.

Now, for $x_i$ to be in the spanning tree, you must have chosen the $i$'th copy of $y_j$ for some $j$. So we must have a permutation $\pi$, where we have chosen the $\pi(j)$ copy of vertex $y_j$. For this permutation to be a spanning tree we must have $M(\pi(j), j) = 1$ for each vertex $j$. This shows that the permutation $\pi$ yields a spanning tree if and only if it contributes $1$ to the permanent of $M$. Thus, the number of spanning trees is the permanent of $M$.


Decomposing k-connected graphs into (k+1)-connected components A connected graph can be decomposed into its biconnected components. This block cutpoint tree is unique. Similarly, biconnected graphs can be decomposed into triconnected components. The corresponding SPQR tree describes all the 2-vertex cuts in the graph and is uniquely determined from its graph.

This process does not generalize to higher connectivity. For example, given a triconnected graph $G$, there can be multiple "trees" describing all the 3-vertex cuts of $G$.

  Are there special classes of graphs such that $k$-connected graphs (in these classes) can be decomposed uniquely into their $k+1$-connected components.

Note that my question is slightly different from this question.

The following recent paper seems to be related to your question:

Connectivity and tree structure in finite graphs
Johannes Carmesin, Reinhard Diestel, Fabian Hundertmark, Maya Stein

http://arxiv.org/abs/1105.1611


Difference between locally testable and it's boolean closure A language $L$ is called

i) locally testable in the strict sense iff there exists $P, S, I \subseteq X^*$ such that
$$
 w \in L \mbox{ iff } pref^k(w) \in P, suffix^k(w) \in S, infix^k(w) \subseteq I.
$$
for some $k > 0$.

ii) locally testable iff for $u,v \in X^*$ the following holds:

If $pref^k(u) = pref^k(v), suffix^k(u) = suffix^k(v), infix^k(u) = infix^k(v)$ then
$$
 u \in L \mbox{ iff } v \in L.
$$
Meaning if two words coincide in there infixes, suffix and prefix up to a specific length $k > 0$ then they are either both in the language or they are both not.

iii) the class of locally testable events with order is defined as the smallest class of languages containing the locally testable languages and closed under the boolean operations union, intersection and complementation. (this could be equivalently defined with locally testable in the strict sense instead of locally testable)

In what sense do they differ, that iii) contains more languages is clear, for example the language which contains for example $00$ followed by $01$ is in iii) but not in ii) or i) I think (because it involves some kind of order in requiring that $01$ need to follow $00$), but in what sense are ii) and i) different, what is a languge contained in ii) but no in i)?

In ii), you say that $u$ being in $L$ can be deduced only by knowing $pref^k(u)$, $inf^k(u)$ and $suff^k(u)$.

This mean that $L$ can be given by a set $E\subseteq (X^*\times 2^{X^*}\times X^*)$, namely $u\in L$ iff $(pref^k(u),inf^k(u),suff^k(u))\in E$.

The reason why condition i) is stronger is because it forces $E$ to be of the form $P\times 2^I\times S$.

An example of a language which is in ii) but not i) is therefore given by $E=\{ (a,X^*,a),  a\in X\}$. This means that $L$ is just the language of words whose last letter is equal to the first. $L$ is locally testable with $k=1$ for condition ii), but it is not for any $k$ for condition i).


What is the best approximation and exact algorithm for vertex cover on cubic graphs? "Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.

The best-known algorithm for vertex cover in (general) graphs runs in time $O(1.2114^n)$ by Bourgeois, Escoffier, Paschos and van Rooij. You may read their paper and see whether their algorithm can be improved for cubic graphs.

Bourgeois, N., Escoffier, B., Paschos, V. T., & van Rooij, J. M. (2012). Fast algorithms for max independent set. Algorithmica, 62(1-2), 382-415.

Moreover, the following paper proves a hardness result for an ($1+\epsilon$) approximation algorithm for vertex cover in cubic graphs.

Alimonti, P., & Kann, V. (1997, March). Hardness of approximating problems on cubic graphs. In Italian Conference on Algorithms and Complexity (pp. 288-298). Springer, Berlin, Heidelberg.

However, a greedy 2-approximation algorithm for vertex cover in general graphs is easy. Just pick an uncovered edge each time and choose both of its ends.


Definition of a prefix-free Turing machine A prefix-free function is one whose domain is prefix-free.
  Similarly, a prefix-free (Turing) machine is one whose domain is
  prefix-free. It is usual to consider such a machine as being
  self-demiliting, which means that it has a one-way read head that halts when the machine accepts the string described by the bits read
  so far. The point is that such a machine is forced to accept strings
  without knowing whether there are any more bits written on the input
  tape.

From Downey and Hirschfeldt, Algorithmic Randomness and Complexity, page 122.

I don't understand why such a device would ensure that the domain of the function is prefix-free. Take a word $\omega$ accepted by the machine. Then, as the next bits won't be read, $\omega \eta$ is also accepted. So $\omega$ and $\omega \eta$ are in the domain, which is not prefix-free.

Where am I wrong ?

If you were using a self-delimiting machine as described, you have to change your notion of what it means for the machine to accept a string. You want to say that the machine accepts a string $\omega$ if it halts in an accept state with the read head on the last symbol. The idea is to think of the computation as a loop: it first asks whether $\omega\upharpoonright 1$ is in the language, then whether $\omega \upharpoonright 2$ is, and so forth, and it halts if it finds a prefix of $\omega$ in the language or if it runs out of bits of $\omega$.

The point is that if the input tape contains an infinite juxtaposed sequence of nonempty words from the language, the prefix free machine can be used to parse out the individual words from the sequence.  The definition of a prefix-free machine from the book is designed for this sort of application, not for the problem of deciding whether an individual word is in the language.


Simple k-nearest-neighbor algorithm for euclidean data with highly variable density? An elaboration on this question, but with more constraints.

The idea is the same, to find a simple, fast algorithm for k-nearest-neighbors in 2 euclidean dimensions.  The bucketing grid seems to work nicely if you can find a grid size that will suitably partition your data.  However, what if the data is not uniformly distributed, but has areas with both very high and very low density (for example, the US population), so that no fixed grid size could guarantee both enough neighbors and efficiency?  Can this method still be salvaged?

If not, other suggestions would be helpful.

I'd recommend using a kd-tree or an R-tree. These structures automatically partition the data.

A kd-tree (k-dimensional tree) is a binary tree in which every node is a point. Every non-leaf node splits the space in half along one of the axes. Points on one side of the split form the left subtree, points on another side form the right subtree. A kd-tree has guaranteed space complexity O(n) and average search, insertion and deletion complexity of O(log n). The cost of building the tree is O(n log n) when using an advanced linear median-finding algorithm. The k-nearest-neighbors search boils down to moving down the tree, checking distances to the elements in final subtree and unwinding the recursion up the tree if more elements are needed. kd-trees are easy to implement in memory, but non-trivial to implement on disk. They may need to be rebuilt when changing data.

R-trees (rectangle trees) group nearby objects in minimum bounding rectangles, group the rectangles in larger rectangles, and so on. This means that they can store not only points, but also polygons. The complexity of search is between O(log n) and O(n), depending on the amount of overlap between rectangles. There are various optimization strategies and algorithms for splitting overflowing nodes and bulk-loading. While more complicated, R-trees have advantages over kd-trees. They are more disk-oriented, making them useful for real databases. Unlike non-bulk-loaded kd-trees, they are balanced, and therefore preferred for changing data.

In conclusion, if the data will change after building the tree or you want the data to be stored on disk, I'd use an R-tree, otherwise kd-tree.


Why does Huffman coding eliminate entropy that Lempel-Ziv doesn't? The popular DEFLATE algorithm uses Huffman coding on top of Lempel-Ziv.

In general, if we have a random source of data (= 1 bit entropy/bit), no encoding, including Huffman, is likely to compress it on average.  If Lempel-Ziv were "perfect" (which it approaches for most classes of sources, as the length goes to infinity), post encoding with Huffman wouldn't help.  Of course, Lempel-Ziv isn't perfect, at least with finite length, and so some redundancy remains.

It is this remaining redundancy which the Huffman coding partially eliminates and thereby improves compression.

My question is: Why is this remaining redundancy successfully eliminated by Huffman coding and not LZ? What properties of Huffman versus LZ make this happen? Would simply running LZ again (that is, encoding the LZ compressed data with LZ a second time) accomplish something similar? If not, why not? Likewise, would first compressing with Huffman and then afterwards with LZ work, and if not, why?

UPDATE:
It is clear that even after LZ, some redundancy will remain.  Several people have made that point.  What isn't clear is: Why is that remaining redundancy better addressed by Huffman than LZ? What's unique about it in contrast with the original source redundancy, where LZ works better than Huffman?

This was originally a comment, but it got too long.

If you look at DEFLATE, what is being compressed by Huffman is the output of LZ77; LZ77 works by (when this takes fewer bits than the raw data) sending an pointer earlier into the string being compressed, and a match length that tells how many symbols to take after the pointer. The theory shows that, even without additional compression, this technique eventually converges to the source entropy. However, in data compression, any time you have a distribution that isn't completely random, you might as well compress it. There's no reason to believe that the output of LZ77—the pointers and the match lengths—are completely random. They have to converge to complete randomness in the asymptotic limit, since LZ77 is asymptotically optimal, but in practice you only use a finite dictionary, so they presumably stay far enough away from being completely random that you win by doing further compression on them. Naturally, you use one Huffman code for the pointers and another for the match lengths, since these two processes have different statistics.

Why use Huffman rather than LZ for the second round of compression? The big advantage LZ has over Huffman is in treating dependencies between symbols. In English, if one letter is a 'q', the next is extremely likely to be a 'u', and so on. If the symbols are independent events, then Huffman is simpler and works just as well or better for short strings. For the output of LZ77, my intuition is that the symbols should be fairly independent, so Huffman should work better.


Importance of irrational numbers in computer science Computers can only deal with a few rational numbers. Why is it important as a computer scientist to deal with irrational numbers?

The question displays a fundamental misunderstanding about the nature of what can be done with computers.  To correct this misunderstanding, I suggest getting a copy of the computer algebra software Maple and trying the commands

expand((1+sqrt(2))^5);
sin(Pi/4);

If computers can only deal with rational numbers, how do you explain the results?


Is there a simple algorithm for proof search on CoC? Given the usual Calculus of Constructions with an extra primitive, _, that stands for "attempt to fill this location in a way that type-checks", is there any simple/elegant algorithm capable of solving this problem for a large class of terms? For example, given the term below:

λ (N : Type)
λ (S : {x : N} N)
λ (Z : N)
λ (A : {x : N} Type)
λ (B : {x : N} (A x))
λ (C : {x : (A (S (S (S Z))))} Type)
(C _)

The algorithm would replace _ by (B (S (S (S Z)))),  as it is the only substitution that makes the resulting term well-typed. I'm specifically looking for keywords / references, as I believe this is a pretty well-researched subject (given that most theorem provers feature proof search), but I've never seen an algorithm described in a simpler setup (like plain CoC).

Is there a simple algorithm? yes. Simply enumerate all possibilities.  Of course this is pretty intractable in practice.

A proper sub-problem of term generation in CoC is "higher-order unification".  It handles the simply typed lambda calculus.  It is undecidable.  But there is a classic practical solution by Huet.  There are a lot of resources here: https://stackoverflow.com/questions/1936432/higher-order-unification.

Now the only good reference I know for CoC term generation is "A Complete Proof Synthesis Method for the Cube of Type Systems" by Dowek.  I believe this summarizes his thesis work (in french) and there is a draft pdf floating around (it has some errors).  His r-splitting construction is a little awkward for implementations, but he does a good job of highlighting the difficulties, and suggesting practical in-complete solutions.


Is there a succinct representation for all problems? Recently I saw an interesting question on succinct problems from here. I was wondering if all problems have a succinct representation(It would be great if you can provide me a reference/proof). When I read the paper linked in the post, I could find mostly only graph problems with succinct representation. Can a problem like testing for primality have a succinct representation? Is there a proof/reference for this anywhere?

Any language $L$ consisting of strings of length $2^k$ for nonnegative integers k has a succinct version: given a binary circuit $C$ that takes $k$ inputs and outputs a single bit, is the truth table (seen as a binary string of length $2^k$) a string of the language $L$. You can restrict any language to strings whose length is a power of two, or you can try other encoding tricks.


Hartmanis-Stearns conjecture and the computable transcendental numbers In the 1965 article "On the computational complexity of algorithms" by Hartmanis and Stearns, the authors conjecture that if a real-time Turing Machine computes the real number $r$ in, for example, base 10, then $r$ is either a rational number or a transcendental number.

Is there a computable transcendental number that is not computable by a real-time Turing machine in, for example, base 10?

Let $L$ be an EXPTIME-complete language, and let $r \in (0,1)$ be the corresponding real. Clearly $r$ is computable. The number $r$ cannot be algebraic since the $n$th bit of an algebraic number can be computed in time $n^{O(1)}$ (Datta and Pratap). Since the $n$th bit of any number computable by a real-time Turing machine can be computed in time $O(n)$, $r$ cannot be computed by a real-time Turing machine.


A question in constraint based analysis I may have a very naive question on Constraint Based Analysis. (a technique of static program analysis).

I am reading an informal introduction from F. Nielson

He gives such an example,

let f = fn x => x 1;
    g = fn y => y + 2;
    h = fn z => z + 3
in (f g) + (f h)

The author explained that:

  ...the problem is that we cannot immediately point to the body of x:
  we need to know what parameters f will be called with. This is exactly
  the information that the Control Flow Analysis gives us:

  For each function application, which functions may be applied.

However, in my naive point of view, this information can be obtained statically and exactly, at least seen from this example. It suffices to check the "in-" part of the instruction "let...in..." to decide the functions that may be applied, doesn't it??
Although I do see in OO programming, it would not be evident to decide what the virtual calls really calls at run-time, I find from this above example that this piece of information can be obtained in a trivial way by looking at its syntax.

So where am I wrong? Thank you for your ideas.

Can you point to where this example comes from? It might help.

I think the author is trying to express something a little different than what you're anticipating with this example. For instance, for a C programmer reading this introduction, this example would illustrate that "x 1" in the first line isn't like x(1) in C, it's more like (*x)(1) in C -- you're calling a function there, sure, you even know the type of the function you're calling, but you don't know which function. Certainly you are correct that in this example you can figure out "oh, it's either got to be the function associated with g or the function associated with h." But I posit that when you sort this out in your own head, what you're doing is just executing the program, which is of course the most straightforward way of "statically analyzing" any terminating code!

The example is small; any example that's going to be easy enough for you to straightforwardly understand is, almost by definition, going to be one where your brain can "statically" figure out the answer. The challenge that Control Flow Analysis tries to solve is working over potentially large programs, quickly and precisely.


From Extractors to Pseudorandom Generators? Luca Trevisan showed how many constructions of pseudorandom generators can in fact be thought of as extractor constructions:

http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf

Is there a meaningful converse? I.e., can "natural" constructions of extractors be thought of as pseudorandom generators (PRG) constructions?

Extractor constructions seem to correspond to distributions over PRGs (such that any distinguisher won't succeed in distinguishing for almost all of them). Are there known applications for this?

Salil Vadhan wrote to me that the answer to my question is known, and PRGs are equivalent to extractors.

Quoting him:

"See Proposition 21 and the discussion following it in my survey http://people.seas.harvard.edu/~salil/research/unified-icm.pdf
(There's a typo - "black-box hardness amplifier" should be "black-box PRG construction")

It says extractors are equivalent to black-box PRG constructions where you only care about the amount of advice, and not the running time, in the reduction.  Asking for bounded running time amounts to asking for extractors with "local list-decoding"."