I think the "few nonzeros" problem is NP-hard, by reduction from the partition problem. Suppose we are given $m$ numbers $a_1,\ldots,a_m$ whose total sum is $2 s$, and have to decide whether they can be partitioned into two subsets such that the sum in each subset is $s$. We can solve this problem using a linear program with $2 m$ variables. For each  $i\in[2]$ and $j\in [m]$, the variable $x_{ij}$ determines what fraction of the number $a_j$ is in subset $i$. There are $m+1$ constraints (besides non-negativity):

For each $j\in[m]$: $x_{1j}+x_{2j} = 1$
The equal-sum constraint: $\sum_{j=1}^m x_{1j} a_j =  \sum_{j=1}^m x_{2j} a_j$

There always exists a solution with at most $m+1$ nonzeros. In this solution, at most one  number is "cut" between the sets. Indeed, it is easy to solve the partition problem if we are allowed to cut one number: just order the numbers on a line and cut the line into two parts with equal sum.

Now, if we could solve the "few nonzeros" problem, then we could decide whether the above LP has a solution with at most $m$ nonzeros, which would imply a solution to the partition problem (in which no number is cut). But this problem is known to be NP-complete.

NOTE: the partition problem is considered "the easiest NP-hard problem". So, while "few nonzeros" is NP-hard, it may still be easy in practice. Alternatively, it may be possible to reduce to "few nonzeros" from a harder NP-hard problem. So its exact hardness is still open.


All Pairs Shortest Path - Directed graph with integer weights

I'll first answer question (2). Let's solve the $(\max,+)$ product problem. The $(\min,+)$ product can be solved analogously by negating entries and adding $M$ to each entry to make all entries positive.

Take $A$ and $B$ whose product $C$ we want to compute, and create matrices $A'$ and $B'$ where $A'[i,j]=(n+1)^{A[i,j]}$ and $B'[i,j]=(n+1)^{B[i,j]}$ for all $i,j$.
Compute the product $C'$ of $A'$ with $B'$. This takes $O(Mn^\omega \log n)$ time since the bit representation of the integers in $A'$ and $B'$ has length $O(M\log n)$.
Consider now $C'[i,j]=\sum_k A'[i,k]B'[k,j]=\sum_k (n+1)^{A[i,k]+B[k,j]}$.
If $\max_k A[i,k]+B[k,j] = z$, then $C'[i,j]\geq (n+1)^z$, and if $\max_k A[i,k]+B[k,j]<z$, then $C'[i,j]\leq n\cdot (n+1)^{z-1} < (n+1)^z$. Thus, $C[i,j]$ is the largest power of $n+1$ that's at most $C'[i,j]$ and hence $C$ is easy to obtain from $C'$.

With respect to question (1), in order to find for each $i,j$, the index $k$ that achieves the minimum (called the witness), one uses a method by Zwick (from Uri Zwick. 2002. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49, 3 (May 2002), 289-317.) This method is based on ideas from an earlier paper by Alon, Galil, Margalit and Naor on finding witnesses for Boolean matrix multiplication.

The basic idea is to first figure out a way to extract the witness $k$ for entry $i,j$ provided $k$ is a unique witness for the minimum. Then one uses a carefully chosen, polylogarithmic number of random samples of columns of $A$/rows of $B$ which ensures that $k$ is the unique witness for $i,j$ in one of the samples with high probability. To extract a unique witness, one only needs to do $\log n$ distance products. For each $l=1,\ldots,\log n$, let $K_l$ be the integers whose $l$th bit is $1$, and compute the distance product of $A$ and $B$, restricted to the columns of $A$/rows of $B$ with indices in $K_l$. Then if $k$ is unique such that $C[i,j]=A[i,k]+B[k,j]$, one can compute the the binary representation of $k$ by setting to $1$ only those bits $l$ for which the distance product for $K_l$ had $C[i,j]$ as its $i,j$ entry.


Why is the first step in the Lovasz-Vempala convex volume algorithm correct?

It is also unclear to me what $\epsilon$ means in that line of the paper.
The approximation error for $Z(a_0)$ is never mentioned again;
my interpretation is that the authors are saying the error is so small it can
be ignored.

The bound I get is:
$$ \tag{*} Z(a_0)=Z(2n) \geq (1-(2/e)^n \mathrm{poly}(n)) \int_0^\infty e^{-2nt} t^n \pi_n dt.$$

So the approximation should be ok for $n > 100 \log \epsilon^{-1}$ and large $n$.
I don't know if it is necessary to use a different analysis or algorithm
to get Theorem 1.1 as stated for the regime where
$\epsilon$ is exponentially small compared to $n$.

To show (*), I claim the stronger statement that
$\int_1^\infty e^{-at}t^n dt \leq e^{-a}/n$
for all $a\geq 2n$ - this can be shown by induction on $n$.
Using Stirling's approximation on $\int_0^\infty e^{-2nt}t^n dt=n!(2n)^{-(n+1)}$,
$$ \frac{\int_1^\infty e^{-2nt}t^n dt}
{\int_0^\infty e^{-2nt}t^n dt}
\leq \frac{e^{-2n}(2n)^n}{n^n e^{-n}} \mathrm{poly}(n)
= (2/e)^n \mathrm{poly}(n).
$$


How hard is it to count the number of local optima for a problem in PLS?

Consider the maximum matching problem in bipartite graphs. The family of feasible solutions consists of all matchings, and local search is performed via finding augmenting paths. The problem belongs to PLS since an augmenting path can be found in polynomial time if a current matching is not maximum, and maximality can be checked in polynomial time. Any local optimum is a maximum matching (i.e., global optimum). However, it is #P-hard to compute the number of maximum matchings in a bipartite graph.

Since a local optimum can be found in polynomial time, the problem is unlikely to be PLS-complete. So, I'm afraid this is not an intended answer (your question restricts to PLS-complete problems). However, I should point out that counting the number of local optima can be hard even though one local optimum can be found efficiently.


Maximizing a submodular function of two sets with different size constraints

The problem is likely to be hard to approximate. The densest bipartite subgraph problem can be cast as a special case. Given a bipartite graph $(V,E)$ where $V=V_1 \uplus V_2$ define $f(S,T)$ for $S \subseteq V_1, T \subseteq V_2$ to be the number of edges between $S$ and $T$. Then $f$ satisfies the desired property. In fact $f(S,\cdot)$ is modular and so is $f(\cdot,T)$. If $a=b=k$ then we are asking for a $k$ by $k$ densest bipartite subgraph problem. Only a polynomial ratio approximation is known, and under some assumptions this problem can be shown to be hard.


Dinner-table description of theoretical computer science?

I give people a concrete example. Specifically, I often motivate complexity theory with the same very illustrative (but simple) problem. I ask my audience how they would instruct a small child to discover whether his name is in an alphabetically sorted list of names (and tell them that it takes the child 3 seconds to compare any one name to another). It is often the case that the person/group will come up with the naive, linear approach. I force the conversation to turn to the logarithmic algorithm (I might use a different word than logarithm) either by asking the person for something better or by mentioning it myself. I show them how doubling the size of the list only adds three seconds of work for the child with this new approach. And I compare this directly with the linear version, which will now seem entirely silly.

Of course, I bring it back to earth. I tell them that child in question is generally a computer but that it could be a child or really anyone in general. That the questions we ask aren't really about computers but are more about the amount of space, time and information you need to solve problems. And I motivate complexity analysis by analogy to the two different methods for solving the same problem.

When I've got their attention - I bring out the heavy hitters. I ask them "can you prove that the logarithmic solution is the best you can ever hope to do or can you find something better?" and I ask them "are there problems that no process (algorithm) can hope to solve?" I've been surprised at how people try to tackle these questions when they don't have a TCS background.


Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$

Assume as given that $m=\omega(\sqrt{n})$.

Fix any $\epsilon>0$. We will consider $r\in[1,n]$ with $r<(1-\epsilon)n$. The aim is to show that with high probability as $n\to\infty$, $r$ is included in the set of differences.

First consider the set $A=\{a_i:i<m/2\}\cap[1,\epsilon n]$. The number of $i$ with $i<m/2$ such that $a_i<\epsilon n$ is binomial with expectation around $\epsilon m/2$. So with high probability as $n\to\infty$, the number of such $i$ will be at least $\epsilon m/4$, which is $\omega(\sqrt{n})$. Then (claim, "left as exercise", not hard to show) with high probability as $n\to\infty$, the set $A$ has size at least $\sqrt{n}$. Let us write $G$ for this "good event", that $|A|\geq\sqrt{n}$.

Suppose that indeed $G$ holds, i.e. there are at least $\sqrt{n}$ distinct values of $a_i$ less than $\epsilon n$, for $i<m/2$. Note that for each such value, there is a value $k\in [1,n]$ which is precisely $r$ larger. Now consider the values of $a_i$ for $i\geq m/2$. These are independent and each one has probability at least $\sqrt{n}/n=1/\sqrt{n}$ of being at distance $r$ from an element of the set $A$. The probability that no difference $r$ is produced is then at most $(1-1/\sqrt{n})^{m/2}$ which goes to 0 as $n\to\infty$ since $m=\omega(\sqrt{n})$. So indeed, the probability that $G$ holds but no difference of size $r$ exists tends to 0 as $n\to\infty$.

So (uniformly in $r<(1-\epsilon)n$) the probability that $r$ is included in the set of differences tends to 1 as $n\to\infty$.
Hence using linearity of expectation,
$$
\liminf
\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}\right] \geq 1-\epsilon.$$
Since $\epsilon$ is arbitrary, the limit is 1 as desired.


Reduction

The decision version of your problem (where $k$ is given and we wish to know whether a hub exists for that $k$) is NP-hard by reduction from dominating set.

Let $G = (V, E)$ be the given graph for the dominating set problem and let $k$ be the target number of vertices to be selected for the dominating set problem.

Then construct the instance of your problem (a graph $G'$, a distance function, a set of source vertices $S$, a set of exit vertices $EX$, a target number of hub vertices $k'$, and a pair of values $\gamma$ and $\delta$) as follows:

The new graph $G' = (V', E')$ has vertex set $V'$ and edge set $E'$.
$V' = V \times \{0,1,2\}$.
For all $v \in V$, $((v, 0), (v, 1))$ and $((v, 1), (v, 2))$ are edges in $E'$.
For all $(w, v) \in E$, $((w, 1), (v, 1))$ is an edge in $E'$.
No other edges are present in $E'$.
Every edge has length 1, so that the distance function is the standard undirected graph distance.
$S = V \times \{0\}$.
$EX = V \times \{2\}$.
$k' = k$.
$\gamma = \delta = 2$.

Correctness

