About the decidability of sets enumerated in non decreasing order

Suppose there were a computable $f$ as described in the question. Then we could solve the Halting problem as follows.

Given a Turing machine $T$, consider the computable function $g$, defined by
$$g(k) = \begin{cases}
1 & \text{if $T$ halts in $\leq k$ steps} \\
0 & \text{otherwise}
\end{cases}$$
This is a computable, nondecreasing and total function. Therefore, we may use $f$ to establish that the range of $g$ is decidable. But now we just check whether $1$ is in the range to figure out whether $T$ halts.

Notice that I never used the finite/infinite distinction. The above argument works even if we assume that $f$ enumerates a finite set. Are you sure you got your theorem correct? The one I know says that an infinite set is decidable if it can be enumerated by a computable strictly increasing function. There is of course another theorem stating that every finite set can (obviously) be enumerated in increasing order.

Supplemental: Let us look at the matter from a constructive point of view. We have two constructive theorems, assuming Markov principle (which is generally used in computability theory):

  Theorem 1: If a finite set can be enumerated in non-decreasing order then it is decidable.

(A set is said to be finite if it is isomprhic to $\{0, 1, \ldots, n-1\}$ for some $n \in \mathbb{N}$, so the extra conditions in the theorem does not actually help, as every finite set is decidable.)

  Theorem 2: If a non-finite set can be enumerated in non-decreasin order then it is decidable.

However, we cannot just stick these two together into "any set enumerated in increasing order is decidable" because the following is not a constructive theorem:

  Theorem (classical): Every set is finite or non-finite.

In fact, in computability theory there are counter-examples. An immune set is infinite, but it does not contain any infinite computable sequence.


Numerically stable fast convolution algorithm?

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

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


We assume that edge weights are positive integers.  Given a directed graph G with edge weights, call an edge e redundant if e does not belong to any minimum-weight strongly-connected spanning subgraphs of G.

We claim that unless P=NP, there is no polynomial-time algorithm that always finds a redundant edge in a given directed graph with edge weights as long as there is one.  More precisely:

Theorem.  Given a directed graph G with edge weights, it is NP-hard to find a redundant edge in G or declare that G does not have a redundant edge.

Proof.  The key observation is that if G has a unique minimum-weight strongly-connected spanning subgraph, then you can compute that subgraph by removing the redundant edges one by one.  Therefore, it remains to show that the uniqueness does not make the minimum-weight strongly-connected spanning subgraph problem any easier, but this is proved by the next Lemma.  QED.

Lemma.  Given a directed graph G with edge weights, it is NP-hard to compute the weight of the minimum-weight strongly-connected spanning subgraph of G even under the promise that G has a unique minimum-weight strongly-connected spanning subgraph.

Proof.  As you know, the problem without the promise is NP-hard (even for the unit-weight case) by a reduction from the Hamiltonian circuit problem.  We reduce the problem without the promise to the problem with the promise.

Let G be a directed graph with edge weights.  Label the edges of G by e0, e1, …, em−1, where m is the number of edges in G.  Let wi be the given weight of the edge ei.  Let the new weight w′i=2mwi+2i.  Then it is easy to verify that G with the new weights has a unique minimum-weight strongly-connected spanning subgraph.  It is also easy to verify that the minimum weight W of a strongly-connected spanning subgraph in G with the original weights can be computed from the minimum weight W′ in G with the new weights as W=⌊W′/2m⌋.  QED.


Definition of matrix-multiplication exponent $\omega$

The matrix multiplication exponent being $\omega$ does not guarantee that there is an algorithm that runs in time $O(n^\omega)$, but only that for each $\epsilon > 0$, there is an algorithm that runs in $O(n^{\omega+\epsilon})$. Indeed if you can find an algorithm that runs in time $O(n^2 \mathrm{polylog}(n))$, then this shows that $\omega = 2$.

You can find the formal definition in the book Algebraic Complexity Theory by Peter Bürgisser, Michael Clausen, Amin Shokrollahi.


The Faddeev-Leverrier algorithm seems to be a good start to answer your question, since it reduces the computation of $\alpha_k$ to matrix multiplications and traces. It runs in polynomial time (even in NC) and I guess any efficient treatment of sparse matrix operation carries to this algorithm.

Oddly enough the wikipedia page about that exists only in French and German:

https://fr.wikipedia.org/wiki/Algorithme_de_Faddeev-Leverrier

I found this article in english explaining the method:

http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1085-14.pdf


Motivating Talk on Foundations of Cryptography

Since you can't rely on a knowledge of complexity theory, you have to emphasize the change in paradigm from security by obscurity to security by intractability, by positing the idea that some problems are hard to solve efficiently. This of course elides the many problems associated with the Impagliazzo worlds of intractability, but it gives a flavor of the way modern crypto works.

for ZKP, which are truly awesome, there are many ways to convey the basic ideas intuitively. See for example my answer on MO, as well as the hilarious Ali Baba and the 40 thieves story. While these were originally designed for a younger crowd, they work well at all ages to convey the right intuition.


High probability events without low probability coordinates

How does $\epsilon$ compare to $n$? If $\epsilon$ can be $O(1/\sqrt{n})$, then I think we can accomplish what you want. Let $B = \mbox{Supp}(X) - E$. Note that $B$ is given $\epsilon$ probability mass under $X$. Let $\lambda(i,\sigma)\epsilon$ denote the probability mass assigned to strings in $B$ such that the $i$th coordinate has symbol $\sigma$.

Suppose $(i,\sigma)$ were a low probability coordinate for some strings in $E$. Let $\delta(i,\sigma)$ denote the probability mass assigned to those strings. Then, by definition, $\frac{\delta(i,\sigma)}{\delta(i,\sigma) + \lambda(i,\sigma)\epsilon} \leq \epsilon$, implying that $\delta(i,\sigma) \leq 2\lambda(i,\sigma)\epsilon^2$. We can discard these low probability strings while only suffering a $\delta(i,\sigma)$ loss in prob. mass to $E$.

Continue doing this for all possible bad $(i,\sigma)$, and in the end we only discard at most $\sum_{i,\sigma} \delta(i,\sigma) \leq \sum_{i} \sum_{\sigma} 2\lambda(i,\sigma)\epsilon^2 \leq 2\sum_{i} \epsilon^2 = 2n\epsilon^2$. This uses the fact that for all $i$, $\sum_{\sigma} \lambda(i,\sigma) = 1$.

If you wanted $E'$ to have probability mass $1 -\gamma$, then $\epsilon$ needs to be such that $\epsilon + 2n\epsilon^2 \leq \gamma$, or that $\epsilon = O(\gamma/\sqrt{2n})$ suffices.

It's not clear to me at the moment whether this dependence on $n$ can be gotten rid of; I'll continue thinking about it.


(This was meant as a comment, but went long).
Very interesting question.
If you are willing to think about other complexity measures besides Kolmogorov's, then there are some answers in Learning theory that might satisfy you. I leave it for the experts in the area.

For example, if I'm not mistaken, in "A theory of the learnable" Valiant proved that a boolean function can be reconstructed given a polynomial number of "positive points" on the size of its k-CNF formula (for any fixed k, and I mean
with "positive points" those of the form $(x_1,\ldots,x_n,1)$).

In Knuth's TAOCP 7.2.1.6 it is shown in an astonishing way (using the Christmas tree pattern) that to reconstruct a monote boolean function (i.e. non-decreasing in each variable) you need exactly ${n+1 \choose \lfloor n/2\rfloor+1}$ points.


Error reduction with expanders and derandomization

You can't expect this to be true since you can reduce the error of a constant-error algorithm to $1/n$ using an additional $O(\log n)$ bits using expanders (and by the way you don't really need even these extra bits to do that). So if an error of $1/n$ can go down to $\exp(-n)$ error using only $O(n/\log n)$ additional bits, then you could always go from constant error to $\exp(-n)$ error using $O(\log n)+O(n/\log n)=O(n/\log n)$.


Problems that are NP-hard to approximate even when the input graph is regular

For all $k\geq 3$, the problem maximum induced matching is APX-hard for $k$-regular bipartite graphs. See this paper.

A matching $M$ of a graph $G$ is induced if for every pair of edges $e,e'$ in M, there is no edge between them in $G$.


Exact algorithm or parameterized algorithm for Maximum Edge Biclique Problem?

A good starting point could be the paper Exact exponential-time algorithms for finding bicliques which provides an $O(1.31^n)$-time algorithm for Constrained Bipartite Vertex Cover on graphs with $n$ vertices. As discussed in the paper this algorithm can be used to find bicliques with constraints on the sizes of the two parts. This in turn can be used to find bicliques with a maximum number of edges by considering all possibilities for the size constraints.

Concerning parameterized algorithms, it depends on the parameter that you want to consider.

If the parameter is the number $\ell$ of edges in the biclique, then a simple fixed-parameter algorithm can be obtained from the fact that whenever $\ell\le \Delta$ where $\Delta$ is the maximum degree of the input graph $G$, then we have a yes-instance. If $\ell>\Delta$, then one may find a maximum-edge biclique by considering for each vertex $v$ in $G$ the induced subgraph of $G$ containing $v$ and all vertices within distance 2 of $v$. This subgraph has $O(\Delta^2)$ vertices giving a running time of $2^{O(\ell^2)}\cdot n^{O(1)}$ for the nontrivial case. This can probably be improved but I am not aware of algorithms with running time $2^{O(\ell)}\cdot n^{O(1)}$.

If the parameter is the number of vertices in the maximum edge biclique, then one needs to be quite careful with the exact problem definition. For example,
if one asks for a biclique on at least $k$ vertices with at least $\ell$ edges, then one should obtain fixed-parameter tractability for $k$ by the above arguments. In contrast, if one asks for a biclique on at most $k$ vertices with at least $\ell$ edges, then the problem is a generalization of Balanced Bipartite Subgraph, also known as $(k,k)$-Biclique, which is W[1]-hard with respect to $k$ as shown by Bingkai Lin in The Parameterized Complexity of $k$-Biclique.


formal languages: what does R-trivial mean?

A semigroup $S$ is $R\text{-trivial}$ iff $a \: R \: b \Rightarrow a = b$ for all $a, b \in S$ where $R$ is Green's relation $a \: R \: b \Leftrightarrow aS^1 = bS^1$. The set of $R\text{-trivial}$ monoids forms a variety which can be ultimately defined by the equations $(xy)^n x = (xy)^n$.

A language is $R\text{-trivial}$ if its syntactic monoid is $R\text{-trivial}$. This variety of languages is alternatively defined as the set of all languages that can be written as a disjoint union  of languages of the form $A_0^* a_1 A_1^* a_2 \ldots a_n A_n^*$ where $n \geq 0$, $a_1, \ldots, a_n \in A$, $A_i \subseteq A \setminus \{a_{i+1}\}$ for $0 \leq i \leq n-1$. Another definition given in [Pin], which I'm not familiar with, uses the so-called automates extensifs ("extensive automata"). You can find more results about those languages in [Pin]. There is an English version of this book, I've never read it but I'm pretty sure that you can find the same content.

