Do we care about confluence because of unique normal forms?

I don't know what you mean by "practical", but confluence is very useful from the semantic point of view.  Hopefully other people will be able to give you other answers from other points of view (for instance from the standpoint of abstract term rewriting, which is not my specialty).

For instance, in $\lambda$-calculi and related languages, usually the meaning of expressions is given by (something like) the smallest congruence such that $(\lambda x.M)N=M\{N/x\}$ (this is usually called $\beta$-equivalence). Reduction arises (historically, as well as technically) as an orientation of the above equality, so that one may redefine $\beta$-equivalence as $(\leftarrow\cup\to)^\ast$ (the reflexive-transitive closure of reduction and expansion), and study $\beta$-equivalence by means of reduction (there are "practical" advantages to this: for instance, $M\simeq_\beta N$ is often undecidable, whereas $M\to N$ is always decidable, and sometimes you may be able to replace $\simeq_\beta$ with $\to$ in some definition or statement of some property).

Now, confluence is equivalent to the transitivity of the following relation:

$$M\sim N\quad\text{iff}\quad \exists P.\,M\to^\ast P,\,N\to^\ast P,$$

that is, $M\sim N$ precisely when $M$ and $N$ have a common reduct. Therefore, if you have confluence, $\sim$ is an equivalence relation, and in fact it coincides with $\beta$-equivalence. The relation $\sim$ is technically much more convenient than $(\leftarrow\cup\rightarrow)^\ast$ (it involves only reduction, not arbitrary chains of reductions/expansions). So, if a calculus is confluent, it is usually a quite useful fact to know, although of course it is often only used to prove uniqueness of normal forms (which by the way, as you observe, I wouldn't know how to prove otherwise).

Also note that confluence is a sort of "practically necessary" condition for $\beta$-equivalence to be meaningful: many calculi of interest in practice are Turing complete, in which case the lack of confluence usually implies that everything is $\beta$-equivalent (one is likely to be able to concoct a term which non-deterministically reduces to every possible term).  So, in presence of confluence, $\simeq_\beta$ is a meaningful notion which may be taken as the basis, for instance, of denotational semantics; in absence of confluence, something else must be found (like some kind of behavioral equivalance, as in process calculi, which is much more complex).

Edit: as suggested by Guido, I add a further note on the additional interest of confluence with respect to uniqueness of normal forms (UN), which I had not thought of when writing my answer.

Confluence implies the following property: $N\simeq_\beta N'$ with $N$ and $N'$ normal implies $N=N'$ (syntactic equality). In other words, distinct normal forms cannot be $\beta$-equivalent. (This immediately follows from the characterization of $\simeq_\beta$ as $\sim$ given above). This property is interesting because it implies the consistency of $\simeq_\beta$ seen as an equational theory, as soon as there is more than one normal form (as is the case, for instance, in the $\lambda$-calculus).

On the other hand, UN is not enough to obtain the above property, as shown by the following rewriting system:

$$N\leftarrow M\to\Omega\leftarrow M'\to N',$$

in which all five terms are distinct and $\Omega$ is a term that reduces to itself.  We have $N\simeq_\beta N'$ and yet $N$ and $N'$ are distinct normal forms.


Regular expressions of families of regular expressions

Regular languages are closed under union, concatenation and star, so regular expressions under regular expressions describes regular languages. So, regex, that describe regex, that describe regex still describe family of regular languages, and you can continue that process as long, as you want.

Here, by «describe» I mean that first, you have just regex, like $(aa|b)^+ = R_0$  and regex $(a|bb)^+ = R_1$, than you describe regex level 1 like $(R_0R^*_1R_0)$, this regex describe languages  $(aa|b)^+(aa|b)^+$, $(aa|b)^+(a|bb)^+(aa|b)^+$, $(aa|b)^+(a|bb)^+(a|bb)^+(aa|b)^+$, …  and so on.

In other terms regex under regex can be described using composition operation. Let $L$ be a regular language under alphabet $\Sigma$ and $|\Sigma| = n$. Consider regular languages $L_{\sigma_1}, L_{\sigma_2}, \ldots, L_{\sigma_n}$  under some alphabet $\Delta$. So, for each word $w$ from $L$ we substitute letter $w[i] = \sigma_j$ by corresponding language $L_{\sigma_j}$, so $w = w[1]w[2]\ldots w[k] \to L_{w[1]}L_{w[2]}\ldots L_{w[k]} $  and union of all such languages, forms language $comp(L,L_1,\ldots,L_n)$. So, level of regex under regex is just number of composition operations, that were used. And regular languages are closed under composition-operation.

But there are some interesting results obtained by technique that's very closed to the one, that  you describe. I mean the $\delta-$operation. $\delta(L)$ is a such language, that every word from $\delta(L)$ yields by such tree, that every path in that tree lies in $L$. To learn more about it see the paper .


If $GI$ is in $coNP$, then we would have the result: $GI$ is not $NP$-complete unless $NP=coNP=PH$.  (Currently known: $GI$ is not $NP$-complete unless $\Sigma_2 P = \Pi_2 P = PH$).

Since $GI$ is in $coAM$, obviously derandomizing $coAM$ (doi link) would put $GI \in coNP$, but I don't know of any candidate graph properties for putting $GI \in coNP$ otherwise. I look forward to more answers though!

Interestingly, in that paper they also show that Graph Non-Isomorphism has subexponential size proofs -- that is, $GI \in co NSUBEXP$ -- unless $PH = \Sigma_3 P$.  This is at least headed in the direction of showing conditionally that $GI \in coNP$.


This only aims at partially answering the first question of the post:

  What are some directed problems that remain NP-hard on DAGs ?

In [1], a few natural problems on directed graphs are given that remain NP-hard on DAGs. The motivation of the paper is to find a "good" treewidth-like measure for digraphs. They argue that the drawback of many measures for digraphs is that they are constant for DAGs, but many directed counterparts of natural problems remain NP-hard on DAGs. For more on this topic, see also [2] and the references of these papers.

[1] Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith: On Digraph Width Measures in Parameterized Algorithmics. IWPEC 2009:185-197. Full version

[2] Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar: Are there any good digraph width measures?. IPEC 2010, to appear. arXiv


GI-hard graph problem not known to be $NP$-complete

After extensive search, I found the Legitimate Vertex Deck problem (LVD) which is related to the famous Graph Reconstruction conjecture. A deck of graph $G(V, E)$ is a multi-set of graphs $F = \{G_1,G_2, . . . , G_n\}$ such that $G_i$ is isomorphic to $G−v_i$ ($G-v$ is a graph obtained from $G$ by removing $v$ and its incident edges). ($|V|=n$)

The k-LEGITIMATE VERTEX-SUBDECK problem, given multi-set of graphs $F= \{G_1,G_2, . . . , G_k\}$, Decide whether there is a graph $G$ such that $F$ is a subset of its vertex-deck (k-LVD =$ \{[G_1, . . . , G_k]|(∃G)[[G_1, . . . , G_k] ⊆ vertex-deck(G)]\}$)
where $k \ge 3$

k-LVD problem is $GI$-hard and is not known to be $GI$-equivalent. It is open problem whether k-LVD is $NP$-complete (for $k \ge 3$). See the open problems section of Complexity results in graph reconstruction.

Also, the paper suggests the existence of a problem of intermediate complexity between $GI$ and k-LVD. The problem is LVD= n-LVD where all $n$ candidate cards are given (Input for LVD is $F= \{G_1,G_2, . . . , G_n \})$.


About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective

Yes, there are some papers. The most relevant one to your question might be: https://arxiv.org/pdf/1611.00756.pdf


Transactional partially-ordered message queuing

A standard RDBMS should be enough; this is a sketch of how it can be done in a RDBMS even without BEGIN TRANSACTION capabilities (a mix of SQL/pseudocode):

Create two tables with the following columns:

Table MESSAGES:
*MSGID            int not null auto_increment,  (primary key)
SEQID             int,
SEQORDER          int not null auto_increment,
RETRIES           int default 0,
MSGDATA           varchar(...)

Table SEQUENCES
*SEQID            int not null,  (primary key)
SEQLOCKED         int,
SEQHASH           varchar(256)

The Generators can simply insert into the MESSAGE table their requests (and optionally fill the SEQUENCES table):

For example suppose a Generator must insert a message with SEQID=120

1) INSERT INTO SEQUENCES VALUES (120, 0, MD5(RAND()) )
// if the SEQID is already present the previous query
// just fails, do not worry about it
2) INSERT INTO MESSAGES (SEQID, MSGDATA) VALUES (120, 'bla bla bla')
// the auto_increment option in columns will assign correct values for MSGID and
// SEQORDER

The Consumers can do their stuff without using BEGIN TRANSACTION in this way:

// retrieve the SEQID of an unlocked sequence that contains a message:
1) SELECT * FROM SEQUENCES s LEFT JOIN MESSAGES m ON  m.SEQID = s.SEQID
      WHERE SEQLOCKED = 0
      ORDER BY SEQORD LIMIT 1
// suppose we retrieve a sequence with SEQID=120 and SEQHASH='102f...'
// we first lock the sequence using a standard tecnique:
2) newhash = MD5(RAND())
3) UPDATE SEQUENCES SET (SEQHASH=newhash, SEQLOCKED=1)
     WHERE (SEQID=120 AND SEQHASH='102f...')
4) IF (records_updated() = 1)   // lock acquired
   // we pick the older message of the sequence
   4.1) SELECT * FROM MESSAGES s WHERE SEQID=120 ORDER BY SEQORD LIMIT 1
   4.2) .... if we get a message (suppose MSGID=1234) then process it ....
   4.3) IF everything is ok THEN
          DELETE MESSAGES WHERE MSGID=1234
        ELSE
          UPDATE MESSAGES SET (RETRIES = RETRIES+1) WHERE MSGID=1234
   // finally we must unlock the sequence
   4.4) UPDATE SEQUENCES SET (SEQLOCKED=0) WHERE SEQID=120

restart from step 1)


One can show a lower bound for the data structure you are asking for under the Strong Exponential Time hypothesis. In particular, if all the entries have one bit, then one can use the data structure to do subset queries: i.e the data structure stores a family ${\cal F}$ of $N$ sets, each of size at most $k$. Then, the user may make "subset" queries - give a set $S$ and ask whether there is an $X \in {\cal F}$ such that $S \subseteq X$.

Such a query can be supported if we have a "universal index" - if we look for the lexicographically first entry coming after $S$, where we sort first by the columns where $S$ is $1$ and then along the ones where $S$ is $0$ then any element appearing after $S$ according to this order must be a superset of $S$.

Now, subset queries are equivalent to "dot product = 0" queries from this awesome answer by Ryan Williams - go read it. I will just summarize the effects of this answer on the universal index problem; assuming the Strong Exponential Time Hypothesis one can't support queries with running time $O(poly(k)N^{0.99})$, even if the family ${\cal F}$ is given in advance and we only have queries of type $3$ (i.e the data structure is static), and we have $poly(N,k)$ pre-processing time.


Growth rate of primitive recursive functions

The answer is no, there is no exponential bound on PR.
PR contains Knuth's up-arrow functions, Elementary functions, etc.
PR is equal to the union of Grzegorczyk hierarchy.
Exponential functions appear at the third level of the Grzegorczyk hierarchy.

