Lack of atomic propositions in the Calculus of Constructions from ATTAPL textbook

I have no thoughts on whether this is on-topic for TCS and if need be I can repost my answer elsewhere. But I think the question is a good opportunity to demonstrate how to think about the CoC pending some consensus to move it.

The rule BETA-ALL, which says we can beta-reduce terms underneath the all binder (but not the type of the argument), is not part of the typing or equivalence rules of $\mathsf{CC}$. Pierce is extending his definition of $\beta$-reduction first seen in Section 2.3 (section "Strong Normalization"), which itself is defined "As an auxiliary device for the soundness and completeness of algorithmic typechecking." Specifically the fact that this reduction is strongly normalizing can be used to show that typechecking halts.
Pierce mentions on page 51 that "We may use type and term variables declared in a fixed initial context to simulate the built-in types and operators of a programming language."

Also see Figure 2-1 (First-order dependent types), in which one of the context formation rules (labelled "term variable binding") is that if $\Gamma$ is a well-formed context and $T$ is a well-formed type, we can pick a variable name $x$ and and then $\Gamma, x :: T$ is a well-formed context. (It seems to be implicit that $x$ should be a fresh name, i.e. does not conflict with the rest of $\Gamma$, and that $T$ is well-formed in context $\Gamma$.).

Now combine this with rule of Figure 2-7 which states that $T ::= \ldots \mathsf{Prop}\ldots$, meaning $\mathsf{Prop}$ is a type. Therefore we can add $\mathsf{True} :: \mathsf{Prop}$ to the context. Likewise with $\mathsf{False}$.

To add a proof of $\mathsf{True}$, use rule K-App to deduce that $\mathsf{Prf} \:\mathsf{True}$ has kind $\ast$, i.e. is a type, and apply term variable binding again to add some proof $\mathsf{Unit} :: \mathsf{Prf} \,\mathsf{True}$ to the context.
When introducing $\mathsf{Prop}$, we also introduce this new binder called forall, which seems reasonable. Now we have to give this a semantics---how do we prove some forall x, P? The rule merely states that a proof of forall x, P is the same thing as offering "a proof of $P$ for every $x$" where the latter is defined as a dependent product (something our system already had). In a sense, the rules just say "by using the operator $\mathsf{Prf}$, $\mathsf{Prop}$ acts like $\ast$."

Perhaps you're wondering why this is interesting. We know that a proposition $p:\mathsf{Prop}$ can be coerced to a type $\mathsf{Prf} p : \ast$, and the equivalence says the binder forall acts like a dependent product, so what is gained?. But notice that by using T-ALL and QT-ALL, $\mathsf{Prop}$ can effectively play the role of $T$ when forming the dependent product, so we can quantify over $\mathsf{Prop}$ and still have a $\mathsf{Prop}$. This is the "impredicativity"  Pierce refers to, and it makes the system drastically more expressive. If we tried to get rid of the coercion just take $\mathsf{Prop} \equiv \ast$, we would have $\ast : \ast$, which is known to be inconsistent by a theorem of Girard.
To exhibit a natural number per Pierce's definition, you must be able to satisfy this criterion: If I give you any type $a$, term $z : a$, and successor function $s : a \to a$, you must be able to offer me some term of type $a$. Since you don't know the type $a$ in advance, the only thing you can do is apply $s$ to $z$ some number of times, and that is effectively the same thing as having a natural number. Pierce is showing that $\mathsf{CC}$ is expressive enough to type Church's encoding of the natural numbers , which is good because that encoding becomes impossible when you move from untyped lambda calculus to STLC. See these course notes. See also the Wikipedia page on System F for more information---System F is less expressive than $\mathsf{CC}$ but still good enough to play this game.


Doubt in John Langford's "Tutorial on Practical Prediction Theory for Classiﬁcation" paper

I think this is a typo.

In the Definition 2.1 and Definition 2.2, the estimation of $c_D$ is done by empirical summation of $\mathbf{1}(c(x_i) = y_i)$.

Later in the Definition 3.1 it used the following notation :
$$
... = \Pr_{...} \left( \sum_i Z_i < k \right) = ...
$$
In this notation $Z_i=1$ corresponds to correct decisions or $c(x_i) = y_i$, and $Z_i=0$ corresponds to the mistakes or $c(x_i) \neq y_i$. I suppose that in this binomial representation $Z_i = 1$ (correct decision) corresponds to heads" (And similarly $Z_i = 0$ (wrong decision) corresponds totail").

That said, the right sentence seems to be "... having k or less errors is at least $\delta$"


I would suggest using some Graph database like neo4j and have a look into the paper running large graph algorithms


A decision variant, without the minimality condition, asking whether there is a set $B$ of size $n$ is called the set basis problem [SP7] in Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson. The NP-completeness of it was proved by Stockmeyer.


Information complexity of query algorithms?

Yes, information theory is useful for proving lower bounds on the query complexity of problems in Computer Science.

Alexander Golynski gave a good example in his ground breaking paper titled "Cell probe lower bounds for succinct data structures", presented at SODA 2009. He uses information theory to prove a lower bound on query complexity, which in turns yields a lower bound in the bit-probe model for (succinct) data structures. You can download the paper from citeseer's cache or from ACM's repository. There does not seem to be a journal version of the article.

You might be interested also in the following articles from his bibliography, which also relate communication complexity with information theory:

Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and
Avi Wigderson. On data structures and asymmetric
communication complexity. Journal of Computer and
System Sciences, 57(1):37–49, 1998. [link]
Anna Gal and Peter Bro Miltersen. The cell probe
complexity of succinct data structures. In International
Colloquium on Automata, Languages and Programming,
pages 332–344, 2003. [link]


What is the grammar of network protocols and file formats?

There is an international agreed notation for describing protocols and format specifications
(well actually there are several), which is ASN.1. It is a form of Context_free grammar notation.

I used to teach formal notations for networking at one time, but these things have dropped out of the curriculum in favour of security ; which is interesting when a better understanding of the formalism might help enhance security.

It is possible to generate code for handling protocols; and some is done that way. Using state machines for the protocol and notations like ASN.1 for the packet descriptions much can be automated, and has been in the past.


What is the categorical semantics of subtyping?

Semantically, a coercion $c : A \leq B$ is just a morphism $c : A \to B$, which gets added to the interpretation of terms at the appropriate points. The  basic problem this creates is the issue of coherence: are you guaranteed that a term will have a unique meaning, given that the same term can potentially have coercions hidden in many possible places in the program?

One of the first treatments of this issue was John Reynolds' 1980 paper, Using Category Theory to Design Implicit Conversions and Generic Operators, which shows how you can give a categorical semantics to a system of coercions and use it to ensure that it is coherent.

If you're interested in coercive subtyping for rich (e.g., dependent) type theories, then Zhaohui Luo is the go-to guy.


You haven't specified exactly what kind of circuits, but in general since parity $\oplus$ is in $\mathsf{TC^0}$ and majority $Maj$ is complete for $\mathsf{TC^0}$, you get a similar subexponential size lower-bound for majority.

A simple reduction would go through counting function $NumOnes$ that counts the number 1s in the input in binary. This would give $2^{n^{\Omega(1/d)}}$ where constant in the exponent comes from the size of $\mathsf{AC^0}[Maj]$ circuit computing $numones$. I don't know the best value of the constant but it shouldn't be big.

On the other hand, there are $2^{n^{O(1/d)}}$ circuits for majority as majority is in $\mathsf{NC^1}$ and any $\mathsf{NC^1}$ circuits can be converted into a subexponential-size bounded-depth $\mathsf{AC^0}$ circuit (by performing a layered brute-force).


I think that Robertson and Seymour showed that every minor-free graph can be decomposed into a "clique-sum" of "almost bounded genus" graphs. The basic building blocks are not planar graphs but graphs of bounded genus (genus depending on the excluded minor). I think that toroidal graphs are not decomposable any further.


There is a simple construction: Take any $d$-regular non-bipartite expander $G=(V,E)$ - there are several constructions of those, e.g., Margulis, or the Zig-Zag construction. Now, turn it into a bipartite graph $G' = (V_1 \cup V_2, E')$ as follows: $V_1$ and $V_2$ are copies of $V$. Two vertices $v_1 \in V_1$ and $v_2 \in V_2$ are adjacted in $G'$ if and only if the corresponding vertices in $G$ are adjacted. The expansion of $G'$ follows from the expansion of $G$.

However, one thing that should be noted is that the expansion factor in all those constructions is at most $d/2$. We do not have bipartite expanders that have a better expansion factor and are balanced (i.e. have degree $d$ on both sides).


What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

I believe if you trace through the argument given, e.g., in Section 4.1 of Ker-I Ko's survey, you get an upper bound of $\mathsf{DTIME}(2^{2^{O(n^2)}})$. In fact, we can replace $n^2$ here with any function $nf(n)$ where $f(n) \to \infty$ as $n \to \infty$. This isn't quite what was asked for, but it's close.

In particular, using the translation between oracle separations and circuit lower bounds, and following Ko's notation, we have the following:

We will diagonalize over strings of length $t(n) = p_n(m(n))$ where $p_n(x) = x^n + n$ is "the" $n$-th polynomial (in some enumeration of poly-time algorithms) and $m(n)$ will be specified below.
Translating into circuit lower bounds, this means we're considering bounded-depth circuits on $2^{t(n)}$ inputs.
The requirement (see p. 15 of Ko) we need $m(n)$ to satisfy $\frac{1}{10} 2^{m/(d-1)} > d p_n(m(n))$ for all $n$. Here $d$ is the depth of the circuits we want to diagonalize against, or equivalently the level $\mathsf{\Sigma_d^p}$ of $\mathsf{PH}$ we want to diagonalize against. To diagonalize against all of $\mathsf{PH}$, simply choose $d$ to be a function of $n$ that is $\omega(1)$; we may choose such a $d$ that grows arbitrarily slowly, though (perhaps subject to some computability assumption on $d(n)$, but that should be no obstacle). If we make the guess that $d(n)$ is constant (even though it's not, but it will grow arbitrarily slowly), then we see that $m(n)$ around $2^n$ should work.
This means that $t(n) \sim 2^{n^2}$, so we are looking for a lower bound against circuits with $\sim 2^{2^{n^2}}$ inputs.
Trevisan and Xue (CCC '13) showed that one can find an assignment on which a given bounded-depth circuit on $N$ inputs doesn't compute PARITY with a seed of $polylog(N)$ length.
For us $N=2^{2^{n^2}}$, so $polylog(N) = 2^{O(n^2)}$. We can brute force over such seeds in $2^{2^{O(n^2)}}$ time and use the first one that works.

To replace the $n^2$ with $nf(n)$, just let $p_n(x) = x^{f(n)} + f(n)$ instead.

Interestingly, if I'm understanding correctly, I believe this implies that if one could improve the Trevisan-Xue...

...to a pseudodeterministic/Bellagio algorithm (see Andrew Morgan's comment below), one would get that $\mathsf{BPEXP} \not\subseteq \mathsf{P/poly}$; or
...to a nondeterministic algorithm that guessed $polylog(N)$ bits but then ran in $poly(N)$ time, and such that on any accepting path it makes the same output (cf. $\mathsf{NPSV}$), it would imply $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$; or
... to a deterministic algorithm, one would get $\mathsf{EXP} \not\subseteq \mathsf{P/poly}$.

On the one hand, this suggests why derandomizing the switching lemma further should be hard - an argument which I'm not sure was known before! On the other hand, this strikes me as a kind of interesting take on hardness versus randomness (or is this actually a new thing, oracles versus randomness?).


Conditions for tractability of 3SAT-Satisfiability

Yes. If $ 0< \epsilon <1$ is a constant (or $1/\textit{polylog}(n)$), and you are promised that at least $ \epsilon 2^n $ of all possible assignments are satisfying the input 3CNFs, then you can find such an assignment in deterministic polynomial-time.

The algorithms is not difficult:

Claim: Under the promise stated, there must exist a constant size set $ S $ of variables that hits all clauses in the 3CNF, in the sense that every 3-clause must contain a variable from $ S $.

Proof of claim (sketch): Otherwise, there must exist a large enough family of 3-clauses from the 3CNF, in which each variable occurs only once. But this family, when sufficiently large, has already less than $ \epsilon $ fraction of satisfying assignments. QED

Thus, you can run over all possible (constant number) of assignments to $ S $. Under every fixed assignment to $ S $, the 3CNF becomes a 2CNF, by the assumption that $ S $ hits the original 3CNF. Now, you can use the known polytime deterministic algorithm for finding a satisfying assignment for 2CNF formulas.
Overall, you get a polynomial time upper bound.

The algorithm for 2SAT is I think already in S. Cook famous 1971 paper.

The algorithm for 3CNFs is from:
L. Trevisan
A Note on Deterministic Approximate Counting for k-DNF
In Proc. of APPROX-RANDOM, Springer-Verlag, page 417-426, 2004

The original paper showing the result for 3CNF is:
E. Hirsch, A fast deterministic algorithm for formulas that have many satisfying assignments, Journal of the IGPL, 6(1):59-71, 1998


Existence of graphs of every order related to Barnette’s conjecture

I have a partial solution, with constructions for the first question and for the second question when $n = 2\ (\text{mod}\ 4)$.

Here are constructions for $n = 8$ and $n = 14$. These generalise to constructions for $n = 0\ (\text{mod}\ 4)$ and $n = 2\ (\text{mod}\ 4)$, by taking any square, for example 1,2,3,6 in the second construction, and replacing it with a ladder like shown in the third image.

For the second question, the $2\ (\text{mod}\ 4)$ construction has no nontrivial automorphisms when $n \geq 18$, as we can recover the labeling. First find the added ladder and the pairs 1-2 and 3-6. To discern between them, note that the nodes 1 and 2 are not in any four-node cycle except in the ladder, while 1 and 6 are. Similarly 2 and 3 are not in a four-node cycle except in the ladder, while 1 and 6 are. Then you can uniquely discern 4 (only non-ladder node connected to 1), 5 (same for 6), 8 (only node connected to 3 and 5) and so on.


When is a non-unitary quantum system only theoretical?

Look at John Preskill's Lecture Notes; particularly Section 3.2.

As you noted, you can do a NAND gate by using a Toffoli gate and throwing away some of the output qubits. This results in decoherence, so you no longer necessarily have a pure state of your system.

For non-unitary quantum operations, if you assume that the environment doesn't remember anything, then the most general thing you can do is a unitary operation followed by throwing away some part of the system.

If you assume that the environment has memory, things get much more complicated. But note that here, your operations aren't consistent because the outcome of an operation will depend on what the input was the last time you performed the operation. I don't know if you want to include this class of operations. While they are important in physics, they aren't very useful for quantum computation.


deterministic randomness extractor and privacy

I came across this late. Don't know if this question still matters. I am posting this as an answer since it is too long for a comment.

If n can be 1 but m is not too large (say, at most a small exponential in the min-entropy), a random function will be a good extractor with high probability. It will cost you a factor of something like log m in the min-entropy.

However, for large values of n, you should be able to find a good deterministic  extractor no matter how large m is since, once you condition on x, the distribution on outputs is IID. In particular, it is symmetric, so you can use as idea like von Neumann's trick or its generalizations to extract a small number of random bits just from the ordering of the elements. That might be enough to get the seed for a strong randomness extractor which could extract the rest of the randomness from the source. You have to be careful, but the idea would be to rely heavily on the IID structure to get a a deterministic extractor. Don't know if that's good enough for the application.


Finding a special cut-set in an weighted undirected graph

This problem is NP-complete.

Here's a simple reduction from MAXCUT:

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

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

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

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

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


I think your question was addressed in Beigel and Gill's paper
"Sorting n objects using k-sorter" from 1990 and the abstract of the paper says it all:

  A k-sorter is a device that sorts k objects in unit time. The complexity of an algorithm that uses a k-sorter is defined as the number of applications of the k-sorter. In this measure, the complexity of sorting n objects is between $\frac{n \log n}{k \log k}$ and $\frac{4n \log n}{k \log k}$, up to first-order terms in n and k.


I can't help you with your CMS, but a very good place to read about the logic of access control is Deepak Garg's PhD thesis, Proof Theory for Authorization Logic and Its Application to a Practical File System.


Programming Language Theory and Abstract Algebra

Algebra in the classical sense of the word is used in modeling of computational effects as algebraic operations, see for example these slides by Gordon Plotkin, or you can read real papers and Ph.D. theses, if you actually meant to ask the question.

And to blow my own horn, have a look at Eff and read about it, a language designed around the idea that computational effects are algebraic operations and that handlers are homomorphisms of algebras.


Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

There are essentially only two algorithms that I'm aware of:

Use repeated-squaring, along the lines you mentioned.
Factor $n$ using a state-of-the-art algorithm, then use the Chinese remainder thoerem.  If $p$ is prime, you can compute $a^{b^c} \bmod p$ efficiently by computing $b^c \bmod p-1$ using fast exponentiation, call the result $d$, then computing $a^d \bmod p$.  If $n$ is a product of primes, you can combine the results using the Chinese remainder theorem.

There is believed to be no efficient algorithm for this problem that is faster than these schemes.  I don't know of any proof of that fact, but this assumption is used as a hardness assumption for one scheme in the literature on timelock cryptography (for the special case where $b=2$), and I don't think any faster algorithms are known.

Of course if you let me pick a value of $a$ that has small order modulo $n$, this will be easy.  As another example, if $n$ has a small prime factor $p$ and $a= 0 \pmod{n/p}$, the problem is also trivial.  There are probably multiple special cases that trivialize the problem, but they're probably not very interesting.  If $n$ is a product of two large primes and $a,b,c$ are chosen randomly, the odds of hitting those special cases should be negligibly small.


Better lower bounds than 3n for non-boolean functions?

According to the paper A $5n − o(n)$ Lower Bound on the Circuit Size over $U_2$ of a Linear Boolean Function by  Kulikov, Melanich, and Mihajlin, when $m=o(n)$ there are no lower bounds known better than $3n - o(n)$. It also outlines a method for obtaining functions for which a $4n - o(n)$ lower bound holds, when $m=n$, based on a result of Lamagne and Savage.


Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?

I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (in the sense Goldreich uses it), but rather about Cook reductions being inherent to this notion, in the sense that they cannot be replaced by  Karp reductions. Goldreich makes a distinction between a "general notion of reduction", meaning a Cook reduction, and the restricted notion of a Karp reduction. Then he points out that the fact that Cook reductions in his definition of self-reducibility cannot be replaced by Karp reductions is not merely because of some formality (i.e. "syntactic considerations") but is inherent because a Karp reduction only makes a single query to the decision problem oracle, and, hence, only reveals "a single bit of information". The exercise shows that many more than a single bit of information need to be revealed (log many bits, as you point out).


Any existing Reeds-Shepp implementations?

Copy of my comment above (I suppose that the question can be accepted/closed):

I think that the question is not research level, however perhaps this can help you:
http://msl.cs.uiuc.edu/~lavalle/cs326a/rs.c (README: http://msl.cs.uiuc.edu/~lavalle/cs326a/README_RS).

You can also take a look at Chapter 13 of the book "Planning algorithms".


Barriers to separating other complexity classes

There are (at least) two areas where existing barriers have little to say:

ACC Lower Bounds There is no known barrier to proving that TC0 is not in (non-uniform) ACC -- other than the possibility that the separation may be false. It's unclear whether the Natural Proofs barrier should apply to ACC. The question boils down to: should we expect there to be pseudorandom functions implementable in ACC?

LOGSPACE vs NP As pointed out by Fortnow, the existing oracle mechanisms for space-bounded computation do not seem to present a real barrier to LOGSPACE vs NP. To my knowledge, the known oracle models which yield a collapse of LOGSPACE and NP also collapse ALTERNATING LOGSPACE (i.e., P) and ALTERNATING POLYTIME (i.e., PSPACE), hence these oracles treat alternating computational models inconsistently with reality (since LOGSPACE is not equal to PSPACE).


Quantum analogues of SPACE complexity classes

You might want to check  Space-Bounded Quantum Complexity, by John Watrous.

There you have the result that for any $s=\Omega(\log n)$, a Quantum Turing Machine running in space $s$ can be simulated by a probabilistic Turing Machine with unbounded error running in space $O(s)$. You also have that any Quantum Turing Machine running in space $s$ can be simulated in $NC^2(2^s) \subseteq DSPACE(s^2) \cap DTIME(2^{O(s)})$


Maximum flow using Ford-Fulkerson and DFS

If adjacency lists are fixed in advance then DFS always terminates (even if there are irrational capacities).

See Dean, Goemans, Immorlica -- Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data.


Per the section quoted in the comments, it appears that one of the cited documents takes input in the form of an adjacency matrix. In this scenario, taking $s$ and $t$ to correspond to the first and last indices respectively, we can prove that $\Omega(n^2)$ bits of the matrix may need to be read to decide STCONN even under the promise that the $(n/2)\times(n/2)$ square blocks in the top-left and bottom-right are all ones (with the necessary adjustments for odd $n$).
Indeed, we have some $\Omega(n^2)$ entries unaccounted for in the matrix, and there is an $s$-$t$ path iff any one of them is a $1$. So in the worst case, we might need to read all of these $\Omega(n^2)$ bits to prove $s$-$t$-non-connectivity (or half of them if the graph is known to be undirected, which doesn't change the order of growth). We can turn this into a lower bound against randomized algorithms by considering the case that with 50% probability we either add or don't add in a $1$ uniformly at random: we must read some $\Omega(\varepsilon n^2)$ bits to gain a $\varepsilon$ advantage over a random coin flip.
Graphically, this corresponds to the case where $s$ and $t$ each lie within disjoint cliques of size $n/2$, and we wish to determine if there is at least one edge joining these cliques. One can also do the same thing with any other pair of connected structures of order $\Omega(n)$ each.


Parametrized complexity of the 2-Long Paths Problem

Your problem is fixed-parameter tractable, which follows from the heavy machinery of Robertson & Seymour. Your problem can be stated in terms of rooted minors. A graph $H$ with designated root vertices $s$ and $t$ is a rooted minor of a graph $G$ with roots $s$ and $t$, iff there is a function $f \colon V(H) \to 2^{V(G)}$ which assigns to each vertex of $H$ a subset of vertices in $G$, called a branch set, such that the following holds:

For each $v \in V(H)$ the branch set $f(v) \subseteq V(G)$ induced a connected subgraph of $G$, and
The sets $f(v)$ and $f(u)$ are disjoint for $u \neq v$, and
For each edge $e = \{u,v\} \in E(H)$, there is an edge of $G$ between the branch set $f(u)$ and the branch set $f(v)$, and
The branch set of $s \in V(H)$ contains the $s$-vertex in $G$, and the branch set of $t \in V(H)$ contains the $t$-vertex in $G$.

Now consider the rooted graph $H$ with roots $s$ and $t$, connected by two vertex-disjoint paths of length $k$. (So $H$ is a cycle of length $2k$ with the root vertices at distance $k$ along the cycle.) You can show that $G$ has two vertex-disjoint $st$ paths of length at least $k$ if and only if the graph $G$ with roots $s$ and $t$ has $H$ as a rooted minor. Testing rooted minors is fixed-parameter tractable parameterized by the size of $H$, which follows from Graph Minors XIII. So your problem is FPT.

(If you are not familiar with graph minors, you might want to first absorb the fact that a graph has a cycle of length at least $k$ iff it contains the $k$-vertex cycle graph as a minor.)


Find a string with minimal edit distance from a set of given strings

Your problem is called the Median string problem. Nicolas and Rivals proved that the Median String problem (under the Levenshtein distance) is NP-complete even for binary strings.


A partition problem in which some numbers may be cut

The largest number is the soft number

I claim that for any instance of your problem, if the instance is solvable (it is possible to partition the numbers using one soft number) then it is possible to solve the instance using the largest number as the sole soft number. This is easy to prove: any solution can be modified into a solution with the largest number as the soft number; simply place the number that is currently the soft number into the partition that contains the largest number and split the largest number among the parts of the partition instead.

Packing problem

Here is a problem that I will call the packing problem:

The input consists of a list of positive numbers $a_1, a_2, \ldots, a_k$ and one final number $\ell$ such that $\ell \ge a_i$ for all $i$. Define $s = \frac{1}{3}\left(\ell + \sum_{i = 1}^ka_i\right)$. Then the problem is to partition the list of $a_i$s into three parts such that each part has sum at most $s$.

I claim that the packing problem with inputs $a_1, \ldots, a_k$ and $\ell$ is equivalent to your problem with input list $a_1, \ldots, a_k, \ell$. If it's possible to pack the numbers $a_1, \ldots, a_k$ into three groups each of sum at most $s$ then you can use $\ell$ as a soft number to round out each of the sums to exactly $s$; thus you have a partition of $a_1, \ldots, a_k, \ell$ into three groups of sum $s$ using one soft number. If on the other hand $a_1, \ldots, a_k, \ell$ can be partitioned into three groups of sum $s$ using one soft number then the list can be partitioned into three groups of sum $s$ using $\ell$ as the soft number (by the result from the previous section). In this case the grouping of the $a_i$s into three parts satisfies the condition that each part has sum at most $s$.

The packing problem with no small numbers

Say that an instance of the packing problem "has no small numbers" if for every $i$, $a_i > \frac{\ell}{2}$. I claim that you can reduce the packing problem to the packing problem with no small numbers.

Suppose that in packing problem instance $(a_1, \ldots, a_k), \ell$ some $a_i$ has $a_i \le \frac{\ell}{2}$. WLOG suppose $a_k$ is this $a_i$. Then I claim the packing problem instance $(a_1, \ldots, a_{k-1}), \ell+a_k$ is equivalent to the original instance. Notice that the value $s$ remains the same in both instances.

Certainly if you can pack the numbers $a_1, \ldots, a_k$ into three groups with each group having sum at most $s$ then you can pack the numbers $a_1, \ldots, a_{k-1}$ into three groups with each group having sum at most $s$.

On the other hand, suppose you can pack the numbers $a_1, \ldots, a_{k-1}$ into three groups with each group having sum at most $s$. For each of the three groups, consider the value $s$ minus the sum of the elements in the group. Call these values $e_1, e_2, e_3$; here $e_i$ is the amount of "empty space" in group $i$. We know that $e_1 + e_2 + e_3$, the total empty space, is equal to $3s - \sum_{i = 1}^{k-1}a_i$ (total space $3s$ minus space used $\sum_{i = 1}^{k-1}a_i$). But $3s - \sum_{i = 1}^{k-1}a_i = a_k + \ell$ by the definition of $s$. Thus, the three groups have $a_k + \ell$ empty space in total. Then since $a_k < \frac{\ell}{2}$, we know that the total empty space is more than $3a_k$. By the pigeon hole principle, at least one of the groups has $a_k$ or more empty space in it. Thus, we can add element $a_k$ to one of the groups and end up with a packing of the numbers $a_1, \ldots, a_k$ into three groups with each group having sum at most $s$.

Thus, in order to solve your problem, it is sufficient to solve just the packing problem with no small numbers.

Lemma 1

Lemma statement:

Suppose we can partition $a_1, \ldots, a_k$ into groups 1 and 2 such that group 2 has an even number of elements and the sum of the elements in group 1 is in the interval $\left[s - \frac{\ell}{2}, s\right]$. Then it is possible to further partition group 2 into two subgroups 2a and 2b each of which has sum at most $s$. Notice that groups 1, 2a, and 2b are a solution of the packing problem instance.

Here's a proof.

Tentatively assign half of the elements of group 2 to subgroup 2a and the other half to subgroup 2b. Create a matching between the elements of the two subgroups. Swap these pairs between the two groups, one pair at a time. If there are $2n$ elements in group 2 then this process passes through exactly $n+1$ possible partitions of group 2 into subgroups 2a and 2b. I claim that at least one of those partitions has both subgroups with sum less than $s$.

Let $S_{2a}$ and $S_{2b}$ be the sums of the two subgroups (we allow these values to change as the groups change).

At each step of the above process, group 2a gains one element and loses another. Since each element has value between $\frac{\ell}{2}$ and $\ell$, we can conclude that at each step of the above process, $S_{2a}$ changes by at most $\frac{\ell}{2}$.

Also, the final value of $S_{2a}$ is equal to the initial value of $S_{2b}$ since by the end of the process the groups have entirely swapped.

Let $A$ be the average value of $S_{2a}$ and $S_{2b}$. Note that this is constant as the groups change. We know that the initial and final values of $S_{2a}$ average to $A$ (since the initial and final values of $S_{2a}$ equal the initial values of $S_{2a}$ and $S_{2b}$). Thus, $A$ must be between the initial and final values of $S_{2a}$. As we change the groups, the value of $S_{2a}$ takes steps of size at most $\frac{\ell}{2}$ from one side of $A$ to the other. From this, we can conclude that at some point, the value of $S_{2a}$ must be within half of the maximum step size ($\frac{\ell}{4}$) of $A$. Since $S_{2b}$ always has the same distance from $A$ as $S_{2a}$, we can conclude that at some point, both sums $S_{2a}$ and $S_{2b}$ are within $\frac{\ell}{4}$ of $A$.

$3s - \ell - (S_{2a} + S_{2b})$ is the sum of the elements of group 1; thus, $3s - \ell - (S_{2a} + S_{2b}) \ge s - \frac{\ell}{2}$ (by the condition on the sum of group 1). Rearranging, we have that $(S_{2a} + S_{2b}) \le 2s - \frac{\ell}{2}$. Therefore, the average of $S_{2a}$ and $S_{2b}$ is at most $s - \frac{\ell}{4}$. Then at the time that both $S_{2a}$ and $S_{2b}$ are within $\frac{\ell}{4}$ of $A$, we see that they are both at most $s$ as desired.

Case 1: $k = 3n$

Sum the $n$ smallest $a_i$s and also the $n$ largest $a_i$s.

If the $n$ smallest $a_i$s sum to more than $s$, then no group can have $n$ or more elements (as any choice of $n$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n$ elements. Thus, in this case there is no solution to the packing problem instance.

If the $n$ largest $a_i$s sum to at most $s$, then every choice of $n$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of equal size solves the packing problem instance.

The only remaining case is that the smallest $n$ elements sum to at most $s$ and the largest $n$ elements sum to more than $s$. As in the lemma, we can slowly transition between these two sets: start with a group initialized with the smallest $n$ elements and swap elements until the group has the largest $n$ elements. Each step moves the sum of the group by at most $\frac{\ell}{2}$ (by the same logic as in the proof of the lemma) and the sum crosses the value $s$ at some point in this process. Therefore, either immediately before or immediately after crossing the value $s$, the sum is less than $s$ but less by at most $\frac{\ell}{2}$. In other words, at some point in this process, the group has a sum in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

Case 2: $k = 3n+1$

Sum the $n+1$ smallest $a_i$s and also the $n+1$ largest $a_i$s.

If the $n+1$ smallest $a_i$s sum to more than $s$, then no group can have $n+1$ or more elements (as any choice of $n+1$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n+1$ elements. Thus, in this case there is no solution to the packing problem instance.

If the $n+1$ largest $a_i$s sum to at most $s$, then every choice of $n+1$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of size $n$, $n$, and $n+1$ solves the packing problem instance.

The only remaining case is that the smallest $n+1$ elements sum to at most $s$ and the largest $n+1$ elements sum to more than $s$. As in the previous case, we can slowly transition between these two sets: start with a group initialized with the smallest $n+1$ elements and swap elements until the group has the largest $n+1$ elements. Each step moves the sum of the group by at most $\frac{\ell}{2}$ (by the same logic as in the proof of the lemma) and the sum crosses the value $s$ at some point in this process. Therefore, either immediately before or immediately after crossing the value $s$, the sum is less than $s$ but less by at most $\frac{\ell}{2}$. In other words, at some point in this process, the group has a sum in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

Case 3: $k = 3n+2$ first easy subcase

Sum the $n$ smallest $a_i$s and the $n$ largest $a_i$s.

If either value is in the interval $[s-\frac{\ell}{2}, s]$, immediately apply the lemma with that choice of $n$ elements as group 1 and the remaining $2n+2$ elements as group 2. This allows us to find a solution to the packing problem instance.

If the $n$ smallest $a_i$s sum to less than $s-\frac{\ell}{2}$ and the $n$ largest $a_i$s sum to more than $s$ then we can start with the $n$ smallest $a_i$s and swap elements until we end up with the $n$ largest $a_i$s. At each step the sum moves at most $\frac{\ell}{2}$, so at some point in this process we have a group of $n$ elements whose sum is in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n+2$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

If the $n$ smallest $a_i$s sum to more than $s$, then no group can have $n$ or more elements (as any choice of $n$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n+1$ elements. Thus, in this case there is no solution to the packing problem instance.

The only remaining case is that both the $n$ smallest and $n$ largest $a_i$s add to less than $s-\frac{\ell}{2}$.

Case 3: $k = 3n+2$ second easy subcase

Sum the $n+2$ smallest $a_i$s and the $n+2$ largest $a_i$s.

If either value is in the interval $[s-\frac{\ell}{2}, s]$, immediately apply the lemma with that choice of $n+2$ elements as group 1 and the remaining $2n$ elements as group 2. This allows us to find a solution to the packing problem instance.

If the $n+2$ smallest $a_i$s sum to less than $s-\frac{\ell}{2}$ and the $n+2$ largest $a_i$s sum to more than $s$ then we can start with the $n+2$ smallest $a_i$s and swap elements until we end up with the $n+2$ largest $a_i$s. At each step the sum moves at most $\frac{\ell}{2}$, so at some point in this process we have a group of $n+2$ elements whose sum is in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

If the $n+2$ largest $a_i$s sum to at most $s$, then every choice of $n+2$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of size $n$, $n+1$, and $n+1$ solves the packing problem instance.

The only remaining case is that both the $n+2$ smallest and $n+2$ largest $a_i$s add to more than $s$.

Case 3: $k = 3n+2$ hard subcase

Suppose neither of the above two subcases handled the instance. Then we know the following:

both the $n$ smallest and $n$ largest $a_i$s add to less than $s-\frac{\ell}{2}$.
both the $n+2$ smallest and $n+2$ largest $a_i$s add to more than $s$.

Since the $n+2$ smallest $a_i$s add to more than $s$, no group can have $n+2$ or more elements. The only way this is possible to accomplish is if the groups have sizes $n$, $n+1$, and $n+1$.

Note that since the $n$ largest $a_i$s add to less than $s-\frac{\ell}{2}$, it doesn't matter what elements are in the group of size $n$: that group will have sum less than $s$ anyway. Clearly, we can modify any solution by swapping the $n$ largest $a_i$s into the group of size $n$. These swaps only decrease the sums of the other two groups, so there exists a solution to the packing problem instance if and only if there exists a solution in which the $n$ largest $a_i$s form one of the groups.

Thus, the task at hand is simply this: is it possible to partition the $2n+2$ smallest $a_i$s into two groups of size $n+1$ such that each of those two groups has sum at most $s$. WLOG suppose that the $a_i$s are in increasing order so that the $2n+2$ smallest $a_i$s are $a_1, \ldots, a_{2n+2}$

Let $v$ be the average of the $n$ largest $a_i$s. Let $x_i = v - a_i$ for each $i$. Then $3s = \ell + \sum_{i = 1}^{3n+2}a_i = \ell + \sum_{i = 1}^{2n+2}a_i + \sum_{i = 2n+2}^{3n+2}a_i = \ell + \sum_{i = 1}^{2n+2}(v - x_i) + nv = \ell + (3n+2)v - \sum_{i = 1}^{2n+2}(x_i) = (\ell-v) + (3n+3)v - \sum_{i = 1}^{2n+2}(x_i)$.

Then $s = (n+1)v + \frac{\ell - v}{3} - \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i)$.

If we choose some set $I$ of $n+1$ indices, then the sum of the $a_i$s with $i \in I$ is equal to $\sum_{i\in I}a_i=\sum_{i\in I}v - x_i = (n+1)v-\sum_{i\in I}x_i$. A set of indices $I$ is a valid choice for one of the groups provided this sum is at most $s$. In other words, using the alternate definition of $s$ derived above, the condition we are interested in is $\sum_{i\in I}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$. Obviously, the remaining $n+1$ indices $I' = \{1,\ldots, 2n+2\} \setminus I$ must also satisfy this condition: $\sum_{i\in I'}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$. Since $\sum_{i\in I'}x_i = \sum_{i = 1}^{2n+2}x_i - \sum_{i\in I}x_i$, we can rewrite the second condition as $\sum_{i\in I}x_i \le \frac{2}{3}\sum_{i = 1}^{2n+2}(x_i) + \frac{\ell - v}{3}$.

Thus we have restated this subproblem using an equivalent alternative: we are trying to choose a set $I$ of $n+1$ indices among $\{1, \ldots, 2n+2\}$ such that $\frac{2}{3}\sum_{i = 1}^{2n+2}(x_i) + \frac{\ell - v}{3} \ge \sum_{i\in I}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$.

Note that $\ell \ge v$ (and therefore $\ell-v \ge 0$) since $v$ is the average of some $a_i$s and $\ell$ is an upper bound on all $a_i$s. Let $X = \sum_{i = 1}^{2n+2}(x_i)$. Our condition above can be rewritten as follows: choose a set $I$ of $n+1$ indices among $\{1, \ldots, 2n+2\}$ such that $\sum_{i\in I}x_i$ is in the interval $[cX, (1-c)X]$ where $c = \frac{1}{3} - \frac{\ell - v}{3X} \le \frac{1}{3}$.

Suppose that for some $j$, $x_j$ has value at least $\frac{X}{3}$. In this case, let $I$ consist of the index $j$ and also of the $n-1$ indices corresponding to the smallest $x_i$s. If these $x_i$s add to at most $(1-c)X$ then this choice of $I$ satisfies the above constraint: the sum $\sum_{i\in I}x_i$ is at least $x_j \ge \frac{X}{3} = \frac{1}{3}X \ge cX$ and at most $(1-c)X$. Thus, this set of indices $I$ can be used to select one of the groups of size $n+1$ in a solution to the packing problem instance. On the other hand, if these $x_i$s add to more than $(1-c)X$ then the instance cannot be solved: one of the two halves will include $x_j$ and the sum of that half is always going to be more than $(1-c)X$ (since it was more than that even when we put the smallest elements with $x_j$).

Thus, we have handled the case that some $x_j$ has value at least $\frac{X}{3}$. The remaining case is that every $x_i$ has value at most $\frac{X}{3}$. Then assign the $x_i$s to two groups, 1 and 2, arbitrarily. Create a matching of the elements of the two groups and swap those pairs one pair at a time. Over the course of this process, the sum of the elements of group 1 will move from it's initial sum to the initial sum of group 2's elements. In other words, the sum of group 1 will cross the average value $\frac{X}{2}$. Each step in this process involves group 1 losing an $x_i$ and gaining one; since the $x_i$s have value at most $\frac{X}{3}$, a pair of $x_i$s differs by at most $\frac{X}{3}$ and so each step moves the sum of group 1 by at most $\frac{X}{3}$. Thus, there will be some point in the process when the sum of group 1 is within half the maximum step size of the average. Thus, at some point the sum of group 1 will fall within $\frac{X}{2} \pm \frac{X}{6}$. But this is the interval $[\frac{1}{3}X, \frac{2}{3}X]$, which is a subinterval of $[cX, (1-c)X]$. Thus, at some point during this process, the group 1 at the time will satisfy our desired condition. We can use this group of $x_i$s to select a corresponding group of $a_i$s; these $a_i$s form one of the two groups of size $n+1$ needed to solve the packing problem instance.

Conclusion

The above exhaustive casework can be used as an algorithm to partition a list into three groups of the same sum using one soft number. The casework will also identify when this is impossible. The runtime of this algorithm is polynomial.


If "unbalanced expanders" count as expanders for the purpose of this question (an unbalanced expander: a bipartite graph $G=(A,B,E)$, such that for every subsets $A'\subseteq A$, $B'\subseteq B$, the fraction of edges between $A'$ and $B'$ is about ${|A'||B'|}/{|A||B|}$), then yes, many problems on expanders (e.g., constraint satisfaction problems) are NP-hard to approximate.

In particular, the proof of the two-query, low error, PCP Theorem [with Ran Raz in 2008] constructs expander graphs.


One-way functions with polynomial inverting complexity

Some functions are conjectured to have that property, aptly called moderately hard. They were first proposed in the context of spam fighting, and then found their ways into more complicated applications, such as concurrent zero knowledge and timed commitment. They usually use a function of the form $f(x) = g^{2^{2^x}} \bmod N$, first suggested by Rivest, Shamir and Wagner:

  N is a product of two large primes. Without knowing the factorization of N, the best that is known is repeated squaring - a very sequential computation in nature.

If $VNP=VP$, then factorization can be performed efficiently, and therefore we do not have to resort to repeated squaring. However, performing factorization for someone who does not know the factors of N incurs a polynomial overhead.

You may also be interested in the concept of feebly one-way functions, though they are not exactly related to the question.

See the following references as well:

Pricing via Processing -or- Combatting Junk Mail by Dwork and Naor.
Moderately Hard Functions: From Complexity to Spam Fighting by Naor.
Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints by Dwork and Sahai.
Timed Commitments by Boneh and Naor.


Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions

You can still argue by counting. No matter how randomness is used, there is a way to fix the randomness in such a way that the function is computed correctly deterministically on at least $\frac{2}{3}2^n$ inputs. Thus assuming any function can be computed with error at most $\frac{1}{3}$ by some circuit in size $S$, any function can be described by a circuit of size $S$ together with a set of at most size $\frac{1}{3}2^n$ of inputs where the answer is incorrect.


How good is the Huffman code when there are no large probability letters?

There are lots of papers that study exactly the problem you mention. The first in the series is a paper by Gallager, "Variations on a Theme by Huffman", IEEE-IT, vol. 24, 1978, pp. 668-674. He proves that the difference between the average codeword length of an Huffman code and the entropy  (he calls that quantity "redundancy") is always strictly less than $p$ (= largest probability in the probability distribution), in the case  $p\geq 1/2$, and it is less than $p+0.086$, if $p<1/2$. Better bounds are known, you can find them in the numerous papers that quote Gallager work.


Inappoximability status of Max One in Three SAT for satisfiable instances

The most relevant paper I know is

"The Complexity of Making Unique Choices: Approximating 1-in-k SAT" by Guruswami and Trevisan (link)

They give an algorithm for satisfiable instances which for $k=3$ would achieve a ratio of $\frac{4}{9}$, beating the random assignment. They also mention that 1-in-3 SAT is $\frac{5}{6}$-inapproximable, but I'm not sure if that applies to satisfiable instances. They cite Guruswami's Master's thesis for this.


Are there Belief Revision techniques for quantified data?

Fuzzy Belief Revision and Probabilistic Belief Revision are two flavours of Belief Revision that do not fall within the formal logic propositions characterisation of the field.


Hyperscan is a high-performance multiple regex matching library that uses hybrid automata techniques to allow simultaneous matching of large numbers of regular expressions across streams of data. They explained their approach here:
https://www.hyperscan.io/2015/10/20/match-regular-expressions
Apparently, they didn't find a fast algorithm (in the worst case) for this problem: "We have not found a single, elegant automata approach that handles arbitrary regular expressions in arbitrary number". However, they used a lot of optimization which works well enough in practice.
I also believe that in the worst case, the given regular expressions can be so complex that no better solution exists.


Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

EDIT: Added Lemma 2 which covers all cases asked about.
Lemma 1.  Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing number of 1's, with the time taken between each word and the next polynomial in $n$ and the size of the DFA.
Proof.  Here's the algorithm.  Fix an input DFA $M$ and integer $n$.
For each $k\in\{0,1,\ldots, n\}$ in increasing order, do the following:

Construct a new DFA $M_k$ with a state $(s, i, j)$ for each state $s$ in $M$ and $i, j \ge 0$ with $i+j\le n$.  The new DFA $M_k$ simulates $M$, but uses the indices $i$ and $j$ to count, respectively, the number of 0's and 1's seen so far.  Make $(s, 0, 0)$ the start state, where $s$ is the start state of $M$. Make each state $(s, i, j)$ an accepting state of $M_k$ if $s$ is an accepting state of $M$ and $i+j=n$ and $j=k$. So $$L(M_k) = \{w \in L(M) : w \text{ has length $n$ and $k$ ones}\}.$$  Note that $M_k$ is a directed acyclic graph whose size is polynomial in $n$ and the size of $M$.

Enumerate the words accepted by $M_k$ as follows.  First delete all dead states (states not reachable from the start state, or from which no accept state can be reached).  Find the lexicographically first path in the language of $M_k$ by starting at the start state, then traversing from each node to the next, taking a 0-edge if possible and otherwise a 1-edge.  Stop upon reaching a start state, and output the path found.  Next, repeat the following: let $p$ be the path just enumerated.  Find the path $p'$ following $p$ in lexicographic order as follows.  Take the last 0-edge $(u, w)$ on $p$ such that there is a 1-edge out of $u$, and replace that 0-edge edge and the remaining suffix of $p$ by the 1-edge (say, $(u, w')$) out of $u$ and the lexicographically first path from $w'$ to an accept state (computed as described above, taking 0-edges when possible).  If there is no such edge $(u, w)$, stop.

Note that there are no dead states, so the algorithm can always find $p'$ as described above.
By inspection the time for Step 1 is polynomial in $n$ and the size of $M$, and each path enumerated in Step 2 is enumerated in time polynomial in $n$ and the size of $M$.  The words in $L(M)$ of length $n$ are enumerated in order of increasing number of 1's (i.e., increasing value of $k$.)  $~~\Box$
Lemma 2.  Given an instance of the "weighted" variant in the post, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing weight, with the time taken between each word and the next polynomial in $n$ and the size of the DFA.
Proof. By a construction similar to Step 1 of the algorithm in the proof of Lemma 1, the problem reduces to the following problem.  Given an edge-weighted DAG $G=(V,E)$ and two nodes $s$ and $t$, enumerate all paths from $s$ to $t$, in order of increasing path weight, taking time polynomial in the size of the DAG between enumerated paths.
Here is an algorithm for that problem.  (Note: the data maintained by the algorithm will be become exponentially large, but this will be okay each additional path will still be enumerated in polynomial time.)
Observation 1.
Let $P_v$ denote the paths from $s$ to $v$.  For $v\ne s$,
$$P_v = \bigcup_{u:(u,v)\in E}\{ p \circ (u, v) : p \in P_u \},$$
where $\circ$ denotes concatenation.  Consider $P_v$ ordered by increasing path weight.  In this order, consider only the paths that end in a given edge $(u, v)\in E$.  Let these paths be
$$p_1 \circ (u, v),~p_2 \circ (u, v), ~\ldots, ~p_\ell \circ (u, v).$$
Then $p_1, p_2, \ldots, p_\ell$ are the paths in $P_u$, ordered by increasing path weight.
For each vertex $v$ and index $i$, let $P_v(i)$ denote the $i$th in $P_v$, ordered by path weight. We will build an enumerator of $P_v$ that enumerates the $s$-$v$ paths in order $P_v(1), P_v(2), \ldots$, that is, by increasing path weight.  At any given time, each enumerator $P_v$ will have so far enumerated $P_v(1), P_v(2), \ldots, P_v(i_v)$ for some $i_v$. It will support two operations:

Increment. Enumerate the next path $P_v(i_v+1)$ in the sequence and increase $i_v$ by one.

Query. Given an index $i\le i_v$, return the cost of the $i$th path in the sequence, i.e., the cost of $P_v(i)$.

The overall algorithm will simply repeatedly increment the enumerator for $P_t$ to enumerate all its paths in order.  It remains to describe how to implement the enumerator $P_v$ for any given $v\ne s$ to support the two operations above.
$P_v$ will record (in an array), for each path $P_v(i)$ that it has already enumerated (i.e., $i\le i_v$), the cost of that path.  This will let it perform the query operation in constant time.
To support the increment operation, following Observation 1, $P_v$ will maintain, for each edge $(u, v)$ into $v$, the index $j_{uv}$ such that the most recent path that ends in edge $(u, v)$ that it has enumerated is $P_u(j_{uv})\circ (u, v)$.  (Hence, $\sum_u j_{uv}$ equals $i_v$, the number of paths that $P_v$ has enumerated so far.)
By Observation 1, the next path $P_v(i_v+1)$ in the sequence is the cheapest of the following paths:
$$P_u(j_{uv}+1) \circ (u, v) \text{ such that } (u,v) \in E.$$
The enumerator will find this path by calling each enumerator $P_u$ for $(u, v)\in E$, to find the cost of $P_u(j_{uv}+1)$.  Having found the best path, say $P_{u'}\circ (u', v)$, it will increment $j_{u'v}$, and in the case that $j_{u'v} = i_{u'}$ (the best path uses the most recent path enumerated by $P_{u'}$), it will increment $P_{u'}$ (have it enumerate its next path), ensuring that $i_{u'}$ is at least $j_{u'v}+1$.  This way, each cost query to $P_v$ can be done in constant time.
Note that any given call to $P_t$ results in each enumerator $P_u$ being incremented at most once total, even though increments can propagate and  several enumerators $P_v$ could in principle ask $P_u$ to increment.  This is because, during any given call to $P_t$, for a given enumerator $P_u$, we can assume by induction (on distance to $t$) that each of its "parents" $P_v$ (with $(u,v)\in E$) is incremented at most once during the call to $P_t$.  So, once $P_u$ is incremented once during the call, its $i_u$ has increased by one, which is the most that any parent could need.
(Alternatively, we could proceed in rounds $r=1,2,\ldots$, and in round $r$ have every enumerator $P_u$ increment by one, producing $P_u(r)$.  Because $P_v(i) = P_u(i') \circ (u, v)$ where $(u,v)\in E$ and $i' \le i$, this would suffice.  It would still be polynomial time, but not as efficient.)  $~~\Box$
EDIT 2: Code for the algorithm (on DAGs) in the proof is here.


How do you get the Calculus of Constructions from the other points in the Lambda Cube?

First, to reiterate one of cody's points, the Calculus of Inductive Constructions (which Coq's kernel is
based on) is very different from the Calculus of Constructions. It is
best thought of as starting at Martin-Löf type theory with universes,
and then adding a sort Prop at the bottom of the type hierarchy.  This
is a very different beast than the original CoC, which is
best thought of as a dependent version of F-omega. (For instance, CiC
has set-theoretic models and the CoC doesn't.)

That said, the lambda-cube (of which the CoC is a member) is typically presented as a pure type system for reasons of economy in the number of typing rules. By treating sorts, types, and terms as elements of the same syntactic category, you can write down many fewer rules and your proofs get quite a bit less redundant as well.

However, for understanding, it can be helpful to separate out the different categories explicitly. We can introduce three syntactic categories, kinds (ranged over by the metavariable k), types (ranged over by the metavariable A), and terms (ranged over by the metavariable e). Then all eight systems can be understood as variations on what is permitted at each of the three levels.

λ→ (Simply-typed lambda calculus)

 k ::= ∗
 A ::= p | A → B
 e ::= x | λx:A.e | e e

This is the basic typed lambda calculus. There is a single kind ∗, which is the kind of types. The types themselves are atomic types p and function types A → B. Terms are variables, abstractions or applications.

λω_ (STLC + higher-kinded type operators)

 k ::= ∗ | k → k
 A ::= a | p | A → B | λa:k.A | A B
 e ::= x | λx:A.e | e e

The STLC only permits abstraction at the level of terms. If we add it at the level of types, then we add a new kind k → k which is the type of type-level functions, and abstraction λa:k.A and application A B at the type level as well. So now we don't have polymorphism, but we do have type operators.

If memory serves, this system does not have any more computational power than the STLC; it just gives you the ability to abbreviate types.

λ2 (System F)

 k ::= ∗
 A ::= a | p | A → B  | ∀a:k. A
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Instead of adding type operators, we could have added polymorphism. At the type level, we add ∀a:k. A which is a polymorphic type former, and at the term level, we add abstraction over types Λa:k. e and type application e [A].

This system is much more powerful than the STLC -- it is as strong as second-order arithmetic.

λω (System F-omega)

 k ::= ∗ | k → k
 A ::= a | p | A → B  | ∀a:k. A | λa:k.A | A B
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

If we have both type operators and polymorphism, we get F-omega. This system is more or less the kernel type theory of most modern functional languages (like ML and Haskell). It is also vastly more powerful than System F -- it is equivalent in strength to higher order arithmetic.

λP (LF)

 k ::= ∗ | Πx:A. k
 A ::= a | p | Πx:A. B | Λx:A.B | A [e]
 e ::= x | λx:A.e | e e

Instead of polymorphism, we could have gone in the direction of dependency from simply-typed lambda calculus. If you permitted the function type to let its argument be used in the return type (ie, write Πx:A. B(x) instead of A → B), then you get λP. To make this really useful, we have to extend the set of kinds with a kind of type operators which take terms as arguments Πx:A. k , and so we have to add a corresponding abstraction Λx:A.B and application A [e] at the type level as well.

This system is sometimes called LF, or the Edinburgh Logical Framework.

It has the same computational strength as the simply-typed lambda calculus.

λP2 (no special name)

 k ::= ∗ | Πx:A. k
 A ::= a | p | Πx:A. B | ∀a:k.A | Λx:A.B | A [e]
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

We can also add polymorphism to λP, to get λP2. This system is not often used, so it doesn't have a particular name. (The one paper I've read which used it is Herman Geuvers' Induction is Not Derivable in Second Order Dependent Type Theory.)

This system has the same strength as System F.

λPω_ (no special name)

 k ::= ∗ | Πx:A. k | Πa:k. k'
 A ::= a | p | Πx:A. B | Λx:A.B | A [e] | λa:k.A | A B
 e ::= x | λx:A.e | e e

We could also add type operators to λP, to get λPω_. This involves adding a kind Πa:k. k' for type operators, and corresponding type-level abstraction Λx:A.B and application A [e].

Since there's again no jump in computational strength over the STLC, this system should also make a fine basis for a logical framework, but no one has done it.

λPω (the Calculus of Constructions)

 k ::= ∗ | Πx:A. k | Πa:k. k'
 A ::= a | p | Πx:A. B | ∀a:k.A | Λx:A.B | A [e] | λa:k.A | A B
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Finally, we get to λPω, the Calculus of Constructions, by taking λPω_ and adding a polymorphic type former ∀a:k.A and term-level abstraction Λa:k. e and application e [A] for it.

The types of this system are much more expressive than in F-omega, but it has the same computational strength.


Is the primality problem with unary input NLOGSPACE-Hard?

This language is in $\mathsf{LOGSPACE}$ via trial division. It is also known logarithmic space is neccessary ([1]). For a generalization to sparse sets, see bounded language complete for NSPACE(log n)?. For hardness in binary case, see Are the problems PRIMES, FACTORING known to be P-hard?.

[1] J. Hartmanis, L. Berman, On tape bounds for single letter alphabet language processing. Theoretical Computer Science vol. 3 http://www.sciencedirect.com/science/article/pii/0304397576900244


Take a clique of size 5 and consider a graph on $n = 5k$ nodes consisting of $k$ copies of this clique. The size of a maximal cut in this graph is $6k = 6n/5$. Indeed, from each copy we can maximally have 6 edges in a cut.
By the following lemma the size of a maximal cut can not be much smaller.

Lemma. In any undirected 4-regular with $n$ nodes there exists a cut with at least $\lceil 6n/5 \rceil$ edges.

More precisely, for $n$ divisible by 5 the answer to your question is exactly $6n/5$. For other $n$ it can be a bit bigger, but only by a $O(1)$ term. Indeed, we can again consider a graph where all but $O(1)$ nodes are paritioned into  copies of a 4-regular clique.
Proof. Let $G = (V, E)$ be a 4-regular graph with $n$ nodes and let $(S, T)$ be a maximal cut. For a node $a\in V$ let cut-degree of $a$ be the number of edges containing $a$ and belonging to the cut $(S, T)$. We rely on the following two easily verifiable observations:

Observation 1: any node has cut-degree at least 2. Indeed, assume that $a\in V$ has cut degree at most $1$. WLOG, $a\in S$. Then removing $a$ from $S$ and putting it to $T$ would result in a larger cut, contradiction.
Observation 2: no edge of the cut connects two nodes with cut-degree 2. Indeed, assume that nodes $a\in S$ and $b\in T$ are adjacent and both have cut-degree 2. Then swapping $a$ and $b$ (putting $a$ to $T$ and $b$ to $S$) would result in a larger cut, contradiction.

Assume that $|S| = s, |T| = t$. Let $x$ be the number of nodes from $S$ with cut-degree 2. Similarly, let $y$ be the number of nodes from $T$ with cut-degree 2.
Let $C$ be the size of the cut $(S, T)$. Note that $C$ equals the sum of cut-degrees over the nodes from $S$. Exactly $x$ nodes from $S$ have cut-degree $2$. By observation 1 all the other nodes from $S$ have cut-degree at least $3$. Hence
$$C \ge 2x + 3(s - x) = 3s - x.$$
Applying a similar argument to the set $T$ we obtain:
$$C \ge 2y + 3(t - y) = 3t - y.$$
Now, let us sum up the cut-degree over all nodes of $G$ with cut-degree 2. By observation 2 we never count an edge of the cut twice. Hence
$$C \ge 2x + 2y.$$
By summing up these 3 inequalities with appropriate weights we obtain:
$$5C \ge 2(3s - x) + 2(3t - y) + 2x + 2y = 6(s + t) = 6n.$$
This gives us $C \ge \lceil 6n/5\rceil$. Proof of the Lemma is finished.


What are the limitations of dependent typing?

One obvious missing feature from most dependent type theories is the ability for substructural reasoning.

The guarantees given by systems like Agda and Coq tend to be very extensional, that is they enforce properties about the values of the computations, rather than their operation. Some obvious things we might want to track about the operation of an algorithm:

Runtime
Space usage
Which resources they "own", e.g. which files they are allowed to access without risk of a race condition

All these things (and more!) become possible with various flavors of substructural types. This seems to be an important active research subject in the PL community.

A possible reference is Wadler, Linear Types can Change the World!

Note that using "deep embeddings", it is possible to enforce some of these properties in a standard dependent types system, see e.g. Brady & Hammond Resource-safe Systems Programming with
Embedded Domain Specific Languages.


Tardos Function Counterexample to Blum's $P\neq NP$ Claim

so these remarks imply that the Tardos function $f$ is the same as
  CLIQUE.

Short answer - NO.

It is only a monotone "clique-like": accepts all $k$-cliques, and rejects all  complete $(k-1)$-partite graphs. It can, however, accept some graphs rejected by CLIQUE: graphs $G$ with $\omega(G) < k$ but $\chi(G)\geq k$ (so-called "non-perfect" graphs). The paper by Grötschel,
Lovász and Schrijver implies that $f$ has a non-monotone circuit of polynomial size. But, according to Theorem 6 in the "proof", any monotone clique-like Boolean function requires non-monotone circuits of super-polynomial size.
So, one of these two papers must be wrong. The GLS-1981 paper stood for already > 35 years  ...

What Tardos does is the following. She starts from the graph function $\varphi(G):=\vartheta(\overline{G})$, where $\vartheta$ is the famous Lovász' theta-function. The fundamental fact is that the number
$\varphi(G)$ is sandwiched between the clique number and the chromatic number: $\omega(G)\leq \varphi(G)\leq \chi(G)$.
She then uses the fact that $\vartheta(G)$ can be approximated in polynomial time. Based on this, she defines a graph-function $\phi(G)$ with the following properties:

 Values of $\phi(G)$ can be computed in polynomial time (in the number $n$ of vertices).
 $\phi$ is monotone: adding edges can only increase its value.
 $\omega(G)\leq \phi(G)\leq \chi(G)$ holds for all graphs $G$.

Then (as Clement C. notes) she defines the desired monotone Boolean function $f$ as: $f(G)=1$ iff $\phi(G)\geq k$. By (1), the function has a (non-monotone) circuit of polynomial size. By (2), $f$ is a monotone Boolean function. By (3),
$f$ accepts all $k$-cliques, and rejects all complete $(k-1)$-partite graphs.

See here for technical details.


What formalisms exist to describe the translation of an abstract syntax tree into another formal language?

Look at Bob Harper's book. It provides loads of declarative formalisms for specifying programming language semantics and so forth. Chapter 6 describes declaratively how to translate concrete into abstract syntax. You could use the same ideas to translate one language into another.

Following Harper (and many others), you could write rules defined inductively on the structure of your source syntax, as follows:

$\begin{array}{c}
a \leadsto e \qquad b \leadsto f \qquad x=foo(a,b,e,f) \\
\hline
\mathsf{K}~a~b \leadsto \mathsf{S}~e~f~x
\end{array}
$

Here $\mathsf{K}$ is a constructor in your source language and $\mathsf{S}$ is in your target language. $foo$ is some function which may compute other required information (it too could be defined as a set of rules).
The translation function/relation essentially inductively decomposes your source syntax and produces a term in your target. You can also thread through additional information to help with the translation process. For example, your rule could look like:

$\begin{array}{c}
E'\vdash a \leadsto e \qquad E''\vdash b \leadsto f \qquad x=foo(E,E',E'',a,b,e,f) \qquad E' = \cdots
\qquad E''=\cdots \\
\hline
E\vdash \mathsf{K}~a~b \leadsto \mathsf{S}~e~f~x
\end{array}
$

Here $E$ can store any information that needs to be threaded through.

Note that such specifications differ very little from a standard recursive function defined inductively in the program syntax. But they may be easier to read, and they may actually define a relation, rather than a function, by allowing a little nondeterminism.


Longest path in a DAG that's not too long

This is NP-hard by reduction from subset sum.    There is a vertex for each element of the

set and one more vertex.    The extra vertex has an outgoing edge to each other vertex

but no incoming edges, and otherwise there is an edge from x to y if and only if  x < y .

The weight of each edge is equal to that edge's terminal vertex.

However, one can topologically sort the vertices and then use dynamic programming

in a way that's similar to the dynamic programming algorithm for subset sum.


Prefix Dictionary Problem in External Memory

You might store $\Theta(B)$ children in every node of a trie with alphabet size $\Theta(B)$ by treating your binary sequences as strings over an alphabet each letter of which takes $\Theta(\lg B)$ bits. This will waste space if your string set is sparse, but I think inserts and prefix searches require $(n/\lg B)$ I/Os in the worst case where $n$ is the length of the longest unique prefix (in the case of insert) or the length of the prefix searched for.

To find the longest sequence with a certain prefix, store with each child pointer the length of the longest descendant string.

If the number of strings you plan to store is $o(2^n)$, you might also be interested in the string B-tree. Insert takes $O(n/B + \log_B k)$ I/Os in the worst-case for a string of length $n$ in a tree containing $k$ strings. Prefix search takes $O((p + occ)/B + \log_B k)$ I/Os in the worst-case, where $p$ is the length of the prefix to search and $occ$ is the number of results of the search. These are both larger than your requested bound ($O(p/B)$ or $O(n/B)$ in this notation), and prefix search isn't exactly what you're looking for, it sounds like, but I think storing the longest descendant length will work in this case.


What's the proof of this lemma by Hajnal about the randomized query complexity of monotone graph properties?

I sent an email to Péter Hajnal, and he kindly confirmed that the bound in the lemma should be $\Omega(\frac{\Delta_L(G)}{\lceil \delta_L(G) \rceil} n)$.


Random walk and mean hitting time in a simple undirected graph

I have decided to ask David Wilson himself, soon thereafter got a reply:

  For undirected graphs on $n$ vertices, the worst case mean hitting time is $\Theta(n^3)$. The example is the barbell graph, which consists of two cliques of size $n/3$ connected by a path of length $n/3$. I don’t know what the worst constant is. The [Brightwell-Winkler] paper looks at (expected) hitting times $H(x,y)$ started at $x$ and ending at $y$.  The mean hitting time is the average of $H(x,y)$ for fixed $x$ and random choices of $y$ from the stationary distribution of a random walk.  It’s a nice fact that this doesn’t depend on $x$. I learned about hitting times from the Aldous-Fill book, which is unfinished but on the web.

There is even a proof of this fact in the abovementioned book, which goes like this:

To construct a graph on $n=2n_1+n_2$ vertices, start with two complete graphs on $n_1$ vertices. Distinguish vertices $v_l \neq v_L$ in one graph ("the left bell") and vertices $v_R \neq v_r$ in the other graph ("the right bell"). Then connect the graphs via a path $v_L - w_1 - \cdots w_{n_2} - v_R $.

Then it is informally argued that it takes mean time about $n_1$ to hit $v_L$ and from there, there's chance $\frac{1}{n_1}$ to hit $w_1$, so it takes mean time about $n_1^2$ to hit $w_1$. From $w_1$ there is chance about $\frac{1}{n_2}$ to hit the right bell before returning into the left bell, so it takes mean time about $n_1^2 n_2$ to enter the right bell.

Setting $n_1 = n_2 = n/3$ gives us mean time $O(n^3)$.

Admittedly, I'm lost at the point they state:

  From $w_1$ there is chance about $\frac{1}{n_2}$ to hit the right bell before returning into the left bell.

But to ease my mind, I ran a simulation of random walks on barbell graphs constructed this way, between vertices picked from the stationary distribution. Indeed, the mean hitting time fitted very nicely to a curve $\frac{(n+1)^3}{54}$.

However, comments on the informal proof are still welcome.


n irrational number whose digits are pseudo-random: conceptual mismatch?

TL;DR The decimal expansion of a fixed rational number is not pseudorandom in the cryptographic sense, but irrational numbers (are conjectured to) exhibit some weaker but interesting forms of pseudorandom behavior.

Roughly speaking, a sequence $s \in \{0, \ldots, B\}^n$ is pseudorandom with respect to distinguishers $\cal A$, if it cannot be distinguished (with non-trivial probability) from a uniformly random sequence sampled from $\{0, \ldots, B\}^n$ by any algorithm $A$ in a class of algorithms $\cal A$. Usually in cryptography, $\cal A$ is the class of polynomial-time algorithms or polynomial-size circuits. Then it is easy to see that any sequence that can be generated in polynomial time by a deterministic algorithm is not pseudorandom: the distinguisher just simulates the generator. For this reason, pseudorandom generators in cryptography are randomized, and we speak of a pseudorandom distribution rather than a fixed pseudorandom sequence.

However, there are weaker notions of pseudorandomness (corresponding to more restricted classes $\cal A$ of distinguishers) that the expansion of an irrational number in an integer basis might satisfy. For example, $\sqrt{2}$, $e$, and $\pi$ are conjectured to be normal, which is a kind of pseudorandomness: each pattern of $k$ digits in base $B$ appears with frequency $1/B^k$, in the limit. This is like pseudorandomness with respect to distinguishers which can only ask "approximately how often does this pattern appear in the expansion of $\sqrt{2}$?" However, at the moment we are unable to prove normality for any of the above fundamental constants, in any base, even though it is conjectured they are absolutely normal, i.e. normal in every base. This is a famous open problem.

Something that we understand better is sequences like $(k\sqrt{2} \bmod 1)_{k = 1}^\infty$ ($x \bmod 1$ just means the fractional part of $x$). By Weyl's ergodicity criterion, we know that for any Lebesgue integrable function $f$, the average
$$
\overline{f}_n = \frac{1}{n-1}\sum_{k = 0}^{n-1}{f(k\sqrt{2} \bmod 1)},
$$
converges to the expectation $\mathbb{E}[f(x)]$, where $x$ is a uniformly sampled random number from $[0, 1]$. We also have deviation estimates: for $f$ the indicator function of an interval $I = [a, b]$, $a, b \in [0,1]$, the average $\overline{f}_n$ deviates from the expectation $b-a$ by $O((\log n)/n)$ in the worst case, and by $O(\sqrt{\log n}/n)$ on most intervals $[a, b]$ ("most" is measured by the natural product measure). Moreover, Beck has recently shown a central limit theorem, which quantifies the statement that numbers $n$ for which the deviation is large are very rare. For an intro to  the pseudorandomness properties of these sequences, check section 2.3. of Chazelle's discrepancy book.


DPLL can be modified to count model, i.e. to solve #SAT. So yes, you can modify the Abstract DPLL for #SAT.

However, AFAIK DPLL is not state-of-the-art for #SAT, so a DPLL-based framework is neither important nor useful. The Abstract DPLL is useful because it covers most state-of-the-art DPLL-based SAT solvers.

You can take a look at these following papers:

1) Counting Model using Connected Components. It is implemented in the tool RelSAT.

2) On Compiling CNF into Decision-DNNF. CNF is compited into DNF to count model. The authors have a tool, c2d, implementing this approach.


Is PARITY in QAC_0 (if that even makes sense)

The question makes sense, and the short answer is that it's an open problem.

Here's the long answer: Depending on how you define constant-depth unbounded-fanin quantum circuits, you might get different classes. QAC0 is usually defined to have unbounded fanin Toffoli gates and single-qubit gates. QAC0wf is the class where we also allow a "fanout" gate, which copies an input bit to many outputs. (It implements |a>|0>...|0> --> |a>|a>...|a>) This class is really powerful since it contains, besides PARITY and AC0, also ACC0 and TC0.

So the obvious question to ask is whether PARITY is contained in QAC0, and this is an open problem. It is equivalent to asking whether QAC0 = QAC0wf. I guess that the belief is that PARITY is not in QAC0. Further information can be found in the survey Small depth quantum circuits by Bera, Green and Homer.


Computational hardness for sampling a uniform matching

Concerning your general question, I think the paper by Aaronson and Arkhipov [1] on boson sampling is a good example. They show that if there exists a classical poly-time algorithm that exactly (or at least "extremely accurate" as they state it) samples from a certain distribution, then the polynomial hierarchy collapses up to some level.

To prove the same thing for an approximate sampling algorithm, they must rely on some unproven conjectures.

[1] Aaronson, Scott, and Alex Arkhipov. "The computational complexity of linear optics." Proceedings of the forty-third annual ACM symposium on Theory of computing. ACM, 2011.


Solving Feedback Vertex Set (FVS) in FPT time $5^k$ with iterative compression?

I found the solution, it is also mentioned in the book in chapter 4.1.

We start by taking a subgraph with $k+1$ arbitrary vertices instead of the whole graph, so the whole vertex set is a $k+1$-solution. Then we do DFVS with every subset to obtain a $k$-solution. Finally we add another vertex from the original graph to our current subgraph (and current solution) and repeat.

Thus each step takes $5^kpoly(n)$ time and we do $n$ iterations.


Why is complementary slackness important?

Complementary slackness is key in designing primal-dual algorithms. The basic idea is:

Start with a feasible dual solution $y$.
Attempt to find primal feasible $x$ such that $(x, y)$ satisfy complementary slackness.
If step 2. succeeded we are done. Otherwise an obstruction to finding $x$ gives a way to modify $y$ so that the dual objective function value increases. Repeat.

A classical example is the Hungarian algorithm. The Ford-Fulkerson algorithm can be seen as another example. Note that step 2. is a feasibility problem which often is easier than the original optimization problem, and also often can be solved combinatorially. This is the power of complementary slackness. For example, in the case of minimum cost bipartite matching, step 2 amounts to checking if there exists a perfect matching
using only tight edges. In the case of maximum $s$-$t$ flow, step 2 amounts to checking if the saturated edges separate $s$ and $t$.

Primal-dual algorithms are nice for many reasons. Philosophically, they provide more insight than a generic algorithm. They usually give strongly polynomial time algorithms, whereas we still do not have strongly polynomial LP solvers. They are often more practical than generic algorithms. This is especially true if we cannot write down the LP explicitly and our only other choice is the ellipsoid algorithm, which is the case with non-bipartite matching and Edmonds' primal-dual algorithm.

Primal-dual is also a very useful framework for approximation algorithms, by using relaxed versions of complementary slackness. This has been useful in designing approximation algorithms for NP-hard problems (see e.g. Chapter 7 of the Williamson-Shmoys book) and in designing online algorithms with good competitive ratio (see the book by Buchbinder and Naor). The point here is that the algorithm maintains a solution $y$ to the dual of the LP relaxation of a hard problem, and at each step either finds an integral primal feasible $x$ such that approximate complementary slackness is satisfied, or improves the dual solution $y$. Approximate complementary slackness is a condition of the following form: if $x_i > 0$ then the corresponding dual constraint is tight, and if $y_j > 0$, the corresponding primal constraint would be tight if $x$ is scaled by $\alpha$. This gives an approximation factor $\alpha$. It's all very nicely explained in the above two sources.


Can all unambiguous grammars be parsed in linear time?

Unambiguous context-free parsing is in $O(n^2)$ using Earley's algorithm.  Whether there exists a parsing algorithm working in linear-time on all the unambiguous context-free grammars is an open problem.  One of the most advanced statements of this kind is due to Leo [1991], who showed that a variant of Earley parsing works in linear time for all LRR grammars.

[Leo 1991] Joop M. I. M. Leo.  A general context-free parsing algorithm running in linear time on every LR($k$) grammar without using lookahead, Theoretical Computer Science 82(1):165--176. doi: 10.1016/0304-3975(91)90180-A


Goodrich's "Randomized Shellsort: A Simple Oblivious Sorting Algorithm" has a discussion of data-oblivious sorting. Sorting networks are data-oblivious, but impractical in general, as I understand it.


Does $NP=PP$ collapse the counting hierarchy?

We have
$$\mathrm{PP^{NP}\subseteq PP^{ModPH}\subseteq P^{PP}},$$
thus by the assumption,
$$\mathrm{PP^{PP}\subseteq PP^{NP}\subseteq P^{PP}\subseteq P^{NP}\subseteq NP}$$
as under the assumption, NP closed under complement. This implies $\mathrm{CH=NP}$.


4CT is equivalent to:

Coloring a hypergraph induced by a finite family of discs (not necessarily interior disjoint but also discs that might have arbitrary overlaps) with at most four colors $[1]$.
The proposition that every planar triangulation with more than three vertices is the union of two connected bipartite graphs, each with no isthmus $[2]$.
A combinatorial problem about the three-dimensional vector cross product algebra $[3]$.
The proposition that the grammar G is totally ambiguous $[4]$.
For any positive integer $n$, there exists at least a signable path joining two permutations of $S_n$.
An algebraic equivalent of the four-color theorem is presented. The equivalent is the assertion of non-membership of a family of polynomials in a family of polynomial ideals over a particular finite field $[6]$.

Smorodinsky S. On the chromatic number of geometric hypergraphs.
Mabry R. Bipartite Graphs and the Four-Color Theorem.
Kauffman L.H. Map coloring and the vector cross product.
Cooper B. J. et al. Toward a language theoretic proof of the four color theorem.
Eliahou S. et al. Signed permutations and the four color theorem.
Howard L. An Algebraic Reformulation of the Four Color Theorem.


Lower bound on the largest restrained cubic subset

These subsets of grids, and your graph-theoretic interpretation of them, are studied in my paper

The complexity of bendless three-dimensional orthogonal graph drawing.
D. Eppstein.
J. Graph Algorithms and Applications 17 (1): 35–55, 2013.
http://dx.doi.org/10.7155/jgaa.00283

I don't think I included the quadratic example suggested in daniello's answer in this paper, but you can find it in one of my blog posts from ten years ago, https://11011110.github.io/blog/2006/06/09/topology-of-xyz.html (see the ETA at the bottom).

Incidentally, the same construction (points with coordinate sum 0 or 1) in the 3d integer lattice, without the mod $n$ part, produces a lattice embedding of the hexagonal tiling of the plane. Doing the same thing in 4d, similarly, produces a lattice embedding of the 3d diamond lattice. See another of my papers:

Isometric diamond subgraphs.
D. Eppstein.
16th Int. Symp. Graph Drawing, LNCS 5417, 2009, pp. 384–389.
https://arxiv.org/abs/0807.2218


PromiseBQP and expectation values of operators

Aaronson is working within a particular context, but if you take his statement in an absolute sense, you're right to be skeptical.

  Translated into “physics language,” the question is this: suppose we had an efficient classical algorithm to estimate the expectation value of any observable in quantum mechanics.

This is technically imprecise. PromiseBQP and BQP, as you no doubt understand, are concerned with sampling states that are constructed with polynomial-sized (uniform families of) circuits. And it's true that if you're talking about 'estimating the expectation value of any observable',  this seems to include ANY quantum state which may generally require an exponential number of gates to construct.

However, the concerns of a complexity theorist preclude much worrying about such 'exponentially' constructable quantum states. In any 'quantum experiment,' if a state evolves from a particular pure quantum state in a set amount of time t, the expectation value of its observables will be very close to some state that can be constructed from a circuit with a polynomial number of gates.

That is, the complexity theorist paradigm of 'experiments deal with polynomial time constructable states' is realistic for experimental physics in all contexts that I'm familiar with.


Is there a candidate for a post-quantum one-way group action?

Yes, there is an old proposal for this due to Couveignes, which was independently rediscovered by Rostovtsev and Stolbunov.

In both cases, the set of elliptic curves with some common endomorphism ring $\mathcal O$ is acted on by the ideal class group of $\mathcal O$. The secret key is essentially a description of an isogeny via its kernel ideal, and the action of a group element $[\mathfrak a]$ takes a curve $E$ to the codomain of said isogeny:
$$
    ([\mathfrak a], E) \longmapsto E/\mathfrak a = E/\bigcap_{\alpha\in\mathfrak a}\ker\alpha
    \text.
$$
There is a nice graph-walking interpretation of this action, which is described (for instance) in Section 14.1 of Luca De Feo's lecture notes. (They also contain more of the background necessary to understand this construction!)

While it is possible to invert the group action by solving an instance of the hidden-shift problem, giving rise to a subexponential quantum attack, the system remains unbroken for reasonably big parameter sizes.
A much bigger problem is that these schemes are painfully slow in practice: Even after considerable optimization effort, one computation of the group action still takes minutes.

The performance issue has been tackled by a recent proposal called CSIDH by switching to supersingular elliptic curves, which drastically improves efficiency while keeping essentially the same underlying structure. It is still slow relative to comparable pre-quantum schemes, as well as incomparable post-quantum schemes, but may have a place in a post-quantum world due to its unique features.


research on systematically attacking multiple instances of undecidable problems

Let's say an algorithm A solves a "special case" of the decision problem L if on input x, $A(x)$ always either outputs the correct answer $L(x)$, or outputs "?".
These algorithms (which may be randomized) are sometimes called "errorless heuristics" and have been studied in complexity theory, esp. average-case complexity; see e.g. this paper of Watson and references therein.

A basic question you can ask about a very difficult decision problem is whether it contains any nontrivial easy cases.  E.g. if L is decidable, is there any (deterministic) errorless heuristic A for L that solves $L(x)$ on infinitely many inputs?  This has been explored in the notion of immunity (along with co-immunity, bi-immunity, simplicity and others) in computability theory.  See e.g. this wiki article.  Complexity-theoretic analogues have been studied as well.

Since you mention multiple instances, I might also interpret the question as looking for research into algorithms which, given instances $x^1, \ldots, x^m$ for a decision problem (i.e. language) L, compute some partial information about the membership/nonmembership of the given strings in $L$.

One of the earliest and most influential works of this type was by Jockusch, who in his dissertation and this 1968 paper defined "semi-recursive" languages.  L is semi-recursive if there is a computable "selector" function that, given instances $x^1, x^2$, selects one of these two strings as being "logically more likely" to lie in L.  That is, we require that whenever at least one of $x^1, x^2$ lie in L, the string selected by the selector lies in L.

The study of polynomial-time analogues of this concept was initiated by Selman in this 1979 paper.  Since then there has been tons of work on "p-selective" languages (the polytime version of semi-recursive languages) along with "membership comparable" languages and many other related concepts.  I can't summarize all this work, but consult e.g. this article of Beigel, Fortnow, and Pavan, and this book of Hemaspaandra and Torenvliet.  The concept of bounded queries in computability and complexity is also related, see this survey by Gasarch.


Sampling from Multivariate Gaussian with Graph Laplacian (inverse) Covariance

There are two separate issues here.

How to use efficient solvers for $Ax=b$ in order to apply $A^{1/2}b$.
How to compute the determinant.

The short answers are 1) use rational matrix function approximations, and 2) you don't, but you don't need to anyways. I address both of these issues below.

