Methods of converting an image to graph In my thesis on object recognition based on spatial relations and visual features, I need to convert the images to graphs to be able to work on their spatial relations. Could you introduce some methods you're familiar with along with their advantages and disadvantages? Google yielded no relevant results.

I haven't done much research yet, except for reading a few articles to get familiar with different approaches and methods and have a clear view of what I want to do. Going through this article, a method is proposed for converting an image to graph, which is called irregular pyramids. So all I want to know is whether there are other methods for such propose?

I'm not an expert, but perhaps this recent survey can help you:

K. Santle Camilus, V. K. Govindan, A Review on Graph Based Segmentation;
I.J. Image, Graphics and Signal Processing, 2012, 5, 1-13

Abstract: ... The major
four categorizations we have employed for the purpose of
review are: graph cut based methods, interactive methods,
minimum spanning tree based methods and pyramid
based methods. This review not only reveals the pros in
each method and category but also explores its
limitations. ...


How to define a function inductively on two arguments in Coq? How can I convince Coq that the recursive function given below terminates?
The function takes two inductive arguments.
Intuitively, the recursion terminates because either argument is decomposed.

Specifically, the function takes two trees as input.

Inductive Tree :=
| Tip: Tree
| Bin: Tree -> Tree -> Tree.

On Trees, I like to do the following style of induction.

Inductive TreePair :=
| TipTip : TreePair
| TipBin : Tree -> Tree -> TreePair
| BinTip : Tree -> Tree -> TreePair
| BinBin : TreePair -> TreePair -> TreePair.

Fixpoint pair (l r: Tree): TreePair :=
  match l with
    | Tip =>
      match r with
        | Tip => TipTip
        | Bin rl rr => TipBin rl rr
      end
    | Bin ll lr =>
      match r with
        | Tip => BinTip ll lr
        | Bin rl rr => BinBin (pair l rl) (pair lr r)
      end
  end.

The definition of TreePair is accepted, but the definition of the function pair yields the error message:

Error: Cannot guess decreasing argument of fix.

So I am interested in how to convince Coq of the termination.

Coq's fixpoint definitions require that inductive calls receive a structurally smaller argument. Deep down, a fixpoint construct takes a single argument: there's no built-in concept of a recursive definition over two arguments. Fortunately, Coq's definition of structurally smaller includes higher-order types, which is extremely powerful.

Your two-argument fixpoint definition follows a simple pattern: either the first argument becomes smaller, or the first argument remains identical and the second argument becomes smaller. This fairly common pattern can be handled by a simple fix-in-fix.

Fixpoint pair l := fix pair1 (r : Tree) :=
  match l with
    | Tip => match r with
              | Tip => TipTip
              | Bin rl rr => TipBin rl rr
            end
    | Bin ll lr => match r with
                    | Tip => BinTip ll lr
                    | Bin rl rr => BinBin (pair1 rl) (pair lr r)
                   end
  end.

For more complex cases, or if your tastes run that way, you can use recursion closer to the way it's taught in math courses, building the fixpoint from a step computation and a separate well-foundedness argument, often using an integer measure. You can also make your definition look more like a classical program in a non-total language with a separate termination using the Program vernacular.


Reductions between languages of different densities? The density of a language $X$ is a function $d_X \colon \mathbb{N} \to \mathbb{N}$ defined as $$d_X(n) = |\{x\in X \mid |x| \le n\}|.$$
Suppose $A$ and $B$ are languages over some finite alphabet, $A$ many-one logspace reduces to $B$, and $B$ is not in $\textsf{L} = \text{DSPACE}(\log n)$.
Functions $f,g \colon\mathbb{N} \to \mathbb{N}$ are polynomially related if there are polynomials $p$ and $q$ such that for all $n\in \mathbb{N}$, $f(n) \le p(g(n))$ and $g(n) \le q(f(n))$.

  If the density of $A$ is not polynomially related to the density of $B$, can there be a logspace reduction from $B$ to $A$?

Background

I expect the answer is no, but can't currently show this.

Clearly, if $A$ is in $\mathsf{L}$ then there is no logspace reduction from $B$ to $A$.
So there are some examples for which it is possible to provide a definite negative answer.

I first had in mind the case where $B$ is some hard language, and $A$ is obtained by blowing holes in $B$ by taking $A = B\cap G$, for some gap language $G$ which contains all words of length $n \in S_G$ for some set $S_G \subseteq \mathbb{N}$ (see Schmidt 1985 and also Regan and Vollmer 1997).
This guarantees a trivial reduction from $A$ to $B$.
Gap languages $G$ usually have exponentially increasing gaps between the intervals of sizes in $S_G$.
This ensures that the densities of $A$ and $B$ are not polynomially related.
However, there is no guarantee that blowing holes in a language always gives rise to a language that has too little structure to be the target of a reduction from $B$.
(The term blowing holes is from Downey and Fortnow 2003.)
The difference in densities might be enough to guarantee this, but I don't immediately see how.

Another example is when $B$ is a mixture of a hard language and $A$.
First create a gappy language $A\not\in\mathsf{L}$ by intersecting some language $C \not\in \textsf{L}$ with a gap language $G$.
$A$ will then only contain instances of sizes that are in the intervals of the set of sizes $S_G$ determining the gap language.
Now create $B$ by mixing $A$ with some hard language $D$ in the gaps, by taking the union of $A$ and the intersection of $D$ with the complement of $G$.
If $D$ is hard enough compared to $C$, such as $D$ being $\textsf{2EXPSPACE}$-hard while $C \in \textsf{PSPACE} \setminus \textsf{L}$, then by the space hierarchy theorem there can be no logspace reduction from $D$ to $A$.
It then seems possible to extend this to show that there is no logspace reduction from $B$ to $A$.

This still leaves the situation where $D$ is harder than $C$ but "not too much", for instance take $D$ to be SAT and $C$ to be STCON, or $D$ to be QBF-SAT and $C$ to be SAT.
To get a result, one might have to assume $\mathsf{L} \ne \mathsf{NP}$ for STCON/SAT or $\mathsf{NP} \ne \mathsf{PSPACE}$ for SAT/QBF-SAT, but it is not immediately clear to me how to use these assumptions.

Let $A$ be any language not in $L$, such that $A$ has density $2^{o(n)}$, and define
$$B = \{s \circ 1 | s \in \{0,1\}^*\} \cup \{s \circ 0 | s \in A\}.$$
Here $\circ$ is concatenation. The language $B$ has density $\Omega(2^n)$, which is superpolynomial in $2^{o(n)}$. On the other hand, $A$ and $B$ log-space reduce to each other ($A$ to $B$ by concatenating $0$, and $B$ to $A$ by reducing all strings ending in $1$ to the smallest yes instance of A, and removing the last bit from all strings ending in $0$). Hence $B \notin L$ as well.


Generalizing linear interpolation to posets Assume that I have an array $A$ of $n$ numerical values where some are known and some are unknown (with $A[0]$ and $A[n-1]$ assumed to be known). If I want to estimate an unknown value $A[i]$, a reasonable way is to perform linear interpolation: find the largest $j < i$ such that $A[j]$ is known, find the smallest $k > i$ such that $A[k]$ is known, and do a weighted average $A[j] := {k-i \over k-j}A[k] + {i-j \over k-j}A[j]$. In particular, this ensures that the following property (*) holds:

$$\text{if } A[j] \leq A[k] \text{ then } A[j] \leq A[i] \leq A[k]$$

Now, you can see an array as a totally ordered structure, and wonder about what would happen in the case of a partial order. Assume that I have a DAG $G = (V, E)$ of $n$ nodes where every node $v \in V$ has a numerical value $\mu(v)$ where some values are known and some are unknown (with the values of the roots and leaves assumed to be known). If I want to estimate some unknown $\mu(v)$, it seems that I should interpolate it out of the values of the closest ancestors and descendents of $v$ whose values are known. The question is: what should we do, exactly? Is there a generalization of linear interpolation in this setting?

[Here is a possible choice: for every couple $(u, w)$ of ancestors and descendents of $v$, perform linear interpolation along all the possible chains between $u$, $v$ and $w$ to get a value for $v$, and average all the values over all chains and ancestor-descendent pairs to get your final estimate. Is this the correct way to do things? Can this estimation be computed more efficiently than with this definition? (i.e., could we do it in linear time in the size of the neighborhood of $v$ under consideration, rather than in a quadratic way?). Do we still have some variant of property (*)? (note that, even if you assume monotonicity, i.e. for each ancestor-descendent couple $(u, w)$ you assume $\mu(u) \leq \mu(w)$, then the estimation $\mu(v)$ obtained by the previous process may still violate monotonicity, i.e. $\mu(v) > \mu(u)$ for some ancestor $u$ of $v$)]

In a recent paper, we propose such a scheme. The scheme is illustated in a specific crowdsourcing application setting, but the idea is fairly simple. We just see the order constraint $\mu(u) \leq \mu(v)$ of each DAG edge $(u, v)$ as a linear inequality constraint, we consider the admissible convex polytope of assignments to these linear inequalities, and we choose the center of mass of this polytope as our interpolation result.

The paper explains the scheme in more detail, includes an algorithm, computational hardness results, an approximation scheme that derives from existing work, a tractable case when the DAG is a tree, and a discussion of alternate schemes.


Getting started with Hashing for Information retrieval I  recently finished my bachelors and now work on Cross-lingual language  search. I want to get started in hashing and see how they are useful  in information retrieval. (Yes, I know what hashing is), but there are so many methods and all of them  sound  pretty fascinating,  so it will be awesome to have a list of resources, which can be referred to,  starting from absolute newbie level to the current state-of-the art.

Please don't refer me to something like a Knuth because while Knuth is pretty awesome, it is not what i am looking for.

Probably this may help you. May not cover all but I found this as a great place to start. http://burtleburtle.net/bob/hash/


Vertex subset of maximum size I was wondering if this problem has a name and/or it has been already studied.

  Problem: Given an undirected graph $G=(V,E)$, a function $f: V \to \mathbb N$, and a natural number $k$ :
  Does there exist a subset $S\subseteq V$ with $|S| \geqslant k$, such that
  $$ \forall v \in V \,:\, \biggl|\;\Bigr(N(v) \cup \{v\}\Bigr) \cap S\;\biggr| \;\leqslant\; f(v) \;?$$

Question.
Is this problem NP-complete? Are there good approximation algorithms?

I think a general polynomial time solution to this would be able to be used to solve k-SAT.

For each variable create two vertexes corresponding to true and false and connect them by an edge. Start by assigning k to to the number of variables (half the number of vertexes), and each of their f values to 1. Let not being in S mean true or false. Now we have a graph where each variable has to be either true or false.

For each OR operation on x variables create one vertex and connect it to the appropriate true/false vertexes.

