Lower bound for NFA accepting 3 letter language

The bounds...

We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber & Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the same paper.

...cannot be substantially improved

There can be a subexponential gap between $Cov(M)+Cov(N)$ and $NFA(L)$. The following example, and the proof of the gap, is an adaptation of a similar example illustrating the limitations of 2-party protocols for proving lower bounds on nondeterministic state complexity from (Hromkovič et al. 2009):

We use the alphabet $[n]= \{\,1,2,\ldots,n\,\}$. Let $L=\{\,xyz\in [n]^3 \mid x=y \vee x\neq z \,\}$.

We first take care of $Cov(M)$. Observe that if $w=xyz$ with $y=z$, then
$w \in L$: in case $x=y$, $w\in L$ and in case $x\neq y$, we also have
$x\neq z$ and thus $w\in L$. Also, if $w$ is of the form $xyz$ with
$y\neq z$, then $w\in L$ iff $x\neq z$. So we can write $L = L'\cup L''$,
with $L'=\{xyz\in [n]^3 \mid y=z\}$ and $L''=\{\,xyz\in [n]^3 \mid y\neq z
\wedge x \neq z \,\}$.

Now consider the bipartite graphs $G' = (U',V',E')$ with $U'=[n]$, $V'=
\{yz \in [n]^2 \mid y=z\}$, $E' = U' \times V'$, as well
as $G'' = (U'',V'',E'')$ with $U''=[n]$, $V''= \{ yz \in [n]^2 \mid
y\neq z\}$,
$E'' = \{(x,yz) \mid x\neq z\}$, and $G = (U' \cup U'',V' \cup V'', E'\cup E'')$.
Then a biclique edge cover for the graph
$G$ gives rise to a covering of $M$ with $1$-monochromatic
submatrices, and vice versa (Theorem 21 in Gruber & Holzer 2006).

A simple kernelization trick for computing a biclique edge cover for $G'$
is to put the twin vertices from $U'$ into equivalence classes. Then we do the same in the resulting graph for the twin vertices from $V'$.
Twin vertices are those with identical neighborhood.
This step does not alter the minimum number of bicliques needed to cover all
edges in the respective graph.

The kernelization step collapses $G'$ into a graph with two vertices and
a single edge. Thus, the edges of $G'$ can be covered with a single
biclique. Applying the kernelization step to $G''$ yields a crown graph
on $2n$ vertices, whose bipartite dimension (the minimum biclique edge
cover number) is known to be $\sigma(n)$, where $\sigma$ is the inverse
function of the middle binomial coefficient (De Caen et al. 1981). Notice that $\sigma(n)=O(\log n)$.
Thus the bipartite dimension of $G$ is $1+\sigma(n)$, which is identical
to $Cov(M)$.

Now consider $Cov(N)$. Observe that if $w=xyz$ with $x=y$, then $w \in
L$. If $x\neq y$, then $x\in L$ iff $x\neq z$. So we can write $L = L'''
\cup L''''$
with $L'''=\{xyz\in [n]^3 \mid x=y\}$ and $L''''= \{xyz\in [n]^3 \mid
x\neq y \wedge x\neq z\}$. Almost the same argument as above yields
$Cov(N)=1+\sigma(n)$.

It remains to give a lower bound on the nondeterministic state
complexity of $L$. Observe that $L$ contains all words of the form $xxx$
with $x\in[n]$. For each such word $xxx$ fix an accepting computation of a minimal
NFA accepting $L$. Let $p_x$ denote the state reached after reading the
prefix $x$, and let $q_x$ denote the state reached after reading the
prefix $xx$ of the input word $xxx$. Then all pairs $(p_x,q_x)$ must be
different. For the sake of contradiction, assume $(p_x,q_x)=(p_y,q_y)$
for some $x\neq y$. Then we can construct an accepting computation
on input $xyx$, such that the NFA is in state $p_x=q_x$ after reading
the prefix $x$, and in state $q_y=q_x$ after reading the prefix $xy$.
But the string $xyx$ is not in $L$. For the state set $Q$ of the NFA, this shows
that $|Q|^2 \ge n$. Thus,
for large $n$, we obtain a subexponential separation between $Cov(M)+Cov(N)$ and $|Q|$ (the nondeterministic state complexity of $L$).

References

Dominique de Caen, David A. Gregory, Norman J. Pullman: The Boolean rank of zero-one matrices, in: Cadogan, Charles C. (ed.), 3rd Caribbean Conference on Combinatorics and Computing, Department of Mathematics, University of the West Indies, pp. 169–173 (1981)
Hermann Gruber and Markus Holzer. Finding Lower Bounds for Nondeterministic State Complexity is Hard. Report TR06-027, Electronic Colloquium on Computational Complexity (ECCC), March 2006. Short version appeared in: Oscar H. Ibarra and Zhe Dang, editors, 10th International Conference on Developments in Language Theory (DLT 2006), Santa Barbara (CA), USA, volume 4036 of LNCS, pages 363-374. Springer, June 2006.
Juraj Hromkovic, Holger Petersen, Georg Schnitger: On the limits of the
communication complexity technique for proving lower bounds on the size
of minimal NFAs. Theor. Comput. Sci. 410(30–32): 2972–2981 (2009)


Purpose and determining when to use hidden layers

A hidden layer is used to increase the expressiveness of the network.  It allows the network to represent more complex models than possible without the hidden layer.

Choosing the number of hidden layers, or more generally choosing your network architecture including the number of hidden units in hidden layers as well, are decisions that should be based on your training and cross-validation data.  You should train the network with a set amount of nodes (to start, try one hidden layer, with one unit per input unit) and test the model.

See this link for more help:  http://www.faqs.org/faqs/ai-faq/neural-nets/part3/section-10.html


This is really a stubborn -- and well-studied -- problem. Regarding positive results, an exact algorithm by Kameda and Weiner, a heuristic approach by Polák, and a recent approach using SAT solvers by Geldenhuys et al. come to mind. But there seem to be far more negative results ruling out other possible approaches (e.g. approximation algorithms, special cases, less powerful models of NFAs, ...) See below for some references.

T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Transactions on Computers, C-19(7):617–627, 1970.

A. Malcher. Minimizing finite automata is computationally hard. Theoretical Computer Science 327:375-390, 2004.

L. Polák. Minimalizations of NFA using the universal automaton. International Journal of Foundations of Computer Science, 16(5):999–1010, 2005.

G. Gramlich and G. Schnitger. Minimizing NFAs and Regular Expressions. Symposium on Theoretical Aspects of Computer Science (STACS 2005), LNCS 3404, pp. 399–411.

H. Gruber and M. Holzer. Inapproximability of nondeterministic state
and transition complexity assuming P <> NP. Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205–216.

H. Gruber and M. Holzer. Computational complexity of NFA minimization for finite and unary languages. Language and Automata Theory and Applications (LATA 2007), pp. 261–272.

H. Björklund and W. Martens. The tractability frontier for NFA minimization. International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5126, pp. 27–38.

J. Geldenhuys, B. van der Merwe, L. van Zijl: Reducing Nondeterministic Finite Automata with SAT Solvers. Finite-State Methods and Natural Language Processing (FSMNLP 2009), LNCS 6062, 81–92.

EDIT (June 8, 2015)

Update: The following paper presents a heuristic algorithm for reducing the size of nondeterministic Büchi automata, along with experiments on random automata. As they state in the conclusion, their method applies to NFAs as well: "While we presented our methods in the context of Büchi automata, most of them trivially carry over to the simpler case of automata over finite words."

Richard Mayr, Lorenzo Clemente. Advanced Automata Minimization. POPL 2013. Extended Technical Report EDI-INF-RR-1414.

Their command-line tool Reduce v1.2 can be invoked with the option "-finite" for reducing a given NFA. The implementation is open source and released under the GNU General Public License.


I believe SDP is the only known technique to solve the maximum independent set problem on perfect graphs. To get the independent set, one could do the following. Guess if a vertex is in the independent set, delete it and solve the SDP. If it returns the same value, then there is an independent set without this vertex. So, make this vertex adjacent to all other vertices, and continue. This should give you an actual independent set.

Otherwise, we have identified one vertex of the independent set, and we can remove it and continue on the remaining graph.


Counting number of solutions to a specific SAT formula

This is not an answer, just a long comment.

First, you say that you are unsure if this problem in in #P.  It depends on how you define your input, which can either be the $n$-by-$n$ graph or just $n$.  I would say that it is more natural to take the graph as input, in which case, an NP machine can guess $n^2$ bits (which is a polynomial, linear even, in the size of the input) and can check in polynomial time, linear even, if all your constraints are satisfied.  If the input is just $n$, then $n^2$ is exponentially larger than the input size $\log(n)$, so we can't say your problem is in #P, but it is in the counting class related to NEXP (in the same way that #P is the counting class related to NP).

Second, this input issue also affects what types of hardness we can expect to prove. If the input is the grid graph, then you have at most one input for each input length.  Such problems are said to be sparse (which means there is at most a polynomial number of inputs for each input length) and are not expected to be hard by (a generalization of) Mahaney's theorem.  But if you pick $n$ to be your input so that set of instances is no longer sparse, then your output is exponentially larger than your input.  What I am trying to say here is that the typical notions of hardness don't apply very well to your problem.

Third, I can say something about the possibility of this problem being tractable.  My research is in counting problems defined by local constraints, which we formally define as Holant problems. The difference between Holant problems and your problem is that we don't put such tight restrictions on the inputs graphs.  We allow restrictions like planar, bipartie, and prescribed degree (such at $k$-regular or at most degree $k$), none of which defines a sparse set of graphs.

The best I can do to cast your problem as a Holant problem is as follows.  For omitted definitions, see the preliminary section in a recent paper of mine.  In the Holant framework, edges take values from a finite domain and vertices impose constraints on the values assigned to its incident edges.  To (partially) model your problem, we consider the Boolean domain $\{0,1\}$.  As a first attempt to capture your problem, think of an $n$-by-$n$ grid graph as the input.  To associate a bit with each vertex $v$, we add an edge $e_v$ incident $v$ and to a new vertex $u_v$.  To communicate this bit value to the neighboring internal vertices, we duplicate all the edges between internal vertices (i.e. vertices not on the boundary) in the original $n$-by-$n$ grid graph.

The vertices on the boundary have no constraint, which is represented by the signature $[1,1]$ tensored with itself twice for the corner vertices and three times for the vertices on the sides.  The remaining interior vertices pick an edge in each direction and require these four edges and the other edge added above (with its associated bit) to take the same value. Then we impose your constraint by comparing this value with the four values assigned to the remaining four edges (one edge in each direction).  Of course, between each pair of internal vertices, they have to agree on which edge each uses to communicate their bit value.  One way to decide this, in a planar embedding of this graph, is that each vertex should use the edge that is encountered first in a clockwise traversal of its incident edges.

The paper of mine that I linked to above is a dichotomy for Holant problems that use symmetric signatures (which means that the output is invariant under any permutation of the input).  Unfortunately, the constraint that I used to capture your problem at internal vertices is not symmetric and it is still an open problem to prove the generalization of that dichotomy for general (i.e. not necessarily symmetric) signatures.  Worse yet, we currently do not even know how to decide if this Holant problem is easy or hard according to what we conjecture the dichotomy to be.  Furthermore, we can impose restrictions on the input graphs like being planar and bipartite that are satisfied by your grid graph, the hope being that this Holant problem may become tractable under these restrictions. However, a dichotomy for such Holant problems is years, maybe even a decade away.

