what is "one-to-one reduction from a function f to another function g" I am reading a paper called "Rational Proof". It mentioned the following one-to-one reduction. I cannot google an introduction of it.

An excerpt from the paper.
"Recall that a one-to-one reduction from a function $f$ to another function $g$ is a triple of polynomial time computable functions ($\alpha$, $\beta$, $\gamma$) such that:

For all $x$ in the domain of $f$ we have $y=f(x)$ if and only if $g(\alpha(x))=\beta(y)$
For all $x$ in the domain of $f$, let $w=\alpha(x)$. Then we have $g(w)=z$ if and only if $f(x)=\gamma(z)$.
"

Any reference for the formal definiton of the so-called "one-to-one reduction" is appreciated. Thanks.

The definition is composed of two parts. First, we want a reduction from $f$ to $g$. That's a way of computing $f$ given an oracle to $g$. This reduction is formed by two polytime functions $\alpha,\gamma$ which are used in the following way: $f(x) = \gamma(g(\alpha(x))$.

Second, we want the reduction to be one-to-one. That explains the if-and-only-if in (2). Moreover, for some reason we want an efficient one-to-one right-inverse $\beta$ of $\gamma$, satisfying $y = \gamma(\beta(y))$. The function $\beta$ can be used to answer the following question: what value of $g$ corresponds to a given value of $f$? (In contrast, $\gamma$ tells us what value of $f$ corresponds to a given value of $g$.) Why this is need will be apparent from the way the paper uses $\beta$.

The actual properties stated in the definition are slightly weaker (you want the function to be one-to-one only for values which actually occur in the formulas), but this is the gist of it.


Minimizing the maximum dot product among k unit vectors in an n-dimensional space Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let,

$$\alpha = \max_{1 \le i <j \le k} \{v_i \cdot v_j\}.$$

What is the minimum possible value of $\alpha$?

Answer: $\alpha = - 1/(k-1)$. This value is attained when vectors $v_i$ are the vertices of a regular simplex, centered at the origin.

This follows from symmetry: given a set of vectors $u_i$ consider new vectors $u_i'= \frac{1}{\sqrt{k}}\left( u_i \oplus u_{i+1} \oplus \dots \oplus u_{i-1} \right)$ (where we add up all vectors $u_i$ in the cyclic order starting from $u_i$). It is easy to show that vectors $u'_i$ form a better (or equal) solution than vectors $u_i$, and that vectors $u_i$ are vertices of a regular simplex (not necessarily centered at $0$). Symmetry arguments (like this one) are very useful in general for finding extreme configurations of vectors. In this case, it is very easy to find the value of $\alpha$ directly.

I. Let us first prove that $\alpha \geq -\frac{1}{k-1}$. We have,
$$0 \leq \|v_1 + \dots + v_k\|^2 = \sum_i \|v_i\|^2 + 2\sum_{i < j} v_i \cdot v_j \leq \sum_i 1 + 2\sum_{i<j} \alpha = k + k(k-1) \alpha.$$
We get that $\alpha \geq - 1/(k-1)$.

II. Now we prove that  $\alpha \leq -\frac{1}{k-1}$. Consider a $k\times k$ matrix $A = (a_{ij})$ with $a_{ii} = 1$ and $a_{ij} = {-1/(k-1)}$ for $i\neq j$. This matrix is (non-strictly) diagonally dominant and thus is positive semidefinite. (Note also that $A$ is the normalized Laplacian matrix of $K_k$.) Therefore, there exist a set of vectors $v_i$ with $v_i \cdot v_j = a_{ij}$. We get that
$$\alpha \leq \max_{i\neq j} a_{ij}  = -1/(k-1).$$

We proved that $\alpha = -1/(k-1)$. Note that vectors $v_i$ are vertices of a regular simplex since the distance $\|v_i - v_j\| = \sqrt{2- 2v_i \cdot v_j} = \sqrt{2k/(k-1)}$ is the same for all pairs $i,j$ (where $i\neq j$), and $\sum v_i =0$ since $\|\sum v_i\|^2 = 0$.

What we computed equals
$$-\frac1{\vartheta(\text{empty graph on } k \text{ vertices})-1},$$
where $\vartheta$ is the  Lovász Theta Function;
see the Wikipedia article on the Lovász Theta Function for details.


Solution Clusters and Monotone-2SAT It is known that generic k-SAT formulas may exhibit the presence of exponentially many solution clusters.

Question:
Is it true also for Monotone-2SAT formulas?

For the definition of cluster, see Kaveh's answer to the question SAT Solution Space - Definition of Cluster of Solutions.

The answer is no.  If you consider a graph with satisfying assignments as vertices where two assignments are joined by an edge if the Hamming distance is 1, the graph is always connected because every satisfying assignment can be eventually transformed to the all-1 assignment by changing the value of one variable from 0 to 1.


Neural Networks to classify accelerometer double taps I'm building an application for Android devices that requires it to recognize, by accelerometer data, the difference between walking noise and double tapping it. I'm trying to solve this problem using Neural Networks.
At the start it went pretty well, teaching it to recognize the taps from noise such as standing up/ sitting down and walking around at a slower pace. But when it came to normal walking it never seemed to learn even though I fed it with a large proportion of noise data.
My question: Are there any serious flaws in my approach? Is the problem based on lack of data?
The network
I've choosen a 25 input 1 output multi-layer perceptron, which I am training with backpropagation. The input is the changes in acceleration every 20ms and output ranges from -1 (for no-tap) to 1 (for tap). I've tried pretty much every constallation of hidden inputs there are, but had most luck with 3 - 10.
I'm using Neuroph's easyNeurons for the training and exporting to Java.
The data
My total training data is about 50 pieces double taps and about 3k noise. But I've also tried to train it with proportional amounts of noise to double taps.
The data looks like this (ranges from +10 to -10):
Sitting double taps: http://i.stack.imgur.com/a7PDT.png

Fast walking: http://i.stack.imgur.com/ljRwp.png
So to reiterate my questions: Are there any serious flaws in my approach here? Do I need more data for it to recognize the difference between walking and double tapping? Any other tips?

Based on your post I'm assuming you haven't had much experience with this type of work. Here are several things that immediately jump out as being potential problems:

