complexity of deciding whether there's a small polynomial with a given root Let $f\in (\mathbb{Z}/p\mathbb{Z})^\ast$ be a nonzero element of a prime finite field.  For $d, r\in \mathbb{N}$ consider the problem of deciding whether there is a nonzero polynomial $$P(x) = a_0 +a_1x+a_2x^2+...+~a_dx^d \in \mathbb{Z}[x]$$ of degree not exceeding $d$, and also $|a_i|\leq r$ for all $i$, and also such that $\overline{P}(x)\in (\mathbb{Z}/p\mathbb{Z})[x]$ has $f$ as a root.  (So this is a decision problem depending on $f, p, d, r $).   Is there anything known about the general time complexity of this problem?

Here is an algorithm that solves the problem in time
$$\tilde O\Bigl(\min\Bigl\{(2r+1)^{\frac{d+1}2},p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)}\Bigr\}\sqrt r\Bigl)\subseteq\tilde O(p).$$
The tildes hide $(\log p)^{O(1)}$ factors coming from operations in $\mathbb F_p$ and from implementation of sets by, say, min-heaps.

First, observe that the answer is always YES if $d+1\ge\frac{\log(p+1)}{\log(r+1)}$: there are $(r+1)^{d+1}\ge p+1$ polynomials $P$ of degree at most $d$ with coefficients in $\{0,\dots,r\}$, hence by the pigeonhole principle, there exist two such polynomials $P_0\ne P_1$ such that $\overline{P_0}(f)=\overline{P_1}(f)$. Then $P=P_0-P_1$ satisfies the requirements.

Thus, we may assume without loss of generality
$$d+1\le\left\lfloor\frac{\log p}{\log(r+1)}\right\rfloor.$$
Then (assuming $r\ge1$)
$$(2r+1)^{\frac{d+1}2}\le p^{\frac{\log(2r+1)}{2\log(r+1)}}\le p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)},$$
hence it suffices to find an algorithm working in time
$$\tilde O\Bigl((2r+1)^{\frac{d+2}2}\Bigr).$$

For any $i\le d+1$, let
$$V_i=\{\overline P(f):P\in\mathbb Z[x],P\ne0,\deg(P)<i,\|P\|_\infty\le r\}.$$
Using this notation, the problem is equivalent to finding out if $0\in V_{d+1}$, and we can compute $V_i$ using a simple recurrence. The whole algorithm looks like this:

If $r=0$, output NO.
If $d+1\ge\frac{\log(p+1)}{\log(r+1)}$, output YES.
For each $j=\lceil\log(d+2)\rceil,\dots,1$, compute $V_{\lfloor(d+1)2^{-j}\rfloor}$ and $f^{\lfloor(d+1)2^{-j}\rfloor}$ by using the recurrences
$$\begin{align*}
V_0&=\varnothing,\\
V_{2i}&=V_i\cup\bigl\{a+f^ib:a\in V_i\cup\{0\},b\in V_i\bigr\},\\
V_{2i+1}&=V_{2i}\cup\bigl\{a+f^{2i}b:a\in V_{2i}\cup\{0\},b\in\{\pm1,\dots,\pm r\}\bigr\},
\end{align*}$$
where all the arithmetic operations are modulo $p$.
If $d$ is even, compute $V_{\lceil(d+1)/2\rceil}$ from $V_{\lfloor(d+1)/2\rfloor}$ as above.
If $0\in V_{\lceil(d+1)/2\rceil}$, output YES.
For each $a\in V_{\lceil(d+1)/2\rceil}$, if $-af^{\lceil(d+1)/2\rceil}\in V_{\lfloor(d+1)/2\rfloor}$, then output YES.
Output NO.

It should be clear from the discussion above that the algorithm is correct. Moreover, we have
$$|V_i|\le(2r+1)^i,$$
and since these bounds form a geometric series, it is easy to see that the time needed to compute $V_i$ using the above recurrences is also
$$\tilde O\Bigl((2r+1)^i\Bigr).$$
Thus, the algorithm runs in time
$$\tilde O\Bigl((2r+1)^{\lceil(d+1)/2\rceil}\Bigr)\subseteq\tilde O\Bigl((2r+1)^{(d+2)/2}\Bigr).$$


Is there a notion of "inevitable reduction?" I was just working on a semantics paper and realized I needed a notion of inevitable reduction. I came up with this definition:

  Let $\rightarrow$ be a binary relation. We say that $a$ inevitably reduces to $b$, or $a \rightarrow^{\forall *} b$, if either $a=b$ or, for all derivations $a \rightarrow x_1 \rightarrow x_2 \rightarrow \dots$ (where the $x_i$ are either infinite or terminate in a normal form), there is some $i$ such that $x_i = b$.

This seems way too simple and fundamental to not already exist, but I've never encountered it before. (I've read "Term Rewriting and All That" in full, and just took a skim through "Advanced Topics in Term Rewriting".) It's clearly related to confluence, and can also be stated in terms of dominators. Still, I have no leads for finding prior uses.

So, anyone know prior work on this?

I have never heard of this exact concept in rewrite theory, which certainly doesn't prove it hasn't been considered.

However, I will make the point that it may not be quite as useful a concept as it first appears, at least in classical rewrite theory because it behaves poorly under substitution:

If $t\rightarrow t'$ is an inevitable reduction, and $t$ contains a free variable $x$ which also appears in $t'$, then $t[u/x]\rightarrow t'[u/x]$ is never an inevitable reduction if $u$ is not normal (since if $u\rightarrow u'$ then $t[u/x] \rightarrow t'[u'/x]$ can avoid $t'[u/x]$).

It would seem that inevitable reducts are quite rare in general, even for pretty reasonable systems, except for normal forms (which are interesting for other reasons). Obviously this only holds for general notions of reductions; specific strategies might have many more (deterministic strategies only have inevitable reductions).

In general, rewrite theorists are more interested in which redexes need to be reduced (to hit normal forms) rather than which terms need to be hit. This has been studied quite a bit, under the name of needed reductions: a needed redex is one that must be triggered in order to reach a normal form. See e.g. Needed reduction and spine strategies for the lambda calculus or Reduction Strategies for Left-Linear Term Rewriting Systems.

I believe this latter notion is stable under substitution for reasonable systems (say, orthogonal).


Locally sorted sequences Let $S=s_1,\ldots,s_n$ be a sequence and $p$ be a permutation on the indices of $S$ such that $p$ sorts $S$.

Define a sequence to be locally sorted with degree $k$ if $\forall s_i \in S |p(i) - i | \leq k$.

How many locally sorted sequences of degree $k$ are there for $n$ elements? Hopefully, there will be a better approach than "enumerate all possible sequences and check each one".

I wasn't sure how to approach this problem, so I tried proofing results for various values of $k$. I solved this for $k=1$; it's just a Fibonacci sequence. $k=2$ is a lot more difficult to me. I keep overcounting.

For handiness, here's some Python code to use when checking results:

from itertools import permutations
def check(seq, k):
    for i in range(0, len(seq)):
        index = i+1
        if abs(seq[i] - index) > k: return False
    return True
n = 5
k = 2
orig = [ i+1 for i in range(0,n) ] # easier if we use sequences of integers
check_count = 0
for perm in permutations(orig):
    if check(perm,k):
        check_count += 1
print(check_count)

Your problem is solved in the paper Spheres of Permutations under the
Infinity Norm — Permutations with limited displacement by Torleiv Kløve.

See also A002524 and other sequences linked there. I found Kløve's paper by calculating the first few values of A002524 and finding it on the OEIS.


Known algorithms to go from a DFA to a regular expression I was wondering whether there is a ``better'' (I will explain in what sense) algorithm to start from a DFA $\mathcal{A}$ and construct a regular expression $r$ such that $L(\mathcal{A})=L(r)$, than the one in the book by Hopcroft and Ullman (1979). In there, the sets $R_{ij}^k$ are used to represent sets of strings that take the DFA from state $q_i$ to $q_j$ without going through any state numbered higher than $k$. This construction, although obviously correct and very useful, is rather technical.