PR can alternatively be defined using the iteration function in place of recursion.

A good reference for information about these classes is the first chapter of second volume of "Classical Recursion Theory".

Also have the general function growth hierarchies like
Grzegorczyk hierarchy,
slow-growing hierarchy, and
fast-growing hierarchy.


Computational complexity and reductions to linear programming

ILP is NP-complete.  This has a few implications to your question.

  Moreover, I believe that there are inherently nonlinear problems that cannot be expressed in the form of LP nor ILP.

As long as you consider problems in NP, no, all problems in NP can be rewritten as ILP in polynomial time.  If you consider problems not in NP, then they cannot be expressed in the form of LP or ILP because both LP and ILP are in NP.

  is there any known relation between the complexity of a problem and it's expressibility in the form of (integer) Linear Programming (except the obvious facts stated in the previous paragraph)?

This is essentially asking which special cases of ILP can be solved in polynomial time.  One of the fairly large classes of ILP which can be solved in polynomial time is ILP with totally unimodular constraint matrices; see Wikipedia.  But if you want a very general result, it is unlikely that you get anything more than tautological statements such as “the optimization problem is in P if there is a polynomial-time algorithm to solve it.”  Indeed, your question is formally equivalent to asking which problems in NP are in P, and obviously we do not know any necessary and sufficient characterization which is easy to check.


computing maximal bit density over a FSM

First, you mean "sup" rather than "max", because it is easy to construct examples of regular languages, such as 00(011)*00  where there is no max.  (The sup may not be attained.)

Second, by "FSM" I assume you mean finite automaton.

Then I claim that either the maximum bit density is achieved by a word of length < n, the number of states, or it is given by the maximum bit density over a loop of size at most n.
This means there are only finitely many cases to check, for each DFA.  Probably with a bit more work, one can get a polynomial-time algorithm out of it.

To see the claim, first note that if we compute the bit density of the sequence of words
$(u v^i w)_{i \geq 0}$ then this sequence is either (a) strictly increasing, (b) strictly decreasing, or (c) constant.  If the maximum bit density is attained and occurs at a shortest word x of length $>= n$, by the pumping lemma we can write $x = uvw$ where $|uv| \leq n$.  In each case we get a contradiction.  In (a) there are words with higher bit density, like $uv^2w$; in (b) there is a word with higher bit density, namely $uw$, and in (c) there is a shorter word with the same bit density.

The remaining case is that the maximum density is not attained.  A slightly more complicated argument, almost exactly the same as in my paper with Schaeffer, then proves the claim about the loops.

The Critical Exponent is Computable for Automatic Sequences.
Luke Schaeffer, Jeffrey Shallit
Int. J. Found. Comput. Sci. Vol. 23 No. 8 Pg. 1611-1626
Year: 2012


Variant of Subset Sum Problem with Changing Bound

It's still NP-complete, via a reduction from the partition problem (in the form of: given a collection of $n$ positive numbers $x_i$, where $n$ is even, partition the numbers into two subsets with equal sums). This exact form of the partition problem is not one of the ones mentioned by Garey and Johnson (SP12); in particular they don't mention the constraint that the numbers be positive. But they do mention a variation of partition in which the numbers are paired and you have to use one from each pair. By adding the same positive number to both numbers in a pair you can make them all positive, and then by adding different large powers of two to different pairs you can get an instance where
the one-from-each-pair constraint is the only way to solve it, and doesn't need to be specified as an explicit constraint.

In the partition problem, we can assume without loss of generality that $\sum x_i=1$, since multiplying or dividing the inputs by a scalar doesn't change the problem. We'll also assume that $n$ is even, since that's what you get from the reduction from the paired variation of partition. Thus, we are trying to find a subset whose sum is $1/2$. Note that, if there is such a subset, then its complement is also a solution; in particular, one of the two solutions has at least $n/2$ elements.

Given such a partition instance, set up an instance of the changing-bound problem with $T=2n$ input values: $n$ of them of the form $1+x_i$, and another $n$ of them that are all equal to $1$. Set $k=(3n-1)/2$. Because $k$ is so large, any near-optimal solution must include at least one of the values that is equal to $1$, so this will necessarily be the minimum value. The goal of the changing-bound problem is then to have the sum of the whole set (including its minimum) come as close as possible to $(3n+1)/2$ without exceeding it. If the partition problem has a solution, then we can turn it into a solution to the changing-bound problem that exactly reaches this goal of $(3n+1)/2$, by choosing a partition solution with at least $n/2$ elements and padding them with the desired number of $1$s. And conversely, if the changing-bound problem has a solution with the exact value $(3n+1)/2$, then the subset of this solution consisting of the values of the form $1+x_i$ also give a solution to the partition instance.


Can Non-termination be considered an algebraic effect?

Non-termination can be considered an algebraic effect up to a point. It's an exception that cannot be handled. More precisely, we may introduce a nullary operation (constant) $\bot$ which signifies non-termination, but then we disallow handling it, as that would allow us to implement the Halting oracle.

Such treatment of non-termination is a bit naive. A more satisfactory account of non-termination would use domain-theoretic semantics, or a lifting monad.


Are edge-vertex graphs of polytopes (decent) expanders?

For 0/1-polytopes (all vertex coordinates are 0 or 1), this is not known to be true.  There is a conjecture by Mihail and Vazirani that the edge expansion of the graph of a 0/1-polytope is at least one.  More information is described in a paper by Volker Kaibel.

I should note two things.  (1) For 0/1-polytopes, the Hirsch conjecture is true.  (2) When performing a random walk on the vertices of a polytope, we need to take care of possible degeneracy.  One vertex can correspond to a lot of bases, and so the walk can stay at the same vertex if we perform a random walk over the bases.  If we want to perform a random walk over the vertices, we need to have a procedure that gives a random adjacent vertex.


Does there exist an ontology for algorithms?

[More of an extended comment.]

I think I disagree with the premise of your first paragraph... That being said, while I don't know of a database, there has been some work systematically studying small Turing machines. See Small universal monotone Turing machines, https://cstheory.stackexchange.com/a/20980/129, https://cstheory.stackexchange.com/a/11614/129. While some of this is interesting, I would say it has yet to "bear much fruit (i.e., understanding)." I hope someday it will.

There's also a mismatch between listing small Turing machines and understanding algorithms that are built by people (much as there is still a gap between listing all genes and understanding what they do, though not quite the same). Namely, an ontology of algorithms that are built by people should including things like those mentioned in Thomas Klimpel's comment. (Note: it should also include holographic algorithms, a relatively recent surprise in the ontology of algorithms!) But an ontology of small TMs looks completely different. Given how small a corner of the space of algorithms people have explored, and given the uncomputable problems involved, I highly doubt there would ever be a "complete" ontology of algorithms - either in the sense of small TMs or in the sense of all algorithms people would build. But I suppose having a partial one might still be interesting for some purposes...


Using a probability distribution in the fooling set technique for communication complexity

It is true that there is "no randomness" in the sense that the protocol is not randomized and is supposed to work on all inputs. However, that does not mean that we are not allowed to use probability distributions in the analysis of the algorithm.

This theorem says that when you wish to prove a lower bound, then for the purpose of the analysis, you can take whatever distribution $\mu$ you like, and the communication complexity would be at least $\log(1/\delta)$, where $\delta$ is the largest probability of a monochromatic rectangle.

If you do not like thinking about it in terms of probability, you can also think about it as a counting argument. Suppose you could prove that every monochromatic rectangle contains at most $t$ pairs. Then, this would imply that the communication complexity must be at least $\log\left(\frac{|X \times Y|}{t}\right)$ by simple counting.

Now, the foregoing argument is exactly equivalent to applying the theorem you stated with $\mu$ being the uniform distribution and $\delta$ being $\frac{t}{|X \times Y|}$. The theorem generalizes this argument to work with probability distributions other than the uniform.

In the case the distribution is not uniform, this is equivalent to augmenting the counting argument with weights. Suppose you assign each pair some weight such that

The total weight of $X \times Y$ is $W$.
Every monochromatic rectangle has weight at most $w$.

Then, clearly the communication complexity must be at least $\log(W/w)$ (since there must be at least $W/w$ monochromatic rectangles). The theorem you stated is just a different way to look at this argument.


Online transitive closure better than O(N^2) per edge addition

O(n) time per edge addition:

G. F. Italiano (1986): Amortized efficiency of a path retrieval data structure, Theoretical Computer Science 48, 273–281.
J. A. La Poutré and J. van Leeuwen (1988): Maintenance of transitive closures and transitive reductions of graphs, Proc. WG 1987.


Variation on partial Set Cover with penalties

This answers question (2):

The greedy heuristic for Set Cover / Maximum Coverage always picks the set which contains the maximal number of uncovered elements.

Assuming your modification for the heuristic is picking the set which greedily increases the solution profit, you might end up in a lousy approximation ratio.

Consider the following example:
$$A = \{a_1,a_2,\ldots a_{k}\}, B=\{b_1,b_2,\ldots b_k\}$$
$$C = \{C_1\} \cup C_2$$
$$C_1= A\cup B \setminus\{b_1\}$$
$$ C_2 = \{\{a_{i},b_1\}|i\in[k]\}$$

The greedy heuristic will output $C'=\{C_1\}$, so the profit is $1$, while the optimal solution is $C_2$ which gives profit $k-1$.


This is a partial answer that only gives a candidate intermediate $NP$-complete problem.

$k$-Equal Sum Subsets problem: Given a multiset of $n$ positive integers $A = \{a_1,...,a_n\}$, are there $k$ nonempty disjoint subsets $S_1,...,S_k ⊆ \{a_1,...,a_n\}$ such that $sum(S_1) = ... = sum(S_k)$?

The problem is weakly $NP$-complete when $k= O(1)$ and therefore has pseudo-polynomial time algorithm for any fixed constant integer $k > 2$. However, it becomes strongly $NP$-complete when the number of equal sum subsets $k= \Omega(n)$.

If $k= \omega(1)$ and $k= O(\log n)$ then $k$-Equal Sum Subsets problem is a candidate intermediate $NP$-complete problem (as described in the question). This problem is neither known to have a pseudo-polynomial time algorithm nor proven to be $NP$-complete in the strong sense.

Reference:

CIELIEBAK, EIDENBENZ, PAGOURTZIS, and SCHLUDE, ON THE COMPLEXITY OF VARIATIONS OF EQUAL SUM SUBSETS, Nordic Journal of Computing 14(2008), 151–172


Questions about Farhi's pre-Adiabatic paper

Everything interesting happens in this paper happens within the 2D subspace generated by the two vectors $|s\rangle$ and $|w\rangle$. The vector $|r\rangle$ is a vector from this subspace orthogonal to $|w\rangle$, giving us the basis $|w\rangle, |r\rangle$, where the analysis will be very simple (using 2x2 matrices).