Matrix square root approximations

The idea here is to convert a rational function approximation for scalar functions into a rational function approximation for matrix functions.

We know that there exist rational functions that can approximate the square root function extremely well,
$$\sqrt{x} \approx r(x) := \frac{a_1}{x+b_1} + \frac{a_2}{x+b_2} + \dots + \frac{a_N}{x+b_N},$$
for positive $b_i$. Indeed, to get high accuracy on the interval $[m,M]$, you need $O(\log \frac{M}{m})$ terms in the series. To get the appropriate weights ($a_i$) and poles ($-b_i$), just look up rational function approximation online or in a book.

Now consider applying this rational function to your matrix:
$$r(A) = a_1(A + b_1 I)^{-1} + a_2(A + b_2 I)^{-1} + \dots + a_N(A + b_N I)^{-1}.$$

Owing to the symmetry of $A$, we have
\begin{align}
||A^{1/2} - r(A)||_2 &= ||U\left(\Sigma^{1/2} - r(\Sigma)\right)U^*||_2, \\
&= \max_i |\sqrt{\sigma_i} - r(\sigma_i)|
\end{align}
where $A = U \Sigma U^*$ is the singular value decomposition (SVD) of $A$. So, the quality of the rational matrix approximation is equivalent to the quality of the rational function approximation at the location of the eigenvalues.

