Historical reasons for adoption of Turing Machine as primary model of computation. It's my understanding that Turing's model has come to be the "standard" when describing computation. I'm interested to know why this is the case -- that is, why has the TM model become more widely-used than other theoretically equivalent (to my knowledge) models, for instance Kleene's μ-Recursion or the Lambda Calculus (I understand that the former didn't appear until later on and the latter wasn't originally designed specifically as a model of computation, but it shows that alternatives have existed from the start).

All I can think of is that the TM model more closely represents the computers we actually have than its alternatives. Is this the only reason?

This seems to be true in the context of (some areas of) computer science but not generally.
One reasons has to do with the Church's Thesis. The main reason is that some experts like Godel didn't think that the arguments that previous/other models of computation capture exactly the intuitive concept of computation were convincing. There are various arguments, Church had some, but they did not convince Godel. On the other hand Turing's analysis was convincing for Godel so it was accepted as the model for effective computation. The equivalences between different models is proven later (I think by Kleene).
The second reason is technical and a later development related to the study of complexity theory. Defining the complexity measures like time, space, and nondeterminism seems to be easier using Turing machines than other models like $\lambda$-calculus and $\mu$-recursive functions.
On the other hand, $\mu$-recursive functions were and are still used as the main way of defining computability in logic and computability theory books. They are easier to work with when one only cares about effectiveness and not about complexity. Kleene's book "Metamathematics" was very influential for this development. Also $\lambda$-calculus seems to be more common in CMU/European style computer science like programming languages and type theory. Some authors prefer the RAM and Register Machine models.
(It seems to me that for some reason Americans adopted Turing's semantic model and Europeans adopted Church's syntactic model, Chruch was American and Turing was British. This a personal opinion/observation and others have a different view. Also see these papers by Viggo Stoltenberg-Hansen and John V. Tucker I,II.)
Some resources for further reading:
Robert I. Soare has a number of articles on the history of these developments, I personally like the one in the Handbook of Computability Theory. you can find more by checking the references in that paper.
Another good resource is Neil Immerman's computability article on SEP, see also Church-Turing Thesis article by B. Jack Copeland.
Godel's collected works contains lots of information on his views. Specially introductions to his articles are extremely well-written.
Kleene's "Metamathematics" is a very nice book.
Finally, if you are not still satisfied check the archives of the FOM mailing list, and if you cannot find an answer in the archive post a an email to the mailing list.


Given a partition and an element, find the subset that includes this element I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am mostly interested in some general background on this problem. I'm stuck because I do not know of a canonical "name" for this problem.
Does this problem have a name, or is there a closely related problem that might generate some useful hits?

It is unlikely to have a "name" because it is trivial: it can be solved with a hashtable, array, self-balanced binary search tree, or any other data structure that maps $x$ to $X_i$.


Primitive Recursive Definition : Binary numbers Usually primitive recursive functions are define from Zero, Identity and Successor, projectors, composition and recursion.

But you obtain algorithms that works with unary numbers. For example, the addition $x+y$ has complexity $O(y)$, whereas usually, it has complexity $O(|x|+|y|)$. Is there a canonical definition of recursive functions that consider integers as binary string ? Any references are welcomed.

The concept of primitive recursion function easily generalizes to any inductive data structure. For example, you can define the primitive recursive functions on binary strings as the smallest class of functions containing $\epsilon$ (the constant "empty string"), $S_0,S_1$ (append $0$ or $1$), projections and closed under composition and the scheme allowing to define a function $f$ by
$$
\begin{align*}
f(\epsilon,\vec x) &= g(\vec x), \\
f(zi,\vec x) &= h_i(z,\vec x,f(z,\vec x)), & i\in\{0,1\}
\end{align*}
$$
as soon as $g$ and $h_0,h_1$ are already in the class.

In the above setting, the usual numerical functions may be encoded either by considering only unary strings (i.e., $n$ is represented by $1^n$), in which case you can mimick the usual primitive recursive functions, or, more interestingly, by representing integers in binary. In that case, the successor function is not part of the basic functions but must be defined (and this is not immediate).

As you point out, traditional recursion theory considers primitive recursion on unary strings (or tally integers) because in that setting complexity is not a main concern.  On the other hand, whenever complexity classes are defined in terms of recursive functions, primitive recursion on binary strings (or binary integers) is routinely used. See for example the seminal paper by Bellantoni and Cook "A New Recursion-Theoretic Characterization of the Polytime Functions", Computational Complexity 2(2):97-110.


Pairwise comparison of bit vectors Define a partial order $\le$ on $\{0,1\}^d$ by pointwise comparison, i.e., we say $x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,d$.

I am interested in the following problem:

Given $x_1,\dots,x_n \in \{0,1\}^d$ and $y_1,\dots,y_n \in \{0,1\}^d$, I want to determine whether there exists $i,j$ such that $x_i \le y_j$.

How efficiently can this be solved?  Pairwise comparison requires $\Theta(n^2)$ comparisons.  Can we find a more efficient algorithm?

I would be fine with assuming that the $x$'s and $y$'s come from some reasonable distribution and evaluating using the expected running time, if that helps.  We can assume $d$ is small compared to $n$.

Equivalent statement of the problem: Given sets $S_1,\dots,S_n$ and $T_1,\dots,T_n$, determine whether there exists $i,j$ such that $S_i \subseteq T_j$, where all sets are over the universe $\{1,2,\dots,d\}$.

This problem is sometimes called Subset Containment and it is computationally equivalent to: given $n$ sets $S_1,\ldots,S_n \subseteq [d]$, are there $i \neq j$ such that $S_i \cap S_j = \varnothing$? (I believe the reduction is folklore and appears in several places, but one concrete reference is the arxiv paper "Into the Square".) In turn, this disjointness problem is identical to the (gradually becoming infamous) Orthogonal Vectors (OV) problem.

Therefore, algorithms for OV apply directly to this problem. Hence the problem can be solved in $O(2^d \cdot n)$ time, $O(n^{2-1/O(\log(d/\log n))})$ time, and so on (see for example, this SODA'15 paper). Also, there is an $\tilde{O}(n + 2^d)$ time algorithm (I can give it, if you're interested). Furthermore, fine-grained hardness results for OV apply to the problem as well. For example, if it could be solved in $n^{1.999} 2^{o(d)}$ time in the worst case, then the Strong Exponential Time Hypothesis is false -- but don't let that stop you ;)

