How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0? Given an undirected graph $G=(V,E)$ devise an algorithm that will check whether its edges can be directed in such a way that the vertices of the resulting directed graph will all have indegree higher than $0$. For any edge $\{u,v\}∈E$ only one direction can be chosen: $(u,v)$ or $(v,u)$.

I'm quite new to graphs and graph algorithms so I was wondering if I'm on the right track:

I think the key to the solution is to determine whether the graph is acyclic.

In order to do that we can use BFS algorithm on the graph by coloring layer $i$ in red, layer $i+1$ in blue and again $i+2$ in red and so forth. If at the end of the algorithm we have an edge which connects two nodes of same color that the graph is cyclic.

If the graph is acyclic this means that no matter how we choose the directions if we use topological sorting there will always be a node without an incoming edge, which means that such graphs cannot become directed graphs of indegree higher than $0$ as requested.

Intuitively I think if we have a cyclic graph then our algorithm should be able to turn it into directed with all nodes of indegree higher than $0$ but I'm not sure how to prove this. Maybe like this:

Suppose we choose a graph component with one cycle (circle). We then remove an edge from the circle. Now the component becomes acyclic and using topological sorting we'll have one node without an incoming edge. So now put back the previously removed edge to that node and all the requested conditions hold (the graph is directed and all nodes have at least one incoming edge).

Edit: modified to emphasize how this approach can be generalized to any arbitrary degree sequence of lower bound in-degrees.