For each OR operation create a large number Z of auxilary vertexes with an f value of 1, and connect each by an edge to the OR vertex. Increment k by Z for each OR operation. We can see this will force the OR operation vertex to not be a member of S, and all the auxilary vertexes to be in S.

Now assign the f value of each OR vertex to Z+x-1. Z of these will be taken by the auxilary vertexes.  The OR vertex is not in S, so this means at maximum x-1 of the connected variable vertexes can be in S, so at least one of the variable nodes connected to an OR vertex will have to not be in S.


Expressiveness of Infinitary Logic I'm trying to put together a general picture of the expressiveness of some logics: First-Order Logics, Fixed-Point Logics, (Finite Variable) Infinitary Logics and the respected versions with Counting. (Source)

$\mathcal{L}^k_{\infty\omega}$ is infinitary logic with $k$ distinct variables and

$$\mathcal{L}^\omega_{\infty\omega} := \bigcup_{k \in \omega}  \mathcal{L}^k_{\infty\omega}$$

is finite variable infinitary logic. (Analog for Counting)

This is in the context of Finite Model Theory so in general all structures are finite.

  We say  $\varphi$ and $\varphi'$ are equivalent if for every structure
  $\mathcal A$

  $$ \mathcal A \models_\mathcal L \varphi \Leftrightarrow \mathcal A
> \models_{\mathcal {L'}}  \varphi'.$$

  If for every $\mathcal L$-sentence there is a equivalent
  $\mathcal L'$-sentence we write

  $$ \mathcal L \leqq \mathcal L'.$$

Most of the relations are relatively straight-forward. $\mathcal{L}^\omega_{\infty\omega}$ cannot express that a graph has an even number of nodes. Hence, both $\mathcal{L}_{\infty\omega}$ and $\mathcal{C}^\omega_{\infty\omega}$ are
strictly stronger because they can express any predicate over finite structures.

A though one is $\mathcal{L}_{\infty\omega} \equiv \mathcal{C}_{\infty\omega}$. I think this is correct since $\mathcal{L}_{\infty\omega}$ can express every predicate, thus adding counting should not make it more powerful. This it far from a proof but at most an intuition. Any ideas?

The other one I don't know is $\mathcal{C}^\omega_{\infty\omega} \lneqq \mathcal{C}_{\infty\omega}$. Again my intuition is that it is correct: How can we express any predicate with finite variables even with Counting? Any ideas on that? Maybe an example which is not expressible in
$\mathcal{C}^\omega_{\infty\omega}$?

There is a famous example of Cai, Fürer and Immerman, which shows that the $\mathcal{C}_{\infty\omega}^k$-hierarchy is strict and in particular that $\mathcal{C}_{\infty\omega}^\omega$ cannot express every query on finite structures. The paper is quite famous because it disproved a conjecture that IFP+C captures PTIME. Your proof that $\mathcal{L}_{\infty\omega}\equiv\mathcal{C}_{\infty\omega}$ is correct.


Formal proof of correctness of Levenshtein distance Has anyone formalized, in a proof assistant (constructively!) the correctness of the computation of Levenshtein distance ? The related Q&A on here is about paper proofs.  Searching around did not come up with any leads.
Note that I'm equally interested in correctness as that of a proof of optimality, i.e. knowing that an algorithm returns a correct sequence of edits, from which the distance is trivially computed, is quite interesting too. That the sequence is optimal can be a second step.

As pointed out in a comment above, the answer is yes, in Lean.  See the paper and the code as linked into comments.
I was rather hoping Agda or Idris... but perhaps the Lean formalization is actually constructive.


upper bound on the size of a DFA for A|B given the DFAs for A and B? Given RegEx A and B where the size of the compiled DFAs are m and n respectively, what is the upper bound on the size of the compile DFA for A|B? It shouldn't be hard to show that it can't be more than n*m but can a lower upper bound be shown?

What about other related case:

What is the expected case for real world examples? Is it less than n+m?
What about the three part case with A, B and C?

The upper bound of $nm$ follows from the usual Cartesian product construction that you will find in just about any book on automata theory.  A lower bound of $nm$ is observed (for the case $\operatorname{gcd}(n,m) = 1$) in this paper:

  Sheng Yu.  State Complexity of Regular Languages.  Journal of Automata, Languages and Combinatorics, 2001.

The lower bound is proved for DFAs that I would consider to exist in the real world -- but if you want an expectation you will have to be more precise about the distribution from which $A$ and $B$ are drawn.

The bound is simple and can surely be extended to three DFAs.


Match a string agains a set of regexes There are several algorithms to match a (simple) string against a regular expression (see here).
But if we have a lot of regexes, can we find one of them that matches the given string faster than checking the string with all of the regexes, one by one?
For example, if we have $k$ regexes, each with a length of $m$ and a string of length $n$, using the $O(mn)$ algorithm to match a string with a regex $k$ times gives us a running time of $O(kmn)$. Can we do better than this?
If you have an answer which requires some assumptions, please explicitly tell them.

Hyperscan is a high-performance multiple regex matching library that uses hybrid automata techniques to allow simultaneous matching of large numbers of regular expressions across streams of data. They explained their approach here:
https://www.hyperscan.io/2015/10/20/match-regular-expressions
Apparently, they didn't find a fast algorithm (in the worst case) for this problem: "We have not found a single, elegant automata approach that handles arbitrary regular expressions in arbitrary number". However, they used a lot of optimization which works well enough in practice.
I also believe that in the worst case, the given regular expressions can be so complex that no better solution exists.


Complexity of the search version of 2-SAT assuming $\mathsf{L = NL}$ If $\mathsf{L = NL}$, then there is a logspace algorithm that solves the decision version of 2-SAT.

Is $\mathsf{L = NL}$ known to imply that there is a logspace algorithm to obtain a satisfying assignment, when given a satisfiable 2-SAT instance as input?
If not, what about algorithms which use sub-linear space (in the number of clauses)?

Given a satisfiable 2-CNF $\phi$, you can compute a particular satisfying assignment $e$ by an NL-function (that is, there is an NL-predicate $P(\phi,i)$ that tells you whether $e(x_i)$ is true). One way to do that is described below. I will freely use the fact that NL is closed under $\mathrm{AC}^0$-reductions, hence NL-functions are closed under composition; this is a consequence of NL = coNL.

Let $\phi(x_1,\dots,x_n)$ be a satisfiable 2-CNF. For any literal $a$, let $a^\to$ be the number of literals reachable from $a$ by a directed path in the implication graph of $\phi$, and $\let\ot\leftarrow a^\ot$ the number of literals from which $a$ is reachable. Both are computable in NL.

Observe that $\let\ob\overline \ob a^\to=a^\ot$, and $\ob a^\ot=a^\to$, due to skew-symmetry of the implication graph. Define an assignment $e$ so that

if $a^\ot>a^\to$, then $e(a)=1$;
if $a^\ot<a^\to$, then $e(a)=0$;
if $a^\ot=a^\to$, let $i$ be minimal such that $x_i$ or $\ob x_i$ appears in the strongly connected component of $a$ (it cannot be both, as $\phi$ is satisfiable). Put $e(a)=1$ if $x_i$ appears, and $e(a)=0$ otherwise.

The skew-symmetry of the graph implies that $e(\ob a)=\ob{e(a)}$, hence this is a well-defined assignment. Moreover, for any edge $a\to b$ in the implication graph:

If $a$ is not reachable from $b$, then $a^\ot<b^\ot$, and $a^\to>b^\to$. Thus, $e(a)=1$ implies $e(b)=1$.
Otherwise, $a$ and $b$ are in the same strongly connected component, and $a^\ot=b^\ot$, $a^\to=b^\to$. Thus, $e(a)=e(b)$.

It follows that $e(\phi)=1$.


Can any language be modeled as LR(k) If L(G1) is the language that is produced by grammar G1 and G1 is not LR(k) parsable (specifically speaking for k = 1). Does there exist a grammar Gx that is L(Gx) = L(G1) where Gx is LR(1) parsable ? If that is possible can it be generalized to all possible languages or just a subset?

You can mechanically transform an LR(k) grammar into an LR(1) grammar (source)

This is not true for LR(*) grammars (k=inf). However, that statement doesn't mean that there isn't such a grammar for the same language. You might just need to rewrite the grammar.

Grammars exist that cannot be transformed, however. Languages for Context-Sensitive grammars can be more expressive than context-free grammars (can only be recognized by linear-bounded automata). Therefore, your hoped-for translation is possible for just a subset.

Update for clarification:

There are languages that can not be represented by LR grammars but do have a grammar that is not LR (the language requires something more powerful than LR). There are also grammars that are not LR that recognize a language that can be recognized by an LR grammar (the language just happens to have a complex grammar, but it is not required).


doubt about two minesweeper gadgets (Unlike most posts on stackexchange with that word,

I really do doubt that they work as described.)

In Figure 15 of this paper, the cells two to the right of the leftmost circle and two to the left of the rightmost circle hold the values 3 and 1 respectively. $\:$ Due to the rows of 1s that are three above each of those circles, the mostly-blank area is presumably supposed to have no mines, which would make the value 3 impossible. $\:$ Since the figure is otherwise mostly symmetric, I believe the 3 I mentioned two sentences ago should be replaced with a 1. $\:$ However, even if that is done, I do not see any way to determine the status of the $z$s even after both $r$ and $s$ are revealed, despite the three sentences on the previous page whose middle sentence starts with "Additionally". $\:$ For the same reason, Figure 14 also does not seem to do what it is supposed to.

  Am I missing something here?

Since the figure is otherwise mostly symmetric, I believe the 3 I mentioned two sentences ago should be replaced with a 1.

Indeed, the 3 is obviously a typo.

  However, even if that is done, I do not see any way to determine the status of the zs even after...

  Am I missing something here?

After $r$ is revealed:

If it was a mine, you can reveal the numbers on the fields occupied by $r'$.
If it was not a mine, you can reveal the numbers on the fields occupied by $r$.

In both cases, you can deduce the status of the $z$s from the revealed numbers.


What is known about learning a maximal independent set in a (very) sparse graph? Maximal independent set is known to be hard in many meanings (hard to approximate, $W[1]$-hard, etc.). But if the number of edges is very small, then the problem becomes simpler. Here, I'm interested in learning an independent set from an unknown graph.
Assume that we have an unknown sparse graph $G=(V,E)$ with at most $k\ll |V|$ edges ($k$ is given).
We want to find a maximal independent set for the graph using as few queries as possible, where Query$(S)$, for some $S\subseteq V$ returns 1 if $S$ is an independent set and $0$ otherwise.
For example, if $k=1$, we can find an independent set of size $n-1$ using $\Theta(\log n)$ queries.

What is the query complexity for general $k$?
If I want to learn the exact graph (rather than just a maximal independent set), is the query complexity similar?

For $k=1$ we can also find the edge using $\Theta(\log n)$ queries.
The run time of the algorithm here can be arbitrary, all I care about is the query complexity.

Roughly $O(k \log(n/k))$ queries suffice, in the regime you are talking about.

We can equivalently think of this as finding a minimal vertex cover for $G$, given ability to query whether a particular set is a vertex cover or not.  The  algorithm is as follows:

Let $S := V$ (the set of all vertices).
While $S$ is not a minimal vertex cover:

Pick a random subset $T \subseteq S$ of size $|T| = \lceil |S|/k \rceil$.
If $S \setminus T$ is a vertex cover, let $S := S \setminus T$.

Note that the final vertex cover will have size $\le k$.

How many iterations does this take to converge?  Well, for $S \setminus T$ to be a vertex cover, $T$ must avoid all of the vertices in the final minimal vertex cover, so the probability that a $S \setminus T$ is a vertex cover is at least

$$\left(1 - {k \over |S|}\right)^{|T|} \approx \left(1 - {k \over |S|}\right)^{|S|/k} \approx 1/e.$$

In other words, there is a constant probability in each iteration that $S \setminus T$ is a vertex cover.  Thus, the total number of iterations is proportional to the number of times that we succeed in reducing the size of $S$.

Each time that we successfully reduce the size of $S$, we multiply its size by a factor of $1 - 1/k$.  We start with $n$ vertices, and end with about $k$ vertices, so the number of reductions $r$ satisfies

$$n \times \left(1 - {1 \over k}\right)^r = k,$$

or in other words,

$$r = {\log(k/n) \over \log(1 - 1/k)} \approx k \log(k/n).$$

Thus, we do a total of $O(k \log(k/n))$ iterations, i.e., a total of $O(k \log(k/n))$ queries.  When the algorithm terminates, we have found a minimal vertex cover.

What is the cost of testing the termination condition?  The algorithm terminates when we have already tried all possible subsets $T$ of $S$ and none of them can be removed from $S$ ($S \setminus T$ was not a vertex cover for any subset $T$ of size $\lceil |S|/k \rceil$).  Note that we'll end with a vertex cover of size $\le k$, so in the last iterations, $|T|=1$, so it'll only take $O(k \log k)$ iterations before we've tried all possibilities for $T$.  At that point the procedure terminates.  So, this doesn't increase the total asymptotic running time.

You can think of this algorithm as a simple variant of delta debugging.


Question about an old result of Erdős and Simonovits My question concerns the  following result of Erdős and Simonovits.

A graph $G$ is $d$-almost-regular if $d\delta(G)\geq \Delta(G)$. Theorem 1 of the above paper states that a large $n$-vertex graph $G$ with $n^{1+\alpha}$ edges contains a large $d$-almost-regular subgraph $H$ for a constant $d$ depending only on $\alpha$. I cannot follow the proof of the theorem:

In case a) of the proof, if $C_1$ represents less than $\frac{1}{2}n^{1+\alpha}$ many edges, then we consider $G-C_1$. The resulting graph has only then at least $\frac{1}{2}n^{1+\alpha}$ edges, if $n$ refers to the order of the graph we are considering right now in the inductive step and not the order of the original graph (unless we are in the first step of the induction).

When we later show that the induction terminates after a bounded number os steps, however, we estimate the number of edges by $\frac{1}{(4A)^k}n^{1+\alpha}$. This holds only true if $n$ refers to the order of the original graph throughout the induction.

I tried to modify the proof such that case a) works, that is, $n$ refers to the order of the current graph in the inductive step. It is not hard to show that also then the induction terminates. However, with those modifications I cannot obtain that the subgraph $H$ is still large.

