Universal witness set for $NP$ Inspired by this answer given by Noam, which I think implies (if I understood correctly his answer ) that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from a strings space $S$ to combinatorial objects in some space $Y$ such that $A$= $\{ a: a=f(x), x \in S \}$. The space $S$ represents the set of all witnesses $x$ of an $NP$ problem $A$.

This motivates studying the properties of the space $S$ (of all witnessing strings $x$) for various $NP$ problems.

  Is there a published work that studies space $S$ for various problems inside $NP$ such as $P$ problems, $NPI$ problems, and $NP$-complete problems?

UPDATE 9/7/2015:

The following formalism is taken from Theory of computational complexity;

"A binary relation $R \subseteq\Sigma^* \times \Sigma^*$ is called polynomial honest if there exists a polynomial function $p$ such that $<x,y> \in R$ only if $|x|\le p(|y|)$ and $|y|\le p(|x|)$. A function $f:\Sigma^* \to \Sigma^*$ is polynomially honest  if the relation $\{ <x, f(x)>: x\in \Sigma^*\}$ is polynomial honest.

Therefore, $A \subseteq \Sigma^*$ is in $NP$ if and only if $A=Range(f)$ for some polynomial honest and polynomial time computable function $f$."

Now, assume that there exists a universal witness set $W \subseteq \Sigma^*$ such that for every $NP$-complete set $D_i \subseteq \Sigma^*$ there is some polynomially honest and polynomial-time computable function $g_i:W\to \Sigma^*$ such that $D_i=Range(g_i)$.

  What are the consequences of existence of a universal witness set for $NP$? Does it imply $P \ne NP$?

The last question is interesting only when the universal witness set $W$  is in $P$ (3SAT can be seen as universal witness set but it is not known to be in $P$).

My answer to the question is that I don't know of published work. However, I've recently been thinking a bit about formalizing what I believe is essentially your question, so I'll try to collect some thoughts in the following "extended comment", hoping that it will be interesting, useful, or spark productive discussion! (Maybe this is already well-known or studied, in which case I apologize.)
Consider the set of all languages on a fixed alphabet; call this the "universe". In analogy with a topology, we can define a sort of "computational space" as this universe together with a set of languages, i.e. a set of subsets of this universe. In particular $P$ is the set of languages decidable in polynomial time. I'll think of languages in $P$ as the analogues of open sets and polytime-computable functions (which will serve mainly as reductions) as the analogues of continuous functions.
Note that $P$ is closed under complement, finite union, and finite intersection, but not countable union or intersection (breaking the analogy).
Now in analogy with continuous functions, consider all polytime functions: functions $f: \Sigma^* \to \Sigma^*$ that are computable in polynomial time. You might also want to require that its input and output sizes are polynomially related (i.e. for some $p$, $|x| \leq p(|f(x)|)$). This choice could alter the sequel a little, so that's a caveat, but the whole discussion is sub-formal anyway.

We can see that the polytime functions satisfy the following property: $B \in P \implies f^{-1}(B) \in P$. We would like the following to be true: They are the only such "continuous" functions (note that output-size-messiness comes in when attempting to prove this converse). I don't know if it's true and it might even be equivalent to a very hard problem.

We can also see that a language $B$ is in NP if and only if it is the polytime image of a language in $P$, that is, there exists $A \in P$ and polytime $f$ with $f(A) = B$.
Sketch: If $A \in P$, then to decide the language $f(A)$ in nondeterministic polynomial time, given $y$, guess $x$ and accept iff $f(x)=y$. On the other hand, if $B$ is in NP, let $A = \{(x,w) : x \in B \text{ and $w$ is an NP certificate for $x$}\}$. $A$ is decidable in polynomial time and the polytime function $f$ that projects onto the first element of the pair satisfies $f(A) = B$.

Therefore, we can notice that $P = NP$ if and only if $P$ is closed under these polytime mappings, i.e. for all $A \in P$ and polytime $f$, $f(A) \in P$. The analogous statement in topology would be "all continuous mappings are open mappings".

We can see that an NP-complete set $B$ has the property that, for every $A \in P$, there exists a polytime $f$ with $f^{-1}(B) = A$. If $P \neq NP$, then an NP-intermediate set $C$ would therefore satisfy that there is some $A \in P$ with, for every polytime $f$, $f^{-1}(C) \neq A$; and also that it is not decidable in polynomial time, so there is no $A \in P$ and polytime $f$ with $f^{-1}(A) = C$.