In closing, let me emphasize that this Holant problem that I have described is "more difficult" than your problem (when the input is the grid graph).  The input to this (planar, bipartite) Holant problem can only use the complicated arity 9 constraint (that was assigned to the internal vertices) and the (unconstraining) unary constraint $[1,1]$ but the graph is not restricted to grid graphs. Formally speaking, your problem (when the input is the grid graph) reduces to this Holant problem. So, if this Holant problem were easy, then your problem (when the input is the grid graph) is easy too, but if this Holant problem is hard, then I want to say that your problem is hard, but I don't know how to do so (as I discussed above).


Is there a reduction to "door and pressure plate" games that doesn't explode solution length?

Perhaps you can easily simulate a LBA; the idea is the following:

for every cell of the LBA tape add a cell gadget $G_i$ that can be entered only from the bottom and leaved only from the top;
the gadget has an entrance door $C_i$ which simulates the head position (only one $C_i$ is opened at every step);
then there are two bit doors $Z_i$ and $O_i$; $Z_i$ is opened if the cell contains a  zero, $O_i$ is opened if there cell contains a one;
both bit doors lead to a similar control structure which is made by several one-way corridors; a corridor corresponds to a state of the LBA, and the door $q_i$ of the $i$-th corridor is opened if and only if the current state of the LBA is $q_i$;
according to the (possibly non-deterministic) transition table of the LBA, a traversal of the (opened) corridor changes the current state of the LBA and the configuration of the bit-doors, closes door $C_i$ and opens $C_{i+1}$ or $C_{i-1}$.

A cell gadget is sketched in the figure below.

Non-deterministic choices can be realized splitting the corridors  in the control structures into two or more sub-corridors as shown in the figure below.

Note: if a plate can only open/close a single door, then you can add an auxiliary structure with (long) one way corridors that (de)activates the distinct state doors of each cell.


What is the maximal load of a "latency-bounded" Cuckoo Hash?

Section 4 of the journal version of the original Cuckoo Hashing paper shows that to have insertion succeed with probability $p$, your numbers $T$, $n$, and $\epsilon$ must satisfy

$$
\frac{13}{n^2 \epsilon}
+
2(1+\epsilon)^
{1-(2T-1)/3}
<p
$$

where the two sub-tables are of size $n(1+\epsilon)$.

So for $p = 9/10$, $T=8$, and $n=1,000,000$, we get $\epsilon \approx 0.221$. The first term is basically negligible.


When $k$ is given as part of the input, the second problem is equivalent to the monochromatic Max-IP problem (given $S \subseteq \{0,1\}^d$, find $\max_{(a,b) \in S, a\ne b} a \cdot b$).

Recently I and Ryan Williams have an (unpublic yet) work showing that when $d = O(\log n)$, OVP and a bichromatic version of Max-IP (given $A,B$, find $\max_{(a,b) \in A \times B} a \cdot b$), is actually equivalent: that is, if one of them has $n^{2-\varepsilon}$ time algorithm, so does the other one. (The reduction from OVP to Max-IP is well-known, the new reduction here is that from Max-IP to OVP).

Since the monochromatic version of Max-IP can be reduced to the bichromatic version, the above result also implies that when $d = O(\log n)$, monochromatic Max-IP can be reduced to OVP.

I believe it is an open question that whether OVP can be reduced to monochromatic Max-IP. This is also closely related to establishing the OV-hardness for the closest pair problem (see e.g. On the Complexity of Closest Pair via Polar-Pair of Point-Sets)

For monochromatic Max-IP, there is an algorithm with running time $n^{2 - 1/\widetilde{O}((d/\log n)^{1/3})}$ time algorithm by Alman, Chan and Williams (also pointed out by Rasmus), for which I believe is the state of the art. While the best algorithm for OVP runs in $n^{2 - 1/O(\log c)}$ time when $d = c \log n$, which is significantly faster.

Also, the approximate version of Max-IP is also studied by this paper On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product, which gives a characterization for the bichromatic case (that is, for which dimensions $d$ and approximate ratio $t$, the problem can be solved in $n^{2-\varepsilon}$ time?). The algorithm in that paper also works for the monochromatic case.


Minimum Degree Spanning Tree Without Restricting Vertices Searched

This is not an answer, but some experimental evidence on why I think this might be an $OPT+1$ approximation.
I wrote some python code that runs the local search algorithm (without restricting the vertices searched) and solves the problem optimally with ILP. I tried it on thousands of small random graphs and the local search was always $OPT$ or $OPT+1$. Here is the code:
import networkx as nx
from pulp import *

def local_search(G):
    T = nx.algorithms.tree.mst.minimum_spanning_tree(G)

    while True:
        noChange = True
        for w in G:
            for u,v in G.edges():
                Tset = set(T.edges())
                if (u,v) not in Tset:
                    T.add_edge(u,v)
                    C = nx.algorithms.cycles.find_cycle(T)
                    T.remove_edge(u,v)
                    C_vertices = set([x for y in C for x in y ])
                    if w in C_vertices and T.degree[w]>=max(T.degree[u], T.degree[v])+2:
                        T.add_edge(u,v)
                        for x,y in C:
                            if x==w or y==w:
                                T.remove_edge(x,y)
                                break
                        noChange = False
        if noChange:
            break
    return max([T.degree[u] for u in G]), T

def opt_soln(G):
    prob = LpProblem("The Minimum Degree Spanning Degree",LpMinimize)
    z = LpVariable("maxIndegree",1,None,LpInteger)
    variables = {
        tuple(sorted([u,v])) : LpVariable(f"x_{(u,v)}",0,1,LpInteger) for u,v in G.edges()
    }
    vertex_to_edges = {
        u : [variables[tuple(sorted([u,v]))] for v in G.neighbors(u)] for u in G
    }
    prob += z
    prob += lpSum(variables.values()) == (len(G)-1)
    for u in G:
        prob += lpSum(vertex_to_edges[u]) <= z
    prob.solve()
    return value(prob.objective)

tries = 1000
for _ in range(tries):
    n = 34
    p = 0.1
    d = 10
    G = nx.generators.random_graphs.fast_gnp_random_graph(n, p)
    #G = nx.generators.random_graphs.random_regular_graph(d, n)
    if not nx.is_connected(G):
        continue
    delta_T, T = local_search(G)
    delta_star = opt_soln(G)
    if delta_T-  int(delta_star)>1:
        print(delta_star, delta_T)
    #nx.draw(T)


What is known about the relationship between PR and NEXP?

Transforming the comments above into an answer:

NEXP is strictly contained in PR. Indeed define the class ELEMENTARY as
$$\mathsf{ELEMENTARY}=\text{DTIME}(2^n)\cup \text{DTIME}(2^{2^n}) \cup \text{DTIME}(2^{2^{2n}}) \cup ...$$

It can be shown that ELEMENTARY is strictly contained in PR. Since $\mathsf{NEXP}\subseteq \mathsf{ELEMENTARY}$ we have that $\mathsf{NEXP}$ is strictly contained in $PR$.

As pointed out by Huck Bennett above, the fact that $\mathsf{NEXP}\subseteq \mathsf{ELEMENTARY}$
is a consequence from the fact that

$$\mathsf{NEXP} = \text{NTIME}(2^{\text{poly}(n)}) \subseteq \text{DTIME}(2^{2^{2^n}}) \subsetneq \mathsf{ELEMENTARY}$$


The problem that you describe is NP-hard even on stars as we can reduce Multicut in Trees to its decision version (where we have a cost bound). In Multicut in Trees the input is a tree $G=(V,E)$, a set $S\subseteq {V\choose 2}$ of vertex pairs, and an integer $k$ and one asks whether one can separate all vertex pairs of $S$ by removing at most $k$ edges. The reduction to your problem is to keep $G$ and $S$ as they are, set $N$ to $k+1$ and set the cost bound for accepting a solution to $+\infty$. Then the Multicut instance is a yes-instance if and only if the constructed instance is a yes-instance.

Note that this reduction does not specify how to define the edge weights. In other words, even testing whether there is a feasible solution, that is, any partition with $N$ parts is NP-hard.


Hook length formuli and their invariance properties?

Consider two posets $P,Q$ and an element $x \in V(P)$. Let $Pe(x)$ denote the immediate predecessors of $x$ and let $Su(x)$ denote the immediate successors of $x$ in $P$. Let $Min_Q,Max_Q$ denote the minimal, resp. maximal, elements of $Q$. Fix two mappings $Conn_1 : Pe(x) \rightarrow Min_Q$ and $Conn_2 : Su(x) \rightarrow Max_Q$. It is then possible to define a poset $R$ by starting with $(P - x) \uplus Q$ and by adding an arc $(w,Conn_1(w))$ for each $w \in Pe(x)$, and an arc $(w,Conn_2(w))$ for each $w \in Su(x)$.

This operation has a simple meaning for trees: given a tree $T$, you pick a node $u$, and you substitute it by a tree $T'$ by attaching the leaves of $T'$ to the children of $u$ in an injective manner. This means that the trees are closed under this operation of substitution, and thus we could expect that it preserves the property you're interested in. I admit though that I have no idea of what I'm doing with this defn, this might be a joke so please check on your side :)


Parallel programming languages which look deterministic?

I'm not sure about the "without any additional tags or meta-data" part, but I know that recent versions of Matlab make it pretty easy to parallelize your code by simply adding the "par" keyword to your for loops (see the Matlab help for more info).

This is as close to having no "noticeable differences for the programmer" that I'm aware of.


Full Completeness vs Full Abstraction of a program translation

Unfortunately, there are too many things are going on here.  So, it is easy to mix things up.  The use of "full" in "full completeness" and "full abstraction" refer to completely different ideas of fullness.  But, there is also some vague connection between them.  So, this is going to be a complicated answer.

Full completeness:  "Sound and complete" is a property you want for a traditional logic to have with respect to its semantics.  Soundness means that whatever you can prove in the logic is true in the semantic model.  Completeness means that whatever is true in the semantic model is provable in the logic.  We say that a logic is sound and complete for a particular semantic model.  When we come to constructive logic, such as Martin-Lof type theory or linear logic, we care not only about whether formulas provable, but also what their proofs are.  A provable formula may have many proofs and a constructive logic wants to keep them apart.  So, a semantics for a constructive logic involves specifying not only whether a formula is true, but also some abstract semantic notion of "proof" ("evidence") for its truth.  Abramsky and colleagues coined the term "full completeness" to mean that the proofs in the logic can express all the semantic proofs in the model.  So, "full" refers to proofs here.  A "complete" logic can prove everything it needs to.  A "fully complete" logic has all the proofs that it needs to have.  So "full completeness" means "constructive completeness" or "proof completeness".  This has nothing to do with full abstraction.

Full abstraction: "Adequate and fully abstract" is a property you want for the semantic model of a programming language.  (Note the first difference: we are now dealing with the properties of the semantic model, not the properties of the language!)  Adequacy means that, whenever two terms have the same meaning in the semantic model, they are observationally equivalent in the programming language (with respect to some notion of execution).  Full abstraction means that, if two terms are observationally equivalent, they have the same meaning in the semantic model.  These ideas can be related to soundness and completeness, but in a somewhat contrived way.  If we think of the semantic model of a programming language as a "logic" or a "proof method" to talk about observational equivalence, then adequacy means that this proof method is sound; full abstraction means that this proof method is complete.  There is no notion of "full completeness" here because nobody has yet produced a semantic model that represents a constructive proof method.  (But, such a thing is theoretically possible, and one of these days somebody might do so.)