Am I misunderstanding something? Is there a newer presentation of this theorem?

Yep. The writing is not great (but this is a nice result [but there should be an easier proof by now]). Anyway, you should read the $n^{1+\alpha}$ in the proof as a fixed quantity $\tau$, which is the number of edges in the original graph. The rest then follows.


Online transitive closure better than O(N^2) per edge addition I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this:

For every new edge u->v connect all nodes in Pred(u) \cup { u } with all nodes in Succ(v) \ \cup { v }.

For O(N^2) edges this translates in a total time complexity of O(N^4) which much worse than, for example, Floyd-Warshall.

O(n) time per edge addition:

G. F. Italiano (1986): Amortized efficiency of a path retrieval data structure, Theoretical Computer Science 48, 273–281.
J. A. La Poutré and J. van Leeuwen (1988): Maintenance of transitive closures and transitive reductions of graphs, Proc. WG 1987.


Chordal Graphs and maximum independent sets For a chordal graph $G$ there is a clique tree such that its vertices corresponds to maximal cliques of $G$ and there is a edge between two vertices iff the intersection of the corresponding cliques are also their minimal vertex separator and for each vertex in the graph the cliques containing it, induces a subtree.

Now my questions are:-

  1.Take a subpath of the tree of length 5 with the property that no
  vertex has degree more that 2 and intersection of all the maximal
  cliques is non empty. Does there exist a independent set of
  atleast size 3 in the subgraph induced by that vertices present in the
  maximal cliques taken in the path?

  2.If yes, then is the bound of path length and independent set size tight?

There are arbitrarily long sub-path whose induced subgraph contains no three independent vertices.  See the graph below for length 4:

Indeed, vertices in a sub-path induces an interval subgraph.  So you can use standard interval models (the endpoints of the interval for a vertex $v$ are the indices of leftmost and rightmost bags that contain $v$) to construct the tight example easily.  The graph given above have intervals:
[1,1], [1,2], [1,3], [2,4], [3,4],[4,4].  Likewise, you can construct for a subpath of length n: the basic idea is that each interval either starts from 1 or ends at n.


Are there interesting graph classes where the treewidth is hard (easy) to compute? Treewith is an important graph parameter that indicates how close a graph is from being a tree (although not in a strict topological sense).

It is well known that computing the treewidth is NP-hard.

  Are there any natural classes of graphs where the treewidth is hard to compute?

Similarly:

  Are there interesting graph classes where the computation of the treewidth is easy? If yes, is there any structural property/test that can be exploited? I.e., Graph $G$ has property $X$ $\Rightarrow$ computing the treewidth of $G \in \mathbf{P}$.

Treewidth is NP-hard to compute on co-bipartite graphs, indeed the original NP-hardness proof of treewidth of Arnborg et al. shows this. Additionally, Bodlaender and Thilikos showed that it is NP-hard to compute the treewidth of graphs of maximum degree $9$. Finally, for any graph of treewidth at least $2$, subdividing an edge (i.e, replacing the edge by a degree $2$ vertex adjacent to the two edge endpoints) does not change the treeewidth of the graph. Hence it is NP-hard to compute treewidth of bipartite 2-degenerate graphs of arbitrarily large girth.

The problem is polynomial time solvable on chordal graphs, permutation graphs, and more generally on all classes of graphs with a polynomial number of potential maximal cliques, see this paper by Bouchitte and Todinca. Note that in the same paper it is shown that the set $\Pi(G)$ of potential maximal cliques of a graph $G$ can be computed from $G$ in time $O(|\Pi(G)|^2 \cdot n^{O(1)})$. Also, Bodlaender's algorithm determines whether $G$ has treewidth at most $k$ in time $2^{O(k^3)}n$. Hence, treewidth is polynomial time solvable for graphs of treewidth $O((\log n)^{1/3})$.

It is an outstanding open problem whether computing the treewidth of planar graphs is polynomial time solvable or NP complete. It is worth noting that the related graph parameter branchwidth (which is always within a factor 1.5 away from treewidth) is polynomial time computable on planar graphs.


Graph class with easy chromatic number, but NP-hard coloring Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard?

Without any further restriction the answer would be yes. For example, it is known that in the class of 3-chromatic graphs it is still NP-hard to find a 3-coloring, while the chromatic number is trivial: it is 3, by definition.

The above example, however, could be called "cheating" in a sense, because it makes the chromatic number easy by shifting the hardness to the definition of the graph class. Therefore, I think, the right question is this:

Is there a graph class that can be recognized in polynomial time, and the chromatic number of any graph $G$  in this class can also be computed in polynomial time, yet finding an actual $k=\chi(G)$-coloring for $G$ is NP-hard?

I think you need to specify more carefully what you mean by "NP-hard" for a problem like this with a known solution but an unknown witness.

The most natural definition, to me, would be something like a many-one reduction, where there exist two polynomial time functions $p$ and $q$, where $p$ maps SAT instances to graphs with a known chromatic number and $q$ maps colorings of these graphs to truth values, such that $q(\chi)$ equals the correct truth value for SAT instance $X$ whenever $\chi$ is a valid optimal coloring of $p(X)$. However, this is not possible unless $\mathsf{NP}=\mathsf{coNP}$. For, if such $p$ and $q$ existed, then every unsatisfiable SAT instance $X$ would have a witness to its unsatisfiability, namely a coloring of $p(X)$.


Circle graph visualisation I have a graph. I need visualise it with nodes arranged in a circle. How can I know whether it is possible arrange the nodes on a circle so that there no edges intersect in the visualised graph?

If the edges are permitted to be laid both inside and outside the circle, then it is called the 2-page graphs; if edges can only be laid inside the circle, it is the 1-page graphs, which is also know as the outerplanar graphs. See the book embedding entry in Wikipedia for more information.

By your comment, I guess the term you're searching for is outerplanar, since the complete graph on 4 vertices is 2-page. Outerplanar graphs can be recognized in linear time; see

  Linear algorithms to recognize outerplanar and maximal outerplanar graphs, S.L. Mitchell, Information Processing Letters, 1979.


$\mathsf{EXP}$ vs $\oplus\mathsf{EXP}$ In our recent work, we resolve a computational problem which arose in combinatorial context, under assumption that $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$, where $\mathsf{\oplus{}EXP}$ is the $\mathsf{EXP}$-version of $\mathsf{\oplus{}P}$. The only paper on $\mathsf{\oplus{}EXP}$ that we found was the Beigel-Buhrman-Fortnow 1998 paper that is cited  on Complexity Zoo. We understand that we can take parity versions of $\mathsf{NEXP}$-complete problems (see this question), but perhaps many of them are in fact not complete in $\mathsf{\oplus{}EXP}$.

QUESTION: Are there complexity reasons to believe that $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$?  Are there natural combinatorial problems that are complete in $\mathsf{\oplus{}EXP}$?  Are there some references we might be missing?

In terms of complexity reasons (rather than complete problems): The Hartmanis-Immerman-Sewelson Theorem should also work in this context, namely: $\mathsf{EXP} \neq \oplus \mathsf{EXP}$ iff there is a polynomially sparse set in $\oplus \mathsf{P} \backslash \mathsf{P}$. Given how far apart we think $\mathsf{P}$ and $\oplus \mathsf{P}$ are - e.g. Toda showed that $\mathsf{PH} \subseteq \mathsf{BPP}^{\oplus \mathsf{P}}$ - it would be quite surprising if there were no sparse sets in their difference.