The choice of a $(k', \gamma, \delta)$-hub is the choice of $k'$ vertices in $V' \backslash (S \cup EX)$ such that for every $v \in S$ there exists a chosen vertex within distance $\gamma$ of that vertex and a vertex $w \in EX$ within distance $\delta$ of that chosen vertex.

The instance generated by the reduction (when run on graph $G = (V, E)$ and value $k$) asks whether a $(k,2,2)$-hub exists. In that particular case, it is a question of whether there exists a choice of $k$ vertices in $V' \backslash (S \cup EX) = V \times \{1\}$ such that for every $v \in S = V \times \{0\}$ there exists a chosen vertex within distance $2$ of that vertex and a vertex $w \in EX = V \times \{2\}$ within distance $2$ of that chosen vertex.

But notice that any vertex that could be a hub vertex is of the form $(v, 1)$, and therefore has distance one from exit vertex $(v, 2)$. The part of the condition requiring a nearby exit vertex is then automatically satisfied.

Thus the instance is a "yes" instance if and only if there exists a choice of $k$ vertices in $V' \backslash (S \cup EX) = V \times \{1\}$ such that for every $v \in S = V \times \{0\}$ there exists a chosen vertex within distance $2$ of that vertex. This occurs if there exists a choice of $k$ vertices $C \subseteq V$ such that for every $v \in V$ there exists some $c \in C$ with $d((v, 0), (c, 1)) \le 2$.

But $d((v, 0), (c, 1)) \le 2$ if and only if $c$ and $v$ are equal or neighbors in $G$. Thus we can rewrite the condition for the problem instance to be a "yes" instance as follows: there exists a choice of $k$ vertices in $V$ such that every vertex in $V$ is either adjacent to a chosen vertex or is chosen itself. This is exactly the "yes" condition for the dominating set instance, proving this reduction to be answer preserving.

Since the reduction is clearly polynomial time, this concludes the proof that your problem is NP-hard.


Cartesian factorization of a finite set of n-tuples

If I understand the question correctly, the problem is easy (once we understand the problem).

As I understand it, you are given a finite set X⊆A1×…×An and want to find the “best” set I⊆{1,…,n} of indices that is feasible, where we say that a set I is feasible when X can be written as the direct product of the sets Ai for i∈I and some set of (n−|I|)-tuples (where indices are permuted appropriately).

You consider two formulations of the meaning of “best”: (1) the product ∏i∈I |Ai| is maximized, (2) the size |I| is maximized.  However, it does not matter which criterion you use because both can be maximized at the same time.

For each i=1,…,n, test whether the singleton set {i} is feasible (this can be done efficiently).  Let J be the set of indices i such that {i} is feasible.  It is easy to see that J is also feasible, and moreover J is the maximum with respect to inclusion among the feasible sets of indices.  Therefore, the index set J maximizes both criteria (1) and (2) stated above.


Is this edge orientation optimization problem NP-hard?

I believe that this problem is NP-hard, here is a sketch proof (don't hesitate to ask for more details if needed).
The idea is based on a reduction from the Not-all-equal 3-SAT. For $\varphi$ a 3-SAT formula with $m$ clauses, we will build $G(\varphi)$ a graph that has minimum objective value of $2\times m$ iif $\varphi$ has a solution. Before diving into the  building of $G(\varphi)$ let us show the gadgets that we will use.
Fixed node gadget:
The idea here is pretty simple. To fix a node $n$ in $G(\varphi)$ we make sure that $n$ has at least $2\times m+2$ neighbors in $G(\varphi)$ by adding nodes only linked to $n$. Once a node $n$ is fixed then any orientation with objective value less or equal $2\times m$ is such that $d_{in}(n)=0$ or $d_{out}(n)=0$.
Litteral gadget: For each variable $x_i$, we will create two fixed nodes $x_i$ and $\lnot x_i$ that will be linked together with an edge. Because the two nodes are fixed and linked, in any orientation of the graph with value less than $2m$, we will have either $d_{in}(x_i)=0 \land d_{out}(\lnot x_i)=0$ or $d_{out}(x_i)=0 \land d_{in}(\lnot x_i)=0$.
Clause gadget: The idea here is slightly more intricate. For each clause $C_j = l_1 \lor l_2 \lor l_3$ we will create three nodes $C_j^1$, $C_j^2$ and $C_j^3$ which are the red nodes in the graph drawn below. In this graph the three blue nodes will correspond to the three literals $l_1$, $l_2$ and $l_3$. Since the literals will be fixed nodes, we know the orientation for the blue-red edges (i.e. the dashed edges) and we want to compute the orientation of the red-red edges (i.e. the filled edges) that minimizes the objective value.

We can easily show that either all the dashed edges are in the same direction (i.e. all blue to red or all red to blue) in which case the minimum objective value is 4 or they are in diverse directions in which case the minimum objective value is 2.
Putting everything together:
If there is a solution to the not-all-equal problem we can orient the edges outward for true literals and inward for false literals and each clause triangle can be oriented in a way to have an error of $2$, therefore the overall error is $2\times m$. On the converse, if there is an orientation with error less or equal to $2\times m$ then we can retrieve a solution to the not-all-equal problem. Indeed, the fixed nodes have an in or out degree of 0 therefore we can say that literals with in degree equal to zero are true and the other are false. Since each literal is connected to its negation their value are coherent and it is a solution to the not-all-equal problem $\varphi$ because since each triangle clause has error at least 2 and the overall error is $2\times m$ it means that all triangle clauses are connected to a positive and a negative literal.


Are a few hundred reduction steps too many to get the normal form of Y fac ⌜3⌝?

Church coding is really bad if you want to use pred.
I would advise you to use some more efficient coding in Peano style:

// arithmetics

: p_zero = λs.λz.z
: p_one = λs.λz.s p_zero
: p_succ = λn.λs.λz.s n
: p_null = λn.n (λx. ff) tt
: p_pred = λn.n (λp.p) p_zero
: p_plus = μ!f.λn.λm.n (λp. p_succ (!f p m)) m
: p_subs = μ!f.λn.λm.n (λp. p_pred (!f p m)) m
: p_eq = μ!f.λm.λn. m (λp. n (λq. !f p q) ff) (n (λx.ff) tt)
: p_mult = μ!f.λm.λn. m (λp. p_plus n (!f p n)) p_zero
: p_exp = μ!f.λm.λn. m (λp. p_mult n (!f p n)) p_one
: p_even = μ!f.λm. m (λp. not (!f p)) tt

// numbers

: p_0 = λs.λz.z
: p_1 = λs.λz.s p_0
: p_2 = λs.λz.s p_1
: p_3 = λs.λz.s p_2
...

This is some code taken from one of my old libraries, and μ!f. … was just an optimized construction for Y (λf. …). (And tt, ff, not are booleans.)

I'm not really sure you would obtain better results for fac though.


Random self-avoiding lattice cycle within a given bounding box

It seems that because you are only using the counts for number of cycles in a graph to randomly choose a cycle, that if you had a random approximation for this number, then you could still choose a cycle approximately uniformly.

Note that the number of cycles in a graph $G$, which contains edge $(u, v)$, equals the number of cycles in $G - (u, v)$ plus the number of simple paths from $u$ to $v$ in $G - (u, v)$.  Thus, with a polynomial time approximation for the number of $u$-$v$ paths, the a polynomial time approximation can be achieved by incrementally building up to $G$ one edge at a time, approximating as you go.

I actually think that there's a more straightforward method for choosing a cycle.  Let $G$ be the entire graph of edges around the $n \times n$ grid of squares. For each edge $(u, v)$ find the number of cycles containing that edge (which is the number of $u$-$v$ paths in $G$ - $(u, v)$). Then randomly choose an edge weighted by the number of cycles that contain it.  This will be the first edge in your randomly chosen cycle. All other edges will be chosen by extending one edge at a time.

Assume that you have chosen a path which is part of your random cycle.  Let the set of vertices on this path be $C$ and let $v_s$ and $v_e$ be the endvertices of the path.  Also let $N$ be the set of neighbors of $v_e$ which are not in $C$ (note that there are only up to 3 in this particular graph).  For each $u \in N$ count the number of $u$-$v_s$ paths in the induced graph $G[V - (C - \{v_s, v_e \} ) ]$. Then choose a neighbor, $u$, of $v_e$ weighted on the paths just counted. Add the edge $(v_e, u)$ to your chosen path, extending it by one.

In this way, a polynomial number of edges are chosen, each requiring a small number of calculations of a polynomial time approximation algorithm.  Thus, a cycle can be uniformly chosen.

I currently have a stackexchange question requesting references for fast path count approximation algorithms. I've read in a few places that these algorithms exist but haven't yet found them.


About the sign-rank of the Minsky-Pappert function

There's the Minsky-Papert function, which is a depth-two formula, OR composed with AND, where the OR is of size $n^{1/3}$ and the AND is of size $n^{2/3}$. I.e., it's $OR_{n^{1/3}}\circ AND_{n^{2/3}}$.

Then there's the particular communication complexity problem studied in the papers you linked, which is now a function of 2 $n$-bit strings $x$ and $y$, where $x$ is given to Alice and $y$ to Bob. This function is $OR_{n^{1/3}}\circ AND_{n^{2/3}} \circ (x \vee y)$, maybe more clearly expressed as

  $\bigvee _{i=1}^{n^{1/3}}\circ \bigwedge_{j=1}^{n^{2/3}} \circ (x_{ij} \vee y_{ij})$

This is the communication problem for which both papers you linked to prove a sign rank lower bound. If you look at Corollary 1.1, they're talking about this function, not the Minsky-Papert DNF.

Note that any communication problem can be represented as a matrix, by having $x$ index rows and $y$ index columns. The papers prove lower bounds on the sign rank of this matrix for the above communication problem. (Rank and sign rank being measures that make sense for matrices.) What Minsky and Papert showed was a sign degree (or threshold degree) lower bound on the Minsky-Papert DNF. Degree (and sign degree) are measures of Boolean functions.


Are innermost reductions perpetual in untyped λ-calculus?

I believe $tt$ with $t=(\lambda x. (\lambda y.1) (x x))$ will terminate using $L$ even if it has an infinite reduction.

The first reduction step is: $L(tt)=L(t)t=L(\lambda x.(\lambda y.1) (x x))t=(\lambda x.L((\lambda y.1) (x x)))t=(\lambda x.1)t$.

The first reduction step with $F_\infty$ is $F_\infty([(\lambda x.(\lambda y.1 (x x))) t]))=(\lambda y.1) (tt)$.


Computing min rank is NP-hard:

Rene Peeters, "Orthogonal Representation over Finite Fields and the Chromic Numbr of Graphs", 1996.
Salim Y. El Rouayheb, Mohammad Asad R. Chaudhry, Alex Sprintson, "On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks", 2007.


What is the difference between proofs and programs (or between propositions and types)?

The programming languages people use day to day don't fit so well into the Curry-Howard correspondence, because their type systems are too weak. To say something interesting using Curry-Howard for imperative programs, one needs to have a more sophisticated type system. The book Adapting Proofs-as-programs pushes this angle with the aim of synthesising imperative programs. With dependent types becoming more and more popular, certainly in research functional languages (Agda, Epigram), the distinction is becoming blurrier. Of course you can do program synthesis/extraction within the Coq theorem prover (and presumably others), which is of course based on Curry-Howard.

The Curry-Howard correspondence can also be used in situations where the proofs do not so clearly correspond to programs (or they are not programs anyone will ever run). One example of this is in Proof-carrying authorization. The propositions correspond to statements about who is authorized to do what. Proofs provide the required evidence that a proposition holds, thus an authorization request is permitted. In order to encode the proofs, proof terms are introduced (via Curry-Howard). Proof terms are sent between parties as representations of proofs of the validity of authorization requests, but they are not considered programs.


String version of even-odd partition problem

It is possible to reduce from the "unshuffling a string" problem: given a string $w \in \Sigma^*$, decide whether $w$ is a shuffle square, i.e. $w$ is in the shuffle product of two identical strings. This problem is proved to be NP-complete for alphabet of size at least nine, see this question for references and discussion.

Here, for two strings $u$ and $v$  the shuffle product is defined as the set of all $w = u_1 v_1 \ldots u_i v_i$ for each representation $u = u_1 \ldots u_k$ and $v = v_1 \ldots v_k$ with $u_i, v_i \in \Sigma^*$ (i.e. $u_i$ and $v_i$ are strings, not letters).

The reduction is easy: given $w = a_1 \ldots a_n$, $a_i \in \Sigma$, take $x_{i, 0} = a_i$ and $x_{i, 1} = \epsilon$, where $\epsilon$ is the empty string. Then the answer in your problem (with alphabet of size nine) is YES if and only if $w$ is a shuffle square.

Finally, use an arbitrary prefix-free binary encoding of $\Sigma$, thus getting a reduction for the binary case.


What's the "smallest" complexity class for which a superlinear circuit bound is known?

I believe that the smallest such classes known are $S_2P$ (Cai, 2001), $PP$ (Vinodchandran, 2005), and $(MA \cap coMA)/1$ (Santhanam, 2007).  All of these are indeed known to not be in $SIZE(n^k)$ for each constant $k$.


Number of points on the interior of the convex hull of a random subset

Computing the probability that a point is inside a random convex-hull is quite interesting, and got some attention recently (under a slightly different sampling model). The exact probability can be computed (but not too quickly). Good estimates follow by looking on the Tukey depth of the points of interest. See the following recent paper, and references therein.

http://sarielhp.org/p/14/prob_ch/


Problem with a group as complexity parameter?

Many of the best results around graph isomorphism and permutation group algorithms are parametrized by some structure of a relevant group. For example, let $\mathcal{S}_d$ denote the class of groups all of whose composition factors are isomorphic to subgroups of $S_d$. Then coset intersection for groups in $\mathcal{S}_d$ can be solved in polynomial time for constant d. This is closely related to the polynomial-time isomorphism test for bounded-degree graphs.

I think there are also several other problems that are solvable in polynomial time when certain associated groups are in $\mathcal{S}_d$ for $d=O(1)$, but I don't have references off the top of my head.


What is the standard name for the function which inflates a string by duplicating each of its characters?

As pointed out by Marcus Ritt, the correct name for this operation seems to be stutter.

As far as I could determine, it has mostly been used in the field of concurrency theory, where I could trace it back at least to Lamport's 1983 seminal paper on temporal logic.


Finding mapping between two spatial representations of the same objects

If your error norm is the Frobenius distance (that is, $m(X, U) = \|X - U \|_F$, then there is a closed form for your problem. $A = V^+ U$, where $V^+$ is the Moore-Penrose pseudoinverse of $V$ (this is a generalized inverse for non-square matrices).


Write $p=p_0=1-q$. We may assume that $\epsilon<\eta \le p\le 1/2$. Then the sample complexity is of order $\log(1/\delta)$ times the reciprocal of the relative entropy  $D((p,q)||(p+\epsilon,q-\epsilon))$.
This yields sample complexity  $\Theta(p\epsilon^{-2}\log(1/\delta))$.


Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

Take a deterministic TM $M$ and a word $w$. Consider its computation histories for the word $w$. Let $L$ be invalid histories (those which don't start with $w$, don't end with acceptance or are invalid). Either $L = A^{\ast}$ ($M$ doesn't accept $w$) or $L = A^{\ast} - \{h\}$ for some string $h$ ($M$ accepts $w$ with computation history $h$). First of all, $L$ is effective CFL, in the sense that you can build a grammar/PDA recognising it. Moreover, $L$ is a (noneffective) DCFL, but you can't show a DPDA for it effectively. Even more, $L$ is (noneffective) regular.

Small clarification:

You asked if the following problem is decidable:

given PDA $M$ promised that $L(M)$ is a DCFL, and a DPDA $N$ determine if $L(M) = L(N)$.

The answer is no, and in fact the following stronger fact holds: The following problem is undecidable:

given PDA $M$ promised that $L(M)$ is regular, determine if $L(M)=A^{\ast}$.


Edge-partitioning cubic graphs into claws and paths

This isn't an answer to the complexity of the problem, but it at least shows that the complexity has a chance at being nontrivial: it's an example of a cubic graph that cannot be partitioned into paths and claws.

(source: uci.edu)

Within each of its three lobes, any partition into paths and claws can only use six of the seven edges. The remaining six central edges take the form of a claw with each edge subdivided, which cannot be partitioned into paths and claws.

ETA: The graph shown above is more famous as an example of a cubic graph without a perfect matching. But every cubic graph with a perfect matching has a decomposition into paths (not even using any claws). By König's theorem this includes all cubic bipartite graphs and by Petersen's theorem this includes all bridgeless cubic graphs, answering a question of Joseph Malkevitch in the comments.

The proof is very simple: if M is a perfect matching in a cubic graph, the removal of M leaves a 2-regular graph, that is, a disjoint union of cycles. Orient each cycle arbitrarily, and attach each edge uv of M to the cycle edges that follow u and v in the orientations of their cycles.

In the other direction, if there exists a decomposition into paths, then there exists a perfect matching: the middle edges of each path must be a matching since no two middle edges can share a degree-three vertex.

(Disclaimer: this idea may have already been present in Carsten Thomassen's invited talk at GD 2010, which was about this sort of graph decomposition problem.)

(addition to disclaimer (by Anthony Labarre): the "orientation idea" for going from a perfect matching to a partition into paths appears in this paper by Jünger, Reinelt and Pulleyblank, who attribute it to W. H. Cunningham.)


Complexity of topological sort with constrained positions

I think this problem is NP-hard. I try to sketch a reduction from MinSAT. In the MinSAT problem we are given a CNF and our goal is to minimize the number of satisfied clauses. This problem is NP-hard, see e.g., http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec

Divide the vertices into two groups - some will represent literals, the others clauses, so $n=2v+c$ where $v$ is the number of variables of the CNF (usualy denoted by $n$) and $c$ is the number of clauses. Direct an edge from each literal-vertex to the clause-vertex where it occurs. Define $S$ for a literal-vertex that represents $x_i$ as $\{i,i+v+k\}$ (where $k$ is an arbitrary parameter), so either $f(x_i)=i$ and $f(\bar x_i)=i+v+k$ or $f(\bar x_i)=i$ and $f(x_i)=i+v+k$. For each clause-vertix, let $S=\{v+1,\ldots,v+k,2v+k+1,\ldots,n\}$, so $k$ of the clause-vertices are ``small''.

Now the CNF has an assignment where at least $k$ clauses are false if and only if your problem can be solved for the above instance.  The MinSAT problem is exactly to test whether a CNF formula $\varphi$ has an assignment that makes at least $k$ clauses false, so this shows that your problem is NP-hard.

To help you understand this reduction, here's the intuition: small labels ($1,2,\dots,v+k$) correspond to the truth value False, and large labels ($v+k+1,\dots,2v+k$) correspond to True.  The constraints for literal-vertices ensure that each $x_i$ is either True or False and that $\overline{x_i}$ has the opposite truth value.  The edges ensure that if any literal is True, then all clause-vertices containing it are assigned True as well.  (In contrast, if all literals in a clause are assigned False, then this graph structure allows the clause-vertex to be assigned either False or True.)  Finally, the choice of $k$ ensures that $k$ of the clause-vertices are assigned False and $c-k$ of them are assigned True.  So, if there is a valid topological sort of this graph, then there is an assignment to the variables that makes at least $k$ of the clauses of $\varphi$ false (all of the clause-vertices that were assigned False, plus possibly some of the ones that were assigned True).  Conversely, if there is an assignment to the variables that makes at least $k$ of the clauses of $\varphi$ false, then there is a valid topological sort of this graph (we fill in the labels for the literal-vertices in the obvious way; and for each clause of $\varphi$ that is true, we give its corresponding clause-vertex a label that corresponds to True; the other clause-vertices can receive labels corresponding to an arbitrary truth value).


One way communication complexity of multi exact matching

For the lower bound, consider the following problem: Alice is given $x \in \{0,1\}^n$ and Bob is given $i \in [n]$. Their goal is to output $x_i$ (in other words, they need to decide if $i$ is in the set indicated by $x$). This problem is called $INDEX$ in the literature. For the rest of this answer, I assume that Alice always speaks first.

Claim: the randomized one-way communication complexity of $INDEX$ is $\Omega(n)$. By Yao's minimax principle, it suffices to give a linear lower bound on distributional one-way communication complexity of $INDEX$ with respect to the uniform distribution. Let $\pi$ be a one-way protocol that solves $INDEX$ with probability of error $\le 1/64$ with respect to the uniform distribution. For $x \in \{0,1\}^n$ let $M_x$ denote the message sent by Alice on input $x$, and let $\pi(x,i)$ denote the protocol's output on the input $(x,i)$. We have probability of error = $\mathbb{E}_x (P_i(\pi(x,i) \neq x_i)) \le 1/64$. Thus, by Markov's inequality $P_x(P_i(\pi(x,i) \neq x_i) \ge 1/32) \le 1/2$. Let $A$ be the set of all $x$ such that $P_i(\pi(x,i) \neq x_i) \le 1/32$. Note that $|A| \ge 2^{n-1}$. Let $M$ be a message sent by Alice. Let $o \in \{0,1\}^n$ be the string defined by $o_i = \pi(M,i)$. By above, if $x$ is such that $x \in A$ and $M_x = M$, then $x$ and $o$ differ in at most $n/32$ positions. Number of such $x$ is at most ${n \choose n/32} 2^{n/32} \le (32 e)^{n/32} 2^{n/32} \le 2^{8n/32} = 2^{n/4}$. In other words, we have shown that a given message $M$ can arise out of at most $2^{n/4}$ different inputs. Thus the total number of messages has to be at least $2^{n-1}/2^{n/4} =2^{3n/4-1}$. Therefore there is a message of length at least $3n/4 -1 = \Omega(n)$.

Now, this gives an $\Omega(n)$ lower bound for your problem via a reduction. Given $x \in \{0,1\}^n$ Alice constructs $n$ strings $s_1, \ldots, s_n$ as follows: if $x_j = 1$ then Alice sets $s_j$ to be the binary expansion of $j$ (padded to have $n$ bits), otherwise she sets $s_j$ to be 0. Upon, receiving $i$, Bob constructs his own string to be the binary expansion of $i$ (padded to $n$ bits). Bob's string matches one of Alice's strings if and only if $x_i = 1$.


What persistent data structure for a set of partially ordered elements?

The paper "Sorting and Selection in PoSets" by Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008 which describes a dynamic representation of PoSets based on antichains.

You might also be interested in the paper "Succinct Posets" by Munro, Nicholson, 2012 recently released on Arxiv and in the bibliography therein. Their data-structure is static but I assume that the next step is to have a dynamical data-structure.


Partition edges into edge disjoint walks

Create a new source and connect it to $s_1,\ldots,s_k$, and create a new sink and connect it to $t_1,\ldots,t_k$.
Every edge has capacity $1$ and cost $−1$.
With this, the problem is a special case of the min-cost flow problem.


The algorithm is described in the proof of Theorem 9. For every proper minor closed class $\mathcal{F}$ and every planar graph $H$ there is a constant $c(\mathcal{F}, H)$ such that if the tree-width of $G\in\mathcal{F}$ is at least $c$, then the answer is positive. Furthermore, the property of containing $H$ as an induced minor is an MSO definable property (and the length of the formula depends on $H$ only). Hence you first check whether the tree-depth of $G$ is smaller than $c$ and compute a tree-decomposition (e.g. by Bodlaender's algorithm). If so, you take an MSO model-checker and check whether $H$ is an induced minor of $G$ by testing whether $G$ satisfies the appropriate formula. If not, you simply answer yes.

Note though that the constant $c$ depends on the class $\mathcal{F}$ and if you don't have an explicit list of excluded minors, there might be no constructive way to find them. You cannot just take a bipartite graph and apply the theorem. The graph must be from some class $\mathcal{F}$ with the above properties.


Computing the Cheeger constant: feasible for which classes?

Notice that approximating sparsest cut to within $\alpha$ gives a $2\alpha$ approximation for the Cheeger constant as defined. Here are some papers that give constant approximation algorithms for sparsest cut in restricted graphs:

Bounded genus: http://dl.acm.org/citation.cfm?id=1873619
Bounded treewidth: http://arxiv.org/abs/1006.3970

Furthermore, http://arxiv.org/abs/1006.3970v2 proves that sparsest cut is NP-hard for graphs with pathwidth 2, and has quite a few more references to approximating sparsest cut on restricted instances.

I would assume that for all classes of graphs mentioned in the paper, no exact algorithms are known (as they're interested in approximations). In particular, if sparsest cut is NP-hard for graphs with pathwidth 2, it's also NP-hard for graphs of treewidth 2, and cutwidth 2. I suppose that doesn't give quite a lot of room.. maybe there is another better parameterization for sparsest cut.

I am pretty sure that sparsest cut is NP-hard on regular graphs but can't find a reference.

Per noticed that I wasn't careful when I looked at the papers above. The hardness result is for nonuniform sparsest cut. Computing uniform sparsest cut or the Cheeger constant is easy on trees (WLOG the optimal cut separates a subtree). With a little more work that gives a dynamic programming algorithm for computing the Cheeger constant on bounded treewidth graphs.

Table 1 in paper 2 above also mentions a result that gives a constant approximation for graphs with an excluded minor.

For bounded genus graphs, the best that seems to be known is a constant approximation (paper 1 above gives $O(\sqrt{\log g})$ where $g$ is the genus.


Existence of $opt^c$-approximation of Dominating Set with $c < 1$?

I think it is still open if Dominating Set or Hitting Set have a f(OPT) approximation for some (nontrivial) function f. This is should be a very difficult (and possible deep) question to answer. I consider it the most exciting question in parameterized approximation (along with the analogous question for Clique). You might want to have a look at my survey [1] that discusses this. Note that it is shown in the more recent paper [2] that "monotone circuit satisfiability for weft-2 circuits", a problem which is more general than Dominating Set, does not have f(OPT) approximation for any f.

[1] D. Marx. Parameterized complexity and approximation algorithms.
The Computer Journal, 51(1):60-78, 2008.

[2] D. Marx. Completely inapproximable monotone and antimonotone parameterized problems.
In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, Cambridge, Massachusetts, 181-187, 2010.


Yup. Everything follows from duality. (I am only half joking).
A partial list:

Boosting

The Hard-Core Lemma

Online Learning

The ability to actually solve LPs efficiently

A large fraction of approximation algorithms results.

Much more

To develop algorithms, you often need a constructive or algorithmic version of the duality theorem (which is essentially equivalent to Von-Neumman's min-max theorem in game theory -- the applications in game theory are also huge). This is essentially what the multiplicative weights algorithm is. See Arora/Hazan/Kale for the best survey on this topic: http://www.satyenkale.com/papers/mw-survey.pdf


Bounds on the size of the smallest NFA for L_k-distinct

This is not an answer but a method which I believe would leave to an improved lower bound. Let us cut the problem after $a$ letters are read. Denote the family of $a$ element sets of $[n]$ by $\mathcal A$ and the family of $b=k-a$ element sets of $[n]$ by $\mathcal B$. Denote the states that can be reach after reading the elements of $A$ (in any order) by $S_A$ and the states from which an accepting state can be reached after reading the elements of $B$ (in any order) by $T_B$. We need that $S_A\cap T_B\ne \emptyset$ if and only if $A\cap B=\emptyset$. This already gives a lower bound for the required number of states and I think it could give something non-trivial.

This problem essentially asks for a lower bound on the number of the vertices of a hypergraph whose line graph is (partially) known. Similar problems were studied e.g., by Bollobas and there are several known proof methods that can be useful.

Update 2014.03.24: In fact if the above hypergraph can be realized on $s$ vertices, then we also get a non-deterministic communication complexity protocol of length $\log s$ for set disjointness with inputs sets of size $a$ and $b$ (in fact the two problems are equivalent). The bottleneck is of course when $a=b=k/2$, for this I could only find the following in Eyal and Noam's book: $N^1(DISJ_a)\le \log \big(2^k \log_e {n\choose a}\big)$ proved by the standard probabilistic argument. Unfortunately I could not (yet) find good enough lower bounds on this problem but assuming the above is sharp, it would give a lower bound $\Omega(2^k\log n)$ unifying the two lower bounds you have mentioned.


What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture?

An earlier version of this answer was originally posted as an answer to the question “Consequences of Unique Games being a NPI problem” by NicosM.  Because it turned out that it did not answer what he wanted to ask, I moved it to this question.

Short answer: They mean different statements.  The latter implies the former, but the former does not necessarily imply the latter.

Long answer: Recall that the unique game problem is the following promise problem.

Unique game problem with parameters k∈ℕ and ε, δ > 0 (1−ε > δ)
Instance: A two-player one-round unique game G with label size k.
Yes-promise: G has value at least 1−ε.
No-promise: G has value at most δ.

The unique games conjecture states:

  Unique games conjecture.  For all constants ε and δ, there exists a constant k such that the unique game problem with parameters k, ε, and δ is NP-complete.

Consider results of the following form:

  (1) Assuming the unique games conjecture, problem X is NP-hard.

(An example of X is the problem of approximating maximum cut within some constant factor R > RGW.)

Most (if not all) of the results of the form (1) actually prove the following fact:

  (2) There exist constants ε and δ such that for every constant k, the unique game problem with parameters k, ε, and δ is reducible to X.

It is easy to verify that (2) implies (1).  However, (2) implies more than (1): for example, suppose that one day we can prove that a variant of the unique games conjecture where “NP-complete” is replaced with “GI-hard.”  Then (2) implies that X is also GI-hard.  (1) does not imply this.  This is why some people consider that statement (1) is not the best way to state the theorem: (1) is weaker than what is actually proved, and the difference might be important.

Although (2) is a more accurate statement of what is proved, it is clearly mouthful.  This is why people have come up with a shorthand for it: “Problem X is UG-hard” is a shorthand for (2).


What are good conferences for algorithms about finite automata?

The main conferences where automata are among the main topics are ICALP, LICS, STACS, CSL, MFCS, FSTTCS.

If you feel your paper is not strong enough for these conferences (which accept about a quarter of the papers that are sent each year), you can send to conferences which are a little less exigeant.

The ICALP submission deadline is soon (in a week), after this the next in the list is FSTTCS I believe.

These conferences are all european (except FSTTCS from India), it seems that automata are less popular in USA, but it might be that your results interest some people at STOC or FOCS.


Could you please provide a reference to the context, where the term "efficiently samplable distribution" is used? Because there is a well-known concept called "polynomial-time samplable distribution", so because in TCS we usually mean "efficient" = "polynomial-time", I guess these two can coincide.


How to choose good diagonals when partitioning an orthogonal polygon into rectangles?

Starting with 5,7,$f$ and $g$ is correct. In order to complete the maximum independent you can proceed as follows. First, delete the vertices that are reachable from an unmatched vertex via an alternating path (in your example 5,6,7,$e$,$f$,$g$). This leaves a balanced bipartite graph (that is, it has the same number of vertices on each side), and you can simply add one of the two sides to your independent set. In your example, you get the maximum independent set $\{1,2,3,4,5,7,f,g\}$ or $\{a,b,c,d,5,7,f,g\}$.


How do I describe this (graph-)problem for a research paper?

Replace any negative value with zero. Then, think of the numbers in the range $1\dots W$ as vertices in a graph, and think of a pair $(x,y)$ as corresponding to an edge from vertex $x$ to vertex $x+y$ (or to $W$ if $x+y>W$), with weight $f(x,y)$. This graph is a DAG, and what you are looking for are the nonzero edges on a longest path from $1$ to $W$ in this DAG. DAG longest path problems can be solved in time linear in the size of the DAG (here, $O(WH)$); see https://en.wikipedia.org/wiki/Longest_path_problem.


Just an extended comment: I'm not an expert, but for what regards 1., something can be said if you interpret: $HALT(k) = 1$ iif $TM_k$ halts on the empty tape.

In this case the string $s$ that lists the first $n$ bits $HALT(k)$, $k = 1,2,...,n$ is highly compressible:

$|s|=n$
let $h$ be the number of halting TMs between $1$ and $n$ ($h \leq n$)

If you know $h$, in order to build $s$ you can simply simulate all TMs between $1$ and $n$ and when $h$ of them stops you have enough information to reconstruct $s$ (you have the positions of the $1$s, the other can be set to $0$s).

So $K(s) = \lceil \log h \rceil + c$

If you interpret $HALT(k) = 1$ iif $TM_k$ halts on all inputs, then:

$K(s) =  min\{n, K(\lceil \log n \rceil, \lceil \log z \rceil )\} + c$

Where $z$ is the minimum number such that for every non halting $TM_k$ in 1..n exists $y \leq z$ such that $TM_k(y)$ doesn't halt. Informally you can simulate the $n$ TMs on inputs $1..z$ being sure that those who halts are the only TMs that always halts on all inputs.

Perhaps the same reasoning can be applied to points 2. and 3.


Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?

First of all, Cook actually showed that the problem of whether a logical expression is a tautology is $\mathbb{NP}$-complete under Cook reductions. The proof however works by replacing them with Karp reductions to show that $SAT$ is $\mathbb{NP}$-complete, in the modern sense of the term.

As for whether Cook understood the significance of a $\mathbb{NP}$-complete problem not being in $\mathbb{P}$, going through the actual paper  shows that he did. However, I believe it wasn't until Karp's list of 21 complete problems that the practical significance of Cook's result began to be understood.


Quanitifier Free Presburger Arithmetic: Upper bound on solution size?

You can find an answer in the following paper:

Joachim von zur Gathen, Malte Sieveking. A bound on solutions of integer linear equalities and inequalities.
Proc. AMS 72(1) (1978)
(pdf)

A simple corollary of their result follows.
Let's say we have two integer systems, $A x = b$ and $C x \ge d$,
where you want $x$ to be in $\mathbb Z^n$.
Consider determinants of all square submatrices of the matrix $E = \left(\matrix{A & b \\ C & d}\right)$
and denote by $M$ an upper bound on their absolute values.
(In other words, set $M$ to be larger than or equal to the absolute value of all minors of $E$.)
Now, if there exists an $x \in \mathbb Z^n$ satisfying both $A x = b$ and $C x \ge d$, then
there exists such an $x$ whose components are at most $(n + 1) M$ in absolute value.

It remains to note that a determinant of a $k \times k$-matrix $S$ is at most $k!\, \|S\|_{\mathsf{max}}^k$
where $\|S\|_{\mathsf{max}} = \max |s_{i j}|$. Combining these two bounds will give a specific polynomial
bound on the size of a smallest solution (and this is already an easy exercise).


Ehrenfeucht-Fraïssé games (Ajtai-Fagin in fact) for regular languages.

We will give a winning strategy for Delilah. Let Samson choose his $c$ and $m$. Then Delilah chooses $w = a^n b^n$ for a large $n$ to be determined later. Let Samson choose his subsets $C^w_1,\ldots,C^w_c$ which we view as a coloring of the positions of $w$ with $2^c$ colors. Let $w'$ denote this colored word. The goal of Delilah at this point is to find a segment $w'[i,\ldots,j]$ of $w'$ with the following properties for an $r$ and a $t$ to be chosen later:

$0 \leq i \leq j \leq n$ (thus the segment belongs to the first part of $w'$),
the $r$-neighborhoods (neighborhoods of radius $r$) of $i$ and $j$ in $w'$ are isomorphic,
for every $k \in [i,\ldots,j]$, the $r$-neighborhood of $k$ in $w'$ appears as $r$-neighborhood of at least $t$ other positions of $w'$.

If she manages to do that, then she will choose her colored word to be
$$
v' = w'[0,\ldots,i-1] w'[i,\ldots,j]^2 w'[j+1,\ldots,2n-1].
$$
If $v$ is the ${a,b}$-word underlying $v'$, it will follow that $v$ does not belong to $L$ (because we pumped a non-empty segment of $a$'s), and Delilah has a winning strategy in the $m$-turn EF game on $w'$ and $v'$ (this follows from Hanf's Theorem if $r$ and $t$ are sufficiently large with respect to $c$ and $m$; see Theorem 1.4.1 in Ebinghaus and Flum book "Finite Model Theory").

Thus, it remains to show that if $n$ is sufficiently large with respect to $c$, $m$, $r$ and $t$ we can find a segment $w'[i,\ldots,j]$ as above. But this follows from a standard pigeonhole argument using the fact that the number of ismorphism types of $r$-neighborhoods is finite.

This worked for successor structures. With a linear order it will be a bit harder but I didn't think much about it.

Note that, not surprisingly, this argument looks a bit like "pumping" argument in automata. However, it is not as silly as just translating the formula to an automaton. I think it counts as a model-theoretic argument.


Is this a weaker or stronger form of the halting problem

The standard proof that the halting problem $L$ is undecidable also gives an efficient algorithm for constructing an instance on which a given Turing machine $H$ fails to solve the halting problem.
For any Turing machine $H$, let $M_H$ be a Turing machine implementing the following algorithm: "On input $\langle P \rangle$ where $P$ is a Turing machine, run $H(\langle P, P \rangle)$. If it outputs $1$, run forever, otherwise halt."
By design, $H(\langle M_H, M_H \rangle)$ fails. Either it runs forever, or else it halts and gives the wrong answer to the question of whether $\langle M_H, M_H \rangle \in L$. Given $\langle H \rangle$, one can efficiently construct $\langle M_H, M_H \rangle$.


Are there any annotated formal verification systems for pure functional programming languages?

You might want to check out Liquid Haskell, which allow working with type refinements rather than dependent types. Type refinements can be seen as a restricted logical language that allow you to express Hoare-style properties of the inhabitants of various datatypes. Another possible candidate is the $F^*$ language, which offers similar constructs.

There seems to be a close correspondence between refinement types and the ACSL like notations.

Finally I can only suggest taking a closer look at Agda and Idris, as they can compile to Haskell, and are aimed at providing the user with a usable programing language (especially Idris). I suspect it's possible to integrate Haskell libraries into Idris code without too much trouble.


Obviously there is an operational semantics of Ltac by Jedynak et al.


Is there a space efficient way to represent numbers on the lambda calculus?

If I am not mistaken the simulations between Turing machines and $\lambda$-calculus can be accomplished with a polynomial-time slowdown. Of course, for this to make sense we need to specify an evaluation strategy and measure of cost for $\lambda$-calculus but I am sure something reasonable can be found.

You ask about numbers in particular. Of course Church encodings are inefficient but they are only one possibility. In $\lambda$-calculus we can encode finite lists and the constants true and false. With these numbers can be encoded in binary as lists of boolean values, which gives an efficient representation. The charm of Church encodings is in their elegance.


Hard gaps in maximum constraint satisfaction problems?

Prasad Raghavendra in the STOC'08 best paper proved a dichotomy conjecture for approximating Max-CSP assuming the Unique Games Conjecture. This is not how he presented it originally, but he did give talks presenting things this way a couple of years later, e.g., at the IAS, where it was videotaped:
http://www.math.ias.edu/seminars/abstract?event=36669

The difference from showing SNP-hardness is that here we talk about quantitatively optimal results.


Why are NPI problems not all of the same complexity?

You cannot show that a problem is $\mathsf{NPI}$ without separating $\mathsf{P}$ from $\mathsf{NP}$.

There are artificial problems that can be proven to be in $\mathsf{NPI}$ using generalizations of Lander's theorem (also see this) assuming that $\mathsf{NP}\neq\mathsf{P}$.

Also padded version of $ \mathsf{NEXP\text{-}complete} $ problems are $\mathsf{NPI}$ assuming $ \mathsf{NEXP} \neq \mathsf{EXP} $ (see also this and this).

A problem in $\mathsf{NP}$ is often conjectured to be $\mathsf{NPI}$ when:

we can show under reasonable assumptions that it is not $\mathsf{NPC}$ yet it is not known to be in $\mathsf{P}$,
we can show under reasonable assumptions that it is not in $\mathsf{P}$ yet it is not known to be in $\mathsf{NPC}$,

and sometime just when we cannot show that it is in $\mathsf{NPC}$ or $\mathsf{P}$.

An example of a reasonable assumption is the exponential time hypothesis (or some of other computational hardness assumptions).

  Basically what I am asking is why would a problem that can be satisfied in polynomial time (if at all) but not solved in polynomial time (as long as P doesn't equal NP) not be polynomial time reducible to each other.

I don't see why one would expect that to be true. But in any case, assuming $\mathsf{NPC}\not \subseteq \mathsf{P}$ it follows from Lander's theorem that there are infinitely many levels of $\mathsf{P}$-degrees between $\mathsf{P}$ and $\mathsf{NP}$.


A reference for a "more algebraic" approach to pushdown automata and CFLs?

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

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

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


Smooth Complexity of the Nonnegative Permanent

Lipton (New directions in testing, 1991) showed that if the permanent is easy
for most matrices, then it is easy for all matrices. I do not know an online version but you can find the result in many lecture notes, for instance here:
http://www.cse.cuhk.edu.hk/~andrejb/courses/f07-80240233/notes/lec16.pdf
There are improvements by Gemmel and Sudan (IPL 43(4): 169-174. 1992).
So the permanent is hard on the average for the uniform distribution.
For a smoothed polynomial time algorithm you have to choose the distribution in such a way that this average-case hardness is circumvented.


Can the optimal minimum cost two-commodities flow be fractional on this special case?

Even, Itai, and Shamir proved that the undirected integral two-commodity flow is NP-hard even if all capacities are one. As far as I understand, the following is an example of what you ask for. It has a fractional solution twice as large as the integer one (All edge capacities are one. The costs don't really matter, as they only come in play to break ties between several optimum flows.):


Graph embedding which maximizes minimum angle

I don't think any such algorithm is known. The results I know about maximizing the minimum angle in straight line drawings of planar graphs are:

Every planar graph has a (possibly nonplanar) drawing in which the minimum angle is inversely proportional to the maximum degree. For the main proof idea and some references, see http://11011110.livejournal.com/230133.html
There exist planar graphs of degree d such that the minimum angle in any straight line planar drawing is $O(\sqrt{(\log d)/d^3})$. This result is due to Garg and Tamassia, "Planar drawings and angular resolution: algorithms and bounds", ESA '94. They also show that achieving near-optimal angles with a grid drawing may require a grid of exponential area.
Every planar graph has a planar drawing in which the minimum angle is bounded by a function of its degree. This can be shown using the Koebe-Andreev-Thurston circle packing theorem. For a reference to a slightly stronger version of this result (showing that every planar graph of bounded degree has a planar drawing with a bounded number of edge slopes) see http://11011110.livejournal.com/205447.html


jflap is pretty nice and can do this. See here: http://www.cs.duke.edu/csed/jflap/.


Is the cutting lemma true with O(r) lines?

If the $O(r)$ lines you choose must be drawn from the original set of $n$ lines then the answer is no, it's not possible. In particular if you take $n$ lines tangent to a circle, and then choose any $r$ of them, the region containing the circle will still be intersected by all $n$ of the lines.


How are imperative languages more different from each other than functional languages?

Simon is basically correct, from an extensional point of view. We know pretty well what the semantics of modern functional languages are, and they really are relatively small variations of one another -- they each represent slightly different translations into a monadic metalanguage. Even a language like Scheme (a dynamically typed higher-order imperative language with first-class control) has a semantics which is pretty close to ML and Haskell's.

From a denotational point of view, you can start by giving a pretty simple domain equation for the semantics of Scheme -- call it $V$. People could and did solve equations like this in the late 70s/early 80s, so this isn't too bad. Similarly, there are relatively simple operational semantics for Scheme as well. (Note that when I say "Scheme", I mean untyped lambda calculus plus continuations plus state, as opposed to actual Scheme which has a few warts like all real languages do.)

But to get to a category suitable for interpreting modern typed functional languages, things get quite scary. Basically, you end up constructing an ultrametric-enriched category of partial equivalence relations over this domain. (As an example, see Birkedal, Stovring, and Thamsborg's "Realizability Semantics of Parametric Polymorphism, General References, and Recursive Types".) People who prefer operational semantics know this stuff as step-indexed logical relations. (For example, see Ahmed, Dreyer and Rossberg's "State-Dependent Representation Independence".) Either way, the techniques used are relatively new.

The reason for this mathematical complexity is that we need to be able to interpret parametric polymorphism and higher-order state at the same time. But once you've done this, you're basically home free, since this construction contains all the hard bits. Now, you can interpret ML and Haskell types via the usual monadic translations. ML's strict, effectful function space a -> b translates to $\left<a\right> \to T\left<b\right>$, and Haskell's lazy function space translates to $\left<a\right> \to \left<b\right>$, with $T(A)$ the monadic type of side effects interpreting the IO monad of Haskell, and $\left<a\right>$ is the interpretation of  the type ML or Haskell type a, and $\to$ is the exponential in that category of PERs.

So as far as the equational theory goes, since these languages can both be described by translations into slightly different subsets of the same language, it is entirely fair to call them syntactic variations of one another.

The difference in feel between ML and Haskell actually arises from the intensional properties of the two languages -- that is, execution time and memory consumption. ML has a compositional performance model (i.e., the time/space cost of a program can be computed from the time/space costs of its subterms), as would a true call-by-name language. Actual Haskell is implemented with call-by-need, a kind of memoization, and as a result its performance is not compositional -- how long an expression bound to a variable takes to evaluate depends on whether it has been used before or not. This is not modelled in the semantics I alluded to above.

If you want to take the intensional properties more seriously, then ML and Haskell do start to show more serious differences. It is still probably possible to devise a common metalanguage for them, but the interpretation of types will differ in a much more systematic way, related to the proof-theoretic idea of focusing. One good place to learn about this is Noam Zeilberger's PhD thesis.


Formal Methods Applied to Role-Based Security (RBAC)

My knowledge is a bit stale, as I haven't actively researched this field in the last couple of years. None of these is probably the state of the art, but a good place to start looking backwards (i.e., chase references) and forwards (i.e., see who cites it).

If you're looking into information flow (making sure classified information doesn't leak to untrusted roles), a reasonable place to start is Martin Abadi et al's Dependency Core Calculus. I think it's reasonable enough that anyone who does formal methods in the area would refer to it (directly, or once removed).

If you're looking into access control/authorisation (role A says role B controls the data, role B says you can access the data, etc.), Abadi recently published a tutorial book chapter on the subject, so might be a good place to start.

If you're looking into authentication (whether the agent saying he is A is indeed A), I defer to someone else. I'll try to have a look later.


Tarjan Strongly Connected Components Question

v.lowlink = min(v.lowlink, v'.index) in line 16 is indeed correct. For a full proof you can consult Tarjan's original paper which can also be found here.

  Robert Tarjan: Depth-first search and
  linear graph algorithms. In: SIAM
  Journal on Computing. Vol. 1 (1972),
  No. 2, P. 146-160.

Completely unrelated to the question, there is an amusing 1983 retrospective by Bob Tarjan here on the paper cited above.


Efficient generation of permutational invariant quantum states

Yes, they can. Recall that any reversible classical function can be computed in superposition. Now, generate the state
$$
\frac{1}{\sqrt{n!}}\left(\sum_{i=1}^n |i \rangle \right) \left( \sum_{i=1}^{n-1} |i \rangle \right)\left(\sum_{i=1}^{n-2} |i\rangle \right) \ldots \left(\sum_{i=1}^2 |i\rangle \right) \bigg(| 1\rangle \bigg) . $$
This is the superposition of all sequences where the $i$'th position contains a number between 1 and $n+1-i$. It's easy to generate because it's a tensor product of $n$ registers.

Then, find a reversible classical mapping from these sequences to permutations. One way of doing this is as follows. If there is an $i$ in the $t$'th position, take the $i$'th unused number available for the permutation. For example: suppose we have the sequence 24211. This gets mapped to the permutation as follows:

$$\begin{array}{r|l}
24211 & \ \ \ \emptyset \\
4211 & 2 \\
211 & 25 \\
11 & 253 \\
1 & 2531 \\
\emptyset \ \ \  & 25314
\end{array}
$$
To illustrate, the third element of the permutation is $3$ because at the third step, the available numbers are $1$, $3$, $4$, ($2$ and $5$ are already in use) and the second of these is $3$. You can easily check that each of these steps is a reversible computation, and so implementable in superposition on a quantum computer.


Historic Relationship between Typed Lambda Calculus and Lisp?

First, your friend is wrong about the history of the $\lambda$-calculus. Church created the untyped calculus first, which he intended as a foundation for mathematics. Fairly quickly, it was discovered that the logic derived from this calculus was inconsistent (because non-terminating programs existed).  Eventually Church developed the simple theory of types as well, and many other things besides, but that wasn't the original point of the system.

An excellent overview of the history is found in this paper.

Second, the simply-typed lambda calculus is a quite restrictive language. You need some form of recursive type to write any interesting kind of program in it. Certainly, it would be impossible to write the kinds of programs in McCarthy's original paper with the $\lambda$-calculi based type systems understood in 1958. Cutting-edge programming type systems at that point were the ones found in Fortran and COBOL.


Difference between time-bounded and memory-bounded Kolmogorov complexity

Assume that there exists a sparse set $L \in \mathbf{NP} -\mathbf{P}$, this is equivalent to $\mathbf{EXP}\not= \mathbf{NEXP}$.

Then we can construct such a sequence. Indeed, consider $L_n = \{l_1,\ldots, l_k\} = L \cap \{0,1\}^n$.

Denote by $s_i$ the lexicographically first certificate for $l_i$.

Define $x_n$ as the list of pairs: $ x_n:= \{ (l_1, s_1), \ldots, (l_k,s_k)\}$.

Certainly, $C_{\mathsf{poly}(n)}(x_n) = O(\log n)$. Let us show that $C^{\mathsf{poly}(n)}(x_n) > c\log n$ for every $c$.

Indeed, otherwise there exists a polynomial-time algorithm calculating   all strings of complexity  at most $c\log n$ (including $x_n$). Hence we can verify that a string belongs to $L$ in polynomial time.


Is the set of Multiplicative Proof Nets a proper subset of set of well formed single-agent Interaction Nets?

Your observation about cut-elimination being faithfully represented in the unlabelled interaction nets is correct.  However, the answer to your question is no.

Let us call $\delta$ the unique agent of the system. Such an agent is binary; we distinguish its two auxiliary ports by referring to as left and right. We call cell an occurrence of the agent in a net. The interaction rule between two $\delta$ cells $c$ and $d$ is as follows: the two cells disappear and two wires are created, each connecting that which was the left (resp. right) port of $c$ to the left (resp. right) port of $d$.

Consider now the net $\mu$ composed of two $\delta$ cells, call them $c$ and $d$, such that:

their principal ports are connected by a wire (there is a cut);
the right auxiliary port of $c$ is connected by a wire with the left auxiliary port of $d$ (there is an axiom between them);
the other two auxiliary ports (the left of $c$ and the right of $d$) are free (in proof net syntax, this means they are connected with two axioms with one free conclusion each).

Observe that $\mu$ reduces in one step to a wire (in proof nets syntax, the net reduces in two steps to an axiom).  So the result certainly has no vicious circle.  However, the only sensible way to label $\mu$ (by "sensible" I mean avoiding ill-typed things like a cut between two tensors or between two pars) is to label one delta cell with a tensor and the other with a par, obtaining a net which is not correct: there is a "bad" cycle going through the cut and the axiom connecting the auxilary ports of $c$ and $d$.


When we say a parameter is good for a problem?

In my opinion, this is actually one of the main questions in parameterized algorithms. There is a number of articles that discuss the "art" of problem parameterization, I list a few of them below.

In a nutshell, an ideal parameter $k$ for a problem should give you two things:

The problem is fixed-parameter tracable for parameter $k$ with a good running time dependence on $k$. That is, it can be solved in $f(k)\cdot n^{O(1)}$ time for some moderately exponential function $f$.
The value of $k$ is small in typical instances of this problem.

Most of research in parameterized algorithms focuses on the first issue. The second issue is not really treated in a systematic empirical fashion I'd say. That is, there are no comprehensive studies measuring the value of parameters in real-world instances. What people do to justify the study of particular parameters is to systematically compare parameter values. For example, one may say that a fixed-parameter algorithm for a parameter $k$ is more useful than a fixed-parameter algorithm for parameter $\ell$ if $\ell>k$ in many instances and $\ell\ge k$ in all instances. Using these relations between parameter values one may navigate through parameter space to obtain useful fixed-parameter algorithms.

For example, if you have shown that a graph problem with input graph $G$ is fixed-parameter tractable for the parameter vertex cover number $\mathrm{vc}(G)$ you may want to show that it is fixed-parameter tractable for the parameter feedback vertex set number $\mathrm{fvs}(G)$ because  $\mathrm{fvs}(G)\le \mathrm{vc}(G)$ in all graphs. If this is the case, then you may want to show that the problem is fixed-parameter tractable for the treewidth $\mathrm{tw}(G)$ of the graph since $\mathrm{tw}(G)\le \mathrm{fvs}(G)+1$ in all graphs and so on.

Some references:

Michael R. Fellows, Bart M. P. Jansen, Frances A. Rosamond:
Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3): 541-566 (2013)
Rolf Niedermeier:
Reflections on Multivariate Algorithmics and Problem Parameterization. STACS 2010: 17-32
Christian Komusiewicz, Rolf Niedermeier:
New Races in Parameterized Algorithmics. MFCS 2012: 19-30


Constant Width Max Sum Product Multi-objective Shortest path problem

For K=2, PARTITION reduces to this problem, so it is NP-hard.

Take an instance of PARTITION: a list of nonnegative integers $x_1,\dots ,x_n$, and you ask if there is a subset $I\subseteq [1,n]$ such that $\sum_{i\in I} x_i=\sum_{i\notin I}x_i$.

Let $S=\sum_{i\in[1,n]} x_i$, and $y_i=\exp(-\frac{x_i}S)$ for each $i$. Note that $y_i\in (0,1)$.

You build a graph with $n+1$ nodes $p_1,\dots ,p_n,p_{n+1}$.
You have two edges from $p_i$ to $p_{i+1}$: one with weight $(\frac{y_i}2,\frac12)$ and the other with weight $(\frac 12,\frac{y_i}2)$. The division by $2$ is there to ensure the additionnal constraint that the sum of coordinates is at most $1$.

A path from $p_1$ to $p_{n+1}$ corresponds to a partition $I$: you end up with the vector $$\big(\dfrac{\exp(-\frac1S\sum_{i\in I} x_i)}{2^n}~,~ \dfrac{\exp(-\frac1S\sum_{i\notin I} x_i)}{2^n}\big).$$
Since the minimum of $e^{-x}+e^{-(1-x)}$ is reached for $x=1/2$, there exists a path of weight $\exp(-1/2)/2^{n-1}$ if and only if there was a balanced Partition of the initial integer list.


The most recent issue of the CACM has an article by Faliszewski, Hemaspaandra and Hemaspaandra on the use of complexity theory in the realm of social choice theory and election design in particular. One example of such a result is that while Arrow's theorem guarantees that any election system is 'hackable', it might be NP-hard to do so.


Shortest cycle separator for biconnected planar graphs

This doesn't seem to be possible, at least not without finding the right notion of "easy".

Consider a graph formed by taking a grid graph with $k$ rows and $l+1$ columns, and identifying the leftmost column of vertices with the rightmost column of vertices. Here, we have $n = kl$ vertices, and we're interested in $k \le l$. The graph is planar, and has treewidth at least $k$, as it has a $k\times k$ grid graph as a minor.

Additionally, a cyclic separator achieving constant $f$ in this graph seems to need $\Omega(l)$ vertices (where the constant depends on $f$). Imagine the graph drawn on a cylinder of circumference $l$ and height $k$, where the graph forms an equally spaced grid on the surface of the cylinder. Then if a cyclic separator has length less than $l$, it cannot "go around" the cylinder. Hence a cyclic separator gives a way to find a region in a $k\times l$ rectangle whose perimeter is the length of the separator, and whose area is at least a constant ($1-f$) fraction of the whole rectangle's area. I don't know the exact isoperimetric inequality for this, but it seems like such a region would need perimeter $\Omega(l)$ in order to have enough area and fit into the rectangle.

Thus we have a graph with treewidth $k$ and whose separators need to be of size $\Omega(l)$. Choosing parameters like $k = n^\epsilon$ and $l = n^{1-\epsilon}$, we thus see that a cyclic $(s,f)$-separator for constant $f$ needs to have $s = \Omega(n^{1-\epsilon})$, even for graphs with treewidth $n^\epsilon$.


Most CS conference publications use the ACM BibTeXstyle file (or the plain style file) to cite papers, and that constitutes the de facto 'style'. Different journals and conferences often prescribe their own citation format via a different BibTeX style.

So the short answer to your question is that there isn't a common style, and if you believe in using BibTex, then merely changing the style file can allow you to accommodate different styles.


The construction you suggest does work, but it is not optimal. The reason why people use the sphere with a constant expansion is that then a $\sqrt{\epsilon}$-net is enough. That reduces the size of the coreset from $O(1/\epsilon^{d-1})$ to $O(1/\epsilon^{(d-1)/2})$. To see that replacing $\epsilon$ by $\sqrt{\epsilon}$ in your construction does not work, consider the case of a regular triangle (or simplex) where only points within distance roughly $\sqrt{\epsilon}$ of the vertices are sampled.


Are there common names for the subtiers of PTIME?

As complexity classes LIN, QUAD, CUB etc are not well-behaved, and not easy to handle.

In the definition, you must freeze the model of computation (that is, deterministic Turing machines with one tape). So you will do complexity theory in a single artificial model.
The definition of these classes is fragile: In contrast to our standard complexity classes, the classes LIN, QUAD, CUB do not remain stable if you move to other models, like RAMs or Turing machine with two tapes.
There also is no natural reduction concept available on LIN, QUAD, CUB (except for reductions that are equally strong as the class itself).

Summary: All in all this means trouble, and the classes are not very appealing.


What's the complexity of recognizing equivalence for the following relation?

The recognition problem is equivalent to the graph isomorphism (recognition) problem, and the invariant problem is equivalent to the graph isomorphism invariant problem.

To reduce the current problem to graph isomorphism, given an m×n matrix A, let S be the set of integers which appear as an entry of A at least once.  We construct a graph G(A) with m+mn+|S| labeled vertices as follows.

For each row i, the graph has a vertex ui labeled as “row.”
For each cell (i, j), the graph has a vertex vij labeled as “cell in column j.”
For each integer k∈S, the graph has a vertex wk labeled as “entry.”
For each cell (i, j), connect ui and vij by an edge, and connect vij and waij by an edge.

Then it is not hard to see that two matrices A and B are equivalent in the sense stated in the question if and only if there is an isomorphism between G(A) and G(B) which preserves labels.  But the isomorphism problem of vertex-labeled graphs is known to be equivalent to the isomorphism problem of usual, unlabeled graphs.

To reduce graph isomorphism to the current problem, given a graph G=(V, E), consider each edge as two directed edges, and construct a 2|E|×2 matrix M(G) by writing the two endpoints of each directed edge in one row.  Then again it is not hard to see that two graphs G and H are isomorphic if and only if M(G) and M(H) are equivalent in the sense stated in the question.


Take the formula in your example, remove the clause $\lnot A \lor \lnot B \lor \lnot C$ and add the following $2$ clauses:

$\lnot A \lor \lnot B \lor \lnot E$
$\lnot B \lor \lnot C \lor E$

You will get a minimal unsatisfiable formula with $n=5$, $m=9$ obeying condition 5.

In general, you may randomly pick a clause $l_1 \lor l_2 \lor l_3$ and split it in $2$ clauses:

$l_1 \lor l_2 \lor v$
$l_2 \lor l_3 \lor \lnot v$

where $v$ is a new variable. Each time you do so, both $n$ and $m$ are incremented by $1$. Repeating this process allows you to "stretch" the initial unsatisfiable core, and to obtain minimal unsatisfiable formulas (obeying condition 5) whose $r=\frac{m}{n}$ tends to $1$ as $n$ grows (which is pretty rare, as formulas with $r=1$ are satisfiable with high probability).


Is the wording of Google's QC Supremacy valid?

You should read the new post by Aaronson, but until then the short answers:

No.
If you can realize it in a real world machine, then it would (if no one finds a fast, classical algorithm until then).
You don't prove anything. It's a practical fact, like AI playing chess better than humans. If a chess genius is born, (s)he might win back the crown for humanity!


Big gaps between RAM and Turing machine complexity

It is known that any problem that you can compute on a RAM machine in time $T(n)$, you can do it in a Turing Machine in time at most $T(n)^2$. You need to notice that the total size of the memory used can not be more than $T(n)$, since that would mean that you did more write operations than $T(n)$, so each time you fetch something from RAM memory, the Turing machine would take in the worst case $T(n)$ time to find the desired element sequentially from the tape. Besides memory access, the rest of operations should take around the same time. And thus you get the bound.


Are there interesting graph classes where the treewidth is hard (easy) to compute?

Treewidth is NP-hard to compute on co-bipartite graphs, indeed the original NP-hardness proof of treewidth of Arnborg et al. shows this. Additionally, Bodlaender and Thilikos showed that it is NP-hard to compute the treewidth of graphs of maximum degree $9$. Finally, for any graph of treewidth at least $2$, subdividing an edge (i.e, replacing the edge by a degree $2$ vertex adjacent to the two edge endpoints) does not change the treeewidth of the graph. Hence it is NP-hard to compute treewidth of bipartite 2-degenerate graphs of arbitrarily large girth.

The problem is polynomial time solvable on chordal graphs, permutation graphs, and more generally on all classes of graphs with a polynomial number of potential maximal cliques, see this paper by Bouchitte and Todinca. Note that in the same paper it is shown that the set $\Pi(G)$ of potential maximal cliques of a graph $G$ can be computed from $G$ in time $O(|\Pi(G)|^2 \cdot n^{O(1)})$. Also, Bodlaender's algorithm determines whether $G$ has treewidth at most $k$ in time $2^{O(k^3)}n$. Hence, treewidth is polynomial time solvable for graphs of treewidth $O((\log n)^{1/3})$.

It is an outstanding open problem whether computing the treewidth of planar graphs is polynomial time solvable or NP complete. It is worth noting that the related graph parameter branchwidth (which is always within a factor 1.5 away from treewidth) is polynomial time computable on planar graphs.


Question on ascending $k$-tuples of naturals whose sum is less or equal than $S$

Let's add one more number $x_{k+1} = S - \sum_i{x_i}$ and assume none of the $x_i$ is zero. Now $(x_1, \ldots, x_{k+1}$) is what is called an $k+1$-part integer partition of $S$. So your tuples are integer partitions of the numbers $0, \ldots, S$ into at most $k$ parts (at most because some $x_i$ could be 0).
Counting partitions is a big topic but a recurrence is not very hard to formulate. Let $q(n,k)$ be the number of partitions of $n$ into at most $k$ parts. The number of your tuples is then $1 + \sum_{n = 1}^{S}{q(n, k)}$. For the recurrence you have two cases:

a) There are $k$ nonzero $x_i$. Then if you subtract one from each $x_i$ you get a partition of $n-k$ with at most $k$ parts. So there is a bijection between partitions of $n$ with exactly $k$ parts and partitions of $n-k$ with at most $k$ parts.

b) There are less than $k$ nonzero $x_i$. The number of such tuples is $q(n, k-1)$.

The recurrence you get is $q(n, k) = q(n-k, k) + q(n, k-1)$. The initial conditions are $q(0, k) = 1$ and $q(n, 0) = 0$ for $n>0$.

As to 3., I think $q(n, k)$ is at least on the order of $n^k$ which would imply that there aren't very succinct representations.


Keyword selection problem in search engine marketing auction

In the most basic form this can be viewed as a learning problem: each keyword gives some profit (taking into account CTR, conversion rate, prices, etc.) which is not known and needs to be learned.  More or less a Multi-armed bandit problem.


Upperbound the order of P3-free partition of P4-free graphs

I update my reply in light of Aravind's comment. The claim in my previous answer was clearly incorrect but, in my defence, I never had a good intuition about graphs.

By adapting Aravind's argument you can show an upper bound of $O(\sqrt{n})$, as every $n$-vertex perfect graph has an independent set or a clique of size $\sqrt{n}$. It should be possible to show the tightness of the bound by reasoning on the tree-representation of the cograph. Consider for instance a complete binary tree $T$ with $N = 2^n$ vertices, and label its nodes as series/parallel in an alternating fashion. It represents a cograph $G$, and any $P_3$-free subgraph $H$ of $G$ must span a subtree of $T$ that does not contain three alternations along a root-leaf path; it should imply that this graph may have at most $O(\sqrt{N})$ vertices, but I leave the details to you.

A related question would be to look for a partition in bicluster graphs, as they are exactly the bipartite $P_4$-free graphs. Observe that this problem can be solved in polynomial time by computing the chromatic number of the graph: an arbitrary pairing between color classes then gives the optimal partition.


Time-entanglement means that quantum information from the past may be teleported into the future without actually being present in the interval between. However, teleportation of one qubit requires two classical bits and one EPR pair, and these must exist in the interval, so there is no saving of space: you need to get half of the EPR pair and both classical bits into the future, and that requires a qubit's worth of quantum memory. So this process does not effect complexity classes.


Advice for a mathematician trying to present a paper at a CS conference?

First and foremost, stay on time.

Usually, at conferences you are supposed to talk for a very limited amount of time, e.g. 25 minutes including 5 for questions. In such slot you will not be able to go deep into the technical details.

You should have a more "marketing" approach to presenting a paper. You have to convince the attendants about:

what your main results are
why your results are important
why later on one should spend some time to actually read your paper

Try to be simple and direct. Most attendees will also have spent part of their mental energy on previous presentations. Chances are they will forget about your paper very soon (there are too many to remember for a human mind!). Your goal is to make them to remember something about your paper.

Leave the proofs out. You can briefly mention the proof technique if relevant, though ("by reduction to problem XYZ").
Provide the definitions and statements -- if they are very technical, you can be a bit vague ("under some regularity conditions..."). Clarity trumps precision here. Provide some background for people not in the field, but do not waste time in reviewing basic definitions. Here it is important to know what the audience is familiar with, which depends on the venue. E.g. in a TCS conference, everyone knows what a non-deterministic Turing machine is.

Write and use a few (computer) slides -- you can't waste time writing on a blackboard, and most venues will expect you to have a computer presentation ready. Bring your laptop to the presentation. For a 25 minutes talk, use around 20 slides. Beforehand, make a pretend presentation in your office, and use a timer to check you can do it on time. Optionally, you can take some notes about what to say on each slide, and use these notes during the talk.

Sum up the main points in the last slide to help people remember your talk.

Expect at least a question at the end. Sometimes a question can be not very relevant since the audience may not have grasped everything. Politely answer that anyway.

The goal of the 3-pages short abstract is similar: to convince people that your results are interesting, and that they should read the full version. Try to summarize the main points, trying to convey the general idea even if the space does not allow a proper discussion. Avoid the technical parts which are not needed to assess your results.


Positivstellensatz and sum of squares method

As already noted in the comments, the question is based on a misunderstanding; the actual Positivstellensatz is a stronger statement than Artin’s theorem on nonnegative polynomials, and the real Nullstellensatz as stated in the question is indeed its special case.

Other comments asked for lecture notes with a proof of the Positivstellensatz, and as I do not know of any, I can as well write it myself.

The overall strategy of the proof below is similar to the model-theoretic proof of Hilbert’s Nullstellensatz; I will use the facts that each ordered field embeds in a real-closed field, and the theory of real-closed fields has quantifier elimination.

First, some notation. Let $F$ be an ordered field, and $f_1,\dots,f_n\in F[x_1,\dots,x_m]$ polynomials.

$I(f_1,\dots,f_n)$ denotes the ideal generated by $f_1,\dots,f_n$, i.e., polynomials of the form $f_1g_1+\dots+f_ng_n$ for some $g_1,\dots,g_n\in F[x_1,\dots,x_m]$.
$\Sigma$ denotes the set of polynomials of the form $\sum_{i=1}^na_ig_i^2$, where $n\ge0$, $g_i\in F[x_1,\dots,x_m]$, and $a_i\in F^+$. (If every positive element is a sum of squares, such as for $F=\mathbb R$, then $\Sigma$ just consists of sums of squares of polynomials.)
$C(f_1,\dots,f_n)$ is the set of polynomials of the form

$$\sum_{I\subseteq[n]}s_I\prod_{i\in I}f_i,$$

where $s_I\in\Sigma$. That is, $C(f_1,\dots,f_n)$ is the least set of polynomials that contains the $f_i$’s, squares, and positive constants, and is closed under $+$ and $\cdot$.

  Theorem (Positivstellensatz): Let $F$ be an ordered field, $R\supseteq F$ a real-closed field, and $f_1,\dots,f_r,g_1,\dots,g_s,h_1,\dots,h_t\in
F[x_1,\dots,x_m]$. The following are equivalent.

  The system $\{f_i(\vec x)\ge0,g_j(\vec x)=0,h_k(\vec x)\ne0:i\in[r],j\in[s],k\in[t]\}$ has no solution $\vec a\in R^m$.
  $-(h_1\cdots h_t)^{2n}\in C(f_1,\dots,f_r)+I(g_1,\dots,g_s)$ for some $n\in\omega$.

We could also accommodate strict inequalities $p_i(\vec x)>0$ by including $p_i$ among both the $f_i$’s and the $h_i$’s.

We will need

  Lemma: Let $S$ be a commutative ring, $u\in S$, and $P\subseteq S$ be such that

  $P$ is closed under $+$, $\cdot$, and contains all squares;
  $S=P-P$;
  $-u^{2n}\notin P$ for all $n\in\omega$.

  Then there is a homomorphism $\phi\colon S\to K$ to an ordered field $K$ such that $\phi(p)\ge0$ for all $p\in P$, and $\phi(u)\ne0$.

Proof of the Positivstellensatz:

$2\to1$: If $f_i(\vec a)\ge 0$ for $i=1,\dots,r$, then also $f(\vec a)\ge0$ for all $f\in C(f_1,\dots,f_r)$. Likewise, $g(\vec a)=0$ for all $g\in I(g_1,\dots,g_s)$. Thus, if $h=h_1\cdots h_t$ satisfies $-h^{2n}\in C(\vec f)+I(\vec g)$, then $0\le-h^{2n}(\vec a)\le0$, thus $h(\vec a)=0$, thus $h_i(\vec a)=0$ for some $i=1,\dots,t$.

$1\to2$: Assume 2 is false. Let $S=F[x_1,\dots,x_m]$, and $P=C(\vec f)+I(\vec g)\subseteq S$. Notice that every $s\in S$ is a difference of two squares, e.g., $s=\bigl(\tfrac12(s+1)\bigr)^2-\bigl(\tfrac12(s-1)\bigr)^2$. Since $-h^{2n}\notin P$ for all $n$, Lemma 1 gives a homomorphism $\phi\colon F\to K$, where $K$ is an ordered field, $\phi(P)\ge0$, and $\phi(h)\ne0$. We may assume $K$ is real closed. Since $P$ includes $F^+$, $\phi$ restricts to an ordered field embedding of $F$ in $K$; we may simply assume $F\subseteq K$. Then, putting $a_i=\phi(x_i)$, we have $f_i(\vec a)\ge0$, $g_i(\vec a)=0$, and $h_i(\vec a)\ne0$ in $K$. The existence of $\vec a$ with these properties can be expressed as a first-order formula with parameters from $F$; since this formula is true in $K$, quantifier elimination for real-closed fields implies it is also true in $R$.

Proof of the lemma:

Using Zorn’s lemma, let $Q\supseteq P$ be a maximal subset of $S$ closed under $+$ and $\cdot$ such that $-u^{2n}\notin Q$ for any $n\in\omega$.

Put $I=Q\cap(-Q)$. Since $Q$ is closed under $+$ and $\cdot$, $I$ is closed under $+$ and $-$, and we have $IQ\subseteq I$. Since $S=Q-Q$, this means $I$ is an ideal of $S$.

I claim that $S=Q\cup(-Q)$. Assume for contradiction that $a,-a\notin Q$ for some $a\in S$. As $a\notin Q$, $Q+aQ$ is a proper extension of $Q$ closed under $+$ and $\cdot$, thus by maximality of $Q$, we have $-u^{2n}=q+ar$ for some $n\in\omega$ and $q,r\in Q$. Likewise, $-a\notin Q$ gives $-u^{2m}=s-at$ for some $m$ and $s,t\in Q$. We have $-u^{2m}r\in-Q$, and $-u^{2m}r=sr-atr=sr+qt+u^{2n}t\in Q$, thus $u^{2m}r\in I$. It follows that $-u^{2(n+m)}=qu^{2m}+aru^{2m}\in Q+I\subseteq Q$, a contradiction.

I also claim that the ideal $I$ is prime. Assume for contradiction $ab\in I$, but $a,b\notin I$. Without loss of generality, $a,b\notin Q$. Thus, $-b\in Q$, and $-u^{2n}\in Q+aQ$ for some $n$, which implies $u^{2n}b\in-bQ-abQ\subseteq Q+I\subseteq Q$. Likewise, $-u^{2m}\in Q+bQ$ for some $m$, thus $-u^{2(n+m)}\in u^{2n}Q+u^{2n}bQ\subseteq Q$, a contradiction.

Thus, $S/I$ is an integral domain, and it is a (totally) ordered ring by making $Q/I$ its positive cone. Its fraction field $K$ is an ordered field, and the quotient map $\phi\colon S\to S/I\subseteq K$ has the required properties.


NP-completeness of a problem using a "T-gadget"

You're asking whether the underlying 3-regular graph has a Hamiltonian path, which is NP-complete.  Your activation signal must traverse every edge in this path exactly twice.

See also this question and this one.


$NP$-complete problem with quasi-polynomial bound on the number of solutions

This is a very interesting question.

First, a clarifying remark. Note that "upper bound on the number of witnesses" is not a property of a computational problem per se, but of a particular verifier used to decide an $NP$ problem, just as an "upper bound on number of states" would not be a property of a problem but of a Turing machine deciding it. So saying "$NP$ problem with upper bound on number of solutions" isn't quite accurate, and if $P = NP$ then every $NP$ problem has a verifier with any number of desired solutions (including zero, and including all possible strings).

So we have to make a definition, to address your question. For $s : {\mathbb N} \rightarrow {\mathbb N}$, let's say an $NP$ problem $L$ "has at most $s(n)$ solutions" if for some constant $c$ there is an $O(n^c)$ time verifier $V$ such that, for every input length $n$ and for every $x \in L$ of length $n$, there are distinct $y_1,\ldots,y_{s(n)}$ of length $n^c$ such that $V(x,y_i)$ accepts for all $i$, and $V(x,y)$ rejects all other $y$ of length $n^c$.

All I think I can say at the moment is this:

Every $NP$-complete problem I know (defined by some natural verifier) has an obvious corresponding $\#P$-complete counting version (with the same verifier).
For any $NP$-complete problem defined with a verifier having at most $poly(n)$ solutions (or even $2^{n^{o(1)}}$ solutions) the corresponding counting version probably isn't $\#P$-complete.

More details: Suppose $L$ is $NP$-complete, with a verifier $V$ that has at most $O(n^c)$ solutions. Then the natural counting "decision" version of $L$, which we define as

$Count_L(x) := \text{the number of $y$ such that $V(x,y)$ accepts}$

is computable in $FP^{NP[O(\log n)]}$, that is, a polytime function with $O(\log n)$ queries to $NP$. That is because deciding whether the number of solutions to $x$ is at most $k$ is in $NP$: the witness, if it exists, is simply the number of $y_i$'s making $V$ accept, which we know to be at most $O(n^c)$. Then we can binary search using this $NP$ problem to compute the exact number of solutions to $L$.

Therefore, an $NP$-complete problem of this kind could not be extended to a $\#P$-complete problem in the usual way, unless $\#P \subseteq FP^{NP[O(\log n)]}$. This looks unlikely; the whole polynomial time hierarchy would basically collapse to $P^{NP[O(\log n)]}$.

If you assume $s(n) = 2^{n^{o(1)}}$ in the above, you would still get an unlikely consequence. You would show that $\#P$ can be computed in $2^{n^{o(1)}}$ time with an $NP$ oracle. That's more than enough to prove, for instance, that $EXP^{NP} \neq PP$ and subsequently $EXP^{NP} \not\subset P/poly$. Not that those separations are unlikely, but it seems unlikely they'd be proved by giving a subexp time $NP$-oracle algorithm for the Permanent.

By the way, I have said nothing too insightful here. There is almost certainly an argument like this in the literature.


Hilbert's Tenth Problem and nonrecursive Diophantine sets

Looking at the paper, I believe that what Shlapentokh is saying is that "there is an undecidable Diophantine subset of $\mathbb Z$" is an immediate consequence of "there is an r.e. set that is not recursive" and the MRDP theorem, where by the "MRDP theorem" is meant "A set is Diophantine if and only if it is r.e."  Nothing deeper than that.


What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?

You can take any degree 3 bipartite graph $G$ and take its disjoint union $G'$ with a cycle $C$ of length 2m. The new graph $G'$ is bipartite, and has average degree $\frac{3n + 2m}{m+n} = 2 + \frac{n}{n+m}$. Also, the number of perfect matchings in $G'$ is exactly twice the number of perfect matchings in $G$, because the perfect matchings of $G'$ are the disjoint unions of a perfect matching of $G$ and a perfect matching of $C$, of which there are two. So, there is a polytime parsimonious reduction from counting perfect matchings in 3-regular bipartite graphs to counting perfect matchings in graphs with maximum degree 3 and average degree $2 + \frac{1}{\mathrm{poly}(n)}$.


Complexity of testing if a hypergraph has generalized hypertreewidth $2$

We do not know (to best of my knowledge).


Polynomial evaluation at all different points

This problem is in general #P-complete, as you can for example encode a SAT instance as a polynomial over GF(2) and reduce #SAT to this problem. So all the standard hardness results apply to this.
If you're happy with finding the fraction of evaluation points over which the polynomial vanishes, up to an additive constant $\epsilon$, then you can trivially evaluate at enough random points and take the empirical estimate.


Bounding the rate of increase of the price of anarchy across equilibrium concepts

The ratio between $POA(MN)$ and $POA(PN)$ can be arbitrarily large. Consider the following congestion game; we have $n$ players and $n$ items, and each player can choose any item. The cost to a player depends on the congestion of the item picked; it is $f(x)$ if $x$ players pick that item. $f$ will be a sharply growing function.

The only pure Nash has each player picking a unique item, so everyone pays $f(1)$. On the other hand, by symmetry, the randomized strategy where each player picks a uniformly random item is a mixed Nash. If $f$ grows steeply, the total cost will be much more expensive, since there is some chance that multiple players pick the same item.


Patience Sort+ ping pong merge implementation

I hope I understood correctly how the ping-pong merge worked. If so here is why it uses two arrays:

A typical merge operations takes two runs in an array and merges them in another arra; then, it copies the results back into the original array. When you have more than 2 runs to merge, you merge them pairwise into an array, then copy everything back to the original array, and repeat until there are no runs left.
The ping-pong merge merges runs pairwise into an array, then instead of just copying them back in the original array, it merges the resulting runs pairwise from the temporary array into another array, then to the first temporary array, then to the second one, etc... The goal is to avoid copying everything back to the original array after each series of pairwise merges.

Now, I guess that your question is actually "why does the ping-pong merge operate back and forth between two temporary arrays instead of merging runs pairwise in a single temporary array, then back to the original array, then back to the temporary array, etc...?"

Honestly, I only have one tentative explanation, and it's not really satisfying: I tend to implement algorithms in C++, and if I wrote the ping_pong_merge algorithm, it could take any pair of random-access iterators, which means that it could handle std::deque (a list of fixed-size arrays) as well as regular arrays. While std::deque has $O(1)$ element access, it is actually slower than std::vector in practice, so using two temporary arrays would ensure that the ping-pong merge only occurs between collections whose random-access is the fastest. This could be a memory vs. performance kind of problem.


How are safety/liveness languages defined on the set of finite or infinite words?

The answer is yes to all questions, so it is enough to answer 2 and 4, as the definitions work in particular for languages of finite words:

A language $P\subseteq \Sigma^*\cup\Sigma^\omega$ is safety if whenever $u\notin P$, then $u$ has a finite prefix $u'\in\Sigma^*$ such that for any word $v$, $u'v\notin P$.

A language $P\subseteq \Sigma^*\cup\Sigma^\omega$ is liveness if for any finite word $u\in\Sigma^*$, there is a word $v$ such that $uv\in P$.


Calculus of constructions: Why forall when pi exists?

It is false that the only well-typed occurrence of Prf has to be of the form Prf(all ...). For example, in the context with a variable p : Prop we can form the type Prf(p) which is not of the stated form. Another possibility is that we have a Prf(t) for some closed term t : Prop which is not of the form all ... but it normalizes to it.
The purpose of Prf is to decode, or coerce, the elements of Prop to types. That is, the elements of Prop are not actual types, so if we want to use them as if they were types, they first have to be coerced to types, which is what Prf does. The rule QT-All states that all decodes to Π.
To put it differently, Prop is a Tarski universe and Prf is the type family that decodes its elements as types.