Denoting the condition number of $A$ by $\kappa$, we can apply $A^{1/2}b$ to any desired tolerance by performing $O(\log \kappa)$ positively shifted graph Laplacian solutions of the form,
$$(A + bI)x=b.$$

These solutions can be done with your favorite graph Laplacian solver—I prefer multigrid type techniques, but the one in the paper you cite should be fine, too. The extra $bI$ only helps the convergence of the solver.

For an excellent paper discussing this, as well as more general complex analysis techniques that apply to nonsymmetric matrices, see Computing $A^α$, $\log(A)$, and related matrix functions by contour integrals, by Hale, Higham, and Trefethen (2008).

Determinant "computation"

The determinant is harder to compute. As far as I know, the best way is to compute the Schur decomposition $A = Q U Q^*$ using the QR algorithm, then read off the eigenvalues from the diagonal of the upper-triangular matrix $U$. This takes $O(n^3)$ time, where $n$ is the number of nodes in the graph.

However, calculating determinants is an inherently ill-conditioned problem, so if you ever read a paper that relies on computing determinants of a large matrix, you should be very skeptical of the method.

Luckily, you probably don't actually need the determinant. For example,

To draw samples from a single Gaussian distribution $N(0,A^{-1})$, the normalization constant is the same at all points so you never need to compute it.
If your Laplacian matrix $A = A_x$ represents the inverse covariance of a local Gaussian approximation at point $x$ to a non-Gaussian distribution, then the determinant does indeed change from point to point. However, in every effective sampling scheme I know (including Markov chain Monte Carlo, importance sampling, etc.) what you really need is the determinant ratio,
$$\det(A_{x_0}^{-1}A_{x_p}),$$
where $x_0$ is the current point, and $x_p$ is the proposed next sample.