I'm writing a monograph about algebraic automata theory and I don't want to distract my audience with too many technical details (at least not with details that are irrelevant for the results I want to show), but I do want to include a proof of the equivalence between DFA and regular expressions for the sake of completeness. For the record, I'm using Glushkov automata to go from a regular expression to a DFA. It seemed more intuitive than $\varepsilon$-transitions, which I didn't define at all (again, because I don't need them).

What other algorithms are known to go from a DFA to a regular expression? I value simplicity over efficiency (that's ``better'' for me in this case), but that is not a requirement.

Thanks in advance for your help!

Two more constructions: Brzozowski-McCluskey aka state elimination [1], and Gaussian elimination in a system of equations using Arden's Lemma.  The best source on these is probably Jacques Sakarovitch's book [2].

[1] J. Brzozowski, E. McCluskey Jr., Signal ﬂow graph techniques for sequential circuit state diagrams, IEEE Transactions on Electronic
Computers EC-12 (1963) 67–76.

[2] J. Sakarovitch, Elements of Automata Theory.  Cambridge University Press, 2009.


Dynamic programming  and shortest path problem Several months back, I asked in math.SE the following question

  I wonder if any dynamic programming problem can always be converted to
  a source-sink shortest path problem in a network with source and sink
  nodes given?

The reason I asked is because I always pictured the type of problems that could be solved by dynamic programming method as source-sink shortest path problems. In other words, the type of problems seemed to always have the interpretation as source-sink shortest path problems, but I was not sure if it was correct.

The only answer I have got so far is

  The answer is no. The simplest example off the top of my head is the
  longest substring of ones in a 0,1 string. The typical DP solution
  would be to use a 1D array and store the length of the longest
  substring up that includes the i-th character in the i-th coordinate.

When I further asked:

  why is the example not able to be formulated into a source-sink
  shortest path problem in a network?

The reply is:

  I don't really see an easy way of doing it as a source-sink SPP. For
  the DP solution, the answer is obtained by scanning the array for the
  largest number.

I am now still not sure how DP solves the longest substring of ones in a 0,1 string, and whether this problem can be interpreted as a source-sink shortest path problem. Also I feel the answerer may run out of idea from his reply. Since my question may also be relevant to algorithm theory, I hope there will be some reply from this site.

Thanks and regards!

One standard view of dynamic programming is the following. Start with a recursive algorithm and then memoize it. By memoization we mean that solutions for intermediate problem instances/sub-problems are stored and not recomputed. If one can argue that the number of sub problems generated in the recursive algorithm for an instance of size $n$ is polynomial in $n$ then memoization leads to a polynomial time algorithm. A recursive algorithm for a problem instance $I$ generates, naturally, an associated DAG $G(I)$ whose nodes are the sub-problem instances and the arcs are the dependencies generated by the recursive algorithm on $I$. It is possible to interpret several different computational problems as solving some kind of shortest path problem on this DAG $G(I)$ (not all though). In these cases it is possible to take out the scaffolding of the recursive algorithm and memoization and directly use a shortest path algorithm in an associated graph. This should not lead one to conclude that all of dynamic programming can be reduced to shortest path computation.


Formally Verified Complexity Theory Is there any ongoing project to formally verify the theorems and proofs of complexity theory using a proof assistant like Coq? Are there any boundaries to doing this?

In the following paper my colleague Uli Schöpp presents a formal verification (in Coq)  of a nontrivial result by Cook and Rackoff on the computational power of graph automata. https://scholar.google.at/scholar?oi=bibs&cluster=4944920843669159892&btnI=1&hl=de (Schöpp, U. (2008). A formalised lower bound on undirected graph reachability. In Logic for Programming, Artificial Intelligence, and Reasoning (pp. 621-635). Springer Berlin/Heidelberg.)


How often is the ECCC queue cleared? I wanted to know as to how often are the submissions for ECCC cleared? Or do we know when is the next set of uploads going to be made on that site? Unlike arxiv where I know when my paper will go online, on ECCC there seems to be no way to know what is the timeline of my article. Last time I had submitted something on ECCC it took about 3 days for it go online. This time I am wondering as to why its taking longer. (..I had gone by this previous experience of 3 days to plan that I would refer to this online index number as reference for an upcoming talk of mine but now it seems I can't do that because the timeline looks indeterminate..)

If this is off-topic I will remove this. I guess people can just comment here rather than write "answers" so that I can eventually remove this question.

Here is an excerpt from the call for papers that explains the procedure:

As soon as a submission arrives, several board members with expertise in its declared area are notified, and once a week all board members are sent the list of pending submissions. Board members may screen a submission at their own discretion, and make the decision whether or not to accept it. An accepted submission is posted as a report immediately. A submission is automatically rejected after two months if no board member accepted it.

The call for papers also lists the members of the board.


Complement problems are not in the same class in parametrized complexity hierarchy? If not in $P$ By "complement problems", I mean the two problems' objective functions are complement. For example, the vertex cover and its complement independent set in this sense. For a graph $G(V,E)$, their answers add up to $|V|$. Another example is a problem I am working on. The dominating set problem and its complement "packing as many edges as possible so that there is no path or circle whose length is more than 2". Dominating set is $W[2]$-complete in the sense, and the edge packing problem is in $W[1]$-complete( whether it is complete in $W[1]$, I am still looking).

So, I come to the following audacious conjecture.
If problem A and problem B are complement, then A and B are not in the same class in the parameterized complexity structure, i.e. $FPT \subseteq W[1] \subseteq W[2] \subseteq \cdots W[SAT] $. Of course, there is another condition : A and B are not $P$ in the classical complexity hierarchy.

I am not very familiar with parameterized complexity theory. So, any advice is welcome. Thank you very much.

The complement problems Minimum (Edge) Bipartization and MaxCut are both in FPT, so the conjecture is false.


Universal and existential types I'm trying to wrap my head around the concepts of universal and existential types but everywhere I look, I see either logical or operational intuitions (or implementations) (e.g. TAPL book by B. Pierce), which, well... is good, but I'd like to see the definitions (where we look at them as sets) -- and from them, derivations of some laws, as well as justifications for our intuitions.

So, because I cannot find those definitions, I decided to do it myself and I think these may be reasonable:

$$\forall x.T \overset{def}{:=} \bigcap_{S - type} T[x := S] $$
$$\exists x.T \overset{def}{:=} \bigcup_{S - type} T[x := S] $$

But, in the aforementioned TAPL book, we are given this definition (although I would call it an identity)

$$\exists x.T \overset{def}{:=} \forall y. (\forall x. T \rightarrow y) \rightarrow y \quad (*)$$

I have two problems with this:

On the LHS of $(*)$ I would expect that $x$ was the only free variable of $T$ (because how to view a type "not-yet-built" with some free variables dangling in it?), but on the RHS it seems like $y$ may have some impact on $T$, so it better be a free variable in $T$. Hence LHS cannot be equal to RHS because sets of free variables of $T$ differ on both sides, right?
Even disregarding the concern at the point 1. -- I tried to rewrite RHS using my definitions and see if I can get my definition of existential type but I stuck:
$$ RHS = \bigcap_{S} (\forall x.T \rightarrow y)[y := S] \rightarrow S  = \bigcap_{S} \left(\bigcap_{R} T[x := R, y := S] \rightarrow S\right) \rightarrow S $$

It doesn't even remotely resemble my definition. Is it possible to simplify the formula I arrived at? Intuitively, because there are function types, it probably will never be equal to my definition. But if they are not equal -- are they at least 'isomorphic' in some sense? If not -- what "went wrong"?

Set theory is doing you some harm here and the sooner you liberate yourself from it the better it will be for your understanding of computer science.

Forget the intersections and unions. People get this idea that $\forall$ and $\exists$ are like $\bigcap$ and $\bigcup$, which is the sort of thing the Polish school was doing a long time ago with Boolean algebras, but it's really not the way to go (definitely not in computer science).

You would like to look at these as sets. Ok, but then we have to ignore issues of size and pretend that there is a set of all sets. (It is possible to fix the issues of size by passing to a different category.) The type $\forall x . T$ is really like the cartesian product
$$\forall X . T \mathrel{{:}{=}} \prod_{S : \mathsf{Set}} T[X \mapsto S].$$
That is, an element of $\forall X . T$ is a function $f$ from sets to sets: for each set $S$ it gives an element $f(S)$ of type $T[x \mapsto S]$. For instance, an element of $\forall X. (X \to X) \to (X \to X)$ is a function $f$ which takes a set $S$ and gives a function of type $(S \to S) \to (S \to S)$. Here are some such functions:
\begin{align*}
f_0(S)(g)(x) &\mathrel{{:}{=}} x \\
f_1(S)(g)(x) &\mathrel{{:}{=}} g(x) \\
f_2(S)(g)(x) &\mathrel{{:}{=}} g(g(x)) \\
f_3(S)(g)(x) &\mathrel{{:}{=}} g(g(g(x)))
\end{align*}
So we get one for every natural number, and it's kind of hard to think of any other examples. (Exercise: google "Church encoding of natural numbers".)

Next, let us look at the existential types. Firstly, the correct encoding of $\exists$ in terms of $\forall$ is
$$\exists X . T \mathrel{{:}{=}} \forall Y . (\forall X . (T \to Y)) \to Y$$
where the variable $Y$ does not appear in $T$! (This should be mentioned in Pierce's TAPL.) Before we look at this encoding, let us do $\exists X . T$ directly in terms of sets. This time it is a coproduct:
$$\exists X . T \mathrel{{:}{=}} \coprod_{S : \mathsf{Set}} T[X \mapsto S].$$
An element of $\exists X . T$ is a pair $(S, a)$ where $S$ is a set and $a$ is an element of $T[X \mapsto S]$. An example would the the type $\exists X . (X \times X \to X)$, whose elements are pairs $(S, m)$ where $S$ is a set and $m : S \times S \to S$ is a binary operation on it. This is also known as a magma. If you get a bit fancier you can express well known structures such as groups and rings (you need to invent identity types first).

Let us see how the encoding of $\exists$ in terms of $\forall$ works. It is wrong to expect that we will get an equality between $\exists X. T$ and $\forall Y . (\forall X . (T \to Y)) \to Y$ (NB: $Y$ is fresh) – only set theory would give people such expectations. We should expect the two to be isomorphic. So the task is to find a bijection between
$$A \mathrel{{:}{=}} \coprod_{S : \mathsf{Set}} T[X \mapsto S]$$
and
$$B \mathrel{{:}{=}} \prod_{R : \mathsf{Set}} \left(\prod_{S : \mathsf{Set}} (T[X \mapsto S] \to R) \right) \to R.$$
This is an exercise in $\lambda$-calculus. In one direction we have the map $f : A \to B$ defined as
$$f(S,a)(R)(h) \mathrel{{:}{=}} h(S)(a)$$
and in the other a map $g : B \to A$ defined by
$$g(\phi) \mathrel{{:}{=}} \phi(A)(\lambda S . \lambda a . (S, a)).$$
(The notation $\lambda S . \lambda a . (S, a)$ means the function $S \mapsto a \mapsto (S, a)$.) Now we can check whether $f$ and $g$ are inverses of each other. One direction is easy:
$$g(f(S,a)) = f(S,a)(A)(\lambda S' . \lambda a' . (S', a'))
  = (\lambda S' . \lambda a' . (S', a')(S)(a) = (S, a).$$
The other direction looks like this:
$$f(g(\phi))(R)(h) = h(\pi_1(g(\phi))(\pi_2(g(\phi))).$$
We could go on a bit more by rewriting $g(\phi)$ to $\phi(A)(\lambda S . \lambda a . (S, a))$, but then we would get stuck!

It turns out that in set theory the encoding of $\exists$ in terms of $\forall$ does not work. But it does work in other setups, where types are not sets. For instance, you can convince yourself that in logic the statements
$$\exists x . \phi(x)$$
is equivalent to
$$\forall{P : \mathsf{Prop}} . (\forall x . (\phi(x) \Rightarrow P)) \Rightarrow P,$$
where $P$ ranges over all propositions (truth values, logical statements). Again, the variable $P$ should not occur in $\phi$.


Introductory resources on Computational Learning Theory Recently I've been reading a decent number of CoLT papers. Although I don't struggle with the individual papers (at least not more than I usually struggle with other theory papers), I don't feel I have a good broad grasp of the field as a whole.
Is there a standard text, surveys, or lecture notes for introducing CoLT at the graduate level?
I have a basic Theory A background, but no specific knowledge of Machine Learning or Statistics. I am mostly interested in things like PAC-learning and learning automata, and less interested in things like Bayesian inference and VC theory.
Related questions

Resource / book for recent advances in statistical learning theory

Kearns and Vazirani is maybe a bit old, but good introduction.


Functions and Counting Problems in Streaming Computation I have read a stream computation paper in STOC07(Paul Beame, T. S. Jayram, and Atri Rudra. Lower bounds for randomized read/write stream algorithms.) and FOCS08（Paul Beame and Trinh Huynh. On the value of multiple read/write streams for approximating frequency moments).
I am interested in this topic with design of algorithms and analysis of limitations.

I want a list of natural counting functions, which stream algorithm theorists often consider like NPcomplete problems list by Garey and Johnson .

Is there such a list ?

I don't know if there's a list of canonical hard problems, but there is a list of open problems in streaming as maintained by Andrew McGregor. This is not limited to the specific models you're referring to  though.


Fixed set of type constructors to simulate all intensional inductive families? I'm wondering, are there small dependent calculi that can simulate a language with inductive families (that is, has a type isomorphic to each inductive family, at least as powerful of induction principles).

For example, I'm thinking:

You can use propositional equality to turn an inductive family into an inductive type with equality constraints on the indices
You can use Sigma types to encode sums-of-products
You can get inductive types with a fixed-point type:

data Fix : (Type -> Type) -> Type where
  Fold : (f : Type -> Type) -> f (Fix f) -> Fix f

which is fine as long as f is strictly positive.

But I'm not certain that these give you the full power of inductive families, particularly whether Fix gives you the full power of eliminators/structural recursion for inductive families.

Are there any references on what is sufficient to model inductive families?

I'm aware of:

W-types, which don't work well in an intensional setting.
Church-encodings, which aren't powerful enough to prove that (0 != 1), and also don't work well in a predicative setting
Levitation/datatype-generic-programming, which seems to give you all of inductive families, but at the expense of having to keep a runtime representation of every type, with a lot of complexity related to this representation. This seems like a chainsaw where I need a knife.

I am not 100% sure this is what you want, but assuming you are looking for a  type theory with a closed set of type constructors, which can model inductive families, then what you want are indexed containers or dependent polynomial functors. What you should look at first is:

Thorsten Altenkirch, Neil Ghani, Peter Hancock, Conor McBride and Peter Morris's 2014 draft Indexed Containers.

This paper is an expanded version of Altenkirch and Morris's 2009 LICS paper. It is all formalized in Agda, and gives a set of codes for defining all the strictly positive families. If you need it, it also gives an interpretation of them into W-types (and M-types for coinductive families). This is probably what you want to look at first.

It may also be worth looking at Containers: Constructing Strictly Positive Types by Michael Abbott, Thorsten Altenkirch and Neil Ghani for the non-dependent case.

Category theorists also invented this concept, which they dubbed dependent polynomial functors. The original paper, and some I found helpful for reading it are:

Wellfounded trees and dependent polynomial functors by Nicola Gambino and Martin Hyland. TYPES 2003.
Generalized Polynomial Functors Marcelo Fiore, ICALP 2012. There is a bit more logical intuition in this paper.
A foundation for GADTs and inductive families: dependent polynomial functor approach. Makoto Hamana and Marcelo Fiore, WGP 2011. This paper shows how to interpret indexed families as polynomial functors.

Now, you might also ask whether or not inductive families are "the morally correct" syntax for indexed containers. The answer is: probably not, but this is because containers/polynomials are too rich to have an obvious syntax.

Tamara von Glehn's PhD thesis, Polynomials and Models of Dependent Type Theory, builds models of dependent type theory out of polynomial functors. This implies that the correct syntax for datatypes in type theory is type theory itself, and I just don't know how to connect that to language design. Someone should give it a try, though!
Pierre Hyvernat has an LMCS 2014 paper, A Linear Category of Polynomial Functors, which uses a different notion of morphism to give polynomials a monoidal closed structure. So perhaps datatype declarations should be written in a linear type theory?


Euclidean TSP in NP and square root complexity In this lecture notes by Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf, it is said that we don't know if Euclidean TSP is in NP:

  The reason being that we do not know how to calculate
  square roots efficiently.

On the other hand there is this paper by Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 saying it is NP-complete, which also means it is in NP. Although he doesn't prove it in the paper, I think he consider the membership in NP trivial, as is usually the case with such problems.

I am confused by this. Honestly, the claim that we don't know if Euclidian TSP is in NP shocked me, since I just assumed it is trivial -- taking the TSP tour as a certificat, we can easily check it is valid tour. But the problem is that there can be some square roots. So the lecture notes basically claim that we cannot in polynomial time solve the following problem:

Given rational number $q_1,\ldots,q_n,A\in\mathbb{Q}$, decide if $\sqrt{q_1}+\cdots+\sqrt{q_n}\leq A$.

Question 1: What do we know about this problem?

This begs the following simplification, which I was unable to find:

Question 2: Is this reducible to the special case when $n=1$? Is this special case polynomial-time solvable?

Thinking about it for a while, I came to this. We want polynomial time complexity with respect to the number of bits of the input, i.e., not the size of the numbers themselves. We can easily work out the sum to a polynomial number of decimal digits. To get a bad case, we need an instance of $q_{1,k},\ldots,q_{n,k},A_k\in\mathbb{Q}$ for $k=1,2,\ldots$ such that for every polynomial $p$, there exist an integer $k$ such that $\sqrt{q_{1,k}}+\cdots+\sqrt{q_{n,k}}$ and $A_k$ agree on the first $p(\text{input-size})$ digits of decimal expansion.

Question 3: Is there such an instance of reational number?

But what is $\text{input-size}$? This depends on the way the rational numbers are represented! Now I am curious about this:

Question 4: Is is algorithmically important if rational number are given as ratio of two integer (such as $24/13$) or in the decimal expansion (such as $2.5334\overline{567}$)? In other words, is there a family of rational numbers such that the size of decimal expansion is not polynomially bounded in the size of ratio representation or the other way around?

Q1. This is a notorious open problem. It is known to be in the fourth level of the counting hierarchy, due to [ABKM]. Not known to be in NP. The problem is not really in computing square roots as claimed in the lecture notes: $n$ bits of a square root of an integer can be computed in time polynomial in $n$ and the bitsize of the integer. The problem is, rather, how close the sum of square roots of integers can get to an integer, without actually being integral.

Q2. The $n=1$ case is of course easy. It's the same as $q \le A^2$, which is in polynomial time, because squaring a rational number is in polynomial time.

Q3. According to this page, the best that's known is that there are integers $a_1, \ldots, a_k, b_1, \ldots, b_k$, all between $1$ and $n$, such that $| \sum_{i = 1}^k \sqrt{a_i} - \sum_{i = 1}^k \sqrt{b_i}| = O(n^{-2k + 3/2})$. This is a lower bound of $\Omega(2k\log n)$ on the number of bits needed to be computed for the potentially harder problem which allows negative coefficients. The best upper bound on the number of bits is exponential in $k$.

Q4. I think the decimal representation could be quite inefficient. The length of the period is the multiplicative order of 10 modulo the denominator, which can be exponential in the number of bits of the denominator.


Busy Beaver Equivalent for the Untyped Lambda Calculus In the same way that the Busy Beaver function is defined for Turing Machines, we could define a similar function for the untyped lambda calculus:

Over all terms in the ULC composed of n abstractions, variables and applications, which has the longest normal form?

This could be defined in a couple ways: we could consider only strongly normalizing ULC terms, or we could look for the longest normal form over all replacements.

Clearly, this function is not computable for arbitrarily large n, for the same reason as for the standard Busy Beaver function. However, I am interested in whether anything is known about this function for small values of n. What values is it known for? What bounds exists for higher n? For what n is the value known to be independent of ZFC?

Sequence https://oeis.org/A333479 in the On-Line Encyclopedia of Integer Sequences mostly answers your question. The question of shortest term for which lack of a normal form cannot be proven in ZFC remains open, but one candidate is the 213 bit Laver program presented in https://codegolf.stackexchange.com/questions/79620/laver-table-computations-and-an-algorithm-that-is-not-known-to-terminate-in-zfc


Voronoi diagram in a graph Let $G$ be a graph with (positively) weighted edges.
I want to define the Voronoi diagram for a set of nodes/sites $S$, to
associate with a
node $v \in S$
the subgraph $R(v)$ of $G$ induced by all the nodes
strictly closer to $v$ than to any other node
in $S$, measuring the length of a path by the sum of weights on the arcs.
$R(v)$ is $v$'s Voronoi region.
For example, the green nodes below are in $R(v_1)$, and the yellow nodes
are in $R(v_2)$.

I would like to understand the structure of the Voronoi diagram.
As a start, what does the diagram of two sites $v_1$ and $v_2$ look like,
i.e., what does the 2-site bisector look like (blue in the above example)?
I think of the bisector $B(v_1,v_2)$ as the complement of $R(v_1) \cup R(v_2)$
in $G$.  Here are two specific questions:

  Q1. Is the bisector of two sites connected in some sense?

  Q2. Is $R(v)$ convex in the sense that it contains the shortest path between any two
  nodes in $R(v)$?

Surely this has been studied before.  Can anyone provide references/pointers?
Thanks!

Addendum for Suresh's comment:

Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs.
Information Processing Letters 27, 125–128 (1988)

Erwig, M.: The graph Voronoi diagram with applications. Networks 36(3), 156–163
(2000)

both references copied from

Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson, Ying Daisy Zhuo: Round-Trip Voronoi Diagrams and Doubling Density in Geographic Networks. Transactions on Computational Science 14: 211-238 (2011)


Surjection from a type to a universe We work in homotopy type theory. Can there be a type $A:U_m$ and a map $f:A\to U_n$ for some $n\geq m$ such that the type $\prod_{T:U_n} \|\mathrm{fib}_f(T)\|$ is inhabited?

No, there can't be such a surjection. Here's how to derive a contradiction, if there is a surjective map $f : A \to U_n$, where $A:U_m$.
Since $m\leq n$, we can pull $f$ back along the embedding $U_m \to U_n$. This gives a surjective map $f' : A' \to U_m$, and it is not hard to see that the type $A'$ is equivalent to a type in $U_m$. Thus we have a surjective map from a type (equivalent to a type) in $U_m$ into $U_m$, and the join construction can be applied with these hypotheses to conclude that the type $U_m$ itself is equivalent to a type in $U_m$. This is well-known to lead to a contradiction.


MSO properties, planar graphs and minor-free graphs Courcelle's theorem states that every graph property definable in monadic second-order logic can be decided in linear time on graphs of bounded treewidth. This is one of the most well-known algorithmic meta-theorems.

Motivated by Courcelle's theorem, I made the following conjecture :

  Conjecture : Let $\psi$ be any MSO-definable property. If $\psi$ is solvable in polynomial-time on planar graphs, then $\psi$ is solvable in polynomial-time on all classes of minor-free graphs.

I want to know if the above conjecture is obviously false i.e., is there an MSO-definable property that is polynomial-time solvable on planar graphs but NP-hard on some class of minor-free graphs ?

This is the motivation behind my earlier question : Are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g.

Being 4-colorable?  Certainly MSO, and trivial on planar graphs.  It's NP-complete for a large enough forbidden clique minor, by reduction to planar 3-colorability.


What happens if we try to extract a witness but it actually does not exist from a term of existential type? Given a term t : ∀x.∃y.(¬(x = 0) ⇒ x = S(y)) in Martin-Lof's type theory, what's the value of w(t(0)), where w is the operator that extracts the witness of a term of existential type?

Any value. It depends upon which $t$ you are given. A term of type $\exists y.(\neg(0 = 0) \Rightarrow 0 = S(y))$ is a pair of an int $y$ and a function that takes a proof of $\neg(0=0)$ and gives you a proof of $0 = S(y)$. You can use a term of type $\neg(0 = 0)$ and type $0 = 0$ (from reflexivity) to derive a term of any type you want. This includes a term of type $0 = S(0)$, $0 = S(1)$, $\ldots$. So, you can make $y$ any integer you want.


How would you define a set of 'fundamental operations' over an object? I'm writing an implementation for a common array structure.

As you would find already familiar, an array is an ordered data structure that you can transform with different (hopefully self-explained) operations like:

set object at index
insert object(s) starting at index i
remove object(s) starting at index i
splice
push
pop
shift
unshift
clear

And then you could intuitively see that you could just code a set of 'fundamental operations' from where you could construct all the other ones. For instance, you could use splice to emulate the behavior of all other operations but you could also use insert and remove to construct all of them.

My question is, then, how would you define those 'fundamental operations'?

Is splice a construct of insert and remove, therefore insert and remove being fundamental?

Or are insert and remove special cases of splice, therefore splice being the fundamental operation for the whole group?

Is there some theory or field of CS that deals with these things?

P.S. Sorry if I'm making a lot of mistakes when presenting the question. I don't know about the correct language for this and have never studied this stuff formally. I hope that I explained myself correctly.

There is no standard notion of "fundamentalness".  It's not clear that what you are looking for is meaningful or makes any sense.  What is "fundamental" is a matter of perspective; I don't see any reason to privilege insert as more fundamental than splice, or vice versa.

So, if you need a concept of "fundamental" for some reason, you'll need to define for yourself what you mean by "fundamental".  If you're going to head that path, I would suggest that you start by asking yourself, "Why do you care?"

Personally, I suspect an XY problem.  I suspect you're asking the wrong question, and you should go back and ask yourself why you want to know and what you will do with the answer -- and that might help you identify a more sensible question or a more pragmatic path to achieving your real goals.


Explain Gurvits's tensor-rank interpretation of Deolalikar's paper [Note: I believe this question in no way hinges on the correctness or incorrectness of Deolalikar's paper.]

On Scott Aaronson's blog Shtetl Optimized, in the discussion about Deolalikar's recent attempt on P vs NP, Leonid Gurvits made the following comment:

  I tried to understand/reformulate the approach, and here
  is my, perhaps very minimalist, attempt: the discrete probabilistic distributions in the paper can be viewed
  as tensors, or very special multilinear polynomials.
  The assumptions “P=NP” somehow gives a (polynomial?)
  upper bound on the tensor rank. And finally, using
  known probabilistic results, he gets nonmatching
  (exponential?) lower bound on the same rank. If I am right, then this approah is a very clever, in a good sense
  elementary, way to push the previous algebraic-geometric approaches.

Despite the suspected/known flaws in Deolalikar's proof, I'm curious:

  In what way can the distributions discussed in Deolalikar's paper be considered as tensors, and how do the statements of his results (regardless of their correctness) translate into statements about tensor-rank?

[I was reading something I thought was totally unrelated and then had an "aha moment" so I think I've figured out at least part of the answer.  I'm not sure if this is what Gurvits had in mind, but this makes sense to me.]

A distribution on n binary variables $x_1,...,x_n$ can be viewed as an element of the tensor product $\mathbb{R}^2 \otimes \dotsb \otimes \mathbb{R}^{2}$ (n factors) (actually the associated projective space, but we'll get to that).  If we label the basis elements of each copy of $\mathbb{R}^2$ by $|0\rangle$ and $|1\rangle$, then a basis of this tensor product space is given by the set of all n-bit strings.  If we have an element of this tensor product whose coefficients sum to 1, then we can interpret the coefficient of any given n-bit string as the probability of that string occurring -- whence, a probability distribution!  Now, since we only want probability distributions (coefficients summing to 1) we can normalize any vector in the tensor product to have that property.  By only considering normalized tensors, we are really only considering elements of the projective space of this tensor product.

Now we have to connect tensor-rank to Deolalikar's notion of polylog-parametrizability.  According to this page by Terry Tao, it seems that Deolalikar's notion of polylog-parametrizability is that the distribution $\mu$ can be "factored into potentials" as $\mu(x_1,...,x_n) = \prod_{i=1}^{n} p_i(x_i ; x_{pa(i)})$ where pa(i) is a set of polylog(n) variables, defined to be the "parents of i" and $p_i( - ; x_{pa(i)})$ is a distribution on $x_i$ that depends only on these parent variables.  Moreover, the directed graph of parents should be acyclic.

Let's start with a very simple kind of distribution. Suppose $\mu$ satisfies $\mu(x_1, ..., x_n) = \prod_{i=1}^{n} p_i(x_i)$ for some distributions $p_i$ (where $p_i$ depends only on $x_i$).  Then it is hopefully clear that the corresponding tensor is the rank 1 tensor: $(p_1(0)|0\rangle + p_1(1)|1\rangle) \otimes \dotsb \otimes (p_n(0)|0\rangle + p_n(1)|1\rangle)$.

For a slightly more complicated distribution, suppose we want to consider the uniform distribution over the strings where $x_{2i} = 1 - x_{2i+1}$ (they are each other's negation) for all $i$.  In Tao's interpretation of Deolalikar's language, this would be a $O(1)$-parametrizable distribution.  Then this corresponds to the tensor $(|0\rangle \otimes |1\rangle + |1\rangle \otimes |0\rangle) \otimes \dotsb \otimes (|0\rangle \otimes |1\rangle + |1\rangle \otimes |0\rangle)$ (needs to be normalized).  If we write this out in full, it contains $2^{n/2}$ terms, and so has tensor-rank at most $2^{n/2}$ over $\mathbb{R}^2$.  However, over $\mathbb{R}^2 \otimes \mathbb{R}^2$, it has tensor-rank 1!  I believe the latter fact corresponds to the fact that the factorization can be described by $O(n)$ numbers -- $O(1)$ for each pair of adjacent bits, for each of $O(n)$ adjacent pairs.  Significantly smaller than the $2^n$ real numbers required in theory for an arbitrary distribution mu on the Boolean cube.

I'm still having trouble formulating two issues, and would appreciate further answers on them:

Making the latter correspondence precise
Writing out the formulae for the tensor corresponding to polylog-parametrizable distribution, and getting an upper bound on its rank.


About estimating escape time of gradient Langevin dynamics I am trying to understand the argument in the proof of Lemmma 6.3 (page 18) of this paper https://arxiv.org/abs/1902.08179. Let me summarize the conceptual crux of the argument here using a slightly different notation than them.

Here we are given $F : \mathbb{R}^d \rightarrow \mathbb{R}$ a convex, differentiable and $L-$smooth function with a minimizer at $x^*$ and 3 constants : $r$ and $C_\xi$ and $i_{max}$ (a positive integer). Now for $\xi_{t,1}$ a sequence of bounded random variables and $\xi_{t,2}$ a sequence of Normally distributed random variables we have the following dynamics happening,

$$x_{t+1} = x_t - \eta_t (\nabla F(x_t) + \xi_{t,1}) + \sqrt{\eta_t} \xi_{t,2}$$

which starts from $x_0$ s.t $\Vert x_0 - x^* \Vert \leq r$

Now they consider a coupled toy Markov chain $x'_t$ s.t $x'_0 = x_0$ and,

$$\text{if } \Vert x_t' - x^* \Vert \geq r \text{ then } x'_{t+1} = x'_t  $$
and $\text{if } \Vert x_t' - x^* \Vert < r \text{ then } x'_{t+1} = x'_t - \eta_t (\nabla F(x_t') + \xi_{t,1}) + \sqrt{\eta_t} \min (C_\xi, \Vert \xi_{t,2} \Vert) \frac{\xi_{t,2}}{\Vert \xi_{t,2} \Vert} $

Hence it seems that the primed sequence is designed s.t it never comes back into the ball once it leaves the interior of the $r$ sized ball around the global minimum of the function.

Now the main technical claim they make to relate the primed and the unprimed sequence is this : say the event $E := \{ \exists i \in \{1,\ldots,i_{\max}\} s.t \Vert x_i - x^*\Vert > r\}$ then some curious union bounding is giving them,

$$\mathbb{P} \left [ E \right ] \leq \sum_{i=1}^{i_{max}} \left ( \mathbb{P} [\Vert x_i'-x^*\Vert^2 \geq r^2] +  \mathbb{P} [ \Vert \xi_{i,2} \Vert \geq C_\xi ] \right )$$

Can someone kindly explain why is the above inequality true?

Observe that the following event contains your event $E$: either (1) for some $i$, $\|\xi_{i,2}\| > C_{\zeta}$ (in which case $x_{i+1}$ and $x_{i+1}'$ are no longer the same), or (2) for some $i$, $x_i'$ leaves the ball. It might be easier to see containment (in the opposite direction) of the complement events: if for all $i$ both $\|\xi_{i,2}\| \le C_{\xi}$ and also $x_i'$ is inside the ball, this surely means that $x_i=x_i'$ for all $i$ and hence also $x_i$ is always inside the ball.

The union bound should now be clear.


NP-Complete Convergent Reductions? A professor I knew in grad school told me about asking his students to reduce an NP-Complete problem to another, then back to the original, then back again and then watching with amusement as the resulting reductions grew out of control.  Eventually this led me to think that there should be some theory that could get a handle on the size introduced by reductions.

For example, what prevents us from taking a source NP-Complete problem (3-SAT, say) and adding a particular type of structure in the resulting NP-Complete problem (HAMILTONIAN CYCLE, say) such that reducing back to the original (3-SAT) would notice the structure and get back the original instance?  Maybe the original problem would need to be 'pre-structured' so that this type of 'ping-ponging' between NP-Complete problems could occur.

In other words, what prevents us from adding some (polynomial amount of) structure to our NP-Complete problems so that reductions from one NP-Complete problem to another converge in size?  The algorithms for reductions would need to notice the structure embedded in the instance and add their own if need.  I could imagine the features to be indicators for the reduction algorithm so that subsequent reductions would be able to avoid instance inflation.

What do these reductions look like?  What's our current best 'inflation factor'?

Surely I'm not the first to think of this.  Does anyone have references that discuss this type of reduction?  Barring that, does anyone have any ideas on what type of structure needs to be added to achieve this result?  I would be surprised if such a method wasn't possible but I would happily hear about any references about impossibility of such a method.

Great question! I have also had thoughts along similar lines, but not found anything in the literature that fully answers all of these questions. However, for this part of your question, I think a satisfactory answer is given by Berman & Hartmanis:

  what prevents us from adding some (polynomial amount of) structure to our NP-Complete problems so that reductions from one NP-Complete problem to another converge in size?

In some sense, nothing: Berman & Hartmanis showed that if two languages have one-to-one, polynomial-time invertible, length-increasing reductions between them in both directions, then the languages are p-isomorphic. (Here a one-to-one function $f$ is poly-time invertible if there is a poly-time function $g$ such that $g(f(x)) = x$ for all $x$, and $g(y)=\bot$ if $y$ is not in the image of $f$.) Two languages being p-isomorphic basically just means that one is a re-encoding of the other, and thus preserves the "structure" of the other in some sense, that I think is similar to what you're talking about. All known natural $\mathsf{NP}$-complete problems are p-isomorphic. The idea of the proof is a ping-pong-type argument.

Finally, as another pointer to the literature: Although the notion of $\mathsf{NP}$-complete is not sensitive to the size of the reduction (so long as it's bounded by a polynomial), the Exponential Time Hypothesis (ETH) and its variants are sensitive to super-linear blow-ups in size. So there may be some work on ETH that addresses parts of your question.


Where do people publish/submit their work on type theory? Besides the most common venues (perhaps POPL, ICFP, LICS and FSCD), where else are papers on type theory commonly published?

Especially, I'm looking for more "pure mathematical" venues/journals which publish work on type theory (especially of the more theoretical kind) from time to time.

You can follow the activities of the EUTypes network, and see what meeting are organized. The list of events is growing nicely. As for journals, I can think of Logical Methods in Computer Science and Mathematical Structures in Computer Science. I can also think of some journals which are owned by you know who, so not mentionable.


Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs Crossposted from MO.

Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).

  Are there NP-hard graph problems that can be solved in
  polynomial time for $C$ other than Clique and Clique
  cover?

If I remember correctly, this is impossible for
independent set (unless $P=NP$).

Search in graphclasses.org didn't find any.

A class for which Clique and Clique cover are
polynomial is C5,C6,X164,X165,sunlet4,triangle-free

Edit

Negative for IS and Domination is in this paper. Page 2, the graphs $S_{i,j,k}$.

I think there is a number of hard problems that become easy for triangle-free graphs; especially those deal directly with triangles such as Partition Into Triangles (Does G have a partition into triangles?). Other less trivial examples include:

Stable Cutset Problem (Does G have an independent set S such that G-S is disconnected?). See:  On stable sutsets in graphs, Discrete Applied Math. 105 (2000) 39-50.
Intersection Graph Basis (Is G the intersection graph of subsets of a k-element ground set?). See: Problem [GT59] in: Garey & Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness.


Generating uniform integers in a range from a random generator with another range Let $p$ and $q$ be two positive integers. I have an oracle that can generate a uniform integer in $\{1, \ldots, p\}$, the integers thus produced being independent across oracle calls. My goal is to generate a random number in $\{1, \ldots, q\}$ with uniform probability, and to do so in a way that minimizes the expected number of oracle calls required.

My question is: What is an optimal algorithm to solve this problem? I expect this to be a standard problem, so I'd be interested in pointers to the name of this problem in the literature. A special case of this problem ($p = 5$ and $q = 7$) is a standard puzzle or interview question (see here, but I was unable to find pointers to a generalization, and I don't see any optimality proof in those answers.

Of course, in general, the problem will not be solvable with a bounded number of oracle calls. Take for instance $p = 2$ and $q = 3$, or more generally, cases where some prime divisor of $q$ is not a divisor of $p$, and it is clear that for any bound $N$, the number of possible outcomes when doing $N$ calls, i.e,. $p^N$, cannot be divided evenly in $q$ buckets for each possible value.

One natural approach outlined here is to see the oracle calls as generating a uniform real number in [0, 1] from its $p$-ary writing, and terminate whenever the first decimal in the $q$-ary writing of that number is certain: think of it as using the oracle to select a subdivision of size $1/p^k$ in the interval $[0, 1]$, and concluding whenever the interval that you fall in is included in one of the $q$ intervals $[i/q, (i+1)/q]$ for $0 \leq i < q$. However, this approach does not seem optimal: for instance, for $p = q+1$, the approach only concludes in one call if the call returns 1, otherwise a second call is necessary. By contrast, a simpler rejection-based approach that calls the oracle, concludes if it falls in $\{1, \ldots, q\}$, and rejects and tries again if it falls in $q+1$, seems to have better performance.

One can try to generalize the rejection-based approach to the following: letting $k$ be minimal such that $p^k \geq q$, use $k$ oracle calls to get a uniform integer $n$ in $\{1, \ldots, p^k\}$. If $n$ falls in $\{1, \ldots, M\}$, for $M > 0$ the smallest multiple of $q$ which is $\leq p^k$, return $n \text{ mod } q$, otherwise try again. However it would seem that the additional information of which excess value in $\{M+1, \ldots, p^k\}$ was obtained could be also used in the next attempt. I can imagine how to do this (see here for a proposed algorithm, which I think is correct), but I have no idea of how to prove the optimality of such a scheme.

I am also curious about the natural variation of this problem where you want to generate not a single random number in $\{1, \ldots, q\}$, but a stream of such numbers. What's the expected number of calls per number, and an optimal method in this case?

[Note that an alternative vision of the problem that does not involve randomness at all is to think of the outcome trees: each node is either a leaf with label in $\{1, \ldots, q\}$ corresponding to a decision, or an internal node with $p$ children corresponding to an oracle call. An algorithm is a (generally infinite) such tree where, for each $1 \leq l \leq q$, the probability mass of all the leaves labeled $l$ (i.e., the sum of the mass over leaves, where the mass of each leaf is $1/p^h$, where $h$ is its height) is equal to $1/q$; and its expected performance is the sum, over all leaves, of $h/p^h$ (probability mass of this leaf, times the number of oracle calls performed in that case).]

I think I can show the optimality of a scheme that I skteched in the question, the one that does rejection sampling but reuses the remaining entropy.

Description of the scheme. Thinking as an algorithm, the scheme is the following. It has two parameters, an integer $n$, and a bound $m$, $0 \leq n < m$, with the invariant that $n$ was drawn uniformly at random in $[0, m[$. (I'll rephrase everything to ranges of the form [0, n[ rather than $\{1, \ldots, n\}$ because it's simpler.)

At each step we do the following:

if $m < q$, then we need more entropy: let $n'$ be the result of calling the oracle that samples in $[0, p[$ uniformly, and recurse with $n := n p + n'$ (i.e., a combination of the current $n$ and the new draw) and $m := m p$ (a larger interval). It is clear that if $n$ is uniform in $[0, m[$ and $n'$ is uniform in $[0, p[$ then the combination $n p + n'$ is uniform in $[0, mp[$
if $m \geq q$, then let $M$ be the largest multiple of $q$ which is smaller than $m$. If $n$ is in $[0, M[$, then we return $n \text{ mod } q$ as the result: this is uniform. Otherwise, the remainder $n - M$ is uniform in the range $[0, m - M[$, so we recurse with $n := n - M$ and $q := q - M$.

In pseudocode, reformulating the second point to substract $q$ multiple times instead of finding $M$, we get the following very simple algorithm:

int algo(int n, int m) {
  // invariant: n is uniform in the range [0, m[
  if (m < q)
    return algo(p*n + randint(p), m * p);
  if (n < q)
    return n;
  return algo(n-q, m-q);
}

algo(0, 1);

Optimality. This algorithm is, I think, optimal. To see why, let me reformulate it in terms of decision trees. What the algorithm does is, at every level, if we have at least $q$ leaves then turn into leaves the largest multiple of $q$ that you can, and grow the other nodes; otherwise just grow all nodes. (This makes it clear that the scheme is uniform, because the labels in $[0, q[$ on the tree are used in exactly the same way.)

Let us consider the (generally infinite) tree $T$ obtained by such a scheme, and consider a hypothetical tree $T'$ which denotes a uniform strategy with a better expected score.

It is clear that the performance of the tree depends only on the number of internal nodes at every depth. In other words, if I can show that, at every level, the number of internal nodes of $T'$ is at least that of $T$, then $T'$ cannot be better than $T$.

But consider any depth $k$. It is clear that, in $T$, the number of internal nodes is precisely $p^k - M$ for $M$ the largest multiple of $q$ which is below $p^k$: let's write $M = mq$. Now if $T'$ does better than this and has less than this number of internal nodes, let us divide the $p^k$ possible outcomes at depth $k$ of $T'$ between the decided ones and the yet undecided ones: more than $mq$ must be decided (to be better than $T$) and they must be split between $q$ outcomes, so the most probable outcome $v$ at that level must have probability at least $(m+1)/p^k$. Now by maximality of $m$ we have $(m+1)q > p^k$, so that $(m+1)/p^k > 1/q$. But by uniformity the probability of $v$ overall (so, in particular, at depth $k$) should not be more than $1/q$. So $T'$ cannot be uniform: outcome $v$ has probability $> 1/q$.

Hence, $T'$ never does better than $T$.

Expected performance. To compute the expected performance of this optimal strategy, one can just write out an equation system based on which recursive calls are performed by the pseudocode above (with the indicated probability distribution). The value of the parameters is bounded, so presumably, for given values of $p$ and $q$, this should be solvable as a geometric series or something like that. (This can be interpreted as an equation system describing the expected number of draws required for a decision forest with $n$ root nodes, $n$ being the number of nodes at the current level.)

Extending to multiple draws. One can generalize this scheme to draw multiple values, in the following way: when you have made a draw in $[0, q[$, instead of starting at a single-root decision tree for the next draw, start at a forest with $m$ nodes, the number of the outcomes with the same label at the level at which you decided, to use this remaining entropy. My conjecture would be that the resulting scheme would have the same performance as the $p$- and $q$-ary solution sketched in my question (so be optimal for multiple draws while concluding faster for a single draw). I have no proof of this fact, though.


Algorithm for approximating convex bodies by a convex hull of ellipsoids I am working in the field of structural engineering and I would like to find an efficient algorithm to construct an approximation (in the Hausdorff metric) of a convex body $K$ by the convex hull of $n$ ellipsoids, for some fixed $n$.  Currently I am only working in dimensions 2 and 3.

My first idea was to work in the dual space using the support function $h_K$ of $K$, which I can compute for a sample of $M$ points on the unit sphere $S_d$, and to minimize the discrete error between $h_K$ and the support function of the approximating set in the $l^{\infty}$-norm.

Does anybody have another idea or some references to give me?  I was unable to find any related work on this subject.

You may want to look into the "Crust" and "Power Crust" algorithms from Amenta, et al.  Rather than ellipsoids, it uses spheres, but I believe the concept is simliar as they are able to, at the limit, construct a water-tight body from an unorganized point-cloud.  In their case the desire was to mesh the original intended shape from the medial axis created between the delaunay and voroni spaces of the point-cloud rather than a convex hull of the points, but you may be able to glean some interesting ideas.

The associated papers can be found here:

A New Voronoi-Based Surface Reconstruction Algorithm

The Power Crust

The Power Crust, Unions of Balls, and the Medial Axis Transform


Pursuing Theoretical Computer Science after CS major So I am currently a sophomore majoring in Computer Science. In the Data Structures course that I am currently studying, I studied the basics of complexity of a program and big O-notation, etc. That got me interested in complexity theory and maybe pursuing TCS later on.
I have always had a great interest in mathematics and although I chose not to major in it (The math department at my university is not very good), I still plan to take some courses like Analysis, Abstract Algebra etc. (I have already taken Discrete Mathematics).  Initially, I started as a physics major so I have also taken two Quantum Mechanics courses.
I was just wondering if graduate admissions in TCS require a minor or major in mathematics or just some specific courses. Because, as far as my mathematical knowledge/skill is concerned, I think I have a strong background since I have always enjoyed solving problems involving proofs (although maybe not very formal ones) and sometimes just solving questions as a hobby.
Which courses are recommended to take if I want to maybe go into TCS later? Considering that I have 2 years left for my undergrad. Also, what are other possible sub-fields in TCS that I could consider?
The math/phy courses I have already taken are: LA, Calc 1 and 2, Discrete math, QM 1 and 2, Probability.

In order to get some feeling of what TCS might look like, I recommend watching the lectures given by Prof. Ryan O'Donnell:
https://www.youtube.com/c/RyanODonnellTeaching/playlists
And lectures given by Prof. Tim Roughgarden:
https://www.youtube.com/channel/UCcH4Ga14Y4ELFKrEYM1vXCg/playlists
And by Prof. Jeff Erickson:
https://www.youtube.com/channel/UClzjdrM8L81bVX_a6u6Hobg/playlists
You may also want to browse some of the podcasts by Simons Institute:
https://www.youtube.com/c/SimonsInstitute/playlists
Good Luck!


For which graph classes the fractional chromatic index rounded up equals the chromatic index? Let $\chi'_f(G)$ be the fractional chromatic index.

For which graph classes $\lceil \chi'_f(G) \rceil = \chi'(G)$?

Since $\chi'_f(G)$ is computable in polynomial time,
 solving this gives tractable graph classes.

Experiments with Sage suggest this is true for
perfect graphs on up to $8$ vertices, though
Sage's implementation is not inefficient.

It is known that for any multigraph $G$ on at most 8 vertices, $\chi'(G)$ is the maximum of the maximum degree and the ceiling of the odd-sets bound, see http://dx.doi.org/10.1016/S0012-365X(96)00364-0 (so what you find with sage is not very surprising).

This recent arXiv manuscript gives some more references for your problem (top of page 3)
http://arxiv.org/pdf/1406.0757v1.pdf

Beside bipartite graphs, non-trivial classes with the property you're looking for include series-parallel graphs.


Is this homework problem on T-joins wrong? In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn below.

The statement of the problem is incorrect.
But $T$-joins are indeed very much related to the perfect matching problem. What the theorem that 9.3a is supposed to be conveying is:
Assume $G$ is connected.
Suppose that $T = V$. The minimum $T$-join can be found as follows: construct a complete graph $G'$ such that the weight on an edge (a,b) in $G'$ is the length of the shortest path between vertices $a$ and $b$ in $G$. Now, find a minimum weight perfect matching in $G'$. This gives the minimum $T$-join in $G$.


Teaching end-course material in a computational-models course As TAs in an undergrad course on computational models, every year we are faced with a dilemma of what material to teach in the last few weeks of the course.

To be specific, our typical syllabus is as follows (basically the first few chapters of Sipser):

Finite Automata: DFA, NFA, determinization, Myhill-Nerode, etc.
Turing Machines: computability (RE,R, mapping-reductions, undecidability results).
Complexity classes: P, NP, PSPACE, karp-reductions, Savitch's theorem, Time/Space Hierarchy theorems.

Now comes the question of what to do next (usually we have about 3 weeks left).

Option 1: NL, coNL, logspace reductions and the Immerman Zzelepcsényi theorem.

Option 2: Randomized complexity (RP, BPP), but in a very low level, since probability is not a prerequisite for the course.

Option 3: Communication complexity - describing a communication model with some very initial results, describing IP and trying to prove $IP=PSPACE$, but usually only getting up to $coNP\subseteq IP$.

Option 4: Kolmogorov complexity. (we haven't tried this one yet).

Other options are welcome.

The question, to be as precise as possible, is as follows:

Assuming that at least 50% of the undergrads are not interested in theory, and that most of them will not continue to grad school, what would be most fitting, so as to teach  interesting material (i.e. less definitions, more theorems), while keeping it somewhat relevant to other disciplines in CS (or, heaven-forbids, the industry)?

My personal answer: I think that NL is a good option - theoretically it is interesting since we have some impressive results (NL=coNL), and practically it is interesting since many exponential time algorithms can be composed with NL algorithms to produce PSPACE algorithms (e.g. NFA universality). On the other hand, one might argue that it is more important to get acquainted with randomized algorithms.

If I'm a student, I would've liked to learn more about other computational models (primarily, lambda calculus and recursive functions). More and more programming languages are incorporating functional features, and learning these subjects would give a great insight into this perspective of thinking about computation.


Determinant modulo m What are the known efficient algorithms for computing a determinant of an integer matrix with coefficients in $\mathbb{Z}_m$, the ring of residues modulo $m$. The number $m$ may not be prime but composite (so computations are performed in ring, not a field).

As far as I know (read below), most algorithms are modifications of Gaussian elimination. The question is about the computational efficiency of these procedures.

If it happened that there is some different approach, I also curious about it.

Thanks in advance.

Update:

Let me explain the source of this question. Assume, $m$ is a prime number. So $\mathbb{Z}_m$ is a field. And in this case we can perform all computations using numbers less than $m$, so we have some nice upper bound on all operations on numbers: addition, multiplication and inversion --- all needed operations to run Gaussian elimination.

On the other hand we can not perform inversion for some numbers in case $m$ not a prime. So we need some tricks to compute determinant.

And now I am curious what are the known tricks to do the job and whether such tricks could be found in and papers of books.

There is a combinatorial algorithm by Mahajan and Vinay that works over commutative rings: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html


Implied Clause and Resolvent (I posted this question on MathSE first, no answer, that is the reason why I come here.)

Let $F$ be a 3-CNF formula on $n$ variables. A clause $c$ is implied by the formula if $F$ and $F \wedge c$ are equivalent.

Question : Is it true that each 4-clause  implied by $F$ (if there are any) is also the resolvent of two implied 3-clauses ?
By extension, is it true that each $k$-clause ($k> 3$) implied by $F$ is also the resolvent of two strictly smaller implied clauses ? (a $k$-clause ($k\leq n$) contains exactly $k$ literals in it).

Thank you for your answers.

Here is a counterexample:
$$
(a \lor y \lor s) \land (\overline{y} \lor b \lor z) \land (\overline{z} \lor c \lor d) \land (\overline{s} \lor b \lor t) \land (\overline{t} \lor c \lor d).
$$
This formula implies $a \lor b \lor c \lor d$, but only the five listed 3-clauses, no two of which resolve to $a\lor b\lor c\lor d$.


Rendering of type-level computation Programming languages with dependent types and/or higher-kinded types feature what might be called compile-time computation at the type-level.  This is usually defined as follows (I'm omitting some details for simplicity), see e.g. [1, 2, 3].

A notion $\equiv_{type}$ of type-equivalence is defined on types, e.g. $(\lambda x^{K}.\alpha)\beta \equiv_{type} \alpha[\beta/x]$  or $(\Pi x^{\alpha}.\beta)M \equiv_{type} \beta[M/x]$, where $M$ ranges over programs, $K$ over kinds, and $\alpha, \beta$ over types.
Then the typing system is enriched with a variant of the following rule.
$$
\frac{
\Gamma \vdash M : \alpha
\quad
\alpha \equiv_{type} \beta
}{
\Gamma \vdash M : \beta
}
$$

However, we can easily extend the relation $\equiv_{type}$ to typing environments $\Gamma$ pointwise,
and also to programs, e.g. $\lambda x^{\alpha}.M \equiv_{type} \lambda x^{\beta}.M$ whenever $\alpha \equiv_{type} \beta$, leading to a rule

$$
\frac{
\Gamma \vdash M : \alpha
\quad
\Gamma \equiv_{type} \Delta
\quad
M \equiv_{type} N
\quad
\alpha \equiv_{type} \beta
}{
\Delta \vdash N : \beta
}
$$

I have never seen this done. I assume that it's just a question of convenience and that both approaches are equally expressive, but I am not sure! Is there some problem with the second approach?

H. Barendregt, Introduction to generalised type systems.
H. Barendregt, Lambda Calculi with Types.
B. C. Pierce, Types and Programming Languages.

In your reference [2], Barendregt shows that the rule

$$ \frac{\Gamma\vdash N:\alpha\quad M\rightarrow^* N\quad \alpha\equiv \beta}{\Gamma\vdash N:\beta} $$

is indeed admissible for Pure Type Systems, as (a trivial consequence of) Corollary 5.2.16.

However there is an issue with your original rule already: the rule should read

$$ \frac{\Gamma\vdash N:\alpha\quad\alpha\equiv \beta\quad {\bf \Gamma\vdash\beta : s}}{\Gamma\vdash N:\beta} $$
for some sort $s$, otherwise you may introduce ill-formed types into your typing judgement, like $(\lambda x y. y)\ \Omega\ (\alpha\rightarrow\alpha)$.

This can be a problem for your extended rule, as usually you only allow well-formed types into your context, with a rule along the lines of

$$ \frac{\Gamma\vdash \alpha:s}{\Gamma,x:\alpha\ \ \mathrm{wf}}$$

If you add the relevant well-formedness requirements ($\Delta\ \mathrm{wf}$ and $\Delta\vdash\beta:s$), and restrict the term level to reduction rather than conversion, then your sophisticated rule becomes admissible.

This is a not completely trivial induction, using the following Lemma:

  If $\Gamma\vdash t:\alpha$, $\Gamma\equiv\Delta$ and $\Delta\ \mathrm{wf}$ then $\Gamma\vdash t:\alpha$

The lemma is proven by induction using an application of the conversion rule at the variable case. The theorem is then proven using the above lemma to discharge the conversion case.

You could adopt the opposite point of view of keeping your more general conversion rule and weakening the context formation rule to

$$ \frac{\Gamma\vdash \beta:s\quad \beta\equiv \alpha}{\Gamma,x:\alpha\ \ \mathrm{wf}}$$

then you get a system with possibly ill-formed types, but no additional typeable terms, though I think this is a very non-trivial result.


find the most similar topological ordering of a dag Given a permutation $L$ of the $n$ vertices of the directed acyclic graph $G=(V,E)$.
Question: is it NP-hard to find the topological order of the $G$ that is the most similar to the given permutation $L$?
(The most similar is that the least number of elements' positions are changed.)
Note: the topological order means the $n$ elements should be placed according to the constraints in $G$.

It is NP-hard. The reduction is from $CLIQUE$, so suppose we are given an undirected graph $H$ on $n$ vertices and $m$ edges, with a parameter $k$, and our task is to decide whether $\omega(H)\ge k$. We will need some sufficiently large numbers $M\gg N \gg n$, where we need about $N=n^2$ and $M=n^3$.
The graph $G$ will have two disjoint parts. The first part will have $M+M^2$ vertices such that there is an arc from each of the $M$ vertices to each of the $M^2$ vertices. In the order $L$ the $M^2$ vertices will have position $M+1$ to $M^2+M$. Since $M$ is huge, this implies that any optimal solution starts with the $M$ vertices, followed by the $M^2$ vertices. From the $M$ vertices, some can be in good position. As we can put these arbitrarily, we can easily determine this optimum; denote it by $X$.
The second part of $G$ will encode $H$. For every vertex of $H$, $G$ will have $N$ vertices. In $L$ each of these will take one of the first $M$ positions. Because of our earlier observations, none of these can keep their original position in an optimal solution, so we should place them to make other vertices 'happy'. For every edge of $H$, $G$ will have exactly one vertex, with $2N$ arcs going into it, one from each copy corresponding to one of its end-vertices. In $L$ each of these will have position $M^2+M+kN+1$ to $M^2+M+kN+m$. Since after the first part of $G$, we have only $kN$ places left before these positions, and $N\gg n$, this means that at most as many of these $m$ vertices can be in position, as many edges can be spanned by $k$ vertices.
To summarize, we can have $M^2+X+\binom k2$ vertices of $G$ in the same position as in $L$ if and only if $\omega(H)\ge k$.
ps. Notice that $G$ has only two levels, i.e., its longest (directed) path has length one.


What does the contention-free communication assumption really mean in the context of DAG scheduling? In many papers about DAG (directed-acyclic graph) scheduling in distributed systems, the authors make the assumption that the communication between the processors of the system where the DAG is scheduled is contention-free.

Does that mean they assume that each communication link can transfer concurrently an infinite number of messages (connections) and each connection uses the full bandwidth of the communication link?

For example, in case there are 5 concurrent connections on a 100Mb/s communication link from processor A to processor B, the speed of each connection is assumed to be 100Mb/s instead of 20Mb/s (i.e. 100/5=20)?

Many thanks in advance.

Not my field of expertise, but I think this is a relaxation in comparison with real-life scenarios. In actual systems, once a connection has been established and a "packet" has been sent (what packet here means depends on the context of the problem being solved), it is possible that an unscheduled interrupt occurs  that pauses this communication and allows a new communication with a different processor to occur.

I believe this relaxation means that once a "packet" is sent, we assume that the other processors do not interrupt this connection until this quantum of information has been sent. Essentially, it makes the processors being collaborators instead of antagonizers and it simplifies the analysis, while still keeping it reasonable, since all processors stick to the schedule and do not monopolize the connection (i.e. they will stop transmitting once this quantum of information has been sent, instead of maintaining their connection and sending their entire message in the expense of others, thus ignoring the schedule given).


Is it possible to verify a typechecker for a total dependently-typed language in that language's logic? I understand the diagonalization argument against implementing an eval function in a total language, and that typechecking in a dependently typed language requires evaluation, so implementing a typechecker for a total dependently typed language in itself is out. But is it possible to write a typechecker T for total dependently typed language A in (possibly non-total) language B, formalize B in A, and prove the correctness/termination/etc. of T in that formalization (without relying on cheats like including a primitive operation in B that does typechecking)? If not, is it possible to add some (presumably non-computable?) axiom to A that is not included in T and allows the proof to go through without allowing verifying incorrect implementations?

More concretely, suppose I have some formalization of turing machines in Coq and write a turing machine that takes a finite text stream (encoded in some reasonable format) and outputs a 1 if it represents a well-typed Gallina fragment and a 0 otherwise. Could I prove termination and correctness of that turing machine in Coq itself?

As often in these matters, the encodings are important: you could have some silly encoding of Turing machines or Gallina terms or both where an input string $\langle n\rangle$ represents "the $n$-th well-typed term in Gallina". The TM that accepts this is trivial, and you'd be able to prove correctness and termination of the machine easily.

See e.g. this Mathoverflow question: https://mathoverflow.net/questions/223109/does-the-notion-of-provably-total-function-depend-on-the-chosen-representation

However, for any reasonable representation, any proof that the "usual" type checking algorithm terminates implies termination of reduction for well-typed terms, which in turn implies consistency of the underlying logic as suggested here. This is impossible if Coq/Gallina is actually consistent, per the second incompleteness theorem.

Two obvious fixes:

Add consistency of Coq (or some equivalent or stronger statement) to your list of axioms. One possible axiom is: consistency of ZFC + $\omega$-many inaccessible cardinals. If you want something more computational, you can add a strong enough form of induction-recursion. I don't think anyone's worked out the details for the CiC yet, but I imagine they're very similar to those for (for instance) Agda.
Add some constraints on the representation of well-typed terms to be checked. In Gallina, terms carry implicit computational content, to be executed as the usual type-checking algorithm runs. However one could imagine an explicit form of the language, where each term comes with a natural number representing the "gas" it is allowed to use, aka the number of steps it must not exceed during reduction. Then the correctness proof for the type-checking algorithm would be conditional on not exceeding this explicit limit of computation.

Note that talking about computability of these axioms doesn't make much sense: a single axiom on it's own is always computable in the sense of computable sets which is usually what we mean when we talk about computable theories.

However an axiom may or may not have computational content, for example an axiom $\exists x,\ P$ may cause a theory to lose the existence property, if there is no closed term $t$ which satisfies $P[t/x]$. However, an axiom that asserts that a Turing machine $T$ halts on all inputs is always correct from a computable (constructive) point of view if $T$ does indeed always halt in the "true" world.


Applications of computer science in biology Is there a survey or tutorial article which talks about application of theoretical computer science to emerging fields of applications of computer science in biology, bioinformatics and nanotechnology?

Are there any problems from these fields that are unsolved and are of intrinsic merit to theoretical computer science?

Are there any algorithms that are already useful or potentially useful in current or future real-world applications and products in these fields? Is there any article which talks about real-world applications and products?

Quite a few programs have resulted from the application of notions from theoretical computer science or mathematics to problems in biology. This includes phylogeny, sequence alignment, and genome rearrangement (see this, chapter 15) software. But you may be asking too many or too unfocused questions at once.


Sufficient condition for termination of an orthogonal first-order rewriting system? I have a terminating orthogonal first-order rewriting system with finite rule set $R$.

Question: What would be an algorithmically verifiable sufficient condition on a new rule $l\to r$ such that for the rule set $R\cup \left\{l\to r\right\}$ the system also terminates? (How to extend the rule set maintaining the termination property?)

This is an entire field of research! In general, you cannot ensure termination of $R\cup\{l\rightarrow r\}$ by examining simply $l\rightarrow r$ and the knowledge that $R$ is terminating.

Indeed, even if $l\rightarrow r$ shares no function symbols with $R$ you may introduce non-termination! Here is a famous counter-example by Toyama. Take the following systems:

$$f(0,1,x) \rightarrow f(x,x,x)$$
and
$$p(x,y) \rightarrow x $$
$$p(x,y) \rightarrow y$$

each system individually is terminating, and you'll note that both systems do not share symbols, and are o̶r̶t̶h̶o̶g̶o̶n̶a̶l̶,̶ ̶a̶s̶ ̶i̶s̶ ̶t̶h̶e̶ ̶u̶n̶i̶o̶n̶ ̶o̶f̶ ̶t̶h̶e̶ ̶s̶y̶s̶t̶e̶m̶ not orthogonal at all! However, the combination is not terminating. The following term rewrites for ever: $f(p(0,1), p(0,1), p(0,1))$.

There is a further counter-example in which both systems are confluent. However orthogonality is a sufficient condition for modular termination (in addition to not sharing symbols). see this survey of modularity results by Gramlich.

However, there are ways to modularly add rules to a rewrite system even with shared function symbols without introducing non-termination. The most common is dependency pairs. There is a syntactic criterion that guarentees that you do not add cycles to the dependency graph, which captures possible sequences of rule applications.

The dependency graph is uncomputable, but there is a simple heuristic which allows to over-approximate it in an efficient way. If the rule does add a cycle to the graph, all is not lost! It becomes necessary to attempt to find an ordering that makes the rule safe to remove. Here's an overview of the AProVE system which implements many many techniques to show termination of rewrite systems in general. You might want to check the associated references.


What is the computational complexity of Acyclic Joins? I am quite new to relational algebra, but I realize that there are efficiency proofs for processing Acyclic joins. I have not been able to understand these results, but this particular problem is quite interesting to me. Given the following table, say $R_i$, $i \in \{1..n\}$

\begin{array}{|c|c|c|}
\hline
A_{i}& A_{i+1} \\ \hline
0 & 0 \\ \hline
0 & 1 \\ \hline
1 & 0 \\ \hline
1 & 1 \\ \hline
\end{array}
Now, I want to evaluate $R_{1}\bowtie_{A_2}R_{2}\bowtie_{A_3} ... R_{n-2}\bowtie_{A_{n-1}}R_{n-1}$, which is going to be a table with attributes $A_{1} .. A_{n}$ and $2^{n}$ rows(Basically resembling a Truth table). What is going to be the computational complexity of evaluating this join, given that it is an acyclic, K-uniform join ? Also, are there any gaurentees for cyclic joins which are of the form as I mentioned above (i.e same the column names keep changing but the table attribute remain the same for ex. AB,BA,AC)

It essentially depends on what you mean by "evaluating this join". If you want to compute the whole table, then the $2^n$ blow-up is unavoidable, just because you need to store all these values.

However, given an acyclic query, you can compute the "semi-join" in time linear in the size of the data and linear in the size of the query. The semi-join is the projection of the results on the variables you still need to finish the computation. In your case, you inductively compute a relation $B_i = \Pi_{A_i,A_{i+1}}(R_1 \bowtie \dots \bowtie R_i)$. In the general case, you compute it inductively on the join tree in a bottom-up fashion and you only keep the variables that appears in the bag you are visiting. More details on this approach could be found in [1] or [2, Chapter 6].

Now you can also enumerate all tuples in the result with a polynomial time delay between two solutions. Even though you need an exponential time to enumerate all solutions, you can guarantee to have enumerated $t$ solutions after a time  $t \times poly(n)$. You can even sometimes (with extra structure) guarantee a constant delay between two solutions. You can read more in [3] or in [4] for a more generic approach.

There is a lot more you can do on acyclic conjunctive queries in polynomial time such as counting the number of tuples in the result [5] (you need to be quantifier free however, or it becomes #P-complete again). One way of uniformly explains these tractability results is through the lens of factorized databases [6]. The paper is quite dense but the main idea boils down to the following: given an acyclic conjunctive query $Q$ and a database $D$, you can compute in time linear in the size of $D$ and $Q$, a circuit computing $Q(D)$. This circuit only usess Cartesian products gates and disjoint union gates and its input are small relations. Given such a circuit, you can then show that it is tractable to enumerate the tuples of the relation it represents (you can also count and do many other interesting things).

References

[1] Flum, Jörg, Markus Frick, and Martin Grohe. "Query evaluation via tree-decompositions." Journal of the ACM (JACM) 49.6 (2002): 716-752.

[2] Libkin, Leonid. Elements of finite model theory. Springer Science & Business Media, 2013.

[3] Bagan, Guillaume, Arnaud Durand, and Etienne Grandjean. "On acyclic conjunctive queries and constant delay enumeration." International Workshop on Computer Science Logic. Springer, Berlin, Heidelberg, 2007.

[4] Idris, Muhammad, Martín Ugarte, and Stijn Vansummeren. "The dynamic yannakakis algorithm: Compact and efficient query processing under updates." Proceedings of the 2017 ACM International Conference on Management of Data. 2017.

[5] Pichler, Reinhard, and Sebastian Skritek. "Tractable counting of the answers to conjunctive queries." Journal of Computer and System Sciences 79.6 (2013): 984-1001.

[6] Olteanu, Dan, and Jakub Závodný. "Size bounds for factorised representations of query results." ACM Transactions on Database Systems (TODS) 40.1 (2015): 1-44.


FNP complexity class Where can I find more information about the FNP complexity class? The only place I did find anything on FNP was http://en.wikipedia.org/wiki/FNP_(complexity)

However, that isn't sufficient for me to understand what that class actually means. For example, what should the FNP version of the decision version of the Hamiltonian Cycle Problem be?

The Hamiltonian Cycle Problem asks to decide, given a graph $G$, whether $G$ is Hamiltonian. This is the decision version. The function version(FNP) asks to actually find a Hamiltonian cycle in $G$ (if any).

I suggest looking at FNP, and related classes (such as NPMV and NPSV) in the Complexity Zoo.

In addition, a quick search in Google Books reveals many books in which you may find more info.

Please be more specific if you have more questions in mind.


Any references for techniques in FPT reductions? As everyone knows, Garey and Johnson's famous book (and many others) provides an excellent reference for reduction technique in classical setting. Are there any surveys or books on the
topic of reduction technique in parameterized algorithm, say the fpt reduction?

Both the original parametrized complexity book by Downey and Fellows, and the newer book by Flum and Grohe, are good references for reduction techniques.


A variant of maximum matching: disjunctive constraints on the endpoints' degrees of edges in matching The question is asked first at here. It described what the problem is and a trival greedy algorithm. Also the accepted answer gave a proof of its NP-completeness.

Problem: Given a graph $G(V,E)$, Find a subset of edges $M \subseteq E$. For each edge $(u,v) \in M$ , $\left( \left(d(u) < c\right) \lor \left(d(v) < c\right) \right)$ holds, where $c=3$. $d(u)$ means degree in $M$, i.e., $d(u)=|(u,v) \in M|$. We call this constraint a degree-constraint.
Output: The maximum sized (cardinality of edges) $M$.

The problem on $c=2$ is already $NP-complete$ as shown by Jukka Suomela. There is a $2-approximation$ algorithm for a general graph already.  Jukka devised a $O(|V|c)$ DP for this problem when $G$ is restricted on trees.

The case of trees and a constant $c$ seems to admit a straightforward dynamic programming algorithm.

You root your tree arbitrarily. You will start from the leaf nodes and propagate information towards the root. You will keep track of the following pieces of information for each subtree; here $u$ is a node and $T(u)$ is the subtree rooted at $u$:

$M_1(u)$ = best matching in $T(u)$ if $u$ has unlimited capacity,
$M_2(u)$ = best matching in $T(u)$ if $u$ has capacity $c - 1$,
$M_3(u)$ = best matching in $T(u)$ if $u$ has capacity $c$.

Note that $M_1(u)$ and $M_2(u)$ can be extended by adding the edge $(v,u)$, where $v$ is the parent of $u$.

All of these values are trivial to compute for a leaf node. Once you have computed these values for all subtrees of a node $v$, you can compute them for $v$; let $C$ consist of the children of $v$:

$M_1(v)$: For each $u \in C$ of $v$ we take either $M_2(u) + (v,u)$ or $M_3(u)$, whichever is better.
$M_2(v)$: We check all subsets $S \subseteq C$ of size at most $c - 2$. For each child $u \in S$ we take $M_1(u) + (v,u)$ or $M_2(u) + (v,u)$, whichever is better. For each child $u \notin S$ we take $M_1(u)$, $M_2(u)$, or $M_3(u)$, whichever is best.
$M_3(v)$: Similar to $M_2(v)$, but we consider subsets of size at most $c - 1$.

Everything is polynomial if $c$ is a constant.


Learning Mixture of Univariate Gaussians There are many papers on learning mixtures of multivariate Gaussians, which exploit various separation/projection techniques. What about one-dimensional (univariate) Gaussians -- any formal guarantees for learning these?

UPDATE: I should clarify: I am particularly interested in polynomial-time algorithms, in the number of mixture components.

Sorry, but there is lots of evidence that not only is this problem a pain in the univariate case, but moreover that having few dimensions actually makes things worse.

For evidence of the difficulty, please see Proposition 15 in Section 6 ("Exponential dependence on $k$ is inevitable") and the related Figure 1 of the following paper, the follow-up to Ankur Moitra and Greg Valiant's original joint work with Adam Kalai:

  Ankur Moitra and Greg Valiant, "Settling the Polynomial Learnability of Mixtures of Gaussians", FOCS 2010.

Proposition 15 states that there exist two mixtures of $k^2$ Gaussians on the line whose $L^1$ distance is exponentially small in $k$.  Since the construction is careful and the distribution parameters are well-behaved (polynomially-sized), this dependence on $k$ is real, and thus any algorithm whose performance depends on statistical distance will run into trouble.

For evidence that few dimensions actually forms a bad regime, please see the following very recent work:

  Daniel Hsu and Sham Kakade, "Learning mixtures of spherical Gaussians: moment methods and spectral decompositions", ITCS 2013.

This work presents a spectral method for recovering spherical mixtures of Gaussians.  So far, so good: univariate Gaussians are spherical.  However, this algorithm requires the $k$ individual means to span a rank-$k$ subspace (and the performance depends on the condition number of these points, meaning you can't just perturb your univariate instance in a $k$-dimensional space and then closely recover your original Gaussians).  As such, you could view their circumvention of the Moitra-Valiant lower bound as coming from an increase in dimension (and of course by maintaining the speherical nature you find from 1-d).

The above two papers have lots of excellent discussion, techniques, nice references.  This is not my field and I can only offer a very surface intuition for what is going on.  In the univariate case, things are really crowded, so the contribution of different Gaussians is confused and it's hard to disentangle them.  In the high-dimensional case, basically everything is far apart and low density; it's hard to get crowded, and easy to pick out points of high density (which now must reside near means).

I only have one other thing to point out, and that's the connection to $k$-means.  $k$-means has a DP in the 1-d case; google tells me it's from the 40s, and while I haven't seen that reference, we can cook up a DP fairly easily:  make your table have size $n\times k$, where $n$ is the number of points, and use "optimal $k$-means cost using $j\leq k$ means and the first $m\leq n$ data points" as your subproblem, noting that each mean owns a contiguous subset of the data.  As I tried just now to adjust this to the Gaussians case, it was interesting to see how the differences between these two scenarios became acute.  First, the hard vs. soft clustering aspect means we can't just knock out contiguous subsets and claim they are owned by some Gaussian (furthermore, for univariate Gaussians of differing variances, the regions where one or the other dominates aren't just two intervals..).  Second, we have no relationship between the variances, the univariate assumption really doesn't help us there (it would seem we need more; and of course, $k$-means is like knowing a fixed (common) variance up front).

So, oh well.


Name of this graph partitioning problem? (related to coloring) Given a graph $G=(V,E)$ and an integer $k$, find a partition $P_1, P_2, \dots, P_k$ of $V$ into $k$ parts that minimize the total number of edges between two vertices in the same part, i.e. $\sum_i |(P_i\times P_i)\cap E|$.
May someone please provide the name of this problem and/or references?
If $k$ is larger than or equal to the chromatic number of $G$, then the number of edges under concern is $0$. But if $k$ is lower than the chromatic number, then it is strictly positive. Also, it is trivially bounded by $m=|E|$ (in the case $k=1$).

(Copied from a comment:)
If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as "maximum k-cut" and also "maximum k-colorable subgraph".


An extension of Chernoff bound I am looking for a reference (not a proof, that I can do) to the following extension of Chernoff.

Let $X_1,..,X_n$ be Boolean random variables, not necessarily independent.
Instead, it is guaranteed that $Pr(X_i=1|C)<p$ for each $i$ and every event $C$ that only depends on $\{X_j|j\neq i\}$.

Naturally, I want an upper bound on $\Pr\left(\sum_{i\in[n]}X_i>(1+\lambda)np\right)$.

Thanks in advance!

What you want is the generalized Chernoff bound, which only assumes $P(\bigwedge_{i\in S} X_{i}) \leq p^{|S|}$ for any subset S of variable indices. The latter follows from your assumption, since for $S=\{i_1,\ldots,i_{|S|}\}$, $$P(\bigwedge_{i\in S} X_{i}) = P(X_{i_1} = 1)P(X_{i_2}=1|X_{i_1}=1)\cdots P(X_{i_{|S|}}=1|X_{i_1},...,X_{i_{|S|-1}}=1)\leq p^{|S|}$$
Impagliazzo and Kabanets recently gave an alternative proof of the Chernoff bound, including the generalized one. In their paper you can find all the appropriate references to previous work:
http://www.cs.sfu.ca/~kabanets/papers/RANDOM2010.pdf


Research in Coding Theory I have just started learning about coding theory. Hence, I would like to ask for your suggestions and guidance for a very beginner like me.

Which books are good for beginning coding theory? (I start reading the notes by J.I. Hall
from here).
Which topics now are hot in coding theory? so that I could look at and choose the track to follow.
Where I could find lastest preprints and papers on coding theory. I know only "Designs, Codes and Cryptography".

Many thanks in advance.

From a mathematical perspective: Try

  1) Handbook of coding theory - Huffman and Pless

  2) Fundamentals of Error-Correcting Codes - Huffman and Pless

  3) Introduction to coding theory - Ron Roth

  4) Algebraic Geometric Codes: Basic Notions - Vladut, Nogin and Tsfasman

  5) Introduction to Coding Theory - Van Lint

  6) Algebraic Geometry in Coding Theory and Cryptography - Harald Niederreiter and Chaoping Xing.

From an engineering perspective: Try

  1) Error Control Coding - Shu Lin and Daniel Costello

  2) Modern Coding Theory - Richardson and Urbanke

  3) Error Correction Coding - Todd K Moon

  4) Channel Codes: Classical and Modern - William Ryan and Shu Lin.

From Computer Science perspective: Try

  1) Madhu Sudan MIT Notes

  2) Algorithmic Results in List Decoding -  Guruswami

  3) Computational complexity - Boaz Barak (Chapter 19)

  4) Refer this cstheory question - Using error-correcting codes in theory

  5) Locally Decodable Codes - Yekhanin

  6) Chapter on applications of coding theory in complexity theory in Different Aspects of Coding Theory - Calderbank.


Survey on #P and/or counting problems Can anyone suggest a good and recent survey on counting problems and/or problems that are #P.

L. Fortnow. Counting complexity. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 81-107. Springer, 1997

This gives more of the structural complexity point of view (complexity classes, oracles, etc.), and discusses other classes related to #P. Although it's from almost 15 years ago, it's really not that out of date in terms of results.


Optimal sort algorithm in number of swaps Given a sequence of $n$ numbers, can it be sorted with $O(n \ln n)$ comparisons and $O(n)$ swaps/moves? Any pointer to publications on that matter or counterarguments showing a $\Omega(n \ln n)$ lower bound would help.

There exists a stable in-place sorting algorithm with $O(n \log n)$ comparisons and $O(n)$ moves.

See:
Gianni Franceschini: Sorting Stably, in Place, with $O(n \log n)$ Comparisons and $O(n)$ Moves. Theory Comput. Syst. 40(4): 327-353 (2007)
http://www.springerlink.com/content/d7348168624070v7/


A System for Visualizing Bibliography Information I'm looking for a software for visualizing main trends in some field.
Specifically, I want it to build a graph of the field with vertexes representing papers and edges representing how close papers are (probably, based on number of co-citations).
It seems to be very useful in order to find important subfields (clusters in the graph) and important papers (centers of the clusters).

To elaborate a little on my comment (which is slightly tangential).

There is a fun site called eigenfactor that provides nice visualizations of how various parts of science cite each other, and their relative size by publication/citation volume. Unfortunately their primary focus seems to be calculating impact factors for journals and so they operate on the level of journals, not individual papers/authors. However, they have a pretty interesting way of identifying subfields.

They use the number of citations from a journal A to a journal B as a weight on the edge from A to B. They then consider a random walk on the resulting graph. Such a walk tends to linger in topic clusters, and thus when they try to create a shortest description of the walk they tend to name the clusters and use a second index inside the cluster (kind of how you would have unique city names, and unique street names in each city, but redundant across cities). I thought it was a pretty nice way of finding clusters, and produces clusters that mimic how most people would divide the topics in science (with the occasional hilarious classification like putting Phys. Rev. Letters in Chemistry instead of Physics) You can read more in their paper or on the mapequation site.