More directly, if there were no sparse sets in their difference, it would say that for every $\mathsf{NP}$ verifier, if the number of strings of length $n$ with an odd number of witnesses is bounded by $n^{O(1)}$, then the problem [of telling whether there is an odd number of witnesses] must be in $\mathsf{P}$. This seems like quite a striking and unlikely fact.


What can the Haskell package category-extras be used for? See here. Has anyone attempted to use this to verify category theoretic proofs? Given the relationship between categories and graphs, are there some applications with respect to graph algorithms? What other possible uses are there for this package and those associated with it?

I realize this is a broad, open-ended question, which may not be entirely appropriate for Stack Exchange. A better place to post this question could also be a helpful answer.

This library is not especially useful for category-theoretic proofs, since Haskell's typechecking is not sufficient to verify that the constructions satisfy the required properties. Surprisingly enough ;), it's actually intended to be used for writing Haskell programs. You are best off asking on the Haskell-cafe mailing list for examples.


Algorithms Design and Complexity - How to think in that 'way'? My question is a general one: How do I start thinking in terms of Algorithm Design and Complexity? I am going to take a Graduate Course in Algorithm Design. I had enrolled in it earlier but dropped it later because I could not keep up with it. I have to take this course as a requirement.

Is there a 'trick' to think in this way? I know this is putting it quite crudely but sometimes a fresh perspective helps to think about a subject differently.

The main problem I have with this course (and similar theoretical courses) is: How do I know that solutions that I come up with are correct? I find the theoretical part to be arbitrary especially when 'proving' a certain algorithm acts or behaves in a certain way?

Our course will be using the standard text: Introduction to Algorithms by CLRS.

Are there any textbooks/sites/books/etc. that might offer a way in becoming confident in this field?

Thanks to everyone,

Jason Dane

I think courses on algorithm design and computational complexity are always challenging for students who not familiar with these subjects because they do require some degree of mathematical maturity and problem solving skill. In my first graduate course on "computational complexity", a friend of mine who had his degree in pure mathematics told me how surprised he was by the fact that although that course didn't require much maths background (at least that's what was told in the course outline), it actually required nearly all the skills he got through all of his pure maths undergrad degree!

I found that I got to know about "the way" most (when I first start my graduate study) by reading and doing exercises from Sipser's book. Be sure that you do the exercises because problem solving skill and mathematical maturity is what you want to learn and not just a bunch of facts or definitions.

However, Sipser's book is only good for complexity and NP-completeness stuffs, it won't suffice to substitute the CLRS book. The only problem with CLRS book is that its advantage of comprehensive coverage might become its weakness since the book might look quite scary or overwhelming for students. So my advice is that you should really go to the library and search for books on algorithms, scan through one by one and choose the ones that fit your thinking pattern most. And again don't forget to do exercises!

For algorithms, I personally suggest the following books (besides the ones suggested by Sadeq and JeffE):

The very readable and beautiful book Algorithms by by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani.
The killer notes (or book draft) by Jeff Erickson. (Since JeffE is too modest to suggest his own notes, I have to do it myself.)

In general, whenever you study a certain algorithm or data structure, if somehow the exposition in your textbook is not clear enough for you, then the best way is to search on google for lecture notes of that particular topic. In may cases, different explanations of the same thing eventually give you the complete picture. At least, that's how it works for me.


Interesting algorithms in the formalization of the Feit-Thompson theorem? It looks like George Gonthier and his collaborators have finished formalizing the Odd Order Theorem.

In his earlier work on the Four Color Theorem, Gonthier invented a bunch of new algorithms (mostly variants of BDDs and graph algorithms) which were especially amenable to formal verification. Since he has said that he was  continuing to use this small-scale reflection style of verification in the work on finite group theory, I wonder what new algorithmic tricks were developed during this development?

(Turning a comment into an answer, and expanding on it)

From talking to someone who worked on this: no. He invented all sorts of clever refinements to many proofs, and restructured many theory developments, both of which are extremely valuable, but the algorithms involved are not interesting -- in fact, many of them are dumb brute force, the very opposite of interesting.

Basically what was sought was as direct a line to the proof of Feit Thompson, without worrying about 'computational content' along the way (and even not overly worrying about reusability of some of the modules).  This was already extremely ambitious given the timelines.  Luckily, several of the people involved in the project have gone on to refactor many parts of the proofs to be

more reusable for a wider set of applications
more computationally meaningful


Lengths and substitution in L-systems Am looking into writing up a Lindenmayer systems implementation. I've looked at a few example implementations and the one thing that's giving me trouble at this stage is how symbols and substitutions are meant to work (if this is even specified in the original treatise).

For example, the implementations I've seen tend in most cases to start with axioms based on A. Let's take the simplest example of this where the Axiom is (just) A.

When this is drawn (depth 0), what should I expect to see? If otherwise undefined, is A meant to render as anything at all? Or does it need to be defined as one full length (whichever symbol is used for this; I have seen pipe being used to this purpose) before it will render out?

Taking a second example, let us say that A renders out, irrespective of what the answer to the above is. If part of F's definition is B, and B is not defined, should B render as a full length?

The way I would expect this to work is that without F being defined at all, nothing should be drawn at depth 0 and subsequently at no other depth, either.

Yet in L-systems Explorer (LSE) and in this web-based implementation, even where a symbol is not defined, it will still be rendered as a full length. The question is, why?

L-systems, are more about general : Abstract rewriting systems rather then to concrete application.

Agree, a wide range of L-systems applications is in computer graphics (generating nature, textures etc), while from mathematical point of view, they are still, the same model.

As stated in referred by you L-systems definition :

  Using L-systems for generating graphical images requires that the symbols in the model refer to elements of a drawing on the computer screen.

Coming back to your question

  Yet in (...) implementation, even where a symbol is not defined, it will still be rendered as a full length. The question is, why?

Answer: Because that's the way, how those implementations' authors decided to map symbols into rendering commands.

You can do in your implementation any other mapping... and still both of them can be same type of system - L-system.

It's all about defining isomorphism between systems behind implementations, or homomorphism between those systems and graphics they generate. If you will make your own implementation, that will draw symbols differently - you will indirectly define your own homomorphism.


Time-bounded Kolmogorov complexity and non-random strings If $t$ is a time constructible function then we can define the time-bounded Kolmogorov complexity of a string $x$ as:

$C^t(x)$ = the size of the smallest program p that generates $x$ in $t(|x|)$ steps

We can also extend the incompressibility notion: a string $x$ is incompressible if $C^t(x) \ge |x|$ (otherwise $x$ is compressible).

Now we can define the function:

$f^t(n) = | \{ x \text{ : } |x|=n \text{ and } x \text{ is compressible with respect to } C^t \} |$

( $f^t(n)$ is the total number of compressible strings of length n ).

What is the relation (if any) between $t$ and the rate of growth of $f$? Can we say something about it?

EDIT:
For example, can we choose $t$ to make $f$ grow polynomially? ... NO

I suspect that there is something that can be said generally, but off the cuff, the best I can see is that as $t$ increases, the number of compressible strings increases as well.

On the other hand, we certainly cannot pick a $t$ such that $f$ is polynomial.  Notice that if $t(|x|)<|x|$, then there isn't enough time to write anything.  On the other hand, strings of the form $yyz$ can be generated by programs of length $|y|+|z|<|x|$ and there are at least $2^{|x|/2}$ of those.  So by monotonicity, $f$ will always be at least this large.


Decision problem related to coloring Given a $k$-colorable graph $G$ and vertices $u$ and $v$ of $G$, what is the complexity of deciding if every $k$-coloring of $G$ must assign the same color to both $u$ and $v$?

It does not seem obvious to me how to use the above problem as an oracle to construct a coloring, so it is conceivable that this problem is efficiently decidable.  On the other hand, minor variants of NP-hard problems, such as this one, typically remain NP-hard.  But most of all, I do not know what problem is a good choice to reduce from.

Any thoughts?

Add the edge $(u,v)$. Your property holds if and only if $G$ is no longer $k$-colorable.


Why is there a need for cyclic proofs? I was reading a paper A Generic Cyclic Theorem Prover. This paper explains about automated theorem prover based on various instantiations like the notion of first order logic equations with inductive definitions using cyclic proofs. I was unable to understand about why cyclic proofs are required. As far as I understand, sometime with the induction rules, we can go to an infinite loop, to avoid this condition of going into infinite loop, they introduced cyclic proofs. Can anyone please correct me if I am wrong?

In order to reason about inductively defined objects (numbers, lists, trees...), one needs to use induction, or some principle that is at least as powerful as induction.

But explicit induction rules cause huge difficulties for automatic proof search, because they typically force you to invent the necessary induction schema and induction hypotheses at the beginning of the proof.  For some discussion of these difficulties, see this paper by Bundy.

Cyclic proof is an alternative to explicit induction; that is, instead of using a standard proof system with explicit induction rules, one can use a cyclic proof system without explicit induction rules.  This allows a somewhat more exploratory approach to proof search, where the induction argument is essentially created implicitly through the discovery of a cyclic proof. See this paper for a comparison between cyclic and non-cyclic proofs (for first-order logic with inductive predicates).


Can a measurement commuting with the stabilizer of a state disturb the state? In Nielsen and Chuang's "Quantum Computation and Quantum Information", Section 10.5.3, the authors claim the following:

  With a system in state $|\psi\rangle$ with stabilizer $g_1,...,g_n$, if a measurement $g$ that is commute with all $g_i$ is applied to the state, then either $g$ or $-g$ is a stabilizer of the system and the measurement doesn't disturb the state.

However, it seems to me that there is a simple counterexample:

  Let $g$ be the $Z_1$ operator in the system, thus it commutes with all stabilizers as $g|\psi\rangle$ is still a valid state in the system. However neither $g$ nor $-g$ is a stabilizer of the code.

Am I missing anything or the quoted claim is indeed false?

The quoted claim from the book is true. It is not true that $Z_1$ must always commute with all stabilizers of $\lvert \psi \rangle$. For example, if $X_1X_2$ stabilizes $\lvert \psi \rangle$ (e.g., if $\lvert \psi \rangle$ was an EPR pair) then $Z_1$ does not commute with $X_1X_2$ and $Z_1$ is not a stabilizer of $\lvert \psi \rangle$.


Enumerating set combinations in an order that maximises the number of previously unseen subsets Consider a set $S=\{a,b,c,d,e,f,g,h,i,j,k\}$, $\left|S\right|=11$.

There are ${11 \choose 5} = 462$ combinations of $S$'s members of size $5$.

There are $462! \approx 1.419 × 10^{1032}$ possible ordering of those sets. All ordering are in $\Phi_0$.

For a given ordering, $\phi \in \Phi_0$, $x_i^\phi$ is the set placed at position $i$.

Initial $\Phi_0$ was defined, following ones are defined as