We can view $A_{x_0}^{-1}A_{x_p}$ as a low-rank update to the identity,
$$A_{x_0}^{-1}A_{x_p} = I + Q D Q^*,$$
where the effective numerical rank, $r$, of the low-rank update is a local measure of how non-Gaussian the true distribution is; typically this is much lower than the full rank of the matrix. Indeed, if $r$ is large, then the true distribution is locally so non-Gaussian that one ought to question the whole strategy of trying to sample this distribution using local Gaussian approximations.

The low-rank factors $Q$ and $D$ can be found with randomized SVD or Lanczos by applying the matrix
$$A_{x_0}^{-1}A_{x_p} -I$$
to $O(r)$ different vectors, each application of which requires one graph Laplacian solution. Thus the overall work for getting these low rank factors is $O(r \max(n,E))$.

Knowing $D = \text{diag}(d_1,d_2,\dots,d_r)$, the determinant ratio is then
$$\det(A_{x_0}^{-1}A_{x_p}) = \det(I + Q D Q^*) = \exp\left(\sum_{i=1}^r \log d_i\right).$$

These low rank determinant ration calculation techniques can be found in A Stochastic Newton MCMC Method for Large-Scale Statistical Inverse Problems with Application to Seismic Inversion, by Martin, et al. (2012). In this paper it is applied to continuum problems, so the "graph" is a grid in 3D space and the graph Laplacian is the actual Laplacian matrix. However, all the techniques apply to general graph Laplacians. There are probably other papers applying this technique to general graphs by now (the extension is trivial and basically what I just wrote).


