Neural Networks: what's the point of learning features that don't linearly separate? Unless I'm mistaken, deep neural networks are good for learning functions that are nonlinear in the input.

In such cases, the input set is linearly inseparable, so the optimisation problem that results from the approximation problem is not convex, so it cannot be globally optimised with local optimization. Support Vector Machines (try to) get around this by choosing features such that the projection of the input space into the feature space is linearly separable, and we have a convex optimisation problem once again.

I don't suppose that a deep neural network always learns features that make the input set linearly separable in feature space. So what's the point in it learning features?

Indeed, one would like to construct features that make classes linearly separable. However, what patterns exactly should be linearly separable?

It is easy to make patterns in training set linearly separable by greatly increasing feature space dimensionality. However, this will not necessarily imply good generalization (correct classification of new patterns).  Quite opposite, it can lead to overfitting. Thus, it is problematic to use the criterion of linear separability directly to select good nonlinear features for classification.

Deep learning networks adopt different approach. They try to select features with good generalization of patterns irrelative to the classification task. Thus, “useful” nonlinear features are selected without danger of overfitting. Indeed, it doesn’t necessarily ensure linear separability of classes, but it makes sense from induction point of view. If one extract statistically independent factors from initial features, in which these factors are mixed, it will be easier to solve any further classification task.


Number of words of length n in a context-free language Denote by $w_n$ the number of words of length $n$ in a (possibly ambiguous) context-free language.

  What is known about $w_n$?

I'm sure this has been studied a lot, but I couldn't find anything at all on it.

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:

Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.

This has been shown for instance in:

Roberto Incitti:
"The growth function of context-free languages"
Theoretical Computer Science 255 (2001), Pages 601-605
Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64 (2002), Pages 308-310

And for a given context-free grammar, one can decide in polynomial time whether the generated language has polynomial or exponential growth:

Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
"Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time.
International Journal of Foundations of Computer Science 21 (2010), Pages 597-618


CSPs with unbounded fractional hypertree width At SODA 2006, Martin Grohe and D$\acute{\rm a}$niel Marx's paper "Constraint solving via fractional edge covers" (ACM citation) showed that for the class of hypergraphs $H$ with bounded fractional hypertree width, CSP($H$) $\in PTIME$.

Definitions, etc.

For a great survey of standard tree decompositions and treewidth, see here (Thanks ahead of time, JeffE!).

Let $H$ be a hypergraph.

Then for a hypergraph $H$ and a mapping $\gamma : E(H) \rightarrow [0,\infty)$,

$B(\gamma) = ${$v \in V(H) : \sum_{e \in V(H), v \in e} \gamma(e) \ge 1$}.

Additionally, let weight($\gamma$) = $\sum_{e \in E}\gamma(e)$.

Then a fractional hypertree decomposition of $H$ is a triple $(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$, where:

 $(T, (B_t)_{t \in V(T)})$ is a tree decomposition of $H$, and
 $(\gamma_t)_{t \in V(T)}$ is a family of mappings from $E(H)$ to $[0, \infty)$ s.t. for every $t \in V(T), B_t \subseteq B(\gamma_t)$.

Then we say the width of $(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$ is $\max${weight$(\gamma_t), t \in V(T)$}.

Finally, the fractional hypertree width of $H$, fhw($H$), is the minimum of the widths over all possible fractional hypertree decompositions of $H$.

Question

As stated above, if the fractional hypertree width of the underlying graph of a CSP is bounded by a constant, then there is a polynomial time algorithm to solve the CSP. However, it was left as an open problem at the end of the linked paper whether there were any polynomial-time solvable families of CSP instances having unbounded hypertree width.
(I should also point out, this question is completely resolved in the case of bounded vs. unbounded treewidth (ACM citation) under the assumption that $FPT \ne W[1]$.) Since there's been some time since the first-linked paper, plus I'm relatively unaware of the general state of this sub-field, my question is:

Is anything known about the (in)tractability of CSPs over graphs with unbounded fractional hypertree width?

You linked to two papers, both with conjectures.  I presume you mean Grohe's 2007 conjecture.

This question was answered in 2008:

  Theorem 5. CSP(C$_0$,_) is in NP, but neither in P nor NP-complete (unless P = NP).  Moreover, the set C$_0$ can be decided in deterministic polynomial time.

Manuel Bodirsky and Martin Grohe, Non-dichotomies in Constraint Satisfaction Complexity, ICALP 2008.  doi:10.1007/978-3-540-70583-3_16 (PDF)

The idea is to blow holes in the instance sizes of CLIQUE, by the same delayed diagonalization technique introduced by Ladner for his theorem.  Note that the set C$_0$ contains arbitrarily large cliques, and the fractional hypertree width of an $n$-clique is $n/2$.  So it is possible to have CSPs of the form CSP(A,_) that are of intermediate complexity, where A has unbounded fractional hypertree width.  This answers Grohe's conjecture in the negative.

At the same conference Chen, Thurley, and Weyer had a paper with a similar result, but that required strong embeddings so technically wasn't of the right form for the conjecture.

Yijia Chen, Marc Thurley, and Mark Weyer, Understanding the Complexity of Induced Subgraph Isomorphisms, ICALP 2008.  doi:10.1007/978-3-540-70575-8_48 (PDF)

Finally, any class of CSP instances can be transformed into a representation with worst-case fractional hypertree width.  In many cases this transformation is polynomially bounded in size and can be done in polynomial time.  This means that it is easy to generate CSPs with unbounded fractional hypertree width, even modulo homomorphic equivalence.  These CSPs are not going to be of the form CSP(A,_) since the target structures are special, but they do provide a neat reason why the CSPs defined by restricting just the source structures are not all that interesting: it is often just too easy to hide the tree-like structure of a CSP instance by changing the representation so that the source structure has large width.  (This is discussed in chapter 7 of my thesis.)


3-coloring of specific planar graphs Consider any tree $T$ with $n>2$ vertices and $k$ leaves. Let's denote $G(T)$ a graph constructed from $T$ by connecting its leaves into $k$-cycle in such way that $G(T)$ is planar.

In case I wasn't clear enough I'll give an example:

Let T be a tree with edges E(T) = { {1,2}, {2,3}, {2,4}, {4,5} } and then E(G(T)) = sum of the sets: E(T) and { {1,5}, {5,3}, {3,1} }, since we are connecting leaves 1,5,3 into a cycle.

And I believe that if $T$ is not $K_{1,2r+1}$ then $G(T)$ is $3$-colorable, but my problem is I don't know how to prove it. I was trying to come up with an algorithm that starts with $2$-coloring of a tree and then with third color fix collisions on a cycle, but this led me to nowhere.

To prove that every tree with two or more internal nodes gives you a 3-colorable graph, use induction on the number of nodes of the tree. If you orient the tree from an arbitrarily chosen root node, there always exists an internal node $v$ whose children are all leaves. Now split into cases:

If $v$ has one child, then the graph can be reduced down to nothing by repeatedly removing vertices of degree at most two, and three-colored by reinserting the vertices in the reverse order and giving them a color distinct from their two neighbors.
If $v$ has three or more children, then the tree can be reduced in size by removing two consecutive children, forming the graph by connecting the remaining leaves into a cycle, and then coloring the smaller graph. The remaining children of $v$ must alternate in color and reinserting the removed children maintains the same alternation.
If $v$ has exactly two children, and there are three or more internal nodes, then remove $v$ and its two children from $T$, form  the graph by connecting the remaining leaves into a cycle, and then color it. Let $p$, $q$, and $r$ be the parent of $v$, the node to the left of $v$'s left child in the leaf cycle, and the node to the right of $v$'s right child in the leaf cycle; $q$ and $r$ are adjacent in the smaller graph, so must have different colors. There are two subcases. If $p$, $q$, and $r$ use only two colors among them, then the two children of $v$ can be colored in alternation with $q$ and $r$ using the same two colors, and $v$ can be given the remaining third color. On the other hand, if $p$, $q$, and $r$ use three different colors, then $v$ can be given $q$'s color, the left child of $v$ can be given $r$'s color, and the right child of $v$ can be given $p$'s color.
In the remaining base case, $T$ has exactly two internal nodes, each adjacent to two leaves. The graph is the graph of a triangular cylinder, which can be three-colored.

Incidentally, if $T$ has no degree two vertices, then $G(T)$ is called a Halin graph; with or without the degree two restriction, it has bounded treewidth, so an alternative method for finding an optimal coloring in linear time is to use dynamic programming. However, this method does not tell you ahead of time which trees require only three colors.


Analysis of the synergy of two algorithms in comparison to their simulation in parallel Consider the following two algorithms for searching in a sorted array of $n$ elements:

A) interpolation search and binary search simulated in parallel, and

B) search through alternating interpolation steps and binary steps.

Both algorithms are of worst case complexity $2\lg n+1$ (and average complexity $2\lg\lg n$ for a reasonable distribution). Is there a complexity model which permits to separate those two algorithm (expressing when one is better than the other)? In particular, is there an example where the simulation in parallel is outperforming the mixed search algorithm?

---Some Basic Background---

1) Interpolation for element $x$ in a sorted array $T$ between position $i$ and $j$ makes a comparison at position $g=i+(j-i)/(T[j]-T[i])*(x-T[i])$, and reduces the search interval to $[i,g]$ or $]g,j]$ according to the result (as opposed to binary search, which compares $x$ to the element at position $(i+j)/2$.)

2) The worst case complexity of the search algorithm simulating in parallel binary search and interpolation search is $2\lg n+1$: Given two algorithms $A$ and $B$ of worst case complexities $f(n)$ and $g(n)$, the worst case of the parallel simulation of $A$ and $B$, stopping as soon as one terminates, has complexity $2\min\{f(n),g(n)\}\in O(\min{f(n),g(n)})$. The complexity of the search alternating steps from binary search and interpolation search is $2\lg n+1$ as well, because the search interval is at least reduced by two every two comparison.

In Willard's Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time, he references a preliminary version (of the linked paper) entitled "Surprisingly efficient search algorithms for nonuniformly generated files" appearing at the 21st Allerton Conference on Communication Control and Computing in 1983, pp. 656-662. I can't find this paper on the web, but in the later (linked) version above, he says that the older paper shows that the synergy between binary and interpolation search can reduce search time to $o(\log n)$ for certain non-uniform distributions of record keys.

Specifically, call a PDF $\mu$ regular if there are $b_1, b_2, b_3, b_4$ such that $\mu(x) = 0$ for $x < b_1$ or $x > b_2$ and $\mu(x) \geq b_3 > 0$ and $|\mu\prime(x)| < b_4$ for $b_1 \leq x \leq b_2$. For data produced by regular PDFs, interpolation search takes $\Omega(\log n)$ expected time, while binary search takes $\Theta(\log n)$ expected time. Interleaving them, however, takes $O(\sqrt{\log n})$ expected time.

You may also be interested in Willard and Reif's "Parallel processing can be harmful: The unusual behavior of interpolation search", which shows that "parallel processing before the literally last iteration in the search of an unindexed ordered file has nearly no usefulness".


Is APX contained in NP? A problem P is said to be in APX if there exists some constant c > 0 such that a polynomial-time approximation algorithm exists for P with approximation factor 1 + c.

APX contains PTAS (seen by simply picking any constant c > 0) and P.

Is APX in NP? In particular, does the existence of a polynomial-time approximation algorithm for some approximation factor imply that the problem is in NP?