$$\Phi_i = \left\{\,\phi \in \Phi_{i-1} \mid \not\exists \phi^\prime \in \Phi_{i-1} , C\left(i,\phi^\prime\right) \gt C\left(i,\phi\right)\, \right\}$$

where $C\left(i,\phi\right)$ is number of subsets given by $x^\phi_i$ which have not already exist as a subset of previous $x^\phi$'s

$$C\left(i,\phi\right)=\left|2^{x^\phi_i} \setminus \bigcup_{\forall h<i}{2^{x^\phi_h}} \right|$$

I'm looking for ways to efficiently enumerate any one of the orderings that exists in $\Phi_{462}$.

Any suggestions, pointing towards relevant/potential useful algorithms or papers would be appreciated.

There are $\sum_{j=1}^4 \binom{11}{j} = 561$ smaller subsets, and each $x^\phi$ contains $\sum_{j=1}^4 \binom{5}{j} = 30$ of them.

If you put all $462$ $5$-element sets in a priority queue with priority corresponding to the number of subsets which haven't yet appeared, after each pop you have to check $30$ subsets to see whether they're appearing for the first time, and for each $k$-element subset that is appearing for the first time you have to update the priorities of $\binom{11}{5-k}$ sets. There's an easy upper bound on the number of updates of $25410$.

As a follow-up optimisation, once every smaller subset has been seen (which happens after you've removed the first 90 elements from the priority queue), you can just iterate through the rest. If your priority queue is e.g. a binary heap, this will save you a lot of $O(\lg n)$ pops.


Recommendations for References on undecidability of First Order Logic I am currently reading Computability and Logic by Boolos Burgess Geoffrey for the proof on "undecidability of first order logic". however, I find the notations a bit confusing. Can anyone recommend any resource website link/ video lecture or a book perhaps which will help me understand the proof of undecidability of first order logic? I am a CS student so, I do not want a completely mathematical /philosophical proof. I came across plenty of those on the web.

Let me clarify one subtle point: first order logic is only undecidable for certain given languages. In particular the language $\cal{L}$ that contains only monadic predicates, that is, predicates of the form $P(x)$ and no function symbols, is decidable.

If you allow function symbols or predicates with more than 1 argument, then $\cal{L}$ usually becomes undecidable. The proof involves encoding Turing machines and their computation sequences using the symbols of the logic. Then one adds a finite series of axioms $\phi_1,\ldots, \phi_n$, and build a formula $\psi(x,y)$ such that
$$ \phi_1,\ldots,\phi_n\vdash \psi(\overline{n},\overline{m})$$
is provable if and only if

  The Turing machine with index $n$ halts in at most $m$ steps on the empty input.

Undecidability of FOL follows, as proving

$$ \vdash \phi_1\wedge\ldots\wedge\phi_n\rightarrow \exists y,\psi(\overline{n},y)$$

is equivalent to determining wether the machine with index $n$ halts.

A detailed description of this proof is given in chapter 4 of Avigad's lecture notes on computability.


Speed-up of universal computation by caching A universal computer is a program that can execute any other program. It is interesting to ask whether there are "booster" computers that execute programs faster than they execute "on their own". In the simplest sense of the question, the answer is negative, as can be seen by the following argument.

Suppose $V$ is a universal computer. Consider the following program $P$: "Run $V$ on my own source code. If it halts in less than $n$ steps, produce output which is different than the output of $V(P)$. Otherwise produce the output '0' (say)". It is clear that $V$ will take at least $n$ steps to execute $P$ and $P$ will execute in approximately $n$ steps on its own. So $P$ and $V(P)$ take approximately the same time.

However, what happens if we allow a pre-computed cache of arbitrary size? Formally, we consider a universal Turing machine with the addition of a special read-only tape on which an infinite computable bit-string $s$ is written in the initial state. Fix $U$ an "ordinary" universal computer program, i.e. $U$ doesn't use the special tape. The question is then

  Can we construct $V$ a program (using the special tape) and $s$ as above s.t. for any $U$-program $P$ if $U(P)$ halts in $t$ steps then $V(P)$ halts in at most $max(f(t), g(|P|))$ steps where $f \in o(t)$ and $g$ is computable?

Repeating the self-referential construction above only yields that the time complexity of $s$ has to be at least $f^{-1}$

Using a pairing function we can allow $s$ to be defined on $\mathbb{N}^2$. Let $s(i,j)=1$ if and only if the $i$'th program $P_i$ halts in at most $2^j$ steps. Then $V$ can test whether $P_i$ halts by testing $s(i,1),s(i,2),\dots$. If $U(P_i)$ halts in at most $2^j$ steps then $V(P_i)$ halts in about $(i+j)^2$ time, assuming the pairing function is sensible. This means that if $U(P)$ halts in $t$ steps then $V(P)$ halts in about
$$(2^{|P|}+\log t)^2\leq \max(4\cdot 2^{2|P|},4(\log t)^2)$$
steps. But $(\log t)^2=o(t)$.


The state of art for sunflower system I am interesting in the sunflower system and its applications in computer science.

Given a Universe $U$ and a collection of $k$ sets $A_i$ is called a k-sunflower system if $A_i \cap A_j = Y $ for all $i \neq j$. And $Y$ is called as the core and $A_i - Y$ is called petals.

A family of sets $F$ is called $s$-uniform is all the sets it contained possess $s$ elements.

Erdos and Rado proved that for a $s$ uniform family of sets $F$ , $F$ must contain a $k$-sunflower system  petals if $|F| > s!(k-1)^s $.

This result is called the sunflower lemma and has many important applications.

Erdos conjectured that for every $k$ there exist a constant $c_k$ such that the upper bound should be $c_k^s$ every $s$-uniform family $F$.
(The  sunflower conjecture)

Unfortunately, this conjecture is still open for $k=3$.

Here is what I want to know.

If we limit the number of elements in the universe $U$.Suppose $|U|$= $u$. Then the problem turns out be:

Given a universe with $u$ elements, and $s$-uniform family $F$ of sets containing the elements in $U$, we supposed can find sequence of constants $c_1$, $c_2$, $c_3$ ,... such that every $s$-uniform family $F$ contains a $3$-sunflower system if $|F|>$ $c_i^s$ and $|U|=i$.

Moreover, if we could prove that the sequence $c_i$ converges to a constant $c$, then it seems we can prove the sunflower conjecture.

But I cannot find such result.It might be that this approach is too stupid or too hard.

Could any one provide the state of art of sunflower lemma and the conjecture(finite version is also OK).

Here is some I can provide.
There is a chapter in Junka's book The Extremal Combinatorics.

The paper above is one of its application(finite version)

On Sunflowers and Matrix Multiplication N Alon et.al

the Erdos sunflower conjecture seems to be very difficult after now over a half century(!) of being open. youve already listed some of the very best and most recent refs on the subj that would be very hard to beat (Alons recent paper, Juknas book on combinatorics). the Alon paper is highly notable for newly linking the conjecture to lower bounds on matrix multiplication, an area that has seen recent groundbreaking advance in the Williams results.[4]

you can find some further treatment, mainly applications to extremal circuit theory (circuit lower bounds 1st discovered by Razborov & extended by others), in Jukna's outstanding book [1].

one notable/related recent ref along these lines apparently not-so-widely-known-or-cited-so-far is [2] by Rossman with a new direction of application (Erdos-Renyi random graphs over monotone circuits) and who proves extended and/or stronger results on "quasi-" sunflowers. the paper is a result from his Phd thesis [3]. from the paper abstract

  We introduce a new variant of sunflowers and prove an analogue of the sunflower lemma that may be of independent interest.

[1] Boolean function complexity, advances and frontiers

[2] The Monotone Complexity of k-Clique on Random Graphs (2009) Rossman

[3] Average-case complexity of detecting cliques by Rossman

[4] Commentary on Williams breakthrough on matrix product lower bound RJ Liptons Godels Lost Letter blog

[5] Detailed Materials on Sunflowers


Is "Is a permutation p an automorphism of a graph in my set?" NP-complete? Suppose we have a set S of graphs (finite graphs, but an infinite number of them) and a group P of permutations that acts on S.

Instance: A permutation p in P.
Question: Does there exist a graph g in S that admits the automorphism p?

Is this problem NP-complete for some sets S?
It would be easy to check that a graph admits the permutation p (i.e. certificate).  Moreover, it's easy to find examples of S where the problem is not NP-complete, such as S being the set of complete graphs, whence the answer is always yes.
Note: I'm not really interested in what type of graphs they are; if you like they can be non-simple, directed, coloured, etc.
ADDENDUM:  The problem I'm currently looking at is classifying which isotopisms are autotopisms of Latin squares (which can also be interpreted as a special type of graph automorphism).
Given a Latin square L(i,j) we can construct a graph in the following way:

The vertex set is the set of cells (i,j) in the matrix and
There is an edge between distinct (i,j) and (i',j') whenever i=i' or j=j' or L(i,j)=L(i',j').

Such a graph is called a Latin square graph (see e.g. this article by Bailey and Cameron http://designtheory.org/library/encyc/topics/lsee.pdf).  We can interpret an autotopism of a Latin square as an automorphism of the Latin square graph.  So let S be the set of Latin square graphs formed from the Latin squares of order n.  So the question I'm interested in is:

Given a permutation p, is p an automorphism of one (or more) of the graphs in S?

My feeling is that it is a difficult question to answer in general -- I'm currently writing a 30+ page paper on the matter (with 2 co-authors).  Actually most of the time it is easy (most of the time it's "no"), but there are some difficult cases.
So I'm interested in finding decision problems that would be related to "symmetry classification".  They don't really need to be related to Latin squares, I'm just hoping to use these techniques to answer the question for Latin squares.

Take any language $L$ (that consists of binary strings). Construct the set $S$ of graphs as follows:

For each string $x \in L$ with $|x| = n$, we have the graph $G_x = (V_x,E_x)$ in $S$, with the set of nodes $V_x = \{1,2,...,3n\}$ and the following edges: if bit $i$ of $x$ is $0$, then the nodes $3i-2$ and $3i-1$ are adjacent, otherwise $3i-2$ and $3i$ are adjacent. There are no other edges.

Now let $p$ be a permutation of $\{1,2,...,3n\}$. Assume that $p$ is an automorphism of some graph in $S$. That is, $p$ is an automorphism of $G_y$ for some $y \in L$. Let $i \in \{1,2,...,n\}$. Let us consider the following two cases:

$p(3i-2) = 3i-1$, $p(3i-1) = 3i-2$, $p(3i) = 3i$. Then we must have bit $i$ of $y$ equal to $0$.
$p(3i-2) = 3i$, $p(3i-1) = 3i-1$, $p(3i) = 3i-2$. Then we must have bit $i$ of $y$ equal to $1$.

Hence if we can solve the question "is a given $p$ automorphism of some $G \in S$", we can also solve the question "is a given string $y$ in $L$". Moreover, if we can do the former in, say, polynomial time in $|p|$, we can do the latter in polynomial time in $|y|$ as well.

Now you can just let $L$ be your favourite NP-hard problem. Or the halting problem...


Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here.

I have asked some people who are more familiar with the research whether they think that there is a $k>0$ independent of $n$ such that there exists an $O(n^2 \log^k n)$ algorithm for matrix multiplication and they overwhelmingly seemed to have intuition that the answer is "no" but could not explain why. That is, they believe that we can do it in $O(n^{2.001})$ time, but not $O(n^2 \log^{100} n)$ time.

What reasons are there to believe that there is no $O(n^2 \log^k n)$ algorithm at a fixed $k>0$?

There's an algorithm for multiplying an $N \times N^{0.172}$ matrix with an $N^{0.172} \times N$ matrix in $N^2 \operatorname{polylog}\left(N\right)$ arithmetic operations. The main identity used for it comes from Coppersmith's paper "Rapid multiplication of rectangular matrices", but the explanation for why it leads to $N^2 \operatorname{polylog}\left(N\right)$ instead of $N^{2 + \epsilon}$ is in the appendix of Williams' paper, "New algorithms and lower bounds for circuits with linear threshold gates".

This only works because Coppersmith's identity has some additional structure you can take advantage of, and the more recent MM algorithms don't seem to have this structure. That said, I'm not sure why one can't hope to extend this approach to $N \times N \times N$ matrix multiplication.


Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$? Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

This is open, as far as I know. It could be provable (because its hypothesis may be false) or it just be difficult to show that any $2^{n^k}$-time algorithm for Succinct3SAT can be converted into a $2^{O(n)}$-time algorithm for Succinct3SAT.

In general, theorems of this kind are called "downward collapses" which say if two "large" classes are equal then two "smaller" classes are equal. These theorems are rare. Usually you can either prove an "upward collapse" (small classes equal implies larger classes equal, like $P = NP$ implies $NEXP = EXP$) or its contrapositive, a "downward separation".

Something along the lines of what you want is the theorem by Hartmanis, Immerman and Sewelson (http://dl.acm.org/citation.cfm?id=808769) that $NE = E$ $\iff$ every sparse set in $NP$ is contained in $P$. This gives a "downward collapse" but only for the sparse sets (those sets that contain only $poly(n)$ strings of length $n$).


Complexity of iterative least squares regression Given a set of points $P = \{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n) \}$ one can use least squares method to fit a polynomial to $P$.
In particular I am interested in linear and quadratic regression.

I am not familiar with the literature, but it seems a fit to $P$ can be computed in $O(n)$ time,
(the degree of the polynomial is considered a constant).

Is there any algorithms for updating these polynomials as one point is added to or removed from P without recomputing the whole polynomial?

Edit:
I found this implementation:
http://algs4.cs.princeton.edu/14analysis/LinearRegression.java.html
Which easily can be modified to dynamically update a linear regression in constant time.

I still wonder how to do quadratic regression but I will try to mimic the technique I found for linear regression.

Linear regression

Yes.  For linear regression, you can do both updates in $O(1)$ time.

Recall that for ordinary least squares estimation, we estimate the parameter vector $\hat\beta$ using the equation

$$\hat{\beta} = (X^T X)^{-1} X^T y.$$

Here $X$ is a $n \times 2$ matrix and $y$ is a $n$-vector.  Adding a point amounts to adding a row to $X$ and $y$; deleting a point corresponds to deleting a row.

So, here is the technique.  When you do the initial estimate, remember the value of $X^T X$ (which is a $2 \times 2$ matrix) and of $X^T y$ (which is a $2$-vector).  This only requires $O(1)$ storage.

Now let's say you add a point.  This involves adding a row to $X,y$, to obtain new values, call them $X',y'$.  We now need to compute $(X'^T X')^{-1} X'^T y'$.  Fortunately, this can computed efficiently.  It is easy to compute $X'^T X'$ in $O(1)$ time, given the value of $X^T X$ and the row that was added to $X$.  It is also easy to compute $X'^T y'$ in $O(1)$, given the value of $X^T y$ and the row that was added to $X,y$.  Once you know the values of $X'^T X'$ and $X'^T y'$, you can simply multiply them (takes $O(1)$ time) and update the stored values.

A similar procedure can be used to remove a point, if you've stored all of the points and all of $X,y$.

Quadratic regression

The same techniques work for quadratic regression.  Now instead of a $n\times 2$ matrix, we have a $n \times 3$ matrix.  Basically, instead of the simple linear model $y \sim \beta_1 x + \beta_2$, we obtain the model $y \sim \beta_1 x^2 + \beta_2 x + \beta_3$, which has three parameters instead of two.  Everything else transfers over, and all updates can be done in $O(1)$ time.

Gradient descent

Finally, one last method.  Some variations on linear regression work by using gradient descent (or some other iterative mathematical optimization algorithm) to find the best model that maximizes some objective function (likelihood, or loss, or whatever).

Heuristically, if you update the set of points, you can often update the existing model much more efficiently than computing a new one from scratch.  In particular, you simply use grade descent with the new objective function -- but you use the old model as the starting point / initial point for the gradient descent.  Gradient descent is usually much faster when the starting point is close to the final optimum value, and when you make a small change (like adding or removing one point) we can expect this to be the case.

I don't think there are any complexity-theoretic guarantees with this approach, so it's entirely heuristic -- but it might work in practice if you are using gradient descent based methods for estimation instead of ordinary least squares.


Max flow with restriction of individual flows What is known about the complexity of solving max flow with restrictions on individual flows for some nodes?

More precisely, in addition to wanting the max flow, you have a constraint for some vertices $S\subset V$ where $\forall s \in S, \forall u\in \{u | (u,s) \in E \} , f(u,s) \leq \frac{1}{2} \sum_{u} f(u,s) $

Meaning no one edge contributes more than half the total flow into a node.

Also, the flows must be integral [and the capacities are integral]

That constraint is linear, so the entire problem is an instance of linear programming, thus can be solved in polynomial time.  (I am assuming there is no restriction or requirement for integer flows.)

In general if you allow arbitrary constraints, the problem can become NP-hard.


Using Pearson Correlation Coefficient in computing user/item similarity I'm researching for an algorithm for item-based/user-based collaborative filtering and I've come to this site.

It uses Pearson correlation coefficient to compute similarity between users and when I read this line:

  A strength of this formula is that it takes into account average
  ratings for each user. So if user a rates everything a 5 and user u
  rates everything a 1, then they still have a similarity rating of 1.

I wonder why it would give a similarity of 1 because using the said equation which is the Pearson and using the given (user a, 5 and user u, 1), it would give a zero for the numerator and denominator.

So what is the reason he said that the similarity of user a and user u with a rating of 5 and 1, respectively is equal to one? Is zero over zero equals to one?

Pearson's correlation is undefined when the variance of one of the random variables is 0, I would look for a more credible source to read from.


Is being fooled by limited independence preserved by products? Question. Let $f,g : \{\pm 1\}^n \to \{\pm 1\}$ be $\varepsilon$-fooled by $k$-wise independence -- i.e. for any $k$-wise independent random variable $X$, $\left|\mathbb{E}[f(X)] - \mathbb{E}[f(U)]\right| \le \varepsilon$ (where $U$ is uniform) and likewise for $g$. Define $h(x,y) = f(x) \cdot g(y)$. Is $h$ necessarily $O(\varepsilon)$-fooled by $O(k)$-wise independence?

If $\varepsilon=0$, the answer is yes: The hypotheses imply that $f$ and $g$ are polynomials of degree at most $k$, which implies $h$ has degree at most $2k$ and is therefore fooled by $2k$-wise independence.

This feels like it shouldn't be too hard to answer. Any ideas?

There is an equivalent formulation in terms of sandwiching polynomials (see e.g. [Bazzi07] $\S 1.1$): Essentially, it asks is the product of two "almost" degree-$k$ functions "almost" degree $O(k)$?

 Equivalent Question.
Let $f,g : \{\pm 1\}^n \to \{\pm 1\}$. Suppose there exist polynomials $f_+,f_-,g_+,g_- : \{\pm 1\}^n \to \mathbb{R}$ of degree at most $k$ such that $$f_-(x) \le f(x) \le f_+(x) ~~~ \text{and} ~~~ g_-(x) \le g(x) \le g_+(x)$$ for all $x \in \{\pm 1\}^n$ and $$\mathbb{E}[f_+(U)-f_-(U)] \le \varepsilon ~~~\text{and}~~~ \mathbb{E}[g_+(U)-g_-(U)] \le \varepsilon.$$ Do there exist polynomials $h_+, h_- : \{\pm 1\}^{n} \times \{\pm 1\}^{n} \to \mathbb{R}$ of degree $O(k)$ such that $h_-(x,y) \le f(x) \cdot g(y) \le h_+(x,y)$ for all $x,y \in \{\pm 1\}^n$ and $\mathbb{E}[h_+(U,U')-h_-(U,U')] \le O(\varepsilon)$?

The obvious thing to try is setting $h_\pm(x,y)=f_\pm(x) \cdot g_\pm(y)$. Unfortunately, it doesn't seem to work out (essentially the signs and inequalities don't go the right way).

