Is there a way to solve an optimization problem where a decision variable shows up in an upper bound (or lower bound) of summation? minimize/maximize $\displaystyle \sum_{i=0}^{f(n)} G(x,n)$
s.t. $n \ge 1$ and $x$ in some feasible region

The decision variables are $x$ (a vector) and $n$ (a scalar).
How is this type of optimization problem classified?
Has it been studied? Any references?

Here is an example of how an unconstrained version of the problem arises:

"Optimizing capacity of buses, K, on a bus route"

The bus route is a loop. One point on
the loop is designated the “bus
station,” the only place passengers
can get on the bus.
Passengers can get off the bus at any
point on the bus route (other than
the bus station).
By the time a bus returns to the bus
station, all of its passengers will
have gotten off.
Passengers arrive by a Poisson
process with rate lambda (per hour).
A bus cannot take off from the bus
station until it has K passengers on
board.
There are N buses that operate on the
one route. When a bus arrives at the
bus station, it waits in line behind
buses that are already there. It’s a
FIFO system where the first bus in
line gets first K arriving
passengers, and so on…
When a passenger arrives at the
station, s/he gets on the first bus
in line and waits until enough
passengers have gotten on the bus to
make a total of K passengers before
the bus takes off. Passengers get on
the bus in a FIFO manner as well.
The waiting time for a passenger is
the length of time from when that
passenger arrived at the bus station
until a bus with that passenger on
board takes off.
The waiting time for a bus is the
length of time from when the bus
arrives at the station until it has K
passengers on board, at which point
it takes off.
It is assumed that the “loading” of
passengers takes zero time.
Also, it takes C(K) time for buses to
travel the length of the bus route. This is a function of K because there is time lost for each passenger that is dropped off.

What is the expected waiting time for passengers? For buses?

The optimization aspect is as follows. Bus drivers want to make the most amount of money in an hour. The higher K is, the more money a bus driver makes per trip on the bus route, but the number of trips per hour goes down. There is a monetary cost (to bus drivers) for each minute that a passenger waits at the stop for a bus (as in loss of goodwill). So the objective function is dependent on both the expected waiting time of buses (which determines how much money buses make per hour) and the expected waiting time of passengers.

I was able to get an expression for the expected waiting time of buses and it is of the form:

E[Waiting time for a bus] = $\displaystyle\sum_{j=0}^{KN} \frac{KN-j}{\lambda}\frac{(\lambda C(K))^j}{j!}e^{-\lambda C(K)}$

E[Waiting time for a passenger] = ??

I have not been able to get an expression for the waiting time of passengers, but I suspect it will also have the upper bound of summation as some function of K.

This problem is strongly reminiscent of "Optimal stopping" of stochastic processes.  These are frequently solved by dynamic programming.  References even to this specialized literature are extensive, due to its applications in decision theory and finance.


Max-Flow and Graph Orientation: Is there any algorithm that can orient undirected graph G(V,E) (i.e., assign directions to edges) to achieve maximum flow in the network? Any suggestion?

I assume you are given an undirected network $G$, and two vertices $s,t$, and you wish to maximize the flow from $s$ to $t$, while directing the edges of $G$. In this case, you can just use the normal Ford-Fulkerson algorithm with the following modification:

Every time you take an augmenting $s$-$t$ path in $G$ and send flow along it, direct the edges along the path. Eventually, your algorithm will stop, and all edges (except those with flow 0) will have a direction. The flow will be maximal, which can be proven using the max-flow-min-cut theorem.


Is it possible to unambiguously read back λ terms from interaction nets without node types? A class of lambda terms can be evaluated using Lamping's abstract algorithm - that is, converting them to interaction nets and applying a set of rules. In order to get the result, you have to read back lambda terms from normalized interaction nets. For example, this net:

Reads back as λλ(1 0), that is, the church-number 1. This net:

Reads back as λλ(1 (1 (1 (1 0)))), the church-number 4. This net:

Reads back as λλ((1 λλ(1 0)) ((1 λλ(1 (1 0))) ((1 λλ(1 (1 (1 0)))) 0))), the church list of the numbres 1, 2 and 3. The readback procedure is trivial, but it uses the tag annotations: λ for a lambda node, @ for an application, R for root, e for garbage, D for fan (duplication). Now, suppose that we erased those tags:

Is it possible, from the configuration of the net alone, to infer the tags and thus readback the same lambda term without them?

So, yes, turns out it is possible, as can be seen on the decode function of my abstract algorithm implementation here. Basically, Lambda and Apply nodes are given the same tag (here, I use 0), and you can infer which is the case based on their positions. Each Duplication node, though, requires an unique tag. Note some terms such as (2 2) will reduce to a net which has Duplication nodes with the same tag. That is not an issue; when decoding, just treat anything with a tag different from 0 as a Duplication node.


How did TCS become conference-oriented rather than journal-oriented? Disclaimer: I can only vouch for my research fields, namely formal methods, semantics and programming language theory. The situation is possibly different in other parts of the discipline.

It seems that TCS has become rather conference-oriented. Researchers aim at publishing in the next conference. Sometimes a journal version appears. Sometimes it doesn't.

In other disciplines (biology, mathematics, and most others I guess) this is unheard of. The effort put into writing the conference papers is a lot lesser, but in turn, the conference papers count a lot less. The "real deal" is the journal publication.

Arguing whether this situation is good or bad could result in a flame war, and doesn't have a precise answer. Instead, let's try a more factual question:

How did we become so conference-oriented? How did conference papers gain so much weight?

While I don't know the answer to this question, it seems crucial that the phenomenon isn't limited at all to theoretical computer science.  I believe SIGGRAPH plays the same sort of role for graphics, NIPS for machine learning, ISCA for architecture, etc. that STOC and FOCS play for theory.  Yet it's true that the emphasis on publication in conference proceedings is a striking feature of computer science as a whole, one that isn't shared by any other academic field that I know about.  (But maybe there are other such fields?)


A good Library for testing whether a minors exists in a graph? I would like to know if there are any free graph libraries for testing whether a specific set of minors exists in a given graph?

NAUTY can be used as a library to help you build a hashtable for the entire poset of graph minors for small $n$.  The key would be the cannonial form given by NAUTY and the value would be a concatenation in sorted order of the cannonical forms of it's direct minors.


What is the right theoretical model to design algorithms for current and upcoming high performance computers This question is similar to a more general question for what is the right theoretical model of a computer to design algorithm and data structures in.
Here, I ask specifically about current high performance computers (like the ones listed as the Top 500) or even about upcoming supercomputers.

Given that these computers are typically working on huge data sets (it seems that some people use such machines mainly because they have enormous combined main memory) aspects of the I/O-model (introduced by Aggarwal and Vitter in 1988) and its parallel version, the PEM (Arge, Goodrich,  Nelson and Sitchinava in 2008) should be present.
On the other hand, there should be something about communication, in particular punishing ultra small packages to all other computing nodes.

As you might imagine, I am not afraid that I am running out of ideas when creating a new model, but I am a little worried that I might overlook previous attempts in doing so, in particular because I have the impression that the years 1980-1995 or so saw many such modeling attempts (like BSP or bridging models) that seem to not have been widely used.

What models should I take a closer look at?

At PODC 2009, Bruce Hendrickson gave a phenomenmal invited talk about these issues.  (His slides don't appear to be online, but you might want to ask him if you could see them.)  I don't think there's a "right" model yet -- bonus for you! -- but I would suggest you look at his papers, especially the ones on the Graphs and Architectures page, where he tries to figure out how to handle enormous graphs with little structure (i.e. "modern" datasets) on massively multithreaded machines.


"long code test" and "dictatorship test" Why is "long code test" also called "dictatorship test"?

I got really confused when I read about it in Arora's survey.

"Long code" and "Dictator code" are two different names for the same code. Here's why:

Let's start with the natural definition of the long code: The message is an $n$-bit string $i$ (the reason I'm calling this $i$ and not $x$ becomes clear soon) and the encoding is a vector $y$ of length $2^{2^n}$ where the positions of $y$ are indexed by all possible Boolean functions that map $n$ bits to one bit. Moreover, $y$ at position $f$ is simply $f(i)$.

Now you can alternatively identify $f$ by its truth table. So you can also assume that the coordinate positions of $y$ are indexed by all possible strings of length $N := 2^n$ (i.e., all possible truth tables) and then $y$ at position $f=(f_1, \ldots, f_N)$ just encodes $f_i$.  So the $i$th codeword is the truth table of the $i$th dictator function (among the dictator functions mapping $N$ bits to one bit). So the long code and the dictator code are the same. In the long code interpretation, codewords correspond to $n$-bit points and codeword positions correspond to $n$-bit predicates. In the dictator code interpretation, codewords correspond to dictator functions on $2^n$ bits and codeword positions correspond to evaluation points.