APX is defined as a subset of NPO, so yes, if an optimization problem is in APX then the corresponding decision problem is in NP.

However, if what you're asking is whether an arbitrary problem must be in NP (or NPO) if there is a poly time O(1)-approximation, then the answer is no.  I don't know of any natural problems that serve as a counter-example, but one could define an artificial maximization problem where the objective is the sum of two terms, a large term that is easily optimized in P, and a much smaller term that adds a small amount if part of the solution encodes an answer to some hard problem (outside of NP).  Then you could find, say, a 2-approximation in poly time by concentrating on the easy term, but finding an optimal solution would require solving the hard problem.


When are more publications less? Are there cases where extra publications can hurt your record?

This is avoiding the obvious cases where you publish incorrect, or controversial results. Also avoiding the case of finite-time: you only have so much time to think and write, so writing a paper might cause you to lose time on another project.

An example use-case might be: you are aiming for a position in theoretical computer science, but often publish in non-theoretical areas which might be under the broader CS canopy or maybe even completely unrelated to CS. On the one hand, this can show broad interests and breadth. On the other hand, this could show a lack of focus, opportunism, or lack of commitment to the field.

Can you avoid the problem by simply listing 'selected publications' on your CV that tailors to the specific position, or will the hiring committee always google scholar you? If so, when should you consider not publishing or publishing under pseudonym (or alternative spelling of name)?

At Aaron's suggestion, here is my second comment from the complexity blog, warts and all.  Italics are (linked) quotes from earlier comments.

  I've seen candidates publishing more than 15 papers a year and then a question was asked whether these 15+ papers are good or not.

  ...because more often than not, the answer is no. Most of the
  uncharacteristically long CVs I've seen in hiring committee meetings
  are chock full of crap. Or they're good in the aggregate, but appear
  to advance their research in too many incremental steps. Even if there
  are diamonds in the slurry, I have to ask—why did they publish all
  that other stuff? Why didn't they make one big splash instead of this
  long, meager dribble? Did they not notice that most of their papers
  were weak? Are they publishing so many papers to advance the state of
  the art, or only to make their CV longer? Are they going to value
  quantity over quality in their own PhD students? Or am I in fact
  witnessing a miracle candidate?

  Despite what Dr. Anonymous two steps above me suggests, these are not irrelevant
  issues. I don't want my department associated with someone known to
  publish reams of crap, or who wastes my colleagues' time reviewing
  tons of incremental papers, or who thinks they're Thor's gift to
  computer science when they're not, or who tries to convince PhD
  students that their CVs need to look like the Manhattan Yellow Pages.
  Those aren't the people I want to work with; that's not the culture I
  want to work in; that's not (in my opinion) what's best for the
  Advancement of Knowledge™.

  And notice I said “suspicious”, not “deadly”. Of course we read
  recommendation letters and search citation indices and even (gasp)
  read the actual papers. Sometimes that's enough to allay my
  suspicions; yes, there are miracle candidates. But just often enough
  for me to keep my suspicions, they're proven right.

  So where exactly does the long CV comes in as a negative, rather than
  the fact that the person does not have significant contributions?

  The problem isn't just that they may not have significant
  contributions, but also that they may have too many not-significant
  contributions. (See my
  earlier comment about "max" vs "sum".)

  Sounds like you guys are rationalizing a case of paper envy, rather
  than following sound academic decisions.

  What the hell is “paper envy”? Result envy or impact envy or
  reputation envy I could get behind, but paper envy? Really? Since when
  are papers something to be envious about?

  Also: Not publicly taking credit for your opinions? Deeply suspicious.


Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time? We know that MIS is hard to approximate within a $n^{1-\epsilon}$ factor in polynomial time and that it is $W[1]$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$ is the size of the independent set).

What about approximating it in FPT time?

  Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?

What about other $f(k)$s?

In the paper: Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses, the authors prove the following bound for Maximum Independent Set:

  For any $r$ larger than some constant, any $r$-approximation algorithm for the maximum independent set problem must run in at least $2^{n^{1-\epsilon}/r^{1+\epsilon}}$ time. This nearly matches the upper bound of $2^{n/r}$.


research on systematically attacking multiple instances of undecidable problems this question is inspired by a recent popular question [1] on a boundary relating to decidable and undecidable problems (ie open problems in this area), a sort of counterpoint.

there are at least some papers of a type that attack multiple instances of undecidable problems. each instance of the general problem is not known a priori to be decidable or undecidable, and the paper describes strategies/techniques for identifying/sorting some into decidable cases, and provides algorithms which decide the problem if it is found to be among the decidable cases.

  what are papers of this genre, systematically attacking multiple instances of undecidable problems?

[1] A simple problem whose decidability is not known / Reyzin, tcs.se

Let's say an algorithm A solves a "special case" of the decision problem L if on input x, $A(x)$ always either outputs the correct answer $L(x)$, or outputs "?".
These algorithms (which may be randomized) are sometimes called "errorless heuristics" and have been studied in complexity theory, esp. average-case complexity; see e.g. this paper of Watson and references therein.

A basic question you can ask about a very difficult decision problem is whether it contains any nontrivial easy cases.  E.g. if L is decidable, is there any (deterministic) errorless heuristic A for L that solves $L(x)$ on infinitely many inputs?  This has been explored in the notion of immunity (along with co-immunity, bi-immunity, simplicity and others) in computability theory.  See e.g. this wiki article.  Complexity-theoretic analogues have been studied as well.

Since you mention multiple instances, I might also interpret the question as looking for research into algorithms which, given instances $x^1, \ldots, x^m$ for a decision problem (i.e. language) L, compute some partial information about the membership/nonmembership of the given strings in $L$.

One of the earliest and most influential works of this type was by Jockusch, who in his dissertation and this 1968 paper defined "semi-recursive" languages.  L is semi-recursive if there is a computable "selector" function that, given instances $x^1, x^2$, selects one of these two strings as being "logically more likely" to lie in L.  That is, we require that whenever at least one of $x^1, x^2$ lie in L, the string selected by the selector lies in L.

The study of polynomial-time analogues of this concept was initiated by Selman in this 1979 paper.  Since then there has been tons of work on "p-selective" languages (the polytime version of semi-recursive languages) along with "membership comparable" languages and many other related concepts.  I can't summarize all this work, but consult e.g. this article of Beigel, Fortnow, and Pavan, and this book of Hemaspaandra and Torenvliet.  The concept of bounded queries in computability and complexity is also related, see this survey by Gasarch.


The quad-edge data structure (Delaunay/Voronoi) 2 questions for the computational geometers or algebraists:

I am just beginning to dive into computational geometry and I am loving it =)

I am attempting to read the famous article by Guibas and Stolfi called "Primitives for the manipulation of general subdivisions and the computation of Voronoi Diagrams" in order to implement a Delaunay triangulation algorithm. I am tempted to skip all the theoretical stuff and just read the description of their quad-edge data structure to save time. However, I think it may be worth it to understand all the math in the article if the structure is widely used, or just because it may be beautiful.

The math is a little to dense for me. I'm not completely ignorant on topology, but the description of their edge algebra requires knowledge of abstract algebra that I don't have.

My two questions are: What other applications of the quad-edge structure are there besides computing Delaunay/Voronoi? It seems like an extremely powerful tool.

The second question; What is an abstract algebra? It would be great if you could give me a reference to an introduction to abstract algebra, just enough so I can understand the section on their edge algebra.

Thank you!

I think Guibas and Stolfi's “edge algebra” formalism is a bit unnecessary.

All that's really necessary is to remember the distinction between primal and dual graphs.  Each face $f$ of the primal graph has a corresponding dual vertex $f^*$;  each edge $e$ of the primal graph has a corresponding dual edge $e^*$; and each vertex $v$ of the primal graph has a corresponding dual face $v^*$.  Primal edges connect primal vertices and separate primal faces; dual edges connect dual vertices and separate dual faces.  The dual of the dual of anything is the original thing.  See Figure 4 in Guibas and Stolfi's paper:

Guibas and Stolfi propose thinking about each edge (either primal or dual) as a collection of four directed, oriented edges; for simplicity, I'll call these darts.  Each dart $\vec{e}$ points from one endpoint $\text{tail}(\vec{e})$ to the other endpoint $\text{head}(\vec{e})$, and locally separates two faces $\text{left}(\vec{e})$ and $\text{right}(\vec{e})$.  The choice of which endpoint to call $\text{tail}(\vec{e})$ is the dart's direction, and the choice of which face to call $\text{left}(\vec{e})$ is its orientation.  (Guibas and Stolfi use “Org” and “Dest” instead of “tail” and “head”, but I prefer the shorter labels, because Unnecessary Abbreviations Are Evil.)

For any dart $\vec{e}$, Guibas and Stolfi associate three related darts:

$\text{tailNext}(\vec{e})$: The dart leaving $\text{tail}(\vec{e})$ next in counterclockwise order after $\vec{e}$.
$\text{flip}(\vec{e})$: The “same” dart as $\vec{e}$, but with $\text{left}(\vec{e})$ and $\text{right}(\vec{e})$ swapped.
$\text{rotate}(\vec{e})$: The dual dart obtained by giving $\vec{e}$ a quarter turn counterclockwise around its midpoint.

These three functions satisfy all sorts of wonderful identities, like the following:

$\text{right}(\text{tailNext}(\vec{e})) = \text{left}(\vec{e})$
$\text{right}(\text{flip}(\vec{e})) = \text{left}(\vec{e})$
$\text{right}(\text{rotate}(\vec{e})) = \text{head}(\vec{e})^*$
$\text{flip}(\text{flip}(\vec{e})) = \vec{e}$
$\text{rotate}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))) = \vec{e}$
$\text{tailNext}(\text{rotate}(\text{tailNext}(\text{rotate}(\vec{e})))) = \vec{e}$

For a complete list, see page 83 of the paper (but beware that the authors use postfix notation $e~Flip$, presumably because it's closer to the declarative code e.Flip).  Guibas and Stolfi call any triple of functions satisfying all these identities an edge algebra.

Moreover, given these three functions, one can define several other useful functions like

$\text{reverse}(\vec{e}) = \text{rotate}(\text{flip}(\text{rotate}(\vec{e})))$ — swap head and tail vertices
$\text{leftNext}(\vec{e}) = \text{rotate}(\text{tailNext}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))))$ — the next dart after $\vec{e}$ in counterclockwise order around the face $\text{left}(\vec{e})$

Finally, knowing these functions tell you absolutely everything about the topology of the subdivision, and any polygonal subdivision of any surface (orientable or not) can be encoded using these three functions.

The quad-edge data structure is a particularly convenient representation of a surface graph that provides access to all these functions, along with several other constant-time operations like inserting, deleting, contracting, expanding, and flipping edges; splitting or merging vertices or faces; and adding or deleting handles or cross-caps.

Have fun!


Distributions which are intractable to sample from? I'm looking for an interesting family of probability distributions $P$ that is intractable to efficiently sample from.

I'm not sure what the right notion of intractable is, though I know the notion of efficiently samplable: the existence of a polynomial-time randomized Turing machine that can simulate samples from $P$.

  Q1: Is a reasonable notion of intractable that if there exists such a randomized Turing machine, it can be derandomized to solve an NP-complete problem? If not, what is the right notion? Is there a good reference for this? (Or just some good search terms.)