I'm also interested in generalisations of this question, where $X$ is, say, small-biased, rather than $k$-wise independent.

I have figured out that the answer to this question is yes.

The proof goes via sandwiching polynomials. It's a simple modification of a proof in [GMRTV12] $\S 4$. (Instead of keeping track of $\mathrm{L}_1$, we keep track of degree.)


Graph partitioning by node deletion Given an undirected graph and an integer $B$,
we ask to find the minimum set of nodes
whose removal partitions the generated graph into connected components,
each having at most $B$ nodes.

We can consider this to be a generalization of the minimum vertex cover,
where $B=1$, since deleting the vertex cover set of a graph $G$ gives an independent set,
i.e. partition G on connected component of no more than 1 node.

Are there similar problems in literature?
This problem is NP-complete on general graphs.
Which known problem on graph theory help to study its (in)approximation?
I want to study it on chordal graphs.
For which cases it may be polynomial and for which it is NP-complete?

The problem that you are describing seems to be a variation of a critical node detection problem. In general, most critical node detection problems aim to identify a set of at most $B$ nodes (or if you are considering the weighted case, a set of nodes with a weighted sum of at most $B$ ) whose deletion results in the maximum disruption of a given property of the graph. In many of the papers that you can find in the literature, the property that is being disrupted often represents a measure of how well connected the residual graph is. For instance, such property may account for the total number of node pairs that remain connected, the number of maximally connected components, or the size of the largest connected component after the critical nodes are removed (you can also search for node interdiction or node blocker problems for other versions). Some references are: Arulslevan et al [1], Shen et al [2], Di Summa et al [3], Addis et al [4], Oosten et al [5] among others. There is also a very short survey [7] on some of these problems. Although, several other papers have been published after that chapter was in press.