The norm in the second question is simply $|||a\rangle||^2 = \langle a | a \rangle $. The meaning of individual terms in the sum is: "Does the result of our (Hamiltonian) algorithm actually get away from the (useless) state we would get without applying the oracle at all?" If this term is small for many different instances (different $w$'s), the algorithm doesn't work, as it would likely give the same (wrong) answer for these instances. Thus, if the sum over all of the $w$'s were small, it would tell us that the algorithm fails. If it is large, it doesn't immediately mean it works, however, having the sum large is a necessary condition for a successful algorithm.


Why would the term "dynamically typed" be considered a misnomer?

The discussion in the section surrounding that paragraph in Pierce's book explains why this is so. In particular, consider the definition of "type system" given on the page before:

A type system is a tractable syntactic method for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute.

Note how aspects like "syntactic method" and "classifying phrases" mean that it applies to "source" programs, i.e., inherently is a static notion. Moreover, in actual type theory, programs that do not "type-check" are not even considered programs. The type system defines the set of well-formed programs. Something that's ill-typed has no meaning.
One could argue that this is the wrong definition. But it is shared by most researchers in the field and certainly by the ones working on type theory. It matches the notion of a "type" as established in mathematics and logic (lambda calculus, type theory). On the other hand, it would be difficult to come up with a sufficiently accurate definition of "type system" that would encompass "dynamic typing" without bordering on technically meaningless.
So from that technical point of view, a dynamic language is untyped, in the same way the untyped lambda calculus is (or equivalently, it has only one single type, such that every program is accepted as well-typed). Dynamic checks are not really on types but on the shape of values, which sometimes carry type-like "tags".


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

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

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

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

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

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

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

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


What is the contribution of lambda calculus to the field of theory of computation?

$\lambda$-calculus has two key roles.

It is a simple mathematical foundation of sequential, functional, higher-order
computational behaviour.
It is a representation of proofs in   constructive
logic.

This is also known as the Curry-Howard correspondence.  Jointly,
the dual view of $\lambda$-calculus as proof and as (sequential,
functional, higher-order) programming language, strengthened by the algebraic feel
of $\lambda$-calculus (which is not shared by Turing machines), has lead
to massive technology transfer  between logic, the foundations of mathematics, and programming.
This transfer is still ongoing, for example in homotopy type theory.  In
particular the development of programming languages in general, and
typing disciplines in particular, is inconceivable without
$\lambda$-calculus. Most programming languages owe some degree of debt to
Lisp and ML (e.g. garbage collection was invented for Lisp), which are direct descendants of the $\lambda$-calculus. A
second strand of work strongly influenced by $\lambda$-calculus are
interactive proof assistants.

Does one have to know $\lambda$-calculus to be a competent programmer, or
even a theoretician of computer science?    No. If you are not interested
in types, verification and programming languages with higher-order
features, then it's probably a model of computation that's not
terribly useful for you. In particular, if you are interested in complexity theory, then
$\lambda$-calculus is probably not an ideal model because the basic
reduction step $$(\lambda x.M) N \rightarrow_{\beta} M[N/x]$$ is powerful: it can make an arbitrary number of copies on $N$, so
$\rightarrow_{\beta}$ is an unrealistic basic notion in accounting for
the microscopic cost of computation. I think this is the main reason why
Theory A is not so enamoured of $\lambda$-calculus. Conversely, Turing machines are not terribly inspirational for programming language development, because there are no natural notions of machine composition, whereas with $\lambda$-calculus, if $M$ and $N$ are programs, then so is $MN$. This algebraic view of computation relates naturally to programming languages used in practice, and much language development can be understood as the search for, and investigation of novel program composition operators.

For an encyclopedic overview of the history of $\lambda$-calculus see History of Lambda-calculus and Combinatory Logic by Cardone and Hindley.


No, it's not regular.  Since it allows arbitrary embedding of balanced delimiters, it must be at least context-free.

For example, consider an array of arrays of arrays:

[ [ [ 1, 2], [2, 3] ] , [ [ 3, 4], [ 4, 5] ] ]

Clearly you couldn't parse that with true regular expressions.


Is there a computing problem which is in quasi-polynomial time but is (maybe) not in $\beta P$?

While I don't know a specific (conjectured) example in $QP-\beta P$, there is still rather compelling evidence that $\beta P$ is a proper subset of $QP$. Namely, these classes behave very differently in their relationship to $NP$:

$\bullet$ It is obvious from the definition that $\beta P\subseteq NP$.

$\bullet$ On the other hand, $QP\subseteq NP$ is not known, and it would be very hard to prove, since it implies $P\neq NP$. (In fact, it is an even stronger statement than $P\neq NP$.)

Such a very different behavior relative to $NP$ seems to provide a fairly strong reason to believe that $\beta P\neq QP$.


I am assuming that we are talking about bounded fan-in circuits.

If a language can be decided by a deterministic Turing machine in time $t_n$ and space $s_n$, then it can be computed by a circuit of size $O(t_n\log s_n)$. The depth can be reduced to $d_n = l_n \log t_n = O(l^2_n)$ where $l_n = \max (s_n,\log n)$.

In the non-uniform circuit case and non-uniform TMs (NU-TM)  (when the space used by a TM includes the log of space used on the oracle tape containing the advice), if the language has circuits of size $c_n = \Omega(n)$, then it can be decided by an NU-TM where time $t_n = O(c^2_n)$ and space $s_n = O(c_n)$.

Similarly for depth $d_n = \Omega(\log n)$, we get an NU-TM with time $t_n = O(n2^{d_n})$ and space $s_n = O(d_n)$.

Form these results we get:

$Size(T^{O(1)}) = NU\text{-}Time(T^{O(1)})$ if $T(n) = \Omega(n)$,
$Depth(S^{O(1)}) = NU\text{-}Space(S^{O(1)})$ if $S(n) = \Omega(\log n)$.

I think we can extend this to uniform classes if we use appropriate uniformity conditions on both sides.

See also chapter 9 of Wegener's book "The Complexity of Boolean Functions" for more details.


I hadn't thought about the Separating Words problem before, but based on looking at the Robson paper referenced in the linked answer, I don't immediately see how techniques from GI would apply.

At a high level, note that techniques for GI such as Luks's and Babai's all compute the automorphism group of a graph, and are very group-theoretic in nature. In the Separating Words Problem, I don't see how groups like this would naturally arise (though perhaps I've just missed it).

At a more detailed level, before asking whether Babai's algorithm has any application here, it is worth asking whether Luks's technique could apply, as this is the framework of Babai's algorithm. (Babai's main improvement was to handle the bottleneck case of Luks's algorithm - Johnson groups - much more efficiently.) Again, my answer to this is more or less the same as in the previous paragraph.

For example, is there a natural symmetry group (aside from a permutation of the alphabet) that preserves the length of the separating word? Even if there were, I don't see how the techniques would apply, but it might at least provide a foothold.

Now, of course, there are lots of combinatorial and group-theoretic lemmas proved along the way in Babai's paper, and it's impossible to say that those won't be relevant, but at least at first glance I don't see how.


A continuous center point of a convex spherical polygon

For your second question...

For any distribution, if you take a sample $R$ of size $O(1/epsilon^2 )$ of it, and compute its center point, it is going to be a $\geq (1/3-\epsilon)$-center point, with probability $\geq 1-\epsilon^{O(1)}$ by the $\epsilon$-net theorem (well, more precisely the $\epsilon$-sample theorem). You can apply this to a polygon - you just need to sample points uniformly inside the polygon. This works in any constant dimension.

Similar ideas were used in the paper "Approximating Center Points with Iterated Radon Point". Or so I believe... ;)

Computing the exact center point for a general polygon is nasty as far as I know. There was a paper in the 90s by Dan Halperin on maintaining the area bisector of a polygon, and it was painful, if my memory serves me right.


Finding a subset of a set in a collection of sets

Your problem sounds to me a lot like Information Retrieval(IR). There you have a collection of sets of words (also known as documents) and you want to find not only existence, but all the sets/documents that satisfy the query condition.

Since the set elements are numbers , you can take advantage of teh apparent structure, thus a signature index would be of much use.

I would recommend taking a look at IR papers, especially related to dictionary structures, like trees, but note that space is usually an issue for those systems, whereas it might not be an issue for your case.


Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$

First, let me add some more to the known results section, specific to your question.

$B$ must occur in another RHS than $A\rightarrow aB$, or we could just copy the rule that has $B$ on the LHS instead of $B$ to the above rule to get a smaller system.
In any other RHS that has $B$, there can be no terminal symbol because instead of $aB$ we could write $A$.
$A$ must occur at least $4$ times on the RHS, otherwise, we could just write $aB$ instead of it.

This already shows that $n$ will be quite large that satisfies these. However, I think such an $n$ might exist. Below I give a set of rules for $n=93$ with $28$ symbols and I challenge all to make a smaller system! (If the challenge is too easy, generalize it in the obvious way...)

$S\rightarrow AAAACCC$

$A\rightarrow aB$

$B\rightarrow aaa$

$C\rightarrow DDD$

$D\rightarrow BBB$

Update

Well, this is not optimal for any $n$ as shown by Peter in the comment...


Infinitary Counting Logics: 1-sorted vs. 2-sorted framework

The answer to the question "Can we diretcly express graph canonization Grädel's way" is no.

