A reference for a "more algebraic" approach to pushdown automata and CFLs? In the Sakarovitch's book on automata theory, it is written in the introduction to the section on rationals in the free group that the material presented therein lays "the foundation of a truly mathematical theory of context-free languages". Nevertheless, this is not made explicit, as context-free languages and pushdown automata are beyond the scope of the book.

I am aware of some connections of free groups (and especially of what Sakarovitch calls involutive monoids) to the theory of pushdown automata and context-free languages -- e.g., the Dyck language, the Shamir's theorem, etc. However, I have had a hard time finding a source in which the "truly mathematical theory of context-free languages", mentioned by Sakarovitch, is actually built up.

The closest thing I have found is the Berstel's book on transductions and context-free languages. However, at first sight it seems to me that pushdown automata are treated only marginally in this book, while the theory of rational subsets of a free group is not applied at all. Perhaps the material I am looking for has been intended for Eilenberg's Volume C, but I am not sure about that neither.

So I would like to ask for a pointer to a book, survey, or perhaps a set of papers, from which I could learn something about the Sakarovitch's "truly mathematical theory of context-free languages" and its relations to free groups and their rational subsets. Or perhaps I am looking for something that does not actually exist?

Sakarovitch's PhD thesis from 1976, titled Monoïdes syntactiques et languages algébriques (syntactic monoids and algebraic languages), revolves around this topic.  At the time, this led to the definition of pointed monoids (see, e.g., his MFCS'75 paper).  Around the 80's, the algebraic object of choice to study CFL's shifted to the Hotz group—Sakarovitch even has a paper on that topic in Acta. Inf.  As far as I know, pointed monoids did not get the attention they deserved, although the same ideas can be found in Behle, Krebs, et al.; likewise, some recent approaches, based on more sophisticated tools, especially Stone duality, may provide a sound framework for such studies.

Another modern approach is that of Clark on the syntactic concept lattice, that I'm not familiar with.

As for the actual intentions of the author, one safe way is to ask him directly.


Characterizing closure under expansion/reduction for big-step semantics? Two common ways of formulating operational semantics for programming languages based on lambda-calculus are big-step and small-step semantics.

In a big step semantics, you give a relation $e \Downarrow v$ which directly relates an expression to the value it computes.
In a small-step semantics, you give a transition relation $e \mapsto e'$ which does one step of evaluation, and you get to a value by iterating the transition relation. $e \mapsto^{*} v$.

These two relations are equivalent, in the sense that $e \Downarrow v$ if and only if $e \mapsto^{*} v$.

However, some things are easier to define one way or another. For example, we can say that a set of terms $R \subseteq \mathrm{Exp}$ is closed under expansion if it satisfies the property that:
$$\forall e \in R, e' \in \mathrm{Exp}.\;e' \mapsto e \;\mathrm{implies}\; e' \in R$$

Likewise, a set $R$ is closed under reduction if if satisfies:

$$\forall e \in R, e' \in \mathrm{Exp}.\;e \mapsto e' \;\mathrm{implies}\; e' \in R$$

It's not immediately obvious to me how to formulate expansion or contraction in terms of a big-step semantics. Does anyone know how?

The notion of "next" and "last" - prior to the idea of "expansion" and "reduction" - are  essentially lost when we read a big-step operational semantics as an inductive definition, which is too bad because the way we usually prove things about big-step operational semantics is by reading it as an inductive definition!

You can prove a "full expansion" property (big step preservation) that $e \Downarrow v$ and $e \in R$ imply $v \in R$, and then observe that the proof of this property actually proves a small-step expansion property. This is because computational structure of the proof actually recovers the small-step evaluation process that Prolog/Twelf would use to execute the big-step semantics as a logic program! But for appropriately tricky semantics (especially non-deterministic ones), I've noticed it's frequently the case that you can prove a big-step property when it doesn't hold for the small-step evaluation process that Prolog/Twelf proof proof search would imply.

In my view, the best option - if we want to use big-step specifications but recover the information that was lost when we treated the big-step semantics as inductive definition - to characterize the small-step evaluation process that Prolog/Twelf would use. (This ends up basically or exactly being an abstract machine semantics.) This may not be satisfying depending on what it is you're trying to do, of course. There are a couple of versions of this: see Hannan and Miller or Ager, for instance. (There's also a bit about this in my thesis, some work I did with Ian Zerny, but I'll link to that when there's a thing to link to.) You could also carefully characterize a set of partial derivations of $e_1 \Downarrow v_1, \ldots, e_n \Downarrow v_n \vdash e \Downarrow v$ that corresponded to partial executions, but when I've contemplated this the details have seemed fraught enough that the abstract machine interpretation seems like a safer bet.


Root finding in [0,1] I am interested in the problem of finding a real root of a polynomial equation $f(x)=0$ where
$f(x)=\sum_{i=0}^n a_ix^i$. Is it possible to give a reduction, i.e, to compute a different polynomial $g$ in polytime such that $f$ has a real root iff $g$ has a real root in [0,1]$?

Here is an alternative to the answer by R B ; It is somewhat simpler, but has the disadvantage of an increase in degree.

Simply take $g(x) = x^{2n}f(x)f(-x)f(1/x)f(-1/x)$.


Compendium of the Best Approximation and Hardness Results for NP optimization problems Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result?

Based on the feedback, it seems that it is safe to assume there is not such a resource (see the end of this question for two close options). -- added on Feb 8.

Since there is a huge body of results and problems introduced in the past two decades, existence of a dedicated wiki could be a great help for students and professionals working on subject of approximation algorithms and hardness of approximation.

I have been suggested to start a new wiki. I like the idea, but I need some feedback before starting:
Are you interested in a wiki devoted to the above subject and are you going to contribute something? What is your preferred format for this wiki (see my preferred format in comments)? Should we use a wiki farm or a wiki engine? In the latter case, what is your suggestion for a wiki engine? MediaWiki?

The two closest options that I am aware of, are:
1- "A compendium of NP optimization problems," edited by Pierluigi Crescenzi and Viggo Kann: This compendium seems to be out-of-date. I think the volume of current results cannot be managed by a few people and if we want an up-to-date list, we should have a wiki.
2- Wikipedia: This wiki is for general audience and you cannot have a short page just including problem description, and the best approximation and hardness result.

When you refer to the Crescenzi-Kann compendium, I'm not sure if you're referring to the book or the website.  The book is out of date but the authors try to keep the website continuously updated.  It would seem that the logical starting point is to approach Crescenzi and Kann with your proposal.


Structure of graphs that exclude a perfect matching on four vertices as an induced graph I am interested in understanding the structure of the class of graphs $G$ such that there is no vertex induced subgraph on four vertices that is a perfect matching. Stated differently for any four vertices $a,b,c,d$ in $G$ if $ab$ and $cd$ are edges then the graph should have at least one more edge on the four vertices. Has this class been studied previously? Any references or insights would be appreciated. We understand this class when restricted to bipartite graphs but the general case seems more tricky.

Yes; they are known as $2K_2$-free graphs. Some additional references:

"On Toughness and Hamiltonicity of $2K_2$-Free Graphs"
"The maximum number of edges in $2K_2$-free graphs of bounded degree";
"Two characterisations of minimal triangulations of $2_{K2}$-free graphs"


What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$ under the Kullback-Leibler divergence? If $D_{KL}$ is the Kullback-Leibler divergence, minimizing $D_{KL}(P_{data}||P_{parameters})$ performs maximum likelihood estimation of the parameters. What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$?

(Azoury and Warmuth, 2001) have shown that minimizing the KL-divergence between two exponential family distributions is the same as minimizing the Bregman divergence that corresponds to their cumulant function, i.e.

$KL(P_{F,\theta_1} || P_{F,\theta_2}) = D_F(\theta_1 || \theta_2)$

For $f = \nabla F$, and $F^*$ the Fenchel conjugate of $F$, we get the following nice relationship for Bregman divergences:

$D_F(\theta_1 || \theta_2) = D_{F^*}(f(\theta_2) || f(\theta_1))$

See Lemma 4 in this paper, which also has references to other work that discusses this connection. The above can also be written without the $f$ transfers on $\theta$. So, there is a simple relationship between these two losses, i.e. between minimizing with $\theta_1$ as the first argument or with $\theta_2$ as the first argument.

Also, I feel I should mention that we can generally talk about maximizing likelihood in terms of Bregman divergences and P(data | params), rather than KL-divergences on densities. The above linked paper shows that

$\max_\theta log \ p(data | \theta) = \min_\theta D_F(\theta | data)$

The relationship above where we swapped the two variables of interest in the loss has a correspondence here:

$p(\theta | data) \ p(data) = p(data | \theta) \ p(\theta)$

giving

$log \ p(\theta | data) = log \ p(data | \theta) + log \ p(\theta) - log \ p(data)$

Since we typically do not put a prior on data, we find that maximizing the likelihood of $p(\theta | data)$ (typically called the MAP estimate) corresponds to maximizing likelihood of the data with a prior on the parameters. Correspondingly, maximum likelihood is like the MAP estimate, with a non-informative, uniform prior on $\theta$.

K. S. Azoury and M. K. Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. 2001


What tools do you use to give presentations? I was wondering what tools that people in this field (theoretical computer science) use to create presentations. Since a great deal of computer science is not just writing papers but also giving presentations I thought that this would be an important soft question. This is inspired by the previous question what tools do you use to write papers.  The most common that I have seen are as follows.

Beamer
Microsoft PowerPoint
LaTeX
GraphViz

I was wondering if there are any other tricks that I am missing?

For drawing diagrams, there's tikz in latex, and, if you have a Mac and a bit of cash, Omnigraffle. Both produce high quality diagrams.


How can I use my computational theory and analysis powers for the greater good? Outside of academia, what are the uses of my 'powers'? What can I do other than teaching and publishing papers? Where all can I apply my powers?

For the sake of argument: Please assume I have a PhD in algorithms/TCS and have learnt a great deal of 'stuff' and made have come up with breakthrough bounds on existing algorithms etc., And I also have a strong footing in algorithmic analysis, approximation/randomized algorithms, mathematical programming etc.,

Rationale behind question: Curious about non-academic career options for folks in this area and to possibly motivate some students that it's "just not theory" and there are potential uses in the outside world in essence.

PS: Please don't answer stating there is a lot to learn and you may want to try topic XXX. I am curious from a career/professional development point of view. Operations Research (OR) seems to be the only good fit, IMO. What other options exist?

Please read William Thurston's answer to the question What's a mathematician to do? on mathoverflow. Just to convince you that it is a must-read, let me quote him.

  The product of mathematics is clarity and understanding. Not theorems, by themselves. Is there, for example any real reason that even such famous results as Fermat's Last Theorem, or the Poincaré conjecture, really matter? Their real importance is not in their specific statements, but their role in challenging our understanding, presenting challenges that led to mathematical developments that increased our understanding.

  The world does not suffer from an oversupply of clarity and
  understanding (to put it mildly). How and whether specific mathematics
  might lead to improving the world (whatever that means) is usually
  impossible to tease out, but mathematics collectively is extremely
  important.