These problems are indeed NP-Hard for general graphs. However, there are some polynomially solvable cases (trees and series-parallel graphs, see [3], [4], and [6]).

For the version that you mention, which is somehow a complement of the above problems (instead of maximizing the disruption, you minimize the number of critical nodes to achieve the desired disruption) there is an article that proves inapproximability for the version of the problem in which the disrupted property is the total number of pairwise connections [8]. Your intuition is correct, vertex cover is commonly used to as a steeping stone.

If have some other questions or ideas, you can send me an email. This is one of my research interests. I will be happy to provide you with more ideas and to collaborate.

There is also something to keep in mind. These problems lay in the intersection of several fields, so there may be some similar versions with different names (I have found problems that belong to the same family, like graph separators, pivotal vertices, and articulation points).

[1]: Detecting critical nodes in sparse graphs

[2]: Exact interdiction models and algorithms for disconnecting networks via node deletions

[3]: Complexity of the critical node problem over trees

[4]: Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth

[5]: Disconnecting graphs by removing vertices: A polyhedral approach

[6]: Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs

[7]: Selected Topics in Critical Element Detection

[8]: On New Approaches of Assessing Network Vulnerability: Hardness and Approximation


Grover's search algorithm for 3 coloring According to Arora & Barak (pdf), pg. 186, for a polynomial-time computable function $f: \{0,1\}^n \to \{0,1\}$ (represented as a circuit computing $f$), Grover's algorithm finds in $O(\text{poly}(n)2^{n/2})$ time a string $a$ such that $f(a) = 1$ (if such a string exists).

My question is an application of Grover's algorithm to 3 coloring. How can you show, using Grover's algorithm, that 3-coloring can be solved on a quantum computer in time $O(\text{poly}(n)2^{n/2})$, where $n$ is the number of vertices?

This is not a direct application of the algorithm, since although you can easily encode each of the $3^n$ (valid and invalid) colorings of the $n$ vertices using $\log_2(3^n) = n\log_2(3) = O(n)$ bits, this means that Grover's algorithm gives a run time of $O(\text{poly}(n)2^{n\log_2(3)/2}) = O(\text{poly}(n)3^{n/2})$.

So maybe, you would need to show that a coloring (possibly valid) can be encoded using only $n + O(1)$ bits? How would you show that?

You don't need to keep track of all $3$ colours for your colouring, because we know how to two colour quickly.

Let the colours be $\{0,1,2\}$. Have an oracle $f: \{0,1\}^{|V|} \rightarrow \{0,1\}$ that you interpret as selection a subset $C_0 \subseteq V$ that you will pretend is $0$-coloured. Your circuit then (1) in polynomial time checks if $V - C_0$ is two-colourable with $\{1,2\}$, and (2) in polynomial time checks if $C_0$ is an independent set. If both are true then it returns $1$, else $0$. Now you are searching over only $2^n$ database entries for a marked element and so have the runtime you wanted.


The concept of binary description by Ray Solomonoff In this article, http://world.std.com/~rjs/rayfeb60.pdf in page 7 of the PDF, Solomonoff gives an a-priori probability for a string which is $pr(S)=2^{-|S|}$.

My question - why are shorter strings considered more probable? Is there some kind of hidden assumption that justifies this?

e.g. that the machine which produces these strings have a constant probability to stop at a any given point (an inherent preference to shorter strings).

Later in page 10 of the pdf he explains that in fact the probabilities are almost 1/2, as there is a very small probability to stop the at each step.

This stems from the following assumption: There is some mechanism that produces these strings, and it does so sequentially, therefore going through shorter strings on its way to longer ones and having a certain probability to stop at each step.

Another explanation that was more satisfying:

These binary strings are in fact prefixes of infinite random sequences. The probability of a prefix to be 1 or 0 is of course 1/2 etc'. The machine that reads these infinite binary strings is a prefix turing machine, which means that if it produces a certain sequence, it does so by reading a prefix of the random string.


Handbook of Logic in Computer Science - is it worth it? I just found the first volume of Handbook of Logic in Computer Science in a library, but unfortunately I won't be able to use it here. It seems like a great resource, but it's insanely expensive to buy - is it worth it? Do you know any good alternatives?

The series is a wonderful resource, but I wouldn't recommend buying it when it is available in the library, unless you knew you were going to use it for many years to come. (I have too many expensive books on my shelf that are lovely to look at, but not used much.) Many articles and tutorials with comparable contents are available on the web. These are probably a better alternative for the moment, in my opinion.


Are social networks typically good expanders? I am interested in the combinatorial properties of social networks as graphs. People have looked at things such as the distribution of the degrees, the clustering coefficient and the compressibility of these graphs. One basic question is: Are these graphs typically good expander graphs?

Has anyone checked, say, the facebook graph's spectral gap? Or the spectral gap of other large real-world networks? I am hoping that someone can point me in the right direction to learn about this topic.

Social networks typically have many vertices with just one or two connections to the rest of the graph. Such vertices will typically lead to a bad spectral gap.

What you could hope for is good vertex/edge expansion for sufficiently large sets. However, if you have tightly-knit communities within the network, then again you would expect low expansion.

I'm not sure if it quite answers your question, but the following empirical paper looks at exactly expansion-like properties in social networks. The answer seems to vary from network to network.
http://fragkiskos.me/papers/expansion_SNSMW11.pdf

I'm sure there is other work out there along these lines, possibly disguised using alternate terminology ("community structure", cut sizes, etc).


Special case of Bin-packing problem We know that the decision version of Bin-packing problem is NP-complete:
Given an integer B, an integer k, and a list of integers X = (x1, x2, . . . , xn) where xi ∈ [0, B], is there any partition of X into k sublists, such that each sublist sums to at most B?

But what about the special case where the given numbers x_i's are as follows:
x_1 = 1, x_2 = 2, ... , x_n = n.

Then is this case also NP-complete?

In general is there any reference that I can find all or many versions of Bin-packing problem, and the facts known about them?

We wrote a paper related to that. Perfect packing theorems and the average-case behavior of optimal and on-line packing, by Coffman, Courcoubetis, Garey, Johson, Shor, Weber, and Yannakakis.  See Theorem 1:

  Perfect Packing Theorem: For positive integers k, j, and r, with k ≥ j, one can perfectly pack a list L consisting of rj items, r each of sizes 1 through j, into bins of size k if and only if the sum of the rj item sizes is a multiple of k.

You should note that this only solves the question when (for the OPs definition of $k$ and $n$) $k$ divides $\frac{1}{2}n(n+1)$. If anybody knows how to solve it for all $k$, they should definitely submit another answer.


Chernoff Bounds for settings with limited dependence Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. By partially I mean the variables could be divided into subsets of size atmost k such that any variable from two different sets are independent.

Of course one possible technique is that we sum the variables in a set and treat the sums as my new random variables but now the bound of the value we would have on these variables would be k and that's unreasonable in the setting that we have. So could something better be said ?

If needed the corelation between variables belonging to a set could be better characterized.

Thanks

If $X_1, \cdots, X_n$ are $k$-wise independent random variables on $[0,1]$, then $$\text{Pr} \left[ \left| \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right| \geq n \cdot \varepsilon \right] \leq \left( \frac{k^2}{4 n \varepsilon^2} \right)^{\lfloor k/2 \rfloor}.$$
Note that this bound does not necessarily improve with greater $k$. So you may want to choose a smaller $k$ to get the best results.

Proof Sketch. W.L.O.G. $k$ is even. Consider the $k^\text{th}$ moment: $$\text{Ex} \left[ \left( \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right)^k \right] = \sum_{S \in [n]^k} \text{Ex} \left[ \prod_{i \in S} X_i - \text{Ex}[X_i] \right].$$
Each summand on the RHS is nonzero only if every $i$ appears at least twice in $S$. (Otherwise, since $\text{Ex}[X_i-\text{Ex}[X_i]]=0$ and the other terms are independent, the product is zero.) So each nonzero summand has at most $k/2$ different values of $i$. So there are at most ${n \choose k/2} (k/2)^k$ nonzero summands. Each summand is bounded by $1$. Thus $$\text{Ex} \left[ \left( \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right)^k \right] \leq {n \choose k/2} (k/2)^k \leq (n \cdot k^2 /4)^{k/2}.$$ Now apply Markov's inequality to obtain the result. Q.E.D. (Sorry the proof sketch is so brief. I can elaborate if you want.)

This appears as Prob. 3.8 p. 52 in Pseudorandomness by S. Vadhan.


Algebraic effects and handlers, dynamic effects What exactly are dynamic effects? What does it mean to dynamically create an effect?

In a language with algebraic effects and handlers (such as Eff or Koka) one could already do different operations based on runtime information, for example:

if x > 10 then
  get ()
else
  put 10

In this case the actual operation done will only be known at runtime. But in the Frank paper ("Do be do be do") they talk about dynamic effects in the sense of ML-style references. In what sense are references a dynamic effect that cannot be done in Eff (without resources) or Koka? Also why were resources removed again from Eff?

Let us take the example, the input/output effect. Ordinarily, one presents this with two algebraic operations print and read. We can then imagine that things get "printed out" and "read in" from some sort of a communication channel. In fact, that's how I/O works in a typical operating system.

Except that in a typical operating system one can open lots of communication channels: open files, bind to internet sockets, etc. Whenever a new channel opens, something new gets created dynamically (i.e., while the program is running). An operating system typically just creates a new integer, the "file handle", but that's just a cheap version of what we really want: an identifier that is guaranteed to be unique and that cannot be guessed by any part of the program, unless it was already given to it. (Integers can be guessed.) Let us call such a thing an instance. (In cryptography it is often called a nonce, but they cheat and think of it as an "unguessable integer". In programming languages we can make sure that instances are abstract tokens that really are unguessable.)

There are other examples where we need to create new instances. One is state, i.e., a memory location with operations update and lookup. Typical programs want to allocate any amount of memory locations, each of which is then an instance of the state effect. In general, instances allow us to create local effects, such as local exceptions and local references. In many applications it is essential to have such effects, for instance so that we can guarantee that only a certain part of the program is allowed to use a certain effect.

There is a tendency among the theoreticians to ignore effect instances because they complicate the theory. I feel that they should not be ignored because a programming language without dynamic creation of effects is next to useless. Who wants to write programs in which all memory allocations, files, and sockets, have to be specified ahead of time?


Why does IFP< not capture PTIME? Consider the logic whose $\tau$-sentences are the sentences in $IFP(\tau \cup \{<\})$, and the satisfaction relation is given by $\mathfrak{A} \models^* \phi$ if $(\mathfrak{A}, <)  \models \phi$ for every ordering $<$ of $\mathfrak{A}$. Why does this logic not capture PTIME? I suppose that it is because a machine cannot quickly determine whether whether all linear orderings satisfy the sentence, but is there a formal proof of this?