(Apologies if the below is extra verbose -- you said that you're new to graph algorithms, and I want to make sure you can follow the reasoning.)

Your problem is a special case of the Santa Clause problem, and the (significantly) more general version that requires each vertex $v_i$ to have in-degree $\geq d_i$ can be solved using Max $s-t$ Flow as follows (your problem is the special case where each $d_i$ is exactly $1$, read up more on maximum flow here). Given an instance $G = (V,E)$ of your problem, we construct a new graph $G'$ with $|V| + |E| + 2$ vertices as follows:

A source node $s$
An edge layer consisting of one node $u_i$ for each $e_i \in E$
A vertex layer consisting of one node $w_i$ for each $v_i \in V$
An sink-node $t$

Further, we connect these nodes with (directed) arcs as follows

$s$ has an arc to each $u_i$ node, with capacity-$1$
Each $u_i$ node has an arc to both $w_j$ and $w_k$, where $v_j$ and $v_k$ are the endpoints of $e_i$ in $G$, again with capacity-$1$.
Each $w_i$ has an arc to $t$, with capacity $d_i$.

Here's an MSPaint diagram of the reduction on a particularly simple example. All drawn edges in $G_2$ are actually downward-oriented arcs.

The claim is that the max $s-t$ flow in this graph is $\sum_i d_i$ iff $G_1$'s edges can be directed so that the min in-degree is $\geq d_i$. Additionally, when the problem is solvable, the optimal solution will be easy to extract*.

The analysis is as follows. The graph has integer weights, so w.l.o.g. we can consider only integer-valued $s-t$ flows (this is called the Integral Flow Theorem). Additionally, the weights on the edges between the $\{w_i\}$ and $t$ ensure that the only way we can get $\sum_i d_i$ units of flow to $t$ is by first getting at least $d_i$ units of flow to each $w_i$. How does flow get to the $\{w_i\}$ nodes? It must originate at the $\{u_j\}$ nodes, which correspond to edges of $G$. Because each $\{u_j\}$ is only getting (at most) $1$ unit of flow from $s$, each $u_j$ gets to pick at most one of its two out-neighbors to send its flow to.

Thus, the interpretation of this flow problem construction is that each edge-node gets to pick at most one vertex-node that can get its unit of flow, and each vertex node $w_j$ must be chosen at least $d_j$ times. This is just like your problem, where we have an edge $e_i$ direct itself towards a vertex $v_j$ (in $G_1)$ if $u_i$ sends a unit of flow to $w_j$ (in $G_2$). In particular, the set of utilized arcs between $\{u_i\}$ and $\{w_j\}$ will tell you exactly how to orient some subset of the edges so that every vertex $v_j$ has at least $d_j$ in-edges. The rest, of course, can be oriented arbitrarily.

* Actually, this construction solves a more general problem, in which we want to maximize the number of vertices with at least $d_i$ in-edges.


checking isomorphism between K regular graph Problem Input is a k regular graph of n vertices and I have to check whether this is isomorphic to another given k regular graph G. This is a restricted version of graph isomorphism in the sense that given graph G is constructed from a p-dimension hypercube graph Hp of 2n vertices [ so n is a power of 2 ] as ...

Since hypercube is always bipartite.[ Hp = (L,R),V ]
G has n nodes corresponding to the left set L of Hp.
For any 2 nodes in L which have a path of length 2 in Hp, there is an edge between the corresponding nodes in G.

It is easy to see that G is regular and highly symmetric [in term diameter,no of diameters etc due to properties of hypergraph ].

My problem is how to detect whether the input graph can be constructed from a hypercube graph as shown or not . i.e. efficiently check for isomorphism.

Note For a given (n,k) there can be many regular graph as shown in http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html

If $p$ is fixed, graph isomorphism can be tested in polynomial time, see [E. Luks. Isomorphism of graphs of bounded valance can be tested in polynomial time. Journal of Computer and System Sciences, 25:42–65, 1982].


Can regexes containing nongreedy (reluctant) quantifiers be rewritten not to use them? Consider a regex language with the greedy quantifier $*$, the nongreedy quantifier ${*}?$, ordered alternation, and character classes. (This is essentially a sublanguage of PCRE without backreferences, look-around assertions, or some of the other fancier bits.)

A match $[a_0,a_1)$ for for a regex $R$ on a string $s = s_0\dots s_n$ is a half-open interval over $\mathbb{N}$ such that $s_{a_0}\dots s_{a_1-1}$ is accepted by $R$.

We give a recursive definition of what makes one match better than another. A match $a = [a_0,a_1)$ for regex $R$ on a string is better than another match $b = [b_0,b_1)$ if $a_0 < b_0$ or, if $a_0 = b_0$ and:

If $R$ is a character class: Character classes have unique matches, so all
matches at the same position for $R$ are equal. Hence this case is impossible.
If $R = ST$:

The leading portion of $a$ is a better match for $S$ than the leading
portion of $b$, or
The leading portions of $a$ and $b$ are equally good matches for $S$, and
the trailing portion of $a$ is a better match for $T$ than the trailing
portion of $b$.

If $R = S|T$:

$a$ is a match for $S$ and $b$ is not, or
$a$ and $b$ are equally good matches for $S$ and $a$ is a better match for $S$ than $b$ is, or
$a$ and $b$ are not matches for $S$ but are matches for $T$, and $a$ is a
better match for $T$ than $b$ is.

All other syntactic forms reduce to the above three for purposes of match
priority:

$R = S{*}$: $R \equiv S^0|S^1|\dots$
$R = S{*}?$: $R \equiv \dots|S^1|S^0$

These infinitary patterns are used for purposes of match priority only---they are not part of the match language under consideration.

The "better" relation is a weak linear order over all possible matches for a
given pattern.

Call two regexes $S,T$ match-equivalent if, for every finite input string, the set of pairwise disjoint best matches for $S$ equals the set of pairwise disjoint best matches for $T$.

Q: Is it the case that for every regex $S$ containing the nongreedy quantifier ${*}?$ there is a match-equivalent regex $T$ which contains no nongreedy quantifiers?

Edit: This is a complete rewrite of the question to clarify what was being
asked.

This answer is based on the assumption that equivalence of two regexes is defined as they recognize the same language.  It does not answer the current question.

You have a common misunderstanding that reluctant quantifiers change the set of strings a regular expression matches.  It does not, and it only changes which options are tried first.

For example, if you perform a regex match 'aaaa' =~ /a+/ in Perl, it finds the first match in the string aaaa, and remembers which substring it matched in a special variable.  Even if there are more than one substring of aaaa which matches the given regex, the matches other than the first match are ignored.

Whether quantifiers are greedy or reluctant affects what the first match is among many matches, but the set of matches does not change.  In this sense, the set of strings which a regex matches is unchanged no matter whether you use usual greedy quantifiers or reluctant quantifiers.


Conditional Dependencies in Compiler Semantic Analysis Passes Imagine that we have a been given an Excel spreadsheet with three columns, labeled COND, X and Y.

COND = TRUE or FALSE (user input)
X = if(COND == TRUE) then 0 else Y
Y = if(COND == TRUE) then X else 1;

These formulas evaluate perfectly fine in Excel, and Excel does not generate a Circular Dependency error.

I am writing a compiler that tries to convert these Excel formulas to C code. In my compiler, these formulas do generate a circular dependency error. The issue is that (naïvely) the expression of X depends on Y and the expression for Y depends on X and my compiler is unable to logically continue.

Excel is able to accomplish this feat because it is a lazy, interpreted language. Excel will just lazily evaluate the formulas at run-time (with user inputs), and since no circular dependency occurs at run-time Excel has no problem evaluating such logic.

Unfortunately, I need to convert these formulas to a compiled language (not an interpreted one). The actual formulas, in the actual spreadsheets, have more complicated dependencies between multiple cells/variables (involving up to over half a dozen different cells). This means that my compiler has to perform some kind of sophisticated static, semantic analysis of the formulas and be smart enough to detect that there are no circular references if we "look inside" the conditional branches. The compiler would then have to generate the following C code from the above Excel formulas:

bool COND;
int X, Y;
if(COND) { X = 0; Y = X; } else { Y = 1; X = Y; }

Notice that the order of the assignment instructions is different in each branch of the if-statement in C.

My question is, is there any established algorithm or literature on compilers that explains how to implement this type of analysis in a compiler? Do functional programming language compilers have to solve this problem?

In general, mutual recursion is the problem you are facing: some languages support it, some don't. The fact is that you can always compile mutual recursion away to simple recursion, using pairs of results instead of a simple result here is an explanation.

The laziness can also be compiled away, by creating thunks, or functions with void argument.

It turns out that in C, mutual recursion is allowed, so only the second trick is required.

int cond = 0;

int if_X(void){
  if(cond){return 0;} else {return Y();}
}

int X(void) {
  return if_X();
}

int if_Y(void){
  if(cond){return X();} else {return 1;}
}

int Y(void){
  return if_Y();
}


Average-case analogue of Small-bias Spaces Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias
$$| \mathbb{E}_{x \in S} [ (-1)^{<x,\alpha>} ] | \leq \epsilon$$
is small. Distributions over such subsets $\epsilon$-fool all linear tests, so if we can make $|S|$ as small as possible, we have a good deranomization primitive.

Is an average case analogue of such a construction studied anywhere, and is it useful? More precisely, suppose we take a subset $S \subset \{0,1\}^n$ such that
$$\mathbb{E}_{\alpha}| \mathbb{E}_{x \in S} [ (-1)^{<x,\alpha>} ] | \leq \epsilon$$
This is, of course, weaker than $\epsilon$-fooling all linear tests. My question is: is there a natural approach to constructing such a set $S$ of small size?

A method used to construct $\epsilon$-bias sets is to interpret it as the vectors of the parity-check matrix of an $\epsilon$-balanced linear code, and so the aim becomes to design such a code with as high rate as possible. Would such an approach work for the average-case too? I am unclear on the correspondence though.

Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$.

In contrast, the best worst-case $\varepsilon$-biased spaces on $n$ bits have size $\tilde\Theta(n/\varepsilon^2)$. So you save a factor of about $n/\varepsilon$ by going from worst-case to average-case.

Unfortunately, as you will see, the construction is a bit silly. This explains why this primitive has not been studied.

Let $m=\lceil \log_2(1/\varepsilon) \rceil$. Let $S = \{0,1\}^m \times \{0\}^{n-m} \subset \{0,1\}^n$. That is, a random $x \in S$ consists of $m$ uniformly random bits, followed by $n-m$ zeros.

We have $|S| = 2^m = 2^{\lceil \log_2 (1/\varepsilon) \rceil} \ge 2^{\log_2(1/\varepsilon)} = \frac{1}{\varepsilon}$ and, similarly, $|S|
 < 2^{\log_2(1/\varepsilon)+1} = \frac{2}{\varepsilon}$.

Now let's analyse the average bias of $S$: $$\underset{\alpha \in \{0,1\}^n}{\mathbb{E}}\left[\left|\underset{x \in S}{\mathbb{E}}\left[(-1)^{\langle x , \alpha \rangle}\right]\right|\right] = \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{E}}\left[\left|\underset{x_0 \in \{0,1\}^m}{\mathbb{E}}\left[(-1)^{\langle x_0 , \alpha_0 \rangle}\right]\right|\right] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\le \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{P}} \left[ \alpha_0 = (0,0,\cdots,0) \right] \cdot 1 + \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{P}} \left[ \alpha_0 \ne (0,0,\cdots,0) \right] \cdot 0\\= 2^{-m} + 0 \le \varepsilon~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$$
The first line uses the fact that only the first $m$ bits are relevant and the second line uses the fact that $x_0$ is uniform.

Furthermore, we can show that $|S| \ge 1/\varepsilon$ is necessary -- a nearly matching lower bound. See this answer for the proof idea.


Restricted Monotone 3CNF formula: counting satisfying assignments (both modulo $2^n$ and modulo $2$) Consider a Monotone 3CNF formula having both the following additional restrictions:

Every variable appears in exactly $2$ clauses.
Given any $2$ clauses, they share at most $1$ variable.

I would like to know how hard is counting the satisfying assignments of such a formula.

Update 06/04/2013 12:55

I would also like to know how hard is determining the parity of the number of satisfying assignments.

Update 11/04/2013 22:40

What if, in addition to the restrictions described above, we also introduce both the following restrictions:

The formula is planar.
The formula is bipartite.

Update 16/04/2013 23:00

Each satisfying assignment corresponds to an edge cover of a $3$-regular graph. After extensive search, the only relevant paper I was able to find on counting edge covers is the (3rd) one already mentioned in Yuval's answer. At the beginning of such paper, the authors say "We initiate the study of sampling (and the related question of counting) of all edge covers of a graph". I'm very surprised that this problem has received so few attention (compared to counting vertex covers, which is widely studied and much better understood, for several graph classes). We do not know whether counting edge covers is $\#P$-hard. We do not know whether determining the parity of the number of edge covers is $\oplus P$-hard, either.

Update 09/06/2013 07:38

Determining the parity of the number of edge covers is $\oplus P$-hard, check answer below.

In any graph, the parity of the number of vertex covers is equal to the parity of the number of edge covers.

To see why, check this answer and observe how the parity of $|C|$ is equal to the parity of $\Delta_{|V|} = O_{|V|} - E_{|V|}$, which is in turn equal to the parity of $O_{|V|} + E_{|V|}$, which is the number of edge covers.

Computing the parity of the number of vertex covers is $\oplus$P-hard: therefore computing the parity of the number of edge covers is $\oplus$P-hard as well.

At least the second half of the question has been settled.


Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$ Let $M$ be a monoid, the family of rational sets $\operatorname{RAT}(M)$ is defined as the smallest set containing the finite subsets, and closed under union, concatentaion and the star operation. The family of recognizable subsets $\operatorname{REC}(M)$ as the family of subsets $L \subseteq M$ such that $L = \varphi^{-1}(\varphi(L))$ for some monoid morphism $\varphi : M \to N$ with $N$ finite.

Now, a McKnight's Theorem says that $M$ is finitely generated iff $\operatorname{REC}(M) \subseteq \operatorname{RAT}(M)$. And by the famous theorem of Kleene, if $M = \Sigma^{\ast}$ for some finite set $\Sigma$, then $\operatorname{REC}(M) = \operatorname{RAT}(M)$. But what about the inclusion $\operatorname{RAT}(M) \subseteq \operatorname{REC}(M)$?

Do you know any example of a  monoid such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$?

If $M$ is an infinite monoid that has no nontrivial finite quotient, then the only recognizable subsets of $M$ are $\varnothing$ and $M$ itself, whereas there are many more rational subsets.

As a special case, this holds if $M$ is any infinite simple group. (Monoid morphisms map inverse elements to inverse elements: $f(x)f(x^{-1})=f(x^{-1})f(x)=f(1)=1$. Thus, surjective monoid morphisms map groups to groups, and are group morphisms.)


Is {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} non-context-free? Is the language {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} context-free or not?

I realized that I have encountered almost all variants of this question with different conditions about the relationship between i, j, and k, but not this one.

My guess is that it is not context-free, but do you have a proof?

Ogden's lemma should work:

For a given $p$ choose $a^i b^p c^k$ and mark all the $b$'s (and nothing else).

$i$ and $k$ are chosen such that for every choice of how many $b$'s are actually pumped there is one pumping exponent such that the number of $b$'s is equal to $i$ and one where it is equal to $k$.

That is $i$ and $k$ have to be from the set $\bigcap_{1 \leq n \leq p} \lbrace p-n + m*n \mid m \in \mathbb{N}_0\rbrace$.

I am quite sure but too lazy to formally prove that this set is infinite.


Is this greedy algorithm for vertex cover studied before? For the vertex cover problem (Given a graph $G$, find a minimum set $S$ of vertices such that $G - S$ is edgeless), there are two famous greedy algorithms.  The edge greedy (finding an edge and taking its both ends) has ratio 2, while the maximum-degree greedy (taking a vertex with the maximum degree) has ratio O(log n). How about the following one:

Repeat until the graph is edgeless,
take a vertex $v$ with the minimum degree, add $N(v)$ into the solution, and $G \leftarrow G - N[v]$.

I noticed some experiments on this algorithm (e.g., https://doi.org/10.1109/ICPCI.2012.6486444). But my interest is on rigorous analyses. Is there any known ratio for it?

Any suggestion of bad examples for this algorithm is also very appreciated.

Unfortunately, the algorithm can be arbitrarily bad.  In the following example, each vertex $u_i$ has $d$ disjoint neighbors, of which only four are drawn. The optimal solution is $\{u_1, \ldots, u_p, w_1, \ldots, w_d\}$, while the greedy algorithm returns its complement.  The ratio is $\frac{d p}{p + d} \approx d$ with $p\to 0$.


Natural maximization problems in FPT Is there a natural (and hopefully well-known) maximization problem that is known to be in FPT?
For instance, Vertex Cover is in FPT, but it's a minimization problem.
I'm looking for natural maximization problems that are in FPT.

Edit (clarification): "I assume you mean a maximization problem that is in FPT when parameterized by the solution size." This is exactly what I meant to ask, as the first comment (by Jan Johannsen) points out.

Here are a few:

Max Cut: Can one color the vertices of an input graph $G$ black and white so that at least $k$ edges go from black to white?
Max Sat: Is there an assignment that satisfies at least $k$
clauses?
Max Leaf: Does $G$ have a spanning tree with at least $k$
leaves?
Longest Path / Cycle: Does $G$ contain a simple path / cycle on at least $k$
vertices?
3-Set Packing: Given a set family ${\cal F}$ of sets of
size $3$, are there $k$ pairwise disjoint sets in ${\cal F}$?


Well-formedness condition for inductive types I work on implementing a simple dependently typed language. I want to implement inductive types there. However, I want them to be well formed. From what I've seen in Coq not all types are acceptable. What can I read about them? Could give a simple enough well-formedness condition which I can use?

Inductive types have been studied heavily and many variants exist. A well-known introduction to inductive definitions is

P. Aczel, An Introduction to Inductive Definitions

which was originally published in the indispensable Handbook of Mathematical Logic, but is now available online stand-alone. An introduction to inductive types is

T. Coquand, P. Dybjer, Inductive Definitions and Type Theory: an Introduction.

The theory of inductive definitions for Coq was first (?) approached in

F. Pfenning, C. Paulin-Mohring, Inductively defined types in the Calculus of Constructions,

I don't know to what extend modern Coq has diverged from what's described in that paper. Either way, none of those is easy reading. You're probably better off to look at a Coq manual and copy the well-formedness conditions imposed there.


Finding a subset of a set in a collection of sets What data structures would you recommend that represent a collections of subsets of $\{1, \dots, n\}$ and support the following operations?

$insert(S)$: inserts $S$ in the collection.
$query(S)$: returns true if there exists $S'$ in the collection such that $S' \subset S$, false otherwise.

My main criterion would be practical time efficiency.

Your problem sounds to me a lot like Information Retrieval(IR). There you have a collection of sets of words (also known as documents) and you want to find not only existence, but all the sets/documents that satisfy the query condition.

Since the set elements are numbers , you can take advantage of teh apparent structure, thus a signature index would be of much use.

I would recommend taking a look at IR papers, especially related to dictionary structures, like trees, but note that space is usually an issue for those systems, whereas it might not be an issue for your case.


To what extent, computational ability for hard tasks helps in solving easy tasks In short, the question is: to what extent, computational ability for hard tasks really helps you in solving easy tasks. (There could be various ways to make this question interesting and non-trivial, and here is one such attempt.)
Question 1:
Consider a circuit for solving SAT for a formula with n variables. (Or for finding Hamiltonian cycle for a graph with $n$ edges.)
Suppose that every gate allows the computation of an arbitrary Boolean function on $m$ variables. For concreteness let’s take $m=0.6 n$.
The Strong exponential time hypothesis (SETH) asserts that even with such strong gates we need superpolynomial circuit size. In fact, we need size at least $\Omega (2^{(0.4-\epsilon) n})$ for every $\epsilon.$ In a sense, gates on fraction of the variables that represent very complicated Boolean functions (much beyond NP-completeness) do not give you much advantage.
We can further ask:
(i) Can we have such a circuit of size $2^{0.9 n}$? $2^{(1-\epsilon)n}$?
A “no” answer will be a vast strengthening of the SETH . Of course, maybe there is an easy “Yes” answer, that I simply miss.
(ii) If the answer to (i) is YES, do gates that computes arbitrary Boolean functions give some advantages compared to gates which “just” compute (say) arbitrary NP functions; or just smaller instances of SAT itself ?
The next question attempts to ask something similar for questions in $P$.
Question 2:
As before let $m< n$ and for concreteness put $m=0.6n$. (Other values of $m$ such as $m=n^\alpha$ are also of interest.) Consider the following types of circuits:
a) In one step you can compute an arbitrary Boolean function on $m$ variables.
b) In one step you can solve a SAT problems with $m$ variables. Or perhaps an arbitrary nondeterministic circuit of polynomial size in $m$ variables.
c) In one step you can perform an arbitrary circuit on $m$ variables of size $m^d$ ($d$ is fixed).
d) In one step you can perform ordinary Boolean gates.
Let us consider the question of finding a perfect matching for a graph with $n$ edges. Matching has a polynomial size circuit. The question is if the exponent in such a matching algorithm can be improved when you move from circuits of type d) to circuits of type c), and from circuits of size c) to circuits of size b), and from circuits of size b) to circuits of size a).
(This may be related to well-known issues about parallel computation or about oracles.)