There seem to be lots of sort-of interesting statements we can make, though their novelty/usefulness is probably dubious. For instance, I think something like this is true: "$P = NP$ if and only if every polytime mapping can be preimaged in polynomial time", (the analogy is that "every continuous function has a continuous inverse").
Similarly, you could probably translate lots of complexity statements into this framework but with again dubious utility. For instance, one-way functions (although I haven't thought about randomized algorithms...that could be quite interesting).
Final notes: I think the most interesting thing about this framework is that it seems not to relativize. One might of course think about other interesting complexity classes than $P$ and $NP$; one might also think of e.g. $DTIME(g(n))$ for a specific $g$; I'm not sure if that's interesting.


"Guarded" negative occurrences in definition of inductive types, always bad? I know how some negative occurrences can definitively be bad:

data False

data Bad a = C (Bad a -> a)

selfApp :: Bad a -> a
selfApp (x@(C x')) = x' x

yc :: (a -> a) -> a
yc f = selfApp $ C (\x -> f (selfApp x))

false :: False
false = yc id

However, I am not sure whether:

all inductive types with negative occurences can turn wrong ;
if so, there is a known mechanical way of doing so ;

For instance, I've been fighting trying to make this type go wrong:

type Not a = a -> False

data Bad2 a = C2 (Bad2 (Not a) -> a)

Any pointer to literature on this subject would be appreciated.

The reason for the ban on negative occurrences can be understood by analogy with the Knaster-Tarski theorem. This theorem says that

if $L$ is a complete lattice and $f : L \to L$ is a monotone function on $L$, then the set of fixed points of $f$ is also a complete lattice. In particular, there is a least fixed point $\mu{f}$ and a greatest fixed point $\nu f$.

In traditional model theory, lattices $L$ can be viewed as propositions, and the order relation $p \leq q$ can be understood as entailment (i.e., that $q$'s truth is entailed by $p$'s truth).
When we move from model theory to proof theory, lattices generalize to categories. Types can be seen as the objects of a category $\mathbb{C}$, and a map $e : P \to Q$ represents a proof that $Q$ can be derived from $Q$.
When we try to interpret types defined by recursive equations, e.e., $\mathbb{N} = \mu \alpha.\;1 + \alpha$, the obvious thing to do is to look for a generalization of the Knaster-Tarski theorem. So instead of a monotone function on a lattice, we know want a functor $F : \mathbb{C} \to \mathbb{C}$, which sends objects to objects, but generalizes the monotonicity condition so that every map $e : P \to Q$ gets a map $F(e) : F(P) \to F(Q)$ (with the coherence conditions that $F$ sends identities to identities and preserves compositions so that $F(g \circ f) = F(g) \circ F(f)$).
So if you want an inductive datatype $\mu \alpha.\;F(\alpha)$, you also need to supply a functorial action on terms for the type operator $F$ in order to be assured that the fixed point you want exists. The strict positivity condition in Agda and Coq is a syntactic condition that implies this semantic constraint. Loosely speaking, it says that if you build a type operator from sums and products, then you can always cook up the functorial action, and so any type formed in this way should have a fixed point.
In dependently-typed languages, you also have indexed and parameterized types, so your real task is more complicated. Bob Atkey (who has blogged about this here and here) tells me that a good place to look for the story is:

Structural Induction and Coinduction in a Fibrational Setting,  Claudio Hermida and Bart Jacobs 1997.
Fibrational Induction Rules for Initial Algebras, Neil Ghani, Patricia Johann, and Clement Fumex 2010.

As Andrej notes, fundamentally whether or not a negative occurence is okay or not depends on what your model of type theory. Basically, when you have a recursive definition, you are looking for a fixed point, and there are a lot of fixed-point theorems in mathematics.
One which I, personally, have made a lot of use of is Banach's fixed point theorem, which says that if you have a strictly contractive function on a metric space, then it has a unique fixed point. This idea was introduced into semantics by (IIRC) Maurice Nivat, and was extensively studied by America and Rutten, and was recently connected by Birkedal and his collaborators to a popular operational technique called "step-indexing".

Solving Reflexive Domain Equations in a Category of Complete Metric Spaces, Pierre America and Jan J. M. M. Rutten 1989.
The Category-Theoretic Solution of Recursive Metric-space Equations, Lars Birkedal, Kristian Støvring, and Jacob Thamsborg. 2010.

This gives rise to type theories where negative occurences in recursive types are permitted, but only when the negative occurences occur under a special "guardedness" type constructor. This idea was introduced by Hiroshi Nakano, and the connection to Banach's theorem was made both by myself and Nick Benton, as well as Lars Birkedal and his coauthors.

A Modality for Recursion, Hiroshi Nakano, 2000.
Ultrametric Semantics of Reactive Programs, Nick Benton and Neel Krishnaswami, 2011.
A metric model of guarded recursion, Lars Birkedal, Jan Schwinghammer, and Kristian Støvring, 2010.


Non-Uniform vs. Uniform Adversaries This question arose in the context of cryptography, but below I will present it in terms of complexity theory, since people here are more acquainted with the latter. This question is related to Problems in NP but not in Average-P/poly and Beating Nonuniformity by Oracle Access.

Informal statement: When do non-uniform adversaries (i.e. poly-size family of circuits) succeed in breaking a cryptographic scheme, but uniform adversaries (i.e. probabilistic poly-time Turing machines) do not?

Complexity-theoretic statement: This is not exactly the same as the above informal statement, but I'm actually interested in this version:

  What natural problems lie in $(\mathsf{NP} \cap \mathsf{P/poly}) - \mathsf{AvgP}$ ?

In other words, what hard-on-average natural $\mathsf{NP}$ problems can be solved by poly-sized family of circuits?

The word solved can be interpreted as the worst-case or average-case (the latter is preferred).

If natural problems cannot be found easily, artificial problems are acceptable as well.

There is hardly any natural problem which is believed to be in P/poly but not in P. The artificial examples can be adapted to answer your question.

Assume $E \neq NE$, then there is a unary language L in NP which is not in P -- unary means that all the strings in the language have the form $1^n$ for some n.

Then define L' to be the set of all strings x such that $1^{length(x)}$ is in L. This is in NP, it is in P/poly, and it is not in average polynomial time


Is this game solvable? Suppose we have two stacks of cards on a table. On each turn, each of two players draws a card from the top of one of the stacks. The game ends when there are no cards left in either stack. The person with the greatest sum then wins. If this were a chess problem, for example, one could attempt to solve this game by starting from a winning final position, and then inducting backwards. However, in this game, the final card picked up has little bearing, as it is the overall sum that results in a winner. Is it possible to find a game plan for perfect play, assuming both players pursue this game plan?

EDIT: The values of all the cards are known by both players, i.e. the players are omniscient when it comes to information about the cards. The card deck need not be complete, just some random cards in two stacks on a table, and we only care about the values.

EDIT 2: I'm wondering whether this can be solved efficiently with an algorithm that does not have to go through all the potential decisions in a decision tree.

I haven't thought it carefully, but I think You can use dynamic programming. If we have n cards in first deck and m cards in second deck, then there is n*m possible states of stack.

Best_Move(i,j)
    return Max(Stack1[i]-Best_Move(i-1,j),Stack2[j]-Best_Move(i,j-1))

You just have to remember all partial results, so they won't be calculated twice. This should give You the bes strategy in O(n*m).


Interdisciplinary topics between control theory and theoretical computer science I am in my second year in a MSc that doesn't relate too much with TCS though I wish it would. It's basically about control theory, signals and systems and I took classes in advanced systems (robust, nonlinear, optimal, stochastic), advanced signal processing and convex optimization.

I am trying to figure out a good area to tackle for my dissertation paper and I was wondering whether I can somehow relate to some TCS subject.

The only area that I can think of it could relate is optimization, but I don't have anything particular in mind, the whole subject being very interesting.

It would be great if you could share which topic you think belongs to both worlds.

PS: This question might be totally out of the scope of this Q&A site, so I totally agree if you feel like it's worth closing. Thanks!

Since you mentioned signal processing, you should look at the area of "compressive sensing".  Here is an excellent non-technical description of the main ideas involved: http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/


Intersection of languages in NP Can intersection of two languages in NP which are not NP complete be NP complete?

Can intersection of two languages in coNP which are not coNP complete be coNP complete?

Can intersection of two languages one in coNP but not complete and other in NP but not NP complete be NP complete or coNP complete?

Just an extended comment to better explain ARi's comment (I was writing it while I saw it).

It is sufficient to use a "large gap" approach similar to the one used in Lardner's theorem; for example:

$A_1 = \{ x \mid x \in SAT \land f(|x|) \text { is even}\} \cup \{x \mid f(|x|) \text{ is odd} \}$

$A_2 = \{ x \mid x \in SAT \land f(|x|) \text { is odd}\} \cup \{x \mid f(|x|) \text{ is even} \}$

Where $f$ is a slow enough increasing function computable in polynomial time. See for example its construction in Ladner's theorem proof in Appendix A.1 of Uniformly Hard Languages.

By construction $A_1, A_2$ are not NPC, but $A_1 \cap A_2 = SAT$


Does L have a definition in terms of circuits? Many complexity classes defined with Turing machines have definitions in terms of uniform circuits. For example, P can also be defined using uniform polynomial size circuits, and similarly BPP, NP, BQP, etc. can be defined with uniform circuits.

  So is there a circuit-based definition of L?

An obvious idea would be to allow polynomial size circuits with some depth limitation, but this turn out to define the NC hierarchy.

I was thinking about this question a long time ago, but didn't find an answer. If I remember correctly, my motivation was to understand what the quantum analog of L would look like.

Well, $L = SC^1$, where $SC^1$ is the class of languages computed by polynomial size circuits of $O(\log n)$ width.

As for $NL$, it could be characterized as the class languages computed by polynomial size skew circuits (which in some sense is just another way of saying nondeterministic branching programs).


What is the difference between standard SIFT descriptor and upright SIFT descriptor? I am conducting a research on the topic of mobile location recognition and recently I have reached the issue of extracting discriminative features. I've read that for upright images is strongly suggested using upright keypoints since they are more discriminative. My problem is that I don't understand clearly what is exactly an upright SIFT descriptor, the reference I found coining the term is:

Handling Urban Location Recognition as a 2D Homothetic Problem

Concretely in the reference they say the following:

  ... for images in which gravity direction information exist we project
  the gravity direction onto the facade and align the keypoints with
  this direction (upright SIFT) ...

My only clue is an implementation of this upright SIFT descriptor as part of an academic project from a course of Digital Image Processing at Stanford

Thank you very much, I would appreciate any insight.

SIFT algorithm detects keypoints, assigns orientation to them and then constructs a descriptor of that keypoint using the assigned orientation as a reference frame. Upright SIFT descriptor does the same thing, but forces orientation to be the vector (0, 1). So it's very simple: upright descriptor simply assumes that the orientation of the features doesn't change over_time/between_images and therefore just uses the unit vector directed upwards to construct the frame of reference.


Is uniform convergence faster for low-entropy distributions? Let $\mathcal D$ be a probability distribution on $\{0,1\}^d$. Let $X_1, \cdots, X_n \in \{0,1\}^d$ be i.i.d. samples from $\mathcal D$.  Let $\mu \in [0,1]^d$ be the mean of $\mathcal D$ and let $\overline X = \frac{1}{n} \sum_{i=1}^n X_i \in [0,1]^d$ be the mean of the samples.

By Hoeffding's inequality and a union bound, $$\mathbb{P}\left[\left\| \overline X - \mu \right\|_\infty \ge \varepsilon \right] \le 2d \cdot e^{-2n\varepsilon^2}$$ for all $\varepsilon \ge 0$. Equivalently, for $\varepsilon,\delta>0$, if $n \ge \frac{\log(2d/\delta)}{2\varepsilon^2}$, then $\mathbb{P}\left[\left\| \overline X - \mu \right\|_\infty \ge \varepsilon \right] \le \delta$.

This bound is tight (up to constants) in the worst case. In particular, the uniform distribution achieves this bound.

My question is whether better bounds are known if we know that $\mathcal D$ has low entropy.

Obviously, if $\mathcal D$ has no entropy (i.e., $\mathcal D$ is a point mass) then one sample is enough for perfect convergence. If the entropy is maximal, then $\mathcal D$ is the uniform distribution and the above bound is tight. What if the entropy is intermediate, e.g., $\mathsf H(\mathcal D) = \Theta(\log d)$? Could we replace $d$ with, say, $\mathsf H(\mathcal D)$ in the above bounds?

Some remarks about how I came to this question:

Let's imagine you are running the Multiplicative Weights algorithm for online learning or solving a repeated zero-sum game. Typically we assume that it outputs a full probability distribution at each step and the loss/gain is exactly the expectation over this distribution. What happens if we cannot output the whole distribution?

If you only output one sample from the MW distribution, then the environment/adversary/other player can best-respond to that move and force the MW algorithm to suffer large loss/small gain. So one sample is insufficient to retain the no-regret guarantee.

What if instead you have $n$ samples from the MW distribution? If $n$ is large enough, uniform convergence kicks in and the empirical distribution of the sample is close to the desired MW distribution and you get the no regret guarantee with high probability.

So the question is how many samples $n$ do you need from the multiplicative weights distribution to get the desired uniform convergence? One thing to note is that the entropy of the MW distribution decreases with each step. (Entropy is one way to analyze the MW algorithm.) So I was hoping that one could show that, as the MW algorithm proceeds, fewer and fewer samples are needed. That led to this question, which I think is interesting in its own right.

My question about MW arose from reading this paper. Here there is a specific cost to each sample from the MW distribution and that cost grows linearly with the number of time steps. Thus, if we could show that, in the final steps where the entropy is low (since MW has converged) and the cost is high, fewer samples are needed, then this might improve the algorithm.

First, let's use McDiarmid's inequality to conclude that
$$\mathbb{P}\left[|| \bar X - \mu ||_\infty \ge
\mathbb{E}|| \bar X - \mu ||_\infty
+
\varepsilon \right] \le  e^{-2n\varepsilon^2},$$
so it remains to bound $\mathbb{E}|| \bar X - \mu ||_\infty$.
Using Jensen's inequality,
$$ (\mathbb{E}|| \bar X - \mu ||_\infty)^2\le \mathbb{E}|| \bar X - \mu ||_\infty^2
\le \sum_{j=1}^d\mathbb{E}(\bar X(j)-\mu(j))^2=
\sum_{j=1}^d\mathrm{Var}[\bar X(j)]=\frac1{n^2}\sum_{j=1}^d\mathrm{Var}[X(j)],
$$
whence
$$ \mathbb{E}|| \bar X - \mu ||_\infty\le
\frac1{n}\sqrt{\sum_{j=1}^d\mathrm{Var}[X(j)]}.
$$
For sufficiently small variances, this is an improvement over your bound.

Update. A different approach would be to introduce the Rademacher random variables $\sigma_i$ and to use the standard symmetrization argument to obtain
$$ \mathbb{E}|| \bar X - \mu ||_\infty
\le2\mathbb{E}\max_{j\in[d]}\frac1n\sum_{i=1}^n\sigma_i X_i(j),
$$
where $X_i(j)$ indicates the $j$th bit of $X_i$. Now there must be a way to bound the latter Rademacher complexity using the entropy of $\mathcal{D}$, but I don't have anything off the top of my head. Massart's finite class lemma will give you a distribution-free bound of $O(\sqrt{\log(d)/n})$.


Is Quasi-polynomial time in PSPACE? I had done some search on this but I was not able to find an answer either way.
Huck answered it fully. Thanks :)

Here's a simple argument that shows that QP is not known to be in PSPACE:

Assume $QP \subseteq PSPACE$. Then we have $P \subsetneq QP \subseteq PSPACE$, where the first inclusion is proper by the time hierarchy theorem.

This separates $P$ from $PSPACE$, which is not known to hold, so $QP \subseteq PSPACE$ must also not be known to hold.

Indeed we have that $PSPACE \subseteq QP \Rightarrow PSPACE \subsetneq EXP$, but $QP \nsubseteq PSPACE$ does not separate the two classes by the THT (as stated in the question).


Are there more polynomial time problems with complexity lower bounds? I'm looking for more problems in $P$ with classical time complexity lower bounds.  Some people might wonder how you could prove such a lower bound.  See below.

Exponential Lower Bounds:

Claim: If you have a problem $X$ that is $EXPTIME$-complete under polynomial reductions, then there is a constant $\alpha \in \mathbb{R}$ such that $X$ is not solvable in $O(2^{n^{\alpha}})$ time.

Proof Idea: By the time hierarchy theorem, there is a problem $Y$ in $O(2^n)$ time that is not in $o(\frac{2^n}{n})$ time.  Further, there must be a polynomial reduction from $Y$ to $X$.  Therefore, there is a constant $c$ such that this reduction takes an instance of size $n$ for $Y$ to an instance of size $n^c$ for $X$.  The lower bound for $Y$ of $O(2^{n^{1-\epsilon}})$ time shifts to a lower bound for $X$ of $O(2^{n^{\frac{1-\epsilon}{c}}})$ time.

Polynomial Lower Bounds:

Some $EXPTIME$-complete problems have nice parameterizations into polynomial time problems.  Consider the problem $X$ from before.  Suppose we have a parameterization $k$-$X$ for $X$ such that:

For each fixed $k$, $k$-$X$ is in polynomial time.

There are of course exceptions to this, but intuitively, as $k$ grows the $k$-$X$ problems should get harder because $X$ has an exponential time complexity lower bound.

An Example:

One example problem that has come up is intersection non-emptiness for tree automata.  That is, given a finite list of tree automata, does there exist a tree that simultaneously satisfies all of the automata?

This problem was shown to be $EXPTIME$-complete here.  Further, we can parameterize the intersection problem by the number of automata $k$.  It can be shown that for fixed $k$, the intersection problem has time complexity $n^{\Theta(k)}$.

Question:

Are there any other $EXPTIME$-complete problems that have natural parameterizations into polynomial time problems with nice lower bounds?

Here's one involving a 2 player pebble game. You decide if it's natural (:

T. Kasai, A. Adachi, S. Iwata. Classes of pebble games and complete problems. 1979

Theorem 3.1 has the EXPTIME-completeness of pebbling. Theorem 3.3 has the easiness of k-pebble.

A. Adachi, S. Iwata, T. Kasai. Some Combinatorial Game Problems Require Omega(n^k) Time. 1984

Theorem 3.2 has the lower bound on k-pebble. Lastly, you might also be interested in:

T. Kasai and S. Iwata. Gradually intractable problems and nondeterminitstic log-space lower bounds. 1985

Sadly that these are all behind paywalls :(


Graduate studies (PhD) in CS Theory vs. Applied Math Given most American universities only accept applications in only one field, I'm trying to figure out what are the advantages/disadvantages of applying to a CS theory program vs an applied math program given one's interest lies somewhere in both departments.

To be more specific, my areas of interest in decreasing order are
1. Combinatorics (Both algebraic and extremal),
2. Optimization (Both convex and combinatorial),
3. Probability theory, randomized algorithm, and information theory.

I don't exactly know on what or with whom I want to work which makes applying to graduate programs a huge headache. So far my understanding is applied math programs are more flexible given CS theory groups are usually very small and focused. On the other hand, I feel a CS degree would fare better in industry if one happened to venture that path.

So to reiterate my question, for someone who doesn't exactly know what he wants to do but generally interested in aforesaid topics, which is better? CS Theory or Applied Math

My two cents are that in my university we've had both mathematics PhD students working on computer science questions (and faculty in the math department with interests in computer science), as well as some computer science students working primarily on purely combinatorial problems.

You might be right that it's sometimes easier to work on CS questions as a math student, rather than on pure math questions as a CS student. Keep in mind that at least in the first two years these two kinds of programs might be fairly different in content. As a math student you will be expected to take core math courses as real analysis, complex analysis, topology, algebra, etc. Combinatorics is usually not part of this core. For a CS program there will be a core CS requirement, which usually involves taking some mix of theoretical and more applied courses. While the core in a math program is fairly standard and strictly enforced, the core in a CS program tends to depend a lot on the program, and the requirements might be more flexible.

However, all that is not really of primary importance (although it will be loads of work) and is all over within the first two years. I understand it's hard to know what you want to work on before you're in grad school, and many students change  their fields. Nevertheless, I would encourage you to look at the faculty pages of schools you are considering, see what professors are working on, and write several emails to faculty and students. PhD level studies are much more about personal relationships and personal drive than they're about a program as a whole. Good programs at the PhD level in my view are distinguished by a strong faculty, and an energetic research culture, rather than by curriculum. You should inquire from faculty and current students about questions like the level of collaboration between math and CS departments. And you should really try to find faculty that have a mix of interests that appeals to you. It's a good idea to write to them to express your interest as well.

As far as industry jobs, I'm not sure there is a huge difference between a CS theory degree and an applied math  degree. But I am not very knowledgeable about this.


Are runtime bounds in P decidable? (answer: no) The question asked is whether the following question is decidable:

  Problem  Given an integer $k$ and Turing machine $M$ promised to be in P, is the runtime of $M$ ${O}(n^k)$ with respect to input length $n$ ?

A narrow answer of "yes", "no", or "open" is acceptable (with references, proof sketch, or a review of present knowledge), but broader answers too are very welcome.

Answer

Emanuele Viola has posted a proof  that the question is undecidable (see below).

Background

For me, this question arose naturally in parsing Luca Tevisan's answer to the question Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?

The question relates also to a MathOverflow question: What are the most attractive Turing undecidable problems in mathematics?, in a variation in which the word "mathematics" is changed to "engineering," in recognition that runtime estimation is an ubiquitous engineering problem associated to (for example) control theory and circuit design.

Thus, the broad objective in asking this question is to gain a better appreciation/intuition regarding which practical aspects of runtime estimation in the complexity class P are feasible (that is, require computational resources in P to estimate), versus infeasible (that is, require computational resources in EXP to estimate), versus formally undecidable.

--- edit (post-answer) ---

I have added Viola's theorem to MathOverflow's  community wiki "Attractive Turing-undecidable problems".  It is that wiki's first contribution associated to the complexity class P; this attests to the novelty, naturality, and broad scope of Viola's theorem (and IMHO its beauty too).

--- edit (post-answer) ---

Juris Hartmanis' monograph Feasible computations and provable complexity properties (1978) covers much of the same material as Emanuele Viola's proof.

The problem is undecidable. Specifically, you can reduce the halting problem to it as follows. Given an instance $(M,x)$ of the halting problem, construct a new machine $M'$ that works as follows: on inputs of length $n$, it simulates $M$ on $x$ for $n$ steps. If $M$ accepts, loop for $n^2$ steps and stop; otherwise loop for $n^3$ steps and stop.

If $M$ halts on $x$ it does so in $t=O(1)$ steps, so the run time of $M'$ would be $O(n^2)$. If $M$ never halts then the run time of $M'$ is at least $n^3$.

Hence you can decide if $M$ accepts $x$ by deciding if the run time of $M'$ is $O(n^2)$ or $O(n^3)$.


Template Metaprogramming and Turing Completeness I am trying to design a Turing Machine using C++ Template Metaprogramming. What steps must be taken to ensure that the code that I'm gonna write will actually build a Turing machine ? I have read that C++ templates are Turing complete but I don't actually know how to prove this thing.

How should I proceed? Turing completeness is really tough to understand and so simulating a Turing Machine would be tougher I guess. What do you guys suggest?

The article you want is C++ Templates are Turing Complete by Todd Verhuizen. It explains how things work in sufficient details. If you can faithfully encode a Turing machine and its behaviour in C++ templates, then this is sufficient to demonstrate Turing completeness.


$BPL$ with polylog random bits is in $L$ Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$.

My question is about a $BPL$ machine that uses only polylog many bits of randomness. In one of Goldreich's papers, it is mentioned in passing that a language decided by such a $BPL$ machine is actually in deterministic logspace $L$. But I am unable to find any explanations of this remark anywhere.

Why can it be derandomized completely in logspace?

It follows from this PRG of Nisan and Zuckerman. This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be decreased to $O(S)$.

In particular, in the setting you describe, we have $S = O(\log n)$, so the number of random bits can be reduced to $O(\log n)$. Then, we can derandomize the algorithm completely by enumerating over all possible coin tosses.


Technical article vs. research paper Being a professional software engineer, i have seen a lot of really interesting technical work, many of it is published as technical articles in technical journals and websites like http://www.drdobbs.com and http://www.codeproject.com and many others, here is a few examples in some areas of interest:

Algorithm engineering and implementation:

http://www.codeproject.com/Articles/18113/KD-Tree-Searching-in-N-dimensions-Part-I
http://www.codeproject.com/Articles/9021/Simple-and-fast-Huffman-coding
http://www.drdobbs.com/cpp/sorting-an-immutable-list/240163397
http://www.codeproject.com/Articles/33781/Calculate-Percentiles-in-O-1-space-and-O-n-time

Data structures:

http://www.codeproject.com/Articles/43103/SlimList
http://www.codeproject.com/Articles/2839/C-AVL-Tree-Template
http://www.codeproject.com/Articles/9138/Fast-Binary-Tree-Operations
http://www.codeproject.com/Articles/23198/C-String-Toolkit-StrTk-Tokenizer
http://www.codeproject.com/Articles/11274/Implementing-a-memory-efficient-search-tree-for-a

Text search:

http://www.codeproject.com/Articles/198236/Boolean-text-search-queries-and-their-processing
http://www.codeproject.com/Articles/20423/N-gram-and-Fast-Pattern-Extraction-Algorithm

Object oriented and generic programming:

http://www.codeproject.com/Articles/16006/Dynamic-Inheritance
http://www.codeproject.com/Articles/19444/Interface-Detection
http://www.codeproject.com/Articles/20085/Superior-container-classes-Smaller-faster-flexible
http://www.drdobbs.com/cpp/theory-versus-practice-the-great-divide/240160938

Database optimization:

http://www.codeproject.com/Articles/25728/Database-Virtual-Cursor

Real time processing:

http://www.codeproject.com/Articles/224733/Shared-Queue

This level of work is considered highly innovative from the technical/engineering point of view.

I wonder if any technical work can be considered an academic achievement and can be deployed in research papers as well as technical articles.

In other words:
When can a technical article be published as a research paper, in which areas? any examples?

Thanks

Thanks for the question; I had similar questions few years ago, before starting in research (I'm not necessarily assuming that's your case).

I've looked at a couple of the links, and they don't really look like research papers in form; I mostly can't really tell if their technical content could be made into a paper because I'm not an expert in the field, but I'm guessing "no". If you compare your links to a paper, you'll notice several differences. But highlighting them and their rationale might help.

The key concepts are:

Scientists learn new knowledge for humankind, and then share what they learn through research papers.
Moreover, we live in information overload, so readers only have time for the most important knowledge.

As a consequence, research papers have some key features.

A research paper contributes new knowledge in a field (novelty). To convince readers of this new information, it provides appropriate evidence to argue for it. What's appropriate evidence varies depending on the field and on what the paper claims.
In fact, since a paper must be novel, it must also argue that its content is novel (though that's done somewhat implicitly). That's done by comparing to related works in the field; if another work looks similar to a submission, the author must explain what's the novelty in his work. Moreover, no paper is entirely novel, so a paper must also say what was already known by citing its invention (except for things that are standard). As a rule, technical articles don't do that; they typically don't claim to be novel. Sometimes the author invented the technique by himself, but it was already known.
Good call for papers mention the criteria for judging papers — this one mentions novelty, importance, evidence and clarity.
A good research paper should also contribute knowledge that is "interesting", and explain it clearly to the reader. What's interesting varies according to the publication venue.
In fact, my favorite intro to research in book form is The craft of research, though what I've read is parts of this condensed version. I'd recommend to start reading it from the Amazon preview.

Example

The above is not really specific to computer science, so let's have an example.
Since most of your examples are in algorithms, I'll try to show what the above means for an algorithm paper (even though I'm not an expert in that area, so I hope I won't get it too wrong). Such a paper might claim that some algorithm is fast, and prove that through complexity analysis or experiments. That paper better claim that the algorithm computes something useful (otherwise, who cares that it's fast?), often because it's correct; appropriate evidence is then a correctness proof. Moreover, this algorithm probably reuses ideas already known to experts (which should be cited), but has some key differences from any similar works (which should also be cited) — maybe it has the same complexity but is more general, or is simpler to implement, or has any other virtues that experts have agreed are interesting.

By contrast, a paper on, say, programming languages would have different claims and different evidence, but would still follow the same basic structure.


Complexity of computing shortest paths in the plane with polygonal obstacles Suppose we are given several disjoint simple polygons in the plane, and two points $s$ and $t$ outside every polygon.  The Euclidean shortest path problem is to compute the Euclidean shortest path from $s$ to $t$ that does not intersect the interior of any polygon.  For concreteness, let us assume that the coordinates of $s$ and $t$, and the coordinates of every polygon vertex, are integers.

Can this problem be solved in polynomial time?

Most computational geometers would immediately say yes, of course: John Hershberger and Subhash Suri described an algorithm that computes Euclidean shortest paths in $O(n\log n)$ time, and this time bound is optimal in the algebraic computational tree model.  Unfortunately, Hershberger and Suri's algorithm (and nearly all related algorithms before and since) seems to require exact real arithmetic in the following strong sense.

Call a polygonal path valid if all its interior vertices are obstacle vertices; every Euclidean shortest path is valid.  The length of any valid path is the sum of square roots of integers.  Thus, comparing the lengths of two valid paths requires comparing two sums of square roots, which we don't know how to do in polynomial time.

Moreover, it seems completely plausible that an arbitrary instance of the sum-of-square-roots problem could be reduced to an equivalent Euclidean shortest-path problem.

So: Is there a polynomial-time algorithm to compute Euclidean shortest paths?  Or is the problem NP-hard?  Or sum-of-square-roots-hard?  Or something else?

A few notes:

Shortest paths inside (or outside) one polygon can be computed in $O(n)$ time without any strange numerical issues using the standard funnel algorithm, at least if a triangulation of the polygon is given.
In practice, floating-point arithmetic is sufficient to compute paths that are shortest up to floating-point precision.  I'm only interested in the complexity of the exact problem.
John Canny and John Reif proved that the corresponding problem in 3-space is NP-hard (morally because there may be an exponential number of shortest paths).  Joonsoo Choi, Jürgen Sellen, and Chee-Keng Yap described a polynomial-time approximation scheme.
Simon Kahan and Jack Snoeyink considered similar issues for the related problem of minimum-link paths in a simple polygon.

Maybe I miss something, but if we consider the "easy" case, where all obstacles are points, then we have the problem of computing the shortest path between two vertices in a planar graph, which, if I am not wrong, it is known as sums-of-square-roots-hard.

PS. I wanted to add a comment and not an answer, but I can't find how. I apologize for that. Can the admins please help me with this.


Is there any good and free Introduction to topological graph theory My knowledge in topological graph theory is in low, I need some good reference which has two simple thing, Definition of new concepts (like genus,graph embedding in surface, ...) also contains related theorem on this topic, It's not essential to prove theorem, I think there should be something like wiki or good survey.

I found some books, but first of all I need some overview on it, maybe it's not necessary to have book to come up with my problems, I found something in wolfram but it's not integrated, and It's not easy to find all related things (because I don't know them) and print them all to have in hand. So first I need good bible (specially free).

In fact I'm working in some aspects of planar graphs and some other types of graph which are near to them (like graphs with small genus), everyone know about filed has any suggestion (book, book chapter, Advise, ... ) I'll be happy to know it.

Also If you know any theorem or definition, I'll be happy to know it, and sure upvote it, because if there isn't good reference is good create one here.

My lecture notes on computational topology include some basic material on topological graph theory.  They don't come anywhere close to the completeness of Archeacon's survey (or Giblin's book, Mohar and Thomassen's book, or Gross and Tucker's book), but you may still find them useful.  (Start with "Curves on Surfaces".)

If you're a student, you may also find your local university library useful.  Most mathematics libraries have copies of all the books I mentioned, and they will actually let you borrow them for free, possibly for several months at a stretch.  Sadly, these books may only be available in a legacy format that is difficult to search and copy from, but hey, you get what you pay for.


Complexity of simple undirected graph isomorphism problem We define a simple undirected graph as a graph where no vertex has a loop and there is only zero or one undirected, unweighted edge between any pair of vertices.

My question:

What is the complexity of the best known algorithm for the simple undirected graph isomorphism problem?

I assume it should be a special case of the exponential algorithm by Babai et. al introduced in Canonical labeling of graphs.

As described in Reading List: Graph Isomorphism by Dave Bacon, this is not among the classes for which we have efficient algorithms. Thanks in advance for your answer.

Yes, the best known algorithm is still the algorithm from Babai and Luks, with runtime $\exp(O(\sqrt{n \log n}))$, where $n$ is the number of vertices in the graphs. Unless I'm mistaken, even the best known conondeterministic algorithm for graph isomorphism has exponential runtime. Babai and Luks' algorithm is plausibly near-optimal for deterministic algorithms, but there is much evidence that there is a polynomial time conondeterministic algorithm for graph isomorphism out there to be discovered. In particular, it is known that graph isomorphism is in coAM, and certain circuit lower bounds imply that coAM = coNP.


On proving it is hard to compute $g^{rb}$ with knowledge of $r$, given $g, g^a, g^{ab}$ I am trying to prove the following

  Given $g, g^a, g^{ab}$ it is hard to compute $r, g^r, g^{rb}$, for some arbitrarily chosen value of $r$

where $g ∈ \mathbb{G}, \mathbb{G}$ is a cyclic group of prime order $p$ and $r∈ \mathbb{Z}^*_p -\{0\} $ and $r \neq a$.

I don't have a clear (far from elegant) proof that, if there exists an algorithm $\mathcal{A}$ that can solve this, then we can solve *some*  hard problem..

The best sketch I can think of is reducing this to a the Okamato's Conference Key Sharing Scheme. However, again, I don't have a clear proof idea here...

Also, I argue, the adversary can submit the following,$(g^a)^t, (g^{ab})^t$,  $t∈_R Z$, however in that case, the adversary has no clue about the value of the exponent

Here, I cranked out the black box optimum to detect any subgroup of $S_{n}$, still exponential but much faster than brute force over all $n!$ permutations.

Your problem is around $O(n  \log  rb)$ with repeated doubling if you have $g$ given to you as a permutation in $S_{n}$.


Any existing Reeds-Shepp implementations? Does anyone know of any open source implementations for finding the optimal path of a Reeds-Shepp car?

I'm trying to implement the formulas myself, but I'm having trouble with one of them. I think it's a typo in their paper; their formula just doesn't spit out the expected result.

The specific formula is found in Section 8.3 in Reeds and Shepp's 1990 paper, found here. I'm trying to find the optimal path from (x = 0, y = 0, theta = 0) to (x = 0, y = 0, theta = -pi), or put differently: the car goes back to the starting position, but pointed in the opposite direction. The correct solution is shown in Figure D of Section 1. The formula in Section 8.3 should give the same turn lengths, but it doesn't. The three turn lengths should all be pi / 3, but working it out by hand gives me completely different values.

Copy of my comment above (I suppose that the question can be accepted/closed):

I think that the question is not research level, however perhaps this can help you:
http://msl.cs.uiuc.edu/~lavalle/cs326a/rs.c (README: http://msl.cs.uiuc.edu/~lavalle/cs326a/README_RS).

You can also take a look at Chapter 13 of the book "Planning algorithms".


Generalized geography on solid grid graphs A post here For which families of graphs is Generalized Geography in $P$? mentioned that generalized geography on solid grid graphs is open. Is the question still open? A quick search on Google shows no results, but I wanted to see if anyone with more familiarity with the area can confirm.

Related to this question, I also wonder if Generalized Geography on grid graphs with holes or thin graphs are also open? What about on bipartite graphs, expander graphs...etc?

Just to complete my comment:

GG remains PSPACE-complete on planar bipartite directed graphs with maximum degree 3 (see
D. Lichtenstein, M. Sipser: GO Is Polynomial-Space Hard. J. ACM 27(2): 393-401 (1980) )

But (vertex) GG on undirected graphs is in P (see this Q&A and this paper) so it is in P also for grid graphs.

For directed solid grid graphs I didn't find any reference, however, I think there is an easy way to simulate a planar bipartite directed graph; the following idea should work:

Both the "diamond" structure (A) and the crossover gadget (C), can be converted into an equivalent (directed) solid grid graph gadget (B) and (D).


Data structure for storing points and finding a predecessor of a point I am looking for a good data structure for storing a set of points
$P\subset \mathbb{N}^n$ that is able to answer the following query:

  Given a point $x=(x_1,\cdots,x_n)$, does there exist a point $p = (p_1,\cdots,p_n)\in P$ such that $p \leq x$, meaning that $p_i\leq x_i$ for all $i\in \{1,\cdots, n\}$?
  If the answer is yes, then the data structure should return one such point.

Ideally, it should be possible to dynamically add points to $P$.

The data structure can 'forget' a point $p \in P$ if there exists another point $p'$ with $p' \leq p$.

The use case that I am thinking about has 'small points'.
Something like $x = (x_i)$ with $\sum_i x_i \leq 30$.
But has a somewhat larger $n$.

ps: I have removed the copy on SO.

What about first computing the skyline (a.k.a. maximal vectors, etc.) of all points, then maintain a data structure for orthogonal range reporting?

The range you are interested in is the orthant with coordinates smaller in all dimensions below your query point.

Actually what you are looking for is a dynamic orthogonal range reporting datastructure. But I add the skyline in case you want to prune the set $P$ first (this answers the part you wrote about 'forgetting' point $p$ if there is some $p'\leq p$).


Are there families of formal languages known to be truly PAC learnable? I specifically mean language families that admit arbitrarily long strings -- not conjunctions over n bits or decision lists or any other "simple" language contained in {0,1}^n.

I am asking about "automata-theoretic" regular languages as opposed to "logic-theoretic" ones: something like the piecewise testable languages, start-height-zero languages, locally testable languages, that sort of thing. The relevant complexity parameter n is the size of the minimal accepting DFA. So, succinctly put: is there an interesting family of n-state DFAs that is known to be efficiently PAC learnable?

There is a recent result on the polynomial pac-learnability of semilinear sets at LICS 2010: Parikh Images of Regular Languages: Complexity and Applications. I guess this is not what you are looking for.

You should also have a look to the paper of Clark and Thollard: PAC-learnability of Probabilistic Deterministic Finite State Automata


Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds? By counting arguments, one can show that there exist polynomials of degree n in 1 variable (i.e., something of the form $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0)$ which have circuit complexity n.  Also, one can show that a polynomial like $x^n$ requires at least $\log_2 n$ multiplications (you need that just to get a high enough degree).  Are there any explicit examples of polynomials in 1 variable with a superlogarithmic lower bound on complexity? (results over any field would be interesting)

Paterson and Stockmeyer show that for most $n$-tuples of rational numbers $(a_1, \dotsc, a_n)$, evaluating $\prod_{i=1}^{n} (x - a_i)$ requires $\Omega(\sqrt{n})$ arithmetic operations, and this is tight.

The following polynomials get within a logarithmic factor of the $\sqrt{n}$ bound, by results of Strassen, Schnorr, and Heintz & Sieveking: $\sum_{i=1}^{n} 2^{2^{i}} x^{i}$, $\sum_{i=1}^{n} e^{2 \pi i / 2^{i}} x^{i}$, $\sum_{i=1}^{n} i^{r} x^{i}$ (for $r$ a rational that is not an integer), etc.  For exact references and for more on this, see pp. 324-325 of von zur Gathen's survey.


Are there subexponential algorithms for PLANAR SAT known? Some NP-hard problems which are exponential on general
graphs are subexponential on planar graphs because the
treewidth is at most $4.9 \sqrt{|V(G)|}$ and they are exponential
in the treewidth.

Basically I am interested if there are subexponential
algorithms for PLANAR SAT which is NP-complete.

Let $\phi$ be a CNF formula on variables $x_i$ and the
$i$-th clause is $c_i$.

The incidence graph p. 5
$G$ of $\phi$ is on vertices $V(G)=\{x_i\} \cup \{c_i\}$
and edges $(x_i,c_i)$ iff $x_i \in c_i$ or $\lnot x_i \in c_i$.

$\phi$ is in PLANAR SAT if the incidence graph is planar.

  Are there subexponential algorithms for PLANAR SAT in terms of $\phi$?

I don't exclude the possibility reduction SAT to PLANAR SAT
to make this possible, though SAT still to be exponential
and $\phi$ is subexponential because of the increase in the size.

Well, you can apply the planar separator theorem together with dynamic programming and get running time $2^{O(\sqrt{n})}$, where $n$ is the number of vertices in the graph. The idea being that you try all possible assignments for the variable vertices on the separator, and all variables mentioned in clauses in the separator (assuming each clause has a constnat number of variables).

If a clause node is large, then you have to be a bit more clever - you have to guess whether to assign it to the left side or right side subproblem. The details for such things tends to be messy and not immediate, so I am not going to give more details. I think the original papers by Lipton and Tarjan solved similar problems using similar ideas, if my memory serves me right.


Areas of research and open problems in functional programming What are the major areas of functional programming that require more research and development? For example, I know a lot of people are asking for dependent types in Haskell, and someone at my uni is doing a PhD in algebraic effects.

The computational implications of homotopy type theory & higher type theory.

Homotopy type theory was invented and developed by a group of computer scientists and mathematicians as a new foundation of mathematics, and as a language to formalize math in, specifically with a view towards algebraic topology (& related fields). However, not much research is done in the computational content of homotopy type theory, i.e. HoTT/HTT as a functional programming language.

Can HoTT be a basis for a practical programming language? What kind of programs do HoTT/HTT enable us to write more easily? What constructs can we add to HoTT/HTT to facilitate programming? There is some research going on in this area, but definitely not enough.

In 2014, Cockx et al. developed a way to do dependent pattern matching without using Axiom K, which is inconsistent with univalence. Later, Sozeau added HoTT support to Equations, the dependent pattern matching plugin for Coq. This is an example of work done on HoTT as a programming language, i.e. to improve developer friendliness.

Also in 2014, Angiuli et al. showed how to do version control using HoTT by developing a Darcs-style "patch theory" in HoTT. This shows that HoTT is a promising tool for some practical programming applications; can we find more appropriate application areas which can benefit from HoTT?


Time complexity of d-dimensional convex hull Consider the convex hull problem in $\Re^d$:

  Input: a list of $n$ points $S$ in $\Re^d$,
  Output: the vertices of the convex hull of $S$.

What is the best lower bound on the time complexity of the
$d$-dimensional convex hull problem?

I don't know any nontrivial lower bounds other than the $\Omega(n\log n)$ algebraic-decision-tree lower bound for two dimensions, which also extends to larger $d$.

As for upper bounds: In 3d, the whole hull can be found in $O(n\log n)$; in four or higher dimensions that doesn't work because the hull complexity grows exponentially with $d$, but nevertheless for any fixed $d$, finding all vertices can be done in time $O(n^2)$ (determining whether a given point is a vertex can be done in linear time by solving a linear program), and the Chan reference below improves this slightly.

See

Ottmann and Scheurer, "Enumerating extreme points in higher dimensions", STACS 1995 and Nordic J. Comput. 2001

Chan, "Output-sensitive results on convex hulls, extreme points, and related problems", DCG 1996

Helbling, "Extreme points in medium and high dimensions", ETH thesis 2010


Fast classical simulation of quantum algorithms Are there examples of cases where the classical simulation of a quantum algorithm for a problem outperforms the best previously known classical algorithm for this problem? "Outperforms" doesn't have to mean different complexity class, it could simply be better scaling.

This question was inspired by the case of efficient classical simulation of a quantum recommendation algorithm.

Your question was inspired by the recent quantum-inspired classical advance in recommendation algorithm. Note that it is not the firs time such a thing happens. In 2015, similar developments happened with approximate MAX3LIN: a quanutm algorithm outperforming all previous known classical algorithms motivated a succesfull search for a better classical algorithm. However, as far as I know, in both these cases, the classical algorithms do not look like classical simulation of a quantum evolution.

I know of one paper describing a classical simulation of a quantum system allowing to outperform previously known algorithms
(Full disclosure: the authors are friends of mine):

  A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices, by
  L. Chakhmakhchyan, N. J. Cerf, R. Garcia-Patron,
  arXiv:1609.02416 /
  Phys. Rev. A 96, 022329

This is based on the connection between the permanent and quantum optics, shown by boson sampling. In opposition to the usual approach, they look at states who are well known to be easy to simulate (thermal states), and use this simulation to perform a Monte-Carlo computation of the permanent of Hermitian positive semidefinite matrices. For some classes of matrices, this algorithm gives a better approximation than the best previously known algorithm (Gurvits algorithm).


Is there a formalization of normalization of impredicative system F? In particular Agda seems not strong enough to prove that.

Is the predicative Calculus of Inductive Constructions universes (Coq without Prop) sufficient?

How about with the impredicative Prop?

Coq without Prop is not strong enough, because it's basically Martin-Löf type theory with universes.
Coq with Prop is strong enough, because you can encode sets of normalizing terms via predicates $S : \mathrm{Term} \to \mathrm{Prop}$, and impredicative universal quantification lets you express arbitrary intersections.


The most applicable areas in Theoretical Computer Science I just wanted to know areas in common to Theoretical Computer Science which have a lot of carrer prospects outside of academia. I specifically wanted to know because I am interested in almost all areas of TCS equally, so why not choose a field for PhD which is more vibrant in terms of carrer choice.
Inspired by this question  MathOverflow

My guesses are
1) Information Theory, all major communication companies and companies which need storage
2) Cryptography (Specifically protocols and construction of new/better codes)
3) Algorithmic Game Theory (Companies like Google are investing a lot in it)
4) Formal Verification(But i think it is a very niche area focussed in Europe)

Anything to do with Machine Learning has a lot of career prospects because you could be employed by either finance or technology companies in general.


Minimal cumulative set sum Consider this problem: Given a list of finite sets, find an ordering $s_1, s_2, s_3, \ldots$ that minimizes $|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$.

Are there known algorithms for this? What is its complexity? I haven't been able to think of an efficient optimal algorithm yet, but it's not obviously in NP-Hard either.

This problem is actually related to a scheduling problem knows as "Precedence constrained scheduling to minimize weighted completion time". The problem is as follows : Given a set of jobs, where each job has a processing time (p) and weight (w) and a precedence graph is defined on the jobs. Goal is to schedule the jobs in a single machine (non-preemptive) such that the precedence constraints are statisfied and the sum of weighted completion time is minimized. The problem is NP-hard and a 2-approximation is known.

Reduction from minimum cumulative sum problem to Precedence constrained scheduling problem :  For each element create a job with p = 1, w = 0. Also for each set create a job with p = 0, w = 1. Create the precedence graph, such that if element $e \in S$, then $e$ must be scheduled before $S$. I think this special case of the scheduling problem is also NP-hard.

See the following links,

1) http://www.win.tue.nl/~gwoegi/papers/precsum.pdf