For the sake of completeness, here is an example of an (artificial) $R\text{-trivial}$ language: $\{b\}^* a \{a,c\}^* b \{a\}^* b \{a,b,c\}^* \cup \{d\}^* \cup abcd$. You can build other examples with the previous definitions. Note that all of the properties of varieties of languages hold for $R\text{-trivial}$ languages, therefore they are closed under union, intersection and complementation. It should help to build more complicated languages.


Secure MAC when the adversary has a verification oracle

If there is a secure message authentication code according to either definition,

  then there is a system that the book's definition classifies as a secure

  message authentication code and your definition classifies as insecure.

Let $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.02 in},\hspace{-0.05 in}\operatorname{Verif}\hspace{.02 in}\rangle\:$ be secure according to either definition. $\;\;$ Since the book's definition

is weaker than your definition, it is in particular secure according to the book's definition.

Fix some efficiently-computable and efficiently-invertable coding of

ordered pairs, for example, concatenating an efficiently-computable and

efficiently-invertible prefix-free representation  of the left entry to the right entry.

Let $\operatorname{MAC}_k\hspace{-0.09 in}'$ work by pairing the output of $\operatorname{MAC}_k$ with the empty string.

Let $\operatorname{Verif}_k\hspace{-0.09 in}'$ accept if and only if [[$\operatorname{Verif}_k$ would accept the message and the left entry

of the tag] and [the right entry of the input is a prefix of $k$]]. $\;\;$ $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ is clearly efficient and satisfies the requirement. $\;\;\;$ Since [pairing the tags with the empty string for]

and [taking the left entry of the output of] a feasible adversary attacking the book's

definition of the security of $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ cannot have a non-negligible probability

of breaking the book's definition of security for $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.02 in},\hspace{-0.05 in}\operatorname{Verif}\hspace{.03 in}\rangle\:$, $\:$ the book's

definition also classifies $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{-0.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ as a secure message authentication code.

However, once an adversary gets any valid message-tag pair for $k$, $\:2\hspace{-0.03 in}\cdot \hspace{-0.03 in}(\operatorname{length}(k)\hspace{-0.04 in}+\hspace{-0.05 in}1)\:$

adaptive queries to $\operatorname{Verif}_k\hspace{-0.09 in}'$ is sufficient to learn $k\hspace{.01 in}$, which would allow forgeries on any message.

Thus your definition classifies $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{-0.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ as insecure. $\;\;\;$ QED

  The strong unforgeability versions of the two definitions are equivalent.

(The "strong unforgeability" versions are obtained by replacing $Q$ with

the set $Q^+$ given in my next sentence, and that is needed to make the

encrypt-then-mac construction provide ciphertext integrity and be IND-CCA2.)

Initialize $\:Q^+\:$ as the empty set, and put $\: \langle m,\hspace{-0.03 in}t\rangle \:$ into $\:Q^+$

each time $\operatorname{MAC}_k$ outputs $t$ on a query of $m$ .

Define a query to be trying if and only if it is submitting

to $\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$ a pair that was already put in $\:Q^+\:$.

Define a query to be early-trying if and only if it is trying and

did not come after any trying query that $\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$ accepted.

$B^{\hspace{.02 in}\operatorname{MAC}_k(\cdot)}\hspace{-0.02 in}\left(\hspace{-0.03 in}1^n,\hspace{-0.02 in}q,\hspace{.02 in}j\hspace{-0.01 in}\right) \;$ interacts with $A$ as follows:

Using less than $\hspace{.02 in}j$ random bits, choose $\;\; r \: \in \: \left\{\hspace{-0.03 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.03 in}3,...,\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.04 in}2\hspace{.02 in},\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.05 in}1,\hspace{-0.02 in}q\hspace{-0.02 in}\right\} \;\;$ almost uniformly.

"Forward" all of $A$'s $\:\operatorname{MAC}_k(\cdot)\:$ queries to $\:\operatorname{MAC}_k(\cdot)\:$ and give that oracle's

(actual) output to $A$, give $0$ as the outputs on the first up to $r\hspace{-0.04 in}-\hspace{-0.05 in}1$ trying queries,

and give $1$ as the outputs of $\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$ on queries to it that are not trying.

If $\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$ makes an $r$-th trying query, then output what that query was.

If $\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$ gives output, then give that same output.

With everything's randomness fixed, if $\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$ makes exactly $\:r\hspace{-0.03 in}-\hspace{-0.04 in}1\:$ early-trying queries and succeeds in the strong unforgeability version of your experiment, then

$B^{\hspace{.02 in}A,\operatorname{MAC}_k(\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n,\hspace{-0.02 in}q,\hspace{.02 in}j\hspace{-0.01 in}\right)\:$ succeeds in the strong unforgeability version book's experiment.

  Therefore $B$ is a constructive straight-line reduction from succeeding in the strong unforgeability version of your experiment with probability at least $\epsilon$ in a way that

  makes less than $q$ early-trying queries, to succeeding in the strong unforgeability

  version of the book's experiment with probability greater than $\;\; \left(\hspace{-0.03 in}\frac1q\hspace{-0.03 in}-\hspace{-0.03 in}\frac{q}{2\text{^}j}\hspace{-0.04 in}\right)\cdot \epsilon \;\;\;$.

  $B$ uses less than $\hspace{.02 in}j$ random bits, has to handle insertions into and membership

  testing for [a set with less than $q$ elements, each of which is an ordered pair whose

  left entry is one of the inner algorithm's queries to $\:\operatorname{MAC}_k\:$ and whose right entry is

  $\operatorname{MAC}_k\hspace{-0.02 in}$'s$\:$ response to that query], and has only trivial additional complexity beyond that.

Clearly, "ignore the $\operatorname{Verif}_k$ oracle" is a constructive straight-line reduction from succeeding

in the strong unforgeability version of the book's experiment to succeeding in the strong unforgeability version your experiment, and that reduction is almost perfectly tight.

Therefore the strong unforgeability version of your definition gives the same

asymptotic MACs as the strong unforgeability version the book's experiment.


Binary search generalizations for posets?

I have not thought this through very much, so please correct me if I am wrong.

Say $w$ is the width of the poset.

For the poset which is the union of $w$ disjoint chains you need at least $w\log n$ evaluations of $P$ by just applying the standard lower bound on the query complexity of binary search to each chain.
Since you give comparisons for free, you can compute a chain decomposition of the poset into $w$ chains for free. Do binary search on each chain to identify the first element that satisfies $P$. Then go over the identified elements and remove any dominated ones. Number of evaluations of $P$ is $O(w\log n)$. This identifies all maximal elements, as there can be at most one maximal element per chain.

ADDED: Actually I am seeing a simple recursive algorithm to do much better ($O(n)$) for the lattice of subsets $2^{[n]}$ (EDIT: domotor described the general strategy in his answer). Here I am assuming $P$ is monotonic downwards (i.e. the subsets $\{X: P(X) = 1\}$ form a lower set), which is I think what you mean. So, here is the algorithm to find a member of the lower set:

a) Test $P(\emptyset)$. If 0, then stop.

b) Test $P(\{n\})$.

b.i) If 0, then recurse on $2^{[n-1]}$ (OK, since no set containing $n$ can be in the lower set).

b.ii) If 1, then there exists a member of the lower set in the sublattice $\{X: n \in X\}$. This sublattice is isomorphic to $2^{[n-1]}$ so once again we can recurse. More precisely, we can run the algorithm for $2^{[n-1]}$, but when the algorithm asks to evaluate $P(Y)$, we evaluate $P(X)$ where $X = Y \cup \{n\}$.

So in each step we recurse on a sublattice which is half the size of original one. Overall, we need to evaluate $P$ at most $2n$ times (in fact you can implement the algorithm to evaluate the predicate $n+1$ times as Yoshio points out, since you only need to check $\emptyset$ once).


Your question is vague in several ways.