There are a lot of tautological examples along the following lines: there is no algorithm to sample from [set of solutions to NP-complete problem union a symbol for no solution], because there is an obvious reduction to [that NP-complete problem] by taking the output of the sampler.

  Q2: What are some more interesting examples of intractable sampling problems than these?

There are also examples perhaps like this: Given a set $X$, the goal is to sample uniformly from $P(P(X))$ (powerset). If you could do so with a polynomial time turing machine, you could produce exponentially many bits of entropy in only polynomially many coin flips, which is impossible (because $H(f(Y)) \leq H(Y)$ for any random variable $Y$ and deterministic function $f$).

In order to avoid this kind of example, I want the underlying set of the distribution to grow at most like $2^{p(|x|)}$, where $p$ is a polynomial in the size of the input.

I'll expand my comment to an answer. Many combinatorial structures in graphs are actually NP-hard to sample from.

The earliest example I can think of is JVV86 (Thm 5.1), which shows that there is no polynomial-time algorithm to randomly generate a cycle in a directed graph, unless NP=RP.

Similar results along this line are NP-hardness for sampling independent sets, colourings etc. See e.g. DFJ02, Sly10, GSV15. Note that the corresponding search problems are all easy.

The problem can also be defined by "soft" constraints. E.g., sampling from an anti-ferromagnetic Ising model is NP-hard. See JS93 (Thm 14).

Results of this sort are usually stated as NP-hard approximate counting problems, due to the standard self-reductions JVV86.


Computation space of Nisan's generator for space bounded machines This is probably a very trivial question. Suppose a space($S$) machine uses $R$ random bits. Then Nisan's PRG for space bounded machines can fool it using a seed of length $O(S\log (R/S))$. Theorem 1 in section 4 also mentions that this PRG can be computed in space $O(S\log R)$. This is due to the fact that we need to store $\log R$ many hash functions, each of $O(S)$ space. My questions is, can we say that the PRG can be computed in space $O(S\log (R/S))$ (to produce $R$ bits as above) as well in stead of $O(S\log R)$? That is, can we use just $\log (R/S)$ hash functions?

Reference paper: N. Nisan, Pseudorandom generators for space-bounded computation, Combinatorica, vol. 12, no. 4, pp. 449-461, Dec. 1992.

Yes, I believe that is correct. See, for example, these lecture notes.


maximize edges minus vertices in a weighted graph for a given weighted vertices and edges graph, we want to find the maximum subgraph. the maximum subgraph is made of some vertices and some edges of the given graph which sum of the edges minus sum of the vertices is maximum. what is the algorithm for this problem? or any help with the code please.

This problem can be reduced to the Project Selection problem: suppose you have a set $P$ of projects each has an associated revenue $p_i \in \mathbb Z$ and you have dependencies between projects represented by a directed graph $G$ where the vertices are the projects and an edge $(i, j)$ means that project $i$ can only be selected if project $j$ is selected as well. We need to choose a feasible set of projects $A \subseteq P$, where a set is feasible if for every $u \in A$ we have all the out-neighbors of $u$ also in $A$ (note that this induces a subgraph $G'$ of the set of all projects in $A$ as vertices and the edges joining any two vertices in $A$), and the goal is to choose a feasible set of projects to maximize $\sum_{i \in A} p_i$.

Our reduction is as follows: given a directed graph $G=(V, E)$ with weights on the edges $w$ and weights on the nodes $h$, we define a new graph $G'=(V', E')$ as follows: we create a vertex $v_i$ in $V'$ for every node $i \in V$ and assign it cost $p_{v_i} = - h(i)$, then for every edge $e = (i, j)$ in $E$ we create a node $u_e$ in $V'$ with cost $p_{u_e} = w(e)$ and we create two edges $(u_e, v_i)$ and $(u_e, v_j)$ in $E'$ (these indicate that this edge can only be chosen if both vertices are). To prove that this is correct, note that for a given feasible set of projects in this new problem we can immediately find the corresponding subgraph of $G$, $G_A = (V_A, E_A)$ and we see that it maximizes
$$ \sum_{i \in A} p_i = \sum_{e \in E_A} p_{u_e} + \sum_{i \in V_A} p_{v_i} = \sum_{e \in E_A} w(e) - \sum_{i \in V_A} h(i)$$
which is our original goal. The Project Selection problem can be solved by maxflow algorithms, see Kleinberg and Tardos Section 7.11 for the solution (and a more thorough description of the problem). There is code for this here, Problem 1082G which does a similar reduction and solves the corresponding max flow problem.


About the correspondence of left introduction and elimination of implication in Sequent Calculus and in Natural Deduction resp. Could anyone give an intuitive (not intutionistic) explanation of the correspondence of left introduction and elimination of implication in Sequent Calculus (SC) and Natural Deduction (ND) respectively? I know they should by the symmetry of SC but I don't see how they correspond to each other. More generally, I don't understand how left introduction of a connective in SC renders exactly the elimination of it in ND intuitively.

In computational terms, a sequent calculus term is a sequentialization of a lambda term. That is, viewed as a type system, sequent calculus can be seen as giving an evaluation order of a lambda-term.

So, suppose $\Gamma \vdash e_1 : A \to B$, and $\Gamma \vdash e_2 : A$.

In natural deduction, the term for implication elimination is $\Gamma \vdash e_1\;e_2 : B$ -- that is, application. However, note that this doesn't tell us whether to evaluate $e_1$ first or $e_2$ first.

In sequent calculus, a corresponding proof term assignment must look like

$$\mathsf{let}\; f = e_1 \;\mathsf{in}\;\mathsf{let}\;v = e_2\;\mathsf{in}\;\mathsf{let}\; x = f\;v \;\mathsf{in}\;x$$

or else it must look like

$$\mathsf{let}\; v = e_2\;\mathsf{in}\;\mathsf{let}\;f = e_1 \;\mathsf{in}\;\mathsf{let}\; x = f\;v \;\mathsf{in}\;x$$

Here, the let-form is the proof term corresponding to the use of the cut-rule, and since all of the left rules act only on hypotheses/variables, this forces us to bind all intermediate results to variables. This requirement ensures that we are forced to explicitly say which of $e_1$ or $e_2$ we reduce and bind to a variable first.

For purely functional languages, this explicitness doesn't matter, but as you add effects it becomes easier to work with sequent calculi. This is why things like calculi of control effects/classical logic are typically presented sequent calculus.


Encoding an infinitely looping process with state in the pi-calculus Suppose I have a process that informally does this

int count = 0
forever do
    receive x on some channel c;
    count += x;
    output count on some channel d;

(here ";" means sequential composition -- so P ; Q means do P, and then do Q)

I know how to implement the sequential composition in the pi-calculus -- that was answered in another question here. I also think I know how to model a state variable like count in the pi-calculus.

But what I can't seem to encode in the pi-calculus is the infinite loop. To do that I would either need recursive process definitions, or use replication somehow. But I can't work out the correct way to use replication here -- because I can't work out what process I am replicating (since the use of state means the process being replicated is different every time).

Any help would be great.

thanks
graham

The process $P{\langle 0, c, d\rangle}$ in the context of a recursively defined process like

$$
P{\langle count, c, d\rangle}
   \quad\stackrel{\text{def}}{=}\quad
c(v).(\overline{d}\langle count+v \rangle\ |\ P{\langle count+v, c, d\rangle})
$$

does the job, although we might quibble about how exact it models the original program. However, there is no problem with a more explicit modelling of state.

Translation from recursion to replication is folklore, easy and already discussed in (1): let's assume you have a process $P$ and it uses recursive definitions $X_1\langle \vec{a}_1\rangle = Q_1$, ..., $X_n\langle \vec{a}_n\rangle = Q_n$, where for simplicity we assume that no $Q_i$ uses recursively defined processes. (This restriction is easy to lift.) Then any use of $X_i\langle \vec{a}\rangle$ in $P$ is replaced by an output $\overline{x_i}\langle \vec{a}\rangle$. Let's call the resulting process $P_{new}$. Now the process

$$
   (\nu x_1 ... x_n) ( P_{new} \ |\ !x_1(\vec{a}_1).Q_1 \ |\ ... \ |\ !x_n(\vec{a}_n).Q_n )
$$

does without recursion what $P$ does with recursion. We might say that each recursive equation is replaced by a 'recursion server'.
I'm glossing over a few details here. For more, see e.g. (2).

R. Milner, The Polyadic pi-Calculus: A Tutorial.
J. Aranda, C. Di Giusto, C. Palamidessi, F. D. Valencia, On
Recursion, Replication and Scope Mechanisms in Process Calculi.


Multiple subset sum where subsets have complementary cardinality $\underline{\mathsf{EQUAL\mbox{ }k-COMPLEMENTARY\mbox{ }SUBSET\mbox{ }SUM(EkCSS)} }$Problem:

Input: $a_1,\dots,a_n,b\in \mathbb Z$, with distinct $a_i$ and $k\in\Bbb Z^+$.

Output: $k$ $\mbox{ }\underline{not\mbox{ }necessarily\mbox{ }disjoint}$ subsets of $a_i$s of sizes $n_1,\dots,n_k$ satisfying $\sum_{i=1}^kn_i=n$ such that each subset sums to $b$.

(1) Is $\mathsf{EkCSS}$ $NP$-complete?

(2) If we replace requiring $k$ subsets by requiring $\lceil\log^cn\rceil$ subsets for some fixed $c\in\Bbb R^+$ does the problem remain NP complete?

(3) Is $\mathsf{EkCSS-Diff}\mbox{ }$ $NP$-complete where $\mathsf{EkCSS-Diff}$ is same as $\mathsf{EkCSS}$ but with added condition $n_i\neq n_j\forall i\neq j$ (different subset sizes)?

This is a reduction (attempt :-) from this slight variant of SUBSET SUM (which should be NPC) to prove that E2CSS is NP-complete:

Given integers $A = a_1,a_2,...,a_n\;; a_i > 0$ (with the additional constraint that n is even) and a target sum $b$. Does exist $X \subseteq A$ such that $|X|=2m, m \geq 1$ (i.e. $|X|$ is even and greater than or equal to 2) and $sum(X)=b$?

Reduction: suppose that $2^k > b+\sum_{i=1}^n |a_i|$; then we expand $A$ adding a dummy solution

$A' = A \cup \{ -2^k, 2^k + b\}$

If $X$ is a solution for the original problem, then  $X, Y= \{ -2^k, 2^k + b\}$ are two distinct solutions for $A'$ and target sum $b$. Now we can further expand $A'$ to $|A''|$ adding padding pairs of integers that do not affect the sums but can be used to "pad" $X$ and $Y$ up to $|X|+|Y|=|A''|$. We have
$|A'|=n+2$, so we add $n/2-1$ pairs $\{2^{k+i},-2^{k+i}\}$, $i=1..n/2-1$:

$A'' = \{a_1,...,a_n,-2^k, 2^k + b, 2^{k+1},-2^{k+1},...,2^{k+n/2-1},-2^{k+n/2-1}\}$, $|A''|=2n$

Using all the $n/2-1$ padding pairs we can build a set $Z$ such that $sum(Z)=0$ and $|Z|=2(n/2-1)=n-2$.

We can notice that using the dummy solution and the padding pairs we can build a set $Y'=Y \cup Z$, $sum(Y')=b$, $|Y'|=n$ (which is half the size of $A''$). So in order to get another different solution we  must use two or more of the $a_i$ plus some padding pairs.