By counting you should be able to compute about $2^{2^m \cdot s}$ functions with such circuits of size $s$ so I'd guess $s=2^{n-m}$ should be enough to compute all functions.


Normal term of double negation of W-type Consider the intensional Martin-Löf type theory without axiom of choice or the law of excluded middle.
Let $A:U_0$ be a type and $B:A\to U_0$ be a function such that $\Sigma_{a:A}(B(a)\to 0)$is inhabited. Then $W_{a:A}B(a)$ is inhabited and so $(W_{a:A}B(a)\to 0)\to 0$ is inhabited. As an inhabited proposition $(W_{a:A}B(a)\to 0)\to 0$ has only one term in normal form. What is that term?

As an inhabited proposition $(W_{a:A}B(a)\to 0)\to 0$ has only one
term in normal form.

First, without function extensionality, this type cannot be proven to be propositional. Second, propositional types do not necessarily have unique normal forms. Normal forms are up to $\beta\eta$ rules, not propositional equality.
$0 \to 0$ has infinitely many normal inhabitants. Listing a few:
$$\lambda\,x. x$$
$$\lambda\,x. \text{0-elim}\,x$$
$$\lambda\,x. \text{0-elim}\,(\text{0-elim}\,x)$$
Similarly, for any inhabited $A$, $(A \to 0) \to 0$ has infinitely many normal inhabitants.


Asymmetry in Property Testing Definition Property Testing refers to the problem of making a small number of queries to determine whether $x$ is in some language $L$ or whether it is far away from being in $L$.

More precisely we want to distinguish
1)  $x \in L$
2)  $x$ epsilon-far from every $y \in L$.

Here, epsilon-far is generally taken to mean hamming distance.

I don't quite understand why property testing has this asymmetric definition, i.e. why don't we want 1) to be  "$x$ epsilon-close to some $y \in L$"