Are there any books containing collections of automata problems?

Sort of indirectly, this book is about research level automata problems:

http://www.amazon.ca/Automatic-Sequences-Theory-Applications-Generalizations/dp/0521823323

An automatic sequence is essentially a set of strings which can be computed by a DFA.


Find a boundary from set of 3d line segments

For each segment extract the two endpoints (remembering which segment they came from), now sort the endpoints by (say) lexicographical ordering. Any two endpoints that are the same are now adjacent. so, scan the sorted list, attache adjacent segments that share endpoints, and then read the cycle by following the resulting list like structure among the segments.
One can improve the running time to linear using hashing and the floor function, etc.


Are there poly time algorithms to determine if a graph is almost bipartite?

The vertex version is called "odd cycle transversal"; it's NP-complete but fixed-parameter tractable. See:

Yannakakis, Mihalis (1978), "Node-and edge-deletion NP-complete problems", Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78), pp. 253–264, doi:10.1145/800133.804355.

Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Finding odd cycle transversals", Operations Research Letters, 32 (4): 299–301, doi:10.1016/j.orl.2003.10.009.

Hüffner, Falk (2005), "Algorithm engineering for optimal graph bipartization", Experimental and Efficient Algorithms: 240–252, doi:10.1007/11427186_22.

The edge version has been called "edge bipartization"; it's also NP-complete but fixed-parameter tractable. See:

Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization", JCSS 72 (8): 1386–1396, doi:10.1016/j.jcss.2006.02.001.