By a "non-negative vector," do you mean a quantum pure state, all of whose amplitudes are nonnegative real numbers?  (Or rather, a state that's equivalent to such a state under multiplication by a complex scalar, which of course is physically unobservable?)

By a "quantum oracle," do you mean a unitary transformation that outputs ACCEPT when fed a non-negative state, and REJECT when fed any other state?  With probability close to 1?

If so, then it's immediate that no such oracle exists.  Indeed, the probability that the oracle accepts is a continuous (quadratic) function of the amplitudes, but the amplitudes can be arbitrarily close to 0 while still being either positive or negative.

So at the least, you'd need some lower bound on the absolute values of the amplitudes -- together, perhaps, with the assumption that the amplitudes are all real (or if complex, that their angles with each other are either 0 or else sufficiently large).  If you impose these conditions, then the "non-negativity oracle" does exist for quantum states of dimension 2: there it's called the "Hadamard gate," or the "Deutsch-Jozsa algorithm"!  On the other hand, because of quantum-mechanical linearity, one can prove that the non-negativity oracle won't exist for states of dimension 3 or greater -- or will exist but only with very large probability of error (approaching 1).


A balanced generalization of Hall’s theorem

You might look into the concept of $f$-factors and specially Tutte's theorem on the existence  of $f$-factors. You might find Proposition 2 of this paper relevant.


Determine if a structure is a model of an inductively defined predicate

What do you mean by the equality in your first formula? In first-order logic (FOL) with equality, one can only apply the equality operator to a couple of terms, not to formulae. Also, your use of equality cannot be considered a case of definition (what could be better depicted by $\triangleq$) since the predicate List appears on both sides of the equality. When creating a definition, the definiendum (in the left side of $\triangleq$) should not be mentioned in the definiens (right side of the $\triangleq$).

By FOL, are you referring to the so-called "first order programming logic" (a formal system specially designed for expressing recursive functions)? Since FOL cannot express transitive closure, I cannot think of a way to properly express recursion in FOL.


Languages that lack contraction, weakening or exchange

As other commenters have mentioned what you are actually asking for is a language for planar string diagrams, aka monoidal categories.

But let me address your question purely from the point of view of quantum computation.  Clearly in any reasonable system you would want to have an introduction rule for the tensor product -- your proposed weakening rule is just a special case of this.  Note that if you have any interesting (i.e. entanglement creating) constants in your language it's not really true to say that your can just forget $A$ in the output, unless the $A$ and $B$ parts never interact.

It also not quite right to say that contraction can't be admitted.  There are (many, inequivalent) maps of type $A \to A\otimes A$ which are quantum-realisable. However none of them are natural transformations, which probably you want.

There were many attempts in the early 2000s to shoe-horn quantum computing into linear logic, which were largely unsuccessful:  too much of the LL structure becomes degenerate, and too little of what makes quantum work is present in bare LL.

However you asked for an example of a system which lacks these rules; an early example is Selinger's QPL http://dx.doi.org/10.1017/S0960129504004256.  More or less every other proposed quantum programming language that actually has a type system will disallow contraction and weakening for quantum data.

If you want to get rid of the exchange rule you might be interested in the field of topological quantum computing.  In this setting the unitary operations are constructed from braidings; so the exchange rule is replaced by the braiding.


Did you try to look this up? Max Cut might be the most well studies problem out there, with tons of information on it on the web.

The survey by Poljak from '95 has a lot on different LP relaxations of Max Cut and the relationships between them. He considers special cases in which the relaxations are integral or almost integral. There are numerous other bounds on Max Cut, as well as non-polyhedral relaxations. This survey is very old, but all known LPs for Max Cut have been known to be dead ends for many years: every known LP relaxation of Max Cut, including the ones mentioned by Poljak, has integrality gap 2. So they are no better starting point than the trivial randomized or greedy algorithms. LPs for Max Cut have been out of fashion at least since Goemans and Williamson's SDP paper.

Some newer results: de la Vega and Mathieu show that adding any constraints with bounded support to the standard LP relaxation leaves the integrality gap at 2 (http://portal.acm.org/citation.cfm?id=1283390). The same is true for $n^\delta$ rounds of the Sherali-Adams hierarchy (http://portal.acm.org/citation.cfm?id=1536455). So in a very strong sense LPs are no help for Max Cut.

On the other hand there is work on primal-dual algorithms for Max Cut based on the GW SDP. Klein and Lu gave a fast approximation for MaxCut that matches Goemans-Williamson: http://dx.doi.org/10.1145/237814.237980 (they use what is now known as the multiplicative weights method to solve the SDP). I don't know the details, but I know that Luca's approximation of Max Cut using eigenvectors is in some sense a dual of the GW SDP (http://arxiv.org/abs/0806.1978). The latest combinatorial random-walk based algorithm is based on Luca's: http://arxiv.org/abs/1008.3938.


Kernighan–Lin algorithm and multiple gain functions

Kim and Moon (2004) compare variants of Kernighan-Lin which combine the usual gain and a lock-based gain, which is relative to the locked vertices. You can combine two gain functions in the range $-n\ldots n$ using an implementation of Fiduccia-Matheyses with $O(n^2)$ buckets.

Kim, Moon, Lock-gain based Graph Partitioning, J Heuristics, 10, 37-57, 2004.


Do "One Way Functions" have any applications outside crypto ?

One-way functions show up crucially in the Razborov-Rudich natural proofs result. I wouldn't consider circuit lower bounds as part of "cryptography", so maybe this fits your criteria.


SAT in some DTIME always via a constructive proof?

I would like to elaborate on Kaveh's answer because I see people wondering about the constructive status of $P = NP$.

Levin's algorithm performs a dove-tailing parallel execution of all Turing machines on the given SAT instance. If and when any machine terminates, it is verified whether its output is a solution to the SAT instance. If so, Levin's algorithm terminates, otherwise it keeps going.

The algorithm solves SAT because there is a Turing macine that solves SAT, and so eventually Levin's algorithm emulates enough of it to find a solution. Moreover, with careful programming the dove-tailing technique incures at most a polynomial slowdown of any particular simulated machine, so if there is a machine solving SAT in polynomial time, then Levin's algorithm does it in polynomial time as well.

Now let us consider the logical complexity of the statement *"Levin's algorithm runs in polynomial time". It is a specific algorithm whose Gödel code is some number $\ell$. The statement that it runs in polytime can be expressed in first-order arithmetic using Kleene's predicate $T$:
$$\exists C, k. \forall m . \exists n < 2^{C \cdot m^k}. T(\ell, k, n).$$
This can be read as: "There are $C$ and $k$ such that for every (Gödel code of a) SAT instance $m$ there is (a Gödel code of) an execution trace $n$ of $\ell$ running on input $k$, and the length of execution trace does not exceed $C \cdot m^k$."

The predicate $T$ is primitive recursive, and so is the inner formula as its quantifier is bounded by a primitive recursive function. If I am not making a mistake here (please correct me if I am, or provide a reference as I cannot be the first person noticing this), this means that we can express $P = NP$ as a $\Sigma^0_2$-formula. Thus, by negating the formula we can express $P \neq NP$ as a $\Pi^0_2$-formula. By Friedman's conservativity result we therefore have

  If Peano arithmetic proves $P \neq NP$ then Heyting arithmetic proves $P \neq NP$.

In other words, this shows that in the context of first-order arithmetic $P \neq NP$ has a constructive proof if it has a classical one.

Am I making a mistake somewhere?


It is a standard fact that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$ for every graph $G$. (See the proof below.)
Denoting $b_k := \sqrt[k]{\alpha(G^k)}$, this implies that the tail of the sequence $(b_k)_{k \geq 1}$ cannot be monotone decreasing, and hence there are infinitely many $k$'s for which $b_{k+1} \geq b_k$, as required.

In order to prove that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$ note that the sequence $(\alpha(G^k))_{k \geq 1}$ is super multiplicative, i.e., $\alpha(G^{k+\ell}) \geq \alpha(G^k) \alpha(G^\ell)$ for all $k,\ell \geq 1$. Indeed, if $I$ is an independent set in $G^k$, and $J$ is an independent set in $G^\ell$, then $I \times J$ is an independent set in $G^{k+\ell}$. Therefore, by (the multiplicative version of) Fekete's lemma it follows that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$.


Can Curry-Howard prove a theorem from the types in your program, that has nothing to do with your program?

I'll answer the opposite question which is:

  can Curry-Howard prove a theorem for your program, which has nothing to do with the type?

The answer is yes, depending on the meaning of "nothing to do". I'll leave the Curry-Howard aspect aside somewhat, but it underlies a lot of this approach.

The key idea is Wadlers' Theorems for Free! building on ideas from Reynolds, which allow you, given a program type, to deduce something about the program. For example, a program $f$ of type

(a, b) -> (b, a)

in haskell must satify

$$ \forall x\ y,\ f\ (x, y) = (y, x)$$

and therefore be the swap function.


What's a good news source for Computer Science?

Theory of Computing Blog Aggregator for theoretical computer science


Here's another approach, which I think runs in $O(k)$ time.

Define $S_k$ by

$$S_k = {1 \choose k} + {2 \choose k} + \dots + {n \choose k} = {n+1 \choose k+1}.$$

The right-hand-side can be computed in $O(k)$ time.

Similarly,

$$S_{k-1} = {1 \choose k-1} + {2 \choose k-1} + \dots + {n \choose k-1} = {n+1 \choose k},$$

and given the value of the previous sum $S_k$, we can compute this sum $S_{k-1}$ in $O(1)$ time (using the fact that ${n+1 \choose k} = {n+1 \choose k+1} \times {k+1 \over n-k+1}$).

In this way, we can compute all of the sums $S_k,\dots,S_2,S_1,S_0$ in $O(k)$ time.

Furthermore, we can find constants $c_0,\dots,c_k$ such that

$$x^k = c_k {x \choose k} + \dots + c_1 {x \choose 1} + c_0 {x \choose 0}$$

holds for all $x$.  It follows that

$$S = 1^k + 2^k + \dots + n^k = c_k S_k + \dots + c_1 S_1 + c_0 S_0,$$

which can be computed in $O(k)$ time.


The average number of compressible strings in a random set of random strings

The answer is less than $2^{n-k}$ of the sequences of length $n$ have complexity less than $<n-k.$ Due to the uniformity assumption on these sequences we just count.

Consider all short programs of bitlength $<n-k.$ Even if all represented sequences of length $n$ the total number of such programs (starting with the empty program) is $$1+2+2^2+..+2^{n-k-1}<2^{n-k}.$$

To clarify,the number of compressible strings by $k$ bits in a the set of length $n$ bits is $2^{n-k}$, their relative number is $2^{-k}$ and their percentage is $100\times 2^{-k}.$ So for each fixed $k$ and all $n$ you get a constant. For example the percentage of strings of length $n$ which are compressible by $k=3$ is $100\times 2^{-3}=12.5\%,$ those compressible by $10$ bits have percentage $100\times 2^{-10}=0.09765625 \%.$


The process you seem to be looking for (merging two descriptions of labeled trees) is called unification. According to the linked Wikipedia article it can be solved in linear time.


Minimum number of triangles required to cover a complete graph?

Let $N(n)$ be the number of triangles needed to cover $K_n$.
Because every triangle covers only three of the $n\choose 2$ edges, we have $\frac{1}{3}{n\choose 2}\leq N(n)$ as a lower bound.
Note that the case $n=2$ is degenerate, as $K_2$ has only one edge and no triangles.
In the following analysis, I will allow myself to use triangles that cover only one edge (for $n>2$, this is without loss of generality because you can use an arbitrary third vertex to create a triangle).
To obtain an upper bound, we apply divide and conquer as follows.
For some $k+m=n$, think of $K_n$ as the union of $K_m$, $K_k$, and $K_{k,m}$.
In particular, let's pick $m:=\lfloor n/2\rfloor$ and $k:=\lceil n/2\rceil$.
Label the vertices of $K_k$ by $u_0,\dots,u_{k-1}$ and the vertices of $K_m$ by $v_0,\dots,v_{m-1}$.
For each edge $\{u_i,u_j\}$ of $K_k$, place the triangle $\{u_i,u_j,v_{i+j\pmod m}\}$.
This covers each edge of $K_k$ using $k\choose 2$ triangles, and also covers the edges $\{u_i,v_l\}$ of $K_{k,m}$ as long as $l\neq 2i\pmod m$.
We can cover the remaining edges $\{u_i,v_{2i\pmod m}\}$ of $K_{k,m}$ using $k$ triangles.
Now, it remains to cover the edges of $K_m$, which we do recursively.
This yields the upper bound $N(n)\leq N(m)+{k\choose 2}+k\leq N(\lfloor n/2\rfloor)+{\lceil n/2\rceil\choose 2}+\lceil n/2\rceil$.
For $n\leq 1$, we have $N(n)=0$, so we can write out the recurrence:
$$\begin{align}N(n)&\leq
\sum_{i=1}^{\log_2 n} \left[{\lceil n/2^i\rceil\choose 2} + \lceil n/2^i\rceil\right]\\
&\leq
\sum_{i=1}^{\log_2 n} \left[{\frac{n}{2^i}+1\choose 2} + \frac{n}{2^i} + 1\right]\\
&=
\sum_{i=1}^{\log_2 n} \left[\frac{1}{2}(\frac{n}{2^i})^2+\frac{3}{2}\frac{n}{2^i} + 1\right]\\
&= \frac{n^2-1}{6} + \frac{3(n-1)}{2} + \log_2 n\\
&= \frac{1}{3}{n\choose 2} + O(n).
\end{align}$$
Therefore, the lower bound is tight up to a linear function of $n$.


Deciding functionality of transducers over infinite words

Françoise Gire actually gives two proofs of her result.

The first proof (I am quoting her paper now) uses a construction similar to the one used in [3] to prove the decidability of the $\omega$-equivalence of two functional finite transducers.

The second proof makes use of the technique you are describing in your question: $T$ is functional if and only if $T \circ T^{-1}$ is a restriction of the identity. The property for an infinitary rational relation of being a restriction of the identity is proved to be decidable in [3,4].

[3] K. Culik and J. Pachl, Equivalence problems for mappings on infinite strings, Inform. and Control 49 (1981) 52-63.

[4] K. Culik, Some decidable results about regular and pushdown translations, Inform. Process. Lett. 8 (1979) 5-8.


Delegating all of the work to the prover in $\mathcal{MA}$ protocols

This is an answer to the last question: MA in the query complexity model.

It isn't always possible to make the prover do all the work (or even any work at all). The reason is that an MA-prover is trying to convince you that the answer is YES. But the problem can be chosen so that in the YES case, there's nothing interesting that the prover can tell you. There are hard problems for which having a YES-prover is completely useless (i.e., it will not reduce the verifier's work at all).

For example, consider the AND problem, where you have to compute the AND of all the bits in the black box. This requires $\Omega(n)$ queries for a bounded-error algorithm. Now if you have access to a YES-prover, there's nothing interesting he can tell you. The most he could do is give you the entire contents of the black box. But since it is the AND function, and he is trying to convince you that the function evaluates to 1, he will always give you the all ones string. So you could have simulated this yourself.

Added: Does this protocol work in communication complexity? Take any CC problem that requires $T(n)$ bits of communication without Merlin. In the MA protocol, Merlin sends the entire transcript of communication to Alice and Bob, had they used the original protocol. Since equality is easy to check in randomized CC, they check that the transcripts are the same with high probability. Once they are convinced that the transcripts are the same, they output the outcome of that transcript of conversation.


If $G=\mathbb{Z}_{2}^{n}$ and the hidden subgroup $H$ has order $2$, then finding the hidden subgroup is equivalent to finding two elements in the same coset of $H$. The latter is in turn a birthday paradox-type problem, so should require $\Theta(\sqrt{|G|})$ queries for a randomized algorithm and $\Theta(|G|)$ queries for a deterministic algorithm. Note that $|G|=2^{n}$ is exponential in the input size.


Distinguishing between $N$ quantum states

As you mention, it is possible to determine the optimal average success probability numerically, which can be done efficiently via semidefinite programming (see e.g. this paper by Eldar, Megretski and Verghese or these lecture notes by John Watrous), but no closed form expression is known.

However, there are several known upper and lower bounds on the probability of error (i.e. 1 minus the average success probability). In terms of pairwise fidelities, the probability of error in your setting is known to be lower bounded by $\frac{1}{N^2} \sum_{i>j} F(\rho_i,\rho_j)$, and upper bounded by $\frac{2}{N} \sum_{i>j} F(\rho_i,\rho_j)^{1/2}$.

There is also another lower bound known in terms of trace distance: $\frac{1}{2}(1 - \frac{1}{N(N-1)} \sum_{i>j} tr|\rho_i-\rho_j|)$, which reduces to the exact Helstrom bound in the case $N=2$. See this paper for a comparison of all of these, and some other bounds too. Note that all of these bounds hold in the average-case setting where there is a prior probability distribution on the states.


Complexity of Parallelogram Range Minimum Query

This can be reduced to rectangular RMQ in $O(n^2)$ time and space. Create a new array $H$ where $H[i][i+j] := G[i][j]$, padding entries $H[i][k]$ with $k < i$ or $k \ge i + n$ with $\infty$. Run $RMQ(a, b, c, d)$ on $H$ whenever you would run $RMQ_P(a, b, c, d)$ on $G$.

Now run your favorite 2D-RMQ algorithm such as this. Perhaps you want to be very conservative with the extra space used though. In that case I suspect unpacking your favorite result will show that it helps to avoid writing $H$ down, and instead use an $O(1)$ function to produce values of $H$ by lookup into $G$.


What is the complexity of this submatrix selection problem?

EDIT: Added an answer meeting the unique-sum requirement.
Lemma 1. The problem is NP-hard by reduction from 3-CNF-SAT, even if the maximum is required to be unique.
Proof. Here's the reduction.  First we describe the reduction to the problem without the requirement that the maximum is unique.
Fix a 3-CNF-SAT instance $\phi$.  Assume WLOG that $\phi$ has more clauses than variables (if not, just duplicate clauses to make it so).  Let $n$ be the number of clauses.
The reduction outputs a $kn\times kn$ matrix $M$, where $k=3$.  $M$ will be a 0/1 matrix, and will have an $n\times n$ submatrix of the desired form and having (at least) $n$ ones iff $\phi$ is satisfiable.
Create $M$ as follows. For each variable $x$ in $\phi$, create a window of three columns: a column $c(x)$ for the literal $x$, a column $c(\bar x)$ for the literal $\bar x$, and one dummy column whose entries are all zero (just so the window has the necessary three columns). Add additional windows of all-zero columns to bring the number of column-windows to the desired number $n$.
For each clause, say $C=\ell_1\vee \ell_2 \vee \ell_3$, create a window of three rows, one for each literal. Name the three rows, respectively, $r(C, \ell_1)$, $r(C, \ell_2)$, and $r(C, \ell_3)$.  In each row, make just one entry 1: for row $r(C, \ell_1)$ the entry in column $c(\ell_1)$, for row $r(C, \ell_2)$ the entry in column $c(\ell_2)$, and for row $r(C, \ell_3)$ the entry in column $c(\ell_3)$.  Make all other entries zero.
This completes the reduction.  To finish we observe that there will be a submatrix of the desired form (with a row in each row-window and a column in each column-window) having (at least) $n$ ones if and only if $\phi$ is satisfiable.
First, suppose that $\phi$ has a satisfying assignment $A$.  Choose the submatrix of $M$ as follows.  Use the columns corresponding to literals that $A$ makes true (one for each variable), and one (all-zero) column from each padding column-window.  For each clause $C$, choose a literal $\ell_i$ in $C$ that $A$ makes true, and choose the row $r(C, \ell_i)$ in $C$'s row-window.  This defines the $n\times n$ submatrix.  Each of its rows has a 1, so the total number of 1's in the submatrix is $n$.
Conversely, suppose that $M$ has a submatrix $M'$ of the desired form with at least $n$ ones.  For each variable $x$, $M'$ uses either the column for the literal $x$, the column for the literal $\bar x$, or the dummy column in $x$'s column-window.  If $M'$ uses one of the two literal columns, assign $x$ the value that makes the literal true.  Otherwise assign $x$ arbitrarily.  This defines the assignment.
To see that it must be a satisfying assignment, recall that the submatrix has $n$ rows, and each row of $M$ has at most one 1, so reach row of the submatrix $M'$ must have exactly one 1.   By the construction of the row-windows in $M$, then, for each clause $C=\ell_1\vee \ell_2 \vee \ell_3$, there is a row $r(C, \ell_i)$ in the submatrix that has a 1, necessarily in the entry for row $\ell_i$ (as this is the only 1 entry in that row).  So column $\ell_i$ must be in the submatrix, so the assignment must make $\ell_i$ true.
EDIT: added the part below to handle the unique-sum requirement.
Hence, the reduction is correct.  Finally, to reduce 3CNF-SAT to the problem when the maximum is required to be unique, modify the previous reduction to output the matrix $M^*$ obtained from $M$ by adding a small perturbation to each entry, specifically, such that
$$M^*_{ij} = M_{ij} + \epsilon_{ij} \text{ where } \epsilon_{ij}=1/2^{nki + j+1}.$$
Because $M$ is a 0/1 matrix, the sum of the values in any sub matrix of $M$ is an integer. Also, for any sub matrix $M'$ of $M^*$, the sum of the perturbations $\sum_{ij\in M'} \epsilon_{ij}$ is less than 1 and is unique (as it uniquely identifies the set of indices of entries in $M'$).  It follows that the valid submatrix of $M^*$ with maximum sum is unique, and has sum at least $n$ iff the given 3-CNF-SAT instance $\phi$ is satisfiable.
(And note that the size of the encoding of $M^*$ is still polynomial in the size of $\phi$.)
$~~\Box$
Exhaustive search takes time polynomial in $k^n$, which is polynomial in the input size in the case that $n$ is constant (but $k$ grows).  So that case (fixed $n$) has a poly-time algorithm.
One could ask further about, say, hardness of approximation.  The above reduction can be done from MAX-3SAT to show that the problem has no PTAS.  But to me it looks like the problem generalizes a variant of Bipartite Densest Subgraph, so may be even harder to approximate.  (This assumes the matrix has non-negative entries.  If negative entries are allowed, it's easy to extend the above reduction so that the optimal value is 1 iff $\phi$ is satisfiable, and zero or negative otherwise, so approximating within any factor is NP-hard).


Hardness of Subgraph isomorphism problem for sparse pattern graph

It is $W[1]$-hard even when $G$ has maximum degree $3$, but $FPT$ if $G$ has constant treewidth (all the above examples have constant treewidth). See the paper Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask) by Marx and Pilipczuk.

Indeed, it follows from an earlier paper of Marx: Can You Beat Treewidth? Theory of Computing 6(1): 85-112 (2010) that a $f(k)n^{o(k/\log k)}$
time algorithm would violate the ETH. Here $n$ is the number of vertices in $H$ and $k$ is the number of vertices in $G$. This holds even when $G$ has max degree $3$ (but the degree of $H$ is unbounded).


As far as I know (and can interpret your question) no such result is known.
There are two reasons:

1) Generally unique games hardness results (as well as NP hardness result) do not yield "instance based" hardness. That is, the UG-hardness result have the following flavor - "if the unique games conjecture is true then for problem $P$ no algorithm can get a better approximation ratio than $\alpha$, where $\alpha$ is the ratio that the canonical SDP achieves on $P$"

2) While the theta function  is an appealing algorithm, and yields a $\sqrt{n}$ approximation for independent set for random graphs, in the worst case its approximation ratio can be close to $n$ (am not sure what's the extreme example), which can of course be achieved trivially. In fact, Hastad has gave an NP-hardness result ruling out an $n^{1-\epsilon}$ approximation for independent set for every $\epsilon>0$. So, even without the unique games conjecture, we know that essentially there is no non-trivial worst case approximation algorithm for this problem.

It would be very nice if there was a natural class of graphs where the theta function yields, say, an $O(\sqrt{n})$ approximation, and it is NP or UG hard to do better. I don't know of any such result.


Most of the important work on generics for C# was done by Andrew Kennedy at Microsoft Research Cambridge. He has a web page devoted to the topic. A fairly recent paper discussion the foundations is this one (which definitely looks like theory to me).

More recent, but interesting, work went into the design of C$\omega$. Also looking at the rather large amount of literature on Java generics, such as Featherweight Java, will also help. If you really want to start looking at the foundations, consider Cardelli's work on Types and Semantics, and perhaps consider looking at System F (and the original papers of Reynolds and Girard).


Classifying noetherian simple groups by order type?

Here's an argument handling a special case. Consider a fixed poset $P = (S,\leq)$. Say that a (well-founded) forest $F$ is a branching-representation of $P$ if:

the nodes of $F$ are bijectively labelled by the elements of $P$;
for each node $u$ of $F$, its children are ???

(SORRY, CAN'T FIGURE THE RIGHT DIFINITION NOW, I'M PUTTING THIS ON STANDBY)

We may then assign an ordinal $o(u)$ to each node of $T$ inductively: (i) if $u$ is a leaf then $o(u) = 1$, (ii) if $u$ has children $(u_i)$, then $o(u) = \sum_i o(u_i)$. The order type of $T$ is then defined as $o(T) = o(r)$ where $r$ is the root.

Is the following true?

  Conjecture: the order type of $P$ equals the minimum of $o(T)$ over all possible branching-representations $T$ of $P$.

Suppose this is true. Consider a poset $P = (S,\leq)$, and let $P^{\natural} = (S',\leq')$ where $S'$ consists of the finite antichains of $S$ and where the order satisfies $X \leq Y$ iff there is an injection $\phi : X \rightarrow Y$ s.t. $u \leq \phi(u)$ (f.a. $u \in X$). Suppose that $ot(P) = \lambda$ with $\lambda$ a limit ordinal, it should then follow that $ot(P^{\natural}) = \omega^{\lambda}$: starting with a b.p. $T$ of $P$, we would construct a b.p. $T'$ for $P^{\natural}$ by 'iterated substitution'.

This might help to analyze the case of ordered free groups. In this case, we have an ordered alphabet $P = (S,\leq)$, and we consider the free group $P^{\sharp}$ over $\{S \cup S^{-1}\}^*$, equipped by the relation $u \preceq v$ iff $u_i \leq v_{\phi(i)}$ for some injection $\phi$. Now, given an element $B = \{b_1,\ldots,b_k\} \in (P^{\sharp})^{\natural}$, we may define the subgroup $\langle B \rangle$ of $P^{\sharp}$ generated by $\cup_{i = 1}^{k} (b_i \downarrow)$.

It follows that the map $\chi : (P^{\sharp})^{\natural} \rightarrow Sub(P^{\sharp})$ defined by $\chi(B) = \langle B \rangle$ is surjective. Consider the equivalence over $(P^{\sharp})^{\natural}$ s.t. $B \sim B'$ iff $\chi(B) = \chi(B')$. Assuming that the equivalence classes of $\sim$ are finite (which seems intuitively true), I think that it would imply $ot(Sub(P^{\sharp})) = ot((P^{\sharp})^{\natural}) = \omega^{\omega^{\omega^{\lambda}}}$ (possibly up to some lower degree terms).

So if the above is correct, you've got at least the ordinals of the form $\omega^{\omega^{\omega^{\lambda}}}$ in question (1).


Complexity class of efficient streaming algorithms

Along with my comment above (noting that not even AC0 is in "StreamL"), let me say that that this class has been studied before; you just need to know what they used to call it.

Search for "one-way logspace" and you will find plenty of references. (Typically, past work treats it as a reducibility concept.) The papers that those papers reference should cover what you need.


Are there any classes of functions which require provably different resources to compute versus computing their inverse?

I was asked to repost my comment.  I pointed out this paper by Hastad, which shows that there exist permutations in $NC^0$ that are P-hard to invert:

http://dx.doi.org/10.1016/0020-0190(87)90053-6 (PS)


Describing state machines mathematically

There is a general theory here, which was introduced into CS by Robin Milner, which Lamport did not go into.

A state machine is generally given as a triple $(Q \in \mathrm{Set}, q \in Q, f \in I \times Q \to \mathcal{P}(O \times Q))$, consisting of a state set $Q$, an initial state $q$, and a transition relation $f$.

Now, suppose we have two automata $(Q, q, f)$ and $(T, t, g)$. Let's ask a question: when are these automata equivalent? If all we are going to do is take the machines and send them inputs and listen to the outputs, we don't want to require the state sets to be the same (for example, if $(T, t, g)$ is the result of running a DFA minimization algorithm on $(Q, q, f)$).

It turns out that the right notion of equivalence is bisimulation.  The idea is that we take two state machines to be the same, if we can produce a relation $R \subseteq Q \times T$, such that

$(q,t) \in R$
for all $(q,t) \in R$ and $i \in I$ and $o \in O$ then:

for all $q' \in Q$, if $(o, q') \in f(i, q)$, then there is a $t' \in T$ such that $(o, t') \in g(i, t)$.
for all $t' \in T$, if $(o, t') \in g(i, t)$, then there is a $q' \in Q$ such that $(o, q') \in f(i, q)$.