In the figure a binary expansion of the elements of $A''$:

The above reduction works for any fixed $k$: just start with the (NP-complete) subset sum variant in which $k$ divides $n$ and $|X|\geq k$, then add $k-1$ dummy solutions (each dummy solution made with $k$ elements) and $(n/k-1)$ padding k-tuples.

If $k$ is part of the input (EkCSS), we have a simple generalization of the E2CSS problem and its NP-hardness follows immediately by the NP-completeness of E2CSS; the reduction is trivial: given an instance $A'',b$ of the E2CSS problem, just transform it to $A'',b,k=2$ which is a valid instance of the EkCSS problem. So EkCSS is NP-complete.

(Very informally) The EkCSS-diff should be NP-complete, too and the reduction from EkCSS is: "attach" to every $a_i$ a group of elements $T_i$ of size $m_i=(i+1)*n$:

$T_i= \{ a_i+1*2^u, 2*2^u,3*2^u,....,(m_i-1) 2^u,-2^u*\sum_{j=1}^{m_i-1} \}, |T_i|=(i+1)*n$

The first element of $T_i$ which replaces $a_i$, contains two detached "bit components" the original $a_i$ and $1*2^u$; but the only way to "clear" $1*2^u$ is to include the other elements of $T_i$ and the final one that is the only negative element (it "clears" all the previous $2^u$ components).