There is a notion of property testing in which 1) is indeed "x is epsilon'-close to some y in L" (where epsilon' < epsilon), which is called tolerant property testing. In general, tolerant testers are harder to design than property tester (since property testing is a special case).

In many cases, one can actually construct a one-sided error property tester which accepts all x in L with probability 1. These constructions rely on locally testing some sort of condition which things in L satisfy globally (and hence anything in L always passes) whereas inputs that are far away from L are unlikely to pass. For example, say you want to test whether a boolean function is linear, i.e. f(x) + f(y) = f(x+y). A natural test would be to randomly pick two points x,y and verify that f(x) + f(y) = f(x+y). Any f that is already linear always passes this test, and one can easily show that those f which are far from being linear fail this test with high constant probability. The problem with detecting if f is close to being linear comes from the fact that the probability of detecting this is too small.


What is the motivation behind the definition of fixed parameter tractability? Wikipedia writes:

  FPT contains the fixed parameter tractable problems, which are those
  that can be solved in time $f(k)\cdot|x|^{O(1)}$ for some computable function $f$. Typically,
  this function is thought of as single exponential, such as $2^{O(k)}$ but the
  definition admits functions that grow even faster. This is essential
  for a large part of the early history of this class. The crucial part
  of the definition is to exclude functions of the form $f(n,k)$, such as $n^k$.

Question: What is the motivation behind this definition?

What's puzzling me is that, if $k$ is fixed (as per "fixed parameter tractability"), then $n^k$ is a polynomial in $n$.  So, why is it crucial to exclude $n^k$?

If you require only that the growth rate be a polynomial in $n$ for fixed $k$, then you get the definition of the parameterized complexity class XP, which is certainly an object of interest, so there's nothing wrong with considering it.

You get the definition of FPT if you further impose the condition that the degree of the polynomial in $n$ remains fixed as the parameter increases.  FPT turns out to be a particularly tractable subclass of XP, and intuitively, the reason is that an expression such as $2^k n^2$ doesn't explode as quickly as an expression such as $k^2 n^k$, if $k$ and $n$ are both increasing.  This intuition is supported both in practice and in theory; i.e., FPT problems tend to be noticeably more tractable in practice than arbitrary XP problems, and one can also get a nice theoretical picture of the structure of XP by starting with FPT at the bottom and constructing hierarchies of other subclasses of XP (such as the W hierarchy) above it.


Witnesses for mathematical software I, like many people, am a keen user of mathematical software such as Mathematica and Maple. However, I have become increasingly frustrated by the many cases where such software simply gives you the wrong answer without warning.  This can occur when performing all sorts of operations from simple sums to optimization amongst many other examples.

I have been wondering what could be done about this serious problem. What is needed is some way to allow the user to verify the correctness of an answer that is given so that they have some confidence in what they are being told. If you were to get a solution from a math colleague she/he might just sit down and show you their working. However this is not feasible for a computer to do in most cases. Could the computer instead give you a simple and easily checkable witness of the correctness of their answer?  Checking may have to be done by computer but hopefully checking the checking algorithm will be much easier than checking the algorithm to produce the witness in the first place.  When would this be feasible and how exactly could this be formalized

So in summary, my question is the following.

  Could it be possible at least in theory for mathematical software to provide a short
  checkable proof along with the answer you have asked for?

A trivial case where we can do this immediately is for factorization of integers of course or many of the classic NP-complete problems (e.g. Hamiltonian circuit etc.).

The concept of "witnesses" or "checkable proofs" is not totally new: as mentioned in the comments, look for the concept of "certificate". Three examples came to mind, there are more (in the comments and elsewhere):

Kurt Mehlhorn described in 1999 a similar problem in computational geometry algorithms (e.g. minor errors in coordinates can yield big errors in the results of some algorithm), solved in a similar way in the library Leda, by insisting that each algorithm produces a "certificate" of its answer in addition of the answer itself.
Demaine, Lopez-Ortiz and Munro in 2000 used the concepts of certificates (they call them "proofs") to show adaptive lower bounds on the computation of the union and intersection (and difference, but this one is trivial) of sorted sets. Don't exclude their work because they did not use certiticates to protect against computing errors: they showed that even though the certificate can be linear in the size of the instance in the worst case, it is often shorter, and hence can be "checked" in sublinear time (given random access to the input as a sorted array or a B-Tree), and in particular in time less than required to compute such a certificate.
I have been using the concept of certificates on various other problems since seeing Ian Munro presenting their implementation at Alenex 2001, and in particular for permutations (apologies for the shameless plug, another one is coming), where the certificate is shorter in the best case than in the worst or average case, which yields a compressed data structure for permutations. Here again, checking the certificate (i.e. the order) takes at most linear time, less than computing  it (i.e. sorting).

The concept is not always usefull for error checking: there are problems where checking the certificate takes as much time as producing it (or simply producing the result). Two examples come to mind, one trivial and one complicated, Blum and Kannan (mentioned in the comments) give others.

The certificate for proving that an element is not in an unsorted array of $n$ elements is obtained in $n$ comparisons and checked in the same time.
The certificate for the convex hull in two and three dimensions, if the points are given in random order, takes as much bits to encode as comparisons to compute [FOCS 2009] (other shameless plug).

The library Leda is the most general effort (that I know of) toward making deterministic certificate-producing algorithms the norm in practice. Blum and Kannan's paper is the best effort I saw to make it the norm in theory, but they do show the limits of this approach.

Hope it helps...


Complexity of a weighted subset selection problem. I'm currently thinking about a problem I'd like to manage in one of my applications.

There is a set of objects $\{A, B, C, D, \ldots\}$. Every object has the same attributes with different values. For example, $A$'s attribute $a_1$ has the value $A(a_1)$, $B$'s attribute $a_1$ has the value $B(a_1)$ and so on.

Now I want to pass a number $x$ which represents the maximum number of objects to selected from the set. For example, $x = 2$ would mean that any combination of at most 2 objects are allowed to be selected from the set.

Given this table of attributes and the number $x$, the algorithm should return at most $x$ objects which, in summation, own the largest attributes. Only the greater one counts.

For example: $A,B,C$ with attributes $a_1,a_2,a_3$ and $x = 2$:

$\begin{array}{|c|c|c|c|}
   & a_1 &  a_2 &  a_3\\\hline
 A &   1 & -100 &   -1\\\hline
 B &  -2 &    2 & -200\\\hline
 C & -20 &  -10 &   10\\\hline
\end{array}$

The algorithm should return $A$ and $B$ since $A(a_1) + A(a_2) + B(a_3)$ serve the maximum when at most 2 objects from the set are allowed to be selected.

If I'd use brute-force, I simply would test all $\binom{n}{x}$ combinations and calculate the overall sum.

Is there a faster way to do this?

Thanks!

I'm going to assume your problem is equivalent to what this computes:

max map SubsetsOfSize(N) \S (sum map attributes \A (max map S \e A[e]))

In other words, find the best set of items such that picking the best available item attribute values gives the largest sum.

Yes, it's NP-Complete. You can encode 3-Sat into it. Each variable becomes a true-row and false-row. Each clause becomes a column with a 1 in the rows corresponding to its satisfying assignments. You prevent true-row and false-rows from being selected simultaneously by adding columns with huge values in those two rows (0 everywhere else) and requiring that exactly half the rows be selected (thus the optimal solution will require each huge value, and picking a true and false will lose a huge value somewhere else). The 3-sat instance being satisfiable is equivalent to being able to select items for a total score of HugeValue*NumVariables + NumClauses.

Example transformation:

(A or B or C) and (not A or B or not C)

   uA uB uC  C1 C2
+A  9  0  0  1  0
-A  9  0  0  0  1
+B  0  9  0  1  1
-B  0  9  0  0  0
+C  0  0  9  1  0
-C  0  0  9  0  1
N = 3


Why are all finite languages regular? It is said that "All finite languages are regular".

But the Pumping Lemma says that,

if a language is regular
one can find a 'large-enough' word w such that it can be decomposed into w = xyz such that FOR ALL i >= 0 the word with a pumped up y^i is also in the language.

But doesn't that state that "every regular language is infinite" since one can always infinitely (i in N) pump the word up and it will be still in the language?

So why are the finite languages regular and how are they fulfill the pumping lemma?

The pumping lemma states that if $L$ is a regular language, then there is an integer $p \geq 1$ (the "pumping length") such that every string $w$ in $L$ of length at least $p$ can be written as $w = xyz$ satisfying (1) $|y| \geq 1$, (2) $|xy| \leq p$ and (3) $(\forall n \geq 0)[xy^nz \in L]$.  (Source: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement)

If $L$ is finite, then one can take the pumping length $p$ to be any integer greater than the length of any string in $L$.  The three conditions above would then be satisfied vacuously because there is no word in $L$ of length at least $p$.


List of TCS conferences along with important dates I saw that there is a post with a List of TCS conferences. However, this does not list important dates like conference date, submission deadline etc. Is there any post or website which maintains these information and also keeps it up-to-date?

I'm maintaining such a list here:
https://sites.google.com/site/yixincaoresearch/conferences.

Thanks due to  Anupam Gupta and Iftah Gamzu.


How is proving a context free language to be ambiguous undecidable? I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a decision? Perhaps I'm wrong and it can be done?

We reduce from Post's Correspondence Problem. Suppose we can, in fact, decide the language $\{\langle G\rangle\vert G\textrm{ a CFG and }L(G)\textrm{ ambiguous}\}$.

Given $\alpha_1, \ldots, \alpha_m, \beta_1, \ldots, \beta_m$:
Construct the following CFG $G = (V,\Sigma,R,S)$:
$V = \{S, S_1, S_2\}$,
$$\begin{align}
R = \{S_{\phantom0}&\rightarrow S_1\vert S_2,\\
S_1&\rightarrow \alpha_1 S_1 \sigma_1 \vert \cdots \vert \alpha_m S_1 \sigma_m \vert \alpha_1 \sigma_1 \vert \cdots \vert \alpha_m \sigma_m,\\
S_2&\rightarrow \beta_1 S_2 \sigma_1\vert \cdots \vert \beta_m S_2 \sigma_m \vert \beta_1 \sigma_1\vert \cdots \vert \beta_m \sigma_m\}
\end{align}$$
(where $\sigma_i$ are new characters added to the alphabet, e.g., $\sigma_i = \underline{i}$).

If the language is ambiguous, then there is a derivation of some string $w$ in two different ways. Supposing, wlog, that the derivations both start with the rule $S\rightarrow S_1$, reading the new characters backwards until they end makes sure there can only be one derivation, so that's not possible. Hence, we see that the only ambiguity can come from one $S_1$ and one $S_2$ 'start'. But then, taking the substring of $w$ up to the beginning of the new characters, we have a solution to the PCP (since the strings of indices used after those points match).

Similarly, if there is no ambiguity, then the PCP cannot be solved, since a solution would imply an ambiguity that just follows $S\Rightarrow S_1\Rightarrow^* \alpha\tilde{\sigma}$ and $S\Rightarrow S_2\Rightarrow^* \beta\tilde{\sigma}$, where $\alpha = \beta$ are strings of matching $\alpha$'s and $\beta$'s (since the $\tilde{\sigma}$'s match).

Hence, we've reduced to PCP, and since that's undecidable, we're done.

(Let me know if I've done anything boneheaded!)


Symbolic Execution is a case of Abstract Interpretation? This is written in the wiki entry of Symbolic Execution, but I can't find any reference for it. Can anyone show me a pointer? Thank you.

I am not aware of a paper concerned with the comparison between symbolic execution and abstract interpretation. Nor do I think one is needed. Reading the original descriptions of these two techniques should be enough.

King, Symbolic Execution and Program Testing, 1976
Cousot, Cousot, Abstract Interpretation: a Unified Lattice Model for Static Analysis of Programs by Construction of Approximation of Fixpoints, 1977

(Conversely, if there would be some unexpected connection, then that would be worth describing. But I very much doubt this is the case.)

The main idea of symbolic execution is that, at an arbitrary point in execution, you can express the values of all variables as functions of the initial values. The main idea of abstract interpretation is that you can systematically explore all executions of a program by a series of over-approximations. (I can hear several AI enthusiasts groaning at the previous approximation.)

Thus, at least in the original formulation, symbolic execution was not concerned with exploring all possible executions. You can see this even in the title: it includes the word ‘testing’. But here's more from Section 8: "For programs with infinite execution trees, the symbolic testing cannot be exhaustive and no absolute proof of correctness can be established."

In contrast, abstract interpretation aims to explore all executions. To do so, it uses several ingredients, one of which is very similar to the main idea of symbolic execution. These ingredients are (1) abstract states, (2) joining and widening (hence, ‘lattice’ in the title).

Abstract states. The concrete state of a program at a particular point in time is basically a snapshot of the memory content (including the program code itself and the program counter). This has a lot of detail, which is hard to track. When you analyze a particular property, you may want to ignore large parts of the concrete state. Or you may want to care only whether a particular variable is negative, zero, or positive, but not care about its exact value. In general, you want to consider an abstract version of the concrete state. For this to work out, you must have a commutativity property: If you take a concrete state, execute a statement, and then abstract the resulting state, you should obtain the same result as if you abstract the initial state, and then execute the same statement but on the abstract state. This commutativity diagram appears in both papers. This is the common idea. Again, abstract interpretation is more general, for it does not dictate how to abstract a state -- it just says there should be a way to do it. In contrast, symbolic execution says that you use (symbolic) expressions that mention the initial values.

Joining and Widening. If program execution reaches a certain statement in two different ways, symbolic execution does not try to merge the two analyzes. That is why the quote above talks about execution trees, rather than dags. But, remember that abstract interpretation wants to cover all executions. Thus, it asks for a way to merge the analyses of two executions at the point where they have the same program counter. (The join could be very dumb ({a} join {b} = {a,b}) such that it amounts to what symbolic execution does.) In general, joining itself is not sufficient to guarantee that you'll eventually finish analyzing all executions. (In particular, the dumb join mentioned earlier won't work.) Consider a program with a loops: "n=input(); for i in range(n): dostuff()". How many times should you go around the loop and keep joining? No fixed answer works. Thus, something else is needed, and that is widening, which can be seen as a heuristic. Suppose you went around the loop 3 times and you learned that "i=0 or i=1 or i=2". Then you say: hmmm, ... let's widen, and you get "i>=0". Again abstract interpretation does not say how to do widening -- it just says what properties widening should have to work out.

(Sorry for this long answer: I really didn't have time to make it shorter.)


Reference for Turing to many-one reductions I am looking for a reference on `reducing' Turing reductions to many-one reductions.  I have in mind a statement of the following form (similar enough statements would also satisfy me):

Theorem.  If $\mathsf{A}\leq_T^f \mathsf{B}$, then $\mathsf A\leq_m^{2^f}\mathsf B^{tt}$.

where "$\leq_T^f$" and "$\leq_m^f$" denote respectively Turing and many-one reductions in deterministic time $f(n)$, and "$\mathsf{B}^{tt}$" denotes a `truth table' variant of the language $\mathsf{B}$, which evaluates a Boolean combination of checks "$x\in\mathsf{B}$".

Proof idea for the statement:  Simulate the $f(n)$-time bounded oracle Turing machine used in the Turing reduction: it's easy enough to obtain a nondeterministic Turing transducer also in time $f(n)$ that guesses the answers of the $\mathsf B$ oracle and writes a conjunction of checks "$x\in\mathsf B$" or "$x\not\in\mathsf{B}$" on the output, to be evaluated by an $\mathsf B^{tt}$ machine.  This transducer can be determinized by exploring both outcomes of the oracle calls, and handling them through disjunctions in the output; it now works in time $2^{f(n)}$.

Oddly enough, I cannot seem to find any related result in complexity textbooks.

Edit: renamed "$A\mathsf B$" into "$\mathsf B^{tt}$" to emphasize the relation with truth tables, as pointed out by @MarkusBläser.

I'm pretty sure you can find this in the book Bounded Queries in Recursion Theory by Martin and Gasarch, but I don't have access to a copy now to check.

(Your statement gives an upper bound of $2^f$; most of that book is about lower bounding such quantities, so the upper bound must be in there somewhere, probably very near the beginning.)

PS - I agree with M. Blaser's comment: you're basically talking about truth-table reductions without using that terminology.


Is the following problem NP-Hard? I'm not expert on complexity theory and combinatorial optimization.
I want to know if the following problem (or similar) is known in the scientific literature, and if you think it is NP-complete.
Thank you in advance for your help.

Input:

Two parameters X and Y, which can be equal.
n customers C1, C2, ... Cn
m types of goods M1, M2 ... Mm

There are X pieces available for each good Mi: a piece of 1kg, another piece of 2kg, ...., a piece of X kg.
Every customer wants to buy a certain number of goods. For example, the client C1 may be interested in buying goods M1, M4, M8 and M9.
A customer is satisfied if he can find all the goods he wants to buy. In addition, the weights of the parts he was able to purchase must satisfy a constraint that I'll explain below.

Output:
How many customers can be satisfied?

The constraint on the weights is as follows:
Take for example the client C1 who is interested in buying goods M1, M4, M8 and M9. Assume that C1 was able to purchase all four goods. Let P1, P2, P3, P4 be the weights of the pieces he was able to buy.
C1 is satisfied if $\sum_i  P_i -1 <Y$.

Edit: Note that the limit Y is common for all customers. The intuition behind the constraint is that we want to limit the number of pieces whose weight is not equal to 1kg.

(I have posted this answer as a comment on the question, but I am reposting it with a little more detail.)

This problem is NP-hard as follows.

As is usual in a proof of NP-hardness, suppose that a natural number K is also given as part of input, and consider the yes/no problem of deciding whether at least K customers are satisfied.  Then this problem is NP-complete, even if it is restricted to the case where X=1, m=3K and each customer wants to buy exactly three goods.  (Note that if X=1, the value of Y is irrelevant as long as Y>0.)  In this case, the problem is equivalent to the NP-complete problem called Exact Cover by 3-Sets.

See Garey and Johnson for more on complexity theory and NP-completeness, including the definition of the Exact Cover by 3-Sets and the proof of its NP-completeness.


What advantages does having a null-able string type confer to a programming language? I've been trying to understand the rationale behind the design of the C# language. Are there any specific advantages that can be gleaned from allowing string type variables to contain null?

At the risk of starting a religious war, I will express my opinion that there are no advantages to having nullable types. These should always be replaced by a sum type such as Ocaml option or Haskell Maybe (paired with sane deconcstructors for such types that force the programmer to always consider both possibilities).

The main reason for this is that null pointers, null objects, and the like are responsible for many, many bugs and countless headaches.


Calculus of Constructions: compress expression to its smallest form I'm aware that the Calculus of Constructions is strongly normalizing, meaning every expression has a normal for that cannot be beta,eta-reduced further. So in fact this is the most efficient expression that calculates the same value as the original expression.

But in certain cases, normalization may reduce a small expression to a huge expression (in terms of size).

Is there a smallest-form of expressions? A form that calculates the same value with the smallest size.

In other words, instead of a time-efficient normal-form, a space-efficient one.

There's a bit of freedom in what we considre "the same value". Let me show that there is no such algorithm if "the same value" means "observationally equivalent". I will use a fragment of the Calculus of constructions, namely Gödel's System T (simply typed $\lambda$-calculus, natural numbers, and primitive recursion on them), so the argument applies to a much weaker calculus already.

Given a number $n$, let $\overline{n}$ be the corresponding numeral representing it, i.e., $n$ applications of $\mathtt{succ}$ to $0$.
Given a Turing mahcine $M$, let $\lceil M \rceil$ be the numeral encoding $M$ in some reasonable way.

Say that two closed terms $t, u : \mathtt{nat} \to \mathtt{nat}$ are equivalent, written $t \simeq u$, when for all $n \in \mathbb{N}$, $t \, \overline{n}$ and $s \, \overline{n}$ both normalize to the same numeral (they normalize to a numeral because we're in a strongly normalizing claculus).

Suppose we had an algorithm, which given any closed term of type $\mathtt{nat} \to \mathtt{nat}$ calculates a minimal equivalent term.
Then we can solve the Halting oracle as follows.

There is a term $S : \mathtt{nat} \times \mathtt{nat} \to \mathtt{nat}$ such that, for all $n \in \mathbb{N}$ and all Turing machines $M$,
$S (\lceil M \rceil, \overline{n})$ normalizes to $\overline{1}$ if $T$ halts within $n$ steps, and it normalizes to $\overline{0}$ otherwise. This is well known, since simulation of a Turing machine for a fixed number of steps $n$ is primitive recursive.

There are finitely many closed terms $Z_1, \ldots, Z_k$ which are minimal terms equivalent to $\lambda x : \mathtt{nat} .\, 0$. Our minimization algorithm returns one of them when we give it $\lambda x : \mathtt{nat} .\, 0$, and it may even be the case that $\lambda x : \mathtt{nat} .\, 0$ is in fact the only such minimal term. All this does not matter, the only thing that matters is that there are finitely many minimal terms that are equivalent to $\lambda x : \mathtt{nat} .\, 0$.

Now, given any machine $M$, consider the term
$$u \mathbin{{:}{=}} \lambda x : \mathtt{nat} .\, S (\lceil M \rceil, x)$$
If $M$ runs forever then $u \overline{n}$ normalizes to $\overline{0}$ for every $n$ and is equivalent to $\lambda x : \mathtt{nat} .\, 0$. To decide whether $M$ runs forever, we feed $u$ into our minimzation algorithm and check whether the algorithm returned one of $Z_1, \ldots, Z_k$. If it did, then $M$ runs forever. If it did not, then it halts. (Note: the algorithm need not calculate the $Z_1, \ldots, Z_k$ by itself, these can be hard-coded into the algorithm.)

It would be nice to know an argument that works with a weaker notion of equivalence, for instance just $\beta$-reducibility.


Actual practical example of a prefix-free Turing-complete language A theoretical construct that comes up a lot in algorithmic computability theory is a universal prefix-free language. For my purposes, this is a language with the following properties:

its syntax is defined by a binary prefix code. That is, concatenating extra digits to the end of a valid program will never result in another valid program, and if you keep choosing 0s and 1s at random indefinitely, you will eventually end up with a valid program.
it is Turing complete
its output is a stream of binary digits

I have a slightly crazy idea that would require me to play around with an actual implementation of such a language - I want to be able to generate arbitrary (self-terminating) binary strings, have them interpreted as programs, and get binary strings as output.

Of course, in principle I could just invent some kind of trivial prefix-free encoding of ASCII, run it through an interpreter for my favourite language, and convert STDOUT to binary. However, if I do this, the chances of it doing anything other than terminate immediately (with a syntax error) are vanishingly small. Thus, I also have the following requirement:

The language is such that a (uniformly) randomly generated program has a reasonable chance of doing something non-trivial and returning output

My question is whether such a language exists - either as a formal definition in the literature that wouldn't be too time-consuming to implement, or as a command line tool or (better) a library that can be called from C++ or Python. Given the amount that has been written about this construct, I would find it mildly surprising if no-one had constructed a concrete example, but I haven't been able to track one down.

While not exactly what you want, esoteric languages Jot, Iota and Zot could be good starting points. They are all Turing complete.

In particular Iota language is defined as

syntax            semantic
F --> i           ^x.xSK
F --> *  F  F     [F][F]

So

  an Iota program is either an i, or a * followed by two Iota (sub-)programs

so it satisfies the prefix property. It's extension Zot adds input and output, where the input is the sequence of bits that follow the valid program description. By restricting Zot to programs with empty input you get a language that should satisfy your requirements. (Or alternatively adding just output to Iota.)

There is Haskell implementation of Zot.


How to become referee for TCS papers and conferences I moved somehow from biophysics to a mixed team where we usually publish in TCS journal / conferences. For getting funding, in the European country where I live, it is advisable to show in your CV that I have refereed papers or conferences on these fields. I have more than 30 publications but never really thought about this. So my question goes, how can I become referee in these cases?

Generally, you are invited to be a referee because the editor knows you or your work or he/she finds you because the paper under review cites your work or is in the same field as your work (perhaps via a google search).

Of course, if you are on the PC of a conference, you get to review loads of papers. You get on the PC by being invited, generally because you are either an old hand in the field or an up and coming star (or a friend/(ex-)colleague of the PC chair).

If you are a student or post-doc, then you should get to do some reviewing if your supervisor/boss/colleague/etc is on the PC of a conference.

In short, you need to be known or linked with someone who is known. Or alternatively you could ask a colleague whether you could review some papers for him/her next time he/she is on a PC.


Why are so few natural candidates for NP-intermediate status? It is well known by Ladner's Theorem that if ${\mathsf P}\neq \mathsf {NP}$, then there exist infinitely many $\mathsf {NP}$-intermediate ($\mathsf{NPI}$) problems. There are also natural candidates for this status, such as Graph Isomorphism, and a number of others, see
Problems Between P and NPC. Nevertheless, the vast majority in the crowd of known $natural$ $\mathsf {NP}$-problems are known to be either in $\mathsf {P}$ or $\mathsf {NPC}$. Only a small fraction of them remains a candidate for $\mathsf {NPI}$. In other words, if we randomly pick a natural $\mathsf {NP}$-problem among the known ones, we have very little chance to pick an $\mathsf {NPI}$ candidate. Is there any explanation for this phenomenon?

I could think up 3 possible explanations, more on the philosophical side:

The reason for having such a small fraction of natural $\mathsf {NPI}$ candidates is that     $\mathsf {NPI}$ will eventually turn out to be empty. I know, this implies ${\mathsf P} =\mathsf {NP}$, so it is very unlikely. Nevertheless, one could still argue (though I'm not one of them) that the rareness of natural $\mathsf {NPI}$ problems is  an empirical observation that appears to actually support ${\mathsf P} =\mathsf {NP}$, in contrast to most other observations.
The smallness of "natural-$\mathsf {NPI}$" represents a kind of sharp phase transition between easy and hard problems. Apparently,  the meaningful, natural algorithmic problems behave in a way that they tend to be either easy or hard, the transition is narrow (but still exists).
The argument in 2 can be taken to the extreme: eventually all problems in "natural-$\mathsf {NPI}$" will be put into $\mathsf {P} \cup \mathsf {NPC}$, yet ${\mathsf P}\neq \mathsf {NP}$, so $\mathsf {NPI}\neq \emptyset$. This would mean that all remaining problems in $\mathsf {NPI}$ are "unnatural" (contrived, without real-life meaning). An interpretation of this could be that natural problems are either easy or hard; the transition is only a logical construct, without "physical" meaning. This is somewhat reminiscent to the case of irrational numbers, which are perfectly logical, but do not arise as the measured value of any  physical quantity. As such, they do not come from physical reality, they are rather in the "logical closure" of that reality.

Which explanation do you like the best, or can you suggest another one?

As others have pointed out, it's debatable to what extent the thing you're trying to explain is even true.  One could argue that, in the 60s and 70s, theoretical computer scientists were just more interested in the sorts of problems that turn out to be either in P or else NP-complete.  Today, because of the rise of complexity-theoretic cryptography, quantum computing, lattices, etc.---as well as the simple fact that NP-completeness has become so well-understood---we've become more and more interested in the sorts of problems that turn out to be NP-intermediate.

Still, one could ask: to the extent that the thing is true---that is, to the extent that so many natural search and optimization problems "snap" to being either NP-complete or else in P---to that extent, why is it true?  Here, I think you can get a lot of intuition by looking at an earlier phenomenon from computability: that so many natural models of computation "snap" to being Turing-complete.  In that case, I'd say the explanation is that, once you have a few basic components---a read/write memory, loops, conditionals, etc.---it's hard to avoid being able to simulate a Turing machine, and therefore being Turing-complete.  In much the same way, once your search or optimization problem has a few basic components---most importantly, the ability to construct "gadgets" that mimic logic gates like AND, OR, and NOT---it's hard to avoid being able to encode SAT and therefore being NP-complete.

The way I like to think about it, problems like SAT exert a powerful "gravitational pull" on all the other computational problems in their vicinity, making them want to "snap up" to being NP-complete also.  So, it normally doesn't even require special explanation when yet another problem succumbs to that pull!  What's more striking, and more in need of explanation, is when an (apparently) hard NP problem has some property that lets it resist the gravitational pull of SAT.  We then want to know: what is that property?  Why can't you play the usual NP-completeness trick for this problem, of constructing gadgets that encode Boolean logic gates?  I made up a list of some common answers to that question in this recent CS.SE answer, but (as another commenter already pointed out) there are other possible answers that I missed.


Fully dynamic algorithms for strong components of a directed graph I'm faced with the problem of maintaining the strong components of a directed graph under insertions/deletions of edges and vertices.

As noted in one of the answers to a closely-related question here, the literature in this area is rather fragmented and hard for a newcomer such as myself to approach.

For example, the paper by Holm et al. appears to focus on undirected graphs, and it's unclear to me whether any of their results can be adapted to work with digraphs.  Other papers I've found focus on either the incremental or decremental cases, rather than the fully-dynamic case.

My need arises in a real-world software engineering scenario, so I would actually be fine with an approach that yields no worst-case asymptotic advantage over the naive idea of running an SCC algorithm from scratch for each update, so long as it performs well in practice.

I'd prefer not to reinvent the wheel, but I also don't have endless hours to wade through the literature, so hopefully someone here can save me some time.

Thanks in advance!

I know it is an older question but this research paper has a relatively straight forward O(m^(3/2)) algorithm for incrementally maintaining them: https://arxiv.org/pdf/1105.2397.pdf
Here is one with O(m) algorithm for decrementally maintaining them: https://arxiv.org/pdf/1901.03615.pdf (from 2019 and it improves on the O(m*sqrt(n)) algorithm of https://u.cs.biu.ac.il/~liamr/scc-new.pdf)
I am not sure there is anything better for doing both operations.  Part of the issue is the data structure used for maintaining them.  Incremental algorithms are typically using Tarjan's Union-Find for fast partitioning of disjoint sets.  While decremental algorithms are using an Even-Shiloach(ES)-tree, as the breadth-first-search representation matches the problem.
As for a unified data structure which efficiently can be used for a fully online SCC maintenance, that would be progress we hope to see soon.


A total language that only a Turing complete language can interpret Any language which is not Turing complete can not write an interpreter for it self. I have no clue where I read that but I have seen it used a number of times. It seems like this gives rise to a kind of "ultimate" non Turing complete language; the one(s) that can only be interpreted by a Turing machine. These languages would not necessarily be able to compute all total functions from naturals to naturals nor would they necessarily be isomorphic (that is maybe ultimate languages A and B exists such that there exists a function F that A can compute but B cannot). Agda can interpret Godel's system T and Agda is total so that such an ultimate language should be strictly more powerful that Godel's system T it would seem. It seems to me that such a language would be at least as powerful as agda too (though I have no evidence, just a hunch).

Has any research been done in this vein? What results are known (namely is such an "ultimate" language known)?

Bonus: I am worried that there exists a pathological case that can not compute functions that Godel's System T could yet can still only be interpreted by a Turing machine because it allows some really odd functions to be computed. Is this the case or can we know that such a language would be able to compute anything Godel's System T could compute?

This is a badly phrased question, so let's first make sense of it. I am going to do it the style of computability theory. Thus I will use numbers instead of strings: a piece of source code is a number, rather than a string of symbols. It does not really matter, you may replace $\mathbb{N}$ with $\mathtt{string}$ throughout below.

Let $\langle m, n\rangle$ be a pairing function.

Let us say that a programming language $L = (P, ev)$ is given by the following data:

a decidable set $P \subseteq \mathbb{N}$ of "valid programs", and
a computable and partial function $ev : P \times \mathbb{N} \to \mathbb{N}$.

The fact that $P$ is decidable means there is a total computable map $valid : \mathbb{N} \to \{0,1\}$ such that $valid(n) = 1 \iff n \in P$. Informally, we are saying that it is possible to tell whether a given string is a valid piece of code. The function $ev$ is essentially an interpreter for our language: $ev(m,n)$ runs code $m$ on input $n$ – the result may be undefined.

We can now introduce some terminology:

A language is total if $n \mapsto ev(m,n)$ is a total function for all $m \in P$.
A language $L_1 = (P_1, ev_1)$ interprets language $L_2 = (P_2, ev_2)$ if there exists $u \in P_1$ such that $ev_1(u, \langle n, m \rangle) \simeq ev_2(n, m)$ for all $n \in P_2$ and $m \in \mathbb{N}$. Here $u$ is the simulator for $L_2$ implemented in $L_1$. It is also known as the universal program for $L_2$.

Other definitions of "$L_1$ interprets $L_2$" are possible, but let me not get into this now.

We say that $L_1$ and $L_2$ are equivalent if they interpret each other.

There is "the most powerful" language $T = (\mathbb{N}, \varphi)$ of Turing machines (which you refer to as "a Turing machine") in which $n \in \mathbb{N}$ is an encoding of a Turing machine and $\varphi(n,m)$ is the partial computable function that "runs the Turing machine encoded by $n$ on input $m$". This language can interpret all other languages, obviously since we required $ev$ to be computable.

Our definition of programming languages is very relaxed. For the following to go through, let us require three more conditions:

$L$ implements the successor function: there is $succ \in P$ such that $ev(succ,m) = m+1$ for all $m \in \mathbb{N}$,
$L$ implements the diagonal function: there is $diag \in P$ such that $ev(diag,m) = \langle m, m \rangle$ for all $m \in \mathbb{N}$,
$L$ is closed under composition of functions: if $L$ implements $f$ and $g$ then it also implements $f \circ g$,

A classic result is this:

Theorem: If a language can interpret itself then it is not total.

Proof. Suppose $u$ is the universal program for a total language $L$ implemented in $L$, i.e., for all $m \in P$ and $n \in \mathbb{N}$,
$$ev(u, \langle m, n \rangle) \simeq ev(m, n).$$
As successor, diagonal, and $ev(u, {-})$ are implemented in $L$, so is their composition $k \mapsto ev(u, \langle k, k \rangle) + 1$. There exists $n_0 \in P$ such that $ev(n_0, k) \simeq ev(u, \langle k, k \rangle) + 1$, but then
$$ev(u, \langle n_0, n_0\rangle) \simeq ev(n_0, n_0) \simeq ev(u, \langle n_0, n_0 \rangle) + 1$$
As there is no number equal its own successor, it follows that $L$ is not total or that $L$ does not interpret itself. QED.

Observe that we could replace the successor map with any other fixpoint-free map.

Here is a little theorem which I think will clean up a misunderstanding.

Theorem: Every total language can be interpreted by another total language.

Proof. Let $L$ be a total language. We get a total $L'$ which interprets $L$ by adjoining to $L$ its evaluator $ev$. More precisely, let $P' = \{\langle 0, n\rangle \mid n \in P\} \cup \{\langle 1, 0\rangle\}$ and define $ev'$ as
$$ev'(\langle b, n \rangle, m) =
\begin{cases}
ev(n,m) & \text{if $b = 0$},\\
ev(m_0, m_1) & \text{if $b = 1$ and $m = \langle m_0, m_1 \rangle$}
\end{cases}
$$
Obviously, $L'$ is total because $L$ is total. To see that $L'$ can simulate $L$ just take $u = \langle 1, 0\rangle$, since then
$ev'(u, \langle m, n\rangle) \simeq ev(m, n)$, as required. QED.

Exercise: [added 2014-06-27] The language $L'$ constructed above is not closed under composition. Fix the proof of the theorem so that $L'$ satisfies the extra requirements if $L$ does.

In other words, you never need the full power of Turing machines to interpret a total language $L$ – a slightly more powerful total language $L'$ suffices. The language $L'$ is strictly more powerful than $L$ because it interprets $L$, but $L$ does not interpret itself.


Is Deolalikar's 2010 proof that $P \ne NP$ correct? There was recently a claimed proof that $P \ne NP$. Not long after its publication there were raised some issues with this proof.

So ... is the proof correct or not ? (Please only answer this if you have evidence ... this question might take some time until it's answered)


Frame rule as a change-preserver? A frame rule, like the one given below, captures the idea that, given a program c with precondition p that holds before it runs and postcondition q that holds afterward, some disjoint condition r should hold both before and after c runs.  (The * connective requires that its arguments be disjoint.)  Often, the pre- and postconditions are states of a heap, and c is an effectful program that modifies the heap in some way.

    {p} c {q}
----------------- (where no free variable in r is modified by c)
{p * r} c {q * r}

Discussions of the frame rule that I've seen always seem to focus on how the disjoint part of the heap, r, is preserved.  This enables "local reasoning": when reasoning about the effect that c has, we can disregard the r part of the heap and only concern ourselves with the part that actually changes.  But another way to look at it is that the change from p to q is preserved, even though r is now sitting there.  In other words, it's important that we end up with the postcondition {q * r}, rather than {q' * r} for some other q'.

So, my question is whether there's any treatment of the frame rule that discusses or makes use of the preservation-of-change-from-p-to-q thing.

But this no-change-to-q property does not actually hold!

Consider {emp} x := alloc(0) {x |-> 0}.  Now, if I frame in y |-> 3, I get

{y |-> 3} x := alloc(0) {x |-> 0 * y |-> 3}

but, by the rule of consequence, I could change the postcondition to

{y |-> 3} x := alloc(0) {(x |-> 0 /\ x != y) * y |-> 3}

To make this more concrete, suppose y is the number 37.  When I run the allocation command in a completely empty heap, it's possible that I will end up allocating address 37, so that x = 37.  But, if I instead start with a heap containing a single cell at address y = 37, this outcome is no longer possible!  Adding a frame to the precondition has pruned some of the nondeterminism in the postcondition.

The paper "Local action and abstract separation logic" (Calcagno, O'Hearn, and Yang) is all about understanding the frame rule from a deeper, semantic perspective.  The key definition of the paper is locality for "actions", where an action is (the semantic representation of) a program.  Locality says that when you add in some frame heap, the only way that the original postcondition can be changed is by pruning some nondeterminism as above.  And, in fact, pruning only arises because of allocation.


Extensions of Ramsey's theorem: monochromatic but diverse As a follow-up of my previous question, which was resolved by Hsien-Chih Chang, here is another attempt to find an appropriate generalisation of Ramsey's theorem. (You don't need to read the previous question; this post is self-contained.)

Parameters: integers $1 \ll d \ll k \ll n$ are given, and then $N$ is chosen to be sufficiently large. Terminology: an $m$-subset is a subset of size $m$.

Let $B = \{1,2,...,N\}$. For each $k$-subset $S \subset B$, assign a colour $f(S) \in \{0,1\}$.

Definitions:

$X \subset B$ is monochromatic if $f(S) = f(S')$ for all $k$-subsets $S \subset X$ and $S' \subset X$.
$X \subset B$ is diverse if $X = \{ x_1, x_2, ..., x_n \}$ such that $x_i < x_{i+1}$ and $x_i\,\not\equiv x_{i+1} \text{ mod } d$ for all $i$.

For example, if $d = 10$, then $\{ 12, 15, 23, 32, 39 \}$ is diverse but $\{ 12, 15, 25, 32, 39 \}$ is not. Note that a subset of a diverse set is not necessarily diverse.

Now Ramsey's theorem says that no matter how we choose $f$, there is a monochromatic $n$-subset $X \subset B$. And obviously it is trivial to find a diverse $n$-subset $X \subset B$.

Question: is there always a diverse and monochromatic $n$-subset $X \subset B$?

Edit: Hsien-Chih Chang shows that the claim is false for a prime $d$, but what about composite $d$? In my applications, I will have a lot of freedom in choosing the exact values of $d \ll k \ll n$, as long as I can make them arbitrarily large. They can be powers of primes, products of prime numbers, or whatever is necessary to make the claim true.

First I have to say: this problem is really interesting!! And here I briefly describe why my previous approaches failed, as suggested in this meta post about incorrect answers.

My first attempt was trying to construct a coloring related to the sumset of the k-subset which makes all n-subset non-monochromatic. Lemma 1 is still available; but Lemma 2 was wrong, by observing that if k and d are related prime, then an n-subset $\{1,3,1,3, \ldots\}$ in module d suggested by @Jukka is a counter-example.
The second try was a proof to the theorem; by counting the ratio of diverse and monochromatic $n$-subsets, we hope that the number of monochromatic ones will surpasses those of non-diverse ones. But the is an error in my calculations, observed by @domotorp: the ratio of being non-diverse will not approaches zero; it converges to about $n/d$, which is clearly larger than $R(n,n;k)^{-n}$.
The third one goes back to the first method, and it shows that for a uber-weak parameter set ($n > k+d-1$ and $d \mid k$), the theorem is false. We used a famous lemma in additive combinatorics: the EGZ-theorem.

The fourth try is due to the answer by @domotorp; it is both clever and inspiring, and I'll try to modify his proof to deal with all the parameters. But still his method is elegant, and I totally appreciate this simple approach.

A diverse n-set contains at least one k-subset with at least $k-1$ "switches between mod classes"; precisely, let $X = x_1,\ldots,x_n$ be a diverse n-set, and let $S^* = x_1,\ldots,x_k$, a switch is defined if $x_i$ and $x_{i+1}$ are in different mod-d classes. We have k-1 switches for $S^*$.

Let a k-subset $S$ be red if $S$ has at most k-2 switches; otherwise it is blue. By the previous paragraph we already had a blue one, now we prove that for $n > k+d+1$, there is an red $S$ in any n-set $X$. Since $n > d$, there are two numbers $x_i,x_j$ in the same mod-d class and $j-i \leq d-1$; and since $n > k+d+1$, there are at least k-2 elements $x_k$ in $X$ with $k<i$ or $k>j$. And we can construct a k-subset $S$ with $x_i$ next to $x_j$, which only switches at most k-2 times. Thus $S$ is a red k-subset.


Treewidth of deep Sierpiński Sieve Graph Note $S_n$ the Sierpiński sieve graph of order $n$, which is obtained from the connectivity of the Sierpiński sieve.

For $n$ high enough, what is the treewidth of $S_n$?

I think that I can show that it is at least $4$ (by obtaining $K_5$ as a graph minor), and that it is at most $5$ (by obtained a tree-decomposition scheme involving bags of size $6$). My gut feeling is that it should be $5$, but I cannot find a proper database for forbidden minors at treewidth $4$ (and I can't access Sanders' thesis mentioned here).

You can recursively decompose each triangle into a smaller triangle and a trapezoid, and each trapezoid into two smaller triangles. The corresponding tree decomposition (whose bags contain the corners of a triangle at one level of the decomposition and a triangle or trapezoid at the next or previous level) has five vertices per bag and therefore has width four.

There is no $K_5$ minor, because the graph is planar. There is, however, a $K_{2,2,2}$ (octahedron) minor (actually, a subdivision), shown below. As this is one of the forbidden minors for treewidth three, the width is four.


Linear programming, a non standard handling of absolute value This is really a basic (undergrad) question in LP but still i would like to
clarify it for myself to be sure. I have a minimization problem from the sort $\min \sum_i |x_i|$ s.t $Ax \le b$.
I've seen that the standard way to convert it to LP is to represent $x_i$ as the difference
of two non negative variables. We question is, can i also handle it like so :
add a new variable t : $|x_i|=t_i$ and get
$$\min \sum_i t_i \\
Ax \le b \\
-t_i \le x_i \le t_i $$
Thanks.

Your formulation ensures that $|x_i|=t_i$ in every optimal solution. However, this does not hold for an arbitrary feasible point.

Picky people could then complain that your formulation isn't entirely correct. However, as long as you don't change your objective function nor use $t_i$ in any other constraint, then you will be fine in practice.

This blog post describes several ways to model absolute values.


Fast convolution over small finite fields What are the best known methods for cyclic convolution of length $n$ over a small field, i.e. when $|\mathbb{F}| \ll n$?  I'm particularly interested in constant-sized fields, or even $\mathbb{F} = \mathbb{F}_2$.  General asymptotic-efficiency statements and references are much appreciated.

Background:  Let $\mathbb{F}$ be a field, and $n > 0$.  We think of vectors $u \in \mathbb{F}^n$ as having coordinates indexed by $\mathbb{Z}_n$.

The (cyclic) convolution of length $n$ over $\mathbb{F}$ is the transformation taking $u, v \in \mathbb{F}^n$ and outputting $u * v \in \mathbb{F}^n$, defined by
$$
(u * v)_i :=  \sum_{j \in \mathbb{Z}_n} v_j u_{i - j},
$$
with index arithmetic over $\mathbb{Z}_n$.

To perform cyclic convolution over large fields, a popular method is to use the Convolution Theorem to reduce our problem to performing Discrete Fourier Transforms (DFTs), and using an FFT algorithm.

For small finite fields, the DFT is undefined because there's no primitive $n$-th root of unity.  One can get around this by embedding$^*$ the problem in a larger finite field, but it's not clear that this is the best way to proceed.  Even if we take this route, it'd be nice to know if someone has already worked out the details (for example, choosing which larger field to use and which FFT algorithm to apply).

Added:

$^*$ By 'embedding' our convolution in, I mean one of two things.  First option: one could pass to an extension field in which the desired primitive roots of unity are adjoined, and do the convolution there.

Second option: if our starting field is cyclic, one could pass to a cyclic field $\mathbb{F}_{p'}$ of larger characteristic--large enough that if we consider our vectors as lying in $\mathbb{F}_{p'}$, no "wraparound" occurs.
(I'm being informal, but just think about how, to compute a convolution over $\mathbb{F}_2$, we can clearly just do the same convolution over $\mathbb{Z}$, and then take the answers mod 2.)

Also added:

Many algorithms for FFT and related problems work especially well for 'nice' values of $n$ (and I would like to understand the situation with this better).

But if one doesn't attempt to take advantage of special values of $n$, the cyclic convolution problem is basically equivalent (by easy reductions involving linear blow-up in $n$) to ordinary convolution; this in turn is equivalent to multiplication of polynomials with coefficients over $\mathbb{F}_p$.

By this equivalence, one can use results in, e.g., this paper of von zur Gathen and Gerhard (building on work of Cantor), who use an extension-field approach to get a circuit complexity bound of $\tilde{O}_p(n)$.  They don't state their bounds in an especially clear way IMO, but the bound is worse than $n \cdot \log^2 n$ even for $\mathbb{F}_2$.  Can one do better?

A recent paper by Alexey Pospelov appears to give the state of the art.  (It isn't the first to achieve the bounds I'll quote, but it achieves them in a unified way for arbitrary fields, and equally importantly, it states the bounds clearly, see p. 3.)

$\bullet$ We can multiply two degree-$n$ polynomials over an arbitrary field $\mathbb{F}$ using $O(n \log n)$ multiplications in $\mathbb{F}$ and $O(n \log n \log \log n)$ additions in $\mathbb{F}$.  This is originally due to Schonhage-Strassen (for char. $\neq 2$) and Schonhage for char. 2.  As I mentioned, this implies the same bounds for cyclic convolution.  Pospelov also states,
"We are currently not aware of any algorithms with an upper bound of [the above] that are not based on consecutive DFT applications..."

$\bullet$ Cantor and Kaltofen generalized these results, showing the bounds hold for arbitrary algebras (not just fields).

$\bullet$ If $\mathbb{F}$ supports Discrete Fourier Transform of appropriate order, that is, if $\mathbb{F}$ has a primitive $N$-th root of unity where $N$ is large enough (I believe $N = O(n)$ suffices) and $N$ is a power of 2 or 3, then we can do polynomial multiplication with $O(n)$ multiplications and $O(n \log n)$ additions.  Various other improvements are possible for fields with other special properties.

$\bullet$ It seems to be plausible, but unknown, whether Furer's recent improvement in integer multiplication (reproved in a different way by De et al.) can help lead to faster polynomial multiplication algorithms, over finite fields say.  Can anyone comment?

Todd Mateer's thesis also seems like an excellent resource to understand the FFT literature and applications to polynomial multiplication (thanks Jug!); but you have to dig more to find what you're looking for.


Consequences of existence of a strongly polynomial algorithm for linear programming? One of the holy grails of algorithm design is finding a strongly polynomial algorithm for linear programming, i.e., an algorithm whose runtime is bounded by a polynomial in the number of variables and constraints and is independent of the size of the representation of the parameters (assuming unit cost arithmetic).  Would resolving this question have implications outside of better algorithms for linear programming?  For instance, would the existence/non-existence of such an algorithm have any consequences for geometry or complexity theory?

Edit: Maybe I should clarify what I mean by consequences.  I'm looking for mathematical consequences or conditional results, implications that are known to be true now.  For instance: "a polynomial algorithm for LP in the BSS model would separate/collapse algebraic complexity classes FOO and BAR", or "if there is no strongly polynomial algorithm then it resolves such-and-such conjecture about polytopes", or "a strongly polynomial algorithm for problem X which can be formulated as an LP would have interesting consequence blah".  The Hirsch conjecture would be a good example, except that it only applies if simplex is polynomial.

This would show that parity and mean-payoff games are in P. See Sven Schewe. From Parity and Payoff Games to Linear Programming. MFCS 2009.


Are theoretically sound pseudorandom generators used in practice? As far as I'm aware, most implementations of pseudorandom number generation in practice use methods such as linear shift feedback registers (LSFRs), or these "Mersenne Twister" algorithms. While they pass lots of (heuristic) statistical tests, there are no theoretical guarantees that they look pseudorandom to, say, all efficiently computable statistical tests. Yet these methods are used indiscriminately in all sorts of applications, ranging from cryptographic protocols to scientific computing to banking (probably). I find it somewhat worrisome that we have little to no guarantee about whether these applications work as intended (because any sort of analysis would likely have assumed true randomness as input).

On the other hand, complexity theory and cryptography provide a very rich theory of pseudorandomness, and we even have candidate constructions of pseudorandom generators that would fool ANY efficient statistical test you could come up with, using candidate one way functions.

My question is: has this theory made its way into practice? I would hope that for important uses of randomness, such as cryptography or scientific computing, theoretically sound PRGs are used.

As an aside, I could find some limited analysis of how well popular algorithms such as quicksort work when using LSFRs as a source of randomness, and apparently they work well. See Karloff and Raghavan's "Randomized algorithms and pseudorandom numbers".

The notion of "theoretically sound" pseudorandom generators is not really well defined. After all, no pseudorandom generator has a proof of security. I don't know that we can say that a pseudorandom generator based on the hardness of factoring large integers is "more secure" than, say, using AES as a pseudorandom generator. (In fact, there is a sense that it is less secure, since we know of quantum factoring algorithms but not quantum algorithms to break AES.)

What we do have mathematical proofs for are various composition results, saying that if you compose block-ciphers or hash functions in certain ways you can get pseudorandom generators or pseudorandom function. Some such results are widely used in practice, e.g., HMAC. But it's true that the results that achieve a PRG and start with just assuming that the basic component is a plain one-way function are not efficient enough to use for applications (and this is at least partly inherent). So, typically we need to assume a  PRG/stream cipher/block-cipher/hash function as a basic primitive, and start building other things from it. The issue is not really about asymptotic analysis since essentially all cryptographic reductions (except perhaps for Levin's universal PRG) can be made concrete and so give concrete guarantees under concrete assumptions.

But even though they are not based on one-way functions, there is a sense in which constructions such as AES are "theoretically sound" because:
(1) There are formal conjectures about their security.
(2) There is work to try to refute these conjectures, and also derive implications from them.

And indeed, people are aware that for many applications, it would not be smart to use PRG's such as LSFR that do not satisfy (1) and (2) above.


Computing the Mobius function The Mobius function $\mu(n)$ is defined as $\mu(1)=1$, $\mu(n)=0$ if $n$ has a squared prime factor, and $\mu(p_1 \dots p_k)= (-1)^k$ if all the primes $p_1,\dots,p_k$ are different. Is it possible to compute $\mu(n)$ without computing the prime factorization of $n$?

One non-answer to your question is that SQUARE-FREE (is a number square free) is itself not known to be in P, and computing the Möbius function would solve this problem (since a square free number has $\mu(n) \neq 0$).


Online Algorithms books Are there any recent books on Online Algorithms? I know of only two books on the subject.

Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv: This is a classic but old book, and does not contain many recent advances in the field.
The Design of Competitive Online Algorithms via a Primal-Dual Approach by Niv Buchbinder and Joseph (Seffi) Naor: This is a new book and contains lot of recent results. However, it's scope is limited to LP based primal-dual algorithms.

Please list here all the books on Online Algorithms that you may know. If there are any books freely available on the web, that will be great.

It seems that there are no recent books or survey papers on online algorithms.


Universal Function approximation It is known via the universal approximation theorem that a neural network with even a single hidden layer and an arbitrary activation function can approximate any continuous function.

What other models are there that are also universal function approximators

This is treated extensively in the statistics literature, under the topic of regression.  Two standard references here are Wasserman's book "all of nonparametric statistics" and Tsybakov's "introduction to nonparametric estimation".  I'll talk briefly about some of the standard stuff, and try to give pointers outside of statistics (this is a common topic and different fields have different cultures: prove different kinds of theorems, make different assumptions).

(Kernel regressors, sometimes called the Nadaraya-Watson Estimator.)  Here you write the function at any point as a weighted combination of nearby values. More concretely,
since this is in the statistics literature, you typically suppose you have some examples $((x_i,f(x_i)))_{i=1}^n$ drawn from some distribution,
and fix some kernel $K$ (can think of this as a gaussian, but zero mean is what matters most), and write
$$
\hat f(x) := \sum_i f(x_i) \left(\frac{ K(c_n(x-x_i)) }{ \sum_j K(c_n(x-x_j))}\right),
$$
where $c_n\to\infty$ (you are more sensitive to small distances as $n$ increases).
The guarantee is that, as $n\to\infty$, a probilistic criterion of distortion
(expectation of sup-norm, high probability, whatever) goes to zero.
(It hardly matters what $K$ looks like---it matters more how you choose $c_n$.)
(Basis methods.)  A similar thing is to choose some family of "basis functions", things like Wavelets or piecewise linear functions, but really anything that forms a (possibly overcomplete) basis for the vector space $L^2$, and determine a weighted linear combination of scaled and translated elements.
The techniques here differ drastically from (1.); rather than plopping down basis functions centered at data points, you carefully compute the weight and location of each in order to minimize some distortion criterion.  (Typically, their quantity is fixed a priori.) One approach is "basis pursuit", where you greedily add in new functions while trying to minimize some approximation error between $\hat f$ and $f$.  To get a sense of the diversity of approaches here, a neat paper is Rahimi & Recht's "uniform approximation of functions with random bases".  Perhaps I should say that the grand-daddy of all of these is the Fourier expansion; there's a lot of good material on this in Mallat's book on Wavelets.
(Tree methods.)  Another way is to look at a function as a tree; at each level, you are working with some partition of the domain, and return, for instance, the average point.  (Each pruning of the tree also gives a partition.)  In the limit, the fineness of this partition will no longer discretize the function, and you have reconstructed it exactly.  How best to choose this partition is a tough problem. (You can google this under "regression tree".)
(Polynomial methods; see also splines and other interpolating techniques.)  By Taylor's theorem, you know that you can get arbitrarily close to well behaved functions.  This may seem like a very basic approach (i.e., just use the Lagrange interpolating polynomial), but where things get interesting is in deciding which points to interpolate.  This was investigated extensively in the context of numerical integration; you can find some amazing math under the topics of "clenshaw-curtis quadrature" and "gaussian quadrature".  I'm throwing this in here because the types of assumptions and guarantees here are so drastically different than what appears above.  I like this field but these methods suffer really badly from the curse of dimension, at least I think this is why they are less discussed than they used to be (if you do numeric integration with mathematica, I think it does quadrature for univariate domains, but sampling techniques for multivariate domains).

Considering various restrictions to your function class, you can instantiate the above to get all sorts of other widely-used scenarios.  For instance, with boolean valued functions, thresholding (1.) will look a lot like a nearest-neighbor estimator, or an SVM with some local kernel (gaussian).  A lot of the above stuff suffers from curse of dimension (bounds exhibit exponential dependence on the dimension).  In machine learning you get around this either by explicitly constraining your class to some family (i.e., "parametric methods), or by an implicit constraint, usually something relating the quality of the approximants to the target function complexity (i.e., an analog of the weak learning assumption in boosting).

By the way, my favorite theorem related to neural net approximation  is Kolmogorov's superposition theorem (from 1957!).  It says that any multivariate continuous function $f:\mathbb{R}^d \to \mathbb{R}$ has the form
$$
f(x) = \sum_{j=0}^{2d}h_j\left(\sum_{i=1}^d g_{j,i}(x_i)\right),
$$
where each $g_{j,i} : \mathbb{R}\to\mathbb{R}$ and $h_j:\mathbb{R}\to\mathbb{R}$ is (univariate) continuous.  Note that unlike neural nets, the $g$'s and $h$'s may all differ.  But even so, given that there are only $\Theta(d^2)$ functions floating around, I find this totally amazing.

(You only asked about function classes, but I figured you'd be interested in methods as well.. if not.. oops)


Lookup complexity in augmented interval tree If we consider the following problem:
Stream of intervals, coming in one at a time, which we maintain in an augmented interval tree (Interval tree). At some point in time later, we get a point,
and are asked to return all intervals covering that point.

What is the complexity of the above lookup operation?

PS : This is not a homework question, but was an interview question.

Let $p$ be the query point, and assume the interval tree is sorted by lower endpoint and each node stores the maximum endpoint in its subtree.

Perform a tree-walk and stop the recursion whenever the lower endpoint of the current node is greater than $p$, or the maximum is smaller than $p$.
Now at most one downward path (of length $O(\log n)$) reports no interval, namely the path that would be taken by binary searching the lowest endpoints for $p$.

Illustrated example:

Consider this interval tree and query point, the rightmost path visited by the pruned tree-walk is the path of orange nodes (which may not contain a reported interval if their maximum endpoints are all less than $p$).
All intervals in the right subtrees have a minimum endpoint greater than $p$ so can be ignored.
However, all intervals in left subtrees (red) of this path have minimum endpoint at most $p$. This means we are sure to report an interval for each (red) subtree (and subtrees thereof) whose maximum endpoint (over the entire subtree) is at least $p$.

Then, whenever we report a subsequent interval, we do so within $O(\log n)$ time.
Since there are $m$ such intervals, this amounts to $O((m+1)\log n)$ time.
Because we prune a tree-walk we also have an upper bound of $O(n)$ time.
This reduces to $O(n)\cap O((m+1)\log n)=O(\min(n,(m+1)\log n))$ time.


Is $GCT$ necessarily a negative result program? $GCT$ is a candidate program to separate permanent and determinant through symmetries. If indeed permanent and determinant can be handled in similar complexity class would $GCT$ be a program which can provide the insight? Is so how would the hypothetical demonstration be?

It depends a little what you mean exactly by "GCT". If you mean it more generally, the answer is certainly yes. If you mean it more specifically about multiplicity obstructions, this is a bit more of an open question.
If you mean GCT generally as applying algebraic geometry to complexity theory, or perhaps even slightly more specifically using geometry to cross the GCT chasm, as in this quote:

By geometric complexity theory, we mean henceforth any approach to cross the GCT chasm using asynthesis of geometry and complexity theory. -Mulmuley, GCT V arXiv

Then the answer is that algebraic geometry can certainly prove positive results in complexity theory. First in principle: $\mathsf{VNP} \nsubseteq \overline{\mathsf{VP}}$ if and only if there is a polynomial vanishing on the latter but not on the former - this is very basic algebraic geometry. Similar results hold whenever one considers the approximative/border/closure of a complexity class. Second, in history: border-rank methods are algebro-geometric, and have yielded new algorithms for matrix multiplication, as well as results relating the complexity of a polynomial to those of its factors Bürgisser (arXiv)
If, on the other hand, you mean more specifically separating complexity classes using multiplicity obstructions, then your question gets at the "converse" question in GCT: that is, it is a theorem that a multiplicity obstruction implies a separation of complexity classes, but is the converse true? In general for $G$-varieties this is almost certainly false (that is, given a reductive algebraic group $G$ like $GL_n$ acting algebraically on a vector space $V$, and two varieties $X,Y \subseteq V$ that are each unions of $G$-orbits, is it the case that $X \subseteq Y$ iff there are no multiplicity obstructions?). But for the particular varieties of interest in GCT, there is some chance that the converse might hold. A first indication of this is that the polynomials studied are characterized by their symmetries, which already tells you that the group action here is telling you more about these particular varieties than it would be for general $G$-varieties.
If the converse held, then one could in principle get a collapse of complexity classes by proving that there were no multiplicity obstructions. On the one hand, this seems quite hard. On the other hand, Bürgisser-Ikenmeyer-Panova (arXiv) proved that there were no occurrence obstructions (multiplicty zero in one class and nonzero in the other).
However, even if the converse didn't hold, knowing that there were no multiplicity obstructions would still, I think, yield significant insight into the relationship between these problems. Each representation of $GL_{n^2}$ appearing in the ring of (meta)polynomials (a polynomial ring in a number of variables that is equal to the number of monomials of degree $n$ in $n^2$ variables) corresponds to a $GL_{n^2}$-invariant property of (ordinary) polynomials. The isomorphism type of such a representation tells you how its defining equations transform under the action of $GL_{n^2}$. The multiplicity of a given isomorphism type (isotype) in the coordinate ring of one of these varieties $X$ thus tells you how many properties of that isotype the polynomials in $X$ have. Knowing that there were no multiplicity obstructions would still imply that these complexity classes share many more properties than one might initially think.