This says that if we can figure out any relation such that (a) the initial states are related, and (b) from related initial states, any I/O action the first machine can take can be mimicked by the second machine in a way that keeps you in the relation, and (c) similarly, the first machine can mimic anything the second can do.

Lamport's notation with primes is a way of concisely describing input-output relations. In this case, the state sets are the program counter of the first program, and the two program counters of the second program. The bisimulation relation is $R(pc, (p, c)) \triangleq pc = p \oplus c$, and then the bisimulation conditions follow trivially (since the relation expressions are equal under the subsitution).

The general theory at work is the theory of coinduction. State machines are representions of corecursively defined sets, and bisimulations tell you when two state machines are representations of the same potentially-infinite object.

Incidentally, this paper is written in a rather polemical style. Equally polemically, I'll point out that the style he advocates in this paper simply fails should you ever need to verify part of a program in isolation -- for example, if you want to prove a library implementation correct, or verifying a program using higher-order functions (or even just dynamic linking).

But both of us will use coinduction, nonetheless.


Verifying Shor's quantum error correction code

Since I don’t understand what you don’t understand, I will try to give a quite formal description, hoping it will help.

$\newcommand{ket}[1]{\left|#1\right>}$
Let’s suppose the error is the unitary $U$ applied on the $k$th qubit.
We have
$$\begin{align}
U&=aI+bX+cY+dZ\\&=aI+bX+icXZ+dZ,
\end{align}$$
with $a,b,c,d$ being real numbers, $I$ is the identity, $X, Y, Z$ the Pauli operators. $X$ is a bit-flip, and $Z$ is a phase-flip.
$Y=iXZ$ is a combination of phase and bit-flip.

Let’s look at a coherent version of Shor error correction, one where there is no measurement, but a set $A$ of 8 ancilla qubits, initially in the $\ket{0}$ state. Their final state, if measured in the computational basis, contains the code syndrome. The error correction is described by a unitary $V$ acting the 9 qubits of the code ($B$) and the 8 ancilla qubits. Since the code corrects both bit-flips and phase-flips, we have:
$$
\begin{align}
V⋅(I\otimes I)\ket{\psi}_B\ket{0}_A&=\ket{\psi}_B\ket{0}_A\\
V⋅(X_k\otimes I)\ket{\psi}_B\ket{0}_A&=\ket{\psi}_B\ket{\phi_{k,X}}_A\\
V⋅(Z_k\otimes I)\ket{\psi}_B\ket{0}_A&=\ket{\psi}_B\ket{\phi_{k,Z}}_A\\
\end{align}
$$
The action of $Y_k=iX_kZ_k$ is also corrected, since it is a phase-flip followed by a bitflip $^*$ :
$$
\begin{align}
V⋅(I_k\otimes I)\ket{\psi}_b\ket{0}_a&=iV⋅(X_k\otimes I)⋅(Z_k\otimes I)\ket{\psi}_b\ket{0}_a\\
&=\ket{\psi}_b\ket{\phi_{k,Y}}_a\\
\end{align}
$$

If we apply this to an arbitrary error $U_k$ on the $k$th qubit, we have :
$$V⋅(U_k\otimes I)\ket{\psi}_b\ket{0}_a=\ket{\psi}_b\left(a\ket0_a+b\ket{\phi_{k,X}}_A+c\ket{\phi_{k,Y}}_A+d\ket{\phi_{k,Z}}_A\right) $$
and the vector $\ket{\psi}_b$ is recovered.


Is there an equivalent to VC-dimension for density estimation as opposed to classification?

For distributions with finite support of size $d$, when the error metric is the $\ell_1$ distance, the analogue of VC dimension is exactly $d$. (In fact, it's pretty much the VC dimension -- since to estimate a distribution over $d$ in $\ell_1$ is equivalent to agnostically PAC-learning the concept class $2^{[d]}$).
For discrete distributions with infinite support, no PAC-type result can be given. Perhaps somewhat surprisingly, a fully empirical (and nearly optimal!) sample-dependent bound on the $\ell_1$ distance between the empirical and true distributions can be given, see:
https://arxiv.org/abs/2004.12680
(to appear in NIPS 2020).
For continuous distributions, the situation is more subtle. You basically can't estimate anything without some absolute continuity and smoothness assumptions; see, for example the impossibility results:
https://papers.ssrn.com/sol3/papers.cfm?abstract_id=139691
https://www.sciencedirect.com/science/article/abs/pii/S0167715298002466
https://www.jstor.org/stable/2242068?seq=1
What's typically done is that we define a class of distributions with certain smoothness properties (Lipschitz, Hölder, Sobolev, Besov) and then design an algorithm that achieves a certain rate for this class, and then argue that no algorithm can achieve a better rate (making our algorithm "minimax" for that class).


A search problem and no algorithm for it

Your description is a bit vague, but the problem you describe seems very similar to the canonical problem defining the complexity class PLS (http://en.wikipedia.org/wiki/PLS_(complexity)). Problems in PLS can be described by an exponentially sized graph that you have access to using two polynomial time algorithms: one for evaluating the weight of a current vertex, and one for directing you to the neighbors of a current vertex. The goal is to find a local-minimum in the graph: any vertex such that none of its neighbors have lower weight.

Complete problems for this class include computing pure strategy Nash equilibria in congestion games (See e.g. here), and no polynomial time algorithms for such problems are known.


Resources to learn about the P vs. NP problem

It's good to see a fellow undergrad in pursue of this great problem, with such an enthusiasm. Allow me to offer you a piece of advice from my own experiences.

$ P \neq NP $ is a very interesting problem. The implications of the answer are immense, especially in the case that the two classes are equal. The reward is great in many levels, from the altruistic scientific one to the materialistic money award. That leads many young people that encounter the problem in trying to solve it, with no or limited knowledge about it.

Perhaps most theory students go through that phase. You will have an idea and think it is right, but it is almost certain that you are wrong. Some people never get through that phase and embarrass themselves by being too stubborn to admit their errors.

In FOCS 2010, Rahul Santhanam compared the $ P \neq NP $ question to a mythical monster. It would take many sacrifices and courage to even try to defeat this monster. After all, it may be the most difficult problem ever. To have a fighting chance, you will have to study a lot about this problem and complexity in general. You'll never know what the "monster's weakness" will be.

So my advice is this: Take your time in knowing the problem. Every time you figure out a solution, assume you are wrong somehow and try to find the problem with it. That way you'll learn much.

As for references, I would recommend Sipser's book as well. After finishing it, I would recommend "Computational Complexity:A modern approach" by Arora and Barak, a more complexity-oriented book, that requires a good understanding of the concept of computation.


Is simply typed lambda calculus equivalent to primitive recursive functions

The simply-typed λ-calculus with β-equality at type (o → o) → o → o  (which can be seen as type of the natural numbers, whenever o is any base type) can define exactly the extended polynomials (= polynomials with if-then-else), see (1). Other notions of equality change this. (2) shows that using $\beta\eta$-equality leads to a larger class of definable functions, although no simple
characterisation is given.

Schwichtenberg's result
can be generalised to functions on words over the binary alphabet,
represented as type (o → o) → ((o → o) → o → o), see (3), and also to
free algebras, see (4).

H. Schwichtenberg, Definierbare Funktionen im λ-Kalkül mit Typen.
M. Zakrzewski, Definable Functions in the Simply Typed λ-Calculus.
M. Zaionc, Word operation definable in the typed lambda-calculus.
M. Zaionc, λ-Definability on free algebras.


Finding the number of independent rows of a matrix

(what follows solves the question for columns, easily adapted to rows either by transposing or by doing a column echelon instead of a row one)

You can do the following: put your matrix in reduced echelon form by the Gauss-Jordan elimination method. Note that this preserves $N(A)$.

Let's say we work on a 5x5 matrix and that we get:

\begin{bmatrix}
1 & a_1 & 0  & 0 & b_1 \\
0 & 0 & 1 & 0 & b_2 \\
0 & 0 & 0 & 1 & b_3 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0
\end{bmatrix}

From this form you can read $N(A)$ immediately: the only columns that can be independent are the ones holding the $1$s (the pivots of the elimination). Now it is obvious that they actually are independent iff. the coefficients on the right of the $1$ they hold are all $0$.

(in our example: the 1st column is independent iff. $a_1=0$ and $b_1=0$; the 3rd column is independent iff. $b_2=0$;
the 4th column is independent iff. $b_3=0$)

This way you get $N(A)$ in $O(n^e)$ where $n^e$ is the complexity of computing the echelon form. (the naive algorithm gives $e=3$).


Decide whether a point is a vertex of a polytope?

This answer expands on Chandra's comment, and on my follow up comment. The problem is indeed solvable in polynomial time. More general versions of it are also solvable in polynomial time: $\Theta$ could be given by a separation oracle, rather than explicitly, and it is also possible to solve an appropriately formulated version for a polyhedron.

Observe first that we have an efficient separation oracle for $P = f(\Theta) = C\Theta + d$. Indeed, deciding $y \in P$ amounts to solving the feasibility problem
$$
y = Cx\\
Ax \le b
$$
over the variables $x$. This problem can be solved with the usual techniques, e.g. the ellipsoid method. By the equivalence of separation and optimization, we can also solve arbitrary linear optimization problems over $P$.

Let us first assume $y \in P$: otherwise we are done. Then, by Caratheodory's theorem, $y$ can be written as a convex combination of at most $m+1$ vertices of $P$. Moreover, such a convex combination is computable in polynomial time using a separation/optimization oracle for $P$: this is proved, for example, in Corollary 14.1g of Schrijver's Theory of Linear and Integer Programming. I.e., given an efficient separation oracle for $P$, we can construct a procedure that takes $y$ and returns vertices $v_1, \ldots, v_k$ of $P$, $k \le m+1$, and coefficients, $\lambda_1, \ldots, \lambda_k \in (0,1]$ such that $y = \sum_{i = 1}^k{\lambda_i v_i}$. Then, $y$ is a vertex of $P$ if and only if the procedure returns $v_1 = y$ and $\lambda_1 = 1$. It is clear that if this happens, $y$ is a vertex. Conversely, if this does not happen, then $y$ can be written as a convex combination of other points in $P$, which means that $y$ is not extremal, and, therefore, not a vertex.

Computing $v_1, \ldots, v_k$ and $\lambda_1, \ldots, \lambda_k$ using a separation/optimization oracle is not too hard. First you compute a vertex $u_1$ of $P$: figuring out  how to do this by optimizing over $P$ is a nice exercise. If $u_1 = y$, we are done. Otherwise, let $\ell$ be the half-line starting at $u_1$ and going through $y$, and let $z$ be the point where $\ell$ intersects the boundary of $P$. Then $z$ lies in a proper face of $P$, and we can recurse on that face to express $z$ as a convex combination of the vertices of the face. We finish by expressing $y$ as a convex combination of $z$ and $u_1$. See Schrijver's book for the details.


What is worst case complexity of number field sieve?

The number field sieve has never been analyzed rigorously. The complexity that you quote is merely heuristic. The only subexponential algorithm which has been analyzed rigorously is Dixon's factorization algorithm, which is very similar to the quadratic sieve. According to Wikipedia, Dixon's algorithm runs in time $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$. Dixon's algorithm is randomized.

All (heuristically) known subexponential algorithms require randomization. Dixon's algorithm needs to find integers $x$ such that $x^2 \pmod{n}$ is smooth (can be factored into a product of small primes) and "random", and the number-field sieve has similar but more complicated requirements. The elliptic curve method needs to find an elliptic curve modulo $n$ whose order modulo some factor of $n$ is smooth. In both cases it seems hard to derandomize the algorithms.

The nominal worst-case complexity of all these algorithms is infinity: in the case of the quadratic sieve and the number-field sieve you might always be generating the same $x$, while in the elliptic curve method you may always be generating the same elliptic curve. There are many ways around this, for example running an exponential time algorithm in parallel.


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


If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?

Generally speaking, for typical NP-complete problems, we don't have a good way to identify the computationally-intractable problems.  For instance, given an instance of SAT, we don't have any good methods to predict how long a SAT solver would take.  And for the most part we don't have anything that comes with any useful proofs.

So, in cryptography, we use cryptographic hardness assumptions, where the assumption does imply (in some sense) that we know which instances are computationally intractable.


Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

The smallest class containing linear time and closed under subroutines is P. The smallest class containing log space and closed under subroutines is still log space. So P and L are the smallest robust classes for time and space respectively which is why they feel right for modeling efficient computation.


Notation of sequences in rate distortion theory

In information theory notation, capital letters such as $X$ denote random variables, and lowercase letters such as $x$ mean their possible outcomes (i.e., fixed values). For example you can write the definition of expectation as $E[X] = \sum p(x) \cdot x$. Moreover, vector values are denoted using length as superscripts, for example $X^n$ means $(X_1, \ldots, X_n)$ (similarly for $x^n$). Moreover a substring $(X_i, \ldots, X_j)$ is often denoted by $X_i^j$. These slides seem to be consistent with this convention.


If $$f=(\Sigma_{i=1}^n x_i)^{2^n}$$
then it has ${2^n+n-1\choose n-1} \approx 2^{n^2}$ monomials and $L(f)=O(n)$.
By a counting argument, there are $2^{O(n\log n)}$ straight-line programs of length $O(n)$.
As $f$ has more monomials, for some we need a longer program.
In fact this argument gives a monomial $m$ for which $L(m)=\widetilde\Omega(L^2(f))$.


How many ephemeral stacks are required to simulate a queue in worst-case $O(1)$ time?

Not sure I fully understand your question, but it seems related to Problem 1.3.49 from Sedgewicks Algorithm book.


Strongly weight-balanced deterministic skip lists

I have been in contact with one of the authors. He confirmed this was a slip.

As stated above, this does not affect, in any way, any of the results of the paper.


Decide if number is negative (in URM machine like language)

Initialise $x \gets v$ and $y \gets -v$. Then increment both $x$ and $y$ in parallel until one of them is equal to 0.


Automata recognizing $X^*$ for a finite code $X$

Since this question received no answer for a long time, let me offer a partial answer to the first part of the question:

  What is known about (minimal) automata recognizing $X^∗$ for a finite code $X$?

Given a finite set of words $X$, the flower automaton of $X^*$ is the finite nondeterministic
automaton $\mathcal{A} = (Q, A, E, I, F)$, where $Q = \{1, 1\} \cup \{ (u, v)
\in A^+ \times A^+ \mid uv \in X \}$, $I = F = \{(1,1)\}$, with four types
of transitions:
\begin{align*}
 (u, av) &\enspace{\buildrel{a} \over\longrightarrow}\enspace
 (ua, v) \text{ such that } uav \in X,\ (u, v) \neq (1,1) \\
 (u, a) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1,
 1) \text{ such that } ua \in X,\ u \neq 1  \\
 (1, 1) &\enspace{\buildrel{a}
 \over\longrightarrow}\enspace(a, v) \text{ such that } av \in X,\ v \neq 1\\
 (1, 1) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1,
 1) \text{ such that } a \in X \bigr\}