However, we can substitute each $v<w$ in a $\{E,<\}$-formula with a $\{E\}$-formula (Libkin's wy) by Logical Transduction (also known as Logical Interpretation). This $\{E\}$ formula is a sentence without free variables. Hence, we can use a construction (by Grädel and Otto in the same paper) to eliminate all number variables which results in a Grädel-formula with the same number of vertex variables.


Computing volume of high-dimensional convex polyhedra

You can try and use qhull http://www.qhull.org/ - it can compute the volume of the convex hull of the vertices. However, a priori I do not see any reason for it to perform reasonably for your range of numbers. If qhull does not work, you can try CGAL/GALIA. In the worst case, you can try and impelement one of the random walk algorithms you mentioned - they should not be too hard to implement in this case, but the constants involved might be very large...


What is the formalism behind ?- (query) in Prolog?

Prolog embodies the idea of computation as proof search. That is: a program is a formula which we would like to satisfy, the computation is the proof search, and the result is the witness for the formula.

To make this idea work we need to reformulate the rules of first-order logic so that they can be read as instructions for execution of a proof search. We may have to give up certain essentially non-computational parts of logic, such as excluded middle. We may further have to restrict the formulas that are allowed to appear, or else we will get something that looks like a general theorem prover insetad of a programming language.

I recommend chapter 8 of Frank Pfenning's notes on Computation and Deduction where these ideas are explained in detail.


Minimizing entropy plus a modular function

Unless I'm mistaken, you can solve your problem in $O(n\log n)$ time using a greedy algorithm.

Minimizing $f(S)$ is equivalent to maximizing
$$\textstyle g(S') = \sum_{i \in S'} b_i + \big(\sum_{i\in S'} \alpha_i\big) \log \sum_{j \in S'} \alpha_j$$
for $b_i=w_i + \alpha_i\log(\alpha_i)$.  Here $S'$ is the complement of your $S$.

Assume WLOG that $\alpha_i>0$ (otherwise $i\in S'$ iff $b_i>0$).

Introduce indicator variable $x_i$ for the event that $i\in S'$,
then relax the problem by allowing $x_i\in[0,1]$.  The relaxed problem is to choose $x\in[0,1]^n$ maximizing
$$\textstyle G(x) = \sum_{i} x_i b_i + \big(\sum_i x_i \alpha_i\big) \log \sum_{j} x_j \alpha_j.$$
The partial derivative of $G(x)$ with respect to $x_i$ is
$$\textstyle b_i + \alpha_i\, \lambda(x),$$
where $\lambda(x) = 1 + \log\sum_j x_j \alpha_j$.
So at any optimal $x$, you have
$$x_i = \begin{cases}
0 & \text{if}~ b_i/\alpha_i < -\lambda(x) \\
1 & \text{if}~ b_i/\alpha_i > -\lambda(x) \\
? & \text{if}~ b_i/\alpha_i = -\lambda(x).
\end{cases}
$$

WLOG, the ratios $b_i/\alpha_i$ are distinct for each $i$ (otherwise an insignificant perturbation of the $b_i$'s makes them so).  So only a single $x_i$ is undetermined by the above condition.  Since $G(x)$ is convex, one of the two neighboring solutions $x'$ (obtained by changing that $x_i$ to zero or one) has $G(x') \ge G(x)$.
Hence, defining $S_j = \{i : b_i/\alpha_i \le b_j/\alpha_j\}$ and $S_0=\emptyset$, the optimal set is $S_j$ for some $j\in\{0,\ldots,n\}$.

So, here is the algorithm.  Assume that $\alpha_i > 0$ for each $i$, and (by sorting first in $O(n\log n)$ time), that
$b_1/\alpha_1 > b_2/\alpha_2 > \cdots > b_n/\alpha_n$.
Enumerate all sets $S_j$ (and compute $G(S_j)$ for each) in $O(n)$ time, then take the best.


Re-packing of integers into fixed-size bins

We can show there's an upper bound based only on B.

Fix B, then i and j. Let the tuple $(x_{1}, \dots, x_{k}) \in \mathbb{N}_{\geq 0}^{k}$ denote the packing where we have $x_{t}$ bins of type $t$, where the type of a bin is just the numbers that are packed in it. We have the trivial upper bound $k \leq 2^{B-1}$.

Let $f(x_{1}, \dots, x_{k}) : \mathbb{N}_{\geq 0}^{k} \mapsto \mathbb{N}_{\geq 0} \cup \infty$ be a function mapping any packing into the minimum number of bins we have to touch, with $f = \infty$ if there exists no repacking. Clearly $f(y_{1}, \dots, y_{k}) \geq f(x_{1}, \dots, x_{k})$ when $y_{t} \leq x_{t}$ for all $t$, since any repacking we can do with $Y$ we can also do with $X$.

Now define $S = \{(x_{1}, \dots, x_{k}) \in \mathbb{N}_{\geq 0}^{k} \mid f(x_{1}, \dots, x_{k}) < \infty\}$. This is a set of $k$-tuples of nonnegative integers, therefore by Dickson's lemma it has only finitely many minimal elements, where an element $X = (x_{1}, \dots, x_{k}) \in S$ is minimal if there exists no other element $Y = (y_{1}, \dots, y_{k}) \in S$ such that $y_{t} \leq x_{t}$ for all $t$. Let $H_{i, j}$ be the maximum value of $f$ over the minimal elements. As the maximum of a finite number of finite elements, it is finite.

Now for any $X = (x_{1}, \dots, x_{k}) \in S$ there exists minimal $Y = (y_{1}, \dots, y_{k}) \in S$ such that $y_{t} \leq x_{t}$ for all $t$, but then $f(x_{1}, \dots, x_{k}) \leq f(y_{1}, \dots, y_{k}) \leq H_{i, j}$. Therefore if $f$ is finite it is at most $H_{i, j}$.

Therefore $\max_{i, j} H_{i, j}$ is an upper bound on the number of bins we need to touch, and it depends only on $B$. As the maximum of a finite number of finite elements, it is finite.


What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?

The pathwidth of $P^3_k$ can be determined as a corollary to some known results.
FitzGerald [2] showed that the bandwidth of $P^3_k$ is $\lfloor \frac{3}{4} k^{2} + \frac{1}{2} k \rfloor$.
Harper [3] showed a condition such that if a graph satisfies the condition, then its pathwidth and bandwidth are the same.
Moghadam [4,5] and Bollobás and Leader [1] independently showed that any multi-dimensional grid satisfies Harper's condition.
These results imply that the pathwidth of $P^3_k$ is also $\lfloor \frac{3}{4} k^{2} + \frac{1}{2}k \rfloor$.

In our paper mentioned by Hsien-Chih, we generalized FitzGerald's result as Yoshio explained.
I believe the treewidth of $P^3_k$ is not known.

FYI: I've just submitted an English version of our paper to arXiv.

B. Bollobás and I. Leader, Compressions and isoperimetric inequalities, J. Combin. Theory Ser. A 56 (1991) 47-62.
C.H. FitzGerald, Optimal indexing of the vertices of graphs, Math. Comp. 28 (1974), 825-831.
L.H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory 1 (1966) 385-393.
H.S. Moghadam, Compression operators and a solution to the bandwidth problem of the product of $n$ paths, Ph.D. thesis, University of California, Riverside (1983).
H.S. Moghadam, Bandwidth of the product of $n$ paths, Congr. Numer. 173 (2005) 3-15.


If the set of factors of an infinite word $\xi$ is regular, is this property stable under "shift's" of $\xi$?

Let $A = \{0,1\}$ be a binary alphabet and let $L = A^* -\{0,1\}^*00\{0,1\}^* = (01,1)^*(\varepsilon + 0)$. I denote by $F(w)$ the set of factors of a word $w$ and by $P(w)$ the set of its prefixes.

Let $w$ be an infinite word such that $F(1w) = L$ and $P(1w)$ is nonregular. Then $F(001w) = L \cup 00P(1w)$. Since $L$ is regular and do not intersect $00P(1w)$, $F(001w)$ is not regular. You can use Yuval's approach to give an explicit construction: take an enumeration $u_0, u_1, ...$ of $L$ and consider a word $1w = 1u_01^2u_1 \dotsm 1^nu_n \dotsm$.


Which results in complexity theory make essential use of uniformity?

I have asked many experts essentially this question, and the answer I always get is: none.  Diagonalization proofs obviously use uniformity, and these are at the heart of the time and space hierarchy theorems, as well as Fortnow-Williams type of time-space lower bounds.  As far as I know, all the other lower bounds we know of, both for complexity class separations and for data structures, seem to be non-uniform.  It would be great to hear that I'm wrong though :).


Let me give a side answer to your question. Consider the variant where you only care about edge-minimal spanning trees: for 2 terminals $s$ and $t$, the problem is equivalent to counting simple $s,t$-paths, which is $\# P$-complete; also, the parameterized version where you ask for paths of length $k$ is $\# W[1]$-hard. If you care about arbitrary $T$-steiner trees (i.e. not necessarily minimal), I expect that it is also $\# P$-hard though I'm not aware of any reference.
These hardness results suggest that it's unlikely to find some "nice formula" for the number of $T$-steiner trees.

The references are: "The complexity of enumeration and reliability problems" by L. G. Valiant, and "The parameterized complexity of counting problems" by J. Flum and M. Grohe.


Squash type vs Propositional truncation type

Squash types correspond to judgmental truncation, not propositional truncation.  In a type theory without a type for judgmental equality, there's non much of a way to make use of an inhabitant of a squash type; there's no way to write an eliminator into any type except another squash type.  Relatedly, having squash types, as presented in the book you linked, makes typechecking undecidable; having propositional truncation types does not result in this drawback.

Why do squash types result in undecidable typechecking?  Quoting the book you linked:

  The first approach to representing the proposition is to consider the ‘squash’
  type, defined in [C+86a] to be

  $\|A\| ≡_{df} \{ t : \top\ \mid\ A \}$

  which will be inhabited by the object $Triv$ if and only if there is some proof
  object $a : A$.

Now let $A$ be your favorite undecidable problem, and ask your typechecker to decide if $Triv$ has type $\|A\|$.  By construction, it can't decide your problem, and thus can't typecheck $Triv : \|A\|$.

Note that this problem is specific to squash types with canonically named inhabitants.  Agda has a form of judgmental truncation, which goes by the name "irrelevant arguments" or "irrelevant fields", without canonically named inhabitants.  Agda maintains decidable typechecking, though I think it doesn't manage to throw away the proofs, and has to carry them around (perhaps only for technical implementation reasons).  (This would be something to ask about on the Agda mailing list.)  These suffer the drawback, mentioned above, of not being able to eliminate into any non-irrelevant types.


As pointed out by many others, much has already been said on many of these questions by Mulmuley, Regan, and others. I will offer here just a brief summary of what I think are some key points that haven't yet been mentioned in the comments.

As to why GCT is considered plausibly capable of showing $P \neq NP$ many answers have already been given elsewhere and in the comments above, though I think no one has yet mentioned that it appears to avoid the known barriers (relativization, algebrization, natural proofs). As to its value - I think even if it takes us 100 years, we will learn something new about complexity along the way by studying it from this angle.

Some progress is being made on understanding the algebraic varieties, the representations, and the algorithmic questions that arise in GCT. The principal researchers I know of who have done work on this are (in no particular order): P. Burgisser, C. Ikenmeyer, M. Christandl, J. M. Landsberg, K. V. Subrahmanyan, J. Blasiak, L. Manivel, N. Ressayre, J. Weyman, V. Popov, N. Kayal, S. Kumar, and of course K. Mulmuley and M. Sohoni.
More concretely, Burgisser and Ikenmeyer just presented (STOC 2011) some modest lower bounds on matrix multiplication using the GCT approach ($n^2 + 2$, compared to the currently best known $\frac{3}{2}n^2 +O(n)$). Although these lower bounds are not new bounds, they at least give some proof-of-concept, in that the representation-theoretic objects hypothesized to exist in GCT do exist for these modest lower bounds on this model problem.
N. Kayal has a couple papers on the algorithmic question of testing when one polynomial is in the orbit of another or is a projection of another. He shows that in general these problems are NP-hard but that for special functions like permanent, determinant, and elementary symmetric polynomials, these problems are decidable in P. This is a step towards some of Mulmuley's conjectures (that certain harder problems - deciding orbit closure - are in P for special functions such as determinant).

I don't have much more specific to say on this than the answer to 2.
As far as I know there has not been fundamental criticism, in the sense that I have not seen any criticism which really discredits the program in any way. There has certainly been discussion about why such techniques should be necessary, the value of the program given the long time horizons expected, etc., but I would characterize these more as healthy discussion than fundamental criticism.


Obviously any decision problem that can be reduced to factoring can be solved with a factoring oracle. But since we're given the ability to make multiple queries, I tried to think of a non-trivial problem for which one would want to make multiple queries.

The problem of computing the Euler totient function seems like such a problem.  I don't know  how to solve the decision version of this problem by a Karp-reduction to the decision version of factoring.  But with Turing reductions, it's easy to reduce this to factoring.


Bibliography needed: How many "good" solutions for Knapsack?

Shooting from the hip here, but I think this might, in fact, be a simple problem to solve in pseudopolynomial time, using dynamic programming (DP). Not sure if that's acceptable, or if you need a polynomial-time algorithm?

  A brief detour: You assume that the optimal value is known, and that $\varepsilon>0$, and I don't know how hard the given counting problem is. If you made no such assumptions, however, you're basically left with (an obvious reduction from) the decision-version of 0-1-knapsack, which is, of course, NP-complete. The question, of course, is whether the additional assumptions are enough to “rescue” the problem from hardness.

My intuition comes from the fact that DP formulations in general are equivalent to path problems (such as shortest/longest path, or the number of paths) in DAGs. I think counting the number of paths from some node $s$ (representing the zero-capacity knapsack and the empty subset of items) that are “long enough,” given some threshold (in your case, $(1-\varepsilon)v$) is quite straightforward as well.

You can formulate it recursively, as follows. Let $G=(V,E)$ be your DAG, let $w(u,v)$ be the edge weight function, let $\ell_\delta(v)$ be the number of $s$-paths ending at node $v$ with a length of at least $\delta$. You then have:

\begin{equation}
\ell_\delta(v) =
\begin{cases}
0 & \text{if $v=s \land \delta > 0\,$;} \\
1 & \text{if $v=s \land \delta \leq 0\,$;} \\
\sum_{u:(u,v)\in E} \ell_{\delta-w(u,v)}(u)& \text{otherwise.}
\end{cases}
\end{equation}

I'm implicitly assuming that all nodes lie on a path from $s$, as they will in your case, but for nodes beside $s$ that don't have predecessors, the sum will simply be an empty sum, which can be assumed to be zero. To implement this, just memoize it or turn it “upside down” and fill the appropriate array.

In the knapsack case, you'd only have two predecessors $u$ to sum over, of course (i.e., the ones representing the solutions with and without the object under consideration in node $v$). The solution will simply be $\ell_{(1-\varepsilon)v}(t)$, where $t$ is the final “corner” of your matrix, with full capacity and the full set of items.


Why is plus-comm a b $:\equiv$ refl (plus a b) not a proof of the commutativity of addition?

But it does follow. The types
$$A = \prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ n\ m)$$
and
$$B = \prod_{(n,m:\textrm{Nat})}(\textrm{plus}\ n\ m) = (\textrm{plus}\ m\ n)$$
are both contractible. Indeed, they are both inhabited and because $\mathrm{Nat}$ is a set, its identity type is a proposition, hence so are $A$ and $B$, as they are products of propoitions. An inhabited proposition is contractible.
Any two contractible types are equivalent, $A \simeq B$, thus by univalence also propositionally equal (as elements of a universe), $A = B$. However, $A$ and $B$ are not judgementally equal.
Consequently, the term $t = \lambda n, m \,.\, \mathrm{refl} (\mathrm{plus}\,n\,m)$ has type $A$ but it does not have type $B$. We can however transport $t$ along an equivalence $e : A \to B$ to obtain a term $e\,t : B$.


A Combinatorial Problem on Extremal Set Theory

Did you want some condition to make $\mathcal{F}$ a large collection? Because the current definition allows for the following, presumably trivial, case. Consider $\mathcal{F}=\{S_1,S_2\}$, where $S_1=[n/2]$ and $S_2=[n]\setminus S_1$. Then we can take $a=n/2$, $b=n$, $c=n/2$.


Complexity involving connected components of 0/1 matrix

So I give a sketch why the problem is NP-complete.
It is very sketchy, which you can take as a sign of trust that you're a smart guy, and not at all a sign of laziness on my part.
We will reduce a variant of PLANAR-SAT, where we also require that the edges connecting the variable to its negated and unnegated occurrences form adjacent intervals in the rotation of the vertex of the variable; e.g., if each variable occurs at most once negated.

The matrix will have a small top-left corner that will contain the important information, and many additional rows and columns to impose a structure on this part.
In particular, I claim that with properly chosen additional rows and columns, we can achieve that instead of arbitrary permutations, we can restrict the problem to permutations that do not change the rows and can swap only given pairs of adjacent columns, or otherwise the number of components would be larger than $k$.

If we can achieve this, then in the top-left corner we "draw" the graph of our PLANAR-SAT, such that at the heart of each vertex there is a pair of swappable columns.
Every other row is constant on these two columns, so only the neighborhood of the vertex is effected.
And at this vertex the negated clause-edges come from one side, the unnegated from the other, the swappable column decides which ones are connected to some main component.
Therefore, the CNF is satisfiable if and only if all clauses can be connected to the main component.

Since I didn't provide any details about the additional part, it is not clear how $k$ depends on $n$.
Can $k$ be kept constant?


I will try to answer this old question of yours, although I am not sure my answer is conclusive but it should point you in the right direction.

First let us discuss linear clique-width.
If a graph has linear clique-width $k$, and one add $1$ vertex to the graph, that vertex can always be placed first in the ordering with a unique color.
Hence linear clique-width only increases by at most 1 when you add a vertex.

Gurski and Wanke showed in "On the relationship between NLC-width and linear NLC-width" that cographs have unbounded linear clique-width.

Since cographs have unbounded linear clique-width but bounded clique-width any good clique decomposition must have a tree structure.
We must show that we can force arbitrarily many deep branches.
Now we do as we do for trees, construct a tree with at 2^k leaves add k vertices and each leaf is connected to a unique subset of new vertices.


Using the de Bruijn sequence to find the $\lceil\log_2 v \rceil$ of an integer $v$

First note that this algorithm only computes $\lceil \log_2 v \rceil$, and as the code is written, it works only for $v$ that fit in a $32$-bit word.

The sequence of shifts and or-s that appears first has the function of propagating the leading 1-bit of $v$ all the way down to the least significant bit. Numerically, this gives you $2^{\lceil \log_2 v \rceil} - 1$.

The interesting part is the de Bruijn trick, which comes from this paper of Leiserson, Prokop and Randall (apparently MIT professors spend time doing bit hacks :) ). What you need to know about de Bruijn sequences is that they represent all possible sequences of a given length in a way that's as compressed as possible. Precisely, a de Brujn sequence over the alphabet $\{0, 1\}$ is a binary string $s$ of length $2^k$ such that each length $k$ binary string appears exactly once as a contiguous substring (wrap around is allowed). The reason this is useful is that if you have a number $X$ whose bit representation is a de Bruijn sequence (padded with $k$ zeros), then the top $k$ bits of $2^iX$ uniquely identify $i$ (as long as $i <k$).


How much independence is required for separate chaining?

Apparently not. "Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence", by  Mathias Bæk Tejs Knudsen and Morten Stöckel shows "a $k$-independent family of functions that imply [heaviest loaded bin] size $\Omega(n^{1/k})$".


Is #PE (#P Easy) closed under decrement?

If $\text{#PE}$ is closed under decrement then $\text P=\text{NP}$: consider $\text{#SAT}+1$. Conversely if $\text P=\text{NP}$ then $\text{#PE}=\text{#P}$ is closed under decrement because we can always find an accepting path if one exists then ignore it.

I don't know whether $f\in\text{#PE}$ always implies $f_{-1}\in\text{#P}$. Your $M$ might not provide an accepting path for us to ignore.


In the definition of class IP(k), the interaction always ends with prover’s message.  Otherwise there is no use for the last message (why?).

The situation is different for the definitions of public-coin interactive proof systems (also known as Arthur-Merlin proof systems), where sending a message from the verifier to the prover is the only way for the verifier to generate a random bit string.  In Babai [Bab85], AM(k) is defined by the verifier (or Arthur) sending the first message and MA(k) is defined by the prover (or Merlin) sending the first message.

[Bab85] László Babai.  Trading group theory for randomness.  In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), pp. 421–429, May 1985.  DOI: 10.1145/22145.22192.


This problem appears to be very similar to SEQUENCING TO MINIMIZE MAXIMUM CUMULATIVE COST, problem [SS7] in Garey & Johnson. To wit:

  INSTANCE: Set $T$ of tasks, partial order $\prec$ on $T$, a "cost" $c(t) \in Z$ for each $t \in T$ (if $c(t) < 0$, it can be viewed as a "profit"), and a constant $K \in Z$.

  QUESTION: Is there a one-processor schedule $\sigma$ for $T$ that obeys the precedence constraints and which has the property that, for every task $t \in T$, the sum of the costs for all tasks $t'$ with $\sigma(t') \leq \sigma(t)$ is at most $K$?

I am uncertain whether the problem remains NP-complete when $K$ is fixed to 0. G&J mention that the problem remains NP-complete if $c(t) \in \{-1,0,1\}$ for all $t \in T$.


Formalization of simulation for Turing machines

First, let's clearly settle what it means for a Turing Machine to compute a function.
Any specification of a deterministic TM $M$ implicitly defines, for each word $w \in \Sigma^*$, a (possibly infinite) sequence of configurations of $M$ when run on $w$ (the machine is said to halt if this sequence is finite). A configuration consists of the state of the TM, the position of its head, and the contents of its tape. This, in turn, defines a function
$$f_M: \Sigma^* \to \Sigma^* \uplus \{\bot\}$$
that the machine computes: for a word $w \in \Sigma^*$, if the sequence of configurations of $M$ when run on $w$ is finite, the function value $f_M(w)$ is the word $v$ that is on the tape in the last configuration of that sequence, and if the sequence is infinite, we set $f_M(w) = \bot$ (indicating that $M$ does not halt on input $w$).
Next, we need to recognize that TMs themselves can be encoded as words over $\Sigma^*$. Let's assume for simplicity that every word $w$ describes a TM $M_w$. Also, define for each TM $M$ the set of words that encode $M$, i.e.
$$ \operatorname{enc}(M) = \{w \in \Sigma^* \mid M_w = M\}.$$
Further, pairs of words $(w, v) \in \Sigma^* \times \Sigma^*$ can be canonically encoded as a single word $u \in \Sigma^*$ - denote this word by $\langle w, v \rangle$.
And now we're ready to rigorously define what we mean when we say that TMs simulate other TMs. We say that a TM $M$ simulates another TM $M'$, if for all $w \in \operatorname{enc}(M')$ and all words $v \in \Sigma^*$,
$$f_M(\langle w, v\rangle) = f_{M'}(v).$$
That is, given any description of $M'$, and an input $v$, $M$ outputs exactly what $M'$ would output, and if $M'$ doesn't halt, then $M$ also doesn't halt.
A universal TM is a machine that simulates all other machines, in the following sense: A TM $M$ is called universal, if for every pair $(w, v) \in \Sigma^* \times \Sigma^*$,
$$f_M(\langle w, v \rangle) = f_{M_w}(v).$$
That is, given any description $w$ of a Turing machine $M_w$, and an input $v$ for that machine, $M$ outputs exactly what $M_w$ would output when run on $v$, and if $M_w$ doesn't halt, then $M$ also doesn't halt.
Edit: Restructured answer to make it more readable.


Game semantics for coinductive predicates

Vicious Circles by Barwise and Moss is a cornucopia of co-algebraic/co-inductive reasoning, and includes material on co-inductive games.

Not sure if it will help you out in your specific need, but might be the source of some inspiration in this line of reasoning.

Edit (x2):

I think you can follow a modified Ehrenfeucht-Fraïssé style approach like this: Falsifier gets to select any item from the stream/disjunction/conjunction.
Verifier then has to show that any such item must be a black cat.

(You could put ordering or number of choices restrictions on Falsifier without loss of generality for a finite set of coinductive rules.)

If you think of coinduction as just induction without a base case, it is obvious that the only (co-)induction rule you have on blackCats is cat == BlackCat, so what else could an individual cat be in that stream?  Any cat that Falsifier selects will have to conform to that rule, so Verifier wins.

Obviously this would scale to more numerous and complex coinductive rules, where the "challenge" for Verifier becomes to choose the appropriate rule for whatever item Falsifier chooses.

Colin Sterling's Bisimulation, Model Checking and Other Games, should help you out. His book Modal and Temporal Properties of Processes has similar material, though in less detail.


Rather than go through some complicated bureaucracy to close this and resuscitate the other earlier-asked variants, it's probably straightforward just to answer this now; I think it's long enough after the previous questions that we don't so much need to worry about it being homework (and the way it's phrased now certainly seems much less suspicious).

The paper I was referring to in the discussion on the earlier problems is:

"Exponentially small bounds on the expected optimum of the partition and subset sum problems", G. S. Lueker, Random Structures and Algorithms, 1998.

But now that I think about it again, I realize that the problem Lueker solves is actually a bit different from what you're asking: he repeatedly replaces a pair of points by their difference, rather than their average. The application for this replacement process is in a variant of the subset sum problem, in which one is given n real numbers and one is trying to find a subset minimizing the difference between the sum of the weights in the chosen subset and the sum of the weights not in the subset. Replacing a pair by their difference is equivalent to imposing a constraint that exactly one of the two items is in the subset: each of the two choices for what to do with the difference in the replaced problem has exactly the same effect as each of the two choices for which item to include in the original problem.

This is also somewhat related to some work of Valiant, "Short monotone formulae for the majority function", J. Algorithms, 5, 1984, 363–366: by repeatedly replacing triples of numbers by their median, you can with high probability find a point near the median of the numbers. See also my paper with Clarkson et al, "Approximating Center Points with Iterated Radon Points", which generalizes this result to higher dimensions.


States and Probability distributions that the 5-qubits IBM computer can produce

I just ran the first state you suggest (i.e. the GHZ state with negative phase in the Hadamard basis). Basically what I did was to write a circuit which creates that state, apply one of 5 stabilizer generators (XIXII,IXXII,IIXXI,IIXIX or -ZZZZZ) and then inverted the creation process. The circuit is shown below for the -ZZZZZ stabilizer.

There seems to be problem with the calibration or something, since I am seeing a bit flip occurring on the first qubit with roughly probability 2/3 that should not happen. The expected result should be 00000 in all cases, however 10000 seems to be twice as likely in almost all cases (prob ~0.1 vs ~0.2 over 1024 runs for each stabilizer generator).

Below are the probabilities of obtaining 00000 for each stabilizer generator over 1024 runs each:
    XIXII:0.10840
    IXXII:0.15625
    IIXXI:0.11621
    IIXIX:0.10645
    ZZZZZ:0.09375

And the probabilities of obtaining 10000 for each stabilizer generator:
    XIXII:0.21777
    IXXII:0.21875
    IIXXI:0.17871
    IIXIX:0.14648
    ZZZZZ:0.19726


Given $n$, let $M = 2n\log n$ (here $2$ is any constant larger than $1$). Put all numbers from $2$ to $M$ in a linked list. Now implement Eratosthenes sieve, by repeatedly running the following algorithm, until you get $n$ primes. Look for the first unmarked number $p$ (they all start unmarked; start looking at the previous prime), take it as a prime, and mark every integer in hops of length $p$. The running time is roughly $M + \sum_p M/p = \Theta(M\log\log M) = \Theta(n \log n \log\log n)$, where $p$ goes over the first $n$ primes. Since the $k$th prime $p_k$ is about $k\log k$, heuristically indeed
$$ \sum_{k=1}^n \frac{1}{p_k} \approx \sum_{k=2}^n \frac{1}{k\log k} \approx \int_2^n \frac{dk}{k\log k} \approx \log\log n.$$
This approximation can be proved rigorously, this is one of the results known as Mertens' theorem.

See Emil's comment below or the Wikipedia article for improvements on this algorithm.

Edit: Before Emil's comment, I suggested implementing the algorithm using a linked list, but that's a bad suggestion since you can't "hop" in a linked list, causing the runtime to be $\Omega(n^2)$.


Kolmogorov Complexity vs Running Time (Edited)

It really depends on your computation model. Suppose for example a model which allows random "seek" instructions, say the RAM machine. The algorithm $A$ can just include a description of the string, and on input $i$ you output the $i$th bit of the string. Conceivably, a universal Turing machine (running on a RAM machine) can execute this algorithm in time $O(\log n)$, especially if we engineer it to specifically handle algorithms of this type.

Any proof that a universal Turing machine (running on an actual Turing machine) requires time $\Theta(n)$ thus needs to appeal specifically to the Turing machine model. In particular, you claim that the universal Turing machine $U$ must read all of $A$ and $i$. But in fact, for any given string $s$ we can construct a universal Turing machine whose programs come in two types: (1) output $s$; (2) everything else. Such a Turing machine can "simulate" $A$ in time $O(\log n)$. The correct claim you should try to prove thus needs to accommodate finitely many exceptions, unless you are fixing a universal Turing machine. (On second thought, it's not clear whether you can pull it off while keeping the string random. Indeed, it seems you won't be able to recognize the program $A$ without reading all of it, which would take time $n$ if the string is Kolmogorov random.)

Even if we fix a universal Turing machine, it's not clear that $A$ necessarily takes time $O(n)$. We can arrange for $A$ to first output $n!$ many zeroes, then erase them and proceed as in your algorithm. Perhaps you meant $A$ to be the one with the lowest time complexity? (say the one minimizing the maximal execution time over all indices)


Analytic solutions in semidefinite programming (SDP)

There are many examples in quantum information and computation where quantities of interest are expressible as optimal values of semidefinite programs. Here are a few beyond those mentioned in the question:

The optimal probability to correctly distinguish states chosen from a known ensemble is expressible as an SDP. (See arXiv:quant-ph/0205178 .)
The general adversary bound, which characterizes the number of queries needed to compute a function by a quantum algorithm in the query model, is represented by a semidefinite program for each possible input length of the problem being considered. (See arXiv:1011.3020 for further details and references.)
There exists a hierarchy of semidefinite programs that characterizes the set of separable density operators. (See arXiv:quant-ph/0308032 .)
Quantum interactive proof systems and the study of quantum coin-flipping protocols are closely tied to semidefinite programming. Suppose you have an interaction between two parties, say Alice and Bob, who exchange quantum information. If you fix one of the two parties, say Alice, and you ask what the optimal probability is for Bob to force Alice to output a particular result, then you can phrase this optimal probability as a semidefinite program. (There are many references here, including http://dl.acm.org/citation.cfm?id=335387, arXiv:quant-ph/0403193, arXiv:0907.4737, arXiv:quant-ph/0611234, arXiv:1003.0038, arXiv:0711.4114, arXiv:1104.1140 .)
The optimal probability for cooperating players Alice and Bob to win an XOR game can, through the use of a well-known theorem of Tsirelson, be phrased as a semidefinite program. This leads to a perfect parallel repetition theorem for quantum provers in XOR proof systems. (See arXiv:quant-ph/0608146 .)
The completely bounded trace norm (or diamond norm) of a mapping from matrices to matrices can be expressed as an SDP. This norm is useful for defining a physically motivated measure of distance between quantum channels.
(See arXiv:0901.4709 for the SDP.)

These SDPs do not all necessarily have analytic solutions, but they have the same flavor as the examples mentioned in the original question in that they represent interesting and arguably fundamental quantities in quantum information and computation. There are other examples as well -- these just happen to be ones I'm familiar with.

The original question asks if there is a general theory behind the existence of analytic solutions to SDPs. I am not aware of such a theory, and cannot see much hope for one to exist. If you write down a random SDP, there will probably not be a nice closed form for the solution.

The reality, at least as I view it, is that things work in the other direction. The SDPs for the fidelity and trace norm mentioned in the original question were specifically designed to represent those quantities: it is not an accident that the optimal solutions were given by such nice and important functions. If you have another quantity in mind, you might be able to express it as an SDP in a simple way by using some thought to come up with the SDP... but going in the other direction, from an SDP to an analytic solution, seems certain to be hard in general.


Are single hidden-layered neural networks at least as good as multi hidden-layered neural networks?

Short answer: Not necessarily. Likely nothing fishy is going on.

Longer answer:
The Universal Approximation Theorem (UAT) says nothing about an individual network's capacity to approximate a function. Moreover it says nothing about trainability or generalization.

The UAT roughly says that for any $\epsilon>0$ and any continuous real-valued function $F$ on compact domain $\Omega$ there exists a feed-forward network $f$ with a single hidden layer (with appropriate weights) such that $| F(x)-f(x)|<\epsilon$ for all $x\in\Omega$. Inductively using the shallow UAT, one can prove a deep UAT. So in theory depth offers no more expressiveness.

Note that this merely guarantees the existence of some appropriately tuned neural network, and not that any particular network can be trained up to that desired accuracy.

On the other hand, deep neural networks have been seen to be often much better in many applications. This is often attributed to their ability to learn hierarchical representations of the data. The UAT says nothing about generalization, which is the bar by which success is usually measured in practice. Here it is argued that deep networks can approximate compositional functions with less parameters than shallow counterparts.

But on the other-other hand, it was noticed that sometimes adding more depth can hurt when training a network. But why should it? One could in principle just set the new layer to be the identity. Apparently the later layers were actually trying to approximate the identity but doing it very poorly. So why not learn how different your layer is from the identity? This observation led to Residual Learning which in turn led to some really, really deep networks.


Has there been a study of circuits operating on arrays?

Not really an answer, but would've been too long a comment. The result of Ben-Or and Cleve that arithmetic formulas can be simulated by branching programs of width 3, works over arbitrary non-commutative rings (in particular over the matrix ring $M_n(F)$). A nice consequence of this is that $\# NC^1$ circuits over $M_n(\mathbb{Z})$ captures ${\text{GapL}}$ over $\mathbb{Z}$ (for which the Determinant is a hard function). See for example, the paper on catalytic space by Buhrman et al. for an interesting generalization of the work of Ben-Or and Cleve. There is a result of Capelli, Durand and Mengel which gives a characterization of the arithmetic complexity class VP as equivalent to formulas whose nodes compute tensor contractions (note that here you even lose associativity).


Can Quarter-Subset Membership be decided space-efficiently?

I assume from the discussion that you are not actually interested in work space as claimed, but in total space including the size of the input. (Otherwise the trivial $n$-bit encoding scheme can be decoded in logarithmic space.)

Let $k$ be a sufficiently large constant, and consider the following encoding scheme for $X\subseteq\{0,\dots,n-1\}$. Split $\{0,\dots,n-1\}$ into $k$ blocks $B_u$, $u<k$, of size $n/k$ each, and put $X_u=X\cap B_u$. The encoding of $X$ consists of the sequence of the following numbers (written in binary) for each $u<k$:

the size $s_u=|X_u|$;
the number corresponding to $X_u$ in the combinatorial number system for $s_u$-size subsets.

As for the size of the encoding, assume $|X|\le n/4$. The numbers $s_u$ take $O(k\log(n/k))$ bits, which will be negligible. We have $s_u\le n/(3k)$ for at least $k/4$ of the $u$'s, in which case the encoding of $X_u$ takes about $H(1/3)\tfrac nk\approx0{.}92n/k$ bits; the remaining $X_u$ take at most $n/k$ bits each. The total is at most $0{.}98n$ bits.

Decoding amounts to deciding which block $i$ goes into, and then figuring out $X_u$; the latter be done easily in space $n/k+O(\log n)$, and one can reuse the space occupied by encodings of the remaining blocks (as long as the total space is at least $2n/k$, which is OK for $k$ large enough).

A better analysis shows that this scheme achieves space essentially $H(1/4)n\approx0{.}812n$: let $p_u=s_u/(n/k)$. Since $|X|/n\le1/4$, the average of $p_u$ over $u<k$ is at most $1/4$. The encoding of $X_u$ takes about $H(p_u)n/k$ bits. Now, the entropy function is concave, hence the average of $H(p_u)$ over $u<k$ is at most $H(1/4)$, and the total space is $H(1/4)n+O(\log n)$. This is optimal up to the $O(\log n)$.

There is of course nothing special about $1/4$. The same argument shows that for any constant $0<c<1/2$, there is an encoding scheme for $\le cn$-size subsets of $\{0,\dots,n-1\}$ that takes $H(c)n+O(\log n)$ bits, and can be decoded in-place. To some extent, it can even be used for $\le s(n)$-size subsets where $s(n)\ll n$, by taking a non-constant number of blocks ($k\ge 2/H(s(n)/n)$ or so), but then the $O(k\log(n/k))$ overhead gets more pronounced, and overtakes the main term when $s(n)$ drops below roughly $\sqrt n$.


What is a practical non-von Neumann architecture?

When I say "von Neumann architecture", I mean some hardware that is limited by the "von Neumann bottleneck" -- i.e., it has all data is funneled through some narrow data bus.

The non-von Neumann programming languages I bump into most often are VHDL and Verilog.
In VHDL and Verilog, by default, everything happens at the same time.
The programmer has to go to extra effort to make a series of events occur in sequential order.
That is very different from most other programming languages that imply a "instruction pointer" that, by default, executes at most one line of code at any one instant, and the programmer has to go to extra effort to get multiple things happening at the same time.

Some people would say that's a more natural default.
Lots of beginning programming students expect a "while( x > 0 ){...}" loop to exit the instant that x becomes equal to zero, and they are surprised to learn that the computer doesn't continously evaluate that condition.

Most people writing VHDL and Verilog code compile their programs onto FPGAs,
creating little blocks of activity that all run at full speed all the time.
Often such people set up a "pipeline" that reads data from the input pins, processes it through a series of blocks, the output pins of one block directly wired to the input pins of the next block, and the final block sends the result out the output pins.
It's reminiscent of the Unix pipeline, except that a new piece of data goes in and a new piece of data comes out on every clock cycle.

The input pins, the intermediate stages, and the output pins are all independent of each other -- you don't have to re-use a single data bus multiplexed between the various pieces of data.

You might also be interested in: Are there other computer architectures apart fom the von neumann /turing architectures?


Lower bounds for quantum circuits using the geodesic framework

Not exactly what you are looking for, I know, but geodesics have been used to prove optimal state transfer rates in Ising spin chains (see arXiv:0705.0378). I'm not sure how related this is to Nielsen's approach, as I haven't read that particular paper, but I remember thinking this was quite a neat result when it first came out. Basically this is the minimum time to transfer a quantum state from one end of a linear array of qubits to the other. It is a very simple problem, but in the above paper they show that the transfer can be achieved significantly faster than was previously believed (although of course there is still a linear scaling, with the speed-up in the constant).


What languages have been successfully cryptographically trapdoored?

It is important to distinguish between trapdoor functions and public-key encryption. While trapdoor functions do yield public-key encryption schemes, some of the candidates you mentioned are only known to imply public-key encryption and do not necessarily give you trapdoor functions. In fact, Gertner, Malkin and Reingold show that there is no black-box construction of a trapdoor function from a "trapdoor predicate" (which can be thought of as a one-bit public-key encryption scheme).

Classical examples of trapdoor functions are the RSA and Rabin functions. A classical example of a trapdoor predicate is deciding Quadratic Residuosity modulo a composite, due to Goldwasser and Micali. The discrete-log and lattice based constructions that you mention yield public-key encryption directly, without going through trapdoor functions.

Below is a (non comprehensive) list of constructions of public-key encryption schemes, most of which are not known to go through trapdoor functions.

El Gamal public-key cryptosystem (including elliptic curve variants). Security is based on the Decisional Diffie Hellman assumption. Doesn't go throuhg trapdoor functions (but see the Peikert-Waters item below for a trapdoor function whose security is based on the semantic security of El Gamal).

[Taher El Gamal: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. CRYPTO 1984: 10-18]
Ajtai-Dwork, Regev. Security is based on unique SVP in lattices. Not known to imply trapdoor functions.

[Miklós Ajtai, Cynthia Dwork: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. STOC 1997: 284-293]

[Oded Regev: New lattice based cryptographic constructions. STOC 2003: 407-416]
Regev, Peikert. Security is based on hardness of learning with errors (this includes a reduction from SVP). Not known to imply trapdoor functions.

[Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. STOC 2005: 84-93]

[Chris Peikert: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. STOC 2009: 333-342]
Peikert, Waters. Security is based on decisional Diffie Hellman and on lattice problems. Known to imply trapdoor functions (through lossy trapdoor functions).

[Chris Peikert, Brent Waters: Lossy trapdoor functions and their applications. STOC 2008: 187-196]
Lyubashevsky, Palacio, Segev. Security is based on Subset-Sum. Not known to imply trapdoor functions.

[Vadim Lyubashevsky, Adriana Palacio, Gil Segev: Public-Key Cryptographic Primitives Provably as Secure as Subset Sum. TCC 2010: 382-400]
Stehlé, Steinfeld, Tanaka, Xagawa, and Lyubashevsky, Peikert, Regev. Security is based on hardness of ring LWE. The advantage of these over previous proposals is their smaller key size. Not known to imply trapdoor functions.

[Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa: Efficient Public Key Encryption Based on Ideal Lattices. ASIACRYPT 2009: 617-635]

[Vadim Lyubashevsky, Chris Peikert, Oded Regev: On Ideal Lattices and Learning with Errors over Rings. EUROCRYPT 2010: 1-23]


Complexity class when reducing decision problem to function problem

In the case of PSPACE and FPSPACE, the answer is yes (since DEC reduces to FUN and DEC is PSPACE-hard, FUN is FPSPACE-hard). The reason is that in PSPACE search always reduces to decision: say you want to compute a function $f(x)$. If the problem of deciding whether the $i$-th bit of $f(x)$ is 1, given $i$ and $x$, is in PSPACE, then $f$ itself is in FPSPACE. Now, if $f$ is in FPSPACE, we can use your function FUN to compute it by using FUN to compute the decision problem "is the $i$-th bit of $f(x)$ 1?" for each $i$. One way to say this is that PSPACE is FPSPACE-hard.

However, there are complexity classes where the relationship between the function and decision versions is not so clear. For example:

It is not known if the search version of Group Isomorphism (find an isomorphism) reduces to the decision version (is there an isomorphism?), when the groups are input as multiplication tables.
$P^{NP[\log]} = P^{NP}_{tt}$, but $FP^{NP[\log]} = FP^{NP}_{tt}$ is not known to hold and would imply $NP=RP$ and $P=UP$ (see Selman, A. A taxonomy of complexity classes of functions. JCSS 48(2):357-381, 1994.) But if $P^{NP}_{tt}$ were $FP^{NP}_{tt}$-hard, we would automatically have equality of the function classes.

(For reference: $P^{NP[\log]}$ is $P$ with an $NP$-oracle, but the $P$ machine is only allowed to make $O(\log n)$ queries to the oracle. $P^{NP}_{tt}$ is the problems that are polytime truth-table reducible to $NP$; this is equivalent to nonadaptive polytime Turing reductions, i.e. all the queries to be made are decided in advance, then all the queries are made, then some computation is done without queries to find the result.)


Lower bound for determinant and permanent

Permanent is complete for VNP under p-projections over any field not of characteristic 2. This provides a positive answer to your second question. If this reduction were linear, it would give a positive answer to your first question, but I believe that remains open.

In more detail: there is some polynomial $q(n)$ such that $det_n(X)$ is a projection of $perm_{q(n)}(Y)$, i.e. there is a certain substitution sending each variable $y_{ij}$ either to a variable $x_{k\ell}$ or a constant such that after this substitution the $q(n) \times q(n)$ permanent is computing the $n \times n$ determinant.

1) Thus Ryser's formula yields a depth 3 formula (depth does not increase under projections because the substitutions can be done on the input gates) of size $2^{O(q(n))}$ for determinant.   UPDATE: As @Ramprasad points out in the comments, this only gives something nontrivial if $q(n) = o(n \log n)$, since there is a trivial depth 2 formula of size $n \cdot n! = 2^{O(n \log n)}$ for det. I am with Ramprasad in that the best I know is the reduction through ABPs, which yields $q(n)=O(n^3)$.

2) If the $m \times m$ permanent can be computed - again, over some field of characteristic not 2 - by a circuit of size $s(m)$, then $n \times n$ determinant can be computed by a circuit of size $s(q(n))$. So a lower bound of $b(n)$ on circuit-size for $det_n$ yields a lower bound of $b(q^{-1}(n))$ on circuit-size for the permanent (that's $q$ inverse, not $1/q(n)$). The above-mentioned $q(n)=O(n^3)$ yields a $b(n^{1/3})$ perm lower bound from a $b(n)$ det lower bound.


algorithm to find a point among n points in plane to minimize the sum of distances

Since you have to compare a sum of square roots, it is not clear/unknown if this problem is in NP. Otherwise, if you assume you can compute sum of square roots and compare them, then I am unaware of an algorithm that works in faster than quadratic time. For approximation, you can just approximate the 1-median using known algorithms in linear time, and then just take the closest point  to this center. This would give you a constant approximation. A better approximation can be had by working somewhat harder.


What is the status of fuzzy logic for TCS in 2011?

I wouldn't consider fuzzy logic dead. For control systems, I don't know. However, there's been a lot of activity in fuzzy logics for proof theorists for the last several years: look for papers by Ciabattoni, Olivetti, Fermüller, Metcalfe, and Baaz for starters.

Edit: Some specific references from my BibTeX file:

D. Galmiche and Y. Sahli, Labelled Calculi for Łukasiewicz Logics, Int. Workshop on Logic, Language, Information and Computation, WoLLIC'08, Edinburgh, LNAI 5110, 2008.
M. Baaz and G. Metcalfe, Proof Theory for First Order Łukasiewicz Logic. TABLEAUX 2007.
D. Galmiche and D. Larchey-Wendling and Y. Salhi, Provability and Countermodels in Gödel-Dummett Logics, DISPROVING'07: Workshop on Disproving Non-Theorems, Non-Validity, and Non-Provability, 2007.
S. Bova and F. Montagna, Proof search in Häjek's Basic Logic, ACM Trans. Comput. Log., 2007.
D.M. Gabbay and G. Metcalfe, Fuzzy logics based on [0,1)-continuous uninorms, AML 46(5), 2007.
G. Metcalfe and F. Montagna, Substructural fuzzy logics. JSL 72(3), 2007.
R. Dyckhoff and S. Negri, Decision methods for linearly ordered {H}eyting algebras. AML 45, 2006.
G. Metcalfe and N. Olivetti and D. Gabbay, Sequent and Hypersequent calculi for Abelian and Łukasiewicz Logics. ACM Trans. Comput. Log. 6(3), 2005.
M. Baaz and A. Ciabattoni and F. Montagna, Analytic calculi for monoidal t-norm based logic, Fund. Inf. 59(4), 2004.
S. Negri and J. van Plato, Proof systems for lattice theory, Math. Struct. in Comp. Science 14(4), 2004.
A. Ciabattoni and
           C.G. Fermüller and
           G. Metcalfe, Uniform Rules and Dialogue Games for Fuzzy Logics. LPAR 2004.
A. Ciabattoni, Automated Generation of Analytic Calculi for Logics with
           Linearity. CSL 2004.
F. Montagna and L. Saccetti, Kripke-style semantics for many-valued logics, Math. Log. Q. 49(6), 2003. Correction in MLQ 50(1), 2004.
D. Larchey-Wendling, Countermodel search in Gödel-Dummett logics, IJCAR 2004, LNAI 3097, Springer, 2004.
G. Metcalfe, Proof Theory for Propositional Fuzzy Logics, PhD Thesis, Department of Computer Science, King's College, 2004.
D. Gabbay and G. Metcalfe and N. Olivetti, Hypersequents and Fuzzy Logic, Revista de la Real Academia de Ciencias 98(1), 2004.
A. Ciabattoni and G. Metcalfe, Bounded Łukasiewicz Logics. TABLEAUX 2003.
M. Baaz and
           A. Ciabattoni and
           C. G. Fermüller, ypersequent Calculi for Gödel Logics---a Survey. JLC 13(6), 2003.
M. Baaz and
           A. Ciabattoni and
           C. G. Fermüller, Sequent of Relations Calculi: A Framework for Analytic Deduction in Many-Valued Logics. Beyond Two: Theory and Applications of Multiple-Valued Logic, M. Fitting and E. Orlowska, eds., Physica-Verlag, 2003.
N. Olivetti, Tableaux for Łukasiwicz Infinite Valued Logic. Studia Logica  73(1), 2003.
G. Metcalfe and N. Olivetti and D. Gabbay, Analytic Sequent Calculi for Abelian and Łukasiewicz Logics. TABLEAUX 2002.
A. Ciabattoni and C. G. Fermüller, Hypersequents as a Uniform Framework for Urquhart's C, MTL and Related Logics.Proceedings of the 31th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2001), 2001.
F. Esteva and L. Godo, Monoidal t-norm based logic: towards a logic for
       left-continuous t-norms, Fuzzy Sets and Systems 124(3), 2001.
M. Baaz and R. Zach, Hypersequent and the Proof Theory of Intuitionistic Fuzzy
           Logic. CSL 2000.
A. Avron, A Tableau System for Gödel-Dummett Logic Based on a
           Hypersequent Calculus. TABLEAUX 2000, LNAI 1847, 2000.
A. Ciabattoni and M. Ferrari, Hypertableau and Path-Hypertableau Calculi for some families of intermediate logics. TABLEAUX 2000, LNAI 1847, 2000.
R.L.O. Cignoli and I.M.L. D'Ottaviano and D. Mundici, Algebraic Foundations of Many-Valued Reasoning, Kluwer, London, 2000.
S. Aguzzoli and A. Ciabattoni, Finiteness in Infinite-Valued Łukasiewicz Logic. J. Logic, Language and Information 9, 2000.
R. Dyckhoff, A Deterministic Terminating Sequent Calculus for Gödel-Dummett logic, IGPL 7(3), 1999.
M. Baaz and
           A. Ciabattoni and
           C. G. Ferm{\"u}ller and
           H. Veith, Proof Theory of Fuzzy Logics: Urquhart's C and Related Logics. Mathematical Foundations of Computer Science 1998, 23rd
           International Symposium, MFCS'98, Brno, Czech Republic,
           August 24-28, 1998, Proceedings, 1998.
P. Häjek, Metamathematics of Fuzzy Logics, Kluer, 1998.
R. Hähnle, Proof theory of many-valued logic--linear optimization--logic
           design: connections and interactions. Soft Comput. 1(3), 1997.

These are largely proof-theory and automated deduction references, though,


Hartmanis-Stearns conjecture and the computable transcendental numbers

Let $L$ be an EXPTIME-complete language, and let $r \in (0,1)$ be the corresponding real. Clearly $r$ is computable. The number $r$ cannot be algebraic since the $n$th bit of an algebraic number can be computed in time $n^{O(1)}$ (Datta and Pratap). Since the $n$th bit of any number computable by a real-time Turing machine can be computed in time $O(n)$, $r$ cannot be computed by a real-time Turing machine.


What is the point of calling $\lambda$-calculus an algebra?

A calculus is a system of computation based on the manipulation of symbolic expressions. An algebra is a system of symbolic expressions and relations between them[*]. That is, a calculus is a system for figuring out answers, and an algebra is a way of expressing the relations between terms.

The $\lambda$-calculus is either a calculus or an algebra, depending on whether you want to think of the $\beta$ and $\eta$ rules as oriented reduction rules or unoriented equations. If you think of the rules as being oriented, then you have fixed an evaluation order, and the rules tell you how to take a term and produce a normal form. If you think of the rules as being unoriented, then they give you the equality relation on $\lambda$-terms.

[*] There is also a categorical definition of algebra, which is a formal definition somewhat more restrictive than the informal idea. Loosely speaking, the difference is that the formal definition of algebra encompasses just those systems without variable binding. So SKI combinators form an algebra, but the $\lambda$-calculus doesn't.


Provable gaps between decision tree complexity and "true" complexity

Meyer auf der Heide described a non uniform family of linear decision trees for Subset Sum with depth $O(n^4\log n)$.  A similar result can be deived from a later algorithm of Meiser for point location in hyperplane arrangements. Of course the problem is NP-hard.


Is parametrized maximum independent clauses problem in FPT?

The problem is known as r-Set Packing:
Instance: A collection $\mathcal{C}$ of subsets of size at most $r$ of a finite set $S$ and an integer $k$.
Parameter: $k$
Question: Is there a subcollection $\mathcal{C'} \subseteq \mathcal{C}$ which consists of at least $k$ mutually disjoint subsets?

For unbounded $r$, the problem is W[1]-hard by an easy reduction from Independent Set (see for example [1]).
However, for constant $r$, the problem becomes fixed parameter tractable (see for example [2]).

[1]: Rodney G. Downey, Michael R. Fellows: Parameterized Complexity. Springer, 1999.
[2]: Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, Sue Whitesides: Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems. Algorithmica 52(2): 167-176 (2008)


Prior work on finding domain-theoretic suprema of equivalent total functions?

My question is this: If f is a Scott-continuous computable function, and is "total" (i.e. the elements of its domain are all finite, and it takes "fully-defined" values to "fully-defined" values), have techniques been developed for computing a maximal h such that f⊑h?
Of course, if the domain of f is a finite set, one can just represent f as a lookup table and then use elementary deduction to compute h. It's not necessarily efficient in practice, but it yields the correct answer. But what about functions over infinite domains?

Scott-continuity rules out the lookup table approach. For a concrete counterexample, let's start with the Sierpinksi domain $O = \{\bot, \top\}$, with order $\bot \sqsubseteq \top$.
Intuitively, think of $\bot$ as nontermination, and $\top$ as termination. In Haskell terms, think of this as the domain interpreting expressions of type $()$ -- i.e., you either get back a unit or the expression fails to terminate. We'll also use $2$, the booleans, and $2_\bot$, the pointed booleans.
Now, suppose you have $f : O \to 2_\bot$. You can't continuously complete this function, even though there are only a finite number of possible $f$'s! The intuitive reason is that when you run $f(\bot)$, there's no finite waiting period sufficiently long enough to decide that its return value is bottom -- if there were, then I could give you a function that spins for one second longer, and then returns the opposite of whatever you completed the function to. (Prove that any continuous $h : (O \to 2_\bot) \to (O \to 2)$ must return a constant function independent of its argument $f$.)
Don't think of bottom as an extra element of the domain of values. This will lead you astray. Instead, think of elements of the domain as observations of a computation. Really do think of sitting in front of a terminal, waiting for your program to print something. Bottom represents your observation when the program is still running and hasn't printed anything to the screen -- it represents observing nothing.
The best book I know for developing the right intuitions is Steve Vickers' Topology via Logic. It's a short and easy read, but your domain-fu will go way up for reading it.


You can also try to get some intuition from the "correct" version, Fisher-Yeates / Knuth shuffle.

for i in range(len(vec)-1):
    swap(i, randint(i, len(vec)-1))

The idea is that, when we get to i, the previous elements are perfectly random, so let's leave them there and recursively shuffle the rest. In contrast, the naive algorithm will sometimes "reach backward" to make a swap.

Now I'm noticing that in the naive shuffle, elements which are below the current index i can only ever move forward from now to the end of the algorithm. Okay, so in particular, the last element only has two ways to end up in the first position: Either the first element can swap with him, and then nobody else ever swaps with him (this has about a $\frac{1}{n}\frac{1}{e}$ chance), or else nobody ever swaps with him until the last round, and then he swaps with whoever's in first (this has the exact same chance). So the last element should only end up first with probability about $\frac{2}{en} \approx 0.74\frac{1}{n}$ instead of $\frac{1}{n}$.

I simulated this in python with n=100 and 100,000 trials, and got 734 trials in which the last element ended up first, versus 992 trials using Fisher-Yeates.


This is the 'guess' of the second decoder about what would be the a priori information in the above formula (to be used by the other first decoder).
And this exactly message passing of 'extrinsic' information is the major contribution of the French researchers.

Bytheway your formula has typo error, dominator/numerators are in the opossite way, please correct.


Given a domain, how do we build a language whose denotation is the domain?

As it turns out, the OP is interested in the specific case of the interval domain. Martín Escardó's PhD thesis "PCF extended with real numbers: a domain-theoretic approach to higher-order exact real number computation" extends the programming language PCF with a datatype of reals whose denotation is the interval domain.


Lower bound on probability of getting two close points in a sample of $n$ points

Here's a counter-example showing your desired bound is not possible, unless I am mistaken.  It's a simple variant of the example in Roei's comment.

Fix any $n$ and $N\ge 4n$.  Take $D$ to contain $N/2$ points that are all the same (or all within distance 1 from each other), and $N/2$ points that are all widely separated (at distance at least 1 from every other point in $D$).  This can be done even with $D\subset\mathbb{R}^1$.

The probability that two uniformly random points in $D$ are within distance 1 from each other is $1/4$.  In your notation, $p=1/4$ for $B=1$.

The probability that $n$ uniformly random points in $D$ don't contain some pair within distance 1 from each other is (at least) the probability that all $n$ points are in the widely separated set and distinct, which is at least $[(N/2-n)/N]^n \ge 1/4^n$.

So, in your notation $1-P \ge 1/4^n \ge (3/4)^{5n} = (1-p)^{5n}$.

So, $P \le 1 - (1-p)^{5n}$.  So your desired upper bound $P \ge 1-(1-p)^{\omega(n)}$ does not hold.

(If you generalize the example above for arbitrary (small) $p>0$, I think you get something like $P \le 1- (1-\sqrt p)^n \approx 1-(1-p)^{n/\sqrt p}$, which is not a counterexample if $p\rightarrow 0$ as $n\rightarrow \infty$.)