The definition of a logic $\mathcal{L}$ capturing a complexity class $\mathcal{C}$ requires that the problem of evaluating $\mathcal{L}$-formulas is itself in $\mathcal{C}$.  However, evaluating formulas of the logic you suggest is coNP-complete (in fact, even without the fixed points).

Membership. You can determine that $\mathfrak{A}\nvDash^* \varphi$ by guessing a linear order and checking that it makes the formula false.
Completeness. A graph is non-3-colourable if, and only if, every linear order $\leq$ on its vertices satisfies the property that, for every pair $x$, $y$ of vertices, at least one of the the vertex sets $\{z\mid z<x\}$, $\{z\mid x\leq z<y\}$ and $\{z\mid y\leq z\}$ contains an edge.  This property is definable without using the fixed point operator.

You could try to get around this by defining the formulas of the logic to be only the order-invariant $\mathrm{IFP}(\tau+<)$ formulas, i.e., those that are true for some linear order if, and only if, they are true for all. But it's an easy consequence of Trakhtenbrot's theorem that this class of formulas is undecidable.


Stochastic multi-armed bandit problem with transition costs The stochastic multi-armed bandit problem ($k$ arms, the $i$'th of which gives you a reward of $1$ with unknown probability $p_i$, and $0$ with probability $1-p_i$, and you must decide at each stage which arm to pull based on the past reward history) is well-studied. For example, there is the UCB1 algorithm of Auer, Cesa-Bianchi, and Fisher which achieves expected regret of $O(\log n)$ in $n$ iterations, treating the other parameters ($k$ and the probabilities $p_i$) as fixed.

My question is: is there any literature out there on this problem with transition costs?  Namely, suppose you pay a cost of $P(i,j)$ whenever you pull arm $j$ immediately after pulling arm $i$?

Thank you!

Yes, it's been studied -- for example you can look at this survey, which is from the econ community.

Also, [Auer '02] considered a similar problem, which he called "shifting bandits" where the learner has to compete with the optimal policy that's allowed to make $s$ shifts, in the adversarial setting -- see section 3 of this paper.


How should I think about proof nets? In his answer to this question, Stephane Gimenez pointed me to a polynomial-time normalization algorithm for proofs in linear logic. The proof in Girard's paper uses proof nets, which are an aspect of linear logic I don't actually know very much about.

Now, I've tried to read papers on proof nets before (such as Pierre-Louis Curien's notes on them), but I have not really understood them.  So my question is: how should I think about them? By "how to think about them", I mean both the informal intuition behind them (e.g., how they behave computationally, or how they are related to  sequents), and also which theorems about them I should prove for myself to really get them.

In answering this question, you can assume (1) I know the proof theory of linear logic well (including things like how the cut-elimination proof goes, and in focalized form too), (2) their categorical semantics in terms of coherence spaces or via Day convolution, and (3) the very basic rudiments of the GoI construction.

Proof nets are interesting essentially for three reasons:

1) IDENTITY OF PROOFS. They provide an answer to the problem "when are two proofs the same"? In sequent calculus you may have many different proofs of the same proposition which differ only because sequent calculus forces an order among deduction rules even when this is not necessary. Of course, one can add an equivalence relation on sequent calculus proofs, but then one has to show that cut-elimination behaves properly on equivalence classes, and also it is necessary to turn to rewriting modulo, which is quite more technical than plain rewriting. Proof nets solve the problem of dealing with equivalence classes by providing a syntax where every equivalence class is collapsed on a single object. This situation is anyway a bit idealistic, as for many reasons proof nets are often extended with some form of equivalence.

2) NO COMMUTATIVE CUT-ELIMINATION STEPS. Cut-elimination on proof nets takes a quite different flavor than on sequent calculi because commutative cut-elimination steps disappear. The reason is that in proof nets the deduction rules are connected only by their causal relation. Commutative cases are generated by the fact that one rule can be hidden by another causally unrelated rule. This cannot happen in proof nets, where causally unrelated rules are far apart. Since most cases of cut-elimination are commutative one gets a striking simplification of cut-elimination. This has been particularly useful for studying lambda calculi with explicit substitutions (because exponentials = explicit substitutions). Again, this situation is idealized since some presentations of proof nets require commutative steps. However, their number is much smaller than in sequent calculus

3) CORRECTNESS CRITERIA. Proof nets can be defined by translation of sequent calculus proofs, but usually a system of proof nets is not accepted as such unless it is provided with a correctness criterion, i.e. a set of graph-theoretical principles characterizing the set of graphs obtained by translating a sequent calculus proof. The reason for requiring a correctness criterion is that the free graphical language generated by the set of proof net constructors (called links) contains "too many graphs", in the sense that some graphs do not correspond to any proof. The relevance of the correctness criteria approach is usually completely misunderstood. It is important because it gives non-inductive definitions of what is a proof, providing shockingly different perspectives on the nature of deductions. The fact that the characterization is non-inductive is usually criticized, while it is exactly what is interesting. Of course, it is not easily amenable to formalization, but, again, this is its strength: proof nets provide insights that are not available through the usual inductive perspective on proofs and terms. A fundamental theorem for proof nets is the sequentialization theorem, which says that any graph satisfying the correctness criterion can be inductively decomposed as a sequent calculus proof (translating back to the correct graph).

Let me conclude that it is not precise to say that proof nets are a classical and linear version of natural deduction. The point is that they solve (or attempt to solve) the problem of the identity of proofs and that natural deduction succesfully solve the same problem for minimal intuitionistic logic. But proof nets can be done also for intuitionistic systems and for non-linear systems. Actually, they work better for intuitionistic systems than for classical systems.


Random monotone function In Razborov-Rudich's Natural Proofs paper, page 6, in the part they discuss that there are "strong lowerbounds proofs against monotone circuit models" and how they fit into the picture, there are the following sentences:

  Here the issue is not constructivity - the properties used in these proofs are all feasible - but that there appears to be no good formal analogue of the largeness condition. In particular, no one has formulated a workable definition of a "random monotone function."

Isn't it easy to distinguish the outputs of a monotone function from a random string?
Isn't the existence of strong lowerbounds telling us that there are no such things?

My question is:

  What do they mean by a workable definition of a "random monotone function"?

I'm not sure, but I think that the problem here is the fact that we don't have any strong assumptions about pseudorandom monotone function generators (at least none that I know of). The idea of the proof in Razborov-Rudich paper is as follows:

  if there is a natural property of functions (i.e. an efficiently
  decidable property that holds for
  sufficiently large subset of functions
  and implies that the function needs
  big circuits), then it can be used to
  break pseudorandom function generators
  (which breaks also pseudorandom
  generators and one-way functions).

If we were to restate the theorem in terms of monotone functions and monotone circuits, we would like it to say

  if there is a natural property of monotone functions (i.e. an efficiently decidable property that
  holds for sufficiently large subset of
  monotone functions and implies that
  the function needs big monotone
  circuits), then it can be used to
  break pseudorandom function generators
  (which breaks also pseudorandom
  generators and one-way functions),

but now the proof from the paper stops to work, because our pseudorandom generator outputs general functions, not necessarily monotone ones, and we cannot use our natural property to break it, because even a relatively large subset of monotone functions will not be large relative to general functions, for the set of monotone functions itself isn't large relative to the set of all functions ( http://en.wikipedia.org/wiki/Dedekind_number ). We could define some pseudorandom monotone function generator and use the natural property to break it, but we probably would not have the equivalence between this generator and one-way functions, so the theorem would not be so interesting.

Maybe this difficulty can be fixed (but I don't think it follows from the proof in the paper in a straightforward way) and maybe the problem with the monotone functions lies somewhere else. I would really like someone more experienced than me to confirm my answer or to show where I am wrong.


Linear regression as a hylomorphism A hylomorphism consists of an anamorphism followed by a catamorphism.
Is it possible to express linear regression as a hylomorphism?

You can indeed see linear regression as arising from a fixed point computation, but it is better to think of it as related to transitive closure computations than to folds or unfolds.
Regression is about minimising the mean squared error. A regression model has a vector of inputs (i.e., the design matrix) $X$, a vector of outputs $Y$ and a set of coefficients $\beta$, with a model
$$
   Y = X\beta + e
$$
where $e$ is a vector of errors. If we view $e$ as a function of $\beta$, we can write:
$$
   e(\beta) = Y - X\beta
$$
Then, the squared error (as a function of the coefficients $\beta$) will be given by the dot product
$$
   SE(\beta) = e^T e
$$
Then a bit of vector calculus will tell you that $\beta$ gets minimised when
$$
\beta = (x^T x)^{-1} x^T y
$$
The matrix inversion in the equation above is secretly a fixed point calculation. To get an intuition for why, you need to recall two facts.

First, the star in Kleene algebra (i.e., models of regular expressions) corresponds to iteration. You can see this in the characterizing equation:
$$A^\ast = I + A A^\ast$$

Next, square matrices with elements valued in a Kleene algebra form a Kleene algebra. So if you think of the equation above in terms of linear algebra, you can sort of see this as saying:
$$\begin{array}{lcl}
    A^\ast &=& I + A A^\ast \\
    A^\ast - A A^\ast & = & I \\
    A^\ast (I - A) & = & I \\
    A^\ast &=& (I-A)^{-1} \\
   \end{array}$$
So matrix inversion has a fundamental connection to the asteration operation in Kleene algebra.

As another source of intuition, if you think of a square Boolean matrix as representing the edge relation in a graph, the Kleene star of the graph represents reachability in the graph -- and graph reachability is very obviously a fixed point property.
This is all quite handwavy, but these ideas have been developed  rigorously. They were first (I think) introduced to computer science by Roland Backhouse and B.A. Carré, and were developed by Robert Tarjan in his 1979 paper A Unified Approach to Path Problems. (Tarjan also points out this means that many graph algorithms can be seen as sparse matrix computations!)


How quickly can we perform base extension in a residue number system? Thinking about residue number systems, one major operation is to extend the set of primes that a given value is modulated by, also known as base extension.  For instance, a given number $N$ can be represented by a sequence of remainders or modulated values by another set of numbers, which are primes.  We then have:

$$N = (n_0, n_1, \dots, n_m)$$

where

$$n_0 \equiv N \bmod p_0$$
$$n_1 \equiv N \bmod p_1$$
$$\dots$$

$$n_m \equiv N \bmod p_m$$

Suppose we have a new sequence of additional primes, $(p_{m+1}, p_{m+2}, \dots p_{m+q})$.

How quickly can we get the new sequence of remainders (or modulated values), $(n_{m+1}, n_{m+2}, \dots n_{m+q})$ for the same number, $N$, in the worst case?

Check out Lemma 4.4 in HesseAllenderBarrington - it may not be terribly useful for sequential complexity but says essentially that CRR (Chinese Remainder Representation) basis extension can be done in very uniform $\mathsf{TC}^0$. The exact bound is $\mathsf{FOM + POW} = \mathsf{FOM}$ (see also Corollary 6.2 of the same paper).