I have great sympathy for your question. I did a PhD in logic as applied within computer science and experienced a crisis of utility at the end. It seemed that the strongest skills and deepest knowledge I had, everything I had trained myself in for was completely irrelevant for obtaining a non-academic job. When Matt Welsh , a tenured faculty member at Havard, posted about leaving for Google there was a discussion in which David Patterson from UC Berkeley made the following comment:

  I don't think most systems people are going to industry for the money nor are those going to academia so that they can be called Professor. We're fortunate to have chosen a field were there are great jobs in industry as well as academia.

I felt, on reading this, that doing a PhD in theoretical computer science was the antithesis of his statement. Now, I have been applying for engineering (not research) jobs in the industry and I have discovered that there is place for us out there.

Algorithms are important and relevant in industry. Several problems in industry require good algorithms. You also need solid engineering and infrastructure to make things work. The number of performance bottlenecks to effectively solving real problems is never ending. If you're good at analyzing time and memory consumption of a real system and improving it, there is a lot of work for you.
Clarity in problem solving is an invaluable skill. You have training in getting to the mathematical essence of a problem and ignoring distracting baggage. You may also be able to implement a good solution, or implement a reduction to a form that can be solved efficiently.
Aesthetics has value. This comment is based on limited exposure but after looking at code that has been open sourced by places like Google and facebook, I see that effort has been made to exercise logical hygiene. If you care about mathematical aesthetics then I expect you may have similar discipline when you program and my impression is that such discipline is valued.
Randomization is at its empowering best in a real system. There are so many situations ranging from protocol design to uses of Bloom filters and clever design of caching mechanisms that rely on randomization to scale. To me seeing randomization in action is as fascinating as seeing it in a theorem and even more satisfying.

There are many people with powers that come with a theoretical computer science education who have gone on to have successful industrial careers. I am not concluding that it is this specific knowledge that made them successful, but it definitely didn't impede them.

In the mid 1970s, an undergraduate at Havard university and an assistant professor wrote a paper titled Bounds for sorting by prefix reversal. When Christos Papadimitriou called up the student to inform him the paper was accepted to Discrete Mathematics, William H Gates had already moved to Albuquerque to start a company.
Ashok K. Chandra, coauthor of the 1979 conference and later 1981 journal paper Alternation is in the industry.
The Algorithms and Theory Group in Google has a lot of formidable theoreticians who, as far as I can tell, work on applied problems as well.

This is just a random and tiny list. My aim is not to be comprehensive but to point out that there are theoreticians everywhere. I hope you enjoy coding, because that is an indispensable skill, and I believe it is one of the few common denominators across computer scientists. Of course, you will not use everything you know on a day-to-day basis. But I don't expect this to be the case even if you stay in academia, unless you continue to work on exactly the same set of problems for years on end. If you were thinking otherwise, try Matthew Might's Illustrated Guide to the PhD.


Logic, language, semantics and more I am working on a project that requires me to learn about logic (specially first order and second order).

Looking for a good book or online reference that can help me with questions such as:

A. What is the difference between Logic, Language and Calculus?

B. How to define operators and their semantics?

etc.

As a beginner, it would be great to read a step by step like instructions with easy examples that helps me understand and build on.

Thanks in advance
Karl

Answer to A. Barwise & Etchemendy's Language, Proof, and Logic is a decent introduction to logic. From the perspective of someone coming from a CS background I found it especially accessible and fun. It's very clearly written, has lots of examples, and comes with 3 programs:

  Tarski's World: is a block world where you can verify the truths of sentences or find counterexamples in an intuitive, visual environment
  Fitch: is a Fitch-style proof system that will check your proofs
  Boole: is a truth-table tool

Once you're done with the main course (I-II), in part III they have more fun topics to explore:

  ZFC
  program correctness
  resolution
  Skolemization
  metalogic (e.g. Lowenheim-Skolem, Compactness, Incompleteness)

As I said, B & E is an introductory course, so next you can move to what's called mathematical logic, which is more technical but more precise and will turn out to be more rewarding in the long run. A canonical text here is Enderton's A Mathematical Introduction to Logic, which even has a special chapter dedicated to Second-Order Logic (something you said you're interested in). It's not as interactive as B & E, but it's a classic and it will prepare you for more advanced logic.

Answer to B. How to give the semantics of operators should become clear after studying these texts. But if you're looking for special kinds of semantics, such as Kripke,  topological, neighborhood, measure-theoretic, domain-theoretic, probabilistic, etc., you'll have to do a little digging to find papers that explain how these things are done.

Hope that addresses at least some of your questions.


Solving linear program with 1 quadratic constraint complexity Consider the following linear program,

$$\min y \\
xc_1 \leq c_2 + yz,\\
x = x_1 + \dots + x_n,\\
z \leq x_1 + x_2, \\
z \leq x_2 + x_3, \\
\vdots\\
z \leq x_{n-1} + x_n, \\
x,x_1, \dots, x_n,y,z \geq 0
$$
where $c_1, c_2$ are constants. This is an example of quadratically constrained linear program where I have 1 quadratic constraint. I wish to find out if this problem is NP-Hard or not. The quadratic constraint can be expressed in the form $\vec{y}M\vec{y}^T$ where $M$ for my problem is not positive semidefinite (and thus, non-convex) which is perhaps evidence of hardness

Listing specific questions below:

Can this problem be transformed into a linear program by taking logarithms?
Is there any literature reference or reduction showing that linear programs with non-convex quadratic constraints is an NP-Hard problem?

Edit : Cross posted question at math.stackexchange

Based on posts from or-exchange and some internet reading, the following algorithm works. We adapt the cutting plane method to binary search for variable $y$. For my problem, the upper and lower bounds for all variables are known (but if these are not known, one can find a bound on $y$ by solving the LP by removing the first constraint). Let $l \leq y \leq u$.

Fix $y = (l+u)/2$. This converts the program to a linear program. If the resulting constraints are feasible, update $u(l) = (l+u)/2$. Keep performing the binary search until we reach the optimal solution with an additive $\epsilon_0$. The running time of the algorithm is $O(PTIME)\log\frac{u-l}{\epsilon_0}$.

While this algorithm can find the optimal solution within a small additive constant, I am still not sure about the hardness of the problem for solving exactly. Any comments regarding complexity are welcome!


Is every well-founded simplification order a well-partial order? I'm contemplating the proof of Kruskal's Tree Theorem, as presented in the book "Term Rewriting and All That." They use it to prove that every simplification order is well-founded: first by showing that the homeomorphic embedding is a wpo, and then by showing that every simplification order contains the homeomorphic embedding.

It seems to me that the only properties they use of the homeomorphic embedding in the proof are that it's well-founded, and that each term is > its subterms -- exactly the property that defines a simplification order. Does the same proof work if I instead use an arbitrary simplification order*? Does this mean every simplification order is a well-partial order*?

*One caveat: restricting terms to a finite set of variables, because it's trivial to construct a counterexample with an infinite set of variables.

Every simplification order is indeed a well-partial order because of this simple statement:

  If $R$ is a well-quasi order, and $S$ is a partial order, and $R\subseteq S$, then $S$ is a well-partial order.

Proof: Exercise. Note that this nice property is not true for well-founded orders in general! In this sense, well-quasi orders are much more "stable". It's often the case that a stronger property is better behaved, even if the weaker property is what we want to prove at the end (well-quasi orderdness vs well-foundedness in this case).

Since every simplification order contains the homeomorphic embedding, it is indeed a WPO.

Your more precise statement is correct: we could directly prove that a simplification ordering is a WPO by re-producing the proof for the homeomorphic embedding, but this is not necessary because of the above statement, which shows that it suffices to prove the statement for the "minimal" such ordering.


Computing the union closure Given a family $\mathcal F$ of at most $n$ subsets of $\{ 1, 2, \dots, n \}$.
The union closure $\mathcal F$ is another set family $\mathcal C$ containing every set that can be constructed by taking the union of 1 or more sets in $\mathcal F$.
By $|\mathcal C|$ we denote the number of sets in $\mathcal C$.

What is the fastest way to compute the union closure?

I have showed a equivalence between the union closure and listing all maximal independent sets in a bipartite graph, therefore we know that deciding the size of the union closure is #P-complete.

However there is a way to list all maximal independent sets (or maximal cliques) in $O(|\mathcal C| \cdot nm)$ time for a graph with $n$ nodes and $m$ edges Tsukiyama et al. 1977.
But this is not specialized for bipartite graphs.

We gave an algorithm for bipartite graphs with runtime $|\mathcal C| \cdot \log |\mathcal C| \cdot n^2$ http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf

Our method is based on the observation that any element in $C$ can be made by the union of some other element of $C$ and one of the original sets.
Hence we will whenever we add an element to $C$ try to expand it by one of the $n$ original sets.
For each of these $n \cdot |C|$ sets we need to check if they are still in $C$. We store $C$ as a binary search tree, so each lookup takes $\log |C| \cdot n$ time.

Is it possible to find the union closure $\mathcal C$ in $O(|\mathcal C| \cdot n^2)$ time?
Or even in time $O(|\mathcal C| \cdot n)$?

The complexity of enumerating maximal independent sets in graphs is the same as in bipartite graphs, so bipartiteness does not bring anything new.

You have an algorithm (with exponential space) in $O(|C|\cdot n^2)$, but no polynomial space algorithm that acheives this time complexity is known. The following paper http://www.sciencedirect.com/science/article/pii/S0166218X08004563 is a good survey.


Faster join of treap-like data structures with approximately the same size Given two AVL trees $T_1$ and $T_2$ and a value $t_r$ such that $\forall x \in T_1, \forall y \in T_2, x < t_r < y$, it is easy to construct a new AVL tree containing $t_r$ and the values in $T_1$ and $T_2$ in time $O(1+|h(T_1) - h(T_2)|)$, where $h(T)$ denotes the height of a tree $T$ (as long as trees store their height).

This is also possible for red-black trees, and I assume many other kinds of balanced trees as well.

Is this possible for treaps or treap-like data structures? What if we leave out $t_r$?

The treaps paper in Algorithmica shows how to do this in $O(\min(h(T_1),h(T_2)))$ expected time. If there is a way to perform O(1) expected join on treaps (or treap-like data structures) with roughly the same size (or root priority), I think it might be possible to use a trick of Kaplan & Tarjan of bootstrapping the spines in order to make treaps (or treap-like data structures) with doubly-logarithmic join.

Nope, it's not possible to do this with ordinary Treaps if the priorities are random.

The precise claim I'll make is that to perform such a merge on two equally sized treaps with random priorities requires updating $\Theta(\log n)$ pointers in expectation.

Here's a rough proof sketch:

Consider the number of pointers you have to change in expectation to perform the operation.  It's easier to prove a $\Theta(\log n)$ bound if we don't insert $t_r$ but just merge $T_1$ and $T_2$.
Consider the right spine $S_1$ of $T_1$ and the left spine $S_2$ of $T_2$.
Color the elements of $S_1$ red and those of $S_2$ blue.
Order $S_1 \cup S_2$ by priority.  We have to change a pointer each time the color changes in this sequence.  Since both spines have size $\Theta(\log n)$ with high probability, and
the priorities are random, it's not too hard to see that the # of color changes in the sequence is also $\Theta(\log n)$.  So we need to update $\Theta(\log n)$ pointers for the merge (without adding $t_r$).

Now, adding $t_r$ while doing the merge doesn't really help much.
The number of pointer changes in that case can be lower bounded as follows:
Order $S_1 \cup S_2 \cup \{t_r\}$ by priority.  Delete everything less than $t_r$ in the sequence.  Then # of color changes in the resulting sequence is our lower bound.
Since $t_r$ has random priority, the expected height of the subtree rooted at it in the final treap is $O(1)$, so it only has $O(1)$ nodes of $S_1 \cup S_2$ with lower priority than it in expectation, so we lost only $O(1)$ pointer changes in our lower bound when adding $t_r$.

Now, that said, there's probably a way to get a "treap-like" data structure which allows for constant expected time merges.


Minimization version of matrix p-norms? I considered a minimization version of matrix p-norms, defined for a matrix $A$ by

$$
f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}.
$$