\end{align*}
It is easy to see that this automaton recognises $X^*$. For instance, if $A= \{a, b\}$ and $X = \{a, ba, aab, aba\}$, the flower automaton of $X^*$ is the following

$\qquad\qquad\qquad$

Recall that an automaton is unambiguous if, given two states $p$ and $q$ and a word $w$, there is at most one path from $p$ to $q$ with label $w$. Then the following result holds:

Theorem [1, Thm 4.2.2]. The set $X$ is a code iff the flower automaton of $X^*$ is unambiguous.

The flower automaton also has an algebraic property which makes it relatively close to the minimal automaton. This property holds for any finite set $X$, but  is easier to state by getting rid of the empty word, that is, by considering a language as a subset of $A^+$ instead of $A^*$.

Recall that a finite semigroup $R$ is locally trivial if, for every idempotent $e \in R$, $eRe = \{e\}$. A morphism $\pi:R \to S$ is locally trivial if for every idempotent $e$ in $S$, the semigroup $\pi^{-1}(e)$ is locally trivial.

The transition semigroup $T$ of the flower automaton of $X^+$ is called the
flower semigroup of $X^+$. Since $T$ recognises $L^+$, there is a surjective morphism $\pi$ from $T$ onto the syntactic semigroup $S$ of $X^+$.