2) http://web.engr.illinois.edu/~chekuri/papers/dam_sched.ps


Computational complexity of clustering algorithms My wish is to describe the time complexity of several clustering approaches. For example, suppose we have $n$ data points in $m$ dimensional space.

Suppose further that the pairwise dissimilarity matrix $\Delta$ of $n\times n$ dimensions is already computed and that we have already spent $O(m\cdot n^2)$ steps. What is then the time complexity just of

hierarchical clustering (HC) using Ward's linkage
HC using complete linkage
HC using average linkage
HC using single linkage
$k$-medoid approach
$k$-means approach

Is there any benefit if the dissimilarity matrix $\Delta$ is not already computed? As I understand it is necessary for HC and $k$-medoid approach but not for $k$--means?

Thank you for your help!

Single linkage clustering is almost the same as minimum spanning trees in complete graphs, easy O(n^2) time. For O(n^2) time for other agglomerative clustering methods (including I'm pretty sure average and complete linkage) see my paper "Fast hierarchical clustering and other applications of dynamic closest pairs", SODA '98 and JEA '00.


Explanation of definition of normalizing: 9.1.12 in Terese "Term Rewriting Systems"? A strategy for a rewriting system is a sub-rewriting system with the same objects and same normal forms.

Definition (from Terese "Term Rewriting Systems").  Let N be a superset of the normal forms of a rewriting system $\to$.  A strategy S for $\to$ is normalizing if the restriction of S (as a relation) to steps which do not have their sources in N is terminating.

I understand that the authors want a more general notion of normalizing such as the strategy which finds a (weak) head normal form.  However, take N to be be exactly the set of normal forms.  Then the definition should express that the strategy always finds a normal form provided one exists.  I am having trouble bridging the gap here...  It seems that N should have to also include the terms which do not have a normal form.

I think you have misunderstood the definitions:

TERESE (9.1.1):

A strategy $S$ for an ARS $\rightarrow$ is a sub-ARS $\rightarrow_S$ of $\rightarrow$ having the same objects and normal forms.

This means that

If $a\rightarrow_S b$, then $a\rightarrow b$ (sub-ARS condition)
If there exists $b$ such that $a\rightarrow b$, then there exists $b'$ such that $a\rightarrow_S b'$ (same normal forms).

The second condition can be read as: if $a$ is not a normal form, then there is some rewrite step from $a$ which conforms to strategy $S$.

TERESE (9.1.12):

If $A$ is a superset of the set of normal forms for $\rightarrow$, a strategy $S$ is $A$-normalizing if the restriction of $S$ to terms not in $A$ is normalizing.

This means that a strategy is $A$-normalizing if every reduction sequence for $\rightarrow_S$ either

Ends on a normal form
Ends in $A$.

Clearly if $A=NF$ then only case 1. is relevant. However if $A$ is taken to be terms in head-normal form, then case 2. may occur independently of case 1.