You should probably perform some type of preprocessing so your inputs are in a more acceptable range such as (-1, 1), or (0, 1). When the magnitude of the input values are large, the the hidden units are likely to saturate (i.e. be very close to $\pm$ 1 assuming you're using tanh hidden units). This causes the gradients to be nearly zero which can result in backpropagation performing poorly.
In my experience, you will not get good results when you have very unbalanced classes (50 tap, 3000 no tap) if you just naively apply some machine learning algorithm. For example, a classifier which always outputs -1 will achieve approximately 98% accuracy on your dataset, while being completely useless for your task.
Since you have not mentioned a training/test split of your dataset or cross validation, I'm assuming you're not doing these things. You should be. Neural networks are notorious for overfitting and if you use the same data to train and assess accuracy, you almost surely will.

That being said, I'm surprised this question hasn't been closed or migrated. It is almost certainly a better match for the CS stack exchange or Metaoptimize.


Circuit Complexity Charaterization for DLogTime and NLogTime $\mathsf{DLogTime}$ and $\mathsf{NLogTime}$ are two of the smallest complexity classes we have. (Note that logarithmic time hierarchy $\mathsf{LH}$ is equal to $\mathsf{AC}^0$ and these are the first two level of $\mathsf{LH}$).

After reading this question, I become interested to see if the separation between these two classes is known, and in fact it is easy to separate them since $OR(x_1,...,x_n) \in \mathsf{NLogTime}-\mathsf{DLogTime}$ (thanks to Robin Kothari. See also known). Now I am interested to know their corresponding circuit complexity characterization. I have searched a little bit and have asked a few people but was not able to find the answer.

  Do we have nice circuit complexity characterizations for complexity classes $\mathsf{DLogTime}$ and $\mathsf{NLogTime}$?

Note: $\mathsf{DLogTime}$ shows up a lot in defining uniformity for small complexity classes. Note that the small time bound does not allow these machines to read the whole input, they can only read $\lg n$ bits from the input, and the classes are defined using machines that can write the address of a bit and then read that bit directly (i.e. don't need to go over all previous bits to reach there).

I think it is far more interesting that the circuit complexity classes used by CS complexity theory make different predictions and use different metrics than those in the VLSI community.  From The VLSI complexity of Boolean functions:

  It is well-known that all Boolean functions of $n$ variables can be computed by a logic circuit with $O(2^n/n)$ gates (Lupanov's theorem) and that there exist Boolean functions of n variables which require logic circuits of this size (Shannon's theorem). We present corresponding results for Boolean functions computed by VLSI circuits, using Thompson's model of a VLSI chip. We prove that all Boolean functions of $n$ variables can be computed by a VLSI circuit of $O(2^n)$ area and period 1, and we prove that there exist Boolean functions of $n$ variables for which every (convex) VLSI chip must have $\Omega(2^n)$ area.

Interestingly, VLSI circuit complexity has a tendency to treat depth as "irrelevant" as there is one and only one "depth" that matters: the critical path.  For most practical purposes, an arbitrarily complex circuit can be treated as $O(1)$ with a latency of $n$.

In fact, I'm not even sure that the concept of $DLogTime$ / $NLogTime$ directly translates in to VLSI circuit complexity.  Even Shannons $2^n/n$ result does not readily translate: Shannons results is valid only for a boolean basis consisting of arity $\le2$ {AND, OR, NOT}.  This is not the only basis, and the number of "gates" needed drops dramatically as you allow more and more gate types.  The following are $area^2$ from a commercial VLSI standard cell library normalized to the size of a 2 input NAND gate:

        2    3    4    <- Arity
and    1.14 1.28 1.41
nand   1.00 1.14 1.28
or     1.14 1.41 1.41
nor    1.00 1.14 1.41
xor    1.62 2.44
xnor   1.62 2.44

buf    1.14
inv    0.80

aoi22  1.28
aoi222 1.62
aoi33  1.62
oai22  1.41
oai222 1.72
oai33  1.62

addf   2.64

Specifically, note the aoi / oai gates which are And Or Invert / Or And Invert consisting of arity sized first function feeding the second function, where the number of first function gates is equal to the number of times arity appears.  For example, aoi22 represents "Two 2 input AND gates feeding a NOR gate".

My point is: Taken separately, a oai222 function can be built using three 2 input OR gates and a 3 input NAND gate, for a total area of ~4.56, not including any area used for interconnect.  Yet this primitive can be realized in an area of just 1.72, which means a discrete manifestation of the same boolean function consumes 2.65 times more area.

Also note that the area for an $n$ input {AND, NAND, OR, NOR, XOR, XNOR} gate, where $n\ge2$, is much less than the area that it would take to build the same function using discrete 2 input gates.  Also note that while the area given for {XOR, XNOR} for this process is "large" relative to the other gates, there are other ways to build the same $n$ input gates using less area.

The propagation properties for the more complex primitives is also significantly better than what would be achieved using discrete gates.

Why is this important?  Because for me, at least, I've spent a simply enormous amount of time sifting through results from complexity theory that are built on a set of assumptions that has the effect of either rendering the result useless or wrong once the assumption is violated.  The following is from Steven Cooks $\mathcal{P}$ vs $\mathcal{NP}$:

  Thus to prove $\mathcal{P} \ne \mathcal{NP}$ it suffices to prove a super-polynomial lower bound on the size of any family of Boolean circuits solving some specific $\mathcal{NP}$-complete problem, such as 3-SAT. Back in 1949 Shannon proved that for almost all Boolean functions $f : \{0,1\}^n \to \{0,1\}$, any Boolean circuit computing $f$ requires at least $2^n/n$ gates. Unfortunately, his counting argument gives no clue as to how to prove lower bounds for problems in $\mathcal{NP}$.

I find Cooks reasoning curious.  Shannons result is valid for all $f : \{0,1\}^n \to \{0,1\}$, therefore if a $\mathcal{NP}$ problem can be described in $\{0,1\}^n$ bits, there must be a {AND, OR, NOT} basis circuit that can decide if it is satisfiable in ~$2^n/n$ gates (the actual paper gives a larger upper, but finite, bound for every possible function).  What this tells us is that anything that uses more than $n$ gates, where $n$ is the upper bound for the size of the $\mathcal{NP}$ problem, is using more gates than is required.  Using a larger, but complete, boolean basis only reduces the number of gates required.  Using a different circuit complexity model, i.e. VLSI, gives even "better" result bounds.  Curious.  But we know for a fact that any solution to a $\mathcal{NP}$ problem that uses more than ~$2^n/n$ "gates" (where gates is used loosely for steps / operations) is doing so in a sub-optimal fashion... and there's an infinite number of ways to find a solution in a sub-optimal fashion.

On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication shows that predicting circuit complexity using a OBDD model over-estimates the actual circuit complexity:

  Lower-bound results on Boolean-function complexity under two different models are discussed. The first is an abstraction of tradeoffs between chip area and speed in very-large-scale-integrated (VLSI) circuits. The second is the ordered binary decision diagram (OBDD) representation used as a data structure for symbolically representing and manipulating Boolean functions. The lower bounds demonstrate the fundamental limitations of VLSI as an implementation medium, and that of the OBDD as a data structure. It is shown that the same technique used to prove that any VLSI implementation of a single output Boolean function has area-time complexity $AT^2 = \Omega (n^2)$ also proves that any OBDD representation of the function has $\Omega(c^n)$ vertices for some $c<1$ but that the converse is not true. There are functions for which any OBDD representation is of exponential size, but there is a VLSI implementation of complexity $AT^2 = O(n^{1+c})$.

  An integer multiplier for word size $n$ with outputs numbered 0 (least significant) through $2n-1$ (most significant) is described. For the Boolean function representing either output $i-1$ or output $2n-i-1$, where $1\le i\le n$, the following lower bounds are proved: any VLSI implementation must have $AT^2 = \Omega(i^2)$ and any OBDD representation must have $\Omega(1.09^i)$ vertices.


The power of randomized logspace with two-way access to the random tape Let $\mathsf{ZPL}$/$\mathsf{RL}$/$\mathsf{BPL}$ denote the classes of the languages which are accepted (with zero/one-side/two-side error) by a logspace Turing machine with one-way access to the random tape.

Let $\mathsf{ZP^*L}$/$\mathsf{R^*L}$/$\mathsf{BP^*L}$ denote the corresponding classes by replacing one-way to two-way access.  We have the normal inclusions $\mathsf{ZPL} \subseteq\mathsf{RL}\subseteq\mathsf{BPL}$ and $\mathsf{ZP^*L} \subseteq\mathsf{R^*L}\subseteq\mathsf{BP^*L}$.

In the following paper,

  On Read-Once vs. Multiple Access to Randomness in Logspace, Noam Nisan, 1995

he prove that $\mathsf{BPL} \subseteq \mathsf{ZP^*L}$, which is rather surprising because it seems that two-way access may be stronger than the one-way access.

  Question.  Do we have any further results which demonstrate the power of two-way access randomized logspace?

Well, here are a couple of observations. There's a famous PRG by Nisan that fools $\mathsf{BPL}$-type algorithms with seed length $O(\log^2 n)$. Given two-way access to the seed, Nisan's PRG can be computed in space $O(\log n)$. Therefore, every language in $\mathsf{BPL}$ can be decided by a $\mathsf{BP}^*\mathsf{L}$-type algorithm that only uses $O(\log^2 n)$ random bits.

In fact, you can get the best of both worlds. By using the same technique that Nisan used to show $\mathsf{RL} \subseteq \mathsf{SC}$, one can show that every language in $\mathsf{BPL}$ can be decided by a $\mathsf{ZP}^*\mathsf{L}$-type algorithm that only uses $O(\log^2 n)$ random bits.

So in terms of the state of the art, two-way randomness is more powerful both qualitatively (two-sided error vs. zero-sided error) and quantitatively (polynomially many random bits vs. polylogarithmically many random bits). However, it seems likely that $\mathsf{L} = \mathsf{BP}^*\mathsf{L}$ and hence the two models are actually equivalent.


Average-case analysis of algorithms using the incompressibility method I recently became very interested in Kolmogorov complexity and the incompressibility method especially in the context of average-case analysis. The "standard" book by Li & Vitanyi showcases many examples, although only two of them are about average-case analysis (heapsort and shellsort). I also found a paper analyzing the average-case of quicksort using incompressibility.

This got me wondering: is there some reason exactly these algorithms were analyzed? More generally, is there something in the nature of an algorithm that makes it suitable (or not at all suitable) for analysis using the incompressibility method?

In addition, does anyone know of any other papers/resources that show even trivial average-analysis of different kind of algorithms, perhaps other than sorting algorithms using the method?

I think that the recent constructive proof of the Lovasz Local Lemma (http://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html) and Patrascu's analysis of the component size in cuckoo hashing might both qualify.  These are both stated in terms of random strings, but would also work with Kolmogorov random strings (http://infoweekly.blogspot.com/2010/02/cuckoo-hashing.html).


What good notations for deterministic context-free and visibly pushdown languages exist? Deterministic context-free languages (DCFL) and visibly pushdown languages (VPL) are both sets of formal languages between context-free languages (CFL) and regular languages (REG). Is there a readable notation that can be expressed in plain ASCII like Backus-Naur-Form for CFL and regular expressions for REG?

Regarding DCFLs, I do not see a better notation than the transition function of the deterministic pushdown automaton, i.e. writing explicitly rules of form $q,z,a\to q',\gamma$ with $q,q'$ states in $Q$, $z$ a stack symbol, $\gamma$ a sequence of stack symbols, and $a$ an input symbol or the empty string.  The notation itself does not enforce determinism, but it is easily checked.  Using a context-free grammar kind of notation (as BNF), you are going to run into problems since DCFLs are a proper subclass of CFLs, and as noted by DaniCL, you cannot decide in general given a CFG whether its language is deterministic.

Regarding VPLs, a bracketed/parenthesis-style for CFGs would be good enough, with rules of form $A\to a\alpha b$ where $A$ is a nonterminal, $a$ a call symbol, $b$ a return symbol, and $\alpha$ a sequence of regular expression over mixed internal symbols and nonterminals.  Since any VPL is also a (D)CFL you could also reuse the above notation for pushdown automata and check that the stack operations match the calls and returns, or write down the transition relation of a nested word automaton (which would be less redundant).

Edit: come to think of it, a notation for XML schemas, like the compact syntax of RelaxNG---which is an ASCII notation---, could easily be used for VPLs.  You'd just need to enforce some naming conventions for tags, e.g. an opening tag "<ab>" for a call symbol $a$ matching a closing tag "</ab>" for a return symbol $b$.


What is the current known hardness of Graph Isomorphism? Inspired by the question is factoring known to be P-hard, I wonder what the current similar state of knowledge is about the hardness of graph isomorphism. I am sure that it is currently not known if GI is in P, but:

  what is the currently known largest class that GI is harder than?

(it was not answered at a similar sounding question)

To address some of the comments, I want to know the currently known maximal class(es) that GI, the problem is complete for. Known algorithms for GI are upper-bounded by superpolynomial functions, and it is a member of NP. But it is not known that GI is P-hard. I'd like to know any classes C for which it -is- known it is C-hard, and hopefully as inclusive as possible.

Graph Isomorphism is hard for DET, the class of problems which are $NC^1$ reducible to the determinant. See "On the Hardness of Graph Isomorphism" by Jacobo Toran. http://epubs.siam.org/sicomp/resource/1/smjcat/v33/i5/p1093_s1?isAuthorized=no

It seems this is the strongest hardness result to date.


What are the relationship and difference between ambiguous grammars and non-deterministic ones? Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars.  According to Wikipedia however, this is false:

  there are non-deterministic unambiguous CFGs

What is the difference between ambiguity and determinism in grammars?  What is an example of a grammar that is non-deterministic but unambiguous?

See this related Wikipedia link:

http://en.wikipedia.org/wiki/Unambiguous_grammar#Recognizing_ambiguous_grammars

  The efficiency of context-free grammar parsing is determined by the
  automaton that accepts it. Deterministic context-free grammars are
  accepted by deterministic pushdown automata and can be parsed in
  linear time, for example by the LR parser.[3] This is a subset of the
  context-free grammars which are accepted by the pushdown automaton and
  can be parsed in polynomial time, for example by the CYK algorithm.
  Unambiguous context-free grammars can be nondeterministic. For example, the language of even-length palindromes on the alphabet of 0
  and 1 has the unambiguous context-free grammar S → 0S0 | 1S1 | ε. An
  arbitrary string of this language cannot be parsed without reading all
  its letters first which means that a pushdown automaton has to try
  alternative state transitions to accommodate for the different
  possible lengths of a semi-parsed string.[4] Nevertheless, removing
  grammar ambiguity may produce a deterministic context-free grammar and
  thus allow for more efficient parsing. Compiler generators such as
  YACC include features for resolving some kinds of ambiguity, such as
  by using the precedence and associativity constraints.

An ambiguous grammar may be defined as a grammar for which there exists more than one parse tree for some string belonging to the language it generates.

A deterministic grammar may be defined as a grammar for which there exists a deterministic machine model which is capable of recognizing the language it generates.

Assume Grammar 1 generates the same language as Grammar 2.  Assume Grammar 1 is unambiguous and Grammar 2 is ambiguous.  If a deterministic machine model is capable of recognizing the language generated by Grammar 1, then it is also capable of recognizing the language generated by Grammar 2 (by the assumption that they both generate the same language).  Clearly, both are deterministic grammars and yet they differ on the question of ambiguity.

The definition of grammar ambiguity addresses the actual syntactical structure of the grammar and its relation to parsing, NOT whether an ambiguous grammar could be structured differently so as to generate the same language and yet remove ambiguity.

The definition of grammar determinism, however, is not related to the structure of a grammar but rather to the properties of the language it generates regarding recognition by an appropriate deterministic machine model.


What is the most intuitive dependent type theory I could learn? I am interested in getting a really solid grasp on dependent typing. I've read most of TaPL and read (if not fully absorbed) 'Dependent Types' in ATTaPL. I've also read and skimmed a bunch of articles on dependent typing.

Many type theory discussions seem to focus on adding incremental features to previous type systems, not "what's the next large generalization up from type system X?". Dependent types seem to be the next large generalization from System F, but I have yet to find the intuitive, canonical dependently typed language. The many references to Calculus of (inductive) Constructions makes me think CoC is that language, but the explanations of the language I have seen don't seem very clear or intuitive to me.

I am expecting/guessing such a language would have features like: (and please let me know if anything in particular jumps out as confused or unrealistic)

Generalized abstraction (can have functions from any domain in the type hierarchy to other, kind -> term, term->type''' etc.)
Has an infinite hierarchy of typing (terms : types : types' : types'' : ...)
A minimum number of basic elements. I am imagining that the language only asserts a single element for each level. For example it might assert that (() : Unit : Type : Type' : ...). Other elements are built from these elements.
Sum and product types are derivable.

I am also looking for an explanation of that language which ideally would discuss:

The relationship between abstraction and quantification in that language. If they are not unified, then explain why they are not unified.
The infinite type hierarchy explicitly

I am asking this question because I want to learn dependent type theory but also because I want to put together a guide that, assuming a little CS background, teaches the use of and how to understand proof assistants and dependently typed languages.

(Cross posted to Reddit)

There are a few different ways of approaching this:

Dependent Type Theory.
This is probably not the easiest way of learning about dependent types, but you could look at the Calculus of Constructions papers and their variants, Pure Type Systems, and Martin Hofmann's article on the Syntax and Semantics of Dependent Types, for example.
Theorem proving. Firstly, take a look at my answer to a related question: How would I go about learning the underlying theory of the Coq proof assistant?.
Programming with dependent types. Looking at recent languages with dependent types  such as Epigram or Agda or less recent ones such as Dependent ML and writing some programs will help solidify the ideas. Epigram, for example, is extremely clean in design. Another angle is to see how dependent types are implemented. One practical dependent type theory is $\Pi\Sigma$: Dependent Types without the sugar. Several PhD theses are devoted to programming with dependent type theory: Dan Licata's, Nils Anders Danielsson's, Ulf Norrel's, Susmit Sarkar's, among others. And of course there's Adam Chlipala's book, given in Marc Hamann's answer.

I'd be inclined to start with programming, before moving to using theorem proving, then start exploring the more theoretical issues.


Cliquewidth of Almost Cographs (I posted this question to MathOverflow two weeks ago, but so far without a rigorous answer)

I have a question about graph width measures of undirected simple graphs. It is well-known that cographs (graphs which can be built by the operations of disjoint union and complementation, starting from isolated vertices) have cliquewidth at most 2. (Courcelle et al, Upper bounds to the clique width of graphs). Now consider some fixed non-negative integer k, and consider the class of graphs $\mathcal{G} _k$ of graphs such that for every $G = (V,E) \in \mathcal{G} _k$ there is a set $S$ of at most k vertices such that $G[V - S]$ is a cograph. Since the graph class $\mathcal{G} _k$ can also be seen as the class of graphs that can be built out of cographs by adding at most $k$ vertices, this class has also been called cographs + $kv$.

My question is: what is a tight bound on the cliquewidth of graphs in $\mathcal{G}_k$, i.e. the graphs which can be turned into a cograph by deleting k vertices?

It is known that if a graph $G$ is obtained from $H$ by deleting $k$ vertices then $cw(H) \leq 2^k (cw(G) + 1)$. This shows that if a cograph $G$ can be obtained from a graph $H$ by deleting $k$ vertices, then $cw(H) \leq 2^k (3 + 1)$, and hence the cliquewidth of a graph in $\mathcal{G}_k$ is at most $4*2^k$. I am unsure whether this exponential dependency on $k$ is necessary. In this context I would also be interested in the maximum decrease in the cliquewidth by deleting a vertex; i.e. if we delete a single vertex from a graph, how much can the cliquewidth decrease?

I will try to answer this old question of yours, although I am not sure my answer is conclusive but it should point you in the right direction.

First let us discuss linear clique-width.
If a graph has linear clique-width $k$, and one add $1$ vertex to the graph, that vertex can always be placed first in the ordering with a unique color.
Hence linear clique-width only increases by at most 1 when you add a vertex.

Gurski and Wanke showed in "On the relationship between NLC-width and linear NLC-width" that cographs have unbounded linear clique-width.

Since cographs have unbounded linear clique-width but bounded clique-width any good clique decomposition must have a tree structure.
We must show that we can force arbitrarily many deep branches.
Now we do as we do for trees, construct a tree with at 2^k leaves add k vertices and each leaf is connected to a unique subset of new vertices.


Which algorithms are used most often in practice? Which algorithms are used most often?

Please write a single algorithm per answer, try to keep your answer short (one or two lines).

Is the Fast Fourier Transform the algorithmic problem solved most times per day by real computer systems?  It has to be close.  So I'd nominate the Cooley-Tukey FFT algorithm.


Nondeterministic communication complexity of set disjointness? In the two-party setting, bounds of $\Theta(n)$ bits are known for deterministic and bounded-error randomized protocols for $\text{DISJ}_n$.
(Here $\text{DISJ}_n$ is the $n$-element set disjointness function; the parties are each given $n$-bit Boolean vectors $x$ and $y$, and have to decide whether there is some index $i$ so that $x_i = y_i = 1$.)

In contrast, for nondeterministic protocols in the two-party setting, the best lower bound I've been able to find in the literature is $\Omega(n^{1/2})$ bits: Alexander A. Sherstov, Communication Lower Bounds Using Directional Derivatives, JACM 2014, doi:10.1145/2629334 (preprint).
A large gap remains between this and the trivial upper bound of $n+1$ bits.

Sherstov's bound is for multiparty protocols.

  Is a better lower bound known for the 2-party case?

Here follows a simple (folklore?) argument that $\Omega(n/\log n)$ bits are required; I am looking for a reference for this so I can cite it, or ideally a stronger $\omega(n/\log n)$ bound.

A standard result (e.g. Theorem 2.11 in the Kushilevitz/Nisan textbook) is that $$D(f) \le O(N^0(f)N^1(f)),$$ where $N^1(f)$ is the nondeterministic communication complexity of $f$ and $N^0(f)$ is the co-nondeterministic communication complexity.
For $f = \text{DISJ}_n$ it is easy to see that $N^0(f) = O(\log n)$, by guessing the index of a common element.
Hence there are constants $C_1,C_2,C_3$ such that for all sufficiently large $n$,
$$C_1 n \le D(f) \le C_2 N^0(f)N^1(f) \le C_2 C_3(\log n)N^1(f).$$
Hence $N^1(f) \ge \Omega(n/\log n)$.

$N^1(DISJ_n) \geq n$.

The fooling set technique actually provides lower bounds on the cover number. $C^1(f)$ is the minimum number of monochromatic rectangles needed to cover the $1$-inputs of $f$.  In the fooling set technique, you create a set of input pairs and show that each must lie in distinct monochromatic rectangles.

In this case, look at the set of input pairs $\{(A,\bar{A}) : A \subseteq [n]\}$.  It is not too hard to show that $(A, \bar{A}), (B, \bar{B})$ must lie in different monochromatic rectangles if $A,B$ are distinct.  Hence, to cover the $1$-inputs, we need at least $2^n$ monochromatic rectangles.

Using $N^1(f) = \log_2(C^1(f))$, we get that $N^1(DISJ_n) \geq n$.

(This example is Example 1.23 from Kushilevitz/Nisan)


Are vertex colourings--in a sense--edge colourings? We know that edge colourings of a graph $G$ are vertex colourings of a special graph,
namely of the line graph $L(G)$ of $G$.

Is there a graph operator $\Phi$ such that vertex colourings of a graph $G$ are
edge colourings of the graph $\Phi(G)$ ?
I am interested in such a graph operator that can be constructed in polynomial time,
i.e. the graph  $\Phi(G)$ can be obtained from $G$ in polynomial time.

Remark:  Similar question can be asked for stable sets and matchings. A matching
in $G$ is a stable set in $L(G)$. Is there a graph operator $\Psi$ such that stable sets
in $G$ are matchings in $\Psi(G)$?
Since STABLE SET is $\mathsf{ NP}$-complete and MATCHING belongs to $ \mathsf{P}$, such a
graph operator $\Psi$ (if exists) cannot be constructed in polynomial time, assuming
$\mathsf{NP}\not=\mathsf{P}$.

EDIT: Inspired by @usul's answer and @Okamoto's and @King's comments, I found a weaker form for my problem: Vertex colourings of a graph $G$ are edge colourings of a hypergraph $\Phi(G)$ defined as follows. The vertex set of $\Phi(G)$ is the same
vertex set of $G$. For each vertex $v$ of $G$, the closed neighbourhood $N_G[v]= N_G(v) \cup\{v\}$ is an edge of the hypergraph $\Phi(G)$. Then $G$ is the line graph of the hypergraph $\Phi(G)$ and therefore vertex colourings of $G$ are edge colourings of $\Phi(G)$.

Again, I am grateful for all answers and comments showing that, with or without assuming $\mathsf{NP}\not=\mathsf{P}$, the operator I am looking for cannot exist. It would be nice if I could accept all the answers!

By analogy with the line graph, I think you are asking the following:

  For every undirected graph $G = (V,E)$, does there exist an undirected graph $G' = (V',E')$ such that each vertex $v \in V$ corresponds to an edge $(v_1,v_2) \in E'$ and the edges corresponding to $u \in V$ and $v \in V$ share at least one endpoint if and only if $(u,v) \in E$?

The answer can be seen to be no. Consider the four-vertex tree $G$ with root $v$ having three children $x,y,z$. In $G'$, we must have four edges: $(v_1,v_2),(x_1,x_2),(y_1,y_2),(z_1,z_2)$. Further, it must be the case that either $v_1$ or $v_2$ is an endpoint of each of the other three edges (i.e., $\left| \{v_1,v_2\} \cap \{x_1,x_2\} \right| \geq 1$, etc). But this means that at least two of the other three edges must share a common endpoint, which violates our requirements since no two of $x,y,z$ are adjacent in the original graph.

I think the same graph will give you a counterexample for the matching question as well.


How is it proven that Key Exchange implies OWFs? Page 38 says that Key Exchange implies the existence of one-way functions.

When I try to work out the proof myself, I get that in the hypothetical case

where there is Key Exchange but no one-way functions, an eavesdropper

would have a non-negligible probability of obtaining a random bits that would

have produced that communication actually observed, and then I get stuck.

As far as I can see, it could be that when the eavesdropper finds such bits,

the probability that the bits found would give the same key as

the parties get from the random bits actually used is negligible.

Does the existence of a secure Key Exchange protocol imply the existence of one-way functions?

If yes, how is that proven?

Your question suggests the following tentative reduction to obtain a OWF from a secure KE: Given an input, interpret it as the private random coins of two simulated parties to the KE protocol. Based on their private randomness, there will be some sequence of public messages between them, and at some point they will stop and agree on a private shared key (with some high probability). Then the public transcript of their communications is the output of the OWF.

You are right to be worried about this approach in the case when Alice and Bob may not agree with probability 1. In fact, this construction is NOT necessarily a OWF in that case. Rather, it is a weaker primitive known as a "distributionally one-way function," which is, informally, a function for which it is hard to generate a uniformly random preimage of $f(x)$, when $x$ is selected at random. It is known (but non-obvious) that one can construct a true one-way function using a distributionally one-way function. See e.g. Exercise 17 on page 96 of Goldreich "Foundations of Cryptography: Basic Tools," which is available for limited viewing on Google preview.

To directly see why the above reduction does not suffice, we can use the common "make a stupid modification" technique. Namely, suppose there exists a secure KE protocol where Alice and Bob agree with probability $1 - \epsilon$. Consider a stupidly-modified KE protocol that works as follows: Alice and Bob first each flip 100 coins. For each of Alice, Bob individually: If all 100 coins are zero, their remaining randomness is interpreted as encoding a sequence of messages which they send to the other party, ignoring whatever the other one says; then they just output a random "shared key." (Otherwise they follow the original protocol.) Given any public transcript, it is possible (with negligible probability) that it was generated by an Alice and Bob who BOTH flipped 100 zeroes and happened to have their remaining randomness specify that exact sequence of messages.

This is still a secure KE protocol, where Alice and Bob will agree with probability at least $1 - \epsilon - 2^{-100}$. On the other hand, it utterly fails to be a OWF in the hoped-for manner, since an attacker who sees some public transcript can always trivially invert by choosing 100-zeroes randomness for each of Alice and Bob.


Lower bound for orienting an asynchronous ring? We require a lower message complexity bound of an asynchronous distributed algorithm that do the following:
Given a undirected ring, with $n$ vertices, we want to let each node direct its edges to form a directed cycle in the ring.

That is: if our ring is : a-b-c-d-a ---> then we want our result to be a->b->c->d->a

Note that the nodes in the ring do not have a common definition of left and right .. that is, the left of node a may be the right of node b etc .. (this is why the problem is difficult)

I think that the lower bound is $\Omega(n\log n)$ - similar to the election problem. But I cannot prove it until now.
I was trying to prove it by contradiction with other known lower bounds. That is, if we can solve this problem, then we can solve problem A with a complexity lower than its known lower bound. I tried it with the election problem, it did not work obviously.
Any suggestions ?

Edit: The answer below was written assuming that the ring is synchronous.

Note that if node ids are chosen from some countable set and you don't care about time complexity, the $\Omega(n\log n)$ messages lower bound for electing a leader in a synchronous ring does not apply.

In that case, there's an $O(n)$ messages algorithm that solves your problem: First, elect a leader using the $O(n)$ time-slicing algorithm of [1], and then, as mentioned in your comment, use the leader to orient the ring. Moreover, $\Omega(n)$ seems to be a trivial lower bound: If $o(n)$ messages are being sent, then there is a segment of $2$ neighboring nodes that do not send/receive any messages throughout the run. By an indistinguishability argument, you can show that there is a run where you get conflicting orientations.

[1] Greg N. Frederickson, Nancy A. Lynch: Electing a leader in a synchronous ring. J. ACM 34(1): 98-115 (1987)


The complexity of counting simple paths in a directed graph Let $G$ be a digraph (not necessarily a DAG) and let $s,t \in V(G)$. What is the complexity of counting the number of simple $s-t$ paths in $G$.

I would expect the problem to be #${\mathsf P}$-complete but have not been able to locate an exact reference.

Also notice that a number of similar questions have been answered correctly here
and elsewhere but not this precise question - to emphasise I am not interested in counting walks and/or undirected graphs (in the first case the variant is in ${\mathsf P}$ and in the other #${\mathsf P}$-hard).

The #P-completeness proof of counting simple s-t paths in both undirected and directed graphs can be found in:

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

From the paper:

...
4. Some #P-complete problems
...
14. S-T PATHS (i.e. SELF AVOIDING WALKS) (directed or undirected)
Input: $G; s,t \in V$
Output: Number of (directed) paths from $s$ to $t$ that visit every node at most once.
...


How are side effects handled in semantics? In Anthony Aaby's "Introduction to Programming Languages" section on Semantics, he makes the following observation:

  Much of the work in the semantics of
  programming languages is motivated by
  the problems encountered in trying to
  construct and understand imperative
  programs---programs with assignment
  commands. Since the assignment command
  reassigns values to variables, the
  assignment can have unexpected effects
  in distant portions of the program.

This strikes me as a remarkable admission, that allowing side effects would motivate a major part of the work in semantics.

How does the existence of side effects in a programming language impact the ability to map a program to a computational model?  Are there approaches to managing state that can improve this process while still allowing side effects?

Building on Charles's answer, the main difficulty in the theory of programming languages is that the natural notion of equivalence of programs is typically not strict equality either in the most straightforward mathematical semantics you can give, or in the underlying machine model. For example, consider the following bit of Java-like code:

Object x = new Object();
Object y = new Object();
... some more code ...

So this program creates an object and names it x, and then creates a second object named y, and then continues executing some more code. Now, suppose that a programmer decides to flip the order of allocation of these two objects:

Object y = new Object();
Object x = new Object();
... some more code ...

Now, ask the question: does this refactoring change the behavior of the program? On the one hand, on the underlying machine, x and y will be allocated at different locations in the two runs of the program. So in this sense, the program behaves differently.

But in a Java-like language, you can only test references for equality, and not for order, so this is a difference that the "some more code" cannot observe.  As a result, most programmers will expect that reversing the order will make no difference to the final answer, and most compiler writers expect to be able to perform reorderings and optimizations on this basis. (On the other hand, in a C-like language, you can compare pointers for ordering, by casting them to integers first, and so this reordering does not necessarily preserve observable behavior.)

One of the central questions of semantics is to answer the question of when two programs are observably equivalent. Since our notion of observation depends on the features of the programming language, we end up with a definition like "two programs are equivalent when no client program can compute different answers based on receiving those programs as inputs." The quantification over all client programs is what makes this question difficult -- it seems like you end up having to say something about all possible client programs to say something about two particular pieces of code.

The trick with denotational semantics is to give a mathematical interpretation that lets you avoid this universal quantification -- you say that the meaning of a piece of code is some mathematical value, and you compare them by checking to see if they're mathematically equal or not. This is local (ie, compositional), and does not involve quantification over all possible clients. (You do need to show that the denotational semantics implies contextual equivalence for it to be sound, of course. When it is complete -- when denotational equality is exactly the same as contextual equivalence, we say the semantics is "fully abstract".)

But means that you need to ensure that the denotational semantics validates those equivalences. So for this example, if you wanted to give a denotational semantics for this Java-like language, you need to ensure not just that calling new takes a heap and gives you back a new heap with the newly-created object, but that the meaning of the program is invariant same under all permutations of the input heap. This can involve quite complex mathematical structures (eg, in this case working in a category which ensures everything works modulo a suitable permutation group).


Kolmogorov's conjecture that $P$ has linear-size circuits In his book, Boolean Function Complexity, Stasys Jukna mentions (page 564) that Kolmogorov believed that every language in P has circuits of linear size. No reference is mentioned and I couldn't find anything online. Does anyone know more about this?

[Following a suggestion of Kaveh, I am putting my (somewhat extended) comment as an answer]

This "conjecture" of Kolmogorov is just a rumor. It was not published anywhere. In the former USSR, "publishing" mathematics meant something different than what it does today: give a talk at a seminar or tell your colleagues at lunch. Counting papers was not an issue. (Actually, I've also enjoined this way of doing math.) I cannot exclude the possibility that this "conjecture" was just told to Levin by Kolmogorov during their walk to a seminar at Moscow University.  So don't take this too seriously as a formal conjecture; it is just a rumor that (needless to say) hasn't been refuted over the years. But since a giant such as Kolmogorov seriously thought about this problem, and hasn't excluded the possibility of a "devil's power", the conjecture should be treated seriously enough, just as a warning about our possibly wrong intuition on what circuits actually do.

Here is a (very, very rough) speculation of my understanding of this conjecture. Our (apparently wrong) intuition about how circuits work relies on viewing the computation by a program as a sequential process which gradually collects information about the input string. This intuition is borrowed from our view of how a Turing machine works. But each input string $x$ determines a subcircuit (witnessing $f(x)=1$ or $f(x)=0$). And for a circuit to be correct, it is enough that the sets of subcircuits for $f^{-1}(1)$ and $f^{-1}(0)$ are disjoint. That is, a circuit is a compact "local encoding" of a given partition of the $n$-cube. The length of this code is the Kolmogorov complexity of the given binary string $f_n$ of length $2^n$. A polynomial time algorithm, however, does more: it gives one "global encoding" of the entire infinite string $f$ for all $n$. Now, an infinite string $f$ allowing an encoding of size $n^c$ must be "simple", and its prefixes "should" allow even more compact "local" encodings. Of course, it remains a mystery why Kolmogorov thought that "local" encodings even of size $cn$ for some $c$ may then be sufficient...

P.S. Sorry, forgot to add: An excellent confirmation of my "thesis" that circuits should be viewed as (static) codes rather than (dynamic) algorithms is the famous
theorem of David Barrington that the entire class $NC^1$ can be simulated by polynomial-size branching programs of width 5. The "gathering information" view here is totally wrong: it is not even clear how to compute the majority function by keeping only 5 bits of information. A clever idea of David was just to encode the behavior of a given formula by particular sequences of 5-permutations, and to show that accepted and rejected strings will get different codes. The point is that a branching program also does not "compute" --- it rather encodes input strings by its sub-programs: when an input arrives, inconsistent edges disappear, and we have a code of this input.


Cut-elimination for calculus with nats or other inductive datatype? Does anyone direct me to a paper detailing a cut-elimination theorem for propositional intuitionistic logic, including an inductive datatype such as the natural numbers (lists or trees would be fine, too)? An example of the kind of system I am interested in is Godel's T, which has types given by the grammar $A ::= \mathbb{N} \;\;|\;\; A \to A'$. I am not very interested in quantifiers over natural numbers or predicates indexed by natural numbers.

I know how to prove beta-normalization for natural deduction version of these systems using a logical relations argument (or related techniques such as NbE), but would like to know if there are standard references on how to adapt these methods to sequent calculi.

The reason I ask is that I am studying adding fixed point operators for guarded recursion to a language. The denotational idea is a rather old one -- interpret types as ultrametric spaces and fixed points via Banach's theorem -- but the purely syntactic techniques I know for proving cut-elimination don't seem to adapt that well.

How about Ulrich Berger's work? For example Strong normalization for applied lambda calculi. The "recursively defined constants" part gets you inductive types, more or less. And don't be put off by the word "untyped", he gets results for typed systems too.


Representation of procedural knowledge I know that knowledge about relationships between things can be represented using ontologies and stored in some sort of file or database system.

Can a network of procedural knowledge also be created in this way? Such that complex algorithms can be defined and stored efficiently, translated into other languages and forms (such as finite state machines or machine language), changed, and form the basis for other AI axioms?

i.e. Procedural Reasoning Systems -- how would a Knowledge Area (KA) be represented as a cognitive primitive in a computer system?

You are probably speaking about something like a process ontology. Lately, that research has focused (moved?) on semantic workflows, e.g. to model processes in science, related with reproducibility. Similarly, we can also find the application of ontologies to business processes.

For more classical (lower level?) approaches, you may be interested in the homoiconicity property of programming languages like Lisp. In such a case these "networks" usually take the shape of parse trees, i.e. the representation is at a syntactic level and semantics are implicit, e.g. loops and recursive calls are still just a syntactic tree, even if the execution would not result into a tree.


Tardos Function Counterexample to Blum's $P\neq NP$ Claim In this thread, Norbet Blum's attempted $P \neq NP$ proof is succinctly disproved by noting that the Tardos function is a counterexample to Theorem 6.

Theorem 6: Let $f \in \mathcal{B}_n$ be any monotone Boolean function. Assume that there is a CNF-DNF-approximator $\mathcal{A}$ which can be used to prove a lower bound for $C_m(f)$. Then $\mathcal{A}$ can also be used to prove the same lower bound for $C_{st}(f)$.

Here's my problem: the Tardos function is not a Boolean function, so how does it satisfy the hypotheses of Theorem 6?

In this paper, they discuss the complexity of the function $\varphi(X) \leq f(v)$, which is not in general a monotone Boolean function, since increasing edges can make $\varphi(X)$ larger to make $\varphi(X) \leq f(v)$ false when it was true with fewer $1$'s in the input. The function $\varphi(X) \geq f(v)$ does not, in general, compute $1$ on $T_1$ and $0$ on $T_0$.

In fact, the test sets $T_1$ and $T_0$ are chosen precisely so that computing $1$ on $T_1$ and $0$ on $T_0$ with monotonicity means your function in precisely computing CLIQUE (they define the boundary of the $1$'s and $0$'s in the lattice of inputs), so these remarks imply that the Tardos function is the same as CLIQUE, which is clearly not true.

Yet, so many people -- and such knowledgeable people -- claim that the Tardos function provides an immediate counterexample, so there must be something I'm missing. Could you please provide a detailed explanation or proof for those of us who are interested parties but not quite on your level?

so these remarks imply that the Tardos function $f$ is the same as
  CLIQUE.

Short answer - NO.

It is only a monotone "clique-like": accepts all $k$-cliques, and rejects all  complete $(k-1)$-partite graphs. It can, however, accept some graphs rejected by CLIQUE: graphs $G$ with $\omega(G) < k$ but $\chi(G)\geq k$ (so-called "non-perfect" graphs). The paper by Grötschel,
Lovász and Schrijver implies that $f$ has a non-monotone circuit of polynomial size. But, according to Theorem 6 in the "proof", any monotone clique-like Boolean function requires non-monotone circuits of super-polynomial size.
So, one of these two papers must be wrong. The GLS-1981 paper stood for already > 35 years  ...

What Tardos does is the following. She starts from the graph function $\varphi(G):=\vartheta(\overline{G})$, where $\vartheta$ is the famous Lovász' theta-function. The fundamental fact is that the number
$\varphi(G)$ is sandwiched between the clique number and the chromatic number: $\omega(G)\leq \varphi(G)\leq \chi(G)$.
She then uses the fact that $\vartheta(G)$ can be approximated in polynomial time. Based on this, she defines a graph-function $\phi(G)$ with the following properties:

 Values of $\phi(G)$ can be computed in polynomial time (in the number $n$ of vertices).
 $\phi$ is monotone: adding edges can only increase its value.
 $\omega(G)\leq \phi(G)\leq \chi(G)$ holds for all graphs $G$.

Then (as Clement C. notes) she defines the desired monotone Boolean function $f$ as: $f(G)=1$ iff $\phi(G)\geq k$. By (1), the function has a (non-monotone) circuit of polynomial size. By (2), $f$ is a monotone Boolean function. By (3),
$f$ accepts all $k$-cliques, and rejects all complete $(k-1)$-partite graphs.

See here for technical details.


Typing inference as a map on abstract syntax trees Is there a reference that explains typing inference for Martin-Löf type theory as a computable map from abstract syntax trees of terms to abstract syntax trees of types? I don't want to identify non-identical judgmentally equal things.
The terms and the types are all defined in the empty context and we also include annotations for the variable types in lambda abstractions.
If there is such a map then is it true if a type is not in beta normal form then it has no terms in beta normal form map to it?

Type inference for dependent type theory is undecidable in general, so what you're asking for is impossible. However, it is possible to separate the syntax into inferrable terms and checkable terms, and implement inference for the inferrable fragment. This is the approach taken by bidirectional typechecking. The paper on LambdaPi by Andres Löh, Conor McBride and Wouter Swierstra describes a tutorial implementation of a dependent typechecker in this style. More advanced typecheckers for dependently typed languages typically rely on higher-order unification to infer the types for more expressions, a good example is the paper on Higher-order Dynamic Pattern Unification by Andreas Abel and Brigitte Pientka.
Regarding your second question, this claim is false: the conversion rule of dependent type theory says that a type is inhabited if and only if its normal form is inhabited. So a type such as (\(X:Type). x) Nat is not in beta normal form but is inhabited by the normal forms zero, suc zero, ...


Data for testing graph algorithms I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, weighted/unweighted) of the graphs in the source if they are known.

Check the following links for graph instances

DIMACS Graphs: Benchmark Instances and Best Upper Bounds
foo

Graph Coloring Instances

CLIQUE Benchmark Instances


Provably secure block ciphers I have read the paper by Anderson and Biham [0] describing the ciphers Bear and Lion, which combine a PRG and a hash function (each cipher does that in a different way). the authors proved that a key recovery attack on the ciphers would imply breaking the PRG and hash function used.
I also read the paper by Morin [1] in which he shows a man-in-the-middle attack on Bear and Lion, and also proposes a new cipher (Aardvark) of the same kind, immune to such attack.

Was there any attack on Aardvark?

And are there other block ciphers with proof of security?

The references are the following (sorry, I couldn't find exactly the publication years and conference names)

[0] Ross Anderson and Eli Biham. Two Practical and Provably Secure Block Ciphers: BEAR and LION.

[1] Pat Morin (1996). Provably Secure and Efficient Block Ciphers.

Construction of provably-secure block ciphers are considered in the following papers:

Pseudo-Random Permutation Generators and Cryptographic Composition by Luby & Rackoff. Full version of this paper can be found in How to Construct Pseudorandom Permutations from Pseudorandom Functions.
On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited by Naor & Reingold. This is in fact a revised version of the above ideas by Luby & Rackoff. Full version can be found in here.

The construct by Pat Morin and many others are reviewed in Building Secure Block Ciphers on Generic Attacks Assumptions.


Keyed queues with depth queries and delete I'm interested in a data structure (let's call it a DMV queue, or DMV for short) over keys (say, strings) with the following operations:

empty is a DMV containing no keys.
enqueue(q,k) adds the key k to the back of the DMV q, unless k is already in q, in which case it does nothing.
dequeue(q) deletes the key at the front of the DMV q, if one exists, and returns it.
delete(q,k) removes the key k from the DMV q.
depth(q,k) returns an natural number indicating the approximate number of keys between the key k and the front of the DMV q. Let $k_q$ denote the exact number of keys between k and the front of q. Then there must be some c such that for all k and q, $k_q/c$ < depth(q,k) < $ck_q$.

I think I know how to provide the queue operations in $\Theta(1)$ time and delete and depth in $\Theta(\lg n)$ time (all expected amortized). Is it possible to do better?

My proposed solution is as follows: Maintain a balanced tree with $O(1)$ operations at the ends. Nearly any finger tree will do. This tree will store the keys in queue order at its nodes. Also, annotate every non-spine node with its number of descendants.

Keep a hash table mapping keys to pointers to nodes in the tree.

To enqueue a key k, add k to the back of the tree. This invalidates $O(1)$ node pointers and creates $O(1)$ new node pointers, so we need only perform $O(1)$ hash table operations. Dequeue is similar.

To delete a key, we look it up in the hash table and find its location in the tree, then delete it from the tree. This takes $O(\lg n)$ time in the tree, and invalidates $O(\lg n)$ slots in the hash table. We must also maintain non-spine node size annotations in the tree, but this also only takes logarithmic time.

To find the depth of a key, we first annotate the spine nodes of the tree with their number of descendants. This takes $O(\lg n)$ time. We then look up the key in the hash table and find its location in the tree. We then follow parent pointers until we reach the root, summing the annotations at left siblings. Note that this is the exact depth.

Your solution can be modified to do everything in $O(1)$ amortized time. Instead of maintaining a balanced tree, just keep track of the number of successful enqueue operations (those in which something was actually added to the back of the queue) and attach that number to queue along with the item during a successful enqueue operation. To find the depth of a key, just take the difference between the number of successful enqueues when it was enqueued, and the number of successful enqueues when the item currently at the front of the queue was enqueued. Note that this gives exact depth.

If you're worried about storing excessively large values after many enqueue and dequeue operations, you can also keep track of the size of the queue and whenever the size is less than half the number of enqueues, re-number the number of enqueues for each entry to 1 through the size, and reset the number of enqueues to the size. Everything takes constant amortized time and each key takes at most one more bit than necessary to represent its depth at insertion.


Questions about regular languages and their sublanguages I am interested in the following questions and would be grateful if anyone could give me hints or point me to articles:

1) Given a regular language $L$, what are its regular sublanguages $L'\subseteq L$, i.e. how to enumerate all regular $L' \subseteq L$ for a given regular language $L$.

2) Could every regular sublanguage $L'$ of a regular language $L$ be written as $L' = L''\cap L$ with $L''$ regular

3) Given a arbitrary language, is it decidable if it is regular (of course one could compute it's syntactic monoid, but this computation could take on forever if the language is not regular)

3) It is undecidable to know whether a given context-free grammar generates a regular language. So even for context-free languages, you are in trouble.


What is DDL (Data Definition Language)? As a part of my curriculum, I am studying principles of DBMS from the book by Silberschatz and Korth.
A part of it is about Data Definition Language (DDL).

I understand, in normal terms, that DDL is any set of commands that modify the schema and not the actual data. That is the simple way of putting it. A certain paragraph in the book states, in addition to what I said, as below:

We specify the storage structure and access methods used by the database system
by a set of statements in a special type of DDL called a data storage and definition language.
These statements define the implementation details of the database schemas,
which are usually hidden from the users.

Can someone please explain to me what the first two lines mean ?
AFAIK, storage structure here would refer to the tables, in RDBMS, and access methods would refer to the views because they define what the user gets to see ?

Still, a simple explanation on this is welcome :)

Operations on a database are divided into DDL and DML.

DDL are operations that alter the structure of the database. This includes creating/dropping tables, constraints, indexes, packages, views, dblinks, adding or removing columns to a table, changing object names and so on.

DML are the operations that alter the data stored in the database. This includes inserting, deleting and updating rows to/from a table.


NTIME(n^k) ≠ DTIME(n^k) ? In "On determinism versus nondeterminism and related problems" (Proc. IEEE FOCS, pages 429–438, 1983), Paul, Pippenger, Szemerédi and Trotter proved that
$\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$.

This answers my question with k=1. Is anything known about a similar result for another fixed k?

No unconditional lower bound is known for any $k \geq 2$ in the multitape TM model (or any model stronger than it).

Ravi Kannan studied this problem in "Towards separating nondeterminism from determinism" (1984). In the process of trying to show $NTIME(n^k) \neq TIME(n^k)$ he managed to prove the following: there is some universal constant $c \geq 1$ such that for every $k$, $NTIME(n^k) \not \subseteq TIME-SPACE(n^k,n^{k/c})$. Here, $TIME-SPACE(n^k, n^{k/c})$ is the class of languages recognized by machines using time $n^k$ and space $n^{k/c}$ simultaneously. Clearly $TIME-SPACE(n^k,n^{k/c}) \subseteq TIME(n^k)$ but it is not known whether they are equal.

If you assume for some $k \geq 2$ that $NTIME(n^k) = TIME(n^k)$, you get interesting consequences. $P=NP$ is obvious, but it also implies that ${\sf NL} \neq {\sf P}$. This can be proved using an "alternation-trading" argument. Basically, for every $k$ and every language $L \in {\sf NL}$, there is a constant $c$ and some alternating machine that recognizes $L$ and makes $c$ alternations, guesses $O(n)$ bits per alternation, then switches to a deterministic mode and runs in $n^k$ time. (This follows, for example, from playing around with the constructions in Fortnow, "Time-Space Tradeoffs for Satisfiability" (1997).) Now if $TIME(n^k) = NTIME(n^k)$ then all these $c$ alternations can be removed with only a small amount of overhead, and you end up with a $TIME(n^k)$ computation that recognizes $L$. Hence ${\sf NL }\subseteq TIME(n^k) \neq {\sf P}$. Probably no such alternating simulation exists, but if you can rule it out, then you'll have the lower bound you seek. (Note: I believe that the above argument is also in Kannan's paper.)


An image coloring problem I have a large collection of microscopy images of cell cultures.  Each image consists of $10^{10} \times 10^{10}$ pixels.  These images have been "segmented", meaning that their pixels have been partitioned into disjoint sets (aka regions) corresponding either to the background or to individual cells.  I'm looking for a reasonably efficient algorithm to assign "colors" to these regions so that no two adjacent regions have the same color, and the number of colors used is "small".

In principle, 4 colors should do, but the problem of finding a 4-coloring for a partition of a plane region into disjoint subregions is NP-hard.

Nevertheless, this statement (and the 4-color problem in general) applies to a more general situation (e.g. arbitrarily complex shapes) than the one I am dealing with, so I'm alert to the possibility that some features of this special case may make the problem reasonably tractable in practice.

First, typically most of the cell regions are in fact isolated (i.e. they are surrounded entirely by background), so the problem of assigning a color to them is trivial.  Second, even when there are adjacent cell regions, these regions have relatively "well-behaved" shapes: they are basically roundish blobs, with no weird curlicues, etc.  In fact, any two pixels in a cell region are connected by a taxicab-path consisting of pixels all belonging to the region.  (By taxicab-path I mean one in which the Manhattan distance between adjacent pixels is always 1; i.e. each step along the path is either vertical or horizontal.)  Also, there is some leeway on the exact boundary of these regions, so it may be acceptable to modify the segmentation algorithm in such a way that the resulting regions are more easily colorable.

I have not found any prior work on coloring that attempts to exploit the features described above, so I thought I'd ask here.

It may very well be that these features of my special case do not result in any simplification of the 4-coloring problem, in which case an algorithm that can efficiently produce a 5-coloring, or even a 6-coloring, would be adequate.

Thanks in advance for your suggestions,

kj

I doubt your features simplify the problem at all, but it's very easy to 6-color a planar graph: find and remove a vertex of minimum degree, color the remaining graph recursively, put back the removed vertex, and give it a color that's different from all of its neighbors.

If you maintain an array indexed by vertex degree, with a list of the vertices with that degree in each array cell, and move the vertices to different lists when a removal causes their degrees to change, then you can find the minimum degree vertex by scanning the array from low to high degrees, and the overall algorithm will be linear time.

This also has the advantage that it automatically and quickly takes care of the completely surrounded regions: they have degree one, so they're dealt with first.

I think the best known time bound for 4-coloring planar graphs is still larger — more specifically, $O(n^2)$ from the work of Robertson, Sanders, and Thomas in the mid-1990s. But there are more complicated methods for 5-coloring planar graphs in linear time; one relevant reference is the paper by Hagerup, Chrobak, and Diks in ICALP 1987, and another is by Frederickson in IPL 1984.


Some good Theoretical Computer Science Journals I have been doing some work in Theoretical Computer Science(especially related to algorithms), and I wanted the publish some of my findings. Can someone please suggest some good journals or publications in the same area.

Apart from top conferences mentioned by @usul, I think Journal of the ACM (JACM) is a top journal in computer science, which also includes many excellent theoretical computer science papers. In addition, I read some papers published in Algorithmica. Also, just giving a reference, I find a link to some journals related to Discrete Mathematics (particularly refer to Theoretical Computer Science and Algorithms part), see http://www.math.iit.edu/~kaul/Journals.html.


Can type inference be classified in two groups: unification-based and control-flow-based? I recently came across the 1995 paper Safety analysis versus type inference (pdf link) by Palsberg and Schartzbach that contrasts unification-based type inference and static analysis methods based on control-flow analysis. According to the paper:

In unification based type inference each identifier is related to a type variable ranging over type schemes, such as $int$ and $\forall a b . a \rightarrow b$. In control-flow static analysis the identifiers get related to variables ranging over what primitive types and other values in the source program can flow into the identifier.
Unification-based type inference is "local" and can be performed one module at a time. Control-flow analysis tends to be global and require the whole program to be analyzed at once.
Damas-Milner unification is a linear time algorithm (for typical programs) while control-flow analysis tends to have worse case running times that are cubic or worse (and at least quadratic in practice).
Control-flow analysis can reason about program safety more precisely than unification-based inference (for example, it can detect some instances of dead code)

My question is: is this classification complete or are there other kinds of type inference that they did not mention?

Perhaps an even better way to see type inference is as a specialization of a single framework: Abstract Interpretation (abbreviated AI).  The hallmark of most unification-based type inference algorithms is that they generate the principal type for a term; translated into AI terms, this means that you never need to widen, nor do you need to go to power domains to find the answer.  Unification turns out to be the 'join' operation -- there is also a nice categorical interpretation of unification which is even more enlightening.

Several comments shed light on this as well: all algorithms can be better understood in terms of generating then solving systems of constraints.  Unification is indeed eager, and constraint-solving (and that includes control-flow based approaches) tend to be lazier.

Perhaps an even better way to see type inference is as an alternate interpreter for a program: rather than producing values, it produces types.  It is very easy to see type inference as a form a partial evaluation.  Perhaps an easy introduction to that circle of ideas is via Aaron Stump's A rewriting view of simple typing.


$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$ Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$  be constants. Are there disjoint subsets $V_1, V_2$ with $V = V_1 \cup V_2$ and $|V_i| \leq (1+\epsilon)|V|/2$ such that at most $M$ edges have an endpoint in both sets?

In Computers and Intractability (1979), Garey and Johnson claim this problem is $NP$-Complete (label: ND17) (they use an upperbound $B \geq 0$ requiring $|V_i| \leq B$, but for us that just means setting $\epsilon= 2B/|V|-1$).

Is anything known about the $NP$-Completeness of this problem for fixed values of $\epsilon$? For $\epsilon = 0$ we get the standard perfectly balanced bisection problem. For $\epsilon  = 1$ the problem is vacuously trivial. What if $\epsilon$ is some fixed constant in $(0, 1)$ (that is, not part of the input, but part of the problem definition).

The case where $\epsilon$ is a fixed constant in $(0,1)$ represents a partition that each part contains at least a constant fraction of the vertices. This was proven to be NP-complete by Wagner and Wagner. This is also known as balanced minimum cut problem. Note that $|V_i| \leq (1+\epsilon)|V|/2$ if and only if $|V_i| \ge (1-\epsilon)|V|/2$ for $\epsilon$ in $(0,1)$.

Wagner D., Wagner F. (1993) Between Min Cut and Graph Bisection. In: Borzyszkowski A.M., Sokołowski S. (eds) Mathematical Foundations of Computer Science 1993. MFCS 1993. Lecture Notes in Computer Science, vol 711. Springer, Berlin, Heidelberg


Why Reflexive Graphs for Parametricity? Looking at models of parametric polymorphism, I am curious why are
reflexive graph categories are used?

In particular, why do they not include relational composition?
In looking at the models, they all seem to support a natural notion of
relational composition:

$$ x(R;S)z \iff \exists y. xRy \wedge y S z$$

Most recent papers that use reflexive graphs seem to take this for
granted, and the only older paper I could find that discussed it was
"Relational Parametricity and Local Variables" by O'Hearn and Tennent
who say:

  One reason for not requiring composability is that, as is well known,
  composition is not preserved by logical relations at higher types.

And I'm not quite sure what this means, so my first question is what
is meant by this and hopefully a better reference on this question.

What I think this means is that for instance the exponential doesn't
necessarily preserve relational composition on the nose. In particular
we can't show $(R;R') \to (S;S') \equiv ((R \to S);(R' \to S'))$.
This means that the exponential doesn't extend to a functor on a
category of relations.

However, while I can't show the equivalence between the above
relations, I can certainly prove an inclusion $((R \to S);(R' \to
S')) \subset ((R;R') \to (S;S'))$, right?

Given $f((R \to S);(R' \to S')) h$, then there exists a $g$ of
appropriate type with $f(R\to S)g(R'\to S')h$, so given an $xRyR'z$, I
can show $f(x) S g(y) S' h(z)$.
Doesn't this means that the exponential does give me a lax functor,
which seems like a bad property to throw away?
So my second question is are there examples where the inclusion in
this direction is not provable, either?

In the months since I asked this question, I think I have found a sensible answer.

Often, the type of relations considered do not compose. For instance, if your notion of a relation $R : D \to E$ between $\omega$CPOs is an $\omega$-chain complete subset of $|D|\times |E|$, then the relation $R : \omega + 1 \to \mathbb{N}$ between the ordered naturals plus infinity $\omega+1$ and the flat CPO of naturals $\mathbb{N}$ given by $R(n,n)$ holds and nothing else, then $R$ is admissible, as is its converse, but the composite $R;R^T : \omega+1 \to \omega + 1$ is not chain-complete, since $n R;R^T n$ for every natural, but we don't have $\omega R; R^T \omega$.


Implications of proof of abc conjecture for cs theory What implications would a proof of the abc conjecture have for tcs?

http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/

Bhatnagar, Gopalan, and Lipton show that, assuming the abc conjecture, there are polynomials of degree $O((kn)^{1/2+\varepsilon})$ representing the Threshold-of-$k$ function over ${\mathbb Z}_6$. For fixed constant $k$, and $m$ which has $t$ prime factors, the abc conjecture implies a polynomial for Threshold-of-$k$ over $\mathbb Z_m$ with degree $O(n^{1/t+\varepsilon})$.

This presumably has relevance to the ${\sf TC^0}$ versus $\sf ACC^0[6]$ problem.


Which kind of grammar is the following? Let me define the following "grammar":

$$A_0 \leftarrow 1$$

$$A_{i+1} \leftarrow A_i \mid A_i \  K_{i+1} \mid A_i \ K_{i+1} \ A_i$$

where $1$ and $K_i$ are terminals (infinite amount of them: $K_1, K_2, \dots$ ), $A_0, A_1, \dots$ are non-terminals, $\mid$ means alternative, $\leftarrow$ defines a non-terminal, $i$ is an integer such that $i \geq 0$.

That is, it looks like a grammar composed of an infinite number of rules and terminals.

My questions are:

can I call such a construction a "grammar"?
in which grammar category can I include it?
have such structures been studied before, can anyone give links or bibliographic references?

Thanks a lot.

The simple answer would be that, having an infinite set of rules, this is not a grammar in the usual sense. Languages over infinite alphabets have been investigated, but usually using register automata rather than grammars.

That being said, you could treat the language as a limit (i.e. infinite union) of finitary languages defined by the "truncations" $G_i$ which you obtain by omitting all indices greater than $i$. I am unfortunately not familiar with research into such beasts.


LP formulation for if-conditions I have the following LP:

/* Objective function */
min: 1 w + 2 x + 0.5 y + z;

/* Variable bounds */
w + x <= T1;
w + y = U1;
x + z = U2;
T1 = 50;
U1 = 70;
U2 = 25;

In this case U1 + U2 > T1 and the optimal solution is y = 70 and z = 25. I want to enforce the condition that w and x variables be assigned values before assigning values to y and z. If U1 + U2 < T1, then I want only w and x to have values and y = z = 0. Is there a way to enforce such a constraint in an LP or an MILP?

Here are answers to your two questions. The details will depend upon which solver you are using:

Ensuring that $w$ and $x$ are assigned values before $y$ and $z$ can often be done programmatically by expressing the variable ordering used by the solver. That is, specifying which variables the solver tries to find values for first. This is possible, for example, in the choco solver (which is a constraint satisfaction problem (CSP) solver not one for LP or MILP), though I'm sure other solvers offer this possibility too.
The GNU Linear Programming Kit actually has an if-then-else construct for expressing conditionals. Look for "conditional" in the manual. You could wrap the clauses you are interested in in such a statement: if U1 + U2 < T2 then y = 0 and z = 0 else true. (Note that I haven't actually tried this, so the syntax may be wrong.)
An alternative answer to the second question takes advantage of the fact that $U1$, $U2$ and $T1$ are constants. Simply, have two variants of the LP problem, one for when $U1 + U2 < T1$ and one for when $U1 + U2 \ge T1$.


Decide if number is negative (in URM machine like language) So I'm learning to program in an assembly language for an abstract machine wich is very similar to an URM Machine.
An URM machine has 3 basic instructions (or 4 in some literature):
        To zero a register: Z(r)
        To increment a register: S(r)
        To Jump to a line or label if registers r1 and r2 contain the same value: J(r1,r2,l)
Now, my abstract machine is even weaker because, for jumping it only alows a comparison between a register and the literal 0.
To compensate it allows to assign any value to a register (not just zero as in the URM) and basic arithmetic operations.
Both machines allow an infinite number of registers.

I was able to write a program that successfully compares two positive numbers and returns the maximum.
Now I would like to make my program able to receive also negative numbers.

My question: How can I check if a number is negative? Is it even possible with only these instructions?

I confess that I'm not very clever with this kind of low level languages...

My maximum program follows: (input goes on r1 and r2 and output comes on r3)

maximo(){
    r5 := r1 - r3
    jump (r5,0,maxr2)

    r5 := r2 - r4
    jump (r5,0,maxr1)

    r3 := r3 + 1
    r4 := r4 + 1
    jump (r1,r1,maximo)
}

maxr1(){
    r3 := r1
}

maxr2(){
    r3 := r2
}

Thank you!

Initialise $x \gets v$ and $y \gets -v$. Then increment both $x$ and $y$ in parallel until one of them is equal to 0.


NP-complete graph property that is hereditary, but not additive? A graph property is called hereditary if it closed with respect to deleting vertices (i.e., all induced subgraphs inherit the property). A graph property is called additive if it is closed with respect to taking disjoint unions.

It is not hard to find properties that are hereditary, but not additive. Two simple examples:

$\;\;\;$ (1) The graph is complete.

$\;\;\;$ (2) The graph does not contain two vertex-disjoint cycles.

In these cases it is obvious that the property is inherited by induced subgraphs, but taking two disjoint graphs that have the property, their union may not preserve it.

Both of the above examples are polytime decidable properties (although for (2) it is somewhat less trivial). If we want harder properties, they could still be created by following  the pattern of  (2), but replacing the cycles with more complicated graph types. Then, however, we can easily run into the situation where the problem does not even remain in $NP$, under standard complexity assumptions, such as $NP\neq coNP$. It appears less trivial to find an example which stays within $NP$, but it is still hard.

  Question: Do you know a (preferably natural)  $NP$-complete graph property that is hereditary, but not additive?

I think the $k$-clique cover problem, which asks whether there exists a partition of the vertices in $k$ sets such that each set induces a clique, has the desired properties.

Clearly, taking induced subgraphs can't make the minimum size of such partition increase. On the other hand, when you take the disjoint union of two graphs, you have to take the union of the partition into cliques of each one.


What games best represent well-known computer science problems? I heard that Clue is a board game that is related to the NP-complete traveling salesman problem.   What are other games that relate to important computational problems?

If by 'show computational theories in them' you mean correspond to complexity classes or fit nicely within complexity classes, then you first have to generalize the game to depend on some parameter $n$. For instance, for a game of Chess with a clock (and maybe a 50-move no checkmate rule) on an 8-by-8 board there are only a finite number of possible games. Thus, everything about the game is solvable in $O(1)$.

To overcome this, complexity theorists usually define a generalized game. So for instance a variant of chess on $n$-by-$n$ boards, then standard complexity questions can be asked. In that case, a lot of the 'fun' two player games become PSPACE-complete or EXPTIME-complete. For instance Reversi and Hex are PSPACE-complete and Chess, Go, and Chinese Checkers are EXPTIME-complete. You can learn more on wikipedia

In terms of NP-completeness, sometimes end-games become NP-complete. In particular, in a really fun game called phutball deciding if a player has a win in one move is NP-complete. Solving who will win the game in general is PSPACE-hard given arbitrary initial configuration


complexity of the half language For any language $L$ over $\Sigma^*$, define
$$L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.$$
In words, $L_{1/2}$ consists of all $x$ for which there is a $y$ of equal length such that $xy\in L$.

An exercise in Sipser's book asks to show that $L_{1/2}$ is regular whenever $L$ is. I have seen two distinct solutions, and both involve an exponential blow-up of states.

Question: can anyone construct a family of languages $\{L_n\}$ such that the canonical automaton for $(L_n)_{1/2}$ is significantly (say, exponentially) larger than that for $L$? My best efforts so far only increase the state size by $+1$!

See Mike Domaratzki's paper, State complexity of proportional removals

http://dl.acm.org/citation.cfm?id=782471

http://www.cs.umanitoba.ca/~mdomarat/pubs/sc_jalc.ps


Find minimum number of transformations to transform from input to target string Given that I have an input string, for example:  aab
And I am given a target string, for example: bababa
And then I am given a set of transformation rules. For example:

ab -> bba
b -> ba

There can be N rules.
The characters for the input and output string don't have to be just a and b, they can be any characters.

How could I do an algorithm that would find the minimum number of transformations that would need to be applied in the input string to get the target string.

In this example, for example, the number would be 3.  Because we would do:

1 - Apply rule 1 (abba)
2 - Apply rule 1 again (bbaba)
3 - Apply rule 2 (bababa)

It could happen that given an input and a target, there is no solution and that should be noticed too.

Also, it can be that the target string is shorter than the input string.

I am pretty much lost in strategies on doing this.  It comes to my mind creating an automata but I am not sure how would I apply in this situation.  I think is an interesting problem and I have been researching online, but all I can find is transformations given rules, but not how to ensure it's a minimum.

Thanks

EDIT

As noted by usul, my previous answer is too broad, so these are some additional notes with personal ideas (so it is now more like an extended comment, than an answer):

If the given grammar is context sensitive, the alphabet has size >= 2 and there are no limits in the number of transformations, then even the problem of deciding if the grammar generates the target string is undecidable. You can easily find a grammar that simulates a NTM; as pointed out by Jeffe Markov algorithms are Turing complete, so given a TM and a string w you can build a grammar and a source string that generate a target string iff TM halts on w. So finding the minimum is undecidable, too.

If you put a limit in the number of transformations (polynomial), then the problem of deciding if the grammar generates the target string is PSPACE complete, and the problem of finding the minimum number of transformations is surely harder.

If the number of transformations is fixed, I think that the the problem is NP complete (I've a fuzzy idea of a quick reduction from monotone NAE-3SAT)

I leave the previous answer below.

The problem of finding the smallest CFG grammar  that generates a given string (also known as Minimum Grammar Compression or MGC) is NP-complete (J. Storer, "NP-completeness results concerning data compression", 1977).

I think that the complexity of the problem when the alphabet is restricted to $\{0,1\}$ (2-MGC) is still unknown.

If you switch to context sensitive grammars (LBAs) then you can look at resource-bounded Kolmogorov complexity. Unlike the unbouded Kolmogorov complexity, finding the smallest program that computes a given string is decidable, but we are obviously nearby intractability. There is a lot of reasearch on the subject (and many open problems); for example consider a binary string of length $2^n$ that represents the truth table of a boolean function $f$ and an integer $s$; the complexity of deciding if there is a boolen circuit of size at most $s$ that computes $f$ is unknown (probably not in $P$ but also unlikely to be NP-complete). Here it is a simple introduction and a very nice paper on the power of random strings.


The complexity of comparing a power to some threshold Consider the following simple problem:

  Given fractions $a/b$, $c/d$ with $a/b<1$ and $c/d<1$, and natural
  number $e$, both encoded in binary (so the problem size is
  $\log(a)+\log(b)+\log(c)+\log(d)+\log(e)$, decide whether
  $$(\frac{a}{b})^e \geq \frac{c}{d}$$.

What's the precise complexity of this problem? Note that one can simply compute $(\frac{a}{b})^e$, as it might require $e\cdot (\log(a)+\log(b))$ bits to store.

Any upper/lower bound? Do I miss something here?

The problem is decidable in polynomial time (in fact, in uniform $\mathrm{TC}_0$). We can recast the question as follows: given positive integers $a,b,c,d,e$, find the sign of
$$\Lambda=e\log(a/b)-\log(c/d).$$
First, note that we can test whether $\Lambda=0$: if we assume w.l.o.g. that $\gcd(a,b)=\gcd(c,d)=1$, then $da^e=cb^e$ implies $a^e\mid c$ and $b^e\mid d$; in particular, apart from the trivial case $a=b=1$, equality can hold only if $e\le\max\{\log c,\log d\}$, in which case we can evaluate $a^e,b^e$ in polynomial time.

Likewise, we can rule out the case when $(a/b)^{e_1}=(c/d)^{e_2}$ for some positive integers $e_1,e_2$. The argument above shows that if this is the case, then $e_1,e_2\le\max\{\log a,\log b,\log c,\log d\}$, hence we can find $e_1,e_2$ by brute force in polynomial time, and then it suffices to compare $e$ with $e_1/e_2$.

Thus, suppose $a/b$ is not a rational power of $c/d$, which implies $\Lambda\ne0$. Write $\alpha_1=a/b$, $\alpha_2=c/d$, $\lambda_1=\log\alpha_1$, $\lambda_2=\log\alpha_2$, $\beta_1=e$, $\beta_2=-1$. Note that the logarithmic height $h(\alpha_1)=\max\{\log a,\log b\}$, $h(\alpha_2)=\max\{\log c,\log d\}$, and $\lambda_1,\lambda_2$ are linearly independent over $\mathbb Q$. By some version of Baker’s theorem (e.g., the “explicit result by Baker and Wüstholz” in http://en.wikipedia.org/wiki/Baker%27s_theorem#Statement), we have

$$\log\lvert\Lambda\rvert>-Ch(\alpha_1)h(\alpha_2)\log\beta_1$$

for some constant $C$ (note that in the statement given in the link, we have $n=2$ and $d=1$, hence $C$ is really independent of the input data). The number on the right-hand side is polynomial in the length of the input, and it thus suffices to approximately evaluate $\Lambda$ with polynomially many bits of precision, which can be done by standard numerical algorithms in polynomial time.

(If you want to look for more information, the keyword is “linear forms in logarithms”.)


EXPSPACE-complete problems I am currently trying to find EXPSPACE-complete problems
(mainly to find inspiration for a reduction), and
I am surprised by the small number of results coming up.

So far, I found these, and I have trouble expanding the list:

universality (or other properties) of regular expressions with exponentiation.
problems related to vector addition systems
unobservable games (see for instance this blog)
some fragment of FO-LTL, in On the Computational Complexity of Decidable Fragments of First-Order-Linear Temporal Logics

Do you know other contexts when EXPSPACE-completeness appears naturally?

Extending the example pointed out by Emil Jerabek in the comments, $\mathsf{EXPSPACE}$-complete problems arise naturally all over algebraic geometry. This started (I think) with the Ideal Membership Problem (Mayr–Meyer and Mayr) and hence the computation of Gröbner bases. This was then extended to the computation of syzygies (Bayer and Stillman). Many natural problems in computational algebraic geometry end up being equivalent to one of these problems. Also see the Bayer–Mumford survey "What can be computed in algebraic geometry?"


Probabilistic and quantum analog of $FP$ and $FNP$? Is there any analog of the computational classes $FP$ and $FNP$ with probabilistic or quantum Turing machines? If so, what are the relation with other computational classes?

I hope the following partially answers your question. I've never seen this  observation published anywhere (please correct me if I'm wrong).

First of all, FQMA - a quantum analog of FNP - was defined: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fqma

One of the compelling reasons to define the complexity class NP is that there is a decision to search reduction: polynomial access to an oracle that solves NP-Complete problems allows you to search for a solution of any problem in FNP in polynomial time.

A decision to search reduction is not known between QMA and FQMA . For example, access to an oracle for the Local Hamiltonian problem is not known to be sufficient to efficiently construct a ground state.

Another related (although, not directly related to your question) reduction which is known for many classical NP problems, but not for QMA problems is downward self reducibility:
A language L is downward self reducible if there is a cook reduction from L to itself such that the queries are shorter than the original input. For example, given a Local Hamiltonian H with m terms, decide whether its minimal energy is below a or above b (where b-a>1/poly) by asking questions regarding Hamiltonians which have m-1 terms or less. Many decision to search reductions have this additional property.


A curious Wilf equivalence class of function compositions I was enumerating pairs of functions from a size $n$ set into itself, and ran into these three relations which all generate the same integer sequence starting at index zero:  1, 1, 6, 87, 2200, 84245. $$f(f(f(x))) = g(f(x))$$
$$f(g(x)) = g(x)$$
$$f(g(x)) = g(g(x))$$

There is a deep theorem on trees in there but it isn't jumping out at me. Anyone have a reference in the literature?

More generally, you can consider the identity
$$ f(g(x)) = g^{(n)}(x), $$
which generalizes your identities, in which $n=3,1,2$ (respectively).

For a given function $g$, this identity states that $f$ needs to have given values on $\operatorname{ran} g$, and is free otherwise. The specific value of $n$ doesn't matter, in fact we can put whatever we want on the right-hand side as long as it doesn't involve $f$. Using inclusion-exclusion, you can come up with an explicit formula for the number of solutions, but I'll leave that to you.


Eliminating cofix in Coq proof While trying to prove some basic properties using coinductive types in Coq, I keep running into the following problem and I cannot get around it. I've distilled the problem into a simple Coq script as follows.

The type Tree defines possibly infinite trees with branches labelled with elements of type A. A branch need not be defined for all elements of A. The value Univ is the infinite tree with all A branches always defined. isUniv tests whether a given tree is equal to the Univ. The lemma states that Univ does indeed satisfy isUniv.

Parameter A : Set.

CoInductive Tree: Set := Node : (A -> option Tree) -> Tree.

Definition derv (a : A) (t: Tree): option Tree :=
  match t with Node f => f a end.

CoFixpoint Univ : Tree := Node (fun _ => Some Univ).

CoInductive isUniv : Tree -> Prop :=
  isuniv : forall (nf : A -> option Tree) (a : A) (t : Tree),
    nf a = Some t ->
    isUniv t ->
    isUniv (Node nf).

Lemma UnivIsUniv : isUniv Univ.
Proof.
  cofix CH.    (* this application of cofix is fine *)
  unfold Univ.

Admitted.

At this point I give up the proof. The current goal is:

CH : isUniv Univ
============================
isUniv (cofix Univ  : Tree := Node (fun _ : A => Some Univ))

I do not know which tactic to apply to eliminate the cofix in the goal to produce (Node something) so that I can apply isuniv.

Can anyone help prove this lemma?
What are the standard ways of eliminating cofix in such a situation?

(* I post my answer as a Coq file. In it I show that supercoooldave's
   definition of a universal tree is not what he intended. His isUniv
   means "the tree has an infinite branch". I provide the correct
   definition, show that the universal tree is universal according to
   the new definition, and I provide counter-examples to
   supercooldave's definition. I also point out that the universal
   tree of branching type A has an infinite path iff A is inhabited.
   *)

Set Implicit Arguments.

CoInductive Tree (A : Set): Set := Node : (A -> option (Tree A)) -> Tree A.

Definition child (A : Set) (t : Tree A) (a : A) :=
  match t with
    Node f => f a
  end.

(* We consider two trees, one is the universal tree on A (always
   branches out fully), and the other is a binary tree which always
   branches to one side and not to the other, so it is like an
   infinite path with branches of length 1 shooting off at each node.  *)

CoFixpoint Univ (A : Set) : Tree A := Node (fun _ => Some (Univ A)).

CoFixpoint Thread : Tree (bool) :=
  Node (fun (b : bool) => if b then Some Thread else None).

(* The original definition of supercooldave should be called "has an
   infinite path", so we rename it to "hasInfinitePath". *)
CoInductive hasInfinitePath (A : Set) : Tree A -> Prop :=
  haspath : forall (f : A -> option (Tree A)) (a : A) (t : Tree A),
    f a = Some t ->
    hasInfinitePath t ->
    hasInfinitePath (Node f).

(* The correct definition of universal tree. *)
CoInductive isUniv (A : Set) : Tree A -> Prop :=
  isuniv : forall (f : A -> option (Tree A)),
    (forall  a, exists t, f a = Some t /\ isUniv t) ->
    isUniv (Node f).

(* Technicalities that allow us to get coinductive proofs done. *)
Definition TT (A : Set) (t : Tree A) :=
  match t with
    | Node o => Node o
  end.

Lemma TTid (A : Set) : forall t: Tree A, t = TT t.
  intros A t.
  destruct t.
  reflexivity.
  Qed.

(* Thread has an infinite path. *)
Lemma ThreadHasInfinitePath : hasInfinitePath Thread.
Proof.
  cofix H.
  rewrite TTid.
  unfold TT.
  unfold Thread.
  (* there is a path down the "true" branch leading to Thread. *)
  apply haspath with (a := true) (t := Thread).
  auto.
  auto.
Qed.

(* Auxiliary lemma *)
Lemma univChildNotNone (A : Set) (t : Tree A) (a : A):
  isUniv t -> (child t a <> None).
Proof.
  intros A t a [f H].
  destruct (H a) as [u [G _]].
  unfold child.
  rewrite G.
  discriminate.
Qed.

(* Thread is not universal. *)
Lemma ThreadNotUniversal: ~ (isUniv Thread).
Proof.
  unfold not.
  intro H.
  eapply univChildNotNone with (t := Thread) (a := false).
  auto.
  unfold Thread, child.
  auto.
Qed.

(* Now let us show that Univ is universal. *)
Lemma univIsuniv (A : Set): isUniv (Univ A).
Proof.
  intro A.
  cofix H.
  rewrite TTid.
  unfold TT.
  unfold Univ.
  apply isuniv.
  intro a.
  exists (Univ A).
  auto.
Qed.

(* By the way, it need not be the case that a universal tree has
   an infinite path! In fact, the universal tree of branching type
   A has an infinite path iff A is inhabited. *)

Lemma whenUnivHasInfiniteBranch (A : Set):
  hasInfinitePath (Univ A) <-> exists a : A, True.
Proof.
  intro A.
  split.
  intro H.
  destruct H as [f a t _].
  exists a.
  trivial.
  intros [a _].
  cofix H.
  rewrite TTid.
  unfold TT.
  unfold Univ.
  apply haspath with (t := Univ A); auto.
Qed.