Theorem. The morphism $\pi:T \to S$ is locally trivial.

An important consequence of this result is that the flower semigroup and the syntactic semigroup have the same number of regular $\mathcal{J}$-classes.

References

[1] J. Berstel, D. Perrin, C. Reutenauer, Codes and Automata. Encyclopedia of Mathematics and its Applications, 129. Cambridge University Press, Cambridge, 2010. xiv+619 pp. ISBN: 978-0-521-88831-8


Given a network flow, are there bounds on the change in weight on nodes?

I think you're using a confusing sign convention, but I'll stick with it.  It's pretty easy to see that for any connected graph you can have all weight flowing into a single vertex (unless I'm misunderstanding something), so the lower bound you'll get is $$\Delta_i\geq -\sum_{i\in V}w_i.$$

Things won't really be better for bounding the square.  For example, if your graph is a star in which every leaf has $w_i=1$, then $$\sum_{i\in V}\Delta_i^2 = (|V|-1)+(|V|-1)^2.$$

You can't get a neighbourhood restriction, either, because you can take the example of a $k$-ary tree in which every leaf has weight 1 and all the weight goes to the root.

What you can get, however, is the possibly useful bound $$\sum_{i\in V}{|\Delta_i|} \leq 2\sum_{i\in V}w_i.$$

To see this, just note that when charge leaves a vertex you'll count it twice.


Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits?

Bipartite graphs are comparability graphs, and it's known (since Provan and Ball) that counting the number of independent sets in bipartite graphs is #P-complete.

J. S. Provan and M. O. Ball. The complexity of Counting Cuts and of Computing the Probability that a Graph is Connected.  SIAM J. Comput. 12 (1983) 777-788.

If I haven't mistaken, this should answer your question.


The coproduct is the disjoint union. Set-theoretically, you can think of forming the coproduct of the sets $A$ and $B$ as:

$$
 A + B \;\;\triangleq\;\; \{ (0, a) \;|\; a \in A \} \cup \{ (1, b) \;|\; b \in B \}
$$

Now it should be obvious that $A + A \not= A$.


Can abstract syntax trees be unparsed in subexponential time?

If the synthesized attributes compute a parse tree, then unparsing can be done in time linear in the size of the parse tree, assuming that string concatenation happens in constant time -- the obvious recursive algorithm on the parse tree will do the job.

I would guess XText is doing backtracking in order to minimize the number of parentheses in arithmetic expressions, line breaks, or some other pretty-printing criteria. However, for most languages it's possible to do that in linear time, as well.

See Norman Ramsey, Unparsing Expressions With Prefix and Postfix Operators. Software—Practice and Experience, 28(12):1327–1356, October 1998.


Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

I'm not sure, but you might be talking about what has been termed incremental computation.

The key idea behind incremental computation is to program in a way such that the program responds to input changes by updating its output while only re-evaluating those portions of the program affected by the change. Incremental computing is feasible in situations where input changes lead to relatively small changes in the output. Clearly, in limiting cases one cannot avoid a complete re-computation of the output, but in many cases the results of the previous computation may be re-used to obtain the updated output more quickly than a complete re-evaluation. In many cases, taking advantage of incrementality therefore dramatically improves performance, especially as the input size increases.

Designing and developing applications that respond to incremental modifications, however, is challenging: it often involves developing highly specific, complex algorithms.

This has lead some people to investigate the idea of moving the responsibility to avoid reevaluation where possible to the language run-time: instead of expecting the programmer to develop software for a particular application and a particular class of incremental modifications, the language run-time is tracking the dynamic data dependences of the computation and incrementally updating their output as needed. This is called  or self-adjusting computation, and  the person most associated with this programming language approach is Umut Acar. I recommend visiting his website for further information.

Note that ideas like this go back to the 1950s. Ad-hoc forms of incremental computing are heavily used in modern web-browsers because you don't want to reprocess ("reflow") the full page when a mutatation (e.g. Javascript performs a DOM operation) is performed.

I also recommend to consider the  related field of online algorithms.


Is there an example of a non context-sensitive language?

Type 0 grammars denote exactly recursively enumerable languages, and CSL = NSPACE[$n$] (e.g., Wikipedia).  Thus, your favorite proof of the Space Hierarchy Theorem gives an explicit language in, say, NSPACE[$n^2$] \ NSPACE[$n$], thus in UL \ CSL.


What are the inclusion relationships if any, between the classes Pspace, PLS, PPP, PPA and PPAD

Strictly speaking, PSPACE contains decision problems, while the others are search problems, so they live in different zoos, but FPSPACE would of course contain all the other problems. Then PPAD is contained in both PPA and PPP, whose relationship is unknown, but were separated by an oracle in Beame et al: Relative complexity of NP search problems. Here the PLS class was not considered, that was separated by an oracle later in Morioka: Relative complexity of local search heuristics and the iteration principle from all the other three classes. (For me this latter paper was too hard to read.) Without oracles, nothing is known.


Forms of types in the calculus of constructions

On the face of it, the result you're asking for is a normalization result, as it asserts that every well-typed term of a certain form has a head-normal form (of a certain shape).

However it is legitimate to ask whether your statement is equivalent to normalization of the CC, since you are only asking for head normal forms of a certain sub-class of terms.

In general, it doesn't make sense to ask whether two true statements are equivalent, since the answer is always (trivially) yes. However in this specific case, normalization of CC must rely on powerful meta-theory, since it implies consistency of some strong form of higher-order logic! So it makes sense to ask:

  In some weak meta-theory (say $\mathrm{PRA}$ or $\mathrm{PA}$) can we prove "CC is normalizing" $\Longleftrightarrow$ "Every closed term of type $*$ or $\square$ reduces to a product"?

The answer, I believe, is no.

Certainly, direction $\Longrightarrow$ holds, as you noted. But in the other direction, we have some counter-examples: in system $\mathrm{F_\omega}$, the fact that "type level" computations are normalizing is a consequence of the normalization of the simply-typed $\lambda$-calculus, and in Girard's system $U^-$, type level normalization holds, whereas it does not at the term level!

Things are a bit more complicated in the CC though, since type level terms can contain arbitrary term-level terms. The trick is that to compute head-normal forms, you don't actually need to dip into those terms to do reductions.