The "average case" (depending on how you define it) is generally easier and is (as far as we know) unrelated to Strong ETH; partial search data structures (such as Rivest's work on partial search from the 1970s) can be used to solve the average case in subquadratic time.


Is there any known Poly-APX-complete minimimization problem? All Poly-APX-complete problems I know are maximization problems, e.g. Max Clique, Max Independent Set, Max One for some set of contraints, and even choosing the attributes of a product to maximize (Max again!) the number of customers preferring it, provided that preferences are additive (http://www.sciencedirect.com/science/article/pii/S1568494617300510). Max, max, max... Is there any known Poly-APX-complete Min problem?

I suspect a problem I'm dealing with might be Poly-APX-complete, but it's a minimization problem. If there were some known Poly-APX-complete Min problem, an AP-reduction from it into my target problem would map Min into Min, so proving the Poly-APX-hardness of my target problem would probably be more natural and easier.

I've just discovered there exists at least one confirmed minimization Poly-APX-complete problem: Min ones if setting all variables true satisfies all clauses (together with other conditions). It is shown in "The Approximability of Constraint Satisfaction
Problems" by Sanjeev Khannay, Madhu Sudanz, Luca Trevisanx and David P. Williamson (http://people.csail.mit.edu/madhu/papers/2001/kstw.pdf), Theorem 2.14, item (5).


Any polynomial which is hard to count but easy to decide? Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate
polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial
$f(x_1,\ldots,x_n)$, the circuit

 computes $f$ if $F(a)=f(a)$ holds for all $a\in \mathbb{N}^n$;
 counts $f$ if $F(a)=f(a)$ holds for all $a\in\{0,1\}^n$;
 decides $f$ if $F(a)>0$ exactly when $f(a)>0$ holds for all  $a\in\{0,1\}^n$.

I know explicit polynomials $f$ (even multilinear) showing that the circuit-size gap "computes/counts" can be exponential. My question concerns the gap "counts/decides".

Question 1: Does anybody know of any polynomial $f$ which is exponentially harder to count than to decide by $\{+,\times\}$-circuits?

As a possible candidate, one could take the PATH polynomial whose variables correspond to edges of the complete graph $K_n$ on $\{1,\ldots,n\}$, and each monomial corresponds to a simple path from node $1$ to node $n$ in $K_n$.
This polynomial can be decided by a circuit of size $O(n^3)$ implementing, say, the
Bellman-Ford dynamic programming algorithm, and it is relatively easy to show that every $\{+,\times\}$-circuit computing PATH must have size $2^{\Omega(n)}$.

 On the other hand, every circuit counting
PATH solves the $\#$PATH problem, i.e. counts the number of $1$-to-$n$ paths in the specified by the corresponding $0$-$1$ input subgraph of $K_n$. This is a so-called $\#$P-complete problem. So, we all "believe" that PATH cannot have any counting $\{+,\times\}$-circuits of polynomial size. The "only" problem is to prove this ...

I can show that every $\{+,\times\}$-circuit counting a related  Hamiltonian path polynomial HP requires exponential size. Monomials of this polynomial correspond to $1$-to-$n$ paths in $K_n$ containing
all nodes.
Unfortunately, the reduction of $\#$HP to $\#$PATH by Valiant requires to compute the inverse of the Vandermonde matrix, and hence cannot be implemented by a $\{+,\times\}$-circuit.

Question 2: Has anybody seen a monotone reduction of $\#$HP to $\#$PATH?

And finally:

Question 3: Was a "monotone version" of the class $\#$P considered at all?

N.B. Note that I am talking about a very restricted class of circuits: monotone arithmetic circuits! In the class of $\{+,-,\times\}$-circuits, Question 1 would be just unfair to ask at all:  no lower bounds larger than $\Omega(n\log n)$ for such circuits, even when required to compute a given polynomial on all inputs in $\mathbb{R}^n$, are known.
Also, in the class of such circuits, a "structural analogue" of Question 1 --
are there $\#$P-complete polynomials which can be decided by poly-size $\{+,-,\times\}$-circuits? --
has an affirmative answer. Such is, for example, the permanent polynomial PER$=\sum_{h\in S_n}\prod_{i=1}^n x_{i,h(i)}$.

ADDED:  Tsuyoshi Ito answered Question 1 with a very simple trick. Still, Questions 2 and 3 remain open. The counting status of PATH is interesting in its own both because it is a standard DP problem and because it is #P-complete.

(I am posting my comments as an answer in response to the OP’s request.)

As for Question 1, let fn: {0,1}n→ℕ be a family of functions whose arithmetic circuit requires exponential size.  Then so does fn+1, but fn+1 is easy to decide by a trivial monotone arithmetic circuit.  If you prefer to avoid constants in monotone arithmetic circuits, then let fn: {0,1}n→ℕ be a family of functions such that the arithmetic circuit for fn requires exponential size and fn(0, …, 0)=0, and consider fn+x1+…+xn.


Can $\{a^nb^n\}$ be recognized in poly-time probabilistic sublogarithmic-space? Consider language $ \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} $.

It is known that $ \mathtt{EQUALITY} $ cannot be recognized by any sublogarithmic-space alternating Turing machine (ATM) (Szepietowski, 1994). (There is an ATM using sublogarithmic space for members but not for all non-members!)

On the other hand,  Freivalds (1981) showed that bounded-error constant-space probabilistic Turing machines (PTMs) can recognize $ \mathtt{EQUALITY} $ but only in exponential expected time (Greenberg and Weiss, 1986). Later, it was shown that no bounded-error $ o(\log\log n) $-space PTM can recognize a non-regular language in polynomial expected time (Dwork and Stockmeyer, 1990). My question is

  whether poly-time sublogarithmic-space PTMs recognize $ \mathtt{EQUALITY} $ with bounded-error.

I have found an answer to my own question. The result was given in Section 5 of Karpinski and Verbeek, 1987.

For any input of length $ n $, a PTM can construct $ \Theta(\log \log n) $ space with high probability (Section 4). (With a very small probability, the machine can also construct logarithmic space, and this might be seen as a "drawback" of the algorithm.) Then, the PTM can decide whether the numbers of $a$'s ($n$) and $b$'s ($m$) are equal with high probability by using $ O(\log \log n) $ space in polynomial time.

The idea is as follows. If $ n \neq m $, then $ \exists k \leq 4 \log(n+m) $ such that $ n \not\equiv m \mod k $ (Alt and Mehlron, 1976). The PTM can pick a random $ k $ by using $ O(\log \log n) $ space. $ O(\log \log n) $ is also sufficient to keep a counter and so trying more than half of all possible $k$'s. The case of $ n \neq m $ can be detected with a probability more than $ 1 \over 2 $.


Relating functors to relational functors with the parametricity translation $\newcommand{\Type}{\text{Type}}\newcommand{\id}{\text{id}}\newcommand{\map}{\text{map}}$
In attempting to answer the question: Rigorous proof that parametric polymorphism implies naturality using parametricity? I tried showing that one obtains the theory of relational functors by applying the parametricity translation to the theory of functors, where relational functors are defined in Logical Relations and Parametricity - A Reynolds Programme for Category Theory and Programming Languages.
Specifically, if we are given
\begin{align*}
F_! &: \Type\to\Type\\
F_{\map} &: (A,B:\Type)\to(A\to B)\to(F_!A\to F_!B)\\
F_{\id}&:(A:\Type)\to F_{\map}(\id(A)) = \id(F_!A)
\end{align*}
I was able to show (with generous hand-waving) that
\begin{align*}
F_!^R &: (A,B:\Type)\to \text{Rel}(A,B)\to\text{Rel}(F_!A,F_!B)\\
F_\map^R &:(A_0,A_1: \Type)\to(A^R:\text{Rel}(A_0,A_1))\to (B_0,B_1:\Type)\to(B^R:\text{Rel}(B_0,B_1))\\
&\quad\to(f_0:A_0\to B_0)\to(f_1 : A_1\to B_1)\\
&\quad\to((x_0:A_0)\to(x_1:A_1)\to A^R(x_0,x_1)\to B^R(f_0x_0,f_1x_1))\\
&\quad\to(x_0 : F_! A_0)\to(x_1 : F_! A_1)\to F_!^R(A_0,A_1,A^R,x_0,x_1) \\
&\quad\to F_!^R(B_0,B_1,B^R,F_\map (A_0,B_0,f_0,x_0),F_\map (A_1,B_1,f_1,x_1))
\end{align*}
But I am having trouble showing that $F_\id^R$ gives some form of the identity extension property, namely that
$$A:\Type\vdash F_!^R(A,A,\text{Id}(A)) = \text{Id}(F_!^RA) $$
It seems to me that the pair $(F,F^R)$ should give a relational functor in the sense of definition 6.1.
Is my intuition that this should be the case correct, and if so, is there some higher level explanation for this (perhaps some sort of Yoneda embedding?)?

$(F, F^R)$ is not necessarily a relational functor. Define $F : \text{Set} \to \text{Set}$ to be the identity functor on sets and functions, but let ${F_!}^R$ send all relations to the trivial relation. Then ${F_{\text{map}}^R}$ trivially holds (along with ${F_{\text{id}}^R}$ and ${F_{\text{comp}}^R}$ which always hold for any $F$, because of the proof-irrelevance of equalities), but $F^R$ does not preserve identity relations.
Going back to the linked question: if a functor is defined internally in a parametric type theory, we don't really care about whether identity extension is derivable: we always get it as part of the "free theorem" package, so every internal $\text{Type} \to \text{Type}$ functor is also a relational functor externally.


Classification of a specific problem Is it known that $\mathsf{IP}\notin\mathsf{NP}^{cc}\cup\mathsf{coNP}^{cc}$ where $\mathsf{IP}$ is inner product communication complexity problem? Where is the classification of $\mathsf{IP}$ currently in?

Let $\mathsf{coIP}$ denote the problem of returning the negation of the inner product. It has roughly the same complexity as $\mathsf{IP}$ since we can add to both players an extra $1$ bit. It is known that the deterministic communication complexity of a decision problem is upper bounded by the product of the non-deterministic complexities of the problem and its complement. Since $\mathsf{IP}$ has deterministic complexity $\Omega(n)$, it follows that the non-deterministic complexity of $\mathsf{IP}$ and $\mathsf{coIP}$ is $\Omega(\sqrt{n})$, and in particular $\mathsf{IP} \notin \mathsf{NP}^{cc} \cup \mathsf{coNP}^{cc}$.

Sun, Wang and Yu showed that the non-deterministic communication complexity of $\mathsf{IP}$ is in fact $\Omega(n)$, even under the promise that the answer is either $0$ or $1$ (as an integer value).

In the related $\mathsf{MA}$ model, in which we demand perfect completeness but only constant soundness, there is an $O(\sqrt{n}\log n)$ protocol due to Aaronson and Wigderson almost matching Klauck's $\Omega(\sqrt{n})$ lower bound; see for example Pitassi's lecture notes.


Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$? I am asking this question from the context of parameter preserving reductions which has implications for kernelization (See Theorem 18 of [1] for an example). For simplicity, here I am assuming that the host graph $G$ is regular. It seems to me that the game theoretic definition of treewidth is more useful here (See Section 2 of [2]).
Let $G$ be a regular graph with maximum degree $\Delta$. Let $H$ be a graph with $\Delta$ marked vertices. Let $G^*$ be the graph obtained from $G$ by replacing each vertex $v$ of $G$ by a copy of $H$ (say, each marked vertex of $H$ takes one neighbor of $v$ each).
Can we say that treewidth of $G^*$ is at most $\max\{tw(G)+\Delta,tw(H)+\Delta\}?$
(Let's use $tw(J)$ to denote the treewidth of a graph $J$.
For the special case $tw(H)\leq tw(G)$, we get the question in the title).
In [1], they consider the case when $H$ is sunlet$_6$ (i.e., $C_6$ plus a leaf attached to each vertex). In that paper, it is claimed that $tw(G^*)\leq tw(G)+2$. Is this claim correct?
(Disclaimer: it is possible that their claim is correct, but my idea of the generalization given as the first question is wrong).
The presentation in [1] gave me the feeling that the answer to the first question is yes. But, I couldn't find a reasonable explanation. I would like to know whether I am overlooking something well-known here.
Similar Situations
We can say the following.

If one vertex $v$ of $G$ alone is replaced by a copy of $H$, then the treewidth of the resultant graph is at most $\max\{tw(G)+\Delta,tw(H)+\Delta\}$.

Idea (in terms of cops and robber game): In an optimal cop strategy of $G$, whenever there is a cop at $v$, place $\Delta$ cops at marked vertices of $H$. Also, choose one of those points, make a new branch there which raids $H$. This forms a cops strategy for the resultant graph.
(Idea in terms of tree-decomposition: In the tree-decomposition of $G$, in each bag containing $v$, replace $v$ by marked vertices of $H$. Also, choose one such bag $B$ and append a new branch there that 'raids' $H$; in other words, take the tree-decomposition of $H$, add marked vertices of $H$ to each bag, and append this as a branch to the vertex associated with the bag $B$.)

Let $K$ be a graph with two marked vertices. Let $G'$ be the graph obtained from $G$ by replacing each edge $e$ of $G$ by a copy of $K$ (say, each marked vertex of $K$ takes one incident vertex of $e$ each). Then, the treewidth of $G'$ is at most $\max\{tw(G)+\Delta,tw(K)+\Delta\}$.

Idea (in terms of cops and robber game): Consider an optimal cops search strategy. For each edge $e=uv$ of $G$, choose a point in the strategy when edge $e$ is searched (i.e., there is a cop at $u$ and a cop at $v$) and raid $H$ at that point. This forms a cops strategy for $G'$.
Thank you.
References
[1] Lauri, Juho; Mitillos, Christodoulos, Complexity of fall coloring for restricted graph classes,  ZBL07173544.
[2] Langer, Alexander; Reidl, Felix; Rossmanith, Peter; Sikdar, Somnath, Practical algorithms for MSO model-checking on tree-decomposable graphs, Comput. Sci. Rev. 13-14, 39-74 (2014). ZBL1302.68184.

Let $G$ be a complete graph with $n$ vertices and $H$ be a complete graph with $n-1$ vertices, all marked. We replace each vertex of $G$ with $H$ to produce a graph $G^*$ with $n(n-1)$ vertices that is $n$-regular. We claim that the treewidth of $G^*$ is at least $n (n-1)/12$, which falsifies the conjecture. Proof:
Suppose that the treewidth of $G^*$ is less than $n(n-1)/12$. Therefore by standard results [1] its vertices can be partitioned to sets $A$, $S$, $B$ such that there are no edges between $A$ and $B$, and $|S| = n(n-1)/12$, $|A| \ge n(n-1)/4$, $|B| \ge n(n-1)/4$, and $|A| + |B| = n(n-1)11/12$.
We call the cliques $H$ in $G^*$ corresponding to vertices of $G$ clusters. The graph $G^*$ has $n$ clusters. Note that each cluster has vertices from at most one of $A$ or $B$. Let $A_f$ be the fraction such that $n A_f$ clusters contain vertices from $A$ and $B_f$ the fraction such that $n B_f$ clusters contain vertices from $B$.
Now, $A_f \ge 1/4$, $B_f \ge 1/4$, and $A_f + B_f \ge 11/12$.
Notice that if there is a cluster $v$ that contains vertices from $A$ and a cluster $u$ that contains vertices from $B$ then these clusters are connected by an edge $\{v_i, u_j\}$, both vertices in it unique to that pair of clusters, and at least one of $v_i$ and $u_j$ should be in $S$.
Therefore we get that $|S| \ge n^2 A_f B_f$, which we can solve with our constraints to a minimum value $|S| \ge n^2 A_f B_f \ge n^2 8/12 \cdot 1/4 = n^2 1/6$, which is a contradiction to the assumed size of $S$.
[1] http://parameterized-algorithms.mimuw.edu.pl/parameterized-algorithms.pdf


Complexity of Finding Optimal Synergistic Set Packings Motivation: While developing tools for fast execution of machine learning workflows, we realized that many workflows require intermediate results -- sometimes we should cache these results, and sometimes we should recompute them from scratch.

We were able to reduce the problem of determining the optimal set of intermediate results to cache to the following very natural problem, which I call synergistic set-packing.

Problem: We are given a universe of $m>0$ elements $U = \{e_1, e_2, \ldots, e_m\}$, as well as a function $c : U\rightarrow \mathbb{Z}^+$ which maps each element to some positive integral cost. We are furthermore given a collection $\mathcal{C}$ containing $n>0$ nonempty subsets of $U$; $\mathcal{C} = \{S_1, S_2, \ldots, S_n\}$. Finally, we are also given a function $p : \mathcal{C} \rightarrow \mathbb{Z}^+$ which maps each $S_i$ to some positive payoff.

Our goal is to choose $X \subseteq U$ that maximizes the following benefit function of payoff - cost:
$$
\left(\sum_{S_i\in\mathcal{C} \text{ with } S_i\subseteq X}p(S_i)\right) - \left(\sum_{e_j\in X} c(e_j)\right)
$$

That is, if we pick all of the elements for some $S_i \in \mathcal{C}$, we get a payoff of $p(S_i)$, but we must pay for all of the elements in $S_i$ to get this payoff.

Approaches: At first glance, this problem seems pretty similar to the (somewhat obscure) NP-hard minimum K-union problem (1), where our goal is to pick the $k$ sets whose union cover the fewest elements (in our problem, in the case of unit costs / payoffs, we would try to pick the $k$ elements that hit the fewest number of sets, and then include the rest of the $m-k$ in $X$, but the analogy does not quite work since there is no requirement that we choose $X$ to have at most $m-k$ elements).

Any help with characterizing this problem's complexity is of course much appreciated!

Example: I will put the cost/payoff next to each item, after a colon. Suppose $U$ is given by (along with costs) $\{e_1: 2, e_2: 2, e_3: 1\}$, and in our collection we have:
$$S_1 = \{e_1, e_2\} : 1$$
$$S_2 = \{e_2, e_3\} : 4$$

Then in this case we would pick $X = \{e_2, e_3\}$, for a total cost of 3 and a payoff of 4, for a net benefit of 1.

(1) Staal A. Vinterbo (2002). A Note on the Hardness of the k-Ambiguity Problem. DSG Technical Report 2002-006.

This is an instance of the standard network flow problem called "Project Selection", and hence can be solved efficiently (even in practice). See (what's currently) Section 24.6 of Jeff Erickson's lecture notes for a nice explanation. It's covered in most introductions to network flow in good undergraduate algorithms courses, so if you don't like Jeff E's notes, I'm sure you can find plenty of alternatives.

The general idea of project selection is that you have a collection of projects, each with a cost/benefit (positive or negative) and a collection of dependencies, and the goal is to find the set of projects that (1) satisfies dependencies, and (2) maximizes the benefit of all the selected projects.

For your case, you would have one project for each set $S_i$, and also one project for each $e_j$. Each $e_j$ project has no dependencies, and each $S_i$ will depend on the $e_j$ in $S_i$. The benefit of $S_i$ is its payoff, and the 'benefit' of each $e_j$ is the negative of its cost. You can see that reasonable ways of selecting projects correspond to all the ways of picking solutions to your problem, and the objective values are the same on either side of the correspondence.

I'll just add that you're really only using a special case of project selection, where there are "good" projects that only depend on "bad" projects that have no further dependencies. Project selection doesn't assume this structure, and can be solved on an arbitrary dependency graph. You might find this useful in your application where you've got multiple phases of computation.


Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism Given two graphs $G, H$ (each has $n$ vertices). We, split $G$ into subgraphs $G_1, G_2... G_x$ (total $x$ vertex set). Similarly,assume  $H$ has  subgraphs $H_1, H_2... H_x$ (total $x$ vertex set).

Consider, a permutation $\pi_k \in \beta_k$ where $H_k^{\pi_k}=G_k$ such that $P= \pi_1 \times \pi_2...\pi_x$ (i.e. $P$ is  the direct product of permutations $\pi_1, \pi_2 ..... \pi_x$) and $H^P=G$.

$\pi_k$ is a local isomorphism and $P$ is global isomorphism of $G,H$.

$G_k, \forall k$ is not an $Independent$ $ Set$ .

Here, $\beta_k (k\leq x \leq n/2)$ is a set of permutations  for each $H_k$. Let, $\beta$ is a number and $\beta_k$ has maximum $\beta$ permutations.

Question  If All $\beta_k$ are given, how many steps are required to construct $P$, i.e. what is the computational complexity of finding $P$?

Brute force leads to $\beta^x$.

Does there exist  a  $\beta^c$ algorithm where $c$ is a constant?

Edit:
1. Consider that  all $H_k$ are ordered according to $G_k$.

A "sifting technique"  might help !
$G_k$ has the same vertices of $H_k$.
$G_k$ has no disconnected component.

The computational complexity of of finding $P$ is polynomial in $\beta$.

We construct the generating set of automorphism group of $H$ using  $\beta_k$, for all $k$. As we know, constructing  generating set of automorphism group of  $H$ is a  GI complete problem [1]. So, we try to construct the generating set of $Aut(H)$ . The technique used in the paper [2]  by E. Luks can used here.

Notation:

From now on, $G, H$ are adjacency matrices of graphs $G, H$ respectively. $H_k, G_k$ are blocks or sub-matrices of matrix $H, G$ respectively. The adjacency matrix of graph $H_k \cup  H_e$ is $M_{(k,e)}$ where   $M_{(k,e)} =\left( \begin{array}{ccc} H_e & R_{k,e} \\ R_{k,e}^{T} & H_k\\ \end{array} \right) $,  where, $R_{k,e}$ is the non symmetric sub-matrix of adjacency matrix $H$.  Here, $R_{k,e}$ represents  edges  between $H_k,  H_e$.  Similarly,  $S_{k,e}$ represents  edges  between $G_k, G_e$.
$$H = \begin{bmatrix}
H_{(x)} & R_{(x, x-1)} & R_{(x,x-2)} & \dots & \dots & R_{(x,1)} \\
R_{(x,x-1)} & H_{(x-1)} & R_{(x-1,x-2)} & \dots & \dots & R_{(x-1,1)} \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\
R_{(x,1)} & R_{(x-1,1)} & R_{(x-2,1)} & \dots & \dots &H_{1} \end{bmatrix}$$

For simplicity, we assume $\beta \leq n^{3}$.

The outline of the algorithm to construct generating set:

At $1^{st}$ iteration -

Step 1. Construct all possible  direct product  $(\pi_1 \times  \pi_2)$ where $\pi_1 \in \beta_1$ and $ \pi_2 \in \beta_2$.

There are $| \beta_1 | \times | \beta_2|  <  n^{9}$ direct products (permutations).  All these permutations (direct products) form set $\gamma_1$. Each element of $\gamma_1$ is a permutation that acts on graph $H_1 \cup  H_2$.

Step 2. Construct/find -

$\alpha_1 =\{ \pi \in \gamma_1 |  (M_{(1,2)}^{\pi}= M_{(1,2)}) \land ( R_{1,2}^{\pi} = S_{1,2}) \land  (H_1^{\pi} = G_1) \land  (H_2^{\pi} = G_2) \}$

$\alpha_1$ is the set of automorphisms of matrix $M_{(1,2)}$.        $|\alpha_1| < n^{9}$.There are two possible cases-

Case 1:  If $|\alpha_1| =1$, then  for each $\pi_1 \in \beta_1$,  there is only one permutation
$\pi_2 \in \beta_2$. So, there could be maximum $n^{2}$ permutations in $\gamma_1$ but only one permutation could be included in $\alpha_1$.

Case 2: If $|\alpha_1| >1$,  we would be able to construct a generating set $\mathcal{S}_1$ of an automorphism group of $Aut(M_{(1,2)})$ Note, that if $\exists \pi_a \in Aut(H)$ such that it acts on   vertices of $H_1 \cup H_2$, then  $  \pi_a \in \langle \mathcal{S}_1 \rangle =Aut(M_{(1,2)})$. So, when we construct direct product of  $\mathcal{S}_1$ and another set,   $\pi_a$ can be found in the resulting generating set. See Theorem 7, on page 31 of [3].The theorem showed how to obtain the automorphism group of an arbitrary graph from the intersection of a specific  permutation group with a direct product of symmetric groups.

Step 3. Now, we construct the generating set  $\mathcal{S}_1$  from $\alpha_1$. This construction of generating set can be done in polynomial time (see [3], page 40, theorem 9). From  [4], we find that $|\mathcal{S}_1| \leq log(n!)$ .
 $\mathcal{S}_1$ is the  generating set  of automorphism of  $H_1 \cup H_2$ .

Step 4. We start $2^{nd}$ iteration, for $\beta_3, \mathcal{S}_1$ (instead of $\beta_2$), $ M_{(2,3)}$  where $M_{(2,3)} =\left( \begin{array}{ccc} H_3 & R_{2,3} \\ R_{2,3}^{T} & H_2 \\ \end{array} \right) $.  We find $\gamma_2, \alpha_2$ repeating  steps $1,2$ and construct $\mathcal{S}_2$ (repeating  step $3$)  which  is the  generating set  of automorphism of  graph $H_1 \cup H_2 \cup H_3$. Note that,                    $|\mathcal{S}_2|  \leq log(n!)$ .

Step  5. We keep repeating above  four   processes, until we find the set $\mathcal{S}_{(x-1)} $  which  is the  generating set  of automorphism of graph $H_1 \cup H_2 \cup H_3 \dots \cup H_x=H $. Note that, $|\mathcal{S}_{(x-1)}|\leq  log(n!)$, since $ \langle \mathcal{S}_{(x-1)} \rangle= Aut(H) \leq S_n$.

Detecting Isomorphism:  We repeat the process of construction of $\mathcal{S}_{(x-1)}$ for graph $G$ and obtain set $\mathcal{R}_{(x-1)}$. I assumed, that  the oracle that gave $\beta_k$, would provide permutation sets for $G$ also.

Once we generate  generating sets of $G, H$, we can decide isomorphism betwen them [1].

References:

[1]Mathon, Rudolf. ,A note on the graph isomorphism counting problem, Inform. Process. Lett. 8 (1979), no. 3, 131–132.

[2] Luks , Eugene M. , Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences, Volume 25, Issue 1, (1982), Pages 42-65.

[3]Hoffmann, Christoph M. ,Group-Theoretic Algorithms and Graph Isomorphism.

[4] Miller, Gary L.  ,On the $n^{\log_2(n)}$ Isomorphism Technique.

Feel free to down-vote, but please leave a comment if you have anything  technical to say, Thanks for your patience.


What is a 'free model'? I was reading this paper on effect handlers and got hung up on the phrase 'free model'.

In context:

      [...] From an algebraic point of view, the $x_e$ provide a model for the theory of exceptions on $X + E$, interpreting each operation $raise_e$ by $x_e$. If we write $X + E$ for the free model and $\overline{X + E}$ for the new model on the same carrier set, we see from the above two equations that [...]

I want to reach for something being freely generated from something else, but I'm not sure what (e.g. right after the comment about $x_e$ providing some other model, where're the parts of the 'free model' coming from?).

Consider a set $E$. The theory of $E$-exceptions is an algebraic theory given by:

for every $e \in E$ a nullary operation symbol $\mathsf{raise}_e$
no equations.

Given a set $X$, we may consider the free algebra $A$ for the theory of $E$-exceptions, with generators from $X$. The algebra $A$ contains everything that we can generate from the generators and the operation symbols. Since our operation symbols are nullary (do not take any arguments), $A$ will contain precisely the generators $X$ and, for each $e \in E$, the operation symbol $\mathsf{raise}_e$. (There are no equations, so we need not quotient at all.) It is not surprising that we would write "$X + E$" for $A$.

In general, an algebra for the theory of $E$-exceptions is given by:

a carrier set $C$
for every $e \in E$, an element $r_e \in C$ which interprets the nullary operation $\mathsf{raise}_e$.

A particulary strange way to create an algebra is to take
$$C = X + E$$
and for each $e \in E$ an element $x_e \in C$. This seems strange only untilwe notice that such an algebra is precisely the same thing as an exception handler. Think of $C$ as the set of "computations" that may either return a "final result" from $X$, or raise an exception from $E$. An exception handler takes an element $c \in C$ and explains how to replace each exception $\mathsf{raise}_e$ with another computation $x_e \in C$ (note: an exception handler may re-raise exceptions, which is why $x_e \in C$ instead of just $x_e \in X$).

$\newcommand{\raise}[1]{\mathsf{raise}_{#1}}$

Supplemental: Perhaps a concrete example will help. A model is given by a set $C$ and a mapping of the constant symbols $\raise{e}$ to elements of $C$.

Let us take $E = \{a,b\}$ and $X = \{u, v, w\}$. Then the free model is given by the carrier
$$X + E = \{u, v, w, \raise{a}, \raise{b}\}$$
together with the mapping
$$\raise{a} \mapsto \raise{a}, \quad \raise{b} \mapsto \raise{b}.$$

The model $\overline{X + E}$ is not fixed, it depends on the mapping $x : E \to X + E$. For example, if we take $x_a = u$ and $x_b = \raise{a}$ then we get the model $\overline{X + E}$ whose carrier is $X + E$ and
$$\raise{a} \mapsto u, \quad \raise{b} \mapsto \raise{a}.$$
Another possibility for $\overline{X + E}$ is to take $x(a) = \raise{b}$ and $(b) = \raise{a}$. This will not be the same as the free model because it exchanges the meaning of $\raise{a}$ and $\raise{b}$. If we take $x(a) = \raise{a}$ and $x(b) = \raise{b}$ then $\overline{X + E}$ is equal to the free model.


Properties of Random Directed Graphs with Fixed Out-Degree I am interested in properties of random directed graphs with fixed out-degree $d$.  I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r.

  Question: Is anything known about the stationary
  distribution and mixing times of random
  walks on these random graphs (for various
  values of $d$)?

I am particularly interested in the case where $d = 2$, which corresponds to a model of random automata over a Boolean alphabet.  (Yes, I realize these graphs are often not connected, but what happens in a given component?)  I am happy with partial results and results about other properties of these graphs.

It seems most of the literature on random graphs focuses on the Erdős–Rényi model, which has very different properties than the model I am thinking about.

In the undirected case random $d$-regular graphs are expanders with high probability (not for $d=2$, but I think $d \ge 3$ suffices), which implies that the mixing time of random walks is $O(\log n)$.  I don't remember enough about these proofs to know whether everything goes through in the directed case (certainly some properties are different: the uniform distribution is no longer stationary), but it may be worth looking into.  Good references for expander graphs are Expander Graphs and their Applications by Hoory, Linial, and Wigderson and Pseudorandomness by Vadhan.


Constructing Orbits of the Automorphism of a Graph Group in Bliss I'm using the Bliss package for graph isomorphism and canonization. The program is working great for the type of graphs I'm interested in. In one of the applications I need to compute the orbits of the automorphism group of the graph. What is the best way to do that in Bliss?

PS: I understand that some people may think that this question is off-topic because it asks about a specific software. But since bliss is a highly specialized software that is used mostly by TCS people (at least consciously) I think that this site is the best one to ask this question. I also think that this may be useful for other researchers interested in graph isomorphism.

If Bliss is not mandatory, you can try Sage: https://www.sagemath.org/
I used it successfully a few times.

This video:  https://www.youtube.com/watch?v=X4_4Bqj6EdA&t=579s
Gives a usage example.


Static structure of program Firstly, I admit that my question is just something very blurred but I hope someone please give me some documents to read.

The execution of a program $P$ can be considered as a sequence of state transitions $State \to State $ (this sequence should be finite if the program halts). By that way we get execution traces of program. Now, we may note that these traces (denoted as a set $T$) are generated by a static structure, that is the syntax of $P$. So we receive the first constraint: the set $T$ can not be arbitrary, instead $T$ must be result of some static rewriting rules applied on the static syntax of program.

Continue this way, if $P$ is a self-modifying program, roughly speaking $P$ can firstly generate other programs $Q_{1}, Q_{2}, \dotsc$, and these programs, at their turns, will generate other traces $T_{1},T_{2}, \dotsc$, so $T = T_{1} \cup T_{2} \cup \dotsc$. And we receive the second constraint: the set $T$ must be result of some static rewriting rules applying on some static rewriting rules applying on the static syntax of programs.

We can continue this construction to some level (may be there exists a limit ?). But a similar view I get is in the high order category theory where there exist morphisms between morphisms, and morphisms between morphisms between morphisms, etc.

So my question is: Do exist some reseaches on that or my thinking is just a stupid nonsense thing ?

There are many ways to define the semantics of a program. If we consider operational semantics, a simple imperative program defines a relation $R \subseteq \mathit{State}\times \mathit{State}$. I'm using "simple imperative" here to mean something that does not modify itself. There is a standard way to view $R$ as a function $\wp(\mathit{State}) \to \wp(\mathit{State})$ that maps a set of states to their successors in $R$.

If a program can modify itself you can consider a pair $\wp(\mathit{State})\times(\wp(\mathit{State})\to \wp(\mathit{State}))$, in which each element $(S,F)$ represents a current set of states in $S$ and a transformer $F$ representing the behaviour of the program. A program of the form you describe can modify either $S$ or $F$.

You may find the following paper useful.

  Multi-Stage Programs are Generalized Arrows, Adam Megacz.

If you are interested in a formalisation oriented towards automatic analysis of such programs, the following paper may interest you.

  Modelling Metamorphism by Abstract Interpretation, Mila Dalla Preda, Roberto Giacobazzi, Saumya K. Debray, Kevin Coogan, Gregg M. Townsend


Reduction from independent set in hypergraphs to independent set in graphs Let me introduce my notations.

IS-H :

Input : an hypergraph $G=(V,H)$, an integer $k$
Question : is there a (weak) independent set of size $k$, i.e. a set $S \subseteq V$ such that $|S| \ge k$ and for all $h\in H$, $h \nsubseteq S$ ?

I denote IS the same problems in graphs.

I know that $IS-H \le_{karp} IS$ as $IS-H \in NP$ and $IS$ is $NP-hard$, but I need an explicit reduction to compute an explicit bound on the size of the obtained instance of $IS$. I have such a reduction in mind but I would prefer to cite an existing one (any "natural" reduction is ok for me, as I don't need to tune the constant in the size of the obtained instance).

Do you know if such a reduction is made explicit somewhere ?
Thank you in advance

From the standard machinery, we can quickly deduce that there is a quasilinear-time reduction from $\textrm{IS-H}$ to $\textrm{IS}$. (But see below if quasilinear isn't good enough for you.)

Recall that $\textrm{3-SAT}$ is hard for $\mathsf{NTIME}[t(n)]$ under reductions that run in time $\tilde{O}(t(n))$, and in particular the resulting 3-CNF formula has size $\tilde{O}(t(n))$.

It's fairly straightforward to check that $\textrm{IS-H}$ can be solved in $\mathsf{NTIME}[\tilde{O}(n)]$ in any reasonable model of computation. (The naive algorithm has some dependence on $n \cdot k$, but this can be reduced with some sorting and binary search.) It follows that there is a reduction from $\textrm{IS-H}$ to $\textrm{3-SAT}$ which has only quasilinear blowup.

Additionally, the usual reduction from $\textrm{3-SAT}$ to $\textrm{IS}$, where 2-cliques are made for each variable and 3-cliques are made for each clause and some edges are added between clause gadgets and the clause's constituent variables' gadgets, has only linear blowup (a 3-CNF on $n$ variables and $m$ clauses gets mapped to an $\textrm{IS}$ instance with $2n+3m$ vertices and $2n+6m$ edges.

Composing these two reductions gives an overall quasilinear-blowup reduction from $\textrm{IS-H}$ to $\textrm{IS}$.

If a quasilinear-blowup reduction isn't good enough for you, we can work a little harder to get a linear-blowup reduction.

The idea is to replace the reduction from $\textrm{IS-H}$ to $\textrm{3-SAT}$ by a more efficient reduction. To do this, we'll reduce $\textrm{IS-H}$ to a version of $\textrm{Circuit-SAT}$ which takes as input circuits in which all gates have fan-in 2. This reduction will have linear blowup. From here, we can use the standard reduction from fan-in 2 $\textrm{Circuit-SAT}$ to $\textrm{3-SAT}$ (using the Tseitin transformation) which has only linear blowup. Composing these with the linear-blowup reduction from $\textrm{3-SAT}$ to $\textrm{IS}$ then completes a linear-blowup reduction from $\textrm{IS-H}$ to $\textrm{IS}$.

The reduction from $\textrm{IS-H}$ to $\textrm{Circuit-SAT}$ proceeds as follows. Let the input hypergraph be $(V,E)$, where we view $E \subseteq 2^V$ which doesn't contain the empty set. Let the input threshold be $k$.

We make variables $x_v$ for every vertex $v \in V$. We think of assignments to the variables as corresponding to subsets $S$ of the variables, where $v \in S$ if and only if $x_v \gets \texttt{True}$ in the assignment.
For each edge $e$, we construct a fan-in 2 formula computing $\bigvee_{v\in e} \overline{x_v}$, to rule out sets $S$ which are not independent sets.
Finally, we just need to translate the constraint $|S| \ge k$. To do this, we just need to give a linear-size, fan-in 2 circuit $\phi$ which takes as input $n$ bits and decides whether the number of bits set to $\texttt{True}$ is at least $k$. This can be done efficiently; see e.g. the answers here, but briefly the idea is just to efficiently compute the binary representation of the number of bits set to $\texttt{True}$, whence any symmetric function can be computed by a circuit of size linear in $n$.

It's easy to check that this is indeed a reduction from $\textrm{IS-H}$ to $\textrm{Circuit-SAT}$ in which the output has fan-in 2 gates and size only linear in the $\textrm{IS-H}$ instance. Moreover, the reduction results in a circuit of size $O(|V| + |E|)$ (where $|E|$ denotes $\sum_{e\in E}|e|$), and so we are done.


Finding a special cut-set in an weighted undirected graph I encountered this sub-problem while working on a problem about robustness of networks against link failures. Suppose we have an undirected graph $G=(V,E)$ such that edges in $E$ have weights taking values from $\{-1,+1\}$. We define the cut-set for $S\subseteq V$ as the set of edges connecting nodes in $S$ to those in $V\backslash S$ (the standard definition), and the cut value of the cut-set as the sum of weights of the edges in it.

It is known that one can find the cut-set with least cut value (min-cut) in polynomial time (in terms of |V|, |E|). I am interested in finding the cut-set whose cut value is the least and greater than zero (i.e., number of edges of weight +1 exceeds the number of edges of weight -1 in the cut-set) - does there exist a polynomial-time algorithm for generating such a cut-set?

This problem is NP-complete.

Here's a simple reduction from MAXCUT:

Given an input graph $G$, we create a new graph $G'=G\cup K_{n^2}$ (i.w. add a separated clique over $n^2$ vertices).

We can now set the weight to be $-1$ for the original graph edges, and $1$ for the edges of the clique.

Claim:
If $G$ has a max cut $(S,\bar S  = V\setminus S)$ such that $|E\cap (S\times \bar S)| = k$, then $G'$ has a minimal "special cut-set" whose value is $|n^2-k-1|$.

Proof:
Since the special cut set's value is required to be positive, $S\cap K_{n^2}$ is neither empty or the entire clique. Since the contribution from the negatively weighted edges of $G$ less than $n^2-1$, we can conclude that $|S\cap K_{n^2}|\in \{1,n-1\}$, and it's contribution to the special cut value is $n^2-1$.

Now the set intersection with $G$ has to be the max cut of $G$, as all of the weights are negative, which contributes another $k$ to the special cut value.


Current research topics in tree automata What are current research topics connected with tree automata?
I'm particularly interested with connection between automatas, logics and databases.
Kind regards,
XYZ

Here is a short list of authors that work on the connections between tree automata, logic and databases. For each author, I will just give one paper, but many more can be found on the respective web pages of these authors.

[1] Luc Segoufin

FO2(+1,<.~) on data trees, data tree automata and branching vector addition systems

[2] Nicole Schweikardt

A note on monadic datalog on unranked trees

[3] Mikołaj Bojańczyk

Automata for Data Words and Data Trees.

You may also check Georg Gottlob's work


Is it a rule that discrete problems are NP-hard and continuous problems are not? In my computer science education, I increasingly notice that most discrete problems are NP-complete (at least), whereas optimizing continuous problems is almost always easily achievable, usually through gradient techniques. Are there exceptions to this?

An example that I love is the problem where, given distinct $a_1, a_2, \ldots, a_n \in \mathbb{N}$, decide if: $$\int_{-\pi}^{\pi} \cos(a_1 z) \cos(a_2 z) \ldots \cos(a_n z) \, dz \ne 0$$

This at first seems like a continuous problem to evaluate this integral, however it is easy to show that this integral is not zero iff there exists a balanced partition of the set $\{a_1, \ldots, a_n\}$, so this integral problem is actually NP-complete.

Of course, I encourage playing around with some numerical tools to convince yourself that most (if not all) numerical tricks to evaluate this integral are doomed to failure once $n$ gets large enough.


Expressing a set of 0-1 strings by Extended Formulation Extended Formulation of a polytope $P \subseteq \mathbb{R}$ is a system of linear constraints which satisfies the following condition:
$x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax + By \geq d$
A convex set of $n$-points $x_{1},...,x_{n}$ in $\mathbb{R}^{d}$ is defined as $\mbox{conv}(\{x_{1},...,x_{n}\})=\{y\in \mathbb{R}^{n}  |y=c_{1}x_{1}+c_{2}x_{2}+\cdots +c_{n}x_{n}, c_{1}+c_{2}+\cdots +c_{n}=1   \}$
Question:
Is the following statement true ?
Statement:
For every $P\subseteq  \{0,1\}^{n}$, If we construct a system of linear constraints $ Ax + By \geq d,x\in \mathbb{R}^{n},y\in \mathbb{R}^{d}$ such that
$x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax + By \geq d$
,then the system of linear constraints $ Ax + By \geq d,x\in \mathbb{R}^{n},y\in \mathbb{R}^{d}$ is a extended formulation of $\mbox{conv}  (P)$  ?
I am not sure about expressing a set of boolean strings by linear constraints.

An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a linear system

\begin{equation}
\label{equation:ExtForm}
Ex + Fy  = g, y\geq 0
\end{equation}

in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real
matrices with $d,r$ columns respectively and $g$ is a column vector
such that $x\in P$ if and only if there exists $y$ such that the equation above holds.

Thus the formulation you described in your question seems to be incorrect.
In special the right side of the inequality is expected to be a vector and not
a number.

I believe that the way in which you represent strings as extremal points of a
polytope is somewhat arbitrary. But a sort of canonical way is to represent
a string $x$ over $\{0,1\}^n$ by a vector $v\in \mathbb{R}^n$  such that
$v_i=x_i$.

However these extremal points are usually meant to represent the solutions to
a given combinatorial problem. For instance, in the cut polytope is the convex hull
the characteristic vectors of all cuts in the complete graph $K_n=(V_n,E_n)$:

\begin{equation}
\label{equation:CutPolytope}
CUT(n) = conv\{ \chi^{\delta(X)\in \mathbb{R}^{E_n}} | X\subseteq V_n\}
\end{equation}

where $\delta(X)$ is the set of edges from $X$ to its complement $\overline{X}$.
Similarly, the stable set polytope is the convex hull of the vectors corresponding
to the characteristic functions of all stable sets of $G$.

\begin{equation}
\label{equation:StableSet}
STAB(G) = conv\{\chi^S \in \mathbb{R}^V | S \mbox{ is a stable set of $G$}\}
\end{equation}

The TSP polytope $TSP(n)$ is the convex hull of all vectors corresponding to the characteristic functions of sets of edges representing the tours in $K_n$:

\begin{equation}
\label{equation:TSP}
TSP(n) = conv\{\chi^F \in \mathbb{R}^{E_n} | F\subseteq E_n \mbox{ is a tour of } K_n\}
\end{equation}

The interest on extended formulations stems from the fact that some polytopes,
such as the Permutahedron,which have an exponential number of facets admit extended formulations with a polynomial number of inequalities. However, recently Fiorini, Massar, Pokutta, Tiwary and De Wolf proved that any extended formulation of any of the three polytopes described above require an exponential number of innequalities.


Results in computer science via the Stepanov method I recently attended a Workshop on Pseudorandomness in Chennai Mathematical Institute on Pseudorandomness. Venkat Guruswami made the following beautiful statement in passing during his talk (on coding theory):

  It is remarkable how much one can prove using the simple fact that a
  degree $d$ polynomial over a field can have at most $d$ roots.

I believe this is also called the Stepanov Method (in those applications, typically roots occur with large multiplicity as well). One place where I've seen this is in a paper on square root bounds for the smallest non-residue by Michael Forbes, Neeraj Kayal, Rajat Mittal and Chandan Saha .

This principal was highlighted in the workshop with the unique and list decoding of Reed-Solomon code (which can be found in this course, for example) in Venkat's talk. In Neeraj Kayal's talk, he gave two other examples -- the proofs of the Finite Field Kakeya Conjecture and the Joints Conjecture (both of which can be found in this  very nice survey by Zeev Dvir). Other examples that I can think of is Dana Moshkovitz's proof of the Schwartz-Zippel Lemma, and another favourite of mine is the AKS Primality test which (if I'm allowed to make a stretch) uses only this fact essentially.

I was wondering if there are other examples of elegant results using (essentially) just this simple fact.

This post is closely related to the earlier question "Polynomial methods for complexity results" but that was for a more general 'polynomial method'.

This may be too obvious, but the correctness proof of the Schwartz-Zippel randomized algorithm for polynomial identity testing uses essentially just this fact, plus induction.


Understanding the Proof of Strong Normalization of the Calculus of Constructions I have difficulties in understanding the proof of strong normalization for the calculus of constructions. I try to follow the proof in the paper of Herman Geuvers "A short and flexible proof of Strong Normalization for the Calculus of Constructions".

I can follow the main line of reasoning well. Geuvers constructs for each type $T$ an interpretation $[\![T]\!]_\xi$ based on some evaluation of type variables $\xi(\alpha)$. And then he constructs some term interpretation $(\!|M|\!)_\rho$ based on some evaluation of term variables $\rho(x)$ and proves that for valid evaluations the assertion $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ for all $\Gamma\vdash M:T$ holds.

My problem: For easy types (like system F types) the type interpretation $[\![T]\!]_\xi$ is really a set of terms, so the assertion $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ makes sense. But for more complex types the interpretation $[\![T]\!]_\xi$ is not a set of terms but a set of functions of some appropriate function space. I think, I almost understand the construction of the function spaces, however it cannot assign any meaning to $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ for the more complex types $T$.

Can anybody explain or give links to some more understandable presentations of the proof?

Edit: Let me try to make the question clearer. A context $\Gamma$ has declarations for type variables $\alpha:A$ and object variables. A type valuation is valid, if for all $(\alpha:A) \in \Gamma$ with $\Gamma\vdash A:\square$ then $\xi(\alpha) \in \nu(A)$ is valid. But $\nu(A)$ can be an element of $(SAT)^*$ and not only $SAT$. Therefore no valid term evaluation can be defined for $\rho(\alpha)$. $\rho(\alpha)$ must be a term and not some function of a function space.

Edit 2: Example which does not work

Let's make the following valid derivation:
$$
\begin{array}{llll}
[] &\vdash  & *:\square &\text{axiom}
\\
[\alpha:*] &\vdash& \alpha:* &\text{variable introduction}
\\
[\alpha:*] &\vdash& *:\square &\text{weaken}
\\
[] &\vdash & (\Pi \alpha:*.*):\square   &\text{product formation}
\\
[\beta:\Pi \alpha:*.*] &\vdash& \beta:(\Pi \alpha:*.*) &\text{variable introduction}
\end{array}
$$

In the last context a valid type evaluation must satisfy $\xi(\beta) \in \nu(\Pi \alpha:*.*) = \{f| f:\text{SAT} \to \text{SAT}\}$. For this type evaluation there is no valid term evaluation.

Unfortunately, I'm not sure there are more beginner friendly resources than Geuvers' account. You might try this note from Chris Casinghino which gives an account of several proofs in excruciating detail.

I'm not sure I understand the gist of your confusion, but I think one important thing to note, is the following lemma (Corollary 5.2.14), proven in the classic Barendregt text:

$$\Gamma \vdash M:T\ \Rightarrow\ \Gamma \vdash T:*\mbox{ or }\square $$

This means that while $[\![T]\!]_\xi$ can be some complicated function, if $\Gamma \vdash M:T$ holds, then $[\![T]\!]_\xi$ has to be a set of terms.

This is insinuated in the outline (section 3.1), where $(\!|t|\!)_\sigma\in[\![T]\!]_\xi$ only if $\Gamma \vdash t:T :*$, which lines up with our expectation, which is that the interpretation of a type must be a set of terms, i.e. ${\cal V}(*)\subseteq{\cal P}(\mathrm{Term})$ (indeed, ${\cal V}(*)=\mathrm{SAT}$!)

It's a common situation in type theory that even though we're only interested in the "base kind" (here $*$), we still have to define semantics for things at higher kinds (hence the need to introduce $\mathrm{SAT}^*$). Things then work out at the end, because only kind which inhabited by types is $*$ (and $\square$, but that's not really important).


Best known deterministic time complexity lower bound for a natural problem in NP This answer to Major unsolved problems in theoretical computer science? question states that it is open if a particular problem in NP requires $\Omega(n^2)$ time.

Looking at the comments under answer made me wonder:

  Aside from padding and similar tricks,
  what is the best known time complexity lower bound on a deterministic RAM machine
  (or multiple-tape deterministic Turing machine)
  for an interesting problem in NP (which is stated in a natural way)?

  Is there any natural problem in NP which is known to be unsolvable in quadratic deterministic time on a reasonable machine model?

Essentially, what I am looking for is an example that rules out the following claim:

  any natural NP problem can be solved in $O(n^2)$ time.

Do we know any NP problem similar to those in Karp's 1972 paper or Garey and Johnson 1979 that requires $\Omega(n^2)$ deterministic time?
Or is it possible to the best of our knowledge that all interesting natural NP problems can be solved in $O(n^2)$ deterministic time?

Edit

Clarification to remove any confusion resulting from the mismatch between lower bound and not an upper bound:
I am looking for a problem which we know we cannot solve in $o(n^2)$.
If a problem satisfies the stronger requirement that
$\Omega(n^2)$ or $\omega(n^2)$ time is needed (for all large enough inputs) then better,
but infinitely often will do.

Adachi, Iwata, and Kasai in a 1984 JACM paper show by reduction that the Cat and $k$-Mice game has an $n^{\Omega(k)}$ time lower bound.   The problem is in P for each $k$.   The problem is played on a directed graph.    The moves consist of the cat and then one of the $k$ mice alternating steps.  The mice win if they can land on a designated cheese node before the cat lands on them.   The question is whether the cat has a forced win.   It is actually a complete problem so the lower bound is really based on the diagonalization that gives the time hierarchy.

Grandjean showed that the Pippenger, Paul, Szemeredi, and Trotter time lower bound applies to a SAT encoding, though the result of Santhanam may subsume it.

In addition to the time-space tradeoff lower bounds for SAT mentioned in other comments, there is a body of work on branching program lower bounds which imply time-space tradeoffs for Turing machines.    For problems like FFT, sorting or computing universal hash functions there are quadratic tradeoff lower bounds of Borodin-Cook, Abrahamson, Mansour-Nisan-Tiwari but these are for functions with many outputs.   For decision problems in P, there are time-space tradeoff lower bounds that apply for time bounds that are $O(n \log n)$ but these are weaker than are known for SAT.


When is it hard to invert a sparse matrix? Are cases where numeric inversion of a sparse matrix is known to be harder than sparse matrix multiplication?
In practice, sparse matrix inversion is done with methods like Jacobi or Gauss-Seidel, which  give a good estimate after a small number of sparse matrix multiplications, when they converge.
However such methods fail to converge when off-diagonal entries are large compared to diagonal entries. I'm curious if this is a limitation of those methods, or reflects a fundamental difficulty of the task.

Jacobi or Gauss-Seidel are not really state of the art for solving systems of linear equations. It is more done by preconditioned conjugated gradient (for symmetric positive semi-definite matrices) and preconditioned (F)GMRES (or other Krylov subspace methods) for arbitrary matrices.
The crucial part here is the preconditioner. There was recently (=21th century) huge progress with very efficient preconditioners for Laplacian systems. In Hardness Results for Structured Linear Systems by Rasmus Kyng and Peng Zhang, it is shown

that if the nearly-linear time solvers for Laplacian matrices and their generalizations can be extended to solve just slightly larger families of linear systems, then they can be used to quickly solve all systems of linear equations over the reals.

They go on to say:

This result can be viewed either positively or negatively: either we will develop nearly-linear time algorithms for solving all systems of linear equations over the reals, or progress on the families we can solve in nearly-linear time will soon halt.

But even beyond such deep theory, one can say something about the computational cost of a preconditioner and its efficiency. A matrix is hard to solve, if its condition number is big. The task of the preconditioner is to reduce the condition number, by approximately inverting the matrix. The (asymptotic) computational cost (vs efficiency) can estimated based on separators of the sparse matrix. For example, to separate a N x N x N grid in 3D, you need a separator of size O(N^2). If you would not approximate the system on the separator, you would get a full matrix of size(N^2), i.e. N^4 non-zero entries. So you need to approximate the clique graph on the separator with a sparse (directed) graph, probably an extender graph. One fast preconditioner algorithm for Laplacian systems approximates the clique (among the neighbors of the eliminated node, which has to be added to the graph) in each elimination step by a tree. This is good enough to keep the computational cost under control. The efficiency of this preconditioner in reducing the condition number is also often extremely good in practice, but proving this theoretically would still be a nice achievement.
A recent result on fast solving sparse linear systems replaced the Krylov subspace methods mentioned above by "an efficient, randomized implementation of the block Krylov method": Solving Sparse Linear Systems Faster than Matrix Multiplication by Richard Peng and Santosh Vempala. Even so the paper title says "solving ... faster than matrix multiplication," this does not answer the question asked here, because the paper means dense matrix multiplication, but the question here is about sparse matrix multiplication.


Relative error estimation of a special type of GapP function Consider the functions included in the complexity class GapP.
We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly finding the sign of $f(x)$ (for a worst case function $f$) is #P-hard --- if we can find the sign, we can use a padding argument, coupled with binary search, to exactly find the value of the function. (For reference, see this.)
Now, consider another class of functions: let's name the class SpecialGap. A function $g(x)$ belongs to SpecialGap if and only if there exists a GapP function $f(x)$ such that $g(x) = f(x)^{2}$.
Note some properties of SpecialGap. In the worst case, computing the sign of a function in SpecialGap is easy --- it is always positive, as it is the square of a function. In the worst case, exactly computing a function from SpecialGap is #P-hard --- noting that #P functions are a subset of GapP functions, if we want to exactly estimate the value of a #P function, we use the procedure we have for finding the exact value of a SpecialGap function to find the exact value of the square of our desired #P function, and then we just take the square root to get the exact value of our #P function. Note that exactly estimating the value of a #P function is #P-hard.
Is multiplicatively estimating the value of a worst-case function, to inverse polynomial error, from SpecialGap also #P-hard?

Here's an attempt at a proof.
Consider a procedure to multiplicatively estimate (upto inverse polynomial relative error) the value of a SpecialGap function $g(x)$, where $g(x) = f(x)^{2}$, for a GapP function $f(x)$. Let the estimate be $\tilde g(x)$, where
\begin{equation}
\left(1 - \frac{1}{p}\right)f(x)^{2} \leq \tilde g(x) \leq \left(1 + \frac{1}{p}\right)f(x)^{2},
\end{equation}
for some polynomially bounded function $p$. Taking the square root, we have
\begin{equation}
\left(1 - \frac{1}{2p}\right)|f(x)| \leq \sqrt{\tilde g(x)} \leq \left(1 + \frac{1}{2p}\right)|f(x)|,
\end{equation}
which is an inverse polynomial multiplicative error estimate to $|f(x)|$.
The proof now reduces to proving that for a function $f(x)$ belonging to GapP, in the worst case, it is #P-hard to have an inverse polynomial multiplicative error estimate to $|f(x)|$. I didn't have any idea on how to prove this. For one, since $|f(x)|$ is always positive, making use of a procedure to find the sign of $|f(x)|$, and then using binary search and padding, fails.

This is #P-hard, already for an arbitrary fixed constant approximation factor. As you noted, it allows you to approximate $|f(x)|$ for any GapP-function $f$, and therefore if $f$ is any #P (or GapP) function, it allows you to approximate $|f(x)-y|$ for a given $y$. With this, you can still compute $f(x)$ by a form of binary search.
Specifically, fix a constant $k\ge\gamma^2+1$, where $\gamma>1$ is the approximation factor. Starting with an initial estimate $0\le f(x)\le 2^{n^c}$, if you already have $a_0<a_1$ such that $a_0\le f(x)\le a_1$, you compute $a'_0\le a'_1$ such that $a'_0\le f(x)\le a'_1$ and $a'_1-a'_0\le\lfloor(1-\frac1k)(a'_1-a'_0)\rfloor$ by computing the approximations $d_0,d_1$ such that
$$\gamma^{-1}d_i\le|f(x)-a_i|\le\gamma d_i,$$
and putting
$$[a'_0,a'_1]=\begin{cases}\bigl[a_0,a_1-\lceil\frac1k(a_1-a_0)\rceil\bigr]&d_0\le d_1,\\{}\bigl[a_0+\lceil\frac1k(a_1-a_0)\rceil,a_1\bigr]&\text{otherwise.}\end{cases}$$
To see that this is correct: if, for example, $d_0\le d_1$, then
$$f(x)-a_0\le\gamma^2(a_1-f(x)),$$
hence
$$f(x)\le\frac{a_0+\gamma^2a_1}{\gamma^2+1}=a_1-\frac{a_1-a_0}{\gamma^2+1}\le a_1-\frac{a_1-a_0}k.$$
The case $d_1\ge d_0$ is symmetric.


Toy examples for barriers to $P \ne NP$ Are there any toy examples that provide 'essential' insights into understanding the three known barriers to $P = NP$ problem - relativization, natural proofs and algebrization?

Let me give a toy example of the relativization barrier. The canonical example is the time hierarchy theorem that ${\bf TIME}[t(n)] \subsetneq {\bf TIME}[t(n)^2]$. The proof (by diagonalization) is only a little more involved than the proof that the halting problem is undecidable: we define an algorithm $A(x)$ which simulates the $x$th algorithm $A_x$ on input $x$ directly step-for-step for $t(|x|)$ steps, then outputs the opposite value. Then we argue that $A$ can be implemented to run in $t(|x|)^2$ time.

The argument works equally well if we equip all algorithms with access to an arbitrary oracle set $O$, which we assume we can ask membership queries to, in one step of computation. A step-for-step simulation of $A_x^O$ can also be carried out by $A$, as long as $A$ has access to the oracle $O$ too. In notation, we have ${\bf TIME}^O[t(n)] \subsetneq {\bf TIME}^O[t(n)^2]$ for all oracles $O$. In other words, the time hierarchy relativizes.

We can define oracles for nondeterministic machines in a natural way, so it makes sense to define classes $P^O$ and $NP^O$ with respect to oracles. But there are oracles $O$ and $O'$ relative to which $P^O = NP^O$ and $P^{O'} \neq NP^{O'}$, so this kind of direct simulation argument in the time hierarchy theorem won't work for resolving $P$ versus $NP$. Relativizing arguments are powerful in that they are widely applicable and have led to many great insights; but this same power makes them "weak" with respect to questions like $P$ versus $NP$.

The above is, of course, a toy example -- there are many other more complicated examples of arguments in complexity which still relativize (i.e., hold up when arbitrary oracles are introduced).


Numerically stable fast convolution algorithm? Suppose you have two vectors of real numbers $\langle a_1, \dots, a_n \rangle, \langle b_1, \dots, b_n \rangle$, with $a_i, b_i \geq 0$, and wish to compute the convolution
$$
c_i = \sum_{j \leq i} a_j b_{i-j}
$$

There is an obvious algorithm to compute this in time $O(n^2)$. This obvious algorithm basically involves a sum of many positive summands, so there is no numerical cancellation. Hence the obvious algorithm is numerically stable.

The other obvious algorithm is to use a Fast Fourier transform to compute $\hat a, \hat b$, obtain $\hat c = \hat a \hat b$, and then use an inverse transform to obtain $c$. This algorithm is much faster, like $O(n \log n)$ time. Unfortunately, the Fourier transforms require adding many terms with different complex phases, so there is catastrophic cancellation. So this algorithm is numerically unstable.

Is there any algorithm which is both fast (near-linear time) and numerically stable?

There is the number theoretic transform where all calculations are done using integers which should completely get round any concerns about numerical stability, at the possible expense of some speed (see e.g. https://ccrma.stanford.edu/~jos/st/Number_Theoretic_Transform.html).  However this will only work for you if your numbers are rational and can be converted to integer representation easily.

There is also a whole range of asymptotically slower algorithms known as Toom-Cook multiplication http://en.wikipedia.org/wiki/Toom-Cook_multiplication. However, I am not sure it is true that multiplication via FFT calculations is necessarily numerically unstable. Do you have a reference for this claim?


Polynomial-time distinguishability threshold of planted clique I have a basic question regarding the best known polynomial-time "distinguishing advantage" for the planted clique problem. By this, I'm referring to the problem of distinguishing the distribution $G(n,\frac{1}{2})$ of Erdos Renyi Random graphs from $G_k(n,\frac{1}{2})$ -- the distribution of graphs formed by planting a clique of size $k$ in $G(n,\frac{1}{2})$. This problem (as well as its natural bipartite variant) is conjectured hard for $k=n^{\frac{1}{2} - \delta}$ when $\delta >0$ is an absolute constant. In this post, you can think of $k=n^{\frac{1}{4}}$.

It is often assumed as a hardness assumption that no polynomial time algorithm can distinguish $G(n,\frac{1}{2})$ from $G_k(n,\frac{1}{2})$ with "non-negligible" advantage. Formally, this means that for any "non-negligible" advantage $\epsilon>0$, there is no polynomial time algorithm $f$ from graphs to $\{0,1\}$ such that $|\Pr[ f(G)=1 ] - \Pr[f(G_k)=1] | > \epsilon$ for $G \sim G(n,\frac{1}{2})$ and $G_k \sim G_k(n,\frac{1}{2})$.

In applications of this hardness assumption which I have seen, "non-negligible" is often taken to mean an absolute constant. In other words, it is believed that no polynomial-time algorithm can distinguish between the two distributions with constant advantage. My question is whether this extends to sub-constant $\epsilon$ which are not too small? i.e., is it believed hard to distinguish the two distributions with advantage, say, $\epsilon = \frac{1}{n}$ or $\epsilon = \frac{1}{\sqrt{n}}$ ? Clearly, there is some advantage $\epsilon$ more than exponentially small in $n$ but less than a constant where this problem crosses from being easy to being hard, and I'm interested in what is known about this "threshold".

The only reference to sub-constant distinguishability I could find is in this paper, which (assuming I understand the paper correctly) seems to rule out polynomial-time distinguishability with $\epsilon > \frac{1}{o(n)}$ via "statistical algorithms." Anybody know what else is known / believed?

My understanding is that no algorithm is known for finding cliques with polynomially high success probability for $k=O(n^{1/2-\epsilon})$.  I think it is believed that getting a polynomially large success probability is not possible.

The reason for my holding this belief is that after a clique-finding algorithm outputs a clique, one can check if it succeeded.  So if the algorithm fails, it can be re-run until the clique is found, which would yield polynomial time algorithm for polynomially high edges.  Of course, this isn't quite right -- an algorithm may be deterministic and its success could depend on the random target graph, and so this trick wouldn't work.  So this is more intuition than proof.

The paper of mine you cite gives concrete lower bounds, but only for a restricted class of algorithms.


What is "Flynn's algorithm" relating to linked lists? The other day, I came across an offhand mention of something called "Flynn's algorithm," which, as I gathered, had something to do with a linked list.  But that's all I was really able to discern.  Can anyone point me to a paper, or at least a web page that might further enlighten me?

You might be thinking of Floyd's algorithm for finding cycles.  Given a singly linked list, it finds a cycle in the list (if one exists) in constant space and time linear in the size of the list.


Capacity of Uniquely Solvable Puzzle (USP) In their seminal paper Group-theoretic algorithms for matrix multiplications, Cohn, Kleinberg, Szegedy and Umans introduce the concept of uniquely solvable puzzle (defined below) and USP capacity. They claim that Coppersmith and Winograd, in their own groundbreaking paper Matrix multiplication via arithmetic progressions, "implicitly" prove that the USP capacity is $3/2^{2/3}$. This claim is reiterated in several other places (including here on cstheory), yet nowhere is an explanation to be found. Below is my own understanding on what Coppersmith and Winograd do prove, and why it's not enough.

  Is it true that the USP capacity is $3/2^{2/3}$? If so, is there a reference for the proof?

Uniquely solvable puzzles

A uniquely solvable puzzle (USP) of length $n$ and width $k$ consists of a subset of $\{1,2,3\}^k$ of size $n$, which we also think of as three collections of $n$ "pieces" (corresponding to the places where the vectors are $1$, the places where they are $2$, and the places where they are $3$), satisfying the following property. Suppose we arrange all the $1$-pieces in $n$ lines. Then there must be a unique way to put the other pieces, one of each type in each line, so that they "fit".

Let $N(k)$ be the maximum length of a USP of width $k$. The USP capacity is
$$ \kappa = \sup_k N(k)^{1/k}. $$
In a USP, each of the pieces needs to be unique - that means that no two lines contain a symbol $c \in \{1,2,3\}$ in exactly the same places. This shows (after a short argument) that
$$ N(k) \leq \sum_{a+b+c=k} \min \left\{ \binom{k}{a}, \binom{k}{b}, \binom{k}{c} \right\} \leq \binom{k+2}{2} \binom{k}{k/3}, $$
and so $\kappa \leq 3/2^{2/3}$.

Example (a USP of length $4$ and width $4$):
$$\begin{align*}
1111 \\ 2131 \\ 1213 \\ 2233
\end{align*}$$
Non-example of length $3$ and width $3$, where the $2$- and $3$-pieces can be arranged in two different ways:
$$\begin{align*}
123 && 132 \\ 231 && 321 \\ 312 && 213
\end{align*}$$

Coppersmith-Winograd puzzles

A Coppersmith-Winograd puzzle (CWP) of length $n$ and width $k$ consists of a subset $S$ of $\{1,2,3\}^k$ of size $n$ in which the "pieces" are unique - for any two $a \neq b \in S$ and $c \in \{1,2,3\}$,
$$ \{ i \in [k] : a_i = c \} \neq \{ i \in [k] : b_i = c \}. $$
(They present it somewhat differently.)

Every USP is a CWP (as we commented above), hence the CWP capacity $\lambda$ satisfies $\lambda \geq \kappa$. Above we commented that $\lambda \leq 3/2^{2/3}$. Coppersmith and Winograd showed, using a sophisticated argument, that $\lambda = 3/2^{2/3}$. Their argument was simplified by Strassen (see Algebraic complexity theory). We sketch a simple proof below.

Given $k$, let $V$ consist of all vectors containing $k/3$ each of $1$s, $2$s, $3$s. For $c \in \{1,2,3\}$, let $E_c$ consist of all pairs $a,b \in V$ such that $\{ i \in [k] : a_i = c \} = \{ i \in [k] : b_i = c \}$, and put $E = E_1 \cup E_2 \cup E_3$. Every independent set in the graph $G = (V,E)$ is a CWP. It is well-known that every graph has an independent set of size $|V|^2/4|E|$ (proof: select each vertex with probability $|V|/2|E|$, and remove one vertex from each surviving edge). In our case,
$$ |V| = \binom{k}{k/3} \binom{2k/3}{k/3}, \quad |E| \leq 3|E_1| = \frac{3}{2}\binom{k}{k/3} \binom{2k/3}{k/3}^2. $$
Hence
$$ \frac{|V|^2}{4|E|} = \frac{1}{6} \binom{k}{k/3} \Longrightarrow \lambda \geq \frac{3}{2^{2/3}}. $$

Like many other questions, the answer to this one can be found in Stothers' thesis. A local USP is a CWP in which the only way in which a 1-piece, a 2-piece and a 3-piece can fit together is if their union is in $S$. Clearly a local USP is a USP, and a construction from [CKSU] shows that the USP capacity is achieved by local USPs (we are going to show that constructively).

Coppersmith and Winograd construct an almost 2-wise independent distribution $S$ on $2^V$ with the following two properties: (1) $\Pr[x \in S] = (|V|/2|E|)^{1-\epsilon}$, (2) For any $x,y,z \in V$ such that the 1-piece of $x$, the 2-piece of $y$ and the 3-piece of $z$ together form a vector $w \in V$: if $x,y,z \in S$ then $w \in S$.

We choose a random subset $S$ of $V$ according to the distribution, and for each edge $(x,y) \in E$, we remove both vertices $x,y$. The expected number of vertices left is roughly $(|V|^2/2|E|)^{1-\epsilon}$. The resulting set $T$ is a local USP: if there are $x,y,z \in T$ in which the 1-piece of $x$, the 2-piece of $y$ and the 3-piece of $z$ fit, forming a piece $w$, then $x,y,z,w \in S$, and so all of $x,y,z$ are removed from $S$.


measures for a DAG (directed acyclic graph)? Recently, I want to devise some kernelization (in the framework of parameterized complexity) for problem on DAG. So, find a proper parameter is essential.
Well, is there a measure for the importance of a node (like the cut vertex in undirected graph)? or how separated the DAG is? May be after small amount of edge deletion (or node deletion) the DAG was decomposed into separated components (Better if the components have similar cardinality)?

There are loads of measures of nodes in a DAG you could use.  For example:

How much the removal of node $v$ reduces the max flow from sources to sinks
the betweenness centrality of $v$
the in-degree of $v$ times the out-degree of $v$

The question should not be if there is a measure, but rather which measure is most appropriate.  That depends on the problem you're trying to solve.


How the Number of Clauses Change the Complexity of Worst Case k-SAT ? Is there a conjecture such that if the conjecture holds then the following (1) and (2) hold ?

(1)The worst case time complexity of k-SAT with n variables and m clauses reaches the maximum value, if m is Cn where C is a constant.

(2)The exponential time hypothesis

This question comes from a view about input size of problems. For example, an instance of 3-SAT with n variables is a 3CNF formula and the length of the formula  could be O(n^3). The complexity of obvious algorithm for 3-SAT with n variables is 2^n. 2^n is strictly smaller than 2^{ O(n^3) }. The complexity is defined as the function of input size like the length of formula and the exponential function of input length is 2^{ O(n^3) } and is not 2^n. 2^n time seems to be a sub-exponential time if the statement (1) does not hold.

I think that your question is already solved in On the Complexity of K-SAT by Russell Impagliazzo and Ramamohan Paturi.

And the answer, as anticipated by JeffE is yes.


How fast is an equivalent 2-tape TM compared to a $O(n^2)$ 1-tape TM? In $O(n^2)$ steps, a 1-tape TM can simulate a 2-tape TM that runs for $O(n)$ steps.
How fast is an equivalent 2-tape TM known to run compared to a $O(n^2)$ time, 1-tape TM?
"Open question" is a fine answer.
Edit: removed the word "simulate" and replace with question about equivalent TMs for clarity, add below facts.
Here are some (uninteresting) related problems I do know bounds on:

$DTIME_{1-tape}(O(n)){\subseteq}DTIME_{2-tape}(O(n))$. It's easy to make an equivalent 2-tape TM by ignoring one tape.
There is a a $O(n)$ time 1-tape TM (recognizing $\{1^n\}$) that takes $O(n)$ time for any equivalent 2-tape TM to run.
$DTIME_{2-tape}(O(n)){\subseteq}DTIME_{1-tape}(O(n^2))$. This is the well-known method mentioned above, to simulate a 2-tape TM on a 1-tape TM.
$DTIME_{1-tape}(O(n^2 logn)){\not\subseteq}DTIME_{2-tape}(O(n))$. Suppose every $O(n^2logn)$ time 1-tape TM ran in $O(n)$ time for some 2-tape TM. Then we would have $DTIME_{1-tape}(O(n^2logn)){\subseteq}DTIME_{2-tape}(O(n)){\subseteq}DTIME_{1-tape}(O(n^2))$ This would contradict known time hierarchy bounds for 1-tape TMs.

Just an extended comment to underline how the question is (up to my knowledge) far from being solved (and easy).
First of all there are no "natural" quadratic lower bounds with respect to multi-tape Turing machines (see e.g. K.W.Regan, On Superlinear Lower Bounds in Complexity Theory). So the approach, find an $O(n^2)$ problem on a 1-tape Turing machine that cannot be solved faster on a 2-tape TM would imply a major breakthrough.
On the opposite direction, one should be able to find a "universal" way to speed-up the simulation of a 1-tape TM on a 2-tape TM, but there are some examples for which the task seems hard; for example a 1-tape TM can efficiently simulate a dynamic non-linear system such as 1-D cellular automata - CA - (steps are parallel and use local information); and it is conjectured that the only way to know the state of the system after $n$ steps is to evolve the system $n$ times according to the rules (see e.g the (famous? :-) computational irreducibility - CIR - conjectured by S. Wolfram and analyzed in H. Zwirn and J.P. Delahaye, Unpredictability and Computational Irreducibility).
For example for every 1-D CA $A$ there is an $O(n^2)$ 1-tape TM $M_A$ that solves the problem:

Given a configuration $x$, is the state of $A$ equal to $x$ after $|x|$ steps from a blank initial configuration?

in $O(|x|^2)$ time.
Just use an expanded alphabet to overlap the target (input) configuration $x$, the current step evolving configuration and the next step configuration, and an extra bit for a "distributed" counter to stop the evolution after  $|x|$ steps.
E.g.
x = 1 1 0 1 0 0 1  (target configuration)

x = [1 0 0 s ] [100s] [000s] [100s] [000s] [000s] [100s]
     | | | +-step counter
     | | +---next step CA configuration
     | +-----current step CA configuration
     +-------target configuration

The TM sweeps from left to right and apply the CA rules writing the new configuration in the "next step" bits. At the end of a sweep the role of the next/current bits are swapped. Furthermore, at every sweep it deletes an $s$, when no more $s$  it simply compares the current configuration to the target configuration.
There are not known ways to speed-up the simulation of a 1D CA on a k-tape TM, and (probably) such speed-up would imply that the Computation Irreducibility conjecture is false.


Efficiently generate list of lightest intervals of a vector Suppose a vector of size $n$ is given. The goal is to compute, $\forall i \in [n]$ the lightest interval of size $i$ (i.e. the interval whose sum is minimal).

For example, if we have the array:

1 1 0 0 1 2 1 0 0 0 1

For any length n, the minimal weight of $i$ length interval is:

interval size:              1  2  3  4  5  6  7  8  9  10 11
interval weight:            0  0  0  1  2  4  4  4  5  6  7

A naive algorithm would compute the shortest interval for each $i$ by itself, which results in a $O(n^2)$ time algorithm (keeping a sliding window of size $i$).

If we attempt a greedy "triangle" algorithm (start from the smallest number, expand by 1 each time), it fails, no matter if we try it botom-up or top-down:

A triangle algorithm would fail at 1 1 1 4 0 1 4

1 1 1 4 0 1 4 -> 0
1:0 :         0
2:1 :       4 0 > 0 1
3:5 :       4 0 1 = 0 1 4     BUT: 1 1 1 would be cheaper
4:6 :     1 4 0 1 < 4 0 1 4
5:7 :   1 1 4 0 1 < 1 4 0 1 4
6:8 : 1 1 1 4 0 1 < 1 1 4 0 1 4
7:12: 1 1 1 4 0 1 4

A reverse triangle algorithm would fail at 0 3 0 0 1 1

6:5: 0 3 0 0 1 1
5:4: 0 3 0 0 1 < 3 0 0 1 1
4:3: 0 3 0 0 < 3 0 0 1     BUT: 0 0 1 1 would be cheaper!
3:3: 0 3 0 == 3 0 0        BUT: 0 0 1 would be cheaper!
2:3: 0 3 == 3 0            BUT: 0 0 would be cheaper!
1:0: 0 < 3

Is it possible to find the interval weights in time $o(n^2)$? Is it possible to approximate them with lower runtime?

You can build the whole table using the following $O(n^2)$ construction:

1: 1   1   0 z:0 w:1   2   1   0   0   0   1
2:   2   1   0   1   3   3   1   0   0   1
3:   y:2   1   1   3   4 v:3   1   0   1
4:     x:2   2   3   4 u:4 ...
5:        ...
...

At every step you are calculating the value $x$ at the top of a "reversed triangle", and the value is simply the sum of an adjacent element in the previous row ($y$ in the figure) and the opposite vertex at the base of the triangle ($z$ in the figure).

*         z
 ...   ...
   y   *
     x
x = y + z

or equivalently:

w         *
 ...   ...
   *   v
     u
u = v + w

For each row the difficulty is given by the lower element of that row.


Density of P-complete languages Suppose $L$ is a Boolean language, of finite strings over $\{0,1\}$.  Let $L_n$ be the number of strings in $L$ with length $n$.  For a function $d(n)$ from the positive integers to the positive real numbers, $L$ has upper density $d(n)$ if $L_n \le 2^n d(n)$ for all sufficiently large $n$.

  Do any P-complete Boolean languages have upper density $O(1/n)$?

Motivation

PARITY has upper density $1/2$.  YES (the language of all finite binary strings) has upper density 1.  Any finite language has upper density 0.
A sparse language $L$ has the property that there is a polynomial $p(n)$ such that $L_n - L_{n-1} \le p(n)$ for all $n$.  If $L$ is a sparse language, then $L_n \le p_1(n)$ for a polynomial $p_1$ of degree one greater than that of $p$, so the upper density of $L$ is zero.
Jin-Yi Cai and D. Sivakumar showed that a P-complete language cannot be sparse unless P = L (= LOGSPACE).  Since P=co-P, any language of which the complement is sparse cannot be P-complete either, unless P=L.
By a simple inequality (see e.g. Corollary 2 of Rosser and Schoenfeld 1962), PRIMES has upper density $(\log_2 e)/n$.  Question Are the problems PRIMES, FACTORING known to be P-hard? discusses whether PRIMES is P-hard (this seems to be open currently).
In some sense, the complete (or universal)languages for a complexity class contain all the structure of the class.  So my tentative hypothesis, based on a wild extrapolation of Cai and Sivakumar's result, would be that such languages cannot be too sparse.  The usual polynomial bound defining sparse languages seems too restrictive, so I'm asking about a bound that is a little less restrictive.

The work on lowness by Fortnow, Hemaspaandra, and others is also possibly related.

The question can be asked of classes other than P, but I can't recall any results that would allow establishing density of, say, $k$-SAT.  Pointers to relevant literature would be most welcome.

Acknowledgements

See also related question Conditional density of primes.  Thanks to @Tsuyoshi Ito and @Kaveh for helpful comments on an earlier version of this question, which was unfortunately ill-posed.

I don't know what the density of common P-complete problems is, but here is a padding argument that shows how to lower any density below $1/n$:

Take your favorite P-complete language $L_n \subseteq \{0,1\}^n$. This language has some density $d(n) \in \omega(1/n)$. Now define $L'_{n + m} = \{x0^m | x \in L_n\}$. In general, $m$ will be some function of $n$, so this might not define $L'$ for all sizes, since we are worried only about the upper density, just make $L'_k = \emptyset$ if $k \neq n + m$. What is the upper density of $L'$? Well, we have

\[
d'(n + m) = \frac{|L'_{n + m}|}{2^{n + m}} = \frac{|L_n|}{2^{n + m}} \leq \frac{d(n)}{2^m}
\]

Now lets use LOG-reductions to build a machine $M$ for $L$ using a machine $M'$ for $L'$. Well, if you are given an input $x$ then simply copy it one bit at a time to the query tape (also use a counter to count what $n$ is), then use a second counter to count upto $m(n)$, adding one every time you add a zero to the query tape (to have log space, we need $m(n) \in poly(n)$ and easily computable). Then query and return the output as your answer.

If we want to be sure we are smaller than $1/n$ then just pick $m(n) = n$, and then we will have $d'(2n) \leq d(n)/2^n \in O(1/n)$.


Consequences of Factoring being in P? Factoring is not known to be NP-complete. This question asked for consequences of Factoring being NP-complete. Curiously, no one asked for consequences of Factoring being in P (maybe because such a question is trivial).
So my questions are:

Which would be the theoretical consequences of Factoring being in P? How the overall picture of complexity classes would be affected by such a fact?
Which would be the practical consequences of Factoring being in P? Please do not say that banking transactions could be in jeopardy, I already know this trivial consequence.

There are pretty much no complexity-theoretic consequences of Factoring being in P. This means that there are no good justifications for factoring being hard, other than that nobody has been able to crack it so far.

Polynomial-time factoring would make it possible to take square roots over $Z_n$ (and also over a much more general class of rings as well), and give polynomial-time algorithms for a number of other number-theoretic problems for which the bottleneck in the algorithm is currently factoring.

As for practical consequences, banking transactions are probably not that much of a problem -- as soon as it was known that factoring was in P, the banks would switch to some other system, probably causing only a brief period of delays while this was being implemented. Decoding past banking transactions would probably not cause serious problems for the banks. A much more serious problem is that all the communication which was previously protected by RSA would now be in danger of being read.


Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits? Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ?

No. Consider the following function on $\{0,1\}^n$:
$$ f(x) = x_0 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1}). $$
Clearly this function is hard for AC0. On the other hand, the function is almost constant, so almost all of its Fourier spectrum is on the first level.

If you want a balanced counterexample, consider
$$ g(x) = x_0 \oplus \left[x_1 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus
\cdots \oplus x_{n-1})\right]. $$
This function is almost always equal to $x_0$, so almost all of its Fourier spectrum is on the first two levels.