Notice that $f_p(A) = 0$ if and only if $A$'s columns are linearly dependent.
Therefore $f_p(A)$ can be seen as a measure of the linear independence of $A$'s columns:
the larger $f_p(A)$ is, the more independent $A$'s columns are.

When $p=2$, $f_2(A)$ equals the smallest singular value of $A$ and can be computed by doing SVD. When $p\neq 2$, is there any known algorithm than can compute $f_p(A)$? Or if this problem has not been studied before for the $p\neq 2$ case, is it likely to be of interest?

Suppose that $A$ is an $m\times n$ matrix, and let $\mathcal{A}$ be the corresponding linear operator whose matrix (w.r.t. the standard basis) is $A$. Let $W\subseteq \mathbb{R}^m$ be the span of the columns of $A$, or, equivalently, the range of $\cal A$. I am going to treat $\mathcal{A}$ as an operator from $\mathbb{R}^n$ to $W$. As long as $A$ has full column rank, the operator $\mathcal{A}$ is an injection, so it is invertible on its range: let $\mathcal{A}^{-1}:W \to \mathbb{R}^n$ be its inverse.

You are asking about the quantity
$$
\min_{x \neq 0}\frac{\|\mathcal{A}x\|_p}{\|x\|_p} = \min_{y \in W\setminus \{0\}}\frac{\|y\|_p}{\|\mathcal{A}^{-1}y\|_p} = \left(\max_{y \in W\setminus \{0\}}\frac{\|\mathcal{A}^{-1}\|_p}{\|y\|_p}\right)^{-1}
$$

So, your quantity $f_p(A)$ is the operator norm of $\mathcal{A}^{-1}$, taken as an operator from the normed space $(W, \|\cdot\|_p)$ to $(\mathbb{R}^n, \|\cdot\|_p)$. In the special case when $A$ is square, this is just an $\ell_p \to \ell_p$ operator norm. Otherwise it's the norm of an operator from a subspace of $\ell_p$ to $\ell_p$.

If you insist on matrix notation, then you can take $B$ to be a matrix whose rows form an orthonormal basis of $W$. Then $B^\top B$ is the orthogonal projection onto $W$, and, since it acts as identity on the column span of $A$, $B^\top BA = A$. Moreover, if $A$ has full column rank, then $BA$ is an invertible square matrix. So, using the  substitution $z = BAx$, you get

$$
\min_{x \neq 0}\frac{\|\mathcal{A}x\|_p}{\|x\|_p}
= \min_{x \neq 0}\frac{\|B^\top BAx\|_p}{\|x\|_p}
= \min_{z \neq 0}\frac{\|B^\top z\|_p}{\|(BA)^{-1}z\|_p}
= \left(\max_{z \neq 0}\frac{\|(BA)^{-1}z\|_p}{\|B^\top z\|_p} \right)^{-1}
$$
This is the inverse of the $\mathcal{B}_p \to \ell_p$ operator norm of $(BA)^{-1}$, where $\mathcal{B}_p$ is the norm on $\mathbb{R}^n$ defined by $\|z\|_{\mathcal{B}_p} = \|B^\top z\|_p$. (Of course this is the same as above: the subspace $(W, \|\cdot \|_p)$ of $\ell_p$ is isometric to the normed space $(\mathbb{R}^n, \|\cdot\|_{\mathcal{B}_p})$; we've just committed to some basis for it.)


Restriction of Exact Cover by 3-sets Exact cover by 3-sets problem is defined as:

Instance: a set $X = \{ x_1,x_2,...,x_{3n}\}$ and a family $F = \{ ( x_{i_1}, x_{i_2}, x_{i_3}) \}  $ of 3-elements subsets of $X$ (triples);
Question: Is there a subfamily $F'$ of $F$ such that every element in $X$ is contained in exactly one triple of $F'$.

It is known that Exact cover by 3-sets problem is NP-complete even if input is restricted such that each element of $X$ appears exactly in three triples.

  Is still NP-complete if the input is restricted further such that no pair of input triples share more than one element of $X$?

I didn't check if the Bangye's solution is correct/simpler, but a quick transformation from RESTRICTED X3C (the name is the same used by Gonzales)  to SINGLE OVERLAP RESTRICTED X3C (the name is invented) that should work is:

Replace each subset $C_j=\{x_1,x_2,x_3\}$ adding 6 new elements $z_{j,1},z_{j,2},...,z_{j,6}$ and 5 new three elements subsets $L_{j,1}=\{x_1,z_{j,1},z_{j,4}\}$,$L_{j,2}=\{x_2,z_{j,2},z_{j,5}\}$,$L_{j,3}=\{x_3,z_{j,3},z_{j,6}\}$,$L_{j,4}=\{z_{j,1},z_{j,2},z_{j,3}\}$,$L_{j,5} = \{ z_{j,4},z_{j,5},z_{j,6}\}$ .

like in the figure below (blue triples).
Informally, the three elements originally in $C_j$ are grouped and in order to include elements $z_{j,1},...,z_{j,6}$ the exact cover must include the group of triples $L_{j,1},L_{j,2},L_{j,3}$ OR the two triples $L_{j,4},L_{j,5}$, but not both.

At this point no pair of triples share more than one element and each element is included in exactly 3 triples; except elements $z_{j,1},...,z_{j,6}$ which are included only in two triples.

In order to fix this it's enough to add a duplicate of every element element $x_i \rightarrow x'_i, z_i \rightarrow z'_i$, a duplicate of each triple containing $x_i$ or $z_i$ elements using the corresponding duplicated elements (green triples in the figure below) and for each original triple $C_j$ add three new elements $t_{j,1},t_{j,2},t_{j,3}$ and 7 new
dummy subsets with elements:
$D_{j,1} =\{ z_{j,2},z_{j,6},t_{j,1} \}$,
$D_{j,2} =\{ z_{j,3},z_{j,4},t_{j,2} \}$,
$D_{j,3} =\{ z_{j,1},z_{j,5},t_{j,3} \}$,
$D_{j,4} =\{ z_{j,2}',z_{j,6}',t_{j,2} \}$,
$D_{j,5} =\{ z_{j,3}',z_{j,4}',t_{j,3} \}$,
$D_{j,6} =\{ z_{j,1}',z_{j,5}',t_{j,1} \}$,
$D_{j,7} =\{ t_{j,1},t_{j,2},t_{j,3} \}$ (yellow triples in the figure below).

(note that the $z,z'$ elements of dummy triples $D_{j,1}, D_{j,2}, ..., D_{j,6}$ and elements $t$ of dummy triples $D_{j,4},D_{j,5},D_{j,6}$ are "shifted"  to avoid triples that share more than one element)

($\Rightarrow$) Suppose that $\bigcup_{j \in A \subseteq \{1,...,3n\}} C_j$ is an exact cover of the original RESTRICTED X3C instance.
Then by construction:

$$\bigcup_{j \in A } ( L_{j,1} \cup  L_{j,2} \cup  L_{j,3} \cup L'_{j,1} \cup  L'_{j,2} \cup  L'_{j,3} \cup D_{j,7} ) \cup \bigcup_{j \notin A } (L_{j,4} \cup L_{j,5} \cup  L'_{j,4} \cup  L'_{j,5} \cup D_{j,7}) $$

is an exact cover of SINGLE OVERLAP RESTRICTED X3C.

($\Leftarrow$) Suppose that there exists an exact cover of the SINGLE OVERLAP RESTRICTED X3C instance.
Every original element $x_i$ must be included exactly once in the cover, but, as seen above, the only way to include an element $x_i$  is by choosing a group of triples $L_{j,1},L_{j,2},L_{j,3}$ that correspond to an original triple $C_j$ that contains $x_i$.
Furthermore  if $L_p, L_q, p \neq q$ are included in the exact cover we have $L_p \cap L_q = \emptyset$.
So the collection $L_{j,k}$ of subsets in the  SINGLE OVERLAP RESTRICTED X3C exact cover correspond to a valid cover $\bigcup C_j$ of the original RESTRICTED X3C instance.

The reduction can be done in polynomial time, so we can conclude that SINGLE OVERLAP RESTRICTED X3C is NP-complete.

Just note that a SINGLE OVERLAP RESTRICTED X3C instance built using the above reduction can contain two valid and distinct exact covers of the original RESTRICTED X3C problem, but we are sure that if only one exact cover exists, it can be "mirrored" to form a valid exact cover of SINGLE OVERLAP RESTRICTED X3C.

Let me know if you need a more formal proof for a paper.

Update 20/04/2020: I noticed that the previous figure had a small issue in the dummy triples and I fixed it.


Hamiltonian Cycle as an integer linear programming problem I'm trying to do reduce Hamiltonian Cycle to integer linear programming. Here's my idea:

Create variables $e_{ij}$ for every edge $(i,j)$ in the graph. Require each $$e_{ij}\in \{0,1\}$$. Create additional variables $v_i$ for every vertex $i$ in the graph, and define $$v_i = \sum_{\{j:(i,j)\in E\}}e_{ij}$$ (so that $v_i$ counts how many edges are connected to vertex $i$). Specify an integer linear program where the goal is to maximize $\sum_{(i,j)\in E}e_{ij}$ subject to the constraint that $v_i = 2$ for all $i\in V$.

As I see it, this should find a solution (if one exists) of exactly $n$ edges in the graph which form cycles. However, there's no guarantee that these cycles are a single tour of the graph. For example, consider a complete graph of 6 vertices. The above problem might find a "solution" which consists of two cycles each of 3 vertices, instead of finding the correct solution of a single cycle which includes all vertices. In short, the sticking point is requiring that the linear program finds only one cycle. Is there a way to enforce a limit on the number of cycles found via a linear programming constraint? I'm stumped on this.

Thanks!

Describing connectivity in integer programming is not as straightforward as the rest of the reduction, I think.

However, it is quite clean to reduce HAMCYCLE to SAT (e.g. here), and it is very clean to reduce SAT to integer programming. I think you will end up with a system that is not all that complicated. Perhaps it is worth doing so than busting your head over a direct reduction.


What do I need to know about post-doc I am a PhD student in Theoretical Computer Science I am finishing PhD this year and now I want to apply for post-doc positions. I want to know if there exists a source where can I read about how to apply for post-doc.

Here is the partial list of questions I am interested in:

1) What scholarships exists in my area?

2) What Universities have open post-doc positions? Beside Princeton/IAS I did not found organized information in other universities.

3) How can I chose the right people to ask recommendation letters from?