In PTS lingo, you only need to reduce $(*,\square, \square)$ and $(\square, \square, \square)$ redexes. But normalization of those only relies on the normalization of some variant of the simply typed $\lambda$-calculus (though I won't detail that argument right now). The hard part is showing that reducing the 2 types of redexes above must result in a head-normal form for terms of type $*$ or $\square$. You can do this by contradiction by supposing there is a head redex at that level, and showing that it must be of one of the two forms above.


Implementing D* Lite for Path-Planning - How detect Edge Cost Change?

In real-world code, you almost never have to "scan the graph for changes."  Your graph only changes when you change it in the code, so you already know exactly when and where it can change!

One common way of implementing this is to have a OnGraphChanged callback in your Graph class, which can be setup to call the OnGraphChanged method in your PathFinder class.  Then anywhere the graph changes in your Graph class, make sure the OnGraphChanged callback is called.


Would a proof that the traveling salesman algorithm can't be encoded on LAL also prove P!=NP?

Yes, in the same sense that if you prove that a specific NP-complete problem can't be reduced to a specific P-hard problem, then you also prove P!=NP. The only issue is that the reduction for which P-hardness hold must be "compatible" with the allowed encodings.

From the information you give in the question, I conclude that LAL is P-time hard. The article Light types for polynomial time computation in lambda calculus by R. Baillot and K. Terui confirms this, by showing that DLAL (dual light affine logic) is a P-complete subset of LAL.

My own experience is that many P-complete problems look attractive and natural. My favorites are linear programming and Horn-satisfiability, but I guess that DLAL (or LAL) look even more attractive to you. But even so they are attractive, using them for resolving N!=NP is probably futile. More than one reduction of specific NP-complete problems to linear programming has been published, but the reductions turned out to exponentially increase the size of the problem.


Covering a binary relation as a union of rectangles

...aha, found it! This is the bipartite dimension problem, and yes it is NP-hard without further assumptions.
Previously asked here: https://cs.stackexchange.com/questions/49266/finding-a-minimal-cover-of-a-subset-of-a-finite-cartesian-product-by-cartesian-p


Process modeling with fine-grained notions of location

Processes in Space by Luca Cardelli and Philippa Gardner is one paper in this direction. It specified a process algebra for describing the evolution of 3D structures.


UGC hardness of the predicate $NAE(x_1, ..., x_\ell)$ for $x_i \in GF(k)$?

I landed on this page from a search about NAE-3SAT.

I am pretty sure that for the problem you are asking, it should be NP-hard to tell if the instance is satisfiable, or if at most $1-1/k^{\ell-1}+\epsilon$ fraction of constraints can be satisfied. That is, a tight hardness result (matching what simply picking a random assignment would achieve), for satisfiable instances, and no need for the UGC.

For $k=2$ and $\ell \ge 4$, this follows from Hastad's factor 7/8+epsilon inapproximability result for 4-set-splitting (which can then be reduced to k-set splitting for $k > 4$). If negations are okay, one can also use his tight hardness result for Max ($\ell-1$)-SAT.

For $k=\ell=3$, Khot proved this in a FOCS 2002 paper "Hardness of coloring 3-colorable 3-uniform hypergraphs." (That is, he removed the original UGC assumption.)

For $\ell=3$ and arbitrary $k\ge 3$, Engebretsen and I proved such a result in "Is constraint satisfaction over two variables always easy? Random Struct. Algorithms 25(2): 150-178 (2004)". However, I think our result required "folding" i.e., the constraints will actually be of the form NAE($x_i+a,x_j+b,x_k$) for some constants $a,b$. (This is the analog of allowing negations of Boolean variables.)

For the general case, I don't know if this has been written down anywhere. But if you really need it, I can probably find something or check the claim.


Here we have $d \ll m$, i.e., we start with a little bit of good randomness, and we end up with a lot.  That's why it's called a "seed": you need something small to get you started, but you end up with a giant beautiful oak tree of randomness.

The other thing to know is that uniformly distributed bits are high-quality randomness, whereas bits with min-entropy $k$ are low-quality randomness.  So an extractor says: if you start with a little bit of high-quality stuff, and a lot of low-quality stuff, you can generate a lot of high-quality stuff.  That sounds potentially useful, at least in theory.

Do cryptographers use them in practice?  Well, they could, but honestly, practitioners usually don't.  Instead, they often use hash functions (and implicitly apply some kind of random oracle assumption).  That's not as principled -- using an extractor would lead to stronger, provable guarantees -- but it's somehow similar.  You could view extractors as providing solid theoretical foundations for this sort of thing.  They also have important implications for a variety of complexity-theoretic results, which I won't try to summarize here, so extractors are certainly interesting to study.


Why are these two definitions of PLS equivalent?

In general, searching a neighborhood for a better solution and reporting the whole neighborhood are two different things. There are for example some exponential neighborhoods, that is, neighborhoods whose size grows exponentially in the input length $n$, that can be searched in polynomial time for a better solution, see for example A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem by Deineko and Woeginger. The PLS framework, however, is not so much concerned with the running time of searching the neighborhood but with the number of iterations that are needed to find a locally optimal solution.


Finding a point outside of each of a set of polygons in a bounded space

If the polygons can overlap, the problem can be solved in $O(n^2)$ time (where $n$ is the number of sides of the polygons in total) by constructing the arrangement of line segments and maintaining as you construct it the number of polygons that cover each cell of the arrangement. There are $O(n^2)$ cells, arrangements can be constructed in $O(n^2)$ time, and it takes constant time per cell to maintain the covering number because it differs by one from the number of any neighboring cell.

You are unlikely to solve the problem significantly faster than $O(n^2)$ because it is equivalent in difficulty to 3SUM — see the original paper on 3SUM hardness, "On a class of $O(n^2)$ problems in computational geometry", by Gajentaan and Overmars (CGTA 1995).

With your specification that the polygons cannot overlap, the same approach works in $O(n\log n)$ time using an output-sensitive arrangement construction algorithm.


Borel-Cantelli Lemma and Derandomization

I don't think they mean derandomization in the traditional sense.  Try looking at the application of the BC lemma in this paper for an example of what they are talking about: http://www.cs.bu.edu/~reyzin/hash.html.

They say "asymptotic" because most BB separations apply to concepts like one-way functions, which are defined asymptotically.  Their result is instead a "concrete" bound that applies to all values of the security parameters, not just sufficiently large values.


Category theory and parsers --- references wanted

One of the very first applications of category theory to a subject outside of algebraic geometry was to parsing! The keywords you want to guide your search are "Lambek calculus" and "categorial grammar".

In modern terms, Joachim Lambek invented noncommutative linear logic in order to model sentence structure. The basic idea is that you can give basic parts of speech as having types, and then (say) ascribe English adjectives a function type taking noun phrases to noun phrases. (eg, "green" is viewed as function taking nouns to nouns, which means that "green eggs" is well-typed, since "eggs" is a noun).

Linearity arises from the fact that an adjective takes exactly one noun phrase as an argument, and the noncommutativity arises from the fact that the order of words in sentences matters. For example, an adjective's noun argument comes after the adjective ("green eggs"), whereas a prepositional phrase's noun phrase comes before the prepositional phrases ("green eggs with ketchup"). In categorical terms, you want a (non-symmetric) monoidal category which is closed on the left and the right. So the type $A\setminus{}B$ is the type of a phrase which has type $B$, when it is preceded by an $A$ on the left, and $B/A$ is the type of a phrase which has type $B$ when succeeded by $A$ on the right, and the type $A \ast B$ is the type of a phrase made by concatenating something of type $A$ with something of type $B$.

It turns out that Lambek grammars are equivalent to context free languages, though apparently this quite a difficult result -- showing CFGs are a subset of Lambek grammars is easy, but the other direction was only established in 1991 by Pentus.

A good exercise^H^H^Hpublication for the reader (ie, I haven't tried it, but think it would be cool to try) is to use Lambek calculus to reformulate Valiant's presentation of CYK parsing via boolean matrix multiplication, in categorical terms. As motivation, I quote from Lambek's 1958 paper The Mathematics of Sentence Structure:

  The calculus presented here is formally identical with a calculus constructed by G.D. Findlay and the present author for a discussion of canonical mappings in  linear and multilinear algebra.


How much bigger does a precomputed lookup table get when salt is added?

There are a couple of different things going on here, and you need to define your problem more clearly.

For starters, let's just look at a simple case where what is being stored in a database (for each user) is either $H(pw)$ or $s, H(s, pw)$ where $H$ is a hash function, $pw \in \{1, \ldots, N\}$ is a password, and $s \in \{0,1\}^\ell$ is a salt.

To attack a single user without a salt, the attacker can pre-compute $H(pw)$ for all possible values of $pw$ yielding a table of size $N$. Without knowing the salt, however, the attacker has to compute $H(s, pw)$ for all possible salts as well, thus requiring a table of size $N \cdot 2^\ell$. On the other hand, if the attacker does no pre-computation but instead just waits until it compromises the database and then obtains $s^*, H(s^*, pw)$, then we are back to the previous case where the attacker just has to compute $N$ values of $H(s^*, pw)$ to learn the password.

Thus, in the single-user case, the salt increases the attacker's off-line computation but does not increase the on-line computation needed.

Before continuing, let me note also that (in the case without the salt) the attacker can use  to obtain various time-space tradeoffs. Use of salts makes rainbow tables less effective as well.

Salts also help, in a somewhat orthogonal way, in the multi-user setting. To see this, note that if the attacker got the database of hashed passwords in the unsalted case, then using $N$ work he gets the passwords of all users. But in the salted case, assuming each of $M$ users is assigned a different salt, the attacker must do $M \cdot N$ work to recover all passwords.


Here the goal is to construct a decision problem D so that (a) if you can factor you can solve the decision problem in polynomial time and (b) if you can solve the decision problem you can factor in polynomial time.   There are a number of ways to do this.  To name just two:

D:  given n and k, does n have a divisor d satisfying 1 < d <= k?
D:  given n and j, is the j'th bit of the smallest nonunit divisor of n equal to 1?

If you can solve 1, then you can identify d using binary search.  Once you have d, you can then continue with n/d until the complete factorization is achieved.  2 is similar.


Easy problems with hard counting versions

One interesting example from number theory is expressing a positive integer as a sum of four squares.  This can be done relatively easily in random polynomial time (see my 1986 article with Rabin at https://dx.doi.org/10.1002%2Fcpa.3160390713), and if I remember correctly, there is now even a deterministic polynomial-time solution.  But counting the number of such representations would allow you to compute the sum-of-divisors function $\sigma(n)$, which is random polynomial-time equivalent to factoring $n$. So the counting problem is probably hard.


O(N) leader election on torus with orientation and non-positional identity

The idea is growing territories. That is, a candidate broadcast to neighbors that are $\alpha^i$ away in iterations.

The trick is in the analysis! (so it s not really clear) -- by getting to know the worst case of candidates, and the number of messages they send + setting $\alpha$ to a certain constant - we get $O(n)$

The solution can be found in N. Santoro book in Chapter 3 (oriented torus)


Why isn't it possible to recover/resume after an Exception?

"Resumable exceptions" are indeed a well-known idea in some programming language circles. In particular, Common Lisp has had resumable exceptions for a long time (so they are really not confined to research language; Common Lisp could be considered "mainstream", it has been widely available and relatively widely used for a long time).

For a discussion of resumable (or "restartable") exceptions, see for example this blog post by Manuel Simoni, which links to this dylan mailing-list post by Chris Double and the following Lambda-the-Ultimate discussion: Common Lisp exception handling.

You made the insightful guess, that resumable exceptions are not a good idea in all contexts. They can make resource handling harder and more generally anything related to side-effects must be considered very carefully when you add new control-flow entry points to a block of code.

It is possible for the exception raising code to decide on whether it should be resumable or not. This is natural if you see resumable exceptions as a combination of usual exceptions and continuations: you raise an exception and, in the attached data, decide whether or not to include a continuation to the rest of the computation; the handler then decide whether or not to invoke that continuation, that is "resume" the exception.

Effect handlers (try..catch block, using-like resource handler assuming lexical lifetime) can get confused if you re-enter the computation. Combining handlers and rich control flow is difficult and gave way to a lot of different approaches in the Lisp/Scheme communities (keywords: dynamic-wind, unwind-protect). You are certainly adding non-trivial complexity to the language.

I speak of "effect handlers" because, once you have such rich forms of control flow, you get very close to the ability of presenting arbitrary effects (exceptions, backtracking, but also logging, mutable state and input/output) on top of it. See for example Andrej Bauer and Matija Pretnar's work on Eff a language based on such "effect handlers".


When is a problem specified on a TM contained in non-uniform classes such as P/poly?

If $N$ were written in unary, then the language would be a unary language, i.e., a subset of $\{0,1\}^*$.   Every unary language is in P/poly.  That's because a P/poly machine is allowed a separate advice string, one per length of the input.  The advice string for length $n$ could just describe whether the input $1^n$ should be accepted or not.  Or, to put it another way, P/poly allows you to specify a separate circuit per input length; so you could use the "always output no" circuit for lengths $n$ such that $1^n$ is not part of the language, otherwise the "always output yes" circuit.  See https://en.wikipedia.org/wiki/P/poly.


The way I understand the difference is that the two concepts are used to give slightly different emphasis, but ultimately they are kind of the same thing. Since neither has a formal definition we cannot expect an exact answer without first limiting the scope to a particular understanding of "type" and "sort".

"Sort" is used when we want to say that there are several different, well, sorts of things that we need to distinguish. An example would be a theory of geometry with sorts "point" and "line".

"Type" is used when not only is there a need to distinguish different sorts of things, but proper attention is paid to the structure of the sorts/types themselves. Thus, typically we can form new types from old ones (products, sums, function types), we can have interesting relations between types (type equality, subtyping), etc. In contrast, one typically just specifies some sorts at the beginning, and then never pays much attention to the structure of the class of all sorts.

This at least is how I percieve the difference, other people may have different experiences.


The circuit characterization are by Kannan, Venkateswaran, Vinay, and Yao given in the paper:

A Circuit-Based Proof of Toda′s Theorem


How the Number of Clauses Change the Complexity of Worst Case k-SAT ?

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

And the answer, as anticipated by JeffE is yes.


Maximum computational power of a C implementation

As noted in the question, standard C requires that there exists a value UCHAR_MAX such that every variable of type unsigned char will always hold a value between 0 and UCHAR_MAX, inclusive.  It further requires that every dynamically-allocated object be represented by a sequence of bytes which is identifiable via pointer of type unsigned char*, and that there be a constant sizeof(unsigned char*) such that every pointer of that type be identifiable by a sequence of sizeof(unsigned char *) values of type unsigned char.  The number of objects that can be simultaneously dynamically allocated is thus rigidly limited to $UCHAR\_MAX ^{sizeof(unsigned\ char*)}$.  Nothing would prevent a theoretical compiler from assigning the values of those constants so as to support more than $10^{10^{10}}$ objects, but from a theoretical perspective the existence of any bound, no matter how large, means something isn't infinite.

A program could store an unbounded quantity of information on the stack if nothing that is allocated on the stack ever has its address taken; one could thus have a C program that was capable of doing some things which could not be done by any finite automaton of any size.  Thus, even though (or perhaps because) access to stack variables is much more limited than access to dynamically-allocated variables, it turns C from being a finite automaton into a push-down automaton.

There is, however, another potential wrinkle: it is required that if a program examines the underlying fixed-length sequences of character values associated with two pointers to different objects, those sequences must be unique.  Because there are only $UCHAR\_MAX ^{sizeof(unsigned\ char*)}$ possible sequences of character values, any program that created a number of pointers to distinct objects in excess of that could not comply with the C standard if code ever examined the sequence of characters associated with those pointers.  It would be possible in some cases, however, for a compiler to determine that no code was ever going to examine the sequence of characters associated with a pointer.  If each "char" was actually capable of holding any finite integer, and the machine's memory was a countably-infinite sequence of integers [given an unlimited-tape Turing machine, one could emulate such a machine although it would be really slow], then it would indeed be possible to make C a Turing-complete language.


Understanding the Beck-Chevalley Condition

So we need to construct a natural transformation $\phi : K(I)u^\# \Rightarrow u^*(K(J))$, which are functors from $D_J$ to $E_I$. So for every $d \in D_J$ we need a morphism $K(I)(u^\#(d)) \to u^*(K(J)(d))$ in $E_I$.

Since $K(I) \dashv H(I)$, this is equivalent to constructing a morphism $u^\#(d) \to H(I)(u^*(K(J)(d)))$ in $E_J$.
Now since $H$ is a fibred functor, $H(I)(u^*(e)) \cong u^\#(H(J)(e))$ for any $e$ so by composition with this isomorphism it is sufficient to construct a morphism $u^\#(d) \to u^\#(H(J)(K(J)(d)))$.
$u^\#$ is a functor so it is sufficient to construct a morphism $d \to H(J)(K(J)(d))$
So we can just use the unit of the adjunction $K(J) \dashv H(J)$.

The whole process is natural since every step is natural.


Polynomial method for complexity results

Some classic examples of the use of the polynomial method are:

Razborov-Smolensky's proof of "Parity not in $AC^0$" (lots of expositions available online, here is one)
Beigel-Reingold-Spielman's proof of "PP is closed under intersection"
Bazzi's result for fooling DNFs, and Braverman's proof of "Polylog independence fools $AC^0$"

Also, fourier analysis of boolean functions (here is a great course by Ryan O'Donnell)  has a HUGE collection of awesome results, my favourite being the Kushilevitz-Mansour-Nisan's proof of the Goldreich-Levin theorem.

Scott Aaronson had in fact given a tutorial at FOCS'08 on the "The Polynomial Method in Classical and Quantum Computing (ppt)".

Hope this helps.