In your case, you are interested in translations rather than semantic models.  The properties of adequacy and full abstraction can be extended to deal with translations as follows.  You think of the target language as your "semantic model", i.e., a formalism that you fully understand somehow.  If so, you have some notion of equivalence for it.  Then, we say that the translation is adequate if, whenever the translations of two source programs are equivalent in the target language, they are observationally equivalent in the source language.  We say that it is fully abstract if, whenever two source programs are observationally equivalent in the source language, their translations are equivalent in the target language.

In reality, I don't know of any target languages that we really fully "understand".  All we know is some other notion of observational equivalence for the target language.  In that case, the translation is adequate if the observational equivalence of the translations in the target language implies observational equivalence in the source language.
$$ \tau(M) \cong \tau(N) \Longrightarrow M \cong N$$
The translation is fully abstract if the observational equivalence of the terms in the source language implies the observational equivalence of the translations in the target language.
$$M \cong N \Longrightarrow \tau(M) \cong \tau(N)$$
Some authors take "fully abstract translation" to mean the combination of these two properties:
$$M \cong N \iff \tau(M) \cong \tau(N)$$

Egger et al seem to be similarly extending the idea of full completeness to translations.  In their set-up, formulas are types and proofs are terms.  Their translation translates types as well as terms.  They call their translation fully complete if the translation of a type $A$ has only those terms that are obtained by translating the original terms of type $A$.
$$\forall N : \tau(A).\; \exists M : A.\, \tau(M) = N$$

Now for the vague connection between full completeness and full abstraction.  Proving that a semantic model or a translation is fully abstract often involves some of definability.  This is because our languages are generally higher-order.  So, if the semantic model or the target language has too many "contexts" then it will be able to poke our terms or semantic meanings in undesirable ways and spoil their equivalence.  "Undesirable ways" means in ways that the programming language itself cannot poke them.  So, to get full abstraction, we need to ensure that the "contexts" available in the semantic model or the target language do come from those in the source language in some form.  Note that this relates to the full completeness property.

Why do we want such properties?  It has nothing to do with compilers!  We want these properties in order to claim that the source language embeds into the target language.  If we are happy with a particular target language (as being clean, understandable, somehow fundamental or God-given) then, if the source language embeds into it, then we can claim that there is nothing new in the source language.  It is just a fragment of the target language that we know and love.  It is just syntactic sugar.  So, fully abstract translations are given by people to establish that particular target languages are great.  They are also sometimes given by people who have a big or complicated language to deal with.  So, instead of defining a semantics for it directly, they translate it to some core language and then give semantics to the core language.  For instance, the Haskell report does this.  But the full abstraction of these translations is rarely ever proved because the source languages are big and complicated.  People take it on faith that the translation is good.

Once again, this has nothing to do with compilers.  Compilers are rarely ever adequate or fully abstract.  And, they don't need to be!  All that a compiler needs to do is to preserve the execution behavior of complete programs.  The target language of a compiler is generally huge, which means that it has lots of contexts that can mess up equivalence.  So, equivalent programs in the source language are almost never contextually equivalent when compiled.


Combinatorial discrepancy of the system of all cuts

I doubt you can do better than $O(n^{3/2})$. Here is a lower bound, using old arguments by Spencer and Erdos, that shows that the discrepancy is $\Omega(n^{3/2})$ if you expand the set system to cuts of induced subgraphs. See the edit for a lower bound for cuts as well, suggested by Domotor.

Let $V$ be the vertex set of the complete graph, and fix a function $f:{V \choose 2} \to \{-1, 1\}$. Split $V$ into $L$ and $R$, each of equal size. Let $S$ be a random subset of $L$. Then, for any $v \in R$,
$$
\mathbb{P}\left(\Bigl|\sum_{u \in S}{f(u, v)}\Bigr| \geq c\sqrt{n}\right) \ge 1/4,
$$
for a suitable constant $c$. (This can be proved using the Central Limit Theorem or a 4-th moment argument.) Letting $T_0$ be the subset of all $v \in R$ satisfying $\Bigl|\sum_{u \in S}{f(u, v)}\Bigr| \geq c\sqrt{n}$, we have that $\mathbb{E}|T_0| \geq n/8$. So there exists some choice of $S$ such that $T_0$ has size at least $n/8$: fix such an $S$ and pick $T = \{v \in R: \sum_{u \in S}{f(u, v)} \geq c\sqrt{n}\}$ or $T = \{v \in R: \sum_{u \in S}{f(u, v)}\leq -c\sqrt{n}\}$, whichever is larger. Clearly
$$
\Bigl|\sum_{u \in S, v \in T}{f(u,v)}\Bigr| \ge \frac{cn^{3/2}}{16}.
$$