Book Embedding Duality of Graphs The definition of Book Embedding on Wikipedia: "A book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. The vertices of the graph are required to lie on this boundary line, and the edges are required to stay within a single half-plane". Full definition is at (http://en.wikipedia.org/wiki/Book_embedding)

Planar embeddings have geometric duals, that has numerous algorithmic application. One of the very nice property of duality of planar graphs is that if $T$ is a spanning tree of a planar grpah $G$, then the set of edges not in $T$ in the dual is a spanning tree of the dual $G^*$. Is there any kind of similar geometric dual for book embeddings? Is there a similar property between the spanning tree of primal and dual graphs as in the planar case?

To keep things a little cleaner let's assume that the graph has a Hamiltonian cycle that's embedded along the spine so that each cell of the embedding lives within a single page. Also those spine edges are places where multiple cells meet so let's make them vertices as well.

Then, within each page of the book, the dual graph is a forest, with all vertices that are not adjacent to a leaf having degree three or more, and having the spine edge vertices as its leaves. So a book embedding with $p$ pages has a dual graph consisting of $p$ plane forests, sharing a common set of leaves in the same cyclic ordering as each other.

Whether this structure is useful for anything is a different question, of course.

As for your question about generalizations of planar graph decompositions into primal and dual spanning trees: I doubt something like that happens in book embeddings, but it can be generalized to embeddings of graphs onto non-planar manifolds. See my paper "Dynamic generators of topologically embedded graphs" (SODA'03).


Lower bounds for quantum circuits using the geodesic framework Some of us have been reading Michael Nielsen's paper on a geometric approach to using quantum lower bounds (in brief, the construction of a Finsler metric on $SU(2^n)$ such that the geodesic distance from $I$ to an element $U$ is a lower bound on the number of gates in a quantum circuit that computes $U$).

I was wondering if there were concrete examples of problems where this program led to a lower bound that came close to, matched or beat prior lower bounds obtained by other means ?

Not exactly what you are looking for, I know, but geodesics have been used to prove optimal state transfer rates in Ising spin chains (see arXiv:0705.0378). I'm not sure how related this is to Nielsen's approach, as I haven't read that particular paper, but I remember thinking this was quite a neat result when it first came out. Basically this is the minimum time to transfer a quantum state from one end of a linear array of qubits to the other. It is a very simple problem, but in the above paper they show that the transfer can be achieved significantly faster than was previously believed (although of course there is still a linear scaling, with the speed-up in the constant).


String version of even-odd partition problem Motivated by Hardness proof of EVEN-ODD PARTITION post I came up with a string version.

String even-odd partition

INPUT: $(x_{1,0},x_{1,1}),\dots,(x_{n,0},x_{n,1})$, i.e.,  $n$ pairs of strings over $\{0,1\}^*$

QUESTION: Does there exist $(b_1,\dots,b_n) \in \{0,1\}^n$ such that $x_{1,b_1} \cdots x_{n,b_n} = x_{1,1-b_1} \cdots x_{n,1-b_n}$?

Equivalently: for each pair, we can either swap the two strings or leave them alone; then we want to know if the concatenation of the left part of each pair can equal the concatenation of the right part of each pair.

Or, in other words, we are trying to partition every pair into two strings to obtain concatenated strings $W_{even} $ and $W_{odd}$  such that $W_{even}= W_{odd}$, where exactly one string from each pair goes to $W_{even}$  and the other goes to $W_{odd}$.  The selected strings have to stay in the same order they appear in the input.

It feels like this should be NP-complete by a reduction from even-partition problem but I can't find an explicit reduction; I am having difficulty in representing integers by appropriate strings.

  Is there a simple reduction to prove the NP-completeness of this string variant?

This was posted first on CS StackExchange.

It is possible to reduce from the "unshuffling a string" problem: given a string $w \in \Sigma^*$, decide whether $w$ is a shuffle square, i.e. $w$ is in the shuffle product of two identical strings. This problem is proved to be NP-complete for alphabet of size at least nine, see this question for references and discussion.

Here, for two strings $u$ and $v$  the shuffle product is defined as the set of all $w = u_1 v_1 \ldots u_i v_i$ for each representation $u = u_1 \ldots u_k$ and $v = v_1 \ldots v_k$ with $u_i, v_i \in \Sigma^*$ (i.e. $u_i$ and $v_i$ are strings, not letters).

The reduction is easy: given $w = a_1 \ldots a_n$, $a_i \in \Sigma$, take $x_{i, 0} = a_i$ and $x_{i, 1} = \epsilon$, where $\epsilon$ is the empty string. Then the answer in your problem (with alphabet of size nine) is YES if and only if $w$ is a shuffle square.

Finally, use an arbitrary prefix-free binary encoding of $\Sigma$, thus getting a reduction for the binary case.


Simulation modeling of diseases Can anyone recommend a good book(s) or journal article(s) on object-oriented program design patterns/principles and simulation modeling of diseases?

I received the above question this morning by email.  It was sent to a SIAM list service I belong to.  I don't know the asker, and I don't know a good answer either.  I figured, though, if some people here had good suggestions, either theoretical or practical, I could send him the link to this question.

Thanks.

Edit: I sent the asker a copy of this question, with Artem K's answer visible.  He responded, saying thanks.

My answer addresses the general theory of disease (and similar) modelling and only briefly touches on the implementations. For simulations (as opposed to analytic work, which usually uses evolutionary game theory or SIR models) the popular paradigm is agent-based modeling (ABM). A good recent book on agent-based modelling from a CS perspective is:

  Yoav Shoham and Kevin Leyton-Brown
  [2009], "Multiagent systems:
  algorithmic, game-theoretic, and
  logical foundations", Cambridge
  University press.

A big general conference of agent-based modeling is AAMAS (links to 2011 and 2012). They don't specialize in disease modeling in particular, but a lot of the techniques they use can be applied there.

In terms of software for doing rapid prototyping of ABMs, a popular one is NetLogo. This seems to be particularly popular in the social sciences, where they do slight variations of standard epidemic models to describe certain social processes.

Currently, it seems like the focus of theoretical work in this field (and this is obviously biased by my own interests) is to consider environments where agents are limited in their interactions. If you just have agents meet randomly, then ABMs are usually overkill and things can be done analytically. However, if there is some interesting network structure (fixed or dynamic) to the interactions (as there often is in real life) then ABMs become an essential tool. A fun recent book that discusses some of these ideas (once again from a CS perspective) is:

  David Easley and Jon Kleinberg [2010],
  "Networks, crowds, and markets:
  Reasoning about a highly connected
  world," Cambridge University press. (a
  draft is available
  online)


Geometric differencing The diff procedure can be generalized to operate on objects other than strings.
For instance, I imagine that computational geometry asks questions like: "Given two volumes, and allowed only the operations of union and subtraction of volumes, what (shortest) sequence of operations transforms the first volume into the second?"

Seems like to generalize diff beyond strings requires three things:
1) a space of objects on which to operate (these are strings in classic diff, but could be anything like surfaces, volumes, etc).
2) for any object, a decomposition of that object into components, along with an operation -, such that OBJECT1 - COMPONENT := OBJECT2. (e.g. "abcdef" - "de" := "abcf")
3) a binary operation of addition such that OBJECT1 + OBJECT2 = OBJECT3 ("abc" + "def" = "abcdef"). Also, closure under this property.

My questions:
Q1) Can you point me to any concrete incarnations of diff outside the string domain? For instance, what's the name of the computational geometry problem I described in the first paragraph? I'm sure there's extensive literature on this but I just don't know what to google.
Q2) Is there an algebraic structure which fits the structure of generalized diff?