(added following daniello's comment):

Odd cycle transversal has an $O(\sqrt{\log n})$ approximation algorithm, but (assuming the Unique Games Conjecture) no constant-factor approximation; see (references copied from "On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal" by Jansen and Kratsch):

Agarwal, Amit, Charikar, Moses, Makarychev, Konstantin, Makarychev, Yury, $O(\sqrt{\log n})$ approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems, STOC'05, pp. 573–581.

Khot, S., On the power of unique 2-prover 1-round games, STOC '02, pp. 767–775.

Wernicke, S., On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems. Master’s thesis, Wilhelm-Schickard-Institut für Informatik, U. Tübingen (2003)


What you are looking for is known as Cutwidth. The problem is NP complete and quite well studied. For example it has a $O((\log n)^{3/2})$- approximation algorithm and is fixed parameter tractable when parameterized by the objective function value.


Are there applications of modular graph decomposition in TCS/complexity theory?

Habib and Paul did a great survey on the algorithmic applications of graph modular decomposition.

In our recent result that shows parameterized tractability of INTERVAL DELETION problem (to remove at most $k$ vertices from the give graph to make it into an interval graph), graph modular decomposition does plays an important role. This problem does receive a lot of interest in the parameterized complexity community (though not in the tradition complexity community), and the problems related to graph classes are the most natural candidates of applications of graph modular decomposition.

However, I am not aware of any application of graph modular decomposition in proofs of lower bounds, and I doubt its applicability on the negative side (only a personal biased view).

A final remark.  As far as I know, most algorithmic applications do not use the full power of graph modular decomposition.  For instance, critical cliques are the series modules at the second level of a modular decomposition tree (the first level consists of every single vertex); and twins are (not necessarily strong) modules made of two adjacent vertices.