4) Assume that someone wants that I will come to his university to do a post-doc and this will require some effort to hire me(need to find money ...), but my first preference is other university which I still do not know if will want to hire me. What should I do in this case.

5) Any other advises and suggestions about what I should know about application for post-doc.

1) What scholarships exists in my area?

At this phase of your education, you should be talking to your advisers on a regular basis, or at least reading all of the material they send out. Usually advisers will send out all kinds of scholarship information as they receive them. So, your best bet is to talk to your adviser. You can also try scholarship search engines, many scholarships are not location-dependent.

  2) What Universities have open post-doc positions? Beside Princeton/IAS I did not found organized information in other universities.

This one is tricky and I recommend talking to your adviser here also. Many opportunities aren't advertised openly - it isn't always what you know, but who you know. Also consider that there may be opportunities and projects in different departments other than CS that need services a CS student can provide.

If you've already looked but couldn't find anything, then contact the advisers at those schools.

  3) How can I chose the right people to ask recommendation letters from?

Think about all of the people in the institution you have worked with. Advisers, teachers, mentors, ... Now, you want to choose the best people based on :

Choose those who knew you and worked close to you
How high ranked are they, how much relation do they have to your desired postdoc position?
How well do they think of you? Did you do good work for them? Did you get high grades in the class? Were they "wow!"ed by your performance?

  4) Assume that someone wants that I will come to his university to do a post-doc and this will require some effort to hire me(need to find money ...), but my first preference is other university which I still do not know if will want to hire me. What should I do in this case.

It's up to you. I think it's better to be open to everyone that you haven't decided yet so they are more understanding if you take a different route. When an offer does come up, just like a job, I think you can wait about a week before deciding. After that, you are stretching your luck.

Just remember that you don't want to burn any bridges here, be patient and open, and a solid offer has much more weight than a "maybe".


Is it possible to represent a regular expression with bounded captures using a DFA and O(1) additional processing? It's well known that a regular expression can be converted to a non-deterministic finite state automaton, which can in turn be converted in to a deterministic finite state automaton. These DFAs can then be compiled directly into code as in e.g. re2c.

However, most libraries for regular expressions allow for captures - where the portion of the string representing a certain portion of the regex is saved for further analysis. With captures things get more complex - a state node passed in an early match may not be able to commit to a capture, as whether the capture is correct or not depends on later nodes.

Although a turing machine can obviously handle such expressions by treating the regex as a NDFA, and maintaining a stack of non-deterministic state transitions (ie backtracking), it's desirable to avoid the unbounded additional memory/CPU usage and allocations this entails.

So: Is it possible to compile a regular expression with a bounded number of captures $(< k)$ into a DFA, allowing $O(1)$ additional processing at each node, and $O(k)$ additional storage?
If not, is there a proof to this effect?

I have no direct answer, but some additional remarks regarding on the topicality of my paper from this year's STACS which Raphael  mentioned in his answer. (Due to space reasons, I opted for a new answer, instead of a comment.)

As far as I understand the question, the classes of regular expressions with $\leq k$ captures corresponded to the classes RegEx(k) of extended regular expressions with at most $k$ variables in my paper. Among the results in the paper, the ones that are probably most relevant to the question are that, even with one variable (the class RegEx(1)),

1) there is no effective way of converting expressions from RegEx(1) to "proper" regular expressions, even if the problem is restricted to those expressions that describe regular languages,

2) even if one is able to convert these expressions with one variable to proper regular expressions (or any other description mechanism for the class of regular languages), the resulting blowup in size is not bounded by any computable function,

3) given an expression $\alpha\in RegEx(1)$, universality (the question whether $L(\alpha)=\Sigma^*$) is not decidable.

This does not directly answer the question, but imposes some limits on possible conversion procedures. For example, if the universality problem for the class of resulting DFAs with extra storage is decidable, such a conversion procedure cannot exist. (On the other hand, although the automata model that is described in the question appears to be underspecified regarding the storage and storage operations, I am under the impression that this problem should be undecidable for the resulting class of automata.)

Among the few papers that deal with regular expressions with variables/backreferences/captures, I know of only two other works that consider something in the direction of limiting the number of variables: Aho's chapter on string matching in the Handbook of TCS (Vol. A), which contains a sketch of a proof that extended regular expressions with at most $k$ backreferences can be matched in time $O(n^{2k})$, and the paper by Reidenbach and Schmid from CIAA 2010, which gives a polynomial time matching algorithm for a larger class of extended regular expressions.


Uses of XORification XORification is the technique to make a Boolean function or formula harder by replacing every variable $x$ by the XOR of $k\geq 2$ distinct variables $x_1 \oplus \ldots \oplus x_k$.

I am aware of uses of this technique in proof complexity, mainly to obtain space lower bounds for resolution-based proof systems, e.g., in the papers:

Eli Ben-Sasson. Size space tradeoffs for resolution. STOC 2002, 457-464.
Eli Ben-Sasson and Jakob Nordström. Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. ICS 2011, 401-416.

Are there other uses of this technique in other areas?

Here's an somewhat relevant example we are currently covering in my class.

The "storage access function" is defined on $2^k+k$ bits as:

$SA(x_1,...,x_{2^k}, a_1,...,a_k) = x_{bin(a_1 \cdots a_k)}$

where $bin(a_1 \cdots a_k)$ is the unique integer in $\{1,\ldots,2^k\}$ corresponding to the string $a_1 \cdots a_k$.

$SA$ has formulas of size about $O(k \cdot 2^k)$ over AND/OR/NOT: have $2^k$ groups of all possible $k$-ANDs over the $a_i$ variables, so that exactly one group outputs $1$ on every input. Then AND each bit $x_i$ with the output of the corresponding group, then OR all of these outputs.

However, the following "SA of XOR" function, on $2^{k+1}$ inputs, requires about $2^{3k}$-size formulas over AND/OR/NOT:

$SA(x_1,...,x_{2^k}, \bigoplus_{j=1}^{2^k/k} a_{1,j},..., \bigoplus_{j=1}^{2^k/k} a_{k,j}) = x_{bin(a_1 \cdots a_k)}$.