In the realm of constructive solid geometry, questions like the one you asked can probably be answered. Here, solids are constructed by unions and differences of basic shapes (for example, a sphere with a tunnel can be described as Ball - Cylinder. Shapes are then built up as trees of operations on basic shapes (at the leaves), and the differencing problem can then be thought of as a labelled tree-diff problem (which has been examined among other things in the context of comparing XML documents).

I'm not claiming that these questions are already being studied, but CSG is definitely one place where the geometric questions you're asking might be addressed.


Church-Rosser property for dependently typed lambda calculus? It is well-known that the Church-Rosser property holds for $\beta \eta$-reduction in simply-typed lambda calculus. This implies that the calculus is consistent, in the sense that not all equations involving $\lambda$-terms are derivable: for example, K$\neq$I, since they don't share the same normal form.

It is also known that one can extend the result to pairs which correspond to product types.

But I wonder if one can further extend the result for dependently typed lambda calculus (perhaps) with polymorphic types, e.g. the Calculus of Constructions?

Any references would also be great!

Thanks

It might be useful to quickly give the counter-example to CR in typed calculi with $\beta$ and $\eta$:

$$ t=\lambda x:A.(\lambda y:B.\ y)\ x$$

And we have
$$ t\rightarrow_\beta \lambda x: A.x$$
and
$$ t\rightarrow_\eta \lambda y:B.y$$

It is immediate that if $A\equiv B$, then the two resulting terms are, in fact, $\alpha$ equivalent, but there is no reason for this to be the case, on untyped terms.

On typed terms, it's pretty clear that $A$ has to be equal to $B$ for the resulting term $t$ to be well-typed. The big difficulty that occurs is this:

  For dependently typed systems, confluence needs to be proven before type preservation!

This is because you need the property of $\Pi$-injectivity
$$ \Pi x:A.B=_{\beta\eta}\Pi x:A'.B'\ \Leftrightarrow\ A=_{\beta\eta}A'\wedge B=_{\beta\eta} B'$$
in order to prove inversion, which is required to prove preservation/subject reduction.

So you can't even prove that $\beta\eta$-reductions preserve types without confluence, but confluence doesn't even hold on untyped/ill-typed terms!

Breaking out of this vicious circle requires some technical tricks, which are hard to summarize here, but arguably the simplest to understand is to simply stop being interested in $\eta$-reductions, but instead concentrate on $\eta$-expansions: $t\rightarrow_{\eta*}\lambda x:A.t\ x$

Of course, you need to restrict this rule to non-$\lambda$ and non-applied terms to even hope to get termination, but with these restrictions it seems that the reduction behavior is much better behaved, and the meta-theory works out without too many problems. A good reference seems to be Neil Ghani, Eta-Expansions in Dependent Type Theory.

A different, and recently quite popular approach, is described by Abel, Untyped Algorithmic Equality for Martin-Löf's Logical Framework with Surjective Pairs.


Formal Semantics of Programming Languages I'm new to programming languages theory and I'm seeking for a good resource on a resource for formal semantics  of programming languages. Specifically looking  for structural operational semantics. I got some book recommendations. But I'm looking for a resource in a  more introductory level. Especially tutorials, web-site and free book recommendations are  welcomed.

Looking at the operational semantics course at my University gives the following three:

Andrew Pitts's lecture notes
Gordon Plotkin's Aarhus notes on structural operational semantics
Matthew Hennessey's The Semantics of Programming Languages

Ohad.


Cryptography protocols using graph problem instances I personally am only aware of basic examples of public key cryptography and I haven't studied cryptography yet. I'm curious if there are circumstances in cryptography where using problem instances from graph theory are preferred to number theory, when building challenges.

(Side question: is number theory generally preferred because the data is more concise and the primitives might be faster in implementation?)

Number theory (along with neighboring "algebraic" areas like lattices and group theory) gets used for public-key crypto because the problems for which we know distributions on instances that (a) are hard and (b) have trapdoors are most naturally stated algebraically. This stands in contrast to the symmetric key setting: a much wider range of natural candidates for one-way functions (which don't require trapdoors) exist.

I imagine one can turn algebraic problems into graph-theoretic ones via the reductions which prove NP-completeness. But those transformations just make the representations more cumbersome -- they don't obviously provide any security advantages.

The eprint paper linked to by Sasho Nikolov in the comments is a good place to look for one of the very few combinatorial alternatives.


On the relation for the Myhill-Nerode theorem/syntactic monoid of a language In order to characterize regular languages one finds the following definition useful:

  Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\equiv_L$-related, and write $x\equiv_L y$ if for all $z\in\Sigma^*$, $xz\in L$ if and only if $yz\in L$.

This is useful because $\equiv_L$ is an equivalence relation for every language $L$, and a language is regular if and only if the index of $\equiv_L$ (that is, the number of equivalence classes) is finite, as per Myhill-Nerode.

Now, I would like to define a binary operation $\cdot$ on $\Sigma^*_{/\equiv_L}$ as: $[x]\cdot[y]=[xy]$, where $[x]$ is the $\equiv_L$-equivalence class of $x$. This $\cdot$ will be operation that will give $\Sigma^*_{/\equiv_L}$ the structure of a monoid.

My question is: Is $\cdot$ well defined for an arbitrary language? How do I prove it?

So far, my approach has been trying to prove that the definition above is equivalent to:

  Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\sim_L$-related, and write $x\sim_L y$ if for all $w,z\in\Sigma^*$, $wxz\in L$ if and only if $wyz\in L$.

This is simple for regular languages, since one can take a minimal DFA and analyze its behaviour with strings that are $\sim_L$-related, but I'm struggling with a general proof. Maybe I'm missing something really simple, but in the paper where I found the "definition" of syntactic monoid, they just take $\Sigma_{/\equiv_L}$ and say "this is the monoid" without specifying the operation, and now that I'm trying to do it with full detail I'm completely stuck. Thanks in advance for your help!

The syntactic monoid of a language $L$, which is $\Sigma^{\ast}$ quotiented by $\sim_{L}$, is usually bigger than the set of equivalence classes of $\Sigma^{\ast}$ quotiented by $\equiv_{L}$. Informally, the Myhill-Nerode relation $\equiv_L$ only cares about the prefixes of a word $w$ (since it reflects the processing of $w$ by a DFA), while the syntactic monoid has to encode the information about all possible infixes of $w$ (otherwise you won't get the algebraic structure $[x]\cdot[y]=[x \cdot y]$)


When does randomization speed up algorithms and it "shouldn't"? Adleman's proof that $BPP$ is contained in $P/poly$ shows that if there is a randomized algorithm for a problem that runs in time $t(n)$ on inputs of size $n$, then there also is a deterministic algorithm for the problem that runs in time $\Theta(t(n)\cdot n)$ on inputs of size $n$ [the algorithm runs the randomized algorithm on $\Theta(n)$ independent randomness strings. There must be randomness for the repeated algorithm that is good for all $2^n$ possible inputs]. The deterministic algorithm is non-uniform - it may behave differently for different input sizes.
So Adleman's argument shows that - if one doesn't care about uniformity - randomization can only speed-up algorithms by a factor that is linear in the input size.

What are some concrete examples where randomization speeds up computation (to the best of our knowledge)?

One example is polynomial identity testing. Here the input is an n-sized arithmetic circuit computing an m-variate polynomial over a field, and the task is to find out whether the polynomial is identically zero. A randomized algorithm can evaluate the polynomial on a random point, while the best deterministic algorithm we know (and possibly the best that exists) evaluates the polynomial on many points.

Another example is minimum spanning tree, where the best randomized algorithm by Karger-Klein-Tarjan is linear time (and the error probability is exponentially small!), while the best deterministic algorithm by Chazelle runs in time $O(m\alpha(m,n))$ ($\alpha$ is the inverse Ackermann function, so the randomization speed-up is really small). Interestingly, it was proved by Pettie and Ramachandran that if there's a non-uniform deterministic linear time algorithm for minimum spanning tree, then there also exists a uniform deterministic linear time algorithm.

What are some other examples?
Which examples do you know where the randomization speed-up is large, but this is possibly just because we haven't found sufficiently efficient deterministic algorithms yet?

I don’t know whether randomization “should” or “shouldn’t” help, however, integer primality testing can be done in time $\tilde O(n^2)$ using randomized Miller–Rabin, while as far as I know, the best known deterministic algorithms are $\tilde O(n^4)$ assuming GRH (deterministic Miller–Rabin) or $\tilde O(n^6)$ unconditionally (variants of AKS).


randomness extraction of real valued sequences of numbers I have a sequence of numbers $x_1, x_2, \dots, x_n, \dots \in \mathbb{R}$ I would like to extract fair bits from that sequence.

My first thought was to use the Von Neumann extractor.  For a sequence of 0 and 1,

divide sequence into pairs
eliminate all occurrences of 00 and 11
apply transformation 01 → 1 and 10 → 0

This produces a sequence of fair bits from biased bits *even if you do not know the bias $p = \mathbb{P}[x_i = 1]$ as long as your sequence is

a Bernoulli trial
independently distributed
identially distributed

The sequence of numbers I have is the hourly readings from a sensor, so it exhibits cyclic behavior every 24 hours + every week.  If I compute the expected value over time, it may be possible to subtract out the daily and weekly cycles leaving sequence of loosely self-correlated real numbers.

How can I extract randomness from here in a simple way?

First, it depends how the quantization of the real values is performed.
Using 8 bits can be really different from using 16 for example.

Assuming that a fixed number of bits is chosen, hash functions are a good and simple way to extract randomness.

Universal Hash Functions are families of hash functions that can be securely used in this context (not all hash functions are suitable for this).


What is "Synthetic Network" in Network Science? I checked out several articles, books available, but didn't find what exactly is a "synthetic network".

It's difficult to answer if you don't explain more precisely the context, but I think it would be networks generated using some random model such as Watts-Strogatz's, Barabasi-Albert's, etc.


Graph families which have polynomial time algorithms for computing the chromatic number Post updated on 31st of August: I added a summary of the current answers below the original question. Thanks for all the interesting answers! Of course, everyone can continue posting any new findings.

For which graph families there exists a polynomial time algorithm for computing the chromatic number $\chi(G)$?

The problem is solvable in polynomial time when $\chi(G) = 2$ (bipartite graphs).
In general when $\chi(G) \ge 3$, computing the chromatic number is NP-hard, but there are many graph families where this is not the case. For example, colouring cycles and perfect graphs can be done in polynomial time.

Also, for many graph classes, we can simply evaluate the corresponding chromatic polynomial; some examples in Mathworld.

I suppose most of the above is common knowledge. I would gladly learn whether there are any other (non-trivial) graph families for which the minimum graph colouring is solvable in polynomial time.

In particular, I am interested in exact and deterministic algorithms but feel free to point out any interesting randomized algorithms or approximation algorithms.

Update (Aug 31):

Thanks to everyone for submitting interesting answers. Here's a short summary of the answers and references.

Perfect and almost perfect graphs

Geometric Algorithms and Combinatorial Optimization (1988), Chapter 9 (Stable sets in graphs).  Martin Grotschel, Laszlo Lovasz , Alexander Schrijver.

Chapter 9 of the book shows how to solve the coloring problem via the minimum weighted clique covering problem.
Since they rely on the ellipsoid method, these algorithms may not be very useful in practice. Also, the chapter
has a nice reference list for different classes of perfect graphs.
Combinatorial Optimization (2003), Volume B, Section VI
Alexander Schrijver.

This book has three chapters devoted to perfect graphs and their polynomial time colourability. I took only a quick look but the basic approach seems the same as in the previous book.
A characterization of b-perfect graphs (2010).
Chinh T. Hoàng, Frédéric Maffray, Meriem Mechebbek

Graphs with bounded tree-width or clique-width

Edge dominating set and colorings on graphs with fixed clique-width (2001).
Daniel Kobler, Udi Rotics

The algorithms here require a k-expression (an algebraic formula for constructing a graph with a bounded clique-width) as a parameter. For some graphs, this expression can be computed in linear time.
Yaroslav pointed out in methods for counting colourings in bounded tree-width graphs. See his answer below.

These two study graph families where $k$ vertices or edges can be either added or deleted.

Parameterized complexity of vertex colouring (2003).
Leizhen Cai.

Colouring can be solved in polynomial time when adding or deleting $k$ edges (for fixed $k$) in split graphs.
Parameterized coloring problems on chordal graphs (2006).
Dániel Marx.

For fixed $k$, chordal graphs to which $k$ edges are added, can be coloured in polynomial time.

Graphs not containing particular subgraphs

Deciding k-Colorability of P5-Free Graphs in Polynomial Time (2010).
Chính T. Hoàng, Marcin Kamínski, Vadim Lozin, Joe Sawada, Xiao Shu.
3-colouring AT-free graphs in polynomial time (2010).
Juraj Stacho.

Colouring quadtrees

Algorithms for coloring quadtrees (1999).
David Eppstein, Marshall W. Bern, Brad Hutchings.

As you observe, all perfect graphs can be colored in polynomial time, but I think the proof involves ellipsoid algorithms for linear programming (see the book by Grötschel, Lovász, and Schrijver) rather than anything direct and combinatorial. There are a lot of different classes of graphs that are subclasses of perfect graphs and have easier coloring algorithms; chordal graphs, for instance, can be colored greedily using a perfect elimination ordering.

All locally connected graphs (graphs in which every vertex has a connected neighborhood) can be 3-colored in polynomial time, when a coloring exists: just extend the coloring triangle by triangle.

Graphs of maximum degree three can be colored in polynomial time: it's easy to test whether they're bipartite, and if not then either they require only three colors or they have K4 as a connected component and require four colors (Brooks' theorem).

Triangle-free planar graphs can be colored in polynomial time, for the same reason: they are at most 3-chromatic (Grötzsch's theorem).


How do I referee a paper? Updated below

We all know the critical importance of peer-review.  It is the main form of quality control and feedback on research.  However, to an early-stage researcher (like me), it can sometimes be a confusing system/process.

Accordingly, there are several treatises on the scientific refereeing process that give guidance.  Two (very different) examples from computer science -- this 1994 article by Parberry and a more recent one by Cormode -- offer great advice (though the latter might be a shade mischievous).

Here, I'd like to solicit broader advice from the more experienced members of this community about the review process, with particular regard to the peculiarities of theoretical computer science.

What are the main criteria for determining the significance of a paper's results?  How do I judge whether a paper should be accepted to the conference/journal? Is it important to verify correctness?
What are the main elements of a referee report, and which parts are most important? Is it always necessary to give a recommendation of (non)acceptance? What goes in the report and what goes solely to the editor?
How does assessment for conferences differ from that in journals?  How do reports for conferences differ from those in journals? (How on earth do I rate my "confidence" in my recommendation?) Should the journal version be significantly different from the conference paper?
What if I don't understand the paper? ...the proof?  (Is it my fault or theirs?)
What about typographical/grammatical mistakes? What if there are a lot of them?
How much time should I spend on a report?
How many reports a year am I expected to write? When is it acceptable to refuse a request to referee?

Of course, any other relevant questions and answers on this topic are encouraged, since this is CW.

This question is inspired by (stolen from) a similar post at MathOverflow.

Update 15/02/2011:

I am still very interested in getting more input on this question especially with regard to reviewing conference papers and program committee membership. (These two roles are themselves different beasts, and both very unlike being a referee for a journal article, IMO.)  Granted, program committee membership is rarer than refereeing or reviewing (and it hasn't been my privilege yet), but is a responsibility that every researcher in theoretical computer science must take on eventually.

Time.  How much time am I expected to spend as a committee member or conference reviewer?  Given the probability that I could get ten or perhaps many more to handle in the space of a few weeks, how do I avoid running out of time?  What are the most important things to spend time on?
Confidence.  What if the paper is too far from my area of expertise?  What factors should go into nominating/asking someone else to review a submission?  If it is not too far from my area of expertise and I elect to review it, when is it permissible to give a confidence rating of 1?
Criteria.  There are critical differences between journals and conferences.  Some very important papers are not published in journals.  Some very important papers did not previously appear in conferences.  What are the most significant distinctions in criteria on which to assess papers in these settings?
Recommendations.  Inherently, there are fewer recommendations that can be offered to the authors of a conference paper, primarily due to space and time constraints.  Also, there is usually only one round of review.  Another consideration is that my report becomes public to the entire strong committee.  What is the scope of suggestions/directives that I can offer?

As before, if you think I've missed out on asking any particular questions, do let me know, or edit directly.  This is CW, after all.

These new thoughts are partly motivated by reading a paper that Suresh mentioned on his blog.

To the best of your knowledge, does the paper make a significant, well-presented, and correct contribution to the state of the art?  If the paper fails any of the three criteria, it's fair to reject it for that reason alone, regardless of the other two.
Here's what I think a report should contain.  Everything should be visible to the author, except possibly for serious accusations of misconduct.

a. A quick summary of the paper, to help the editor judge the quality of the results, and to help convince both the author and the editor that you actually read and understood the paper.  Place the result in its larger context.  Include a history of prior versions, even if the authors include it in the submission.  Be respectful, but brutally honest.

b. A discussion of the strengths and weaknesses of the paper, in terms of correctness, novelty, clarity, importance, generality, potential impact, elegance, technical depth, robustness, etc.  If you suspect unethical behavior (plagiarism, parallel submission, cooked data), describe your suspicions.  Be respectful, but brutally honest.

c. A recommendation to the editor for further action — accept, accept with minor revision, ask for a second round of reviewing, or reject outright.  Keep in mind that you are making a recommendation, not a decision; if you can't make up your mind, just say so.  Be respectful, but brutally honest.

d. More detailed feedback to the author — more detailed justification for your recommendation, requests for clarification in the final version, missing references, bugs in the proofs, simplifications, generalizations, typos, etc.  Be respectful, but brutally honest.
Conference reports should be shorter; program committees have hundreds of papers to consider at once.  Whether there should be a difference between conference and journal papers is up to the journal (and indirectly, up to the community).  Most theoretical computer science journals do not insist on a significant difference; it is quite common for the conference and journal versions of a theory paper to be essentially identical.  When in doubt, ask the editor!
If you still don't understand the paper after making a good-faith effort, it's the author's fault, or possibly the editor's, but certainly not yours.  The author's primary responsibility is to effectively communicate their result to their audience, and a good editor will send you a paper to referee only if they think you're a good representative of the paper's intended audience.  But you do have to make a good-faith effort; do not expect to immediately understand everything (anything?) immediately on your first reading.
If there are a lot of errors, don't even read the paper; just recommend rejection on the grounds that the paper is not professionally written.  Otherwise, if you really want to be thorough, include a representative list of grammar, spelling, and punctuation mistakes, but don't knock yourself out finding every last bug.  Be respectful, but brutally honest.
Expect to spend about an hour per page, mostly on internalizing the paper's results and techniques.  Be pleasantly surprised when it doesn't actually take that long.  (If it takes significantly less time than that, either the paper is either exceedingly elegant and well-written, you know the area extremely well, or the paper is technically shallow.  Don't confuse these three possibilities.)
You should write at least as many referee reports as other people write for you.  If this takes more time than writing your own papers, you're not spending enough time on your own papers.


Meaning of program as solution of a recursive equation I would like to ask you a question about (denotational?) semantic of program. After defining program as a transition system, and the semantics as a transition function: $$next: States \rightarrow States$$
the author stated that the meaning of program is the solution of the equation:
$$ P = next \circ P $$
which is given by:
$$ fix(\lambda f.next \circ f) $$
I could not get the idea here, what is the "meaning"? and why it is the solution of that equation? How it is related to Tarski's fixpoint theorem?

Could anyone explain for me or give me some references to read about it?
Thanks in advance.

"Meaning", or "semantics" to use the more technical term, is only the understanding you wish to associate with the
text of the program.  It can be a mathematical function that specifies
abstractedly what the program computes (denotational semantics), or it
can be a formal description of how the computation is conducted by a
formally defined machinery (operational semantics). It is really a
matter of what you are interested in expressing. The program is a big
formula, and there are many way in which you may want to interpret it.

You may even be interested in so-called non-standard interpretation
that may express specific properties of the program, such as well
typedness.  Even a prettyprinter, that gives you a string of
characters corresponding to a nicely presented version of the program
text can be seen as an interpretation, a meaning for it (however trivial). It is much in
the eyes of the beholder.

However, the definition of a meaning cannot be arbitrary. It is
expected to obey some rules so that it can be used constructively. In
particular, a program or formula is produced by composition, by using
formal operators to build larger formulae from smaller parts. A
meaning, or semantics is expected to follow these compositional rules,
so that you can somehow define the meaning of the whole from the
meaning of the components. The use high order functions makes the
constraint more manageable than appears.

The concept is applicable to other formal structures. For example, the
syntax of a programming language is usually defined by a grammar. The
grammar can have a meaning that is the set of program (strings) that
can be written according to that grammar. It could also be the set of
parse-trees for those programs.

Now a standard meaning of program is what it computes, or how it does
it (again, partly for consistency reasons, the distinction is often
in the eyes of the beholder, depending somewhat on what you do with
that formal meaning).

Coming back to your example:

The function $next$ defines what it is to execute one step of
the program. Its meaning is a function (on a mathematical
domain of states) that gives you the next state after a step of
computation given the current state. By applying this function
repeatedly,  starting from the initial state of your computation, you
will ultimately get to a final state that gives you the result ... or
computes indefinitely (depending on whether that computation is
supposed to terminate).

This means that the effect of running your program is to apply the
function :  $ next \circ  next \circ next \circ next \circ ...$
this composition being as long as necessary for all steps of the
calculation at hand, possibly infinitely many.

This is better expressed by the fixed-point equation:  $P = next \circ P$
since from it you can derive :

$P = next \circ next \circ P$
$P = next \circ next \circ next \circ P$
$P = next \circ next \circ next \circ next \circ P$
and so on

It shows that any function $P$ satisfying this equation will provide as
many steps as needed, applying the function $next$, to get the
computation you want to describe.

Now, this requires a minimum of mathematical apparatus to work
properly, for the equation to have a mathematical meaning.  The mathematical domains used are supposed to allow you to talk about
approximating a function. For example a finite composition of $n$
application of the function $next$ is an approximation of $P$ for when the
program needs no more than $n$ steps to do its work. Typically, a
lattice of ever better approximations will do that (this is what
monotonicity is about: getting ever better approximations, as you
increase the number of applications). Furthermore, you need this
lattice to be continuous, so that the monotonically increasing infinite sequence of
approximations of $P$ will have a limit, which is actually the meaning
of $P$.

In practice, all this is usually described in a more formal mathematical way,
as done for example in the answer of @tathanhdinh.

This technique of approximations can be used as well to describe data structures that contain loops, actually implemented with pointers, though the semantics may not want to know about pointers.


VC dimension of intersection of half-spaces Define $$l_i(x) := \text{sgn} \left( w_i^\top x - b_i \right)$$

for $i=1,...,n$, where $x \in \mathbb{R}^d$.

Then define the classifier

$$ g(x) := \max \{ l_1(x),..., l_n(x) \}$$

which represents the intersection of $n$ linear functions and hence a convex polytope in $\mathbb{R}^d$ with $n$ facets.

What is the VC dimension of the family of all $g$ of this form?

I found that an upper bound is $2 (d+1) n \text{log}_2( (d+1)n ).$

It has been recently shown by Csikos, Kupavskii, Mustafa
in "Optimal Bounds on the VC-dimension" that the VC dimension of $k$-fold unions (or intersections or XORs) of half-spaces in $R^d$ behaves as
$$ \Theta(dk\log k).$$


Potentially stronger form of non-$ETH$ If we have a $2^{n^a}$ algorithm to $K$-$SAT$ where $a<1$ for all $K>2$ then $ETH$ fails and literature gives consequences. What are the consequences if $a=o(1)$?

If $\alpha \in O\left(\frac{\log\log n}{ \log n}\right)$, then you would have proved that $P = NP$, since $n^{\alpha} \in O(\log n)$ and $2^{n^{\alpha}} \in O(\mathrm{poly}(n))$.

On the other hand, for $\alpha \in \omega\left(\frac{\log\log n}{ \log n}\right)$ and $\alpha \in o(1)$, I think the most interesting thing that happens is breaking ETH with all its consequences (including breaking SETH and many other conditional lower-bounds on polynomial and parameterized problems).


Can we replace deterministic part of alternative turing machine with some other equivalent machines? I'm sorry if it is a low level question but I am so confusing.

If $DTime(n)\subseteq \Sigma_2Time(n^{0.2})$ then $DTime(n) \subseteq \Sigma_2DTime(n^{0.2})$

Is this true that $\Sigma_2DTime(n^{0.2})\subseteq\Sigma_2\Sigma_2Time((n^{0.2})^{0.2})=\Sigma_4Time(n^{0.04})$

I picked up DTime in alternative machine and replaced it with $DTime(n)\subseteq \Sigma_2Time(n^{0.2})$  and replacing  n with $n^{0.2}$.

I think you need to work on what $(0.2)^2$ is before you go any further.


The maximum number of induced cycles in a simple directed graph Is the maximum number of induced circuits in a simple directed graph known?

I tried the family of graphs suggested by David and the number of induced cycles is seems to be exactly

$3^{n/3} + \frac{n}{3}$

*tested up to n=51 (for each n multiple of 3).

I don't know what's already known but the obvious bounds are that it is at most $\binom{n}{n/2}$ (Sperner's theorem) and at least $3^{n/3}$ (for $n$ a multiple of three that is at least 9: form a cycle of three-vertex sets and add all edges between vertices in consecutive triples). These bounds hold both for the directed and undirected cases.

The $3^{n/3}$ bound turns out to be the right one, to within a polynomial factor at least, for both the directed and undirected cases. To see this, choose a starting vertex in one of $n$ ways (or a starting edge in the undirected case), and then greedily choose the remaining vertices of the cycle one by one. At each step where you have $k$ choices (the remaining neighbors of the most recently chosen vertex), each choice eliminates all those $k$ vertices from the remaining subproblem, because they can no longer be part of any induced cycle extending what you've already chosen. So, if you define $C(i)$ to be the maximum number of extensions that you could still make, given that you have $i$ remaining vertices, then this number obeys the recurrence $C(i)\le\max_{k\le i} kC(i-k)$. The maximum value of $k$ in this recurrence is given for $k=3$, giving $C(i)\le 3^{i/3}$.


How can DES have 6x4 S-Boxes and still be reversible? Wouldn't data be lost when mapping 6-bit values to 4-bit values in DES's S-Boxes? If so, how can we reverse it so the correct output appears?

DES is a Feistel-based cipher. In such ciphers, the function $\rm F$ need not be invertible. Here's the reason:

In each round, the following operation is applied:

For $i =0,1,\dots,n$

$L_{i+1} = R_i$

$R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$

Decryption is performed as follows:

$R_{i} = L_{i+1}$

$L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$

As you can see, the decryption does not need $\rm F$ to be invertible. (Since the decryption does not need to compute $\rm F^{-1}$.)


Dual to hypercontractive inequality Recall the hypercontractive inequality:

Let $\rho = \sqrt{\frac{p-1}{q-1}}$, then $||T_\rho(f)||_q \leq ||f||_p$

In https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf it is stated that the dual of the hypercontractive inequality is equivalent to the following:

If $f$ has degree at most $d$, then

$||f||_q \leq \rho ^ d ||f||_p$

I am unable to show this (Specifically, the direction that the original version implies the dual version), and would like to help.

Attempt-

We know for every $g$, $||T_\rho(g)||_q \leq ||g||_p$

Plugging $g = T_{\frac{1}{\rho}}(f)$,

$||f||_q \leq ||T_{\frac{1}{\rho}}(f)||_p$

Now if $p=2$ it's clear how to finish since it's clear how $T_{\frac{1}{\rho}}$(f) affect the fourier coefficients, and it's clear how the fourier coefficients relate to the $l_2$ norm. However for $p\neq 2$, it's not clear to me how to show $||T_{\frac{1}{\rho}}(f)||_p \leq \frac{1}{\rho ^d} ||f||_p$, or even relate the norms.

I will note the proof that the dual implies us works well here (I can provide more detalis if needed, but I don't think it will help).

I'm not sure that the statement you want is known to hold in full generality (if you look at O'Donnell's website, he remarks that what he stated in that survey is not in fact known to be true in full generality). That said, it does hold for $q\geq 2\geq p\geq 1$. Let's suppose the Hypercontractivity Theorem holds as you have stated, i.e. for $q\geq p\geq 1$, suppose for $\rho=\sqrt{\frac{p-1}{q-1}}$, we have
\begin{equation}
\|T_{\rho}f\|_q\leq \|f\|_p.
\end{equation}

To use this statement to get this revised version (or almost, you forgot to take the reciprocal of $\rho$), suppose $q\geq 2$ and first take $p=2$, so $\rho^{-1}=\sqrt{q-1}$. As you seem to have figured out, hypercontractivity gives
\begin{align}
\|f\|_q^2&=\|T_{\rho}T_{\rho^{-1}}f\|_q^2\\
&\leq \|T_{\rho^{-1}}f\|_2^2\\
&=\sum_{k=0}^d \rho^{-2k}W_k(f)\\
&\leq \rho^{-2d}\sum_{k=0}^dW_k(f)\\
&=\rho^{-2d}\|f\|_2^2\\
&=\sqrt{q-1}^{2d} \|f\|_2^2,
\end{align}
where $W_k(f)$ is the level-k Fourier weight of $f$, and we use Parseval and the degree assumption. Taking squareroots yields $\|f\|_q\leq \sqrt{q-1}^d\|f\|_2$ in this simple case.

We also have for $1\leq p\leq 2$
\begin{align}
\|f\|_2^2&=\langle f,f\rangle\\
&\leq \|f\|_p\|f\|_{p/(p-1)}\\
&\leq \|f\|_p\sqrt{p/(p-1)-1}^d \|f\|_2\\
&=\sqrt{\frac{1}{p-1}}^{d}\|f\|_p\|f\|_2,
\end{align}
where we use Holder's inequality and then the case we just proved with $q=p'=p/(p-1)$. Putting this together with the previous case, we conclude for all $q\geq 2\geq p\geq 1$, that
\begin{equation}
\|f\|_q\leq \sqrt{q-1}^d \|f\|_2\leq \sqrt{\frac{q-1}{p-1}}^d \|f\|_p,
\end{equation}
as claimed.

According to O'Donnell's website, this paper gives the state of the art on this problem (though I haven't looked through it).


Graph embedding which maximizes minimum angle Given a planar graph, one can   embed it in linear time crossing free into an $n \times n$ grid.
I am interested whether any efficient algorithms are known to straight line embed a planar graph crossing free into a $n^c \times n^c$ grid, for some small $c$, such that the minimum angle between two edges is maximized?

I don't think any such algorithm is known. The results I know about maximizing the minimum angle in straight line drawings of planar graphs are:

Every planar graph has a (possibly nonplanar) drawing in which the minimum angle is inversely proportional to the maximum degree. For the main proof idea and some references, see http://11011110.livejournal.com/230133.html
There exist planar graphs of degree d such that the minimum angle in any straight line planar drawing is $O(\sqrt{(\log d)/d^3})$. This result is due to Garg and Tamassia, "Planar drawings and angular resolution: algorithms and bounds", ESA '94. They also show that achieving near-optimal angles with a grid drawing may require a grid of exponential area.
Every planar graph has a planar drawing in which the minimum angle is bounded by a function of its degree. This can be shown using the Koebe-Andreev-Thurston circle packing theorem. For a reference to a slightly stronger version of this result (showing that every planar graph of bounded degree has a planar drawing with a bounded number of edge slopes) see http://11011110.livejournal.com/205447.html


The number of cliques in a graph: the Moon and Moser 1965 result I'm looking for the full text of the Moon and Moser 1965 clique result On Cliques in Graphs (there exist graphs with a number of maximal cliques exponential in $n$). My university's paywall doesn't have access to the particular journal. (In fact, the preview provides the first few sentences of the proof, but then leaves me without the rest!)

I was interested in this result related to a research direction I was pursuing, but the direction has changed slightly, so admittedly my interest is now purely academic curiosity.

My question is:

  Is there a link to the full text of the paper somewhere OR another paper that sketches the proof OR if a proof sketch is short enough to reproduce here, does anyone know it? Also, I'm interested in the class of graphs with an exponential number of cliques.

I added the BibTeX for reference:

@article {springerlink:10.1007/BF02760024,
   author = {Moon, J. and Moser, L.},
   affiliation = {University of Alberta Edmonton Canada},
   title = {On cliques in graphs},
   journal = {Israel Journal of Mathematics},
   publisher = {Hebrew University Magnes Press},
   issn = {0021-2172},
   keyword = {Computer Science},
   pages = {23-28},
   volume = {3},
   issue = {1},
   url = {http://dx.doi.org/10.1007/BF02760024},
   note = {10.1007/BF02760024},
   year = {1965}
}

I don't have a copy of Moon & Moser at hand, but: the maximum number of distinct maximal cliques in an $n$-node graph (with $n>1$) is $3^{n/3}$, $4\cdot 3^{(n-4)/3}$, or $2\cdot 3^{(n-2)/3}$, according to the value of $n$ mod 3. I think it's a little easier to see this in the complementary form of counting maximal independent sets.

The lower bound is what you're really asking for, and is mostly given already in the comments above: form a graph from the disjoint union of copies of $K_2$ and $K_3$, using as many copies of $K_3$ as possible. Each maximal independent set has exactly one node from each of these complete subgraphs from which the formula follows.

I seem to recall that the upper bound proof of Moon and Moser involved transforming a graph into the lower bound form (or the complementary form for maximal cliques), at each step not decreasing the number of independent sets or cliques. But there's a different way of proving it that leads to worst-case-optimal backtracking algorithms for listing all the cliques or independent sets (see e.g. my paper arXiv:cs/0011009), which I'll only sketch here because the details are a bit tedious. If there's a vertex $v$ of degree three or more in the given graph $G$, then each maximal independent set of $G$ is either a maximal independent set in $G\setminus v$ or it includes $v$ and is a maximal independent set of the graph formed from $G$ by removing $v$ and all of its neighbors. By induction (plugging in the formula for the number of independent sets in these two smaller graphs, with some case analysis mod 3) the bound follows. On the other hand, if no high degree vertex exists then the graph is a disjoint union of paths and cycles, in which one can calculate the number of independent sets directly.


PAC learning boolean conjunctions Kearns and Vazirani (chapter 1) describe an efficient algorithm for PAC learning conjunctions of boolean variables $x_1, x_2, \ldots, x_n$, which starts with the hypothesis $$h=x_1\wedge\overline{x_1}\wedge x_2\wedge\overline{x_2}\cdots x_n\wedge\overline{x_n},$$
and, on each call to an oracle that returns a positive example $a$, removes literals from $h$ to make it consistent with $a$. That is, if $a_i=0$, then you remove $x_i$ from $h$, otherwise you remove $\overline{x_i}$ from $h$.

However, if we don't receive enough examples, $h$ will still be unsatisfiable -- as it was at the beginning. So what are we supposed to do in this case? Remove some "problematic" literals at random?

Thanks for your help!

The first positive example will remove enough literals so that the conjunction will become satisfiable.  For example if the first positive example is $x_1\overline{x_2}x_3$ this removes $\overline{x_1}$, $x_2$ and $\overline{x_3}$. So the only time you will end up with an unsatisfiable clause is if you get only negative examples, which is okay, as the correct thing to do is to classify everything as negative anyway.

Also remember that in PAC learning, the learner gets to choose how many examples to see -- so you generally don't have to worry about "not getting enough examples" (as long as you need a number of examples polynomial in the number of relevant parameters).


Are both safety and liveness properties closed under finite intersection? Given two safety properties $P_1$ and $P_2$, is their intersection $P_1 \cap P_2$ also a safety property? Similarly, if $P_1$ and $P_2$ are liveness properties, is $P_1 \cap P_2$ also a liveness property?

Safety properties are closed under finite intersection. This can be seen by following Alpern and Schneider's characterisation which showed that safety properties are limit-closed when viewed topologically.

Liveness properties as defined by Alpern and Schneider are dense. They are not closed under intersection as soon as there are two elements in the state space. Consider the two-element state space $\{0,1\}$. For state $i$ define $a_i$ as the set of infinite sequences of states that have a suffix consisting of $i$ only. Each $a_i$ is a liveness property but $a_0 \cap a_1 = \emptyset$ cannot be a liveness property because it's not dense.


Is CoC inconsistent with cnat_ind axiom? It is not possible to derive induction for Church-encoded datatypes on the Calculus of Constructions (source). Moreover, according to the accepted answer to another question, it is also not possible to derive induction for Church-encoded datatypes on CoIC, despite the presence of inductive datatypes. As such, I wonder if we assume induction for Church-encoded Nat, cnat_ind; that is:

cnat_ind :
  (n : CNat) ->
  (P : CNat -> Type) ->
  (S : ∀ (n : CNat) -> P n -> P (csucc n)) ->
  (Z : P czero) ->
  P n

where CNat, csucc and czero are the usual Church-encoded Nat type and constructors, would that allow us to inhabit the empty type ∀ (P : *) -> P?

One way to show that it is consistent to add cnat_ind is to internalize parametricity, i.e., we extend the type system with enough structure so that it can prove its own parametricity, from which it then follows that the Church encoding of natural numbers does indeed give natural numbers. See for instance the PhD dissertation Internalizing Parametricity by Guilhem Moulin.


Minimum Unsatisfiable Core Recently in a course I'm taking, we have been learning about the DPLL(T) algorithm for SMT solving. The basic outline goes like this:
DPLL_T(F)
  G = B(F) // where B is the boolean abstraction function
  while (true) do
    A,out = SAT-solver(G)
    if (out = UNSAT) then return UNSAT
    else
      out = T-solver(B'(A)) // where B' is the inverse of B and T is a theory solver
      if (out = SAT) then return SAT
      else G = G and !B(MinimalUnsatCore(B'(A))

This is all fine, but I struggle with the last line, MinimalUnsatCore(). Specifically, the  Minimal Unsatisfiable Core was defined as:

An Unsatisfiable Core $C$ of $A$ contains a subset of atoms in $A$ such that $B'(C)$ is still unsatisfiable.
A Minimal Unsatisfiable Core (MUC) $C^*$ has the property that if you drop any single atom of $C^*$ from $A$, the result is satisfiable.

The description for finding the MUC was that you must drop each atom from $A$, one by one, if the result of dropping a particular atom is satisfiable, then that atom must be in the MUC. This is fine, say, if there were only one conflict, for example:
$$(x = z) \wedge (x > z) \wedge (y = z)$$
The MUC would be $\{(x= z), (x > z)\}$. However if we added another contradiction unrelated to this core:
$$(x = z) \wedge (x > z) \wedge (y = z) \wedge (y > z)$$
Then at any point if we drop one individual atom, then $A$ is still not satisfiable because removing any one atom will still leave a contradiction. How do we remedy this to see that there are multiple MUCs? Can we still do this in linear time w.r.t. the number of atoms in the boolean abstraction? If not, what's the time complexity of finding all the MUCs?
See page 43 here: https://web.stanford.edu/class/cs357/lectures/lec9.pdf
MUCs are referred to as part of the concept of "Minimizing Learned Clauses". Specifically the method discussed on page 44.

If this isn't the correct place for this question (maybe better over at Math.SE or CS.SE?), please let me know.

First thing to say that the minimality here is subset-minimality (as opposed to cardinality-minimality). Observe that minimality is not actually needed. The main objective is to block the assignment A, which led to the conflict. However minimality is beneficial because like this you block other "bad" assignments as well.

Similarly, multiple MUCs are not a problem. All we need is to block the  assignment A so picking an arbitrary MUC is sufficient. Note also that the number of MUCs can be exponential, so going through all of them might not even be feasible and typically is not done in this context.

To compute an MUC there're various algorithms. The easiest is to go through each literal L in the set and remove it. If the set is still UNSAT, then move onto the next literal. If the set is SAT, put the literal L back (it's needed).  If I may shamelessly plug in my paper, here's more algorithms [1].

[1] Minimal Sets over Monotone Predicates in Boolean Formulae. J Marques-Silva, M Janota, A Belov. CAV13


Conversion between k-SAT and XOR-SAT According to XOR Satisfiability Solver Module for DPLL Integration by Tero Laitinen, we need $2^{n-1}$ CNF clauses to convert an $n$ literal XOR-SAT clause if we do not want to increase the number of literals. So, I understand that the computational cost for converting an XOR-SAT expression into a strictly CNF $k$-SAT is exponential.

My question: What is the computational cost if I want to reverse the process? What is the computational cost of converting a CNF $k$-SAT expression into an XOR-SAT one? I assume the promise that in this case only the $k$-SAT expressions with equivalent XOR-SAT expressions are considered.

If all XOR relationships between variables in CNF formulas could be detected in polynomial time, then this would allow the solution of UNAMBIGUOUS-SAT in polynomial time.  By the Valiant–Vazirani theorem this result would imply that NP = RP.

To solve UNAMBIGUOUS-SAT, recall that $a \oplus b$ implies $a \neq b$.  Find the XOR relationship between each pair of variables and use the results to divide the variables into two groups of equivalent variables.  Once this is done, only two test assignments are required to determine satisfiability.

In the limited case of recovering XOR relationships encoded in the usual way, i.e.

$a \oplus b \oplus c$

to

$
\lnot a \lor b \lor c \\
a \lor \lnot b \lor c \\
a \lor b \lor \lnot c \\
\lnot a \lor \lnot b \lor \lnot c
$

this can be done in polynomial time by sorting the clauses followed by a linear-time scan.


Examples of pedantry in TCS Larry Wasserman has a recent post where he talks about the "p-value police". He makes an interesting point (all emphasis mine) (the premise in italics that I added, and his response below it):

  The most common complaint is that physicists and journalists explain
  the meaning of a p-value incorrectly. For example, if the p-value is
  0.000001 then we will see statements like “there is a 99.9999% confidence that the signal is real.” We then feel compelled to correct
  the statement: if there is no effect, then the chance of something as
  or more extreme is 0.000001.

  Fair enough. But does it really matter? The big picture is: the
  evidence for the effect is overwhelming. Does it really matter if the
  wording is a bit misleading? I think we reinforce our image as pedants
  if we complain about this.

Which got me thinking -

  Are there good examples of pedantry in TCS ? Such an example would
  consist of

  A claim that is commonly made in the popular press
  A standard correction that people insist on making
  The correct "big picture" that the claim does capture even while being imprecise.

  where the claim is mathemtically wrong  but "morally right" and the
  correction is technically correct but doesn't change the intuitive
  understanding.

To lead things off, my example would be:

Claim - NP-complete problems take exponential time to solve
Correction - No in fact we just don't know if they can be solved in polynomial time
Big picture - NP-complete problems are HARD

Caution: I know there are many on this forum whose head will explode at the idea of claims that are wrong but "morally correct" :). Remember that these are statements targeted towards the public (where some degree of license can be permitted), rather than statements made in a research paper.

Hm, its tough even to think of examples of claims about TCS that make it to the popular press.

One thing I have seen occasionally is the claim that factoring is NP-hard, when explaining cryptography. This is related to the less innocuous error of claiming that quantum computers can solve NP hard problems, but restricted to the context of cryptography, this is a relatively mild error. The point is just that we (users of cryptography) seem to believe that there is no efficient algorithm for solving the problem. The particular conjectures we use to justify this assertion are besides the point.


Is this language recognizable by a 3 symbols TM in O(n log n)? I was playing with the very interesting and still open question "Alphabet of single-tape Turing machine" (by Emanuele Viola) and came up with the following language :

$L = \{ x \in \{0,1\}^n \text{ s.t. } |x| = n = 2^m \text{ and } count1(x) = k * m; \; n,m,k \geq 1 \}$

where $count1(x)$ is the number of $1$s in the string x.

For example, if x = 01101111 then n = 8, m = 3, k = 2; so $x \in L$

Can L be recognized by a Turing Machine with a single tape and a 3 symbols alphabet $\{ \epsilon, 0, 1 \}$ in $O(n \log{n})$ steps ?

If we use 4 symbols the answer is yes:

check if $|x|=2^m$ replacing $0$s with $\epsilon$ and $1$s with $2$ and at the same time store $m$ $1$s on the right;
then count the number of $2$s modulo $m$ in $O(n \log{n})$.

For example:

....01101111....... input x  (|x| = 8 = 2^3)
000.021.1212.0001.. div 2, first sweep (000. can safely be used as a delimiter)
000.022.1222.00011. div 2, second sweep
000.022.2222.000111 div 2, third sweep --> m = 3 (= log(n) )
000..22.2222....111 cleanup (original 1s are preserved as 2)
000..22.2221102.... start modulo m=3 calculation
000..22.2210022.... mod 3 = 2
000..22.2000222.... mod 3 = 0
000..22.0012222.... mod 3 = 1
000..20112.2222.... mod 3 = 2
000..11122.2222.... ACCEPT

Can't you use the same idea as what you have for the case of 4 symbols, with the following modifications:

Always process a pair of symbols simultaneously.
In your "div 2" sweeps, mark a two-symbol block as "processed" by mapping $(00, 01, 10, 11) \mapsto (\epsilon0, \epsilon1, 0\epsilon, 1\epsilon)$. You still have $\epsilon\epsilon$ available as a "separator" that you can use at both ends, and you can recover the original data easily.
Use a similar trick for "mod 2" steps.

In general, you can squeeze in arbitrarily large amount of bookkeeping information with the help of the third symbol by processing $O(1)$ symbols at a time.


Bitcoin and preventing double spending in decentralized digital currencies A recent approach to creating a decentralized online currency, called Bitcoin, has been generating some interest. The goal is to have a way to transfer currency without a central authority and without double spending or counterfeiting. Their approach is to have all the nodes in the network try to verify a transaction by doing a proof-of-work computation and then the transactions with the most verification are considered official. If an attacker wants to forge the official record (to reverse their first spending and use the coin again), then they must have the majority of the computing power in the network. The biggest downside is that in this scheme, the record of all transactions must be public, which the author assumes is a must:

The only way to confirm the absence of a transaction is to be aware of all transactions. In the mint based model, the mint was aware of all transactions and decided which arrived first.  To accomplish this without a trusted party, transactions must be publicly announced

Is it obvious that all transactions must be publicly known in any such scheme? More broadly: is there any cstheory/crypto research on decentralized digital currencies or related ideas?
Notes
I cross-posted to crypto.SE after a meta discussion.

There has been a lot of work done in this area. A good survey is the first chapter of "Handbook of Financial Cryptography and Security" (for the crypto) and the seventh chapter (for a survey of technologies).

The first scheme to prevent double spending and not require a public global transcript is, to my knowledge, by Chaum, Fiat and Naor [Crypto 88]. In their model, users obtain digital cash that is unlinkable to their identity but if they double spend the coin, then with high probability it will reveal their identity when the coins are eventually returned to the bank. CFN is very inefficient and there has been much work on improving it.


Problem in deterministic time $n^p$ and not lower I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable).

I'm interested in a concrete example, languages of the type " Given $M,x,1^n$ is M printing 1 on input x in less than $n^p$ steps" is known not to belong in $DTIME(n^{p-1})$ but it's very hard to understand why intrinsically it is not in $DTIME(n^{p-1})$.

To my knowledge it is a big open question to find such an explicit $L$, so I'm fine with languages conjectured to be in such classes.

I'm also interested if you replace deterministic time with space, non deterministic time, or probabilistic time, but it should remain polynomial.

Edit: More generally I'm also trying to avoid problems which can be shown to be equivalent to simulations of TM. Unless the lowerbound does not use this fact.

One example of a problem i'd be interested in could be something like "is this graph planar ?". Unfortunately this problem is known to be solvable in linear time.

For many years researchers have studied pebbling problems and emptiness/reachability problems.  Some of these problems have known unconditional resource lower bounds.

Such a problem $X$ is typically shown to have unconditional time complexity lower bounds by reducing the simulation of an $n^k$-time bounded Turing machine on a given input to an instance of $X$.  The time hierarchy theorem can then be applied to obtain the lower bound.

Here are two examples:

Pebbling games: A. Adachi, S. Iwata, T. Kasai. Some Combinatorial Game Problems Require Omega(n^k) Time. 1984
Intersecting one context-free language with k regular languages OR Intersecting k tree languages:  J. Swernofsky  and  M.  Wehar. On  the  complexity  of  intersecting  regular,  context-free, and tree languages. 2015

It's worth noting that there is a parameterized complexity class called $XP$ which contains parameterized problems that are solvable in $n^{f(k)}$ time.  A parameterized problem $X$ is $XP$-complete if every $XP$ problem is $fpt$-reducible to $X$.  There are a few known $XP$-complete problems.  Each $XP$-complete problem $X$ satisfies the property that there exist unbounded functions $f$ and $g$ such that for every $k$, $k$-$X \in DTIME(n^{f(k)})$ and $k$-$X \notin DTIME(n^{g(k)})$.

There are some parameterized problems $Y$ with finer reductions where we know that there exist $c_1 > 0$ and $c_2 > 0$ such that for all $k$, $k$-$Y \in DTIME(n^{c_1 k})$ and $k$-$Y \notin DTIME(n^{c_2 k})$.

Here is a post about the search for $XP$-complete problems: A list of XP-hard problems

I suspect that we could find a pebbling or reachability problem where it is solvable in cubic time, but not quadratic time (maybe intersecting three tree languages could work?).  However, this would require quite a bit of care and careful investigation of the existing Turing machine simulations.

This is a topic that I am very interested in.  Please always feel welcome to reach out if you would like to discuss this in more detail.  Thank you!


How to prove relations between "classes" of types? After reading Effects as Sessions, Sessions as Effects, I was wondering how would a proof of equivalence between both take place, or even, a proof of Sessions types being a Type and Effect System.

In a more generic fashion, how one can prove a relation (e.g. equivalence) between different "classes"* of types? Would that expressiveness test as done by Orchard and Yoshida be enough?

[*]: I don't know how to correctly define it, I don't want to use "kinds of types" or "types of types".

One approach to such questions is via encodings.

Say you have a language $L_1$ and a language $L_2$ and you want to show that they are somehow "the same", you can do this by finding an encoding

$$
   \newcommand{\SEMBTYPE}[1]{\ulcorner #1 \urcorner}
   \newcommand{\SEMB}[1]{\lbrack\!\lbrack #1 \rbrack\!\rbrack}
    \SEMB{\cdot} : L_1 \rightarrow L_2
$$

and then show that for all $L_1$ programs $M, N$ the following holds:

$$
   M \cong_1 N
   \qquad \text{iff} \qquad
   \SEMB{M_1} \cong_2 \SEMB{M_2}
$$

Here $\cong_i$ is a chosen notion of program equivalence for $L_i$. In order to do this for typed languages, one typically also maps $L_1$-types to $L_2$ by way of a function $\SEMBTYPE{\cdot}$ which is extended to typing environments, such that
something like the following holds:

$$
   \Gamma \vdash_1 M : \alpha
   \qquad \text{implies} \qquad
   \SEMBTYPE{\Gamma} \vdash_2 \SEMB{M} : \SEMBTYPE{\alpha}
$$
Here $\vdash_i$ is the typing judgement for $L_i$.
The whole approach is called full abstraction.

In order to avoid the "curse of Church-Turing universality", one typically imposes conditions on $\SEMB{\cdot}$, e.g. that it's compositional, or closed under injective renaming. The more conditions $\SEMB{\cdot}$ meets, the stronger the full abstraction result.

This is also Orchard & Yoshida are attempting to do (Theorems 1- 5), although they don't quite achieve it.


Is "meeting/room planning" NP-complete? Short summary: The problem is to assign people to meetings at different days while respecting the capacities and (inter-day) constraints of the meetings. Each person can only attend at most one meeting at a day.

I don't know if this problem has a common name - therefore the weird title question, sorry. If I overcomplicated any part of the problem definition, let me know.

People P = $\{p_1, .., p_n\}$, Meeting days D = $\{d_1, .., d_m\}$,

Meetings for each day: $M_{d_1} = \{m_{d_1,1}, .., m_{d_1,a}\}, M_{d_2} = \{m_{d_2,1}, .., m_{d_2,b}\}, .., M_{d_m} = \{m_{d_m,1}, .., m_{d_m,z}\}$
The $M_{d_i}$'s are pairwise disjoint.
Each meeting $m$ can hold a maximum number of people of $\text{cap}_{m}$ (capacity),

A person must not attend two (or more) meetings at different days that are "similar". (These conflicts are only between different days ("inter-day conflicts"). There are no conflicts within a day.)
Therefore define meeting constraints $C=\{c_1,..c_q\}$. Every meeting $m$ has exactly one corresponding constraint $c_i = \text{const}(m)$, s.t. [$\text{const}(m_i) = \text{const}(m_j)$] iff. [$m_i$ is "similar" to $m_j$] for all meetings.

There are preferences which person wants to attend which meeting at a particular day, e.g.:
(here 2 preferences are specified - if we generalize it to a fixed $K$ does the problem get any harder with regards to NP-hardness etc?)
$\text{Prefs} = \{$
$(p_1, \color{red}{d_1}, m_{\color{red}{d_1}, \color{green}{2}}, m_{\color{red}{d_1}, \color{green}{4}}),$ // Person 1 wants to attend the $\color{green}{2nd}$ or $\color{green}{4th}$ meeting at $\color{red}{day 1}$
$(p_1, d_3, m_{d_3, 1}, m_{d_3, 2}),$
$(p_3, d_2, m_{d_2, 2}, m_{d_2, 3}),$
$..$
$\}$, where:
a) every person-day combination $(p_i, d_j, ..)$ appears at most once.
b) every tuple has the form: $(p_i, \color{red}{d_j}, m_{\color{red}{d_j}, a}, m_{\color{red}{d_j}, b})$, with $a \neq b$ ($\widehat{=}$ valid preferences only)
(Note: The meeting preferences for each person-day combination are not supposed to be in any order, so (.., .., $x$, $y$) does not mean $x$ is preferred over $y$.)

A valid solution to the problem is:
Assign each person-day combination $(p_i, d_j, X, Y) \in \text{Prefs} $ to the meeting X or the meeting Y or no meeting at all, s.t.:
a) for every meeting $m$: we don't assign more people to $m$ than its capacity.
b) for every person $p$: for every constraint $c$: the person $p$ is assigned to (at most) one meeting with constraint $c$. (Otherwise, $p$ would attend two meetings at different days that are "similar".)

We want to maximize the number of person-day combinations that are assigned to a meeting. (So minimize the number of person-day combinations that are assigned to no meeting at all.)

Is this problem in $P$? (If yes, what is the idea for a polynomial-time algorithm?)
Is this problem NP-hard? (I tried a reduction from Bin-Packing $\leq_p$ ThisProblem, but without success. I think it's NP-hard and would appreciate any helpful ideas for reductions.)

While my initial instinct was also that the problem should be NP-hard, it looks like it might be close to a problem in P, namely list coloring on graphs whose blocks, or 2-connected components, are cliques. I am not sure to what extent this is helpful, because when you solve the reduced instance all meetings will be filled to capacity, which is an additional constraint on your problem. But if the rest of the argument holds up this might have workarounds, so I will state the partial progress.

If sensible, this reduction does not need to know which day a meeting happens to fall on, so I am using more relaxed notation (dropping the info about which day the meeting was on).

Introduce cap$_m$ vertices $$\{v_m^{(1)}, v_m^{(2)}, \ldots, v_m^{(c_m)}\}$$ for every meeting $m$. Let $M_r$ denote the set of all meetings $m$ that are associated with the constraint $c_r$. the edge set involves a big clique on all vertices involved in representing $m \in M_r$, that is, $$E = \{ (v_p^{(i)},v_q^{(j)}) | p,q \in M_r \}$$
$$\color{red}{\cup \{(v_p^{(i)}, v_q^{(j)})| p, q \text{ are meetings at the same day})\}\text{  [see comment below]} }.$$

The color pallette has one color for every person, and the list asssociated with a meeting vertex is the set of all people for whom the meeting is on their preference list.

A valid list coloring in the graph will fill all meetings to full capacity, and will never assign the same person to similar meetings, and will always give a person a meeting that they wanted to be in.

Some things to note:

The meetings will be filled to capacity, so this is not a completely accurate reduction. The simplest fix is to ask for a partial coloring, but I am not sure about the complexity of this question.  One could make the same copies of every meeting an independent set, and add a complete partite structure across meetings with the same constraint. Now, the color corresponding to a person can be repeated within a meeting. However, I am not completely sure that the graph structure now allows for the Ptime algorithm! The other fix would be to introduce junk colors in the pallette, but then some people may not get assigned to meetings at all.
The reduction works with longer preference lists, too.
Conflicts within the same day can also be handled with this modelling.

And this paper mentions that list coloring can be resolved in polynomial time when the blocks of the graph are cliques.


Is there any work combining machine learning and the more exotic forms of complexity theory? It seems to me that machine learning/data mining experts are familiar with P and NP, but rarely talk about some of the more subtle complexity classes (e.g. NC, BPP, or IP) and their implications for effectively analyzing data. Is there any survey of work doing this?

There is some inherent difference or dissimilarity of approaches between the two fields of applied machine learning and TCS/complexity theory.

Here is a recent workshop on the subject at the Center for Computational Intractability, Princeton with lots of videos.

  Description: Many current approaches in machine learning are heuristic: we cannot prove good bounds on either their performance or their running time. This small workshop will focus on the project of designing algorithms and approaches whose performance can be analyzed rigorously. The goal is to look beyond settings where provable bounds already exist.

Workshop: Provable Bounds in Machine Learning — August 1-2, 2012

In TCS a main area of study of "learning" sometimes maybe confusingly even also called "machine learning" is called PAC theory which stands for Probably Approximately Correct. its early 1980s origin predates much more modern research into "machine learning." wikipedia calls it part of the field computational learning theory. PAC often concerns results of learning boolean formulas given statistical samples of the distributions etc and the achievable accuracy of learning given various algorithms or limited samples.  This is studied in a rigorous theoretical way with tie-ins to complexity classes.  But it is not so much an applied study & wikipedias page on machine learning does not even list it.

The Computational Complexity
of Machine Learning PhD thesis by Kearns
Xing slides on (PAC) machine learning


is it by Chebychev's inequality? Let x be random variables with mean zero and variance 1.
Let n be natural number, t>0, C>0.
Let also $P(x^2\geq n)\geq C/(n^t)$.
Show, if $t\geq4$, then $P(x^2\geq n)\leq C/(n^2)$.

I got so fare, that with $t\geq 4$,
$\frac{C}{n^t}\leq \frac{C}{n^2}\leq P(x^2\geq n)\leq \frac{Ex^4}{n^2}$. But how to find bound on $Ex^4$?

Suppose to the contrary that
$$ P(x^2 \geq n_i) \geq C/n_i^2 $$ for some infinite sequence $n_1$, $n_2$, $\ldots$, $n_i$, $\ldots$, with $P(x^2 > n_i) > 2P(x^2 > n_{i+1})$. Then we have $$ Var(x) = \int_{x=0}^\infty x^2 d \mu.$$
But now, let's set $n_0 = 0$ and break this integral up into
$$ Var(x) = \sum_{j=0}^\infty \int_{n_j}^{n_{j+1}}x^2 d \mu.$$
We have$$ \int_{n_j}^{n_{j+1}} x^2 d\mu \geq n_j^2 \int_{n_j}^{n_{j+1}} d\mu = n_j^2(P(x\geq n_j)-P(x \geq n_{j+1})) \geq C/2.$$
This shows that the integral diverges, contradicting the variance being 1.


Simply-stated restriction on imperative programming language that captures the elementary functions? The language of while programs can express the computably enumerable functions.  (This is true even if the only arithmetical operations on variables are, say, incrementation and decrementation.)

If while is replaced by for, making loops always bounded, the language can then express only the primitive recursive functions.

I recently became aware of the class of elementary functions, which are strictly below the primitive recursive functions, but still strictly above the exponential hierarchy.

Obviously it would be possible to define an imperative programming language which captures exactly the elementary functions, say by introducing operators for bounded sum and product.  However, my question is,

  Is there a syntactic change to the language of while programs which restricts it to the elementary functions and which can be stated as simply as the (while -> for) restriction to primitive recursive functions?

A restriction on for programs instead would also suffice, of course, and perhaps I should clarify that I'm not looking for something that is absolutely as simply-stated, just something with comparable simplicity which does not require the addition of extra operators or the like.

Edit: An example of a representative for language is PL-{GOTO} from Brainerd and Landweber's "Theory of Computation" (1974), in which each program has a finite but unrestricted number of variables, each of which can contain a natural number, and which consists essentially of the following commands:

X <- 0 (assign 0 to a variable)
X <- Y (assign the value of Y to X)
X <- Y + 1 (assign the successor of the value of Y to X)
LOOP X; ... END; (repeat the contained block of code X times; does not alter X)

The authors give a proof that this can express exactly the primitive recursive functions.  The language PL does not match the question perfectly, as it uses GOTO instead of while, and PL-{GOTO} is derived from PL by removing GOTO from it.  However, PL programs are just as powerful as while programs, and this GOTO-removal transformation is just as simply stated as replacing while with for.  (Arguably perhaps even a bit simpler.)

Edit 2: http://en.wikipedia.org/wiki/Total_Turing_machine suggests this result goes back to: Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.

According to a classic result of Meyer and Ritchie (mentioned in the paper cited in the question), the elementary functions are characterized by LOOP programs in which the nesting depth of for-loops is restricted to be at most 2.


Alan Turing Documentaries To celebrate Alan Turing 100th birthday, I want to watch a documentary about his life.  However, there are several documentaries to choose from.
Which documentary about Alan Turing is your favorite?
Please include only one documentary per answer.

a leading one is Codebreaker with a list of reviews/publicity here [unfortunately several are behind paywalls]. here is one web review by chris harvey & with quotes by the writer warner.

this documentary originated by channel 4 seems balanced and avoids hagiography, looking at all the aspects of his complex life. has award winning writer, actors and acclaimed producer.


Oracles which put integer factorization in P I'm compiling a list of as many problems (decision or function) as I can find such that, if I had an oracle that could solve the problem in P, then integer factorization would also be in P.

Here is a partial list that I have already compiled. Most of these are fairly straight-forward, I would be interested in some which are a little more obscure. I've also omitted some of the more obvious ones (e.g. an oracle which produces a random prime, or the smallest prime, which divides $n$). In each case $n$ represents the integer to be factored, which is assumed to be a non-square composite, and $i,j$ are positive integers.

There are several related functions depending on what response is returned by the oracle (instead of just 1 or 0) or by swapping less than or below with greater than or above, etc. In general, I am only including one from each case:

Decision Problems on $i$

$f_1(i) = 1$ if $i$ is less than the smallest prime factor of $n$, and $0$ otherwise.
$f_2(i) = 1$ if $i$ is greater than the largest prime factor of $n$, and $0$ otherwise.

Function Problems on $i$

$g_1(i) = $ the sum of the number of factors below $i$.
$g_2(i) = 1$ if the number of factors below $i$ is odd, $0$ otherwise.
$g_3(i) = $ the sum of the factors below $i$.
$g_4(i) = $ the sum of non-factors below $i$.
$g_5(i) = $ the distance from $i$ to the nearest factor of $n$.
$g_6(i) = (i!,n)$ the greatest common divisor between $i!$ and $n$
$g_7(i,j) = $ the power of i in $j!$

Function problems on $n$

$h_1(n) = $ the sum of the factors of n.
$h_2(n) = $ the ratio of $q/p$ where $p$ and $q$ are the innermost factors (closest above and below $\sqrt{n}$).
$h_3(n) = \phi(n)$ Euler's totient function

(This is shameless self-promotion.) If you don’t mind either assuming the generalized Riemann hypothesis (for $L$-functions of quadratic Dirichlet characters) or using randomized polynomial time, then the following search problems work:

Given integers $n,a$ such that the Jacobi symbol $\left(\frac an\right)=1$, output either a square root of $a$ modulo $n$, or a nontrivial factor of $n$.
Any PPA-complete problem, such as: given a circuit $C\colon\{0,1\}^m\to\{0,1\}^m$ computing an involution (i.e., $C(C(x))=x$ for every $x\in\{0,1\}^m$) such that $C(1^m)=1^m$, output an $x\ne1^m$ such that $C(x)=x$.
The weak pigeonhole principle: given a circuit $C\colon\{0,1\}^{2m}\to\{0,1\}^m$, output $x\ne y\in\{0,1\}^{2m}$ such that $C(x)=C(y)$.


Computing distances with approximation less than 2 in general graphs? Given a weighted undirected graph with $m = o(n^2)$ edges, I would like to compute distances of approximation less than 2 between any given pair of vertices. Of course, I would like to use subquadratic space and sublinear query time.

I am aware of Zwick's result that uses matrix multiplication, but I am curious if any combinatorial algorithms are known for this problem?

As far as I know, there is no published result on computing distances of approximation less than 2 in subquadratic space and sublinear query time. For retrieving approximate distances quickly, you may want to look at results and references in "Faster Algorithms for All-pairs Approximate Shortest Paths" by Baswana and Kavitha (journal version of their FOCS paper has a good review of related work); none of these achieve subquadratic space.

For compactly retrieving approximate distances, you may want to look at the results and references in the above two papers. [As an addition to the answer by Gabor, a word of caution: be careful about the notion of sparsity in above papers -- for approximation $2$, a graph is said to be sparse if $m = o(n^2)$, as you probably know already].

As Sariel pointed out in one of the comments above, a natural lower bound on space for computing distances of approximation less than $2$ is $\Omega(m)$, that is, linear in the size of the graph. If the query time is not bounded, this lower bound can not be improved (trivially, one can use shortest path algorithm by just storing the graph). For constant query time, I know of two lower bounds. First, Patrascu and Roddity had some conditional lower bounds in their FOCS 2010 paper that apply for approximation less than $2$. Second, Sommer et. al. had some lower bounds for extremely sparse graphs. I am not aware of any other (non-trivial) lower bounds.

In terms of upper bounds, the results from above papers do not seem to generalize to approximation less than $2$. We recently made some progress on this problem. The paper should be on ArXiv soon, but if you like, send me an e-mail and I'll be happy to share the paper.

Hope this helps.

~Rachit Agarwal


How can I find the distribution of a recursive relation with two parameters? Suppose we have a recursive relation, e.g. $G(n,m) = G(n-1,m) + G(n, m-1)$, with some initial points where $n,m \in \mathbb{Z}^{+}$ and $F$ is a finite-field, e.g. $\mathbb{Z}_p$ for a prime $p$. Also $G: \mathbb{Z}_p \times \mathbb{Z}_p \rightarrow F$. There are enough initial points such that $G(n,m)$ terminates finitely for finite $m$ and $n$.

I want to compute the distribution of this relation over the field $F$ and then compare it to some other distribution, e.g. uniform or Gaussian distribution. The question is how can I do that? I have searched a lot, but could not find an answer. Even search terms are appreciated.

The reason I want to do this is proving hardness of the problem whose solution is finding $n$ and $m$ when $F(n,m)$ is given.

Thanks in advance.

I've never done an exact solution for a "change of variable" problem with a recursive function, but I can give you a formula that might help. If $p : \mathbb{Z}_p \times \mathbb{Z}_p \to [0,1]$ is a probability mass function (i.e. sums to one over its domain), then the probability of any specific output for $G$ is

$$\mathrm{Pr}[x]\ =\ \sum_{(n,m) \in G^{-1}(\{x\})} p(n,m)$$

where $G^{-1} : \mathcal{P}(F) \to \mathbb{Z}_p \times \mathbb{Z}_p$ computes preimages under $G$ by

$$G^{-1}(A)\ =\ \{(n,m) \in \mathbb{Z}_p \times \mathbb{Z}_p\ \lvert\ G(n,m) \in A\}$$

In other words, it's the sum of the probabilities of the pairs $(n,m)$ for which $G(n,m) = x$.

Despite the size of the formula, there are advantages to having it in terms of preimages. Unlike inverses, they always exist. They are often compositional, meaning that preimages under a function can often be defined in terms of preimages under its defining subexpressions, which is often necessary when dealing with recursion. For example, if $f : A \to B$ and $g : B \to C$, then

$$(g \circ f)^{-1}\ =\ f^{-1} \circ g^{-1}$$

Another: if $f_1 : A \to B_1$, $f_2 : A \to B_2$, and $f : A \to B_1 \times B_2$ is defined by $f(x) = (f_1(x),f_2(x))$, then

$$f^{-1}(B_1' \times B_2')\ =\ f_1^{-1}(B_1') \cap f_2^{-1}(B_2')$$

for all $B_1' \subseteq B_1$ and $B_2' \subseteq B_2$.

For addition... well, there might be something for your specific problem.

At the very least, it leads to a nice way to factor a program that enumerates the probabilities of each $x \in F$.


Four color theorem and map pre-simplification of faces with less than 5 edges It is already known that in searching for a solution of the four color problem, regular maps can be pre-simplified by removing all faces with less than four edges. This is described for example in the book "What is Mathematics? An Elementary Approach to Ideas and Methods" about the five color theorem.

I belive that all regular maps can be simplified by removing all faces with less than five edges (instead of less then four), without affecting the search and the validity of the four color theorem. This simplification is described here: http://4coloring.wordpress.com/t1/

In this case Euler’s identity gets really simplified: F5 = 12 + F7 + 2F8 + 3 F9 + ...

What is known about this? Has it already been studied before?

The result is known since Kempe in 1879, and is mentioned in http://en.wikipedia.org/wiki/Four_color_theorem as "Kempe also showed correctly that G can have no vertex of degree 4...."  Your proof does not work, because when you remove two edges joining face B with A and C, A and C may already have been adjacent.  Since you give the combined face a color, then return face B with a new color, you leave A and C adjacent and of the same color.