EDIT: As Domotor pointed out in a comment the above suffices for a $\Omega(n^{3/2})$ lower bound on the discrepancy of cuts as well. Let $S$ and $T$ be the sets above, and $U = V \setminus (S \cup T)$. Define $f(X,Y) = \sum_{x \in X, y \in Y}{f(x,y)}$ for any two subsets $X,Y\subseteq V$. Assume without loss of generality that $f(S,T) \ge c'n^{3/2}$ for $c' = c/16$ (the case $f(S,T) \le -c'n^{3/2}$ is analogous). Then at least one of the cases below holds:

$f(S,U) \ge -c'n^{3/2}/2$ and $f(S, T \cup U) \ge c'n^{3/2}/2$;
$f(T,U) \ge -c'n^{3/2}/2$ and $f(S\cup U, T) \ge c'n^{3/2}/2$;
$f(S \cup T, U) = f(S, U) + f(T,U) < -c'n^{3/2}$.

In each case the discrepancy of some cut is $\Omega(n^{3/2})$.


Is S-T CONNECTEDNESS #P-complete on instances when all s-t paths are of the same length?

After polynomial time preprocessing, you may assume that every edge in $E$ lies on some simple $s$-$t$-path.

If all simple paths between $s$ and $t$ are of the same length, then $G$ is series-parallel, with $s$ as left terminal and $t$ as right terminal vertex. This can be seen easily, since the forbidden subgraphs for series-parallel graphs (= subdivisions of diamonds) create two paths of different lengths between $s$ and $t$.
In a series-parallel graph, the number of spanning subgraphs containing a simple $s$-$t$-path can be determined in polynomial time by dynamic programming.

In the dynamic program, we build up the graph by series and parallel compositions. For every resulting subgraph $G'$, we compute the number $p^+(G')$ of spanning subgraphs that do contain a simple path from its left terminal to its right terminal and the number $p^-(G')$ of spanning subgraphs that do not contain such a path.

In a series composition on $G_1$ and $G_2$, we get $p^+(G)=p^+(G_1)\cdot p^+(G_2)$.
In a parallel composition on $G_1$ and $G_2$, we get $p^-(G)=p^-(G_1)\cdot p^-(G_2)$.
In both cases, the missing value $p^+(G)$ or $p^-(G)$ for $G=(V,E)$ can be computed from $p^+(G)+p^-(G)=2^{|E|}$.


description of continuous probability distribution

You're confusing the Shannon entropy of a discrete probability distribution with the differential entropy of a continuous probability distribution. The minimum distribution length is only given by the Shannon entropy for discrete probability distributions.

What the fact that the differential entropy is 0 for this probability distribution means is that for large $k$, you can approximate this random variable with an expected error of $1/2^k$ using $k$ bits. If the differential entropy were $\ell$, you could approximate it with an error of $1/2^k$ using $k+\ell$ bits.


Yes, it is called a multiple-choice knapsack problem. It can be solved in time $O(N B)$ by dynamic programming. The state of the dynamic program is given by a pair $(i, b)$ and the associated value is the maximum value (clicks) you can get with keywords from $1$ to $i$ with a budget at most $b$.

Source: S. Martello, P. Toth. Knapsack Problems. Wiley, 1990.


Self-organizing maps algorithm(Kohonen networks)

Visualization of clusters.

The same ordered display can be used for illustrating the clustering density in different regions of the data space. The density of the reference vectors of an organized map will reflect the density of the input samples [Kohonen, 1995c, Ritter, 1991]. In clustered areas the reference vectors will be close to each other, and in the empty space between the clusters they will be more sparse. Thus, the cluster structure in the data set can be brought visible by displaying the distances between reference vectors of neighboring units [Kraaijveld et al., 1992, Kraaijveld et al., 1995, Ultsch, 1993b, Ultsch and Siemon, 1990].

The cluster display may be constructed as follows [Iivarinen et al., 1994]. The distance between each pair of reference vectors is computed and scaled so that the distances fit between a given minimum and maximum value, after optionally removing outliers. On the map display each scaled distance value determines the gray level or color of the point that is in the middle of the corresponding map units. The gray level values in the points corresponding to the map units themselves are set to the average of some of the nearest distance values (on a hexagonal grid, e.g., to the average of three of the six distances toward the lower-right corner). After these values have been set up, they can be visualized as such on the display, or smoothed spatially.

The resulting cluster diagram is very general in the sense that nothing needs to be assumed about the shapes of the clusters. Most of the clustering algorithms prefer clusters of certain shapes [Jain and Dubes, 1988].


As per Suresh's request (he is the boss after all) I am making my comment above an answer.

Emina Soljanin at Alcatel-Lucent Labs works on network coding and content delivery networks. She has written survey articles on network coding. See her web page. ect.bell-labs.com/who/emina. You can also check out her papers on content delivery via network coding and other means on the ArXiv.

I also want to say that network coding is a topic of much interest to theoretical computer science - there are several papers in TCS on this topic.


Is there a candidate for a natural problem in $P/poly - P$?

I do not know if this satisfies your requirements, but Bill Gasarch’s blog post in July 2010 asks about languages in SPARSE∩NP which are not thought to be in P, giving an example from Ramsey Theory.  Any such languages belong to (P/poly)∩NP.

Related to this, For any language L∈NP, the language TL={1n: L contains some string of length n} is in TALLY∩NP ⊆ SPARSE∩NP ⊆ (P/poly)∩NP.  Depending on the choice of the language L, TL may not have an obvious reason to belong to P.


Can factorial be encoded in the Kappa-calculus with fixed point operator?

The bare $\kappa$-calculus does not permit defining factorial, even when extended with a fixed point operator. However, this answer deserves some unpacking.

The fixed point operator you give is not well-formed according to the grammar of types in the $\kappa$-calculus. Note that the grammar of types does not contain the function space $\tau \Rightarrow \tau'$ -- this is because the $\kappa$-calculus is a language of first-order functions. An expression has a type $\tau_1 \to \tau_2$, to indicate that it is an expression of type $\tau_2$, whose free variables are typed by $\tau_1$.

The proper typing for a fixed point operator would be roughly something like:
$$
\frac{\Gamma, x:1 \to \tau \vdash e : 1 \to \tau}
     {\Gamma \vdash \mu x:1 \to \tau. e : 1 \to \tau}
$$
Once you've fixed this, you still can't define a factorial.

The plain $\kappa$-calculus does not have sums or natural numbers as a base type. As a result, you can't write branching programs, and so you cannot define interesting recursive functions. If you added natural numbers and their iterator, you could define a factorial function. Hasegawa actually gives factorial as an example in his paper on the $\kappa$-calculus, in a calculus augmented with a basic natural number type.

However, you might wonder why you are able to define factorial in the pure lambda calculus, even though it has no apparent control structures. The reason is that the interaction of fixed points and recursion gives you a "universal type" (i.e., a type $V$ such that $V$ is isomorphic to $V \to V$), and this lets you encode any datatype as a subset (more accurately, a retract) of it.

In more syntactic terms, you can write the Y combinator (i.e., Curry's paradox) in any language with (a) higher-order functions, (b) recursion, and (c) the ability to use each variable more than once in a program. Since the basic $\kappa$-calculus lacks (a), adding even an unrestricted fixed point operator does not make it Turing-complete!


Finding odd holes in circulant Paley graphs

I believe there is a known poly(q) algorithm. My understanding of the algorithm by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković, "Recognizing Berge Graphs", Combinatorica 2005, is that it finds either an odd hole or an odd antihole in any non-perfect graph in polynomial time. The authors write on page 2 of their paper that the problem of finding odd holes in graphs that have them remains open, because steps 1 and 3 of their algorithm find holes but step 2 might find an antihole instead. However, in the case of Paley graphs, if you find an antihole, just multiply all the vertices in it by a nonresidue to turn it into an odd hole instead.

Alternatively, by analogy to the Rado graph, for each k there should be an N such that Paley graphs on N or more vertices should have the extension property: for any subset of fewer than k vertices, and any 2-coloring of the subset, there exists another vertex adjacent to every vertex in one color class and nonadjacent to every vertex in the other color class. If so, then for k=5 you could build an odd 5-hole greedily in polynomial time per step. Maybe this direction is hopeful for a poly(log(q)) algorithm? If it works it would at least show that there are short odd holes, seemingly a necessary prerequisite to finding them quickly.

Actually, it wouldn't surprise me if the following were a poly(log(q)) algorithm: if q is smaller than some fixed constant, look up the answer, else greedily build an odd 5-hole by searching sequentially through the numbers 0, 1, 2, 3, ... for vertices that can be added as part of a partial 5-hole. But maybe proving that it works in poly(log(q)) time would require some deep number theory.

By results of Chung, Graham, and Wilson, "Quasi-random graphs", Combinatorica 1989, the following randomized algorithm solves the problem in a constant expected number of trials when q is prime: if q is sufficiently small then look up the answer, else repeatedly choose a random set of five vertices, check whether they form an odd hole, and if so return it. But they don't say whether it works when q is not a prime but a prime power, so maybe you'd need to be more careful in that case.


Samples provides you only with statistical guarantees. For a fixed $\epsilon$ whatever you compute would hold for everything "except" $(1-\epsilon)$ fraction (I am being very informal here). Thus, taking an $\epsilon$-net sample of a set of points in the plane, computing its smallest enclosing disk, results in a disk $D$ that contains $(1-\epsilon)$ fraction of the whole point set (or $(1-\epsilon)$ of the measure).

Coresets on the other hand, provide geometric guarantees. For example, for a point set $P$ in the plane, an $\epsilon$-coreset for smallest enclosing disk is a subset $S$, such that any disk $D$ that contains $S$, if you slightly expand it (formally, scale it up by a factor of $(1+\epsilon)$, the it must contain all the points of $P$.

The beauty of samples is that you can generate them without a priori knowing what you are going to use them for. Coresets on the other hand are application dependent - you need different algorithms to compute them depending on the function you are trying to capture.

As for characterization - we have many positive results (see the survey here: http://sarielhp.org/p/04/survey/). We also have counter examples which are somewhat mysterious - http://sarielhp.org/p/02/2slab/ (no coreset no cry [after working for months on trying to compute a coreset for this problem, I definitely wanted to cry]). The rule of thumb is that you are not going to have a coreset if:

(A) The underlying function change dramatically if you can remove a single point, and there are many such points (say, closest pair, or k-center clustering, etc). Solving such problems in linear time requires different techniques.

(B) Or putting (A) differently - the underlying function is not very stable if you move points around.

It is unlikely to have a better characterization without assuming something significantly stronger on the underlying function that one is trying to compute.


Shortest path in DAG with path dependent arc costs

Without further information on how the costs can vary, the problem is NP-complete. For instance, consider the following rule for setting costs:

If an edge would return to a previously-traversed node then its cost is $n$
If an edge reaches $t$ without previously traversing all other nodes then its cost is $n$
In all other cases the cost of an edge is $1$.

For such a rule, a Hamiltonian path has cost $n-1$ and all other paths have cost $n$ or greater. The problem could still be solved more efficiently than a brute-force search (e.g. in time $O(n^22^n)$ by dynamic programming) but not in polynomial time unless $\mathsf{P}=\mathsf{NP}$.

So if you want to find a polynomial time algorithm you will need to be much more specific about what sort of dependence between edge cost and previous path information is allowed.


Lemma. If a graph has a $k$-plex on $m$ vertices, then it has a clique on $\frac m{k+1}$ vertices.

Proof. Greedily pick the vertices of the clique from the $k$-plex.

Since a clique on $m$ vertices is also a $k$-plex on $m$ vertices (for any $k$), we get that the size of the maximum $k$-plex is a $k$-approximation of the size of the maximum clique.
Since clique is hard to approximate with an $O(n^{1-\epsilon})$ factor, determining the largest $k$-plex is also hard for any $k=O(n^{1-\epsilon})$.


Matrix multiplication algorithms for research

The fastest way to multiply dense matrices on a modern computer is to call BLAS.


What is the state of the art research in analysing algorithms on GPU architectures?

research into GPU algorithms continues and it is well suited to some problems, but some of the initial excitement may be wearing off after lackluster results and difficulty of translating problems into GPU approaches. also in recent times there is some consternation over transfer overhead to/ from the GPU. from anecdotal/ background stories/ conversations shared by some physics researchers, some universities (eg specializing in supercomputing) spent significant money on GPU clusters which are not largely utilized (eg in physics simulations contexts?), but what factor that may be due to is not clear. a forthright appraisal might observe that historically GPU companies might have overhyped the potential somewhat akin to the Gartner hype curve.

a possibly helpful paradigm for understanding the GPU role in parallel computing is the Berkeley framework of 7 "dwarves" & there is some brief mention of GPU there. another recent success story, at one point GPUs for a time period/ window were heavily used in bitcoin mining, but they are now almost entirely eclipsed by custom ASIC solutions.

from the theoretical pov there may not be so much interest due to that they are to some degree "just a hardware implementation detail" and possibly at best leading to linear speedups (albeit for sizeable/ worthwhile constants) even with ingenious implementations.

what kind of problems lend themselves well to gpu computing? scicomp.se
on GPU algorithms (wrt TCS community) Suresh Venkatasubramanian (tcs.se mod) & commentary by other researchers
Where is the Data? Why You Cannot Debate CPU vs. GPU Performance Without the Answer Gregg / Hazel
Reducing GPU Offload Latency via Fine-Grained CPU-GPU Synchronization Lustig/ Martonosi
techniques to reduce cpu to gpu data transfer latency stackoverflow
CUDA memory transfer overhead
The Landscape of Parallel Computing Research: A View from Berkeley


Introductions to steganography from an information-theoretic standpoint

Here is a brief overview and introduction to steganography:

Christian Cachin. Digital steganography. In Henk C.A. van Tilborg, editor, Encyclopedia of Cryptography and Security. Springer, 2005

Since you asked for an introduction specifically for information-theoretic approaches, you might try this paper as a starting point for more detail:

Christian Cachin. An information-theoretic model for steganography. Information and Computation, 192(1):41-56, July 2004.

If you want a coding-theoretic perspective, you might also enjoy the following papers:

Yin Wang, Pierre Moulin.  Perfectly Secure Steganography: Capacity, Error Exponents, and Code Constructions.  IEEE Transactions on Information Theory, 2008.

Pierre Moulin, Joseph A. O'Sullivan. Information-Theoretic Analysis of
Information Hiding.  IEEE Transactions on Information Theory, 2003.

I do encourage you to also take a look at computational steganography (e.g., the Hopper et al. paper you cite in your question), as many of the powerful results are in the computational security regime


What languages can be reduced to a NP-complete problem in polynomial time

Under Karp reductions, the answer is exactly $\mathbf{NP}$: it is not hard to see that if a language is Karp-reducible to any $\mathbf{NP}$-language, then it is in $\mathbf{NP}$ too. On the other hand, all of $\mathbf{NP}$ reduces to $\mathbf{NP}$-complete languages by definition.

Under Turing reductions, the answer is the class $\mathbf{P}^\mathbf{NP}$: languages that are decidable by a polynomial-time algorithm that has an access to an $\mathbf{NP}$ oracle. Indeed, a Turing reduction of a language $L$ to an $\mathbf{NP}$-complete language is by definition a polynomial-time algorithm deciding $L$ with oracle access to $\mathbf{NP}$. On the other hand, any such algorithm can be simulated with oracle access to an $\mathbf{NP}$-complete language, thus obtaining a Turing reduction.


What do you call the join of two optimization problems?

I think this falls in the category of multi-objective function optimization problems.

To be specific, it's a linear scalarization of an optimization problem with two objective functions.

I don't know this field very well, but I expect their complexity has been studied.


Nontrivial algorithm for computing a sliding window median

Here's a lower bound from sorting. Given an input set $S$ of length $n$ to be sorted, create an input to your running median problem consisting of $n-1$ copies of a number smaller than the minimum of $S$, then $S$ itself, then $n-1$ copies of a number larger than the maximum of $S$, and set $k=2n-1$. The running medians of this input are the same as the sorted order of $S$.

So in a comparison model of computation, $\Omega(n\log n)$ time is required. Possibly if your inputs are integers and you use integer sorting algorithms you can do better.


approximating problems described by multiple parameters

This is not an answer, but rather a personal experience.  I'll post it as an answer since it's too long to be a comment.

If I would be an author, I wouldn't use the expression like "linear-approximation" since it's confusing.

I haven't seen an expression like "linear-approximation" or "logarithmic-approximation" for referring to approximation ratios.  For example, the greedy algorithm for the minimum set cover problem is an $H(n)$-approximation algorithm, where $H(n)$ is the $n$-th Harmonic number, but I haven't seen it's called a logarithmic-approximation algorithm.  Here, $n$ is the size of a universe, and this should be explained in the definition of the problem.  Please note that $n$ is not the input size.

There's one exception.  In the book "Complexity and Approximation" by Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, and Protasi, I can find expressions like log-APX, poly-APX and exp-APX.  For example, log-APX refers to the class of NP optimization problems that have an $O(\log n)$-approximation algorithm, where $n$ is the input size.

Some authors use "a linear approximation algorithm" to mean a linear-time approximation algorithm.  I feel this is still confusing, and I would write linear-time approximation.  People tend to omit "time", and for example when they write "a polynomial algorithm", they often mean a polynomial-time algorithm.


When does randomization stops helping within PSPACE

There is a difficulty with the premise of your question — "when does randomization stops helping within $\mathrm{PSPACE}$ — because it suggests that the computational classes $\mathrm{X}$ such that $\mathrm{P \subseteq X \subseteq PSPACE}$ form some sort of linear hierarchy when this is not evident.

We can illustrate this by comparisons between the polynomial hierarchy and counting classes. As Emil Jeřábek indicates in the comments,
   $$\begin{align*} \mathrm{BP\cdot \Sigma_i^p \subseteq \Pi_{i+1}^p} &&\text{and}&&  \mathrm{BP\cdot \Pi_i^p \subseteq \Sigma_{i+1}^p} \end{align*}$$
 by relativisation of $\mathrm{AM \subseteq \Pi_2^p}\,$; and therefore $\mathrm{BP \cdot PH = PH}$. On the other hand, Toda's Theorem shows that
$$\mathrm{PH \subseteq BP\cdot\oplus P}.$$
If you suppose that "randomization has stopped adding power by the time you ascend to $\mathrm{PH}$", then you will be tempted to suspect that because $\mathrm{PH \subseteq BP \cdot \oplus P}$, perhaps in fact $\mathrm{BP \cdot \oplus P = \oplus P}$. But I don't know that anyone conjectures this, or even that $\mathrm{PH \subseteq \oplus P}$ (which would be a necessary consequence); I think that any result of this sort would be considered a major breakthrough.

Of course, if you only care about the polynomial hierarchy, and more generally (to scale up to $\mathrm{PSPACE}$) quantified boolean formulas, then you can extract some sort of linear answer to your question — in which case Emil's comments are about as complete an answer as you are likely to get.


A $O(2^n/\log n)$-size depth-3 universal Boolean formula was constructed in

  O.B. Lupanov. Complexity of the universal parallel-series network of
  depth 3. Trudy Matem. Inst. Steklov, 133:127-131, 1973 (In Russian)

In this paper Lupanov uses language of parallel-series networks, which is equivalent to De Morgan formulas with unbounded fan-in AND, OR gates (parallel connection of two networks corresponds to disjunction and series connection corresponds to conjuction).


I believe there are two interpretations of your criterion.  One interpretation is easily solvable, and the other is NP-Complete.

First, a greedy algorithm for what you describe:
Let $A_1$, $A_2$, ..., $A_N$ all start as the empty set.
Loop through each $a_i \in A$.
Put $a_i$ in the first $A_k$ such that for each $a_j$ already in $A_k$,
$crit(a_i, a_j) = false$.
After looping through all the elements of $A$, disregard any $A_i$ which is still empty.

This greedy algorithm holds in the three examples you give.

A second interpretation is: "Let the set $A_i$ be as large as possible but not including any elements from $A_1$ to $A_{i-1}$".  Let $A'$ be an $N \times N$ matrix where $A_{i, j}'$ is 1 if $crit(a_i, a_j) = false$ and 0 otherwise.  Then finding $A_1$ is exactly finding the maximum clique of a digraph with adjacency matrix $A'$.  This, of course, makes the problem NP-Hard.

Let's hope you only need the first.


I don't know about a survey, but I've found a recent PhD thesis, which seems to be well written:
Heinlein, Matthias (2019): Erdős-Pósa properties. Open Access Repositorium der Universität Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-11828
The first chapter gives a summary of the problem, known proof techniques and provides references to recent research. I am not an expert on this problem and only skimmed the first chapter briefly, so YMMV.


I think it's just in the first inequality (the Kraft inequality): you sum over all the symbols $1/2^{\text{length of encoding}}$. There are 3 symbols of length $3$ bits and $d$ symbols of length $8$ bits, so that's how you get the first inequality. (Also, does your question have a typo? $a_4,a_5,\dots,a_{d+3}$ rather than $\dots,a_{d+1}$.) The $5/8$ comes from simplifying the inequality: you get $3/8 + d/256 \leq 1$, which is equivalent to $d/256 \leq 5/8$.


Is there any link between TCS and Sustainable Energy research?

Kirk Pruhs is a leader in the area of "green computing", the study of algorithms that treat energy as an expensive resource. Take a look at these slides and  this survey by Sandy Irani and Pruhs.


Finding a cell in an arrangement of simplices

If I am understanding your problem correctly, this is the problem of computing the face containing a given point in an arrangement of line segments. There is a randomized algorithm running in expected time $O(n\alpha(n)\log n)$, where $n$ is the number of line segments, and $\alpha(n)$ is the inverse Ackermann function. The algorithm computes the boundary of the face, and from that you can list the grid points if you want using a sweep algorithm, but the time to do that will of course depend on the number of grid points inside the face.


Construct proof systems for common algorithmic task, like equivalence of regular expressions

You have a non-deterministic algorithm deciding the problem.
If you want to think of it as a proof system for $EQUIV$, then
the proof of $(u,v) \in EQUIVE$ is just the string
representing the computation of your algorithm on $(u,v)$.
The proof checker just checks that
the given string is in fact an accepting computation of your algorithm on $(u,v)$.

Use the alternative definition of proof system, it is often easier to think about: an algorithm that gets a formula and a string and checks if the string of a proof of the formula, rather than a function that checks if a given string of is proof and if so outputs the proven formula.


Formalizing a notion of machine Intelligence

Let me give a partial answer from a learning theory perspective.  As your question isn't well specified, this answer won't be either.  In my answer, I'm assuming your question was inspired by your blog post, linked from your profile.

Say that you are thinking about programs that are just functions (so they have to halt, etc.).  You can ask whether certain classes of such functions can appear randomly by, perhaps, looking at the probability a random program (from some distribution that you think is likely) lands in that class or not, with the hope that probability is polynomially large.  I haven't really thought this argument through.

You can also ask whether such a class is efficiently evolvable according to Valiant's model of evolution (also in @Artem's pointer in comments): luckily what is efficiently evolvable is known to be the class learnable by correlational statistical queries; taking "crossover" into account, you get parallel correlational statistical queries. One thing to note is that just because evolvability is characterized, it is still a separate and sometimes difficult task to determine whether a particular class is evolvable (learnable with CSQs) or not.

If you find a class of "programs" that is neither randomly occurring nor evolvable, perhaps you can conclue it has a "creator/programmer," though that conclusion may still take a leap of faith.


A calculus is just a system of reasoning. One particular calculus (well, actually two closely related calculi: the differential calculus and the integral calculus) has become so widespread that it is just known as "calculus", as if it were the only one. But, as you have observed, there are other calculi, such as the lambda calculus, mu calculus, pi calculus, propositional calculus, predicate calculus, sequent calculus and Professor Calculus.


Face-splitting product of two Vandermonde matrices: When is is invertible?

Sorry if I am missing something, but isn't it always singular in your special case? The first column is identically $1$, the second column is $(\beta_1,\ldots,\beta_{n^2})^T$, and the $n+1$'th column is $(\alpha_1,\ldots,\alpha_{n^2})^T$. If $\beta_i=\alpha_i-1$ for all $1\leq i\leq n^2$, then the $n+1$'th column is a linear combination of the first and second columns, so it is singular, right?
EDIT: in response to the amended question in the comments, I think it becomes nonsingular if and only if the $\alpha_i$ are distinct (note that one direction is obvious; if $\alpha_i=\alpha_j$ for some $i\neq j$, then clearly there are two equal rows).
To see the other direction, suppose that the $\alpha_i$ are distinct, but the matrix is singular. This means the $n+1$'th column is a linear combination of the previous $n$ columns. Defining $f_i(x)=x^i(x-1)^{n-i}$ for $i=0,\ldots,n$, this means there exists $\lambda_0,\ldots,\lambda_{n-1}\in \mathbb{F}$ not all zero such that for all $i=1,\ldots,n+1$,
\begin{equation}
f_{n}(\alpha_i) = \sum_{j=0}^{n-1} \lambda_j f_j(\alpha_i);
\end{equation}
as this holds at $n+1$ distinct points, and both sides have degree $n$ in $x$, this means that $f_n = \sum_{j=0}^{n-1} \lambda_j f_j$ as formal polynomials, as well as functions (the injectivity of the map between polynomials of degree at most $n$ and functions, when the field has at least $n+1$ elements, is essentially the nonsingularity of the Vandermonde matrix in the first place).
To see that this is not possible, note that evaluating both sides at $x=0$ shows that $\lambda_0 = 0$, for all other terms vanish, so this coefficient must be zero because $f_0(0)\neq 0$. Because all remaining terms are now divisible by $x$, we may safely divide through and keep this linear relationship, and then apply the same argument to deduce that $\lambda_1=0$, and so on. But this implies $f_n$ is formally the zero polynomial, which clearly does not hold. Therefore, the matrix has full column-rank and so is invertible.


If you insist that the edges in the complex merge equation don't appear twice (eg. that the + you use is actually a disjunctive union), and you only subtract sets that are superset of one another (*), I think the assertion you want to prove (4) is actually false. Imagine RTG with 5 vertices and 6 edges:
V = { 0, a, b, c, d }
E = { (0,a), (0,b), (a,c), (a,d), (b,c), (b,d) }

now, if To = c and F = d: C(c) contains already all the edges except (b,d) and (c,d), So Sum (Fi-Bi) has to be exactly those edges. Since these edges are only contained in C(d), they must be (not necessarily both) contained in summand d-B for some B. But that is not possible, because whatever B we choose, we add also edges that are already in C(To).
(*) otherwise the assertion (2) is actually false: Result = To + (From - To) satisfies the simple merge equation for all From and To (even if it looks bizarre).
Long story short: You gave inadequate or incomplete definitions.

Q: Why do we have to state definitions rigorously if the proofs are usually trivial if the definitions are right?
A: The definitions are almost always wrong.


About generalized planar graphs and generalized outerplanar graphs

In the notation of Lee and Streinu (citation below) the second class you list are the (2,3)-sparse graphs. They give an algorithm to test whether a graph is (k,l)-sparse in polynomial time. However, the situation with planar graphs and $|E'|\le 3|V'|-6$ is a little more complicated, because that inequality is not true for all sets of vertices (if it were true, no two vertices could be connected by an edge, because $3\cdot 2-6=0$). So the class of (3,6)-sparse graphs (in their notation) consists only of empty graphs.  Probably their algorithms can be extended to graphs for which the inequality holds for all sets of more than two vertices.

Lee, Audrey; Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs", Discrete Mathematics 308 (8): 1425–1437, doi:10.1016/j.disc.2007.07.104, arxiv:math/0702129.


Best Sorting for unlimited integer range

Yes there is.

The best known deterministic algorithm in linear space runs in time within $O(n\lg\lg n)$ and was presented by Han in 2004.
The best known randomized algorithm in linear space runs in time within $O(n\sqrt{\lg\lg n})$ and was presented by Han and Thorup in 2012.

For more details, see the section on "Trans-dichotomous algorithms" from the wikipedia page for "Integer Sorting".


Is Hartmanis-Stearns conjecture settled by this article?

First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn".

Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in real time; in other words, the TM must compute the n'th digit in n time.

Third, the result of Adamczewski et al. is only about finite automata and deterministic pushdown automata, both of which are weaker models than real-time Turing machines.


Algorithm for ordering a list under a similarity function?

The variant of your problem where you DON'T square the distance is called the (weighted) Minimum Linear Arrangement problem. It's NP-hard and there are a number of different approximation methods for it. Here's one link that popped up that has code that you might find useful.

But fortunately for you, you squared the distance, which changes things quite a bit. Let's expand the expression:
$$
\begin{align*}
\sum_{a,b \in A} s(a,b) (i(a) - i(b))^2 &= \sum_{a,b \in A} s(a,b) (i^2(a) +i^2(b) - 2 i(a) i(b)) \\
&= \sum_a i^2(a) \sum_b s(a,b) + \sum_b i^2(b) s(a,b) - 2 \sum_{a,b} s(a,b)i(a)i(b) \\
&= 2 \sum_a S(a) i^2(a) - 2 \sum_{a,b} s(a,b)i(a)i(b) \\
&= 2 u^\top A u
\end{align*}
$$

where $u$ is the vector $i(a)$ and $A_{a,b} = -s(a,b), A(a,a) = \sum_b s(a,b)$.

All of this is a long-winded way of saying that you've essentially defined the Laplacian operator for the complete graph with weights given by your similarity function. At this point, minimizing the form is straightforward. You compute the decomposition of A in the form $A = V \Lambda V^T$, at which point your goal is to minimize the norm $\| u^T V \sqrt{\Lambda}\|$. But note that since $A$ is symmetric, $V$ is orthonormal, and is essentially a rotation matrix, and so what you really want to do is line up $u$ in reverse order of the eigenvalues of $A$ (the elements of $\Lambda$)


Help with the definition of clique percolation

Technically yes, the graph you describe is one 2-clique percolated community. However, this is a reduced case, since a 2-clique is no more than an edge, and so a 2-clique percolated community is just a connected component.

For k > 2, clique percolation results in communities that are only detectable using this method. The example in Wiki uses 4-cliques.


Is there such a thing as a weak coalgebra homomorphism?

The `weak morphisms' you describe do have a name in a slightly restricted setting. They can also be defined quite generally, as I'll explain.

In the case where $T : \mathsf{Set} \to \mathsf{Set}$ preserves weak pullbacks (many natural functors on $\mathsf{Set}$ do) it is known that behavioural equivalence coincides with coalgebraic bisimilarity. Then your morphisms are known as functional $\alpha$-step bisimulations where  $\alpha$ is an ordinal. Admittedly I've only ever seen them defined for ordinals $\alpha \leq \omega$. Prior to coalgebra, modal logicians had studied n-step bisimulations for Kripke frames, which amount to n-step bisimulations for coalgebras for the powerset functor. Your requirement that they be functions as opposed to relations makes them functional n-step bisimulations.

On the other hand, you can define the concept you are talking about in a far more general setting without referring to coalgebraic bisimulations. For any category $\mathbb{C}$ which has limits of ordinal-indexed cochains and any functor $T : \mathbb{C} \to \mathbb{C}$ one can define $T$ 's terminal sequence. The condition regarding limits is actually rather weak e.g. many categories (including $\mathsf{Set}$) are actually complete i.e. have all small limits. The terminal sequence is a diagram in $\mathbb{C}$ and looks like:

$1 \quad \xleftarrow{!_{T1}} \quad T1 \quad \xleftarrow{T !_{T1}} \quad T^2 1 \quad \xleftarrow{T^2 !_{T1}} \quad \dots \quad T^\omega 1  \quad \xleftarrow{f_\omega^{\omega + 1}} \quad T(T^\omega 1) \quad \xleftarrow{Tf_\omega^{\omega + 1}} \quad \dots$

Here $1$ is the terminal object in $\mathbb{C}$ (limit of empty cochain). For example in $\mathsf{Set}$ this can be taken to be the one element set $1 = \{*\}$. The map $!_{T1} : T1 \to 1$ is the unique morphism into the terminal object e.g. in $\mathsf{Set}$ is simply maps every element of $T1$ to $*$. Each $T^n 1$ is computed by iterating $T$ and $T^\omega 1$ is the limit of the cochain preceding it. One can then continue beyond $\omega$, if necessary. Intuitively $T^\alpha 1$ is the collection of  $\alpha$-step behaviours.

Now any $T$-coalgebra $(Z,\gamma)$ induces a cone over this sequence i.e.  a collection of $\mathbb{C}$-morphisms $\mathsf{beh}_\gamma^\alpha : Z \to T^\alpha 1$ for each ordinal $\alpha$. I'll just define them for $\alpha < \omega$:

$\mathsf{beh}_\gamma^0 : Z \to 1$ is the unique map into the terminal object.

$\mathsf{beh}_\gamma^{n+1} = T\mathsf{beh}_\gamma^n \circ \gamma : Z \to T^{n+1} 1$

Intuitively these maps send a state in $Z$ to its $\alpha$-step behaviour. Now we can describe what you are talking about. Suppose we have two $T$-coalgebras $(A,\gamma)$ and $(B,\delta)$. Then a $\mathbb{C}$-morphism $f : A \to B$ preserves $\alpha$-step behaviour iff:

$\mathsf{beh}_\delta^\alpha \circ f = \mathsf{beh}_\gamma^\alpha$

That is, the $\alpha$-step behaviour of $f(z)$ in $\delta$ is precisely the $\alpha$-step behaviour of $z$ in $\gamma$.

Anyway, I hope this is helpful. You can find various references by googling 'terminal sequence coalgebra' or 'final sequence coalgebra'.


Identifying useless edges for shortest path

If you are looking for a way to name (or alternately characterize) these edges you call "useless" and "necessary," you could refer to them as the edges with betweenness centrality =0 and =1, respectively. Every edge can be classified as having =0, =1 or in(0,1) betweenness measure in time of all-pairs-shortest-paths.

This is a well-studied measure of network edges, and there are fast algorithms for updating all the edges' centrality scores upon edge deletions (but I'm not sure about other perturbations).

A centrality function is built-in to mostly every network analysis I've seen, and there is a definition that applies to directed graphs as well:

(edit: the link I gave initially only discussed node betweenness centrality, but here is the only wikipedia article I can find that discusses edge-betweenness centrality:
http://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm
Still, edge-betweenness is a standard measure that can usually be found in network analysis packages.)


Asymptotic Approximation to Number of Knapsack Solutions

The answer is no, assuming we interpret Condition 2 as follows:

For every infinite sequence $X_1,X_2,\ldots$ with each $X_i$ in $[0,1]$,
$$\lim_{n \to \infty} \frac{F(X_1,...,X_n,Y, n)}{N(X_1,...,X_n,Y,n)} = 1.$$

Lemma 1. No function $F$ that satisfies the above condition is continuous (much less differentiable) in every $X_i$.

Proof. Fix any candidate function $F$ that is continuous in each $X_i$.  Fix $Y=1$. To complete the proof, we show there must be a sequence $X_1', X_2', \ldots$ such that
$$\lim\inf_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1,n)} = 0$$
or
$$\lim\sup_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1,n)} = \infty.$$

Start by fixing an arbitrarily large index $n_1$.  To ease notation, for $z\in[0,1]$, define
$$\begin{align}
 F_1(z) &{} = F(z, z, \ldots, z, 1, n_1), \text{ and } \\
 N_1(z) & {}= N(z, z, \ldots, z, 1, n_1).
\end{align}$$
(That is, the restrictions of $F$ and $N$ to $X_1=X_2=\cdots=X_{n_1}=z$, $Y=1$, and $n=n_1$.)

Fix $\epsilon_1>0$ such that
$$F_1(1/2) - F_1(1/2+\epsilon_1) \le 1/2^{n_1}.$$
(This is possible because $F_1$ is continuous, as $F$ is continuous in each $X_i$.)

Meanwhile, by inspection
$$
\begin{aligned}
N_1(1/2+\epsilon_1) &{} = (1 + n_1)/2^{n_1} &&{} = \Theta(n_1/2^{n_1}), & \text{ while} \\
N_1(1/2) &{} = \Big(1 + n_1 + {n_1 \choose 2}\Big)/2^{n_1} &&{} = \Theta(n_1^2/2^{n_1}).
\end{aligned}
$$

Case 1.1. First consider the case that $F_1(1/2+\epsilon_1) \le n_1^{3/2}/2^{n_1}$.

In this case, define $X'_1 = X'_2 = \cdots = X'_{n_1} = 1/2$.
Then
$$\frac{F(X'_1, \ldots, X'_{n_1}, 1, n_1)}{N(X'_1,\ldots, X'_{n_1}, 1, n_1)} =
\frac{F_1(1/2)}{N_1(1/2)}
\le
\frac{F_1(1/2+\epsilon_1)+1/2^{n_1}}{N_1(1/2)}
= O(1/\sqrt{n_1}).$$

Case 1.2. Otherwise $F_1(1/2+\epsilon_1) > n_1^{3/2}/2^{n_1}$.

In this case, define $X'_1 = X'_2 = \cdots = X'_{n_1} = 1/2 + \epsilon_1$.
Then $$\frac{F(X'_1, \ldots, X'_{n_1}, 1, n_1)}{N(X'_1,\ldots, X'_{n_1}, 1, n_1)} = \frac{F_1(1/2+\epsilon_1)}{N_1(1/2+\epsilon_1)} = \Omega(\sqrt{n_1}).$$

So, at index $n=n_1$, the ratio in question is either $O(1/\sqrt n)$ or $\Omega(\sqrt n)$.

To continue, choose index $n_2 \ge n_1^2$,
and set the values of $X'_{n_1+1}, X'_{n_1+2}, \ldots, X'_{n_2}$ as follows. Define
$$\begin{align}
 F_2(z) &{} = F(X'_1, X'_2, \ldots, X'_{n_1}, z, z, \ldots, z, 1, n_2), \text{ and } \\
 N_2(z) & {}= N(X'_1, X'_2, \ldots, X'_{n_1}, z, z, \ldots, z, 1, n_2).
\end{align}$$
(Above, $z$ occurs $n_2-n_1$ times in each parameter list.)
Fix $\epsilon_2>0$ such that
$$F_2(1/2) - F_2(1/2+\epsilon_2) \le 1/2^{n_2}.$$
(This is possible because $F_2$ is continuous, as $F$ is continuous in each $X_i$.)

By inspection, using that $n_2 \ge n_1^2$,
$$
\begin{aligned}
N_2(1/2+\epsilon_2) &{} = O((n_1^2 + n_2)/2^{n_2}) &&{} = O(n_2/2^{n_2}), & \text{ while} \\
N_2(1/2) &{} \ge {n_2 \choose 2}/2^{n_2} &&{} = \Theta(n_2^2/2^{n_2}).
\end{aligned}
$$

Case 2.1. First consider the case that $F_2(1/2+\epsilon_2) \le n_2^{3/2}/2^{n_2}$.

In this case, define $X'_{n_1+1} = X'_{n_1+2} = \cdots = X'_{n_2} = 1/2$.
Then
$$\frac{F(X'_1, \ldots, X'_{n_2}, 1, n_2)}{N(X'_1,\ldots, X'_{n_2}, 1, n_2)} =
\frac{F_2(1/2)}{F_1(1/2)}
\le
\frac{F_2(1/2+\epsilon_2)+1/2^{n_2}}{N_2(1/2)}
= O(1/\sqrt {n_2}).$$

Case 2.2. Otherwise $F_2(1/2+\epsilon_2) > n_2^{3/2}$.

In this case, define $X'_{n_1+1} = X'_{n_1+2} = \cdots = X'_{n_2} = 1/2 + \epsilon_2$.
Then $$\frac{F(X'_1, \ldots, X'_{n_2}, 1, n_2)}{N(X'_1,\ldots, X'_{n_2}, 1, n_2)} = \frac{F_2(1/2+\epsilon_2)}{N_2(1/2+\epsilon_2)} = \Omega(\sqrt{n_2}).$$

So, at index $n=n_2$, the ratio in question is either $O(1/\sqrt n)$ or $\Omega(\sqrt n)$.

Continuing in this way, we can set $X'_1, X'_2, \ldots$ so that there is an infinite sequence of indices $1\le n_1 < n_2 < n_3 < \cdots$
such that, at each index $n=n_i$, the ratio in question is either $O(1/\sqrt n)$ or $\Omega(\sqrt n)$.

Then either there are infinitely many indices $n$ such that the ratio is $O(1/\sqrt n)$, in which case
$$\lim\inf_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1, n)} = 0,$$
or there are infinitely many indices $n$ such that the ratio is $\Omega(\sqrt n)$, in which case
$$\lim\sup_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1, n)} = \infty.$$
$~\Box$


Does NP-completeness/hardness have to be constructive?

Yes, there are such sets, take any $\mathsf{NP}$-intermediate set (any set that is provably $\mathsf{NP}$-intermediate assuming $\mathsf{P}\neq\mathsf{NP}$), e.g. construct one from SAT using Ladner's theorem.

Note that your $L$ needs to considered an $\mathsf{NP}$-intermediate problem, since it is in $\mathsf{NP}$ but not complete for it. Note also that you are assuming that $\mathsf{P}\neq\mathsf{NP}$ otherwise there is no such $L$ as every non-trivial problem would be complete for $\mathsf{NP}$ if $\mathsf{NP}=\mathsf{P}$. Additionally the conditions that you have given does not imply to completeness so the question in the first part is not the same as the question about constructiveness of completeness.

Regarding the question in the title, i.e. "does $\mathsf{NP}$-hardness have to be constructive?".

The answer depends on what we mean by "constructive". Classically, a decision problem $A$ is defined to be $\mathsf{NP}$-hard iff

$$\forall B\in \mathsf{NP} \ B \leq^\mathsf{P}_m A$$

which means

$$\forall B\in \mathsf{NP} \ \exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in B \leftrightarrow f(x)\in A)$$

And by Cook's theorem this is equivalent to

$$ SAT \leq^\mathsf{P}_m A$$

which means

$$\exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in SAT \leftrightarrow f(x)\in A)$$

How can we make this definition constructive? It is already seems very constructive to me.
I guess what you want to ask is if we can prove this for some $A$ without knowing what is $f$ explicitly. I don't remember seeing any such hardness proof.

Classically even when we don't have a specific function there is a function, saying that it is impossible that no function is a reduction is equivalent to saying that some function is a reduction. To talk about constructiveness we need to be more considerate. For example we can talk about statements which are provable classically but not constructively (e.g. intuitionism where different state of mathematical knowledge makes sense, Google for "ideal mathematician" or check this).

Intuitively it seems plausible to me that we can prove such a statement using a proof by contradiction and without giving any explicit reduction function. But it won't mean that there is no constructive proof of the statement. To be say more that no constructive proof exists we have to be more specific: proofs in which theory/system? what do we mean by a constructive proof?


What is the asymptotically fastest known algorithm for computing the nullspace of a matrix?

The exponent of computing a basis of the kernel is the same
as the exponent of matrix multiplication, see the
book Algebraic Complexity Theory by Bürgisser, Clausen & Shokrollahi.
So it can be done in time $O(n^{2.38})$.


Do such instances always admit a 3D matching?


Breaking encrypted file store with a file?

This is called the known-plaintext attack. Any cipher algorithm which is prone to this type of attack is considered very weak. Therefore, AFAIK, no present-day cipher (e.g. AES) has this weakness. Even DES needs 243 known plaintexts to be broken under linear cryptanalysis. (see this topic  on Wikipedia).

On the other hand, all hope is not lost. Weak ciphers or bad implementation of strong ciphers are still commonplace. One noticeable case is with the (old) implementations of ZIP. More info is available here:

http://www.elcomsoft.com/help/archpr/index.html?known_plaintext_attack_(zip).html


Mathematical implications of complexity theory conjectures outside TCS

Here's another example from graph theory. The graph minor theorem tells us that, for every class $\mathcal{G}$ of undirected graphs that is closed under minors, there is a finite obstruction set $\mathcal{Obs(G)}$ such that a graph is in $\mathcal{G}$ if and only if it does not contain a graph in $\mathcal{Obs(G)}$ as a minor. However, the graph minor theorem is inherently nonconstructive and does not tell us anything about how big these obstruction sets are, i.e., how many graphs it contains for a particular choice of $\mathcal{G}$.

In Too Many Minor Order Obstructions, Michael J. Dinneen showed that under a plausible complexity-theoretic conjecture, the sizes of several of such obstruction sets can be shown to be large. For example, consider the parameterized class $\mathcal{G}_k$ of graphs of genus at most $k$. As $k$ increases, we can expect the obstruction sets $\mathcal{Obs}(\mathcal{G}_k)$ to become more and more complicated, but how much so? Dinneen showed that if the polynomial hierarchy does not collapse to its third level then there is no polynomial $p$ such that the number of obstructions in $\mathcal{Obs}(\mathcal{G}_k)$ is bounded by $p(k)$. Since the number of minor obstructions for having genus zero (i.e. being planar) is just two ($\mathcal{Obs}(\mathcal{G}_0) = \{K_5, K_{3,3}\}$), this superpolynomial growth is not immediately obvious (although I believe it can be proven unconditionally). The nice thing about Dinneen's result is that it applies to the sizes of obstruction sets corresponding to any parameterized set of minor ideals $\mathcal{G}_k$ for which deciding the smallest $k$ for which $G \in \mathcal{G}_k$ is NP-hard; in all of such parameterized minor ideals the obstruction set sizes must grow superpolynomially.


Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$?

If your statement holds, then the polynomial hierarchy collapses: $\mathsf{\# P} \subseteq \mathsf{FP}^{\mathsf{PH}}$ iff $\mathsf{\# P} \subseteq \mathsf{FP}^{\mathsf{\Sigma_k P}}$ for some fixed $k$ (by definition). But then by Toda's Theorem we have $\mathsf{PH} \subseteq \mathsf{P}^{\mathsf{\# P}} \subseteq \mathsf{P}^{\mathsf{FP}^{\mathsf{\Sigma_k P}}} = \mathsf{P}^{\mathsf{\Sigma_k P}} = \mathsf{\Delta_{k+1} P}$.


Finding appropriate spanning tree of connected bipartite graph

Isn't this a special case of matroid intersection,
which is solvable in polynomial time?

Fix your graph $G$ and any integer $d \in \{0,1,\ldots,\max_i a_i\}$.
You want to maximize $d$; you can try all possibilities.
For a given $d$, you want to answer the following question:

  Is there is a spanning tree $T$ such that $\max_i a_i - \mbox{deg}_T(u_i) \le d$?

Since any spanning tree has $n-1$ edges, the following question is equivalent:

  Is there an edge-set $S$ of size at least $|E|-n+1$, with at most $d$ edges incident to each vertex in $U$, whose complement contains a spanning tree?

Thus, your problem reduces to the following problem:

  Find a maximum-size edge-set $S$ having at most $d$ edges incident to each vertex in $U$ and whose complement contains a spanning tree.

The independent sets of edges in $G$ form a matroid.  The bases are the spanning trees.  The dual of this matroid is a matroid $M_t^*$.  The edge-sets in $M_t^*$ are the edge-sets whose complement contains a spanning tree.

The edge-sets in which each vertex $u_i$ in $U$ has degree at most $d$ form yet another matroid $M_d$.

Thus, the following two conditions on edge-set $S$ are equivalent:

$S$ is in the intersection $M_d \cap M_t^*$ of the two matroids;
$S$ has at most $d$ edges incident to each vertex in $U$, and the complement of $S$ contains a spanning tree.

So the following algorithm solves the problem in polynomial time:

  Using matroid intersection, find a maximum-size edge-set $S$ in $M_d \cap M^*_t$.


Break text evenly into certain number of lines

If you can compute the raggedness of a line without knowing anything about the other lines, then you can model the problem as finding a minimum-weight $M$-link path in a graph. With concave integer weights for edges, there is an algorithm that solves the problem in $O(N \log U)$ time, where $U$ is the largest absolute edge weight. Another algorithm solves the problem in $N 2^{O(\sqrt{\log M \log \log N})}$ time for any concave edge weights, assuming $M = \Omega(\log N)$. Both algorithms assume that you can compute the weight of an edge in constant time.

You could also use binary search to find a line width such that SMAWK uses $M$ lines with it. In some cases, this algorithm does not guarantee a solution with exactly $M$ lines, however.


The subtlety comes in where we introduce the notion of "harder". The reduction showing that SAT can be reduced to Hamiltonian Cycle shows that the latter is "harder" up to polynomial factors. In doing the reduction, we may very well increase the variable $n$ in question substantially (by some polynomial). And the canonical reductions do blow it up quite substantially.

So what's the upshot? Suppose that the reduction from a SAT instance with $t$ variables yields a HamCycle instance with $n = p(t)$ vertices for some polynomial $p$. Running some $O(2^{\epsilon n})$ time algorithm on this HamCycle instance takes time $O(2^{\epsilon p(t)})$. If $p(t) \ll t/\epsilon$, you just broke SETH. But in general, $p$ may be larger than that (often not even linear), in which case your reduction takes longer than the naive brute force approach.

Some recent papers actually work asking the same line of reasoning that you do to establish SETH hardness. For example, consider the graph diameter problem, where we are asked to determine how far apart the two furthest nodes on a graph lie (that is, we're asked to compute the maximum over all (u,v) pairs the length of the shortest path between u and v). Roditty and Williams showed that even in the unweighted case, where all edge lengths are 1, the problem is difficult to solve in time $O(n^{1+\epsilon})$ (using your notation with $\epsilon<1$). The way they do this, roughly, is by finding an exponential-time reduction from SAT to GraphDiameter that blows up the number of vertices from $t$ to $O(2^{t/2})$. In this new giant instance, the diameter is 3 if the instance is satisfiable, 2 if not. Thus, if they can solve GraphDiameter in time $O(n^{1+\epsilon})$ (and if the original exponential time reduction is fast enough, which it is), then they can solve SAT with $t$ variables in time $O((2^{t/2})^{1+\epsilon}) = O(2^{\frac{1+\epsilon}{2}t}) = O(2^{\epsilon't})$ for $\epsilon'<1$, breaking SETH. In reality, their reduction works through dominating set first, but the key ideas remain the same.


Lower bound on the support size of an $\epsilon$-biased distribution

You shouldn't have a square root. Namely, for every $\delta$-biased distribution $Z$ (using your notation), we have
$$
\delta^2+2^{-n} \geq \lVert Z\rVert^2_2 \geq \frac{1}{\lvert\operatorname{supp} Z\rvert}\tag{1}
$$
since the squared $\ell_2$ norm of a distribution over support of size $N$ is at least that of the uniform distribution on $N$ elements, which is $1/N$.
This gives you, for $t\geq 1$ to choose suitably,
$$\lvert\operatorname{supp} D^{(t)}\rvert \geq \frac{1}{\varepsilon^{2t}+2^{-n}} \tag{2}
$$
since as you have shown $D^{(t)}$ is $\delta$-biased for $\delta=\varepsilon^t$. A natural choice of $t$, in view of (2), is the one balancing the denominator, i.e., such that $\varepsilon^{2t}=2^{-n}$. This leads to taking
$$
t \stackrel{\rm def}{=} \frac{n}{2\log(1/\varepsilon)}\tag{3}
$$
Recalling the standard bound $\binom{n}{k}\leq \left(\frac{en}{k}\right)^k$ for $1\leq k\leq n$ along with (2), (3), and what you mentioned as 2. in your question, we thus get
$$
\left(\frac{e(\lvert\operatorname{supp} D \rvert+t)}{t}\right)^t \geq \binom{\lvert\operatorname{supp} D \rvert+t}{t} \geq \frac{1}{\varepsilon^{2t}+2^{-n}} = \frac{1}{2\varepsilon^{2t}} \tag{4}
$$
so that
$$
 \frac{e(\lvert\operatorname{supp} D \rvert+t)}{t} \geq \frac{1}{2^{1/t}\varepsilon^{2}} \tag{5}
$$

Rearranging and recalling again the choice of $t$ in (3) yields
$$
 \lvert\operatorname{supp} D \rvert\geq  \Omega\!\left(\frac{n}{\varepsilon^{2}\log(1/\varepsilon)} \right) \tag{6}
$$
as claimed.


Lower bound on alternations needed in $BQP$ versus $PH$ result?

If you just want oracle separations with $\#P$, you don't need to use the new result of Raz and Tal. You can use the classic Parity/Majority not in $AC^0$ results from the 1980s.

For example, the strongest quantitative version of Parity not in $AC^0$ says that the $n$-bit Parity function cannot be computed by a quasi-polynomial size $AC^0$ circuit of depth $o(\log n/ \log\log n)$. So scaling this up, we get an oracle separation between $\oplus P$, which is in $\# P$, and $PH$ with $o(n/\log n)$ quantifiers.


Smallest Boolean circuit to generate a language

I will point out a simple connection to nondeterministic circuits, and comment briefly on cryptographic hardness.

For $S \subseteq \{0, 1\}^n$, define the image complexity, denoted $imc(S)$, as the minimal number of gates in any (fanin-two, AND/OR/NOT) Boolean circuit $C: \{0, 1\}^m \rightarrow \{0, 1\}^n$ whose image is $S$.  The question asks about the complexity of computing $imc(S)$, given a truth-table representation of $S$ (a string of length $2^n$).

Also define the nondeterministic circuit complexity of $S$, which we'll denote $ncc(S)$, as the smallest nondeterministic circuit $C(x, y): \{0, 1\}^{n + m'} \rightarrow \{0, 1\}$ accepting exactly $S$.  That is, we require of $C$ that $x \in S$ iff $\exists y: C(x, y) = 1$.  This is a standard notion, used to define the non-uniform class $NP/poly$: it is the class of all sets $S = \{S_n\}_{n > 0}$, with $S_n \subseteq \{0, 1\}^n$, such that $ncc(S_n) \leq poly(n)$.

What I wanted to point out is that $imc(S) = ncc(S) \pm O(n)$.  Both directions of this inequality are simple to verify.

Let $dcc(S)$ denote the deterministic circuit complexity.  Using Razborov-Rudich, the paper that Dai Le mentions shows (roughly speaking here) that under certain cryptographic assumptions, it is computationally hard to distinguish truth-tables of $S$ with $dcc(S)$ small, from truth-tables of truly random $S$ (with $dcc(S)$ near-maximal).  Random $S$ also have $ncc(S)$ nearly-maximal, and we of course have $ncc(f) \leq dcc(f)$. So your problem is hard under the same assumptions.

Which is harder to compute given a truth-table for $S$, $dcc(S)$ or $ncc(S)$?  Is there a reduction either way?  I don't know.


I tried to address the questions you raise in "Five stages of accepting constructive mathematics".
And here are some textbooks:

Constructive analysis by D. Bridges and E. Bishop is the "bible" of constructive mathematics.
Varieties of constructive mathematics by D. Bridges and F. Richman considers several varieties of constructive mathematics, and discusses some of the pathologies and niceties that they possess.
Constructivism in mathematics (volumes 1 and 2) by D. van Dalen and A. Troelstra provides an in-depth treatment of constructive mathematics.


Generalizations of Brzozowski's method of derivatives of regular expressions to grammars?

You might be interested in this paper:

  Yacc is Dead by Matthew Might and David Darais, 2010

  We present two novel approaches to
  parsing context-free languages. The
  first approach is based on an
  extension of Brzozowski's derivative
  from regular expressions to
  context-free grammars. The second
  approach is based on a generalization
  of the derivative to parser
  combinators. The payoff of these
  techniques is a small (less than 250
  lines of code), easy-to-implement
  parsing library capable of parsing
  arbitrary context-free grammars into
  lazy parse forests. Implementations
  for both Scala and Haskell are
  provided. Preliminary experiments with
  S-Expressions parsed millions of
  tokens per second, which suggests this
  technique is efficient enough for use
  in practice.

Also of potential interest:

Yacc is Not Dead, review of this paper by Russ Cox, of re2 fame.
Yacc is dead: An update, reply from Matt Might.
Functional Pearl: Parsing with Derivatives by Matthew Might, David Darais and Daniel Spiewak - an updated version of the "Yacc is Dead" paper, presented at ICFP 2011 in Tokyo.


Is counting the words in a finite regular language #P-complete?

See this paper:
Counting the size of regular sequences of given length is #P-complete:
S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting
and random generation of strings in regular languages.
In ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 551–557, 1995.


Theories which characterize classes of computational complexity

I think the first approach, the bounded arithmetic approach, is the most popular and well-studied approach. The name bounded arithmetic indicates the use of weak subsystems of Peano arithmetics, where  induction is restricted to formulas with bounded quantifiers.  I already summarized the main idea behind this approach in this post. An excellent recent reference on bounded arithmetic is the book by Cook and Nguyen, whose draft is freely available.

The second approach uses linear logic and its subsystem as mentioned by Kaveh, which I don't know much about.

I haven't heard of the third approach although I'm working on bounded arithmetic. But it sounds a bit strange to me since without some form of syntactic or logical restriction, how does then a theory characterize a complexity class?


How efficient are DPLL-based SAT-solvers on satisfiable instances of PHP?

On satisfiable instances of $PHP$, DPLL based SAT solvers will furnish a satisfying assignment in linear time.

To see why, observe how the CNF encoding of an unsatisfiable instance of $PHP$ with $n$ holes and $n + 1$ pigeons is sintactically identical to an instance of $k = n$ Graph Coloring, where the input graph is a clique of $n + 1$ vertices.

Similarly, the CNF encoding of a satisfiable instance of $PHP$ with $n$ holes and $n$ pigeons is sintactically identical to an instance of $k = n$ Graph Coloring, where the input graph is a clique of $n$ vertices.

Now, coloring a clique of $n$ vertices with $n$ colors is straightforward: scan the vertices, and assign to each of them one of the remaining colors (already assigned colors are automatically ruled out by the clique-ness of the graph, using unit propagation). Whatever of the remaining colors you choose, it will be good and will lead you to a satisfying assignment.

From the DPLL solver point of view: each time it will try to guess the boolean value of a variable $v_i$, such value will be right (whatever it is), because there will certainly be a satisfying assignment in which variable $v_i$ has the guessed value. Unit propagation will do the rest of the job, by guiding the solver along the satisfying path (in other words: by preventing it to guess wrong values).

The search then proceeds one variable after the other, linearly, each time making the correct guess.


How to understand the "Availability" of the CAP theorem?

Your question is mixing two somewhat orthogonal interpretations of the term "Availability".

The "reliability theory"/"engineering" interpretation, where availability is basically
the ratio of time the system is not failed.

The "distributed computing" interpretation, which is centered around the idea that

"every request received by a non-failing node in the system must result in a response"

So, let's consider a system of two nodes, that crash at midnight, and are resume operation at noon, every day.
So in the first interpretation we have 50% availability, that is, no nines at all. However, the system can still fulfill the second interpretation.


Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G

If H is the cycle on |G| vertices (and is of maximum degree 2), then this is the Hamiltonian cycle problem. Seems like your problem is NP-hard.


For part (1), if you allow additional restrictions on your graph class, then independent set, Hamiltonian circuit, dominating set, etc., are NP-hard on arbitrary planar graphs but FPT on planar graphs of bounded diameter (because in planar graphs a bound on diameter implies a bound on treewidth). You can turn this into an artificial problem that is NP-hard on arbitrary graphs but FPT on arbitrary graphs of bounded diameter e.g. by asking whether the graph has either a Hamiltonian cycle or a Kuratowski subgraph.

For part (2), dominating set clearly is polynomial in graphs of diameter 1 (just pick a vertex within distance one from everything as your dominating set) but hard for graphs of diameter 2. To reduce from dominating set in arbitrary graphs to graphs of diameter 2, start with an arbitrary hard instance $G$ of dominating set with $n$ vertices $v_i$. Add $n$ more vertices $u_i$, and an additional new vertex $c$, with each $u_i$ adjacent to $v_i$ and to $c$. Call the resulting diameter-2 graph $G'$. Then $G'$ has dominating sets formed by adding $c$ to any dominating set of $G$. However, the dominating sets of $G'$ that avoid $c$ must have size at least $n$ because they include at least one vertex from each $u_i$–$v_i$ pair.


A bicartesian closed category of strict complete partial orders (Hask)

Yes, it's impossible to have a nondegenerate CCC with general recursion and categorical coproducts. The standard reference for this is:

  H. Huwig and A. Poigne. A note on inconsistencies caused by fixpoints  in a cartesian closed category. Theoretical Computer Science, 73:101–112, 1990.

However, I and (most of the other people I've met) learned about it from Achim Jung and Samson Abramsky's handbook chapter Domain Theory, which they have kindly made available for free.

Most of the categories of domains that people work with are subcategories of DCPO, the category of predomains and continuous functions on them. Since predomains do not necessarily have a least fixed point, this category is a bi-CCC, but fixed points only exist for functions into domains.

On page 46 of these notes, there is a big table telling you which subcategory of DCPO different constructions exist in.


Best bounds for the longest path optimization problem in cubic Hamiltonian graph?

Check out
"Finding long paths and cycles in sparse Hamiltonian graphs"
by Feder, Motwani, and Subi from STOC 2000. AFAIK, this is the best algorithm known to date.


The short answer is "to verify additional properties of existing code".  Longer answer follows.

I am not sure "implicit" vs "explicit" is good terminology.  This distinction is sometimes called "structural" vs "nominal" subtyping.  Then there is also a second distinction in the possible interpretations of structural subtyping (described shortly).  Note that all three interpretations of subtyping really are orthogonal, and so it doesn't really make sense to compare them against each other, rather than understanding the uses of each.

The main operational distinction in interpreting a structural subtyping relation A <: B is whether it is witnessed by a real coercion with (runtime/compiletime) computational content, or whether it can be witnessed by the identity coercion.  If the former, the important theoretical property that has to hold is "coherence", i.e., if there are multiple ways to show that A is a substructural subtype of B, each of the accompanying coercions have to have the same computational content.

The link you gave seems to have the second interpretation of structural subtyping in mind, where A <: B can be witnessed by the identity coercion.  This is sometimes called a "subset interpretation" of subtyping, taking the naive view that a type represents a set of values, and so A <: B just in case every value of type A is also a value of type B.  It is also sometimes called "refinement typing", and a good paper to read for the original motivation is Freeman & Pfenning's Refinement types for ML.  For a more recent incarnation in F#, you can read Bengston et al, Refinement types for secure implementations.  The basic idea is to take an existing programming language that may (or may not) already have types but in which types do not guarantee all that much (e.g., only memory safety), and consider a second layer of types selecting subsets of programs with additional, more precise properties.

(Now, I would argue that the mathematical theory behind this interpretation of subtyping is still not as well understood as it should be, and perhaps that is because its uses are not as widely appreciated as they should be.  One problem is that the "set of values" interpretation of types is too naive, and so sometimes it is abandoned rather than refined.  For another argument that this interpretation of subtyping deserves more mathematical attention, read the introduction to Paul Taylor's Subspaces in Abstract Stone Duality.)