This is often called "Andreev's function" in the literature. Hastad proved (improving a component of Andreev's argument) that cubic-size formulas are essentially necessary. (It is not hard to find nearly cubic-size formulas for it, too.)


What is known about this TSP variant? This question was previously posted to Computer Science Stack Exchange here.

Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've developed a fleet of disposable delivery drones, each with an effective range of 50 kilometers. With this innovation, instead of travelling to each city to deliver your goods, you only need to fly your helicopter within 50km and let the drones finish the job.

Problem: How should your fly your helicopter to minimize travel distance?

More precisely, given a real number $R>0$ and $N$ distinct points $\{p_1, p_2, \ldots, p_N\}$ in the Euclidean plane, which path intersecting a closed disk of radius $R$ about each point minimizes total arc length? The path need not be closed and may intersect the disks in any order.

Clearly this problem reduces to TSP as $R \to 0$, so I don't expect to find an efficient exact algorithm. I would be satisfied to know what this problem is called in the literature and if efficient approximation algorithms are known.

This is a special case of the Travelling Salesman with Neighborhoods (TSPN) problem. In the general version, the neighborhoods need not all be the same.

A paper by Dumitrescu and Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, addresses your question. They give a constant factor approximation algorithm for a slightly more general problem (case 1), and a PTAS when the neighborhoods are disjoint balls of the same size (case 2).

As a side comment, I think Mitchell has done a lot of work on geometric TSP variants, so you might want to look at his other papers.


Is there a version of MIP=NEXP with relatively efficient provers? (My question is not a duplicate of this question.)

Fix a good coding of non-deterministic random-access machines.

For non-negative integers $m$ that code such a machine, let

$\operatorname{states}(m)$ denote the number of internal states in the coded machine.

("hc" stands for "hard-coded".)

Choose some polynomial function $hcpoly$, and let $L$ be the language

$\{\langle m\hspace{.02 in},\hspace{-0.025 in}t,\hspace{-0.02 in}s\hspace{-0.02 in}\rangle \;\; : \;\; m$ codes such a machine and $\:t\leq 2^{hcpoly(\operatorname{states}(m))}\:$ and

there is a sequence of non-deterministic choices which will make that machine

accept the empty string in at most $t$ time without using more than $s$ space$\}\;$.

  Is there a MIP protocol for $L\hspace{.02 in}$ in which the provers use not

  much more than $t$ time and/or not much more than $s$ space?

That could just mean $\:poly(\hspace{.02 in}\operatorname{length}(\langle m\hspace{.02 in},\hspace{-0.025 in}t,\hspace{-0.02 in}s\hspace{-0.02 in}\rangle))\:$ time and space, although

ideally it would be $\:poly(\operatorname{states}(m))\hspace{-0.03 in}\cdot \hspace{-0.03 in}t\:$ time and $\:poly(\operatorname{states}(m))\hspace{-0.03 in}+\hspace{-0.03 in}s\:$ space.

Yes.    This paper constructs "a one-round succinct MIP of knowledge, where each prover runs in time $t\cdot \operatorname{polylog}(t)$ and space $s\cdot \operatorname{polylog}(t)$ and the verifier runs in time"  $\operatorname{length}(m) \cdot \operatorname{polylog}(t)$ .


Characterization of union of DCFLs We know that DCFL is not closed under the union operation and
CFL is closed under union and contains the union of DCFLs.

Is there a characterization of finite unions of DCFLs?

One direction is clear:  the union of any finite number of DCFL's is a CFL.

However, a precise characterization of the union-closure of DCFL's was not obvious to me at all (and I teach this stuff and wrote a book on it), so I went searching with a google search.  I found this paper by my colleagues  Martin Kutrib and Andreas Malcher:   Context-Dependent Nondeterminism for Pushdown Automata, O.H. Ibarra and Z. Dang (Eds.): DLT 2006, LNCS 4036, pp. 133–144, 2006.  Theorem 1 gives a characterization of this class.


Are optimal evaluators actually optimal? The following term (using bruijn-indexes):

BADTERM = λ((0 λλλλ((((3 λλ(((0 3) 4) (1 λλ0))) λλ(((0 4) 3) (1 0))) λ1) λλ1)) λλλ(2 (2 (2 (2 (2 (2 (2 (2 0)))))))))

When applied to a church number N evaluates to normal form quickly in several existing evaluators, including naive ones. Yet, if you encode that term to interaction nets and evaluate it using Lamping's Abstract Algorithm, it takes an exponential numbers of beta-reductions in relation to N. On Optlam, specifically:

N   interactions(betas)     (BADTERM N)
1   129(72)                 λλλ(1 (2 (2 (2 (2 (2 (2 (2 0))))))))
2   437(205)                λλλ(2 (1 (2 (2 (2 (2 (2 (2 0))))))))
3   976(510)                λλλ(1 (1 (2 (2 (2 (2 (2 (2 0))))))))
4   1836(1080)              λλλ(2 (2 (1 (2 (2 (2 (2 (2 0))))))))
5   3448(2241)              λλλ(1 (2 (1 (2 (2 (2 (2 (2 0))))))))
6   6355(4537)              λλλ(2 (1 (1 (2 (2 (2 (2 (2 0))))))))
7   11888(9181)             λλλ(1 (1 (1 (2 (2 (2 (2 (2 0))))))))
8   22590(18388)            λλλ(2 (2 (2 (1 (2 (2 (2 (2 0))))))))
9   43833(36830)            λλλ(1 (2 (2 (1 (2 (2 (2 (2 0))))))))
10  85799(73666)            λλλ(2 (1 (2 (1 (2 (2 (2 (2 0))))))))
11  169287(147420)          λλλ(1 (1 (2 (1 (2 (2 (2 (2 0))))))))
12  335692(294885)          λλλ(2 (2 (1 (1 (2 (2 (2 (2 0))))))))
13  668091(589821)          λλλ(1 (2 (1 (1 (2 (2 (2 (2 0))))))))
14  1332241(1179619)        λλλ(2 (1 (1 (1 (2 (2 (2 (2 0))))))))
15  2659977(2359329)        λλλ(1 (1 (1 (1 (2 (2 (2 (2 0))))))))

On similar evaluators such as BOHM, it takes much less beta steps, but more interactions. If optimal evaluators are optimal, how can they evaluate terms asymptotically slower than existing evaluators?

This link has an explanation about the origin of the term, as well as an implementation of the same function that behaves the opposite, almost bizarrely so: it should run in exponential time - it does run in exponential time in most evaluators - yet, optimal evaluators normalize it in linear time!

Efficiency of optlam

I have not studied the details of BADTERM nor of the implementation of optlam evaluator, but I find quite strange that optlam performs a number of ß-interactions drastically different than another optimal evaluator like BOHM. Such a number must be, by definition, basically the same on a given term. Are you sure of the correctness of optlam's core?

Efficiency of optimal evaluators

Recall that the notion of optimality of these evaluators is more properly known as Lévy-optimality, and it is not the naive one, since a strategy of reduction performing the minimum number of ß-steps is not computable. What is minimised, then, is the number of parallel ß-reduction steps performed on a whole family of redex, that is roughly the set obtained by the symmetric and transitive closure of the relation which binds two redexes when one is copied from the other. It should in general not surprise to see discrepancies between the number of ß-steps and the rest of duplication-steps, since we know that most of the normalisation load could be transferred from the former to the latter, as shown by Asperti, Coppola and Martini [1].

It should not surprise us either to see that total number of interactions needed to normalise an term with an optimal evaluator is that lower than with an ordinary one, since previous empirical observation already showed notable performance improvements. In spite of this, such a huge complexity jump, from exponential to linear time, is perhaps the very first of its kind being being discovered, though. (I will check this.)

On the other hand, the theoretical results about the efficiency of optimal reduction (which is your big question), are still few and not yet general, since they are limited to EAL-typed proof-nets (which is basically the same restriction of optmal evaluator, if I correctly understand), but all are mildly positive, since in the worst case the complexity of sharing reduction is bounded by the ordinary one by a constant factor [2,3].

References

A. Asperti, P. Coppola, and S. Martini, (Optimal) Duplication is not elementary recursive, Information and Computation, vol. 193, 2004.
P. Baillot, P. Coppola, and U. Dal Lago, Light logics and optimal reduction: Completeness and complexity, Information and Computation, vol. 209, no. 2, pp. 118–142, 2011.
S. Guerrini, T. Leventis, and M. Solieri, Deep into optimality – complexity and correctness of sharing implementation of bounded logics, DICE 2012, Tallin, Estonia, 2012.


Impact of Grothendieck's program on TCS Grothendieck has passed away. He had massive impact on 20th century mathematics continuing into the 21st century. This question is asked somewhat in the style/spirit, for example, of Alan Turing's Contributions to Computer Science.

  What are Grothendieck's major influences on theoretical computer science?

Grothendieck's inequality, from his days in functional analysis, was initially proved to relate fundamental norms on tensor product spaces. Grothendieck called the inequality "the fundamental theorem of the metric theory of tensor product spaces", and published it in a now famous paper in 1958, in French, in a limited circulation Brazilian journal. The paper was largely ignored for 15 years, until it was rediscovered by Lindenstrauss and Pelczynski (after Grothendieck had left functional analysis). They gave many reformulations of the paper's main results, related it to research on absolutely summing operators and factorization norms, and observed that Grothendieck had solved "open" problems which had been raised after the paper was published. Pisier gives a very detailed account of the inequality, its variants, and its tremendous influence on functional analysis in his survey.

Grothendieck's inequality is very naturally expressed in the language of combinatorial optimization and approximation algorithms. It says that the non-convex, NP-hard optimization problem
$$
\max\{x^TAy: x \in \{-1, 1\}^m, y \in \{-1, 1\}^n\}
$$
is approximated up to a fixed constant by its semidefinite relaxation
$$
\max\{\sum_{i,j}{a_{ij}\langle u_i, v_j\rangle}: u_1, \ldots, u_m, v_1, \ldots, v_n \in \mathbb{S}^{n+m-1}\},
$$
where $\mathbb{S}^{n+m-1}$ is the unit sphere in $\mathbb{R}^{n+m}$. Proofs of the inequality give "rounding algorithms", and in fact the Goemans-Williamson random hyperplane rounding does the job (but gives a suboptimal constant). However, Grothendieck's inequality is interesting because the analysis of the rounding algorithm has to be "global", i.e. look at all terms of the objective function together.

Having said this, it should not be surprising that Grothendiecks's inequality has found a second (third? fourth?) life in computer science. Khot and Naor survey its multiple applications and connections to combinatorial optimization.

The story does not end there. The inequality is related to Bell inequality violations in quantum mechanics (see Pisier's paper), has been used by Linial and Shraibman in work on communication complexity, and even turned out useful in work on private data analysis (shameless plug).


What are good references to understanding the proof of the PCP theorem? I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1))$).

What are good papers/books to read for that?

Both Goldreich's complexity textbook and Arora and Barak's complexity textbook have chapters devoted to explaining the proof of the PCP theorem (with pictures!).

Also, Dinur's paper is worthwhile to read, if you haven't tried to tackle it yet. It's at least more approachable (in my opinion) than the original proof, and you can get a good intuition for how the proof works by skimming just the first 12 pages (and delve into the technical proofs contained in the latter chunk of the paper later, if you prefer).


For a given binary-search tree obtain an isomorphic splay tree I will assume that the reader is familiar with some undergraduate algorithms and data structures. To people who are not familiar with splay trees I recommend to read through this link : https://en.wikipedia.org/wiki/Splay_tree

An interesting problem is :

  Given a binary search tree $T$ with $n$ nodes. Find the sequence $S$ of
  operations (find, insert, delete) to obtain a Splay tree
  $T_{Splay}$, such that $T_{Splay} = T$.

For example the splay tree equal to this one

could be generated by the following sequence:

Insert(3), Insert(2), Insert(1), Find(2)

My questions are:

Is it possible to obtain $T_{Splay}$ for every binary search tree $T$?
If the answer for the above question is positive, find an algorithm to solve this problem. What about its complexity?
If the answer for the above question is positive, how long need to be the sequence $S$?

Unfortunately I can't find any solutions to these problems which means that either it could be hard or simply uninteresting for most of us. I found also a few links about similar problems but none of them could be applied to this case. The full list of links below:

https://stackoverflow.com/questions/14564437/a-sequence-that-forms-the-same-avl-and-splay-trees
https://stackoverflow.com/questions/22413727/determining-if-a-binary-search-tree-can-be-constructed-by-a-sequence-of-splay-tr

Thanks for any answers,
Bartosz Bednarczyk

It can be done with a linear number of operations.

Suppose you start with an arbitrary given tree $T_0$ over keys $[n]$ and want to reach an arbitrary given $T$ over keys $[n]$ using splay operations. (In case we have to start with the empty tree, just insert $[n]$ in any order.)

A result of Cleary [*1] (see also Lucas [*2]) shows that you can get from $T_0$ to $T$ using $O(n)$ normal rotations, even if you restrict yourself to rotations at the root and at the right child of the root.

Let's try to simulate these restricted rotations with splay operations. Rotation at the root is easy, just splay the corresponding child.

What about rotations at the right child? There are two cases (see figure).

The first case (left to right) is easy: splay y, then splay x.

The second case (right to left) is more tricky:

Suppose z has a right child t. Then we can:

splay t, then splay z, then splay x, obtaining the required rotation.

We had to assume that t exists. We can make sure of this, by inserting an $\infty$ key element in the beginning and making sure that it will always remain a leaf. We can make sure it is a leaf in the beginning, for instance by splaying $\infty$, and then 1,2,3,...,n. Afterwards, t $=\infty$ is never splayed, except if the above situation arises where it is the right child of z, and then we can see that it stays a leaf after the transformation.

In the end, we just need to clip away this leaf and get the target tree $T$. This last step is a bit of cheating, since a proper splay deletion would clip away the leaf, then splay its parent.

We can get around this cheating by deleting $\infty$ earlier, i.e. the last time when the above right-to-left transformation involving $\infty$ happens. Then, after the splay z and before the splay x steps, we can do a proper splay-delete t (t $= \infty$) operation, and since t is the child of the root at that time, no unintended side-effect happens.

A (perhaps simpler) alternative formulation is that, if in the above right-to-left transformation z has no right child, then we do the sequence:
insert(n+1), splay(z), delete(n+1), splay(x). (assuming that insert works by inserting as a leaf and then splaying an element).

[*1] S. Cleary, Restricted rotation distance between binary trees,
Inform. Process. Lett. 84 (2002) 333–338

[*2] J. Lucas, A direct algorithm for restricted rotation distance,
Inform. Process. Lett. 90 (2004) 129–134


Computing integer points on the circumference of a given circle Is there a known algorithm that efficiently outputs the set of lattice points on the circumference of a given circle? The input circle is specified using its center $(a,b)$ and its radius $r$. The inputs $a, b, $ and $r$ are not necessarily integers.

If $a=b=0$ and $r=pq$ where $p$ and $q$ are primes congruent to 1 mod 4, then from the $O(1)$ integer points on the circle one could determine the factorization of $r$. So the problem is not going to be easier than factorization.


Consequences of $NP\subseteq P/poly$ to $BQP$ A post here Consequences of $BQP \subseteq P/poly$? queried on Consequences of $BQP \subseteq P/poly$.

It is not known if $NP\subseteq BQP$.

In general, what are the consequences of $NP\subseteq P/poly$?

How does $NP\subseteq P/poly$ affect $BQP$?

I'm not aware of any direct consequence of $NP\subset P/poly$ for $BQP$.  Of course it might lessen the interest in quantum computing, since it would mean that we could do something far more impressive with just good old classical nonuniformity than we could with quantum mechanics.  And it would imply $NP\subset BQP/poly$. :-)  OK, it would also weaken the arguments that BosonSampling, and other quantum sampling tasks of that kind, are classically hard.  For those arguments involve showing that if the sampling tasks can be done in classical polynomial time, then $PH$ collapses to the second or third level (along with several other strange things, like $P^{\#P}=BPP^{NP}$).  But if $NP\subset P/poly$, then $PH$ collapses anyway.


Research about geometry negotiation in widget layout It's very common to view GUI layout as an optimization problem.

I've uncovered a lot of research around linear constraint systems, but a lot of real world layouts can not be represented linearly. For example, a simple "Wrapping" layout introduces discontinuities at line or column breaks.