Every $T_i$ have distinct values for $u$ (and choosen in such a way that the sums don't interfere with each other and with the sum of the original $a_i$s).


Fourier decomposition in terms of another basis Given a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$, it is well know that the Fourier decomposition of $f$ can be written as $f(x)=\sum_{S\subseteq \{1,\ldots,n\}} \widehat{f}(S) \prod_{i\in S} x_i$ where $\widehat{f}(S)$ are the Fourier coefficients. So the quantity $\prod_{i\in S} x_i$ can be viewed as the parity of $x\in \{-1,1\}^n$ when restricted to $S\subseteq [n]$.

Is there a way to write the Fourier decomposition in terms of the AND of its variables, i.e., is it possible to express every Boolean function $f$ in terms of
$f(x)=\sum_{S\subseteq \{1,\ldots,n\}} \widehat{f}(S) AND(x_{S})$?  Can this be generalized even further? In general, can any polynomial $p:\{-1,1\}^n\rightarrow \mathbb{R}$ be written in terms of an "AND" decomposition instead of a parity decomposition (in the Fourier sense).

As pointed out in the comments if $u\in \{\pm 1\}$ then $x=x(u) \in \{0,1\}$ where $$x(u)=\frac{1-u}{2},$$ with $x(-1)=1,$ and $x(1)=0.$ This will then yield
$$f(x)=2^{n-1}f(0)-\frac{1}{2} \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$ and if we denote the $\{0,1\}$ valued version of $f$ as $\tilde{f},$
$$\frac{1-\tilde{f}(x)}{2}=2^{n-1}f(0)-\frac{1}{2} \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$ leading to
$$\frac{\tilde{f}(x)}{2}=\frac{1}{2}\left[1+ \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i\right]-2^{n-1}f(0),$$
or
$$\tilde{f}(x)=1-2^{n}f(0)+\sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$
if I haven't made any errors along the way.


Hereditary Discrepancy It is known that it is NP-hard to distinguish whether a set system has discrepancy $0$ or $O(\sqrt{n})$, given that the set system has $n$ elements and $m=O(n)$ sets.

In general if it is so hopeless to estimate or upper-bound discrepancy , then why do we care about algorithms that give colorings of $O(\mathrm{herdisc}(C)(\log m\log n)^{1/2})$ discrepancy ? I am interested in applications of discrepancy in approximation algorithms.

Actually for applications to approximation algorithms, hereditary discrepancy is often the right quantity. The central result here is due to Lovasz, Spencer and Vesztergombi:

  LSV Thm. For any $m\times n$ matrix $A$ and any vector $x \in [0,1]^n$, there exists a vector $y \in \{0,1\}^n$ such that $\|Ax - Ay\|_\infty \leq \mathrm{herdisc}(A)$.

(If you don't have access to the paper, you can check Lemma 1.14 in Chazelle's book for a proof.)
This theorem can then be used to round a solution to a linear programming relaxation of a combinatorial problem. A very nice example is the recent work on the bin packing problem: for the basic idea check the paper by Eisenbrand, Palvoelgyi, and Rothvoss, and for the best result to date, check this recent arxiv paper by Hoberg and Rothvoss.

The exact guarantee you mention -- efficiently finding a coloring with discrepancy bounded by the hereditary discrepancy -- fits very nicely into this, because it's exactly the guarantee to make the LSV theorem constructive. I.e. if you have an algorithm that for any matrix $A$ finds in polynomial time a coloring $x \in \{-1, 1\}^n$ such that $\|Ax\|_\infty \leq \alpha \cdot \mathrm{herdisc}(A)$, then we have an efficient LSV theorem in which for any $A$ and $x$ there exists a polynomial time computable $y$ such that $\|Ax - Ay\|_\infty \leq \alpha \cdot \mathrm{herdisc}(A)$.

By the way, hereditary discrepancy turns out to be the right quantity in other applications too: constructing $\epsilon$-samples and differential privacy, for example. Also it can be efficiently approximated up to a factor of $\log^{3/2}m$. The largest hardness of approximation known for hereditary discrepancy is factor 2, so hereditary discrepancy may even be approximable within a fixed constant (although I'd be surprised).

EDIT: Let me say a few more words about the approximation, since you say you want to find upper bounds on $\mathrm{herdisc}$. Although my paper with Kunal is not written this way, what we show in fact is that
$$
\gamma_2(A)/O(\log \min(m,n)) \leq \mathrm{herdisc}(A) \leq O(\sqrt{\log m})\gamma_2(A),
$$
where $\gamma_2(A)$ is a classical factorization norm, equal to the smallest number $t$ such that there exist vectors $u_1, \ldots, u_m$, $v_1, \ldots, v_n$ satisfying

for all $i,j$, $\|u_i\|^2 \leq t$ and $\|v_j\|^2 \leq t$;
for all $i, j$, $a_{i,j} = u_i^T v_j$.

It's not hard to turn this definition into a semidefinite program that computes $\gamma_2(A)$. Besides the approximation, this is very useful because $\gamma_2$ has many nice properties which make it easy to give upper and lower bounds which then translate into upper and lower bounds for hereditary discrepancy. My paper with Matousek has some applications.


Finding the distance between two polynomials (represented as trees) A colleague who works on genetic programming asked me the following question. I first tried to solve it based on a greedy approach, but on a second thought, I found a counterexample to the greedy algorithm. So, I thought it's worth mentioning here.

Consider two polynomials which are represented by their expression trees. For instance, $x^3-2x+1$ and $x^2 + 4$ are illustrated below:

Rules:

Each node is either a variable name ($x, y, z, \ldots$), a number, or an operation (+,-,×).
The in-order traversal of the tree should result in a valid polynomial.
Operation nodes have in-degree 2. Other nodes have in-degree 0. All nodes have out-degree 1 (except root, whose out-degree is 0).

On a node N of the tree, define the basic operation as follows:

A basic operation can change the label of the node. For instance, $x$ can be changed to 3, or + can be changed to $\times$.
A basic operation can build an expression tree on top of N (see the example below).

The cost of the basic operation of type 1 is 1. The cost for type 2 is equal to the number of {+,-,×} operations in the newly built expression tree.

Example for type 2: The cost of the following basic operation is 2, since the expression tree built on top of node N uses two operations (- and ×).

Let T1 and T2 be two expression trees representing polynomials.
Define the distance of T1 and T2 as follows: the minimum cost of basic operations for converting T1 to T2. Note that we don't require the converted tree to have the same structure as T2. We just want it to compute the same polynomial as T2. (See the comments for an example.)

  The problem: Given T1 and T2, present an algorithm which computes their distance.

Example 1: Let T1 and T2 are the two trees illustrated at the beginning of this post. To convert the right tree to the left tree, one can build a tree of cost 3 on top of ×, and change 4 to 1 (the total cost is 4).

Example 2: Let T1=$x^4$ be represented by the following tree. To convert T1 to T2=$x^4+4x^3+6x^2+4x+1$, it suffices to add 1 to each of the $x$ nodes, to optain $(x+1)^4$=T2. This can be done by adding a cost-1 expression tree on top of each $x$ node. This example shows that the term-by-term conversion (which I called the greedy approach at the beginning of this post) is not an optimal approach. That is, if one wants to produce terms in T2 which are not present in T1 (i.e. $4x^3$, $6x^2$, $4x$, and 1), the cost will be much higher.

Tree Edit Distance is a generalization of string edit distance. The distance between two trees is the minimum number of node insertions \ deletions \ and relabels required to turn one tree into the other. (when we delete node v, v's children become children of parent(v)).
The problem is NP-hard when the trees are unordered, but when they are ordered (i.e., there is a left-to-right order among siblings) the problem is solvable in O(n^3) time (as in the paper that Sadeq mentioned). A good survey that describes this: http://portal.acm.org/citation.cfm?id=1085283


What data structures exist for fast calculation of distances between multi-dimensional points I'm writing a program that receives data over a network connection. Every data point is simply a 4 dimensional vertex, lets call the dimensions X,Y,Z,W.  The values of each dimension are exponentially distributed.

I'm currently saving the data and plotting the data, in real time, as a 2D scatter plot.  Here is an example of such a plot:

One thing is obvious in the picture is there are most of the points are near the origin. Any two points that overlap are redundant as they carry the identical information. This means that the majority of the points near the origin can be discarded where as very few points far from the origin can be discarded. I'd like to come up with an intelligent way to filter out redundant points.

I've thought of a few way of doing this. One of which would use an intelligent data structure that when insertNewPoint is called the structure first checks to see if any points in the data structure are within a predefined distance of the new point. If this is true than the new point is discarded otherwise it is added to the data structure.

Here is some pseudo code that illustrates the idea:

Structure Points{
    list storedPoints;
    distance threshold;

    insertNewPoint(newPoint){
        for each point in storedPoints
            if calculateDistance(newPoint, point) < threshold
                return false

        storedPoints.add(newPoint)
        return true
    }

}

I anticipate that these data structures will eventually contain upwards of 50K+ points, and each second between 10-100 new points will be received by my program.

Are there data structures that are designed for these kind of operations? If not, what would be the most efficient way implement a structure like this for 4 dimensions?

I'm not sure what you mean by 'overlapping points', and even less clear how you construct a 2D scatter plot from 4D data unless by doing some kind of projection. Having said that, what I think you're looking for is a dynamic near-neighbor data structure. Specifically, you want a data structure that processes queries of the form "Who's my nearest neighbor in the current set" and "insert a point into the current set"

While there's a ton of work on different kinds of near-neighbor structures, your particular situation (dynamic 4D points) suggests at least starting with a grid-based structure. Make (4D) buckets based on segmenting the coordinates, and hash the points in, and then for a query you can do a spiral search (or something similar) around the cell your query lies in.

The next idea would be to build a generalized quad tree data structure (a compressed quad tree) or even something involving space-filling curves, if this first approach doesn't yield the performance you need. There are even more powerful methods, but I wouldn't recommend looking into them till you've exhausted the simple approaches.

Bottom line: "dynamic" and "nearest-neighbor" and "low dimensional" are your google friends.


Partitioning a connected shape into rectangles I imagine this must be an introductory computational geometry question, but I'm not sure of the best search phrases, and I'm interested in variations of the question, also, so I'm hoping for pointers to useful references. I'm interested in feasible algorithms for the following problem.

  Input: A connected set of points (shape) in $\mathbb{Z} \times \mathbb{Z}$.
  Output: A partition of the shape into rectangles, such that the rectangles do not overlap one another, and they cover only the shape, no "empty" space.

I'm interested in finding the minimum number of rectangles, the "best" set of rectangles for any notion of best, whether this problem becomes easier or harder for different classes of shapes.

Thank you. :-)

David Eppstein gave an excellent answer for this question here on MathOverflow (responding to a question for which it is not quite as good an answer). To summarize, there is a polynomial-time algorithm for finding the minimum number of rectangles.


Complexity of a variant of partition problem Motivated by this post, Strongly NP-complete variants of subset sum or partition problem, I am interested in this variant of partition:

Given a solution to balanced partition problem (both parts have same cardinality), find another solution that have maximum cardinality discrepancy (i.e. $||P_1|-|P_2||$ is maximum).

  Is there an efficient algorithm to find such unbalanced partition or is it NP-hard?

I am interested in pseudo-polynomial time algorithms or proving the problem to be strongly NP-hard.

P.S. Here is an example (as requested by @domotorp) $p1=\{2,2,3,4,5, 6\}$ and $p2= \{1, 1,3, 4, 5, 8\}$. The second solution is $p1=\{1,2,3,4,4, 8\}$ and $p2= \{ 1,2,3,5,5,6\}$ (the second solution is not optimal as p1 and p2 have equal number of elements).

The problem of finding a maximum cardinality discrepancy partition (or determining that one doesn't exist) is solvable in pseudo-polynomial time even if a balanced partition is not given.

Suppose that the input is a multiset of positive integers $S = \{x_1, \ldots, x_N\}$. Let $K = \sum_{i = 1}^Nx_i$. Below I demonstrate a dynamic programming algorithm for finding a maximum cardinality discrepancy partition of $S$.

Suppose $s$, $i$, and $c$ are variables with $0 \le s \le K$ and $0 \le c \le i \le N$. Then define $p(s, i, c)$ to be true if and only if there exists a multiset $T \subseteq \{x_1, \ldots, x_i\}$ whose cardinality is $c$ and whose sum is $s$.

We can define a recurrence:

$p(s, 0, 0)$ is true iff $s = 0$.
$p(s, i, c)$ is true if either $p(s, i-1, c)$ or $p(s - x_i, i-1, c-1)$ is true.
$p(s, i, c)$ is false otherwise.

Using this recurrence we can compute the value of $p$ on all valid $s$, $i$, and $c$ in time polynomial in $N$ and $K$.

Furthermore, the predicate $\phi(c) = p(\frac{K}{2}, N, c)$ can be interpreted as "does there exist a subset of $S$ of cardinality $c$ whose sum is half of the sum of $S$?" or equivalently as "does there exist a partition of $S$ with cardinality discrepancy $|N-2c|$?". Thus, after finding all the values of $p$, we can simply look through all the values of $\phi(c) = p(\frac{K}{2}, N, c)$ and select the value of $c$ with $\phi(c)$ true for which the cardinality discrepancy $|N-2c|$ is largest. Call this value $c_0$. If $\phi(c)$ is never true then there is no partition of $S$.

All that's left is to actually find the partition of $S$ one of whose sets has size $c_0$. Here's an algorithm for doing this:

initialize P_1 and P_2 to be empty lists
initialize (s, c) to (k/2, c_0)
for i = N, N-1, ..., 1
| if p(s, i-1, c) is true:
| | add x_i to P_1
| else:
| | add x_i to P_2
| | set (s, c) to (s - x_i, c-1)
output P_1 and P_2

Notice that this algorithm is just following the recurrence of $p$ back from $p(\frac{K}{2}, N, c_0)$ to $p(0,0,0)$. That is, the algorithm maintains the invariant that $p(s, i, c)$ is always true at the start of the loop (this is easy to prove by induction). The invariant even continues to hold after the last iteration of the loop; that is, $p(s, 0, c)$ is true after the loop. Since $p(s, 0, c)$ is only true if $s = c = 0$, we can deduce that $s$ and $c$ decrease from $\frac{K}{2}$ and $c_0$ to $0$ over the course of a loop. Looking at the only line where $s$ and $c$ change, this clearly implies that list $P_2$ ends up containing exactly $c_0$ elements whose total sum is $\frac{K}{2}$. In other words, $P_1$ and $P_2$ form a partition of $S$ whose cardinality discrepancy is $|N - 2c_0|$, which by definition of $c_0$ is exactly the largest possible cardinality discrepancy for any partition of $S$.


Programming Language Theory and Abstract Algebra Are there any applications of Abstract Algebra to Programming Language Theory? Is there anything that would be useful in language design and compiler implementation?

Algebra in the classical sense of the word is used in modeling of computational effects as algebraic operations, see for example these slides by Gordon Plotkin, or you can read real papers and Ph.D. theses, if you actually meant to ask the question.

And to blow my own horn, have a look at Eff and read about it, a language designed around the idea that computational effects are algebraic operations and that handlers are homomorphisms of algebras.


What's wrong with this proof that NP=Co-NP implies NP=PSPACE Below is a short informal proof that NP=co-NP implies NP=PSPACE. What's wrong with the proof?

Assuming NP=co-NP, an instance F of TQBF can be solved by a polynomial NDTM this way:

  Non-deterministically guess the values for all the variables corresponding to existential quantifiers in F.
  The resulting formula F1 (with the guessed values substituted in the formula) will only have universal quantifiers, which makes F1 a Co-NP problem instance.
  Since NP=co-NP, there's a short certificate to verify F1's truth.
  Guess this short certificate too.

That is, the NDTM non-deterministically guesses two things: The values for all the variables corresponding to existential quantifiers in F, and the short certifcate for the intermediate (co-NP) instance F1.

A totally quantified boolean formula consists of an alternating sequence of quantifiers. This sequence is not of length 2, but arbitrarily long. That is the mistake you're making: an instance can be represented as a pair (P, phi) where phi is a propositional formula and L = (X_1, ..., X_k) is a partition of the set of variables occuring in phi, such that X_i are the variables in the i'th quantifier (which is an existential one if i is odd, and universal otherwise). You are assuming that this instance is equivalent to (L', phi), L' = (X_1', X_2') where X_1' is the union of the odd-indexed X_i, and X_2' is the union of the even-indexed X_i. Please verify for yourself that this is not necessarily true.


Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$ I am considering products $U\times V$ of subsets $U, V\subset \{0, 1\}^p$ with a pairwise Hamming distance greater than 1 : $\forall uv\in U\times V, D(u,v) \geq 2$.

Given $p$, I am looking for a good asymptotic upperbound on $\mid U\times V\mid$, the cardinality of the products, for all possible choices of $U$ and $V$.

To make it hopefully more precise :
$$\max \{\operatorname{Card} \ (U\times V) \mid \ U, V\subset \{0, 1\}^p\mbox{ such that  }\forall uv\in U\times V, D(u,v) \geq 2\}.$$

Consider $p=2q$, $q\ge 1$.

Asymptotically, the quantity you are after is $2^{4q-2}$.

First, let's prove a lemma of general interest.

Lemma $(2^{2q}/\sqrt{\pi q})/1.136 < \binom{2q}{q} < 2^{2q}/\sqrt{\pi q}$.

Proof: Recall the Robbins bounds
$$
n! = \sqrt{2\pi}n^{n+1/2}e^{-n}e^{r_n},
$$
where $1/(12n+1) < r_n < 1/(12n)$.
This gives
$$
\binom{2q}{q} = 2^{2q}e^{r_{2q}}/\sqrt{\pi q}e^{2r_q} >
\left(2^{2q}/\sqrt{\pi q}\right)/c
$$
where $c = e^{(18q + 1)/(6q(24q+1))} < e^{19/150} < 1.136$.
Further,
$$
\binom{2q}{q} < \left(2^{2q}/\sqrt{\pi q}\right)/d
$$
where $d = e^{(36q - 1)/(24q(12q+1))} > 1$.$\qquad\qquad\Box$

Corollary $\binom{2q}{q} = \Theta(2^{2q-(\log_2 q)/2})$.

A first pass upper bound is $\left(2^{2q-1}\right)^2 = 2^{4q-2}$, since $U$ and $V$ cannot overlap.

For a lower bound.  By the symmetry of the binomial expansion one can achieve
$$
\left(\sum_{i=0}^{q−1}\binom{p}{i}\right)^2
= \left(\left(2^{2q} - \binom{2q}{q}\right)/2\right)^2
= 2^{4q-2}\left(1-1/\left(\alpha\sqrt{\pi q}\right)\right)^2
$$
where $1 < \alpha < 1.136$ by the lemma.
This expression can be obtained by taking $U$ to be the set of $p$-bit Boolean vectors within Hamming distance $q−1$ from $0\dots 0$, and $V$ to be the vectors within distance $q−1$ from $1\dots 1$.
These sets both have the same size.
(Note that the number of $p$-bit Boolean vectors which have Hamming distance exactly $i$ from the all-zero vector is $\binom{p}{i}$.)

Now note that $\alpha\sqrt{\pi q}$ is smallest when $q = 1$, taking a value that exceeds $\sqrt{\pi}$.  Hence $\left(1 - 1/(\alpha\sqrt{\pi q})\right)^2 > 0.1899$.
It follows that the quantity you are interested in is $\beta 2^{4q-2}$, where $0.1899 < \beta < 1$.

The case for $p$ odd seems a bit more involved, but the same idea might apply.  The "buffer zone" between $U$ and $V$ is now going to consist of vectors of two different Hamming weights instead of just one, so it has roughly double the impact.  This probably calls for a more careful analysis of the error, and the lower bound might leave a bit of slack.

Disclaimer: I wrote the above fairly quickly, so there may be some errors in the derivation.  Please check the details if you plan to use this elsewhere.  Such a natural question has probably also been studied in the coding theory literature.

Reference:

Herbert Robbins, A remark on Stirling's formula, The American Mathematical Monthly 62(1), 1955, 26–29.  doi:10.2307/2308012


Survivable networks, directed case I have been working on a project that turns out to be a special case of the directed version of the survivable network problem.

Iterative rounding gives a 2-approximation of the undirected case. I'm wondering if the directed case has been studied at all and if so, what approximations can be guaranteed.

The directed versions are much harder. A survey by Nutov available on his web page is
a good starting point.
http://www.openu.ac.il/home/nutov/Survivable-Network.pdf


Weakly normalizing + confluent = strongly normalizing? I was reading this abstract and saw that they prove weak normalization and confluence. My limited understanding suggests that those two properties should provide strong normalization, which then leaves me confused about why they'd leave that out in the abstract, thus suggesting I might be wrong.

Is it the case that a confluent weakly normalizing system is strongly normalizing? Why/why not?

Is it the case that a confluent weakly normalizing system is strongly normalizing?  Why/why not?

No, it's not necessarily the case.

Weak normalization means: there exists a reduction strategy that will lead to a normal form.
People often use confluence to mean what rewriting people call "local confluence": this is the property that if $a \leadsto b$ and $a \leadsto c$, then $b$ and $c$ can be joined -- i.e., there exists a $d$ such that $b \leadsto^\ast d$ and $c \leadsto^\ast d$.

This does not rule out the existence of infinite reduction sequences.

As an example, start with the STLC and add a new base type $X$ and constant $c,d : X$ with the reduction rule $c \leadsto c$ and $c \leadsto d$.

There is a weak normalization strategy: use a weak normalization strategy for the STLC and immediately reduce any $c$ to $d$. The calculus is also Church-Rosser, since it inherits this property from the STLC. But it isn't strongly normalizing since you can reduce a $c$ forever.


Are there efficient general Bonferroni-style bounds known? A classic problem in probability theory is to express the probability of an event in terms of more specific events.  In the simplest case, one can say $P[A \cup B] = P[A] + P[B] - P[A \cap B]$.  Let's write $AB$ for the event $A \cap B$.

There are then some ways to bound $P[\cup A_i]$, without assuming independence of the finitely many events $A_i$.  Bonferroni gave the upper bound
$$P[\cup A_i] \le \sum P[A_i]$$
(this is sometimes also attributed to Boole), and Kounias refined this to
$$P[\cup A_i] \le \sum_i P[A_i] - \max_j \sum_{i \ne j} P[A_i A_j].$$

The dependence structure of the events can be thought of as a weighted hypergraph with vertices $A_i$, with the weight of an edge representing the probability of the event associated with the intersection of the vertices in the edge.

An inclusion-exclusion style argument considers larger and larger subsets of events together.  These yield the Bonferroni bounds.  These bounds use all weights for edges up to some size $k$.

If the dependence structure is "nice enough", then the Lovász Local Lemma can be used to bound the probability away from the extreme values 0 and 1.  In contrast to the Bonferroni approach, the LLL uses quite coarse information about the dependence structure.

Now suppose relatively few weights in the dependence structure are non-zero.  Further, suppose that there are many events that are pairwise independent yet are not independent (and more generally, it is quite possible that a set of $k$ events is not mutually independent but is $r$-wise independent for every $r < k$).

  Is it possible to explicitly use the dependence structure of events to improve the Bonferroni/Kounias bounds, in a way that can be computed efficiently?

I expect the answer is yes, and would appreciate pointers to references.  I am aware of Hunter's paper from 1976, but it only deals with pairwise dependencies.  Hunter considers spanning trees in the graph formed by ignoring the edges in the dependence structure of size 3 or greater.

David Hunter, An Upper Bound for the Probability of a Union, Journal of Applied Probability 13 597–603.  http://www.jstor.org/stable/3212481

I think you'll find the answer in the paper "Approximate Inclusion-Exclusion" by Linial and Nisan:
http://www.cs.huji.ac.il/~nati/PAPERS/approx_incl_excl.pdf


Is the finite inverse semigroup isomorphism problem GI-complete? Is the finite inverse semigroup isomorphism problem GI-complete? Here the finite inverse semigroups are assumed to be given by their multiplication tables.

Yes, the finite inverse semigroup isomorphism problem is GI-complete! This is a corollary of

  Theorem: Lattice isomorphism is isomorphism complete

from section 7.2 Lattices and Posets in

  Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo.

because a (semi-)lattice is also an (idempotent commutative) inverse semigroup.

Proof of theorem from technical report:

  It suffices to represent a graph uniquely as a lattice. Given a graph $G$ with $n$ vertices and $m$ edges, we define a lattice with an element for each vertex, an element for each edge, and two additional elements $\text{'}0\text{'}$ and $\text{'}1\text{'}$. Element $\text{'}1\text{'}$ dominates all others (the supremum), and element $\text{'}0\text{'}$ is dominated by all other elements (the infimum). An edge dominates exactly those vertices which are its endpoints. The result is a lattice which uniquely represents $G$.

The idea for this answer came from a discussion with vzn about sufficiently focused questions. The motivation to spend time on graph isomorphism at all also came from vzn's repeated prodding. J.-E. Pin asked in the comment whether there are any specific reasons to consider inverse semigroups. The idea was to have a structure slightly generalizing groups, which is GI complete. I wanted to better understand the relation between group isomorphism and graph isomorphism, but I fear this answer doesn't provide any insight of this sort.


Is DAG isomorphism NP-C Given two directed acyclic graphs $G_1$ and $G_2$, is it NP-Complete to find a one-to-one mapping $f:V(G_1) \rightarrow V(G_2)$ such that $(v_i,v_j) \in D(G_1)$ if and only if $(f(v_i),f(v_j)) \in D(G_2)$?

$D(G)$ is defined as the set of arcs in $G$.

It's GI-complete which means it's probably not NP-complete.

Reduction from undirected graph isomorphism to DAG isomorphism: given an undirected graph $(V,E)$, make a DAG whose vertices are $V\cup E$, with an edge from $x$ to $y$ whenever $x\in V$, $y\in E$, and $x$ is an endpoint of $y$. (i.e. replace every undirected edge with a node and two ingoing edges)

Reduction from DAG isomorphism to undirected graph isomorphism: replace each arc $x\rightarrow y$ in the DAG with a four-edge subgraph consisting of a triangle having $x$ as one endpoint, and a dangling edge on the triangle connected to $y$. The reduction is only ambiguous in the case of a component that's a directed cycle, and that's not a DAG.


Is it possible to encrypt a CNF? Is it possible to convert a CNF $\mathcal C$ into another CNF $\Psi(\mathcal C)$ such that

The function $\Psi$ can be computed in polynomial time from some secret random parameter $r$.
$\Psi(\mathcal C)$ has a solution if and only if $\mathcal C$ has a solution.
Any solution $x$ of $\Psi(\mathcal C)$ can be efficiently converted into a solution of $\mathcal C$ using $r$.
Without $r$, the solution $x$ (or any other property of $\Psi(\mathcal C)$) does not give any help in solving $\mathcal C$.

If there is such a $\Psi$, then it can be used to make others to solve computational challenges for us (with possibly replacing solving a CNF with other problems - I chose CNF because I wanted to make the problem more specific), in such a way that they cannot profit from a possible solution even if they know what problem we've used them to solve.
For example, we could embed a factorization problem into a computer game, which enables players to play only if they work on our problem in the background, from time to time sending back proofs of computation.
Maybe software can be even made "free" this way, where "free" hides a (possibly higher) cost in your parents' electricity bill.

The application you mention is called "proof of useful work" in the literature, see for instance this article.

You can use a fully homomorphic encryption scheme (where the plaintext is the CNF instance) to delegate the computation to an untrusted party without disclosing the input.

This doesn't answer exactly your question, since such scheme doesn't map a CNF into another CNF, but it does work for the intended application.


Addding edges to spanning tree without destroying planarity Given a graph $G=(V,E)$ with n vertices, m edges, and the maximum degree $\Delta$. Let $T$ be a spanning tree of $G$. Let $E_c \subseteq E - E(T)$ be the maximum number of edges that we can add to $T$ so that $T \cup E_c$ is a planar graph. Is there any known upper or lower bound on the size of $E_c$ in term of $n, m$ and $\Delta$

Here's an example of a graph $G$ and a tree $T$ in that graph such that you can't add very many edges from $G$ to $T$ while preserving planarity. Let $P$ be a $2n$-vertex path, and let $S$ be a set of $n$ points $(x_i,y_i)$ in the plane with distinct integer coordinates in the range $[1,n]$ such that the longest polygonals chains in $S$ in which all slopes have the same sign have length approximately $\sqrt n$ (according to the Erdős–Szekeres theorem).  Add to $G$ one edge for each point $(x_i,y_i)$ in $S$, whose endpoints are the vertices at positions $x_i$ and $n+y_i$ in the path.

Now consider any planar graph sandwiched between $T$ and $G$, and draw it in the plane such that $T$ lies along a horizontal line (possibly causing the other edges to curve rather than being straight, but without crossings). We can partition the edges added to $T$ into four classes: the ones that stay below the line, the ones that stay above the line, the ones that wrap around the left endpoint of $T$, and the ones that wrap around the right endpoint of $T$ (wrapping around exactly two endpoints of $T$ doesn't help — all such edges can be deformed topologically so that they stay above or below the line — and wrapping around more than twice is not possible). In each of these four classes, a subset of non-crossing edges must correspond to a monotonic polygonal chain in $S$. Therefore, the total number of added edges is at most $4\sqrt n + O(1)$.

The Erdős–Szekeres theorem can be used in the other direction to find large subsets of edges that don't cross each other when $T$ is a path. I'm not entirely sure what happens when $T$ isn't a path, but it seems likely to me that the size of the planar subsets you can find only goes up in this case, so that (in the case of a linear number of edges and bounded vertex degree) $\Theta(\sqrt n)$ is the right bound on the number of added edges you can always find.


Deterministic dynamic dictionary on a small universe We want to maintain a dictionary of $m$ elements with insert/delete and lookup in the word RAM model. Assume $m=O(n)$ at all times, so there can't be too many inserts without deletions. The universe has size $\{0,\ldots,n^c-1\}$ for some constant $c$.
How fast can we support these operations deterministically (in either worst case or amortized time) if we are restricted to $O(n)$ space? How about $O(n \mathop{\mathrm{polylog}} n)$ space?
A few simple observations:

When $c=1$, an array of size $n$ support all operations in worst time $O(1)$.

It's not hard to come up with a $O(n^{1+\epsilon})$ space data structure so all queries can be done in $O(\frac{1}{\epsilon})$ worst case time for any $\epsilon>0$.

We can implement all operations in worst time $O\left(\frac{(\log \log n)^2}{\log \log \log n}\right)$ with $O(m)$ space using exponential tree.[1]

To clarify, I'm looking for dictionaries with space requirement as a function of the size of the universe, and not the number of elements in the dictionary.

If randomness is allowed, you can get space $B + o(B)$ and time $O(1)$ (worst-case, with high probability), where $B$ is $\lg {U \choose n}$, which is the lower bound on how much space you need using any representation: Arbitman et al., " Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation".

For deterministic dictionaries, the best known bounds are discussed in Thorup's "Mihai Pǎtraşcu: Obituary and Open Problems"


Chernoff bound for weighted sums Consider $X = \sum_i \lambda_i Y_i^2$, where $\lambda_i$ > 0 and $Y_i$ is distributed as a standard normal. What kind of concentration bounds can one prove on $X$, as a function of the (fixed) coefficients $\lambda_i$?
If all the $\lambda_i$ are equal then this is a Chernoff bound. The only other result I am aware of is a lemma from a paper of Arora and Kannan ("Learning mixtures of arbitrary Gaussians", STOC'01, Lemma 13), which proves concentration of the form $\Pr[X < E[X] - t] < \exp(-t^2/(4 \sum_i \lambda_i^2)$, i.e., the bound depends on the sum of the squares of the coefficients.
The proof of their lemma is analogous to the usual proof of the Chernoff bound. Are there other "canonical" such bounds, or a general theory of which functions of the $\lambda_i$'s are such that their largeness ensures good exponential concentration (here, the function was simply the sum of the squares)? Maybe some general measure of entropy?
A more standard reference for the Arora-Kannan lemma would also be great, if it exists.

The book by Dubhashi and Panconesi collects together many such bounds, more numerous than can be listed here. If you find that hard to access immediately, there's an online  survey of Chernoff-like bounds by Chung and Lu


Existing benchmarks for scheduling problems? Which benchmarks exist to evaluate the performance of algorithms for Job-Shop or Flow-shop scheduling problems?

Mainly, there exist 3 benchmarks to test shop scheduling problems.
Namely they are Taillard, Structured and ORLib benchmarks. These benchmarks have different
goals. The Taillard benchmark is the most
used benchmark in the literature. The benchmark targets permutation flowshop, flowshop, open shop and job shop scheduling problems. For details and download of the benchmark refer to http://www.lifl.fr/~liefooga/benchmarks/benchmarks/

The second benchmark shop scheduling problems is the structured benchmark. As
the name suggests, the goal of the benchmark is to have test instances having a structure
additional to the test instances with random instances. It contains all the instances from
the Taillard benchmark. Further details and the benchmark can be found at http://www.cs.colostate.edu/sched/generator/

The third benchmark focuses on collecting test cases found difficult to solve in
industry. We refer to this benchmark as ORLib benchmark. Contains instances from
Taillard + some instances from industry. More details and benchmarks can be found at http://people.brunel.ac.uk/~mastjjb/jeb/orlib/flowshopinfo.html


Approximations for the Stable Fixtures Problem I have a set of N items, each with a subset of those items they can be paired with; each pair has a weight.  I'd like to choose pairs to maximize the total weight, subject to each item being in at most M pairs.

I believe this can be seen as an instance of the Stable Fixtures Problem (itself a generalization of the Stable Roommates Problem), which seeks to find a stable matching if one exists.  However, I don't really care if the matching is stable, and I want to find a high-weight matching in every case.  It doesn't need to be optimal, approximate is fine.

Are there any approximate solutions for this problem, or does this problem go by another name in another field?  Approaches I can think of would be to randomly perturb the ranks (weights) until a stable matching is found, or perhaps treat it as a linear programming problem.

Your problem is called maximum weighted simple b-matching, and it's solvable in strongly polynomial time. See this paper for instance.


What is some important work in fractals? Relating to the discussion on whether fractals are part of TCS, my question is:

  What are some important work/results in fractals in TCS?

The work/results may be focusing on fractals or it may use fractal concepts as a secondary analysis of some primary topic.

Mark Braverman has written quite a bit about Julia sets. See, e.g. Computability of Julia Sets


Fastest approximate triangle counting algorithms in dense graphs One may compute the number of triangles in a graph by matrix multiplication in time $O(n^\omega)$. There is also a very simple algorithm that runs in time $O(n^3/(\epsilon^2 T))$ (where $T$ is the number of triangles) for $1\pm \epsilon$ approximate triangle counting. It works by repeatedly sampling triplets of vertices and using those sample to estimate the number of triangles.
Is there anything asymptotically faster than these two algorithms? I am aware of the sublinear-time algorithms for triangle counting. However, those that I am aware of are parameterized by the number of edges and not the number of vertices. I am only interested in results parameterized by the number of vertices.

I have written up an answer, it can be found here: https://arxiv.org/abs/2104.08501
The best known triangle counting algorithm runs in time $\tilde{O}(n^\omega)$. I was able to retain the exponent of $n$ while having negative dependence on $T$. In fact, the running time is $\tilde{O}_\epsilon(n^\omega/T^\delta)$ such that there is the is no such algorithm for any constant $\delta' < \delta$. In this sense, the algorithm is optimal. (One could, however, imagine an algorithm with non-constant $\delta$.) The value of $\delta$ is $\omega - 2$. This degenerates to $0$, if there exists a quadratic matrix multiplication algorithm.
I have also done the same for sparse matrix multiplication. There, the state-of-the-art was $\tilde{O}(m^{2\omega/(\omega+1)})$. I have retained the exponent while again having "optimal" negative dependency on $T$ (albeit the optimality is in the fairly weak sense mentioned above).
For a sketch of the algorithm, see page 5 in the paper. If you have comments, I would be very happy to hear them.
Here is a diagram comparing the running time to other algorithms:

(I have just noticed that the diagram on the right should have log base $m$, I'll fix it later)
The "optimality" lies in the fact that the blue line (my algorithm) touches the dashed red line (the lower bound). And yes, our algorithm is in fact slower than state-of-the-art for large values of $T$. On that range, the optimal algorithm was in fact already known. One could probably fix that so that this algorithm is never slower than the state-of-the-art; however, the analysis is already technically non-trivial as it is now.


Finding twin vertices in graphs Let $G=(V,E)$ be a graph. For a vertex $x\in V$, define $N(x)$ to be the (open) neighbourhood of $x$ in $G$. That is, $N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}$. Define two vertices $u,v$ in $G$ to be twins if $u$ and $v$ have the same set of neighbours, that is, if $N(u)=N(v)$.

  Given a graph $G$ on $n$ vertices and $m$ edges as input, how fast can we find a pair of twins in $G$, if such a pair exists?

We can check whether two given vertices are twins in $O(n)$ time, by comparing their neighbourhoods. A straightforward algorithm is to find twins is thus to check, for each pair of vertices, whether they are twins. This takes $O(n^{3})$ time (and also finds all pairs of twins). Is there is significantly faster way to find (if there exists) a pair of twins in the graph? Is there known work in the literature that addresses this problem?

Twins in a graph are just modules of size 2. The modular decomposition of a graph can be found in $O(n+m)$ time. The modular decomposition tree implicitly represents all modules of the graph and consists of three types of internal nodes: series, parallel and prime nodes, and the leaves consists of the individual nodes. A set of at least two vertices $S \subset V$ is a module if and only if it is some node in the tree or the union of some set of children of a series or a parallel node.

So to find a pair of twin nodes, if they exist, we can construct the modular decomposition tree in $O(n+m)$ time. Then look at the leaves, if the parent of any leaf is a series or parallel node then that node must have at least two children which form a twin pair. So the total running time is linear.

http://en.wikipedia.org/wiki/Modular_decomposition


Efficiently computable function as a counter-example to Sarnak's Mobius conjecture Recently, Gil Kalai and Dick Lipton both wrote nice articles on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and the Riemann Hypothesis.

  Conjecture. Let $\mu(k)$ be the Möbius function. Suppose $f: \mathbb{N} \to \{-1,1\}$ is an $\mathsf{AC}^0$ function with input $k$ in the form of binary representation of $k$, then
  $$ \sum_{k \leq n} \mu(k) \cdot f(k) = o(n) \text.$$

Note that if $f(k) = 1$ then we have an equivalent form of the Prime number theorem.

UPDATE: Ben Green on MathOverflow provided a short paper which claims to prove the conjecture. Take a look at the paper.

On the other hand, we know that by setting $f(k) = \mu(k)$ (with slight modification so the range is in $\\{-1,1\\}$), the resulting sum has the estimation
$$ \sum_{k \leq n} \mu(k)^2 = \Omega(n) \text.$$
There is an upper bound that $\mu(k)$ can be computed in $\mathsf{UP} \cap \mathsf{coUP} \subseteq \mathsf{NP} \cap \mathsf{coNP}$, so the constraint proposed on $f(k)$ in the conjecture cannot be relaxed to an $\mathsf{NP}$ function.
My question is:

  What is the lowest complexity class $\mathsf{C}$ we currently know, such that a function $f(k)$ in $\mathsf{C}$ satisfies the estimation
  $$ \sum_{k \leq n} \mu(k) \cdot f(k) = \Omega(n) \text{?}$$
  In particular, since some of the theorists believe that computing $\mu(k)$ is not in $\mathsf{P}$, can we provide other $\mathsf{P}$ functions $f(k)$ which implies a linear growth in the summation? Can even better bounds be obtained?

There have been interesting developments on this problem, however Replacing $AC^0$ with ACC(2) (Namely allowing mod 2 gates as well) is still well out-of-reach. Some progress beyond Ben Green's theorem can be found in this MO question https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function as well as this one https://mathoverflow.net/questions/97261/mobius-randomness-of-the-rudin-shapiro-sequence . In addition, Jean Bourgain proved Mobius randomness for every monotone function $f$ (in terms of the binary-digit expansion).


Can all structurally recursive functions be written without explicit recursion using a catamorphism/fold? In particular, I am thinking of a function which involves conditionals changing the recursive behavior and multiple F-algebras.

halting_search :: int -> (a -> bool) -> (a -> a) -> a -> Maybe a
halting_search 0 f_test f_next_candidate candidate = Nothing
halting_search (S n) f_test f_next_candidate candidate = case (f_test candidate) of
  true => Just candidate
  false => halting_search n f_test f_next_candidate (f_next_candidate candidate)

Is this capable of being written just using the cata operator?  The reason I'm asking is because I want a functional language that is fairly expressive but not overly expressive, and it seems like one way to do that might be to not allow explicit recursion but make cata a primitive function.

Your function is completely structurally recursive on n, so it is pretty much just a change of notation to make it a catamorphism on the natural numbers.

type nat = Z | S of nat

(* cata : α → (α → α) → nat → α *)
let rec cata z s = function
  | Z -> z
  | S n -> s (cata z s n)

(* halting_search : nat → (α → bool) → (α → α) → α → α option *)
let halting_search n =
  cata (fun test next seed -> None)
       (fun recur test next seed ->
         if test seed then
           Some seed
         else
           recur test next (next seed))
       n

For languages with higher-order functions and strictly positive datatypes, having a fold is equivalent in expressive power to permitting structural recursion. However, it is not equivalent in terms of efficiency. If you just have fold, then implementing the predecessor function on the Peano natural numbers is O(n), whereas if you have a case form, it is O(1).

(* This is linear time! *)
pred : nat -> nat option
let pred n = cata None (function
                           | None   -> Some Z
                           | Some n -> Some (S n)) n


Hashing sets of integers for inclusion testing I'm looking for a hash function over sets H(.) and a relation R(.,.) such that if A is included in B then R(H(A), H(B)). Of course, R(.,.) must be easy to verify (constant time), and H(A) should be computed in linear time.

One example of H and R is:

$H(A) = \bigvee_{x\in A}  1 << (h(x) \mod k)$, where k is a fixed integer and h(x) a hash function over integers.
R(H(A), H(B)) = ((H(A) & H(B)) == H(A))

Are there any other good examples? (good is hard to define but intuitively if R(H(A), H(B)) then whp A is included in B).

Later edit:

I'm looking for a family of hash functions. I have many sets; 3 - 8 elements in each set; 90% of them have 3 or 4 elements. The example hash function I gave is not very well distributed for this case.
The number of bits of H(.) (in my example, k) which should be small (ie. H(.) must fit in an integer or long).
One nice property of R is that if H(.) has k bits then R(.,.) is true for (3^k - 2^k) / 4^k pairs, ie. for very few pairs.
Bloom filters are especially good for large sets. I tried using BF for this problem, but the optimum results were with only one function.

(crosspost from stackoverflow, I didn't receive an answer good enough)

(This answer was originally in comments but I'm moving it to a separate answer at Suresh's suggestion.)

For your application with very small sets you probably want the number of Bloom hash functions $k$ to be quite large to minimize the number of false positives. To save computation time I suggest the following variation of a Bloom filter. Assume you have three traditional hash functions $h_1$, $h_2$, $h_3$ for the elements that each produce $m$-bit strings. Hash each element to the bitwise and of these three hash functions. The resulting element hashes will be about $2^{-3}=1/8^{th}$ ones. Hash each set to the bitwise or of the hashes of its constituent elements. Because your sets have 3-8 elements the resulting hashes will be in the neighborhood of one-half ones, which is presumably what you want to best keep the false positive rate down.

The difference between the above scheme are the traditional Bloom filter is analogous to the difference between the classic $G_{n,p}$ Erdos random graph model and random $d$-regular graphs. The above scheme has the effective number $k$ of Bloom hashes vary a bit around its mean of $m/8$ but $m/8$ is pretty large so this difference shouldn't matter.


Existence of certain graph gadget related to coloring odd hole free graph Crossposted from MO.

Wondering about the existence of graph gadget related to coloring
(or 3-coloring) odd hole free graphs.

Let $G$ be simple $k$-chromatic connected graph with two
vertices $u,v$.

Is it possible $G$ to satisfy:

All induced $uv$ paths have odd order (even number of
edges).
In all proper $k$ colorings, $u$ and $v$ have distinct colors
(optional) $G$ doesn't contain induced $C_{2n+1}$ for $n>1$

If this is possible, there is reduction $F$ to odd hole free $F'$.

Replace an edge $u'v'$ by the gadget $G$ where $u'=u,v'=v$ and the
rest vertices of $G$ are new vertices.

According to graphclasses coloring odd hole free is NP hard
and 3-coloring is unknown.

Computer search suggest small gadgets don't exist (modulo errors).

One can extract an argument that this cannot work from the paper found by OP in the MO thread. Suppose $G=(V,E)$ is as required, and $c:V\to[k]$ is a $k$-coloring. By the assumption, $c(u)\neq c(v)$. Consider the (bipartite) subgraph $H$ induced by $\{x\in V\ |\ c(x)\in\{c(u),c(v)\}\}$.

If $u$ and $v$ are in the same connected component of $H$, pick any shortest path in $H$ between $u$ and $v$; it is an induced path in $G$, with colors alternating between $c(u),c(v)$, and must have an odd number of edges because the colors at its ends differ. This contradicts the assumption.

So $u,v$ are in different connected components; but then one can toggle the coloring of one of these components to obtain a coloring $c'$ with $c'(u)=c'(v)$, contradiction.


Does there exist a CAS for formal language theory? I need support for: grammars, equivalence classes, finite sets, and some smallest grammar approximation functions.

I am vaguely aware that it's possible to do some computations with formal languages in GAP, but I don't know the details, sorry.  There is a package "Automata", but I'm not sure if there's anything for grammars.


Conditions for NFA universality Consider a nondeterministic finite automata $A = (Q, \Sigma, \delta, q_0, F)$, and a function $f(n)$. Additionally we define $\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$.

Now lets analyze the following statement:

  If $\Sigma^{\leq f(|Q|)} \subseteq L(A)$, then $L(A) = \Sigma^*$.

It is easy to show, that for $f(n) = 2^n+1$ it is true, hence if the automata produces every word with length upto $2^{|Q|}+1$, then it produces $\Sigma^*$.

But does it still hold if $f$ is a polynom?

If not, what could a construction of a NFA $A$ for a given polynom $p$ look like, s.t. $\Sigma^{\leq p(|Q|)} \subseteq L(A) \subsetneq \Sigma^*$?

For the statement to hold, f must grow exponentially, even with the unary alphabet.

[Edit: The analysis is improved slightly in revision 2.]

Here is a proof sketch.  Suppose that the statement holds and let f be a function such that every NFA with at most n states that accepts all strings with length at most f(n) accepts all strings whatsoever.  We will prove that for every C>0 and sufficiently large n, we have f(n) > 2C⋅√n.

The prime number theorem implies that for every c < lg e and for sufficiently large k, there are at least c ⋅2k / k primes in the range [2k, 2k+1].  We take c=1.  For such k, let Nk = ⌈2k / k⌉ and define an NFA Mk as follows.  Let p1, …, pNk be distinct primes in the range [2k, 2k+1].  The NFA Mk has Sk=1+p1+…+pNk states.  Apart from the initial state, the states are partitioned into Nk cycles where the ith cycle has length pi.  In each cycle, all but one state are accepted states.  The initial state has Nk outgoing edges, each of which goes to the state immediately after the rejected state in each cycle.  Finally, the initial state is also accepted.

Let Pk be the product p1…pNk.  It is easy to see that Mk accepts all strings of length less than Pk but rejects the string of length Pk.  Therefore, f(Sk)≥Pk.

Note that Sk ≤ 1 + Nk⋅2k+1 = o(22k) and that Pk ≥ (2k)Nk ≥ 22k.  The rest is standard.


Are there [good/optimal] parallel comparison sorts? Comparing each pair of elements and sorting according to

[[number less than] minus [number greater than]] is a parallel comparison

sorting algorithm with a depth of $1$ comparison and $O\left(n^2\right)$ total comparisons.

By the AKS network, there is a parallel comparison sorting algorithm with

a depth of $O(\log(n))$ comparisons and $O(n\cdot \log(n))$ total comparisons.

1.
Are there any parallel comparsion sorts with a depth of

$o(\log(n))$ comparisons and $o\left(n^2\right)$ total comparisons?
2.
Are there any parallel comparison sorts with a depth

of $1$ comparison and $O(n\cdot \log(n))$ total comparisons?

(answering my own question)

1. $\:$ Yes

2. $\:$ No

Reference:

Tight Comparison Bounds On The Complexity Of Parallel Sorting

by Yossi Azar , Uzi Vishkin (1987)

publisher: Courant Institute of Mathematical Sciences, New York University

retrieved from http://archive.org/details/tightcomparisonb00azar (June 17, 2012)


How practical is Automata Theory? There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important topic and whether it still has applications in practice. Therefore undergraduate students might have trouble in understanding the importance of automata theory and might think it is not of any practical use anymore.

Is automata theory still useful in practice?

Should it be part of undergraduate CS curriculum?

Ever used a tool like grep/awk/sed? Regular expressions form the heart of these tools.
You'll be surprised how much coding you can avoid by principled use of regular expressions - in "practical projects", like an email server.
If you're a CS major, you'll definitely be writing a compiler/interpreter for a (at least a small) language. If you've ever tried this task before and got stuck, you'll appreciate how much a little theory (aka context free grammars) can help you. This theory has made a once impossible task into something that can be completed over a weekend. (And it won the inventor a Turing award - google BNF).
If you're a CS major, at some point, you need to sit back and think about the philosophical foundations of computing, and not just about how cool the next version of the Android API is. On a related note, it is the job of the university not to prepare you for the next 5 years of your life, but to prepare you for the next 50. The only thing they can do in this regard is to help you think - think of automata theory as one of those courses.


What are multiple rounds of SOS/Lasserre hierarchy? Is that the same as saying the one will try to generate a higher-degree "pseudo expectation functional" by solving a SOS-program ? Or is there a difference between the two things?

Or to take a different view,

We needed to show that the projector to low-degree polynomials has bounded hypercontractive norm. We start off defining the projector $\mathcal{P}_d$ as the map,
$$\mathcal{P}_d : ( \{ \pm \}^n \rightarrow \mathbb{R}   )  \rightarrow  ( \{ \pm \}^n \rightarrow \mathbb{R}  )$$
$$ f = \sum_{\alpha \subseteq [n] }\hat {f}_\alpha \chi_\alpha  \rightarrow f' = \sum_{\vert \alpha\vert \leq d } \hat{f}_\alpha \chi_\alpha$$

Where $\chi_\alpha = \prod_{i \in \alpha} x_i$

Then we show that the over the space of such ''$n-$variate Fourier polynomials" $f'$ with degree at most $d$, $\mathbb{E} [f'^4 ] \leq 9^d ( \mathbb{E} [ f'^2 ] )^2  $ (which is equivalent to showing that  $\Vert \cal{P} \Vert_{2 \rightarrow 4 } \leq 9^d$ )

So in the above context is the choice of ``4" what quantifies the number of "rounds" of Lasserre hierarchy used? (the above is called a degree-4 SOS proof!) (as in you can run the SOS-program trying to optimize the hypercontractive norm of an operator only for as large a value of $x$(here $4$) as for which above kind of hypercontractive bounds can be established?)
Since this hypercontractive bound on such projection operators is already proven as a theorem then what does the so-called "Tensor-SDP" algorithm achieve in terms of giving an "efficient certificate"?

Yes, that's exactly what it is: optimizing over higher degree pseudoexpectations. The results I think you refer to prove that the hypercontractive inequality holds when $f$ is replaced by a degree $4$ pseudo distribution over $\mathbb{R}^{\{-1,1\}^n}$, which is stronger than the classical theorem (see Lemma 2.10 in Boaz's notes). Specifically, the stronger Lasserre version of the inequality is that for any degree 4 pseudo expectation operator $\tilde{\mathbb{E}}$ over $f:\{-1,1\}^n\to \mathbb{R}$ we have

$$
\tilde{\mathbb{E}} [\|\Pi_d f\|_4^4] \leq 9^d \tilde{\mathbb{E}}[\|\Pi_d f\|_2^4],
$$
where $\Pi_d$ is the linear projection operator onto the span of degree $d$ polynomials on $\{-1, 1\}^n$, and for $g:\{-1, 1\}^n\to \mathbb{R}$, the $L^p$ norm is defined as
$$
\|g\|_p = (\mathbb{E}_{x} g(x)^p)^{1/p} = \left(\frac{1}{2^n}\sum_{x \in \{-1, 1\}^n} g(x)^p\right)^{1/p}.
$$

Equivalently, this means that the inequality can be proved in a weak proof system, the degree $4$ sum of squares proof system, which is the statement given in Lemma 2.10 in Boaz's notes. See the discussion after the statement of the lemma.

(Something that may be confusing is that there are two different classes of polynomials going on here. One is the degree $d$ polynomials on $\{-1, 1\}^n$: you should treat these as just a subspace of $\mathbb{R}^{\{-1,1\}^n}$. The other class of polynomials are the polynomials that arise in the sum of squares proof of the hypercontractive inequality. These are polynomials over the values of $f$.)

The reason this is interesting is that it gives a low degree sum of squares proof that the hypercube graph is a small set expander. Roughly speaking, the fact that the cube is a small set expander is one of the main ingredients of proving that certain instances of the unique games problem are "hard" for some weaker SDPs, for example for constant number of rounds of the Sherali Adams + SDP hierarchy (SA+SDP). I.e. on these instances SA+SDP overestimates how many constraints can be satisfied, and in some sense the reason is that it "does not know" that the hypercube is  a small set expander. (This is only a rough intuition, the hard instances for Sherali Adams are much more complicated than the hypercube.)

By contrast, because there is a low degree sum of squares proof that the hypergraph is a small set expander (again, I am oversimplifying a lot here, and there are many more ingredients you need), these same instances are not hard even for 8 rounds of Lasserre, i.e. the Lasserre SDP does not overestimate how many constraints can be satisfied in these instances. The precise statement of this result is Theorem 6.1. in the paper Hypercontractivity, Sum-of-Squares Proofs, and their Applications. This is interesting, because these were our best candidates for hard instances of unique games. Essentially, we do not know any distribution on unique games instances (or instances of the small set expansion problem) which are not solved with high probability by constant round Lasserre. You may take this as some evidence that unique games may not be hard after all.