Some real world systems compute layout recursively. They alternate between measuring and positioning widgets, then iterate until a fixed point. I've seen this process called "geometry negotiation" in the documentation for several of these widget libraries. However, I can not find any formal treatment of this approach.

Outside of linear constraints, are there any other formalisms targeted at these sorts of layout optimization systems?

I would suggest looking at these survey papers and tracking down the citations in the bibliography, and digging up subsequent papers which cited these.

Walter Hower, and  Winfried Graf. Research in constraint-based layout, visualization, CAD, and related topics : a bibliographical survey, 1995.
Simon Lok and Steven Feiner, A survey of automated layout techniques for information presentations, 2001.

If you're more interested in the engineering aspects, you should look at Brad Myers' work (from the late 80s/early 90s) on the Garnet and Amulet toolkits. They have a TOPLAS paper, Lessons learned about one-way, dataflow constraints in the Garnet and Amulet graphical toolkits, which summarizes what they learned.


Reductions in Descriptive Complexity Reducing one problem to another are well known in various settings, such as many-one, randomized, truth-table, logspace or a whole slew of other reductions. Descriptive complexity can alternately characterize problems in $\mathsf{NP}$ using Logics, like e.g. extensions of first-order logic and others (see here for an introduction). So, it is natural to ask how to approach reductions in this context. Are there reductions, based on first-order, or second-order logics used in Descriptive Complexity, or even completeness under these reductions for descriptive complexity?

Standard notions of reduction used in Descriptive Complexity are first-order reduction and the weaker first-order projection. Definitions of both these notions are found in Immerman's book on Descriptive Complexity.


Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$? This is intended as a follow up question to Robin Kothari's previous post on polynomial time hardness results.

Specifically, I'm interested in seeing some hardness proofs for problems that are believed to have roughly $\Omega(n^3)$ lower bounds, and I say roughly to allow for slightly subcubic improvements by playing with the word size (such as that for 3SUM by Barab et al. [via Springer]). I would be happy to keep problems in the decision tree model if it simplifies the responses.

From Robin's post, I learned about Jeff Erikson's paper which gives a $\Omega(n^3)$ lower bound for 5SUM (more accurately, he shows that $k$-SUM runs in $\Omega (n^{\lceil k/2 \rceil})$ time in general).

Do papers or other references exist using such reductions to conjecture cubic lower bounds for problems in computational geometry or graph theory?

I think the paper "Subcubic Equivalences Between Path, Matrix, and Triangle
Problems" by V. Vassilevska Williams and R. Williams is what you're looking for. Its abstract contains the list of the following problems on graphs:

The all-pairs shortest paths problem on weighted digraphs (APSP).
Detecting if a weighted graph has a triangle of negative total edge weight.
Listing up to $n^{2.99}$ negative triangles in an edge-weighted graph.
The replacement paths problem on weighted digraphs.
Finding the second shortest simple path between two nodes in a weighted digraph.

According to the abstract the paper is about the following:

  We define a notion of subcubic reducibility, and show that many important problems on graphs and matrices solvable
  in $O(n^3)$ time are equivalent under subcubic reductions.


Isomorphism preserving transformation CNF to Graph? In short we are interested in isomorphism preserving
transformation CNF to Graph.
Let $\phi_1,\phi_2$ be CNF formulas.
Define $\phi_1$ and $\phi_2$ to be isomorphic $\phi_1 \cong \phi_2$
if there exist permutation $\pi'$ of the clauses of $\phi_2$ and
permutation $\pi$ of the variables of $\phi_2$ such that
$\phi_1(x_i)=\pi'(\phi_2(\pi(x_i)))$.
XXX this isomorphism definition might be non-standard, please
fix it.

Main question:  Is there transformation $\Gamma(\phi)$ CNF to
polynomially sized Graph
such that $\phi_1 \cong \phi_2 \iff \Gamma(\phi_1) \cong \Gamma(\phi_2)$

Several papers about satisfiability define the "constraint graph"
of CNF, but it doesn't appear to preserve isomorphism.
Solution might exist when transforming CNF satisfiability as a
problem on a graph.
Here is attempt at solution.
Given CNF formula with $n$ variables $v_i$ and $m$ clauses
$c_i$, construct graph $\Gamma(\phi)$ with vertices $c_i \cup v_i \cup \lnot v_i$.
Add edges $(v_i,\lnot v_i)$, $(v,c_i)$ for $v \in c_i$,
$(\lnot v,c_i)$ for $\lnot v \in c_i$.
Set the weights of $c_i$ have prohibitively large $2n$ and the weights of
$v,\lnot v$  to $1$.
We believe Minimum Weighted Independent Dominating Sets (MWIDS) of weight $n$
in $\Gamma(\phi)$ are in bijection with the satisfying assignment of $\phi$.
If $v$ dominates $c_j$, the clause $c_j$ is satisfied. MWIDS dominates
all clauses, so they are satisfied.
In a satisfying assignment of $\phi$ all clauses are satisfied
and the solution is MWIDS.
We saw very similar unweighted reduction of SAT to MIDS in a paper.

Q2 Does the above construction preserves isomorphism?

Q3 If the construction is correct, but the definition of isomorphism
is incorrect, what does $\Gamma(\phi_1) \cong \Gamma(\phi_2)$
implies about $\phi_1$ and $\phi_2$?

I think there's a straightforward transformation to graphs with colored edges, which can in turn be transformed into ordinary graphs.
Given a CNF $\phi$ with clauses $c_i$ and variables $v_i$, construct a graph with vertices $c_i,v_i,\neg v_i$.  Add black edges between each clause $c_i$ and each literal in it.  Add a red edge between each variable $v_i$ and its complement $\neg v_i$.  This transformation maps isomorphic CNFs to isomorphic graphs, and vice versa.
(Proof: Given $\pi,\pi'$, you obtain a mapping on vertices: map clause $c_i$ to $\pi'(c_i)$ and map variable $v_i$ to $\pi(v_i)$ and $\neg v_i$ to $\neg \pi(v_i)$.  You can verify that this respects the edges.  Likewise, you can convert any mapping between the two graphs into $\pi,\pi'$.)
There are standard reductions that allow you to reduce colored graph isomorphism to graph isomorphism.  You basically use a gadget to represent the colors (you attach each red edge to a copy of a gadget that is unique to the color red, and attach each black edge to a copy of a gadget that is unique to the color black).  If you compose that with the construction I outline above, then you should get the desired reduction from CNFs to graphs.


If NP in BPP then NP equals RP I am looking for a reference to the fact that if NP is included in BPP then NP is equal to RP. See for instance these links:

https://cs.stackexchange.com/q/80509
http://www.inf.ed.ac.uk/teaching/courses/cmc/cw3_solns.pdf
https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf

I know that this is folklore, but I'd still like to cite something that is published and where this would be properly proved.

An actual factual reference is

K. Ko. Some observations on the probabilistic algorithms and NP-hard problems. Information Processing Letters, 14(1):39–43, 1982.

(When I first saw this result --- I don't remember where it was now --- it was called "Ko's Theorem". Googling suggests that another theorem has that name as well...)


"Divide and conquer" data stream algorithms What useful algorithms do there exist that work on huge data streams and also their results are fairly small and one can compute the result for a mixture of two streams by somehow merging their results?

I can name a few:

The obvious things like sum, min, max, count, top-K etc.
Approximate so called "sketch-based" stream algorithms for histograms, counting distinct items or computing quantiles

What others are there?

(I'm interested because I'm writing a hobby project for monitoring distributed systems whose usefulness is directly determined by the usefulness of such algorithms)

Guha et al. '03 give an approximation algorithm for k-median clustering in the streaming model.  Their algorithm divides the data into disjoint pieces, finds O(k) centers for each disjoint piece, and then combines the results to get the k centers.  This seems to be the type of algorithm you're looking for.


Proof techniques for showing that dependent type checking is decidable I'm in a situation where I need to show that typechecking is decidable for a dependently-typed calculus I'm working on. So far, I've been able to prove that the system is strongly normalizing, and thus that definitional equality is decidable.

In many references I read, the decidability of typechecking is listed as a corollary of strong normalization, and I believe it in those cases, but I'm wondering how one goes about actually showing this.

In particular, I'm stuck on the following:

Just because well typed terms are strongly normalizing, doesn't mean that the algorithm won't loop forever on non-well typed inputs
Since logical relations are usually used to show strong normalization, there's not a convenient decreasing metric as we progress typechecking terms. So even if my type rules are syntax directed, there's no guarantee that applying the rules will eventually terminate.

I'm wondering, does anyone have a good reference to a proof of decidability of typechecking for a dependently typed language? If it's a small core calculus, that's fine. Anything that discusses proof techniques for showing decidability would be great.

There is indeed a subtlety here, though things work out nicely in the case of type checking. I'll write down the issue here, since it seems to come up in many related threads, and try to explain why things work out all right when type-checking in a "standard" dependent type theory (I'll be deliberately vague, since these issues tend to crop up regardless):
Fact 1: If ${\cal D}$ is a derivation of $\Gamma\vdash t:A$, then there is a derivation ${\cal D}'$ of $\Gamma \vdash A:s$ for some kind $s$, and for every subterm $u\leq t$, there is some type $B$, a context $\Delta$ and a derivation $\cal D''$ of $\Delta\vdash u:B$.
This nice fact is somewhat hard to prove, and offset by a pretty nasty counter-fact:
Fact 2: In general, $\cal D'$ and $\cal D''$ are not sub-derivations of $\cal D$!
This depends a bit on the precise formulation of your type system, but most "operational" systems implemented in practice do satisfy Fact 2.
This means that you cannot "pass to sub-terms" when reasoning by induction on derivations, or conclude that the inductive statement is true about the type of the term you're trying to prove something about.
This fact bites you quite harshly when trying to prove seemingly innocent statements, e.g. that systems with typed conversion are equivalent to those with untyped conversion.
However, in the case of type inference, you can give a simultaneous type and sort (the type of the type) inference algorithm by induction on the structure of the term, which may involve a type-directed algorithm as Andrej suggests. For a given term $t$ (and context $\Gamma$, you either fail or find $A, s$ such that $\Gamma\vdash t:A$ and $\Gamma\vdash A : s$. You do not need to use the inductive hypothesis to find the latter derivation, and so in particular you avoid the problem explained above.
The crucial case (and the only case which really requires conversion) is application:
infer(t u):
   type_t, sort_t <- infer(t)
   type_t' <- normalize(type_t)
   type_u, sort_u <- infer(u)
   type_u' <- normalize(type_u)
   if (type_t' = Pi(A, B) and type_u' = A' and alpha_equal(A, A') then
      return B, sort_t (or the appropriate sort)
   else fail

Every call to normalize was done on well-typed terms, as this is the invariant for infer's success.

By the way, as it is implemented, Coq does not have decidable type checking, as it normalizes the body of fix statements before attempting to type check them.
At any rate, the bounds on the normal forms of well-typed terms are so astronomical, that the decidability theorem is mostly academic at this point anyways. In practice, you run the type checking algorithm for as long as you have patience for, and try a different route if it hasn't finished by then.


Cases of nearly linear time solvable linear systems Let a square $n\times n$ real matrix ${\bf A}$ and two vectors ${\bf x}$ and ${\bf b}$ of length $n$, such that $${\bf A}{\bf x}={\bf b}.$$
Solving for ${\bf x}$ through standard Gaussian Elimination yields an aggregate complexity of almost $O(n^3)$.
However, there are cases where solving (or $\epsilon$-approximately solving) for ${\bf x}$ costs $O(n\log^\rho n)$, such as systems where ${\bf A}$ is a symmetric and diagonally dominant matrix (e.g., a Laplacian) [1].

Which other families of linear systems (i.e., matrices) admit linear (or nontrivial poly(n)) time solutions?
If we consider finite fields instead of real matrices, are there any families of matrices there that admit nearly linear time solutions?

[1] http://www.cs.yale.edu/homes/spielman/Research/linsolve.html

Linear systems with circulant matrices can be solved in $O(n \log n)$ using the fast Fourier transform. A circulant matrix has entries $a_{i,j} = a_{1,i+j-1 \bmod n}$ so it is completely specified by the first column. Circulant matrices are diagonalized by the fast Fourier transform (log-linear time) and linear systems with diagonal matrices can be solved in linear time. See for instance the Wikipedia article http://en.wikipedia.org/wiki/Circulant_matrix for more details.

Apologies if this is too trivial to be mentioned here.


Greedy MAX SAT approximation ratio Consider a naive MAX SAT approximation algorithm:

pick a literal $l$ which appears in maximum number of clauses
set the corresponding variable of $l$, such that all clauses containing $l$ are satisfied
repeat on the reduced formula until no variables remain

What is the approximation factor of the algorithm?

It's easy to show by induction, that at least half of all clauses will end up sattisfied. But I can't find a tight example  with only 1/2 clauses sattisfied and all clauses satisfiable. I expect, that the approximation ratio is better than 1/2, but I can neither prove it nor disprove it.

Thank you very much.

To complement the other answer: Costello, Shapira and Tetali showed that the expected approximation ration achieved by Johnson's algorithm on a random permutation of the variables is strictly better than $\frac{2}{3}$. Poloczek and Schnitger showed that another randomized version of the algorithm has expected approximation ratio $\frac{3}{4}$, and that the random permutation version does worse than $\frac{3}{4}$.

By the way do not feel bad about getting stuck on this. Proving an approximation ratio better than $\frac{1}{2}$ for this algorithm was an open problem for a while.


Shortest paths with structured dependence on earlier path Perhaps this problem has been studied under a different guise. If so, I'd appreciate any pointers or terms that could help my search for related work.

Suppose we have an undirected simple graph $G=(V,E)$.  Given as input, we associate with each vertex $i$ a binary vector $\boldsymbol m_i$, where $|\boldsymbol m_i| = K$.  $\boldsymbol m_i[k]$ denotes the presence or absence of the $k$-th "marker" for $k \in \{1, ..., K\}$.  Each edge $(i,j)$ is associated with a function $e_{ij} : \{0,1\}^K \to \{0,1\}^K$.  $e_{ij}$ can be arbitrary, except that it must obey a sort of monotonicity property, where

If $m_B[k] \ge m_A[k]$ for all $k$, then $e_{ij}(\boldsymbol m_B)[k] \ge e_{ij}(\boldsymbol m_A)[k]$ for all $k$.

($e_{ij}$ can be different from $e_{ji}$.)

Starting at any vertex, I am interested in efficiently finding a short (or even any) simple path that collects all possible markers (or reporting that one does not exist), where the rules for collecting markers are as follows.  We maintain binary vector $\boldsymbol m$ denoting which markers that we hold (initially none, i.e. all 0), which is updated as we arrive at vertices and traverse edges.

When arriving at vertex $i$, collect all markers present at $i$ that we don't currently hold, i.e. $\boldsymbol m[k] := \max(\boldsymbol m[k], \boldsymbol m_i[k])$ for all $k$.
When traversing edge from $i$ to $j$, $\boldsymbol m := e_{ij}(\boldsymbol m)$.

For $K=1$, I believe this is a standard shortest paths problem.  How efficiently can it be solved for larger $K$?  (In practice, $K$ is around 2 to 100, $|V|$ is several hundred thousand, $|E|$ is 5 to 10 times $|V|$, and if paths exist, we expect them to be fairly short -- if it helps to fix a parameter $L$, which is the maximum path length, I'd be interested as well.)

You can model the situation as a "regular language constraint path problem" as investigated in Barret, Jacob, Marathe 2000.
If you were interested in any shortest path (not just simple ones), this would solve your question:
First, transform your graph into a directed one that additionally has an edge per node (every node is split into two, one for the incoming edges and one for the outgoing edges, these are connected by a new edge, the node edge).  Now, you encode the markers and the functions as labels in an alphabet of size $2^K+2^{2K}$.  The constraining language now has to accept such a word if following your rules leads to the vector of all ones.  This is clearly a regular language because it can be accepted by an automaton with $2^K$ states.

For treewidth bounded graphs the above transformation and an algorithm for regular languages and simple paths (presented in the mentioned paper) allows to solve your question in polynomial time.

For more general graphs, finding a simple paths according to some fairly easy fixed regular language is NP-complete, which does not really imply anything for your question.
In particular the complexity for constant $K$ (and limited path-length) sounds like an interesting question to me.


Linear ordering from weighted directed graph (kittens) I want to build a website to find the cutest kitten(TM) there is. People can upload photos of their kittens, but also can vote on which kitten is the cutest. However, I don't want them to rate on a 1 to 10 scale, but kitten cuteness is relative to other kittens.

Every voter is presented with 3 kittens and needs to order them by cuteness using drag and drop.

From these votes I can compute a weighted cyclic graph with the kittens being nodes and the edges being number of votes

Is there an algorithm to approximate a (partial) linear ordering that takes transitive votes into account ? So one can put the kittens on a 1 to 10 scale after all ?

Sorry for the brevity, maybe I can come back and expand later. There is work in voting and modeling voters that should be relevant. For example, take a model, i.e. in Mallows model, if A is truly cuter than B, then with probability $p > 0.5$ I rank $A$ ahead of $B$ and otherwise I rank B ahead of A. All rankings are made independently.

Then the corresponding voting rule is to compute the MLE underlying "true" ranking that generates the votes we've seen. For this particular model it is the Kemeny rule and it's NP-hard, but there are other models too.

...

(expansion) Condorcet in the 1700s first used the MLE idea. Say that every voter produces a ranking, and in that ranking any given pair of candidates are in the "correct" order with probability $p > 0.5$. Then, given a bunch of people's votes, we want to compute the single linear order that had the highest probability of generating those votes, the MLE. Young showed that the solution of this is the Kemeny voting rule, which minimizes the average bubblesort distance to all the rankings we are given.

Conitzer and Sandholm ('05) extended this idea to other voting rules, with other noise models (e.g. I put the best candidate in the $n$th place with probability $2^{-n}$).

Since then there's been work, e.g. by Xia and Conitzer (09), on extending these ideas to when people don't see the whole list of alternatives, but just get to see some of the alternatives (submit partial orders). This should be relevant to your setting, I think. There is also at least some empirical-type work in this vein. I am thinking specifically of Pfeiffer et al (12). The setting is basically the same as yours. They have some sort of adaptive strategy of which kitten pair (or whatever they used) to show to the next voter. The goal was to get a good ranking with fewer pairwise comparisons (i.e. not asking every voter to rank all the kittens).

That's what I know of the theoretical and AI work. There's also a lot of statistics that I know less about. Probably the stats will be most helpful if you want to actually implement something that aggregates partial rankings/observations.

I know that some of the most popular statistical models for these things are the Mallows model, Bradley-Terry, and Plackett-Luce. All of these are noise models for how voters randomly generate a ranking given the true underlying "correct" ranking. In fact, there is so much work about this going on in statistics that I might suggest you post on stats.se, because I am woefully ignorant but I think they (or perhaps the machine learning community as well) have a lot of work on algorithms for (approximately) finding solutions (e.g. the MLE) given a bunch of rankings and assuming that they were generated using one of these models. At least, I hope these keywords help you in your search!


What's the “smallest” complexity class for which an $\omega \hspace{.02 in}(n)$ circuit lower bound is known? I believe the answers to this question give classes such that for all polynomials $p$,

there is a problem in the class which does not have circuits of size $p(n)$.

However, I'm asking about circuit size $\omega \hspace{.02 in}(n)$.

$\big(\hspace{-0.07 in}\left\langle \hspace{-0.04 in}0^{\hspace{.02 in}0}\hspace{-0.03 in},\hspace{-0.04 in}1^{\hspace{-0.03 in}1}\hspace{-0.03 in},2^{\hspace{.02 in}2}\hspace{-0.04 in},\hspace{-0.03 in}3^1\hspace{-0.04 in},\hspace{-0.03 in}4^4\hspace{-0.03 in},\hspace{-0.03 in}5^1\hspace{-0.04 in},\hspace{-0.03 in}6^{\hspace{.03 in}6}\hspace{-0.03 in},\hspace{-0.03 in}7^1\hspace{-0.03 in},\hspace{-0.03 in}8^8\hspace{-0.03 in},\hspace{-0.03 in}9^1\hspace{-0.03 in},...\hspace{-0.05 in}\right\rangle \:$ is super-linear but not $\omega \hspace{.02 in}(n)$.

Although such even-odd behavior could be handled by padding, one might instead

have extremely long streaks of super-polynomial values between low values.)

$S^p_2$ and $PP$ are both known not to have $n^k$-circuits for any fixed k and there is no known containment between them. Details in my blog post.

Update: As Rickey Demer points out, these results do not necessarily give a language with a lower bound for all $n$ in $S_2^p$. I think the $\Delta^p_3$ is probably the best known. Since $PP$ has complete sets you might be able to get a all $n$ bound but I don't have a full proof.


Is there a P-complete problem on diophantine equations? In general deciding whether a diophantine equation has any integer solutions is equivalent to the halting problem.  I believe that deciding if a quadratic diophantine equation has any solution is NP-complete. Does there exist a further restriction on the equations involved that yields a P-complete problem?

No , as far as i know diaphantine problem in general is undecidable thus equivalent to halting problem , if the equations are restricted to be quadratic then it is np-complete , and linear diaphantine equation can be reduced to integer programming problem and For linear Diophantine equation equations, integral solutions exist if and only if, the GCD of coefficients of the two variables divides the constant term perfectly.


Automata and a kind of pumping lemma on state transition function We encountered this question as an exercise in a Büchi automata book a couple of decades ago, and back then gave a few tries thinking that it should be easy. But haven't seen a solution. My friend Deepak helped me with the problem statement, here it is:

Given a DFA $A =
(Q,Letters,\delta,Final)$ with $n$ states,
each letter $a$ induces a function
$f_a: Q \to Q$, given by $f_a(q) = \delta(q,a)$.
A word $w$, by extension, also induces a
function $f_w : Q \to Q$.

The problem was to show that for any $w$, we can find
a $w'$ of length $\leq n!$, such that $f_{w'} = f_w$.

Wondering if there is any bound on the word length, even if not a $n!$ (like $n^n$).

The following argument works as long as $f_w$ is injective. The same ideas should also work for general $f_w$. Indeed, below I show how they give a bound $|w| \leq O(n!)$. However, even further down I show a much better bound, $|w| \leq e^{2(1+o(1))\sqrt{n\log n}}$, which is tight up to the constant $2$.

Consider some word $w$ which is the minimal length word resulting in $f_w$, and suppose that the range of $f_w$ is $Q$. We want to show that $|w| \leq n!$.
Let $w_{\leq i}$ denote the prefix of $w$ of length $i$. If $f_{w_{\leq i}} = f_{w_{\leq j}}$ for some $i < j$ then $f_{w_{\leq i} w_{>j}} = f_w$, contradicting the assumption that $w$ has minimal length. We conclude that $f_{w_{\leq i}}$ is different for all $i$. Since the range of $f_w$ is full, all $f_{w_{\leq i}}$ must be permutations of $Q$. Since there are $n!$ permutations of $Q$, we conclude that $|w| \leq n!-1$.

Suppose now that $f_w$ is not injective, and write $w = x_1\ldots x_k$, where each step passing from $x_i$ to $x_{i+1}$ decreases the image. The same argument as before shows that $|x_1| \leq n!$, $|x_2| \leq n!/1!$, $|x_3| \leq n!/2!$, and so on. In total, we get that $|w| \leq n!(1+1+1/2+1/6+\cdots) \leq e n!$.

We can do slightly better. For example, if $f_{x_1}(q_1) = f_{x_2}(q_2)$ then when bounding $x_1$, it is enough to consider permutations up to a permutation of the images of $q_1$ and $q_2$, and so when $k \geq 2$ we can conclude that $|x_1| \leq n!/2$. This argument probably gives $|w| \leq (3/2)n!$. One can probably push the argument further, but that would require looking across the boundaries of the segmentation $w=x_1\ldots x_k$.

The following construction shows that $n!-1$ cannot be replaced by anything smaller than roughly $e^{\sqrt{n\log n}}$. Landau's function $g(n)$ is the maximal order of an element in $S_n$. It is known that $g(n) = e^{(1\pm o(1))\sqrt{n\log n}}$. Given an element $\pi \in S_n$ of maximal order, we can construct an automaton over the one language alphabet $\{a\}$ in which $Q = \{1,\ldots,n\}$ and $f_a = \pi$. The word $a^{g(n)-1}$, which generates the permutation $\pi^{-1}$, cannot be shortened.

Consider again the case of injective $f_w$. We can think of the letters of $w$ as generating a subgroup of $S_n$. Babai and Seress show that the diameter of the corresponding Cayley graph is at most $e^{(1+o(1)) \sqrt{n\log n}}$. This means that every permutation in the subgroup, including $f_w$, can be written as a word over the letters of $w$ and their inverses of length at most $e^{(1+o(1)) \sqrt{n\log n}}$. Since the order of each permutation is at most $e^{(1+o(1))\sqrt{n\log n}}$, we can replace the inverse of each letter by at most $e^{(1+o(1))\sqrt{n\log n}}$ copies of itself, obtaining a word of length $e^{2(1+o(1))\sqrt{n\log n}}$. This bound can perhaps be improved by looking at the construction of Babai and Seress.

In the general case, segment $w=x_1\ldots x_k$ as before, where $k \leq n$. A similar argument shows that $|x_i| \leq e^{2(1+o(1))\sqrt{n\log n}}$, and so $|w| \leq e^{2(1+o(1))\sqrt{n\log n}}$.

This still leaves open the value of the smallest $\ell(n)$ such that the minimal word $w$ with given $f_w$ has length at most $\ell(n)$. Our arguments show that $e^{(1+o(1))\sqrt{n\log n}} \leq \ell(n) \leq e^{2(1+o(1))\sqrt{n\log n}}$, leaving a small gap.


Generating "infinite" randomness from a constant number of sources I recently came across a paper by Coudron and Yuen on randomness expansion using quantum devices. The main result of the work is that it is possible to generate "infinite" randomness from a constant number of sources (that is, the number of random bits generated depends only on the number of rounds of the protocol and not on the number of sources).

Naively, this sounds to me like the result allows derandomization of any randomized algorithm with quantum sources, and would imply some kind of containment of randomized complexity classes inside a corresponding quantum class.

But I don't really understand quantum information theory, and am sure there are many subtleties I'm missing. Not to mention that if such claims were possible, the authors would have made it. So my question is:

  Does the existence of "infinite randomness expansion" as described in the paper (and all the related work) imply some kind of derandomization statements for randomized complexity classes ? And if not, why not ?

Update: I was pointed to this excellent high level overview of the area and of the above paper by Scott Aaronson. Unfortunately I'm still confused :).

This is a great question, Suresh!

Our randomness expansion result does not imply any complexity theoretic result. Here's one way to understand the result: we believe that quantum mechanics governs the world, and under this assumption, there are quantum devices that generate genuine, true, information-theoretic randomness.

However, imagine that you're mistrustful of these boxes that claim to do this wonky quantum stuff and generate randomness (for some, this may not take too much imagining). You don't want to deal with qubits. All you understand are classical bit strings.

Randomness expansion is a protocol where you, as a classical verifier, can interact with a bunch of black boxes (think of them as non-communicating provers), and after running a protocol with these black boxes, you've certified that their outputs contain very high entropy -- if the provers pass. Furthermore, the amount of randomness you started with is much less than the output entropy you certified.

In other words, it's an interactive proof for randomness generation.

So, the only "derandomization" aspect of it is to argue that the protocol itself requires small startup randomness. But the outcome is very un-derandomized: the output produced by the boxes is true randomness, not pseudorandomness (i.e. no computational assumptions).


Pi-type over a list in dependent type theory In a formalization I need to create an inductive type which has a term for each element in a list, something like this (I'll use Agda in the following, but everything here is standard dependent type theory):
data DataType : Type where
  inj : (xs : List A) → (x : {! xs !}) → DataType

Of course, we cannot have a Pi type over x : xs in the middle since xs is a term and not a type, so we cannot quantify over it.
We can use singletons to get an n-tuple from a list as follows:
Singleton : (x : A) → Type
Singleton x = Σ[ y ∈ A ] (y ≡ x)

list→type : List A → Type
list→type [] = ⊥
list→type (x ∷ []) = Singleton x
list→type (x ∷ y ∷ xs) = Singleton x × list→type (y ∷ xs)

That way a list 1 ∷ 2 ∷ 3 ∷ [] is turned into the tuple (s1, s2, s3), from which can recover the numbers in the list. However, this tuple is still just one term, so we will only have a single inj (s1, s2, s3) in our data type above when using list→type xs in the Pi type above.
How can we get a different inhabitant in DataType for each element of the list? Is there a standard way to deal with that? Or do I fundamentally misunderstand something? It's of course a bit awkward to mix a data structure understanding of "collection" with the basic doctrine of regarding types as collections (with explicit term constructors), but it still should be possible to reconcile both understandings I hope.

You asked several questions.
You asked about a type indexed by a list, so you can do this.
data DataType (A : Type) (F : A -> Type) : List A -> Type where
  empty : DataType A F []
  _bla_ : forall {xs} {x} -> DataType A F xs -> F x -> DataType A F (x ∷ xs)

Where F is a type family that is indexed by the elements of the list.
Apart from that, you mentioned tuples. Probably you want a sized vector (Data.Vec in stdlib) for tuples. For instance, Vec Nat 3 is such a type that 1 ∷ 2 ∷ [] and 1 ∷ 2 ∷ 3 ∷ 4 ∷ [] are both invalid instances, only 1 ∷ 2 ∷ 3 ∷ [] is.


Could chromatic number be easy to calculate when colouring is hard for some graph class? Similar question was asked before, but there was an error in it so it was left unanswered Graph class with easy chromatic number, but NP-hard coloring

Is there any infinite set of graphs $C$ such as:

There is a polynomial algorithm recognizing for every graph $G$ whether $G$ belongs to $C$
There is a polynomial time algorithm computing chromatic number $\chi(g)$ for every $g \in C$
Humankind does not know a polynomial time algorithm for computing proper colouring for $C$, or (which is better) there is a proof that such an algorithm (under reasonable assumptions) does not exist.

Yes. Since 3-COLORING is FNP-complete, for any problem in FNP we can construct a graph G that is 3-colorable if and only if the problem has a solution. So you can pick your favorite problem from TFNP\FP (if it's not empty!), like finding a factor of a composite number, or a second Hamiltonian-cycle in a 3-regular graph, and convert it into a graph.

In more detail with the example of finding a factor.
We will fix an algorithm that converts a composite number $N$ into a graph $G(N)$ such that from $G(N)$ you can decode the value of $N$.
Compositeness of $N$ is a necessary for $G(N)$ to be in our class.
Moreover, any proper $3$-coloring of $G(N)$ can be converted into a proper divisor $d$ of $N$.
This can be done, e.g., by writing up a CNF that describes whether a given $d$ encoded in binary as $x_1\ldots x_{n}$ divides a fixed $N$ (that also has $n$ digits in binary, but these are not variables).
From satisfiability of a CNF there is a standard reduction to 3-COLORABILITY such that you can easily convert a proper $3$-coloring back to an $x_i$ satisfying assignment.
Thus solving the coloring problem, you would find a divisor $d$.
Moreover, by adding some simple extra gadgets, you can also decide whether a graph is of this form or not.
Our class is formed by graphs created this way, which are thus all $3$-colorable.


Examples/Textbooks on amortized analysis of algorithms I am trying to get the amortized analysis for a complicated algorithm. I am wondering whether there are textbooks or illustrative examples that could serve as inspiration of techniques in amortized analysis.

For textbook references an interesting article is as follows:

https://www.geeksforgeeks.org/analysis-algorithm-set-5-amortized-analysis-introduction/

I can also refer to one recent paper which is very simple involving a straightforward application of amortized analysis:

https://arxiv.org/abs/1804.01823


How are proofs verified probabilistically in interactive proof systems? I'm having a hard time understanding the way Arthur verifies proofs probabilistically with coin tosses in an intuitive manner.

Suppose Arthur is a logician equipped with paper, a pencil and an unbiased coin. Someone hands Arthur a proof that some string s is in some language L. How exactly does Arthur probabilistically check the proof? My interpretation is that he does the following:

Arthur tosses the coin. If it lands showing heads, he accepts the first statement without checking it. If it lands tails, he checks it. If, upon checking, he determines that the first statement is false, he rejects the proof. Otherwise, if he determines that the first statement is true, he continues this process with the next statement of the proof. If Arthur never rejects the proof during this process, then he accepts the proof if one of the statements is a concluding statement of the form "..., hence s is in L" and he rejects the proof otherwise.

Is this a correct interpretation?

Edit: I am not talking about probabilistically checkable proofs. The question above came about from thinking about the class MA.

Your interpretation isn't using randomness in the right way in an MA protocol.

Every MA problem can be reduced to a polynomial-size circuit of AND-OR-NOT gates, with some input variables designated for Merlin and the rest designated for Arthur. First Merlin tells Arthur the TRUE-FALSE values of Merlin's variables. Then Arthur flips coins to choose the TRUE-FALSE values for Arthur's variables. That's all the randomness Arthur needs so he can now throw his coin away.

Now we have a logical circuit with no free variables. Arthur deterministically verifies that the circuit outputs true.