Short answer: yes! You don't need that much machinery to get the proof to go through.

One subtlety: it seems on the face of it that there is a use of the excluded middle: one builds a set $D$ and a number $d$, and shows that either $d\in D$ or $d\not\in D$ which leads to a contradiction. But there is a lemma, true in intuitionistic logic, that states:

$$ \mbox{ for all statements } P, (P\iff \neg P) \Rightarrow \bot$$

This suffices, along with the usual proof. Note that in general "surjection" may have some subtle nuance in constructive/intuitionistic logic (without choice) so you have to make due with "right invertible" instead.

A very standard proof in Coq (which for some reason I couldn't find online) might go as follows:

Inductive right_invertible {A B:Type}(f : A->B):Prop :=
| inverse: forall g, (forall b:B, f (g b) = b) -> right_invertible f.

Lemma case_to_false :  forall P : Prop, (P <-> ~P) -> False.
Proof.
  intros P H; apply H.
    - apply <- H.
      intro p.
      apply H; exact p.
    - apply <- H; intro p; apply H; exact p.
Qed.

Theorem cantor :  forall f : nat -> (nat -> Prop), ~right_invertible f.
Proof.
  intros f inv.
  destruct inv.
  pose (diag := fun n => ~ (f n n)).
  apply case_to_false with (diag (g diag)).
  split.
  - intro I; unfold diag in I.
    rewrite H in I. auto.
  - intro nI.
    unfold diag. rewrite H. auto.
Qed.

Of course, the "right" framework in which to think about these maters, which can be seen as the minimal requirements for this proof to go through, is Lawvere's fixed point theorem which states the the theorem holds in every Cartesian Closed Category (so in particular, in any reasonable type theory).

Andrej Bauer writes beautifully about this theorem in the paper On fixed-point theorems in synthetic computability, and I suspect might have some interesting things to add to this answer.


Temporally Flat One-Way Quantum Computing

It doesn't make sense to me to ask about non-commuting operators being implemented in a single time step (though constant depth certainly makes sense). However, you can implement non-commuting gates on the logical subspace of an MBQC which are implemented using commuting measurements on the resource state, though the implemented gates are not deterministic.

Actually, I believe you are viewing IQP more narrowly than you probably should. The answer to your question is that any MBQC which can be implemented in a single measurement layer in MBQC is contained in IQP. This is simply because rather than expressing the result in terms of the logical Hilbert space, you can express it as a series of commuting operations on the physical qubits. Shepherd and Bremner actually deal with this in their paper (in section 5.2 where such operations are called graph-programs).


This is equivalent to the biclique partition number of a bipartite graph. You can think of M as representing a bipartite graph $G$ on $[n] \times [m]$ in the natural way: $M_{i,j}$ is 1 if and only if there is an edge $(i,j)$ in G (where $i$ is an element of the left partition, and $j$ an element of the right partition). Then $M$ has binary rank $r$ if and only if the edges of the corresponding bipartite graph $G$ can be partitioned into $r$ complete bipartite subgraphs. To see this, take an optimal factorization $M = UV^\intercal$, denote the columns of $U$ by $u_1, \ldots, u_r$, and the columns of $V$ by $v_1, ..., v_r$. $M=UV^\intercal$ is equivalent to $M = \sum_{i = 1}^r{u_i v_i^\intercal}$, and $u_i v_i^\intercal$ represents a complete bipartite graph on the vertices $S_i \cup T_i$, where $S_i$ is the set of left vertices for which $u_i$ is the indicator vector, and $T_i$ is the set of right vertices for which $v_i$ is the indicator vector.

Computing the biclique partition number is NP-hard, and hard to approximate. See these two papers for some results and references: [1], [2].


What is the best and easy (regarding implementation) way of computing three edge independent trees in a 3-connected graph?

The problem can be reduced to the edge orientation problem. Where if tree width (number of independent trees) is c, we need to orient the edges such that each vertex has an outdegree of at most c.

For planar graphs, where c = 3, an O(n log n) algorithm is given by [1]. For general graphs, a simple O(m + n) time algorithm computing a (2c - 1) orientation is shown in [2]. Other algorithms computing exact c orientation are harder including [3] and [4].

[1] Grossi and Lodi. Simple planar graph partition into three forests. Discrete Applied Mathematics, 84:121-132, 1998.

[2] Srinivasa R. Arikati, Anil Maheshwari, and Christos D. Zaroliagis. Efficient computation of implicit representations of sparse graphs. Discrete Applied Mathematics, 78:1-16,1997.

[3] Harold N. Gabow and Herbert H. Westermann. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica, 7:465-497, 1992.

[4] J. C. Picard and M. Queyranne. A network flow soloution to some non-linear 0-1 programming problems, with applications to graph theory. Networks, 12:141-160, 1982.


The two-connected series-parallel DAGs are also called 2-terminal series-parallel graphs. The graph in the figure is also known as Wheatstone graph and is known as the example graph for demonstrating Braess' paradox in algorithmic game theory.
It was shown [1, Theorem 5.3] that a DAG is 2-terminal series-parallel if and only if it does not contain a subgraph that is homeomorphic to the Wheatstone graph.
1 Pietro Cenciarelli, Daniele Gorla, Ivano Salvo: Inefficiencies in network models: A graph-theoretic perspective. Information Processing Letters 131 (2018) 44–50.


In the Hott book, are the most of the type formers redundant? And if so, why?

You are asking several questions which are similar but distinct.

Why doesn't the HoTT book use Church encodings for data types?

Church encodings do not work in Martin-Löf type theory, for two reasons.

First, MLTT is predicative. There is a universe hierarchy, and each type lives at a particular universe level, and a type at level $n$ can only quantify over types at smaller universe levels $k < n$. Church encodings like in System F or the CoC require impredicative quantification, where you can instantiate quantifiers with types which are the same size, or even bigger.

Second, even if you defined datatypes like the natural numbers with Church encodings, to do proofs with these types, you need induction principles to prove things about them. To derive induction principles for Church encodings, you need to use an argument based on Reynolds' parametricity, and the question of how to internalize parametricity principles into type theory is still not fully settled. (The state of the art is Nuyts, Vezzosi, and Devriese's ICFP 2017 paper Parametric Quantifiers for Dependent Type Theory -- note that this is well after the HoTT book was written!)
Next, you are asking why the foundation is not minimal. This is actually one of the distinctive sociological features of type-theoretic foundations -- type theorists regard having a small set of rules as a technical convenience, without much foundational significance. It's far, far more important to have the right set of rules, rather than the smallest set of rules.

We develop type theories to be used by mathematicians and programmers, and it's very, very important that the proofs done within type theory are the ones that mathematicians and programmers regard as being done in the right way. This is because the arguments mathematicians typically regard as having good style typically are structured using the key algebraic and geometrical principles of the domain of study. If you have to use complicated encodings then much structure is lost or obscured.

This is why even type-theoretic presentations of propositional classical logic invariably give all the logical connectives, even though it is formally equivalent to a logic with just NAND. Sure, all the boolean connectives can be encoded with NAND, but that encoding obscures the structure of the logic.


Is this variation of TQBF still PSPACE-complete?

It is an Unordered Constraint Satisfaction game and it is PSPACE-complete and it has been proved to be PSPACE-complete only recently;
a proof can be found in:

Lauri Ahlroth and Pekka Orponen, Unordered Constraint Satisfaction Games.
Lecture Notes in Computer Science Volume 7464, 2012, pp 64-75.

Abstract: We consider two-player constraint satisfaction games on systems of Boolean constraints, in which the players take turns in selecting one of the available variables and setting it to true or false, with the goal of maximising (for Player I) or minimising (for Player II) the number of satisfied constraints. Unlike in standard QBF-type variable assignment games, we impose no order in which the variables are to be played. This makes the game setup more natural, but also more challenging to control. We provide polynomial-time, constant-factor approximation strategies for Player I when the constraints are parity functions or threshold functions with a threshold that is small compared to the arity of the constraints. Also, we prove that the problem of determining if Player I can satisfy all constraints is PSPACE-complete even in this unordered setting, and when the constraints are disjunctions of at most 6 literals (an unordered-game analogue of 6-QBF).

From the content:

...
Our generic example of an unordered constraint satisfaction game is the Game on
Boolean Formulas (GBF). An instance of this game is given by a set of m non-constant
Boolean formulas $C = \{c_1,...,c_m\}$ over a common set of n variables $X = \{x_1,...,x_n\}$.
We refer to the formulas in $C$ as clauses even though we do not in general require them
to be disjunctions.
...
A game on $C$ proceeds so that on each turn the player to move selects one of the
previously nonselected variables and assigns a truth value to it. Player I starts, and
the game ends when all variables have been assigned a value. In the decision version
of GBF, the question is whether Player I has a comprehensive winning strategy, by
which she can make all clauses satisfied no matter what Player II does. In the positive
case we say that the instance is GBF-satisfiable. ..

...
Theorem 4: The problem of deciding GBF-satisfiability of a Boolean formula is PSPACE-complete.

EDIT: Daniel Grier's has found out that the result was also settled by Schaefer in the '70s, see his answer on this page for the reference (and upvote it :-). Schaefer proved that the game is still PSPACE-complete even if restricted to positive CNF formulas (i.e. propositional formulas in conjunctive normal form in which no negated variables occur) with at most 11 variables in each conjunction.


Three questions about finite state machines

No there are some FSA which are irreducible, I believe the 2 state 3 input FSA you give is the flip-flop, every reducible FSA can be made by this one. Start by looking here and the references given http://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory


Tree-decomposition with clique interfaces

See "Decomposition by clique separators", Robert E. Tarjan, Discrete Mathematics 55 (2): 221–232, 1985.

If I understand correctly, your notion of width is essentially the size of the largest piece in Tarjan's decomposition.


If $u\cdot v \in (z \cdot z')^*$ and $v \cdot u \in (z' \cdot z)^*$ then $u \in (z \cdot z')^* \cdot z$

The full statement (including the last point) seems to follow directly from the proof of Proposition 1.3.3 in (Lothaire '83).  The last point is part of the proof: using the notation in the original post, the proof states that $u = (z \cdot z')^{k_1} \cdot z$ and $v = z' \cdot (z \cdot z')^{k_2}$ for some $k_1$ and $k_2$ such that $k_1+k_2+1 = c$.  Perhaps the proof of this proposition could be cited...?


The source of the modular decomposition graph

Upon the suggestion of Louis Esperet, I contacted Philippe Gambette  and Christophe Paul, who confirmed promptly. Paul designed this graph for his Habilitation thesis. When they created a Wikipedia page for modular decomposition, they used this graph. Maybe it's the beginning of its wide adaption. It's also featured in the well known survey of Michel Habib and Christophe Paul (DOI:10.1016/j.cosrev.2010.01.001).

Some nice properties of this graph include:

it is a permutation graph
its prime node (the bull) is a prime graph containing a vertex that avoids every induced P4. When such a node exists, it is unique.


Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?

I do not know if you are interested in hearing more detail of my comment on your question, but here is more detail anyway.

If P=NP, every problem in NP can be solved in polynomial time and therefore in pseudo-polynomial time, which means that no problem satisfies your requirement, as Magnus noted in his answer.  So assume P≠NP in the rest of this answer.

Because P≠NP, there exists a language L∈NP∖P which is not NP-complete (Ladner’s theorem).  Consider the following problem:

Direct product of Partition and L
Instance: m positive integers a1, …, am and k integers b1, …, bk∈{0,1}.
Question: Do both of the following hold?
(1) The m integers a1, …, am form a yes-instance of the Partition problem.
(2) The k-bit string b1…bk belongs to L.

Following the paper by Garey and Johnson, define the Length function as m+⌈log maxi ai⌉+k and the Max function as maxi ai.

It is a routine to check (i) that it is NP-complete in the weak sense, (ii) that it does not have a pseudo-polynomial-time algorithm, and (iii) that it is not NP-complete in the strong sense.

(Hints: (i) Membership to NP follows from the fact that both the Partition problem and L are in NP.  For NP-hardness, reduce Partition to this problem.  (ii) Construct a pseudo-polynomial transformation from L to this problem.  (iii) Construct a pseudo-polynomial transformation from this problem to L by using the fact that Partition has a pseudo-polynomial-time algorithm.)

There is nothing special about the Partition problem in this construction: you can use your favorite weakly NP-complete problem with a pseudo-polynomial-time algorithm.


Are there any implementations of a graph crossing algorithm?

A slow brute-force implementation of the graph crossing number
was added to Sage in

Sage Trac ticket 24216: Add crossing number of a graph

which was closed 2018-01-05, and merged in Sage 8.2.beta3.


Efficient randomness reduction using k-wise independence

Yes.  You can generate a random polynomial of degree $k$, then evaluate this polynomial at $n$ different points in $\tilde{O}(n)$ time using the DFT (the DFT lets you evaluate a polynomial of degree $n$ at $n$ different points in $\tilde{O}(n)$ time).


Reference for the shortcomings of Google's PageRank algorithm?

to answer your specific question, there are many papers that discuss PageRank mathematically, such as:

Deeper Inside PageRank, (A. N. Langville and C.D. Meyer), Internet Mathematics (1), 335–400 (2004)

and in each one you might find discussion of computational and operational issues (computing it faster, using memory more efficiently), but I don't know of any that stand out as addressing shortcomings of -results- specifically.
to answer what you're getting at ("why does google not give me what I want without trying?")

google search does not equal PageRank (though PR is a major part of it)
PageRank itself doesn't address lexical ambiguity
Google's additions try to address multiple meanings of words (different meanings under different contexts), and synonyms (other strings that mean the same thing); they're not perfect, but more and more they are being addressed.


Optimal comparison-based stable sorting in constant space

Mergesort satisfies all three requirements (when merging is performed in place).
See Pardo, L.T., "Stable  sorting  and  merging  with  optimal  space  and  time
bounds", SIAM J. Comput. 6 (1977), 351-372.


Algorithm for ranking members of a regular language?

Let $A = \{1, ..., k\}$ be an ordered alphabet. Then each word on $A^*$ can be viewed as a number in base $k + 1$ (note that $0$ is never used on purpose). Now define
$$
rank(u) = \begin{cases}
u &\text{if $u \in L$} \\
0 &\text{otherwise}
\end{cases}
$$
Then $rank$ preserves the shortlex (or radix) order, which is the order $\leqslant$ on $A^*$ defined by $u \leqslant v$ if and only if $|u| < |v|$ or $|u| = |v|$ and $u \leqslant_{lex} v$. That is, words are first ordered by length and words of equal length are ordered according to the lexicographic order. Now, if $L$ is regular, $rank$ is easy to compute and is of course one-to-one on $L$.


See this answer to an earlier question for a bridgeless cubic graph in which the longest path is only polylogarithmically long.


In my understanding, algebraic data types are basically types whose terms arise as the terms freely constructed by an algebraic specification: the operations of this specification being the term-constructors.

From this point of view, it seems to me that the only possible structures you can represent with algebraic data types are the free ones, that is those algebraic structures where no axiom is required: for instance magmas.

Observe that the fact you can represent free-monoids (that is monoids of strings/lists) as algebraic data types comes from the fact that lists are  ADTs for the algebraic specification with a $0$-ary operation (namely $\text{Nil}$ or $[]$) and a binary operation ($cons$ or $(:)$).

Until you work constrained in the setting of simple types you cannot add constraints (that is equations) in your data-types, hence you cannot represent more general algebraic structures.

A possible way to solve this problem is to use dependent type systems with an identity type: in these type-systems you can represent algebraic structures because equations(constraints) becomes terms (they are the same as programs).

Hope this helps.


Purely(ish) functional data structure with fast append and forward iteration

You're quite right that the "queue = two lists" approaches don't give you the running time you want when you have the ability to re-use earlier versions.  To get O(1) running time (amortized or worst case), you need a way to reverse the rear list and append it to the front list incrementally.  Instead of doing the reverse&append all at once, taking O(N) time, you need to be able to do just a few steps of the reverse&append every time you add a new element or remove/traverse through an element.

Hood and Melville showed one way to do this back in 1980.  For your purposes, their approach would be straightforward to adapt to C (with reference counting).

In the early to mid 90's, I showed several ways to do this, some in O(1) worst-case time and some in O(1) amortized time. Most of these ways depended on lazy evaluation, which initially might seem hard to do in C, but in fact, there are only a very small of "shapes" needed for the lazy evaluation, each of which would be easy to represent using an ordinary node in C.

For example, a "Rotate" node has pointers to three sublists: L, R, and A.  Doing one step of the rotation replaces the "Rotate" node with an ordinary list node containing the head of L, and a pointer to a new Rotate node containing the tail of L, the tail of R, and the result of adding the head of R to the front of A.  Making this translation into explicit Rotate nodes instead of using generic lazy evaluation also means that you get O(1) worst-case bounds instead of O(1) amortized bounds.


Efficiently generate list of lightest intervals of a vector

You can build the whole table using the following $O(n^2)$ construction:

1: 1   1   0 z:0 w:1   2   1   0   0   0   1
2:   2   1   0   1   3   3   1   0   0   1
3:   y:2   1   1   3   4 v:3   1   0   1
4:     x:2   2   3   4 u:4 ...
5:        ...
...

At every step you are calculating the value $x$ at the top of a "reversed triangle", and the value is simply the sum of an adjacent element in the previous row ($y$ in the figure) and the opposite vertex at the base of the triangle ($z$ in the figure).

*         z
 ...   ...
   y   *
     x
x = y + z

or equivalently:

w         *
 ...   ...
   *   v
     u
u = v + w

For each row the difficulty is given by the lower element of that row.


Yes, it is very common. Once we spent months thinking about a problem we start to see relations so well that the solution looks trivial to us. It is not specific to academia, once we have a solution for a problem it makes the problem look easier that it really was, all the clouds that prevented us from seeing it have disappeared.

How to deal with this feeling? I haven't figured out myself but a few observations that might help:

Remind yourself what seems obvious to you is not for many others. How many people in your broad area saw the solution beforehand?

For most results (and most results are not break through results) I think it is the case that someone else in our field who is smart enough could have figured it out as well. This also has an effect that we feel we are not so special after all. Well, we are not! Once we accept that there are others who are smart enough and deal with our ego and become humbler we tend to have higher satisfaction from our contributions. Yes, X, Y, and Z could have done it as well. But we were the person who put the effort to actually do it.

Another one is to pay more attention to what problem we decide to work on. Be very clear with yourself why you want to work on a problem. Don't do so just because it looks interesting or difficult or others say it is interesting. How would knowing the solution to the problem affect our understanding and world? If we are clear about that then the fact that the solution to the problem looks simple wouldn't bother us, it would delight us instead. This might be difficult though for a student, you have to pick a problem that is meaningful and solvable. It is harder in more pure areas than applied sides. And often we don't end up solving the real meaningful problem but make some meaningful advance towards it. Keep in mind that is also valuable. Even our failures can be valuable if we can share the insights we obtained from them with others.

There is also how others judge our contribution. It is will known some areas of theory have a problem of valuing technical heavy lifting more than some meaningful contributions. Don't let them discourage you. In the long term, most of those technical heavy liftings will be forgotten, don't allow the facade to discourage you from working on meaningful problems.

Lots of young researchers focus on proving themselves. Focus instead on building good and meaningful collaborations with others to work on meaningful problems. That is much more important in the long term. With some luck you will end up with some significant meaningful contribution.


Is there a proof that addition is faster than multiplication?

No.

No unconditional better lower bound than the trivial $\Omega(n)$ is currently known for integer multiplication. There are some conditional lower bounds though. For more on this, you can have a look at Martin Fürer's paper Faster Integer Multiplication.

Edit following Andrej's comment: Addition can be done in time $\mathcal O(n)$. In comparison, the best known upper bound for multiplication is (approximately) $\mathcal O(n\log n)$. On the other hand, no non trivial lower bound is known for multiplication, thus there is no proof that addition is faster than multiplication yet. As (too) often in complexity theory, we just don't know!


Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?

Kolloiopoulos and Young give an $O(\log m)$ approximation for general covering integer programs. See the paper below.
http://www.sciencedirect.com/science/article/pii/S0022000005000656


Data structure that allow efficient tag based lookups

This is not exactly an answer of an efficient data structure, but rather an elaboration on the comments of @bbejot and @Kaveh giving a hand-waving argument for why given the current question we should not expect something that does a lot better than searching the whole database. The argument is based on a reduction from SAT, the exponential time hypothesis, and a lot of hand-waving.

Assume we have upto $n$ different tags, then we can think of each id as being associated with a bitvector $x$ of length $|x| = n$ where $x_j = 1$ if we have the $j$-th tag, and $x_j = 0$ otherwise. Since there is no real restrictions on what the database looks like, I can assume it has ids $1$ through $2^n$ with the $k$-th id having an associated tag vector of $k$ written in binary. The order fields can be arbitrary, since they only make the problem harder. Now, if we are given an arbitrary query of $AND$, $OR$, and $NOT$s then this is just asking a SAT question on $n$ variables. By the exponential time hypothesis, we can't expect this to be much faster than $2^n$... or in other words, we can't expect this to be much faster than searching the whole database.

We shouldn't expect efficient search in the length of the query (by reduction to SAT). We also shouldn't expect much better than looking at all the items in the database by the exponential time hypothesis.

To hope for an efficient data-structure for this question, we will have to make some serious assumptions on the structure of the database that are not made in this question. For instance, if we assume a special structure on the queries (such as CNF) then we can hope for something more efficient. An alternative assumption is on the structure of the database. We could probably assume that given $n$ tags, only a small fraction of the tags will be present on any given id (say a logarithmicly few $1$s). This is not an unreasonable assumption given the application of tagged questions (what use are tags if almost every single tag is used for a question).


Comparison-based data structure for finding items

Here's a proof that it's impossible. Suppose you could build such a data structure. Build it. Then choose $n/\log n$ items at random from the list, add $\epsilon$ to each of them, where $\epsilon$ is smaller than the difference between any two items on the list, and perform the queries to check whether any of the resulting items is in the list. You've performed $O(n)$ queries so far.

I would like to claim that the comparisons you have done are sufficient to tell whether an item $a$ on the original list is smaller than or larger than any new item $b$. Suppose you couldn't tell. Then, because this is a comparison-based model, you wouldn't know whether $a$ was equal to $b$ or not, a contradiction of the assumption that your data structure works.

Now, since the $n/\log n$ items you chose were random, your comparisons have with high probability given enough information to divide the original list into $n/\log n$ lists each of size $O(\log n)$. By sorting each of these lists, you get a randomized $O(n \log \log n)$-time sorting algorithm based solely on comparisons, a contradiction.


I'm not sure if I understand the problem specification correctly, but the problem looks a special case of the paint shop problem.  In that context, there is an NP-hardness result.

The main reference is: P. Bonsma, Th. Epping, and W. W. Hochstättler, Complexity results on restricted instances of a paint shop problem for words.  Discrete Applied Mathematics 154 (2006) 1335-1343.  http://dx.doi.org/10.1016/j.dam.2005.05.033

The abstract says as follows.

  We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of its letters such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters.

  This is a special case of the paint shop problem for words, which was previously shown to be NP-complete. We show that this special case is also NP-complete and even APX-hard. Furthermore, derive lower bounds for this problem and discuss a transformation into matroid theory enabling us to solve some specific instances within polynomial time.


No.
Consider block matrices $A = \left(\begin{matrix} 0 & 0 \\ 0 & X \end{matrix}\right)$ (with symmetric $X$) and $B = \left(\begin{matrix} 0 & Y \\ 0 & 0 \end{matrix} \right)$. Computing $AB^T$ from $A$, $B$ and $AB$ means computing $XY^T$ from $X$ and $Y$, since $AB = 0$


One apparent strength of his approach is that it allows higher-order functions (i.e. lambda terms) to be observable outcomes, which measure theory generally makes quite tricky. (The basic problem is that spaces of measurable functions generally have no Borel $\sigma$-algebra for which the application function - sometimes called "eval" - is measurable; see the intro to the paper Borel structures for function spaces.) Scott does this using a Gödel encoding from lambda terms to natural numbers, and working directly with the encoded terms. One weakness to this approach may be that the encoding could be difficult to extend with real numbers as program values. (Edit: This is not a weakness - see Andrej's comment below.)

Using CPS seems to be primarily for imposing a total order on computations, to impose a total order on access to the random source. The state monad should do just as well.

Scott's "random variables" seem to be the same as Park's "sampling functions" in his operational semantics. The technique of transforming standard-uniform values into values with any distribution is more widely known as inverse transform sampling.

I believe there's just one fundamental difference between Ramsey's and Scott's semantics. Ramsey's interprets programs as computations that build a measure on program outputs. Scott's assumes an existing uniform measure on inputs, and interprets programs as transformations of those inputs. (The output measure can in principle be computed using preimages.) Scott's is analogous to using the Random monad in Haskell.

In its overall approach, Scott's semantics seems most similar to the second half of my dissertation on probabilistic languages - except I stuck with first-order values instead of using a clever encoding, used infinite trees of random numbers instead of streams, and interpreted programs as arrow computations. (One of the arrows computes the transformation from the fixed probability space to program outputs; the others compute preimages and approximate preimages.) My dissertation's chapter 7 explains why I think interpreting programs as transformations of a fixed probability space is better than interpreting them as computations that build a measure. It basically comes down to "fixpoints of measures are way complicated, but we understand fixpoints of programs pretty well."


Is education for research-based CS at odds with that of industrial CS?

I struggled with the same question while pursuing my undergrad in CS. I performed a fair amount of research, but currently work as a software engineer. I can tell you that for the most part, you won't do too much theoretical CS in the industry (assuming a typical SE, not something tailored for R&D or the like). You may want to consider looking into R&D positions after graduating, should you decide not to pursue a career in academia.

The learning routes do definitely differ (although this is university-specific), but the principles learned can be used in either setting. Certain classes (Compilers, Automata Theory, etc.) may not seem like they have a place in the typical industry for software engineers, but you'd be surprised just how much they come into play.

The biggest difference that you should be prepped for is the difference in "soft" classes. Software engineers are often expected to interface directly with customers, nontechnical managers, and the like, while researchers/professors generally rub shoulders with their own kind in the workplace. As a SE, you get a lot more face time than many CS people are prepared for.


Applications of Barendregt–Geuvers–Klop conjecture

I'm not (exactly) an expert, but my understanding is that there are very few practical applications of this conjecture, except possibly simplifying the decision procedure for type-checking in normalizing theories, by allowing one to choose any reduction strategy with confidence.

My feeling about this conjecture is that it is an important litmus test on our understanding of normalization proofs in general, which at the moment (though this is rapidly changing) are somewhat ad hoc.

In particular, weak normalization proofs seem remarkably simpler, possibly due to weakly normalizing terms having the structure of a Partial Combinatory Algebra, which is not the case for strongly normalizing terms, as explained at length in a '93 paper by Hyland and Ong. Even simpler are proofs of existence of normal forms, which are the result of applying the technique of Normalization by Evaluation, which, IMO, are the "conceptually correct" proofs.

Given the difference of these 3 notions (SN, WN, existence of normal forms), one might be surprised that we have no examples of "natural" type systems where they don't all coincide (though for the latter 2, one can simply reason about the combinatorics of reductions). In the limited case of PTSes, this is what the BGK conjecture asks.

A satisfying resolution to the question would explain why a proof of WN or NbE can be promoted to a proof of SN, possibly by building a notion of normalization model which coincides in the case of PTSes. This desire for understanding is the principal motivation for the conjecture.


Complexity of selective network improvement problem

Reduction from Set Cover. Suppose the Set Cover instance has sets $S_1,\ldots,S_m$ which are subsets of a universe $U$ of $n$ elements, and an integer $k$. The problem is to decide if the elements of $U$ can be covered by using at most $k$ sets from $\{S_1,\ldots,S_m\}$. Create a directed graph with a node for each set $S_i$ and a node for each element in $U$ and a set is connected by an arc to an element iff that element is in that set (these arcs have a capacity of $1$ each). Add a source node $s$ and connect it to each set $S_i$ with an arc of capacity $|S_i|$. Add a sink node $t$ and arcs connecting each element to $t$ (the capacity if $1$ and cost is $0$). The arc $(s,S_i)$ has cost $1$ and if we improve it the cost becomes $0$. The other arcs have cost $0$ so there is no point improving them. The claim is that there is a feasible cover of size $k$ in the Set Cover instance iff one can select $k$ arcs to improve so that the resulting graph has an $s$-$t$ flow of $n$ with cost $0$. This is not hard to see. One can use lower bounds on a $(t,s)$ arc to enforce a flow of $n$ between $s$ and $t$.


The Drawing Challenge - a problem I made up and can't solve!

A closely related problem is strongly NP-hard.

Leung et al. [1] prove that the following decision version of your problem is strongly NP-complete, by reduction from 3-Partition.

  Is it possible to pack $n$ squares of given widths $w_1, w_2, \dots, w_n$ into a larger square of width $W$?

I misread the original question as a generalization of the following decision problem:

  Is it possible to pack $n$ rectangles with given areas $a_1, a_2, \dots, a_n$ into a $H\times W$ rectangle?

The first problem can be reduced to the second as follows: Squares with widths $w_1,\dots,w_n$ can be packed into an outer square of width $W$ if and only if the minimum-perimeter packing of rectangles with areas $w_1^2, \dots, w_n^2$ into a $W\times W$ rectangle uses precisely $4\sum_i w_i$ units of ink.  (Proof: The minimum-perimeter rectangle with any given area is a square.)

However, this reduction does not imply that the actual posted question is NP-hard.

Joseph Y-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin.  Packing squares into a square.  J. Parallel and Distributed Computing 10(3):271–275, 1990.


Conductance and diameter in regular graphs

As Hsieh notes, your definition of conductance is off from the one I know by a factor of $d$, where $d$ is the degree of the regular graph. This is also known as edge expansion for regular graphs.

A relationship between edge expansion and diameter is quite easy to show. Intuitively, an expander is "like" a complete graph, so all vertices are "close" to each other. More formally, let

$$
\min_{S \subseteq V}\ { \frac{ e(S, S^c) }{ d \cdot \min\{|S|, |S^c|\} }} \geq \alpha
$$

Take any set of vertices $S$ with $|S| \leq |V|/2$. There are at least $\alpha d |S|$ edges coming out of $S$ and since $G$ is $d$-regular, the neighborhood of $S$ (including $S$ itself) is of size at least $(1+\alpha)|S|$. Applying this claim inductively, starting from $S = \{u\}$ for any vertex $u$, we see that for some $t = O(\log_{1 + \alpha } |V|)$, $u$'s $t$-hop neighborhood has size at least $|V|/2$. Therefore, the $t+1$-hop neighborhood of any vertex $v$ has to intersect the $t$-hop neighborhood of $u$, or the graph would have more than $|V|$ vertices, a contradiction. So you have

$$
D = O\left(\frac{\log |V|}{\log (1 + \alpha)}\right)
$$

Of course, it also follows that having a lower bound on the diameter implies an upper bound on edge expansion.

I don't think small diameter implies conductance. If you don't insist on regular graphs (and use Hsieh's definition), then two complete graphs connected by a single edge provides a counterexample.


Are there local maxima in the number of moves required to solve a Rubik's Cube?

Asking Tomas Rokicki this question immediately yielded the correct answer ("yes, local maxima exist"):

  If a position exhibits total
  symmetry, it is of necessity a local
  maximum (all except the start).  A
  little thought should make it clear
  why this is the case in the QTM [quarter-turn metric].  For
  the HTM [half-turn metric] it's a bit more subtle but not
  too bad.

  ...

  Such a position is pons asinorum,
  which is distance 12 in QTM and
  distance 6 in HTM (U2D2F2B2L2R2).

I don't see why this is the case for the half-turn metric; but for
the quarter-turn metric it is clear.  In a position with total symmetry, all neighboring positions must be at the same path length (since all moves are equivalent by symmetry).  So a position with total symmetry must be either a local maximum or a strict local minimum.  But strict local minima cannot exist... there has to be some move that reduces the distance to the solved state, just by the definition of the distance.  The symmetry argument translates to the $n \times n \times n$ cube, as does the example position provided.


Finding a prime greater than a given bound

The current best unconditional result was given by Odlyzko,  which finds a prime $p >N$ in $O(N^{1/2 + o(1)})$ time. The strong conjecture in Polymath4 project seeks to resolve if this can be done in polynomial time, under reasonable number-theoretic assumptions like the GRH.

http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

Currently the project seeks to answer the following question:

  Given a number $N$ and an interval between $N$ and $2N$, check in time $O(N^{1/2 - c})$ for some $c>0$ if the interval contains a prime.

So far, they have a strategy which determines the parity of the number of primes in the interval.

http://polymathprojects.org/2010/06/29/draft-version-of-polymath4-paper/


Are there any applications of techniques in real analysis to theoretical computer science?

Here are two related courses:

Analytical methods in combinatorics and CS by Ehud Friedgut at University of Toronto (2009),
Analytical Methods in Combinatorics and Computer-Science by Irit Dinur and Ehud Friedgut at Hebrew University (2006).

Also check Ryan O'Donnell's notes for his book:

Analysis of Boolean Functions by Ryan O'Donnell.

and the links on the top right corner.


Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?

This is impossible. No finite number of bits of $f(a_0,\dots,a_n)$ suffices to determine any of $a_0,\dots,a_n$; in fact, any nondegenerate real interval contains the values $f(a_0,\dots,a_n)$ for infinitely many vectors $(a_0,\dots,a_n)\in\mathbb Z^{n+1}$, and this holds even you fix all but two of the $a_0,\dots,a_n$ in advance.


Is Bayes optimal RL of a finite set of DFAs feasible?

Even determining whether there is a policy which always succeeds is NP-complete, by a reduction from constructing optimal decision trees (Hyafil and Rivest, Constructing Optimal Binary Decision Trees is NP-complete). We interpret the word $w$ as a sequence of $m-1$ yes/no questions about $k$, drawn from a list of allowed questions, followed by a guess for the value of $k$. It's easy to construct state machines $\delta_k$ which keep a counter of how many questions have been asked so far together with the answer to the most recent question asked as their state, and then accept or reject based on whether the guess at the end is correct.


Alas, you can't force people to do what the protocol says they should do.

Even well-meaning people who intended to follow the protocol occasionally make mistakes.

There seem to be at least 3 approaches:

crypto theory: assume "good" agents always follow the protocol, while "malicious" agents try to subvert the protocol. Design the crypto protocol such that good agents get what they need, while malicious agents get nothing.
game theory: assume every agent looks out only for his own individual interest. Use mechanism design to maximize the total benefit to everyone.
distributed fault-tolerant network: assume every agent makes an occasional mistake, and a few 'bot agents spew out many maliciously-crafted messages. Detect and isolate the 'bot nodes until they are fixed; use error detection and correction (EDAC) to fix the occasional mistake; use convergent protocols that eventually settle into a useful state no matter what initial mis-information is stored in the routing tables.

mechanism design
In game theory, designing a situation (such as setting up the rules of an auction) such that people who are selfishly looking out only for their own individual interests end up doing what the designer wants them to do is called "mechanism design".
In particular, using implementation theory, situations can be designed such that the final outcome maximizes the total benefit to everyone, avoiding poorly-designed situations such as the "tragedy of the commons" or "prisoner's dilemma" where things happen that are not in anyone's long-term interest.

Some of the most robust such processes are designed to be incentive compatible.

The game theory typically makes the simplifying assumption that all relevant agents are "rational".
In game theory, "rational" means that an agent prefers some outcomes to other outcomes, is willing and able to change his actions in a way that he expects (given the information available to him) will result in a more preferred outcome (his own narrow self-interest), and he is smart enough to realize that other rational agents will act similarly to try to obtain the outcome that is most preferred out of all the possible outcomes that might result from that choice of action.

A designer may temporarily make the simplifying assumption that all people only act according to their own narrow self-interest.
That assumption makes it easier to design a situation using implementation theory.
However, after the design is finished,
it doesn't matter whether people act according to their own narrow self-interest ( "Homo economicus" ),
or whether they are altruistic and want to maximize the total net benefit to everyone -- in a properly designed situation, both kinds of people make exactly the same choices and the final outcome maximizes the total benefit to everyone.

convergent protocols

When designing a routing protocol,
each node in the network sends messages to its neighbors passing on information about what other nodes are reachable from that node.

Alas, occasionally these messages have errors.
Worse, sometimes a node is mis-configured and spews out many misleading and perhaps even maliciously-crafted messages.

Even though we humans know the message might be incorrect, we typically design the protocol so that a properly-functioning node trusts every message and stores the information in its routing table, and makes its decisions as if it believes that information to be entirely true.

Once some human turns off a bad node (or disconnects it from the network), we typically design the protocol to rapidly pass good information to flush out the corrupt information, and so quickly converge on a useful state.

combined approaches

Algorithmic mechanism design
seems to try to combine the fault-tolerant network approach and the game-theory mechanism approach.

@Yoichi Hirai and Aaron, thank you for pointing out some interesting attempts to combine game theory and cryptography.


Kth best problem that is NP-hard for K polynomial

Here is an example of something fairly contrived, but which might be a good starting place for reductions to other problems:

Input:  a boolean formula $\phi$ and a satisfying assignment $x$.
Goal:  find a satisfying assignment $y$ to $\phi$ which has as few variables set to true as possible, but at least as many variables set to true as in $x$

This (well, its decision variant) is obviously in $\mathsf{P}$ ($x$ is itself a solution), but finding the next-best assignment (forcing $y \ne x$) is $\mathsf{NP}$-hard: you can force all satisfying assignments to an arbitrary formula to have a superfluous 1, and then plant the all-zeros assignment. You can also fairly easily plant as many (polynomially many, possibly more if you're clever) assignments as you want.


Reference for checking primitive recursiveness

This is known as a Ritchie-Cobham property, or a honesty property of primitive-recursive functions.  See for instance Theorem VIII.8.8, page 297 in P.G. Odifreddi, Classical Recursion Theory, vol. 2, 1999.

Odifreddi refers to

Kleene, General recursive functions of natural numbers, Math. Ann. 112:727--742, 1936,
Cobham, The intrinsic computational difficulty of functions, Log. Meth. Phil. Sci. 2:24--20, 1964,
Meyer, Depth of nesting and the Grzegorczyk hierarchy, Not. Am. Math. Soc. 12, 1965.


It is shown to be $\oplus P$-complete by Faben:
https://arxiv.org/abs/0809.1836
See Thm 3.5. Note that counting independent sets is same as counting solutions to monotone 2CNF.


The Optimum Strategy to Find the Best Parking Slot Along a Busy Road

Like some of the commenters, I'm not sure the problem as written is fully specified, especially with respect to inferring the probability of future spaces being empty.  However, even if you assume that all spaces are empty with known probability $p$, the problem is still interesting.  Much of the reasoning below still applies to the case where the probability is inferred, and the solution should become exact as the number of pre-parking observations goes to infinity.

Question. Assume that parking spaces $-k, -k+1, … -1, 0, 1, 2, 3, ...$ are filled independently with probability $1-p$.  You pass each space in turn and note whether it is filled or empty.  If a parking space is empty, you may choose to park there; but once you pass a space, you may not go back.  You want to park as close to space $0$ as possible.  What strategy minimizes the expected value of $|X|$, where $X$ is the space in which you park?

Answer. You should park in the first available space $x$ such that $x \ge \lceil\log(2) / \log(1-p)\rceil$.

Proof.
Let $Q(x)\equiv E\left[ |X| \big| X>x\right]$ be the expected penalty given that you have passed space $x$.  Clearly you will accept any parking space $x$ such that $x \ge 0$, since at that point each candidate is better than all future possible candidates.  So we can calculate $Q(x)$ for $x \ge -1$ as follows:

$$
\begin{eqnarray}
Q(x \ge -1) &\equiv& E\left[ |X| \big| X > x \ge -1 \right] \\
&=& E[\text{position of first empty space after } x] \\
&=& x + 1/p
\end{eqnarray}
$$

For spaces $x$ with $x < 0$, you will park (if possible) whenever $-x$ (the current penalty) is no greater than $Q(x)$ (the expected penalty if you keep driving); i.e., you will park when the function $D(x) \equiv Q(x)+x \ge 0$.  For $x<-1$, we have:

$$
\begin{eqnarray}
D(x) &\equiv& Q(x)+x \\
&=& p\min\left\{-(x+1), Q(x+1)\right\} + (1-p)Q(x+1) + x \\
&=& Q(x+1) - p \max\left\{0, Q(x+1) + x + 1\right\} + x \\
&=& -1 + Q(x+1) + x + 1 - p\max\left\{0, Q(x+1)+x+1\right\} \\
&=& -1 + D(x+1) - p\max\left\{0, D(x+1)\right\}.
\end{eqnarray}
$$

As long as $D(x+1) \ge 0$, we have $D(x) = -1 + (1-p)D(x+1)$.  This recurrence relation has the closed-form solution

$$
\begin{eqnarray}
D(-n) &=& -1 - (1-p) - (1-p)^2 - ... -(1-p)^{n-1} + (1-p)^n D(0) \\
      &=& (1-p)^n /p - \left(1 + (1-p) + ... + (1-p)^{n-1}\right) \\
      &=& (1-p)^n /p - \left(1 - (1-p)^n\right) / p \\
      &=& \left(2(1-p)^n - 1\right) / p,
\end{eqnarray}
$$
valid until $D(-n)$ becomes negative, after which $D(-n) = -1 + D(-(n-1))$, and so $D$ continues to become increasingly negative as you move to the left.  Moving to the right, then, the first parking space for which $D(x) \ge 0$ is at $x = \lceil\log(2) / \log(1-p)\rceil$.


Other applications of Karger-Stein branching amplification?

@JeffE,  Here is a paper that counts min weight cycles in a graph. As far as I remember, it was definitely inspired by Karger's technique/result and it was a fun proof.  Hope this helps with the teaching.


Phase transition in counting feasible solutions to knapsack problems?

I don't have a reference for you, just a minor remark that is too large for a comment.

We assume $w$ is chosen as follows.  Choose r.v. $x\in[0,1]^n$ uniformly at random (i.e., each $x_i$ is i.i.d. uniformly in $[0,1]$), then set $w_i = x_i/X$, where $X=\sum_j x_j$.  Then with high probability, almost all sets $S$ will have $\sum_{i\in S} w_i \sim 1/2$:

Lemma 1. Let r.v. $w$ be chosen as above.  With probability $1-e^{-n/6}$, for all $\epsilon\in[0,1]$, among the subsets $S\subseteq\{1,\ldots,n\}$, the fraction satisfying $$\textstyle\Big|1/2 - \sum_{i\in S} w_i\Big| \ge \epsilon$$ is at most $2 e^{-n\epsilon^2/4}$.

Proof. For any $x$, and $X=\sum_{i=1}^n x_i$ as described above,
note that $E[X] = n/2$, so by a standard Chernoff bound the probability of the event $X\le n/4$ is at most $e^{-n^2/6}$.
So, with probability at least $1-e^{-n^2/6}$, $X\ge n/4$.

Now fix any $x$ and $w$ with $X\ge n/4$, and fix $\epsilon>0$.  To complete the proof we bound the fraction of subsets $S$ such that $|1/2 - \sum_{i\in S} w_i| \ge \epsilon$.

This fraction equals the probability that $|1/2 - \sum_{i\in S} w_i| \ge \epsilon$ for a random subset $S\subseteq \{1,\ldots,n\}$.

Because $w=x/X$, the condition $|1/2 - \sum_{i\in S} w_i| \ge \epsilon$
is equivalent to $|X/2 - \sum_{i\in S} x_i| \ge \epsilon X$.

Note that $E_S[\sum_{i \in S} x_i] = X/2$,
so by a standard Chernoff bound
$$\Pr_S\big[|X/2 - \textstyle\sum_{i\in S} x_i| \ge \epsilon X\big] \le 2\exp(-X\epsilon^2) \le 2\exp(-n\epsilon^2/4).$$
(The last step uses $X\ge n/4$.) $~~\Box$

We don't have to choose $w$ randomly to get the bound.
Any $w$ with $\max_i w_i = O(1/n)\sum_i w_i$ will do.

Note that the result implies a sharp threshold in the following sense:
for any $c > 1/2$, almost all sets $S$ will satisfy the given knapsack inequality $\sum_{i\in S} x_i \le c$.
For any $c < 1/2$, almost none will.


What math courses should I revisit to prepare for a CS Ph.D. (Reinforcement learning and Game Theory)?

Know linear algebra well, say, at the level of Peter Lax' book (start with the first 9 chapters). Also, some basic real analysis and probability theory should be a good place to start.


Oblivious Turing Machine emulation lower bound

As mentioned above, it is not known in general if there is a faster oblivious simulation.

But interesting lower bounds for this problem are known, under more constrained conditions. For instance, what if you want an oblivious simulation that preserves not only the time $t$ but also the space usage $s$? Beame and Machmouchi have recently proved an interesting time-space tradeoff lower bound for this problem: either the space must increase by a factor of $n^{1-o(1)}$, or the time must increase by a factor of $\Omega(\log n \cdot \log \log n)$.

The paper is here: http://eccc.hpi-web.de/report/2010/104/


Visualizing the parse structure of a range concatenation grammar

Edit: answer obeying the "spirit" of the question:

Let's use the rules
$$S(xy)\to A(x,y)$$
$$A(x,ayb)\to A(x,x)A(y,y)$$
$$A(x,x)\to\epsilon$$
Then we can derive $S(aabb)\to A(a,abb)\to A(a,a)A(b,b)\to\epsilon$.
In this case the parse tree is:

  $$
\begin{eqnarray*}
&S(aabb)\\
&\downarrow \\
&A(a,abb)\\
&\swarrow\quad\searrow \\
&A(a,a)\quad A(b,b)\\
&\searrow\quad\swarrow \\
&\epsilon\\
\end{eqnarray*}
$$

Original answer obeying the "letter" of the question:

Using @MarzioDeBiasi's grammar
$$\begin{eqnarray*}S(xyz)&{\color{red}\rightarrow}&A(x,y,z),\\
A(ax,by,cz)&{\color{green}\rightarrow}&A(x,y,z),\\
A(a,b,c)&{\color{blue}\rightarrow}&\epsilon,\end{eqnarray*}$$
the picture is:

  $$\begin{eqnarray*}
&S(aaaaabbbbbccccc)\\
&{\color{red}\downarrow}\\
&A(aaaaa,bbbbb,ccccc)\\
&{\color{green}\downarrow}\\
&A(aaaa,bbbb,cccc)\\
&{\color{green}\downarrow}\\
&A(aaa,bbb,ccc)\\
&{\color{green}\downarrow}\\
&A(aa,bb,cc)\\
&{\color{green}\downarrow}\\
&A(a,b,c)\\
&{\color{blue}\downarrow}\\
&\epsilon\end{eqnarray*}$$


No, simple polygons are not any easier than disjoint segments. Given any n disjoint segments, there is a simple polygon with O(n) edges that includes all of the input segments as sides of the polygon. Then, any BSP tree for the polygon forms a BSP tree for the segments.

One way to do construct a polygon for a set of segments would be to triangulate the planar straight line graph formed by the input segments, and then pick a spanning tree of the triangulation, which is necessarily non-crossing. Then form a simple polygon by walking around an Euler tour of the spanning tree, using each of the input segments the first time the Euler tour traverses that edge and a parallel segment near it the second time the tour traverses it.


Is there an efficient construction for a trilinear pairing that has been used in theory or practice

This question has been open for long now, and after some research I think I have the following answer

There has been two candidate schemes proposed for multilinear pairing by Garg, Gentry,  Halevi and Coron, Lepoint, Tibouchi.

However either do not have a security proof and their security is given by extensive cryptanalysis.

So, to sum it up, although it is possible to implement a "trilinear" map, these maps are NOT (provably) cryptographically secure.


Is it possible to evaluate interaction combinators efficiently using a path-traveling strategy?

This has been a subject of investigation for the Implicit Computational Complexity (ICC) community recently.

It is known that in certain cases, when the graph you want to evaluate is of a specific type (be it from typing or a global shape restriction, see references) there is a path-based evaluation strategy that is more efficient than the naive one, allowing for instance to evaluate in Logspace [1,2] or Ptime [3].

The jump approach you mention has been studied by Danos & Regnier [4]. They proved it correct (you get the same output) but do not provide an evaluation of the performance gain. I do not know of any work carrying on this analysis (in full generality) so far.

[1] http://www2.tcs.ifi.lmu.de/~schoepp/Docs/intml_long.pdf

[2] http://arxiv.org/pdf/1406.2110.pdf

[3] http://arxiv.org/pdf/1501.05104v2.pdf

[4] http://ac.els-cdn.com/S0304397599000493/1-s2.0-S0304397599000493-main.pdf?_tid=09e49fd8-768c-11e5-a270-00000aacb360&acdnat=1445278134_7609d8ba21c272fe7eab424d38c3f225


The pumping lemma states that if $L$ is a regular language, then there is an integer $p \geq 1$ (the "pumping length") such that every string $w$ in $L$ of length at least $p$ can be written as $w = xyz$ satisfying (1) $|y| \geq 1$, (2) $|xy| \leq p$ and (3) $(\forall n \geq 0)[xy^nz \in L]$.  (Source: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement)

If $L$ is finite, then one can take the pumping length $p$ to be any integer greater than the length of any string in $L$.  The three conditions above would then be satisfied vacuously because there is no word in $L$ of length at least $p$.


Can the mutual information of a "cell" be negative?

By the simple transformation $p(x_0, y) = p(x_0) p(y | x_0)$ your expression merely becomes $p(x_0) KL(p (y|x), p(y))$, where $KL(p,q)$ is the Kullback-Leibler divergence, and is always positive. therefore, your expression is always positive.


Current research topics in tree automata

Here is a short list of authors that work on the connections between tree automata, logic and databases. For each author, I will just give one paper, but many more can be found on the respective web pages of these authors.

[1] Luc Segoufin

FO2(+1,<.~) on data trees, data tree automata and branching vector addition systems

[2] Nicole Schweikardt

A note on monadic datalog on unranked trees

[3] Mikołaj Bojańczyk

Automata for Data Words and Data Trees.

You may also check Georg Gottlob's work


Shortest number of editing move between two words

I don't know whether this exact problem has been studied, but  Chaudhuri et al. studied the related tandem duplication-random loss problem: you are given a permutation, and you want to transform it into the identity permutation by
 (1)  duplicating a segment of any length and appending the copy right after the original, then (2) deleting elements so that you obtain a new permutation instead of a string. Note that applying (1) then (2) accounts for one operation.

Different variants can be defined according to the weight given to each operation, which in their paper depends on the width of the duplicated segments.
They also study a similar problem with the whole genome duplication, which is exactly the kind of duplication you allow. I don't remember reading about work on this problem in the context of strings, but I hope this can at least give you a starting point for your searches.


The question is quite broad, so my answer will also probably be broad.

Traditional logic is Boolean, in the sense that every sentence evaluates to either true or false.

However, there are many contexts in which satisfaction is not Boolean. Examples of this include probabilistic reasoning (captured by PSL that you mentioned), fuzzy logic, quantitative reasoning, knowledge, belief, and trust representations, and many more.

In many such contexts, "truth" is defined as e.g., a value in $[0,1]$, and this is sometimes referred to as "soft truth values". The interpretation of such values can differ according to the usage. For example, a sentence with truth value $2/3$ can mean "the sentence is true with probability $2/3$" (i.e. it is true in $2/3$ of the models), or it could mean "the belief level I have in this sentence is $2/3$" (for some well defined concept of belief).

Or it could mean something like $2/3$ of the agents in this multiple agent system think the sentence is true (which is used to represent e.g. voting scenarios).

For some self-propaganda, I have some work on the topic of quantitative reasoning in temporal logic which you can use as a starting reference.


Choosing subsets of a set such that the subsets satisfy a global constraint

From my answer at math.stackexchange: https://math.stackexchange.com/questions/3205/choosing-subsets-of-a-set-such-that-the-subsets-satisfy-a-global-constraint/3207#3207

Assuming $m$ is an input, your problem is NP-Complete.

Subset sum can be reduced to it.

Given $A = \\{x_{1}, ..., x_{n}\\}$ for which we need to find a subset of sum $S$, we can create $n$ inputs to your algorithm, with input $A$, $m$ and $p_{L} = p_{U} = \frac{S}{m}$, for $1 \leq m \leq n$.

If $m$ is fixed then the brute force algorithm (which you don't want) is $O(n^m)$ and so has a polynomial time algorithm.

If this does not answer your question, can you please clarify exactly what you need?


Transposition of any characters in Damerau–Levenshtein edit distance computation

Thanks for updating the question - here goes an answer tailored to your application:

Since we are dealing with realatively small instances we could define an optimal algorithm based on a backtracking branch and bound schema (Presentation on B&B - easy, Something more thorough with common application) by constructing a "path" of permutations with following assuptions:

We want to promote swaps to preserve metadata - cost = 1
We want to penilize other operations but allow them if nessesary - cost = 2
Dissalow "stupid" moves ex. Inserting a letter that's not in the target sequence
Innitial Upper Bound = Levensthein (plain version not the Damerau extension) x 2 (because of the costs)
Lower Bound current path cost + how many letters (disregard positions) do not match in current and target sequences Example:
i have ABCCDD
i want CCWGZDD

the cost added to current path is (1 (W) + 1 (G) + 1 (Z) + 2 (D)) = 5
(probably there is room for a better Lower Bound but it's usually non-trivial to come up with one)

Each time you get to target sequence and path cost is lower than Upper Bound - update it and backtrack.
Each time your Lower Bound exeeds Upper Bound - backtrack

Please google backtracking algorithms and branch and bound for more information. Should you like the solution but have no idea how to go about implementing it please let me know (PW) I'll try to cook-up some pseudocode for you.

The algorithm in worst case is exponential but on real istances should perform very well.


Best way to determine if a list of bytes are random?

In TCS, another approach to this problem has been via property testing of distributions, where one is to distinguish whether a distribution is (truly) uniform distribution or is "not even close" to being uniform (in a formal way). Here one gets precise bounds on the number of samples needed to decide on the question.

See, for example Section 6 of the following tutorial:
http://people.csail.mit.edu/ronitt/papers/icm.ps

In particular, one can decide whether a distribution on $[n]$ is truly uniform or is $\epsilon$-far (in total variation distance) from uniform with $O(\sqrt{n}/\epsilon^4)$ queries/samples from the said distribution. (This is also tight in the sense that $\Omega(\sqrt{n})$ samples are needed.)


The answer is no. To find the full dictionary of maximal repeated substrings in linear time is a hard problem if no one has ever introduced you to a suffix tree or equivalent.  However, if you don't like using suffix trees, you can achieve much the same result using suffix arrays which can be a little easier to handle.

EDIT: Well... actually this isn't strictly a full answer if you are happy with a slightly super-linear time solution.  You can in that case use the rather lovely result from 1972 "Rapid identification of repeated patterns in strings, trees and arrays" by Karp, Miller and Rosenberg.

Can I ask, what is your motivation? You use the word practical but there is nothing impractical about the suffix tree based methods, unless your data is too large to fit in RAM. In which case the problem becomes interesting again.


Curriculum: Logical/Formal Methods in Security

I suggest familiarizing the students with the following logics:

Epistemic logic: Used to model the knowledge of various parties participating in the protocol, and prove that an adversary cannot gain knowledge of some secret.
BAN logic: An old logic for proving various properties of authentication protocols. (Other belief logics are appropriate as well.)
Logics for transition systems: This includes logics like LTL, CTL, and LTL*. (such logics act on Kripke-like models of the protocol.)
Process Algebras: Several process algebras, like Spi-calculus (or CSP, and its security-related tool, Casper) are useful for modeling security protocols.
Introducing tools like AVISPA of NuSMV are very useful.
I also suggest Formal Correctness of Security Protocols as one of the course textbooks.

A friend of mine, Morteza Amini, has recently got his Ph.D. on modeling access control with logic. He devised a new logic, named $MA(DL)^2$, which stands for "multi-authority deontic logic and description logic." As the name suggests, it combines two non-classical logics (deontic logic + description logic) to decide whether an entity has access to an object. If you like, I can encourage him to provide more information.


Best upper bound on rate for q-ary codes

This is not the best bound even for $q=2$; in fact, this is not the best bound derived from the Delsarte linear program; see the paper "On the optimum of Delsarte's linear program" by Samorodnitsky (1998).

Thus, a better analysis of the linear program is likely to improve the bounds over larger $q$.  Even for $q=2$, this is a complicated analysis, so I don't know whether anybody has performed it for larger $q$.


Johnson and Lindenstrauss lemma for hamming space

Consider the $n$ vectors $e_1,\ldots,e_n$ of weight $1$, and the zero vector $e_0$. The Hamming distance between $e_0$ to any $e_i$ is $1$. Let $\varphi$ be a map into a Hamming cube of dimension $m$, and suppose that it preserves distances up to a factor of $C$. In particular, the $n$ points $\varphi(e_1),\ldots,\varphi(e_n)$ are within distance $C$ of $\varphi(e_0)$. On the other hand, the number of points at distance at most $C$ from $\varphi(e_0)$ is $O(m^C)$. We conclude that $m = \Omega(n^{1/C})$ is polynomial in $n$ rather than logarithmic in $n$.


Sampling from the Voronoi cell of a point

Too short for a comment... The following is intuitive bla bla, and feel free not buy it.

That seems extremely unlikely - assuming the points are uniformly distributed, the number of neighbours of the cell of $q$ is going to be $2^d$. Here is maybe a more formal argument. Pick a set of points on the unit hypersphere such that angle between any two points is at least, I dont know, 80 degrees. We know, that one can pick an exponential number of such points on the sphere without too much effort if the dimension is sufficiently large. Now, intuitively, for any subset of half the points, the Voronoi cell of the center of the sphere should have almost double the volume when compared to the cell volume with all the points. This inituitively implies you have to inspect all the points to get a good volume estimate. Which seems to imply, again intuitively, that sampling uniformly is going to be impossible, since the problems seems to be polynomially equivalent...


The statement is false for any polynomial time recognizable family of tautologies: the proof system will simply check if the formula is one of them and accept if it is. Proof length of them will be O(1). So I don't think any explicit example is known.

Recall that we don't even know if SAT $\notin$ DTime(O(n)) so we also don't know if SAT$\notin$ coNTime(O(n)) which is equivalent to your question TAUT $\notin$ NTime(O(n)) and follows from a positive answer to your question.

On the other hand, if NP is not equal to coNP, then the family consisting of all tautologies has super polynomial length in any efficient proof system.

Part of what people try to do in prof complexity is to rule out interesting classes of algorithms. A lower bound in a proof system implies a lower bound for all (co-nondeterministic) algorithms whose correctness can be efficiently proven in the proof system (if we can formalize and prove the correctness of an algorithm for SAT in a proof system we can consider its failing execution to find a satisfying assignment as proofs of the tautologihood).


Spell Checker with BK tree and edit distance that accounts for transpositions

Actually, the Damerau–Levenshtein distance is a metric. (See, for example, §11.1 of Encyclopedia of Distances, by Deza & Deza, Springer, 2009.) That is, it does obey the triangle inequality. This can be seen quite easily if you view every possible string as a node, with the edit operations and transpositions between them as edges. The Damerau–Levenshtein distance is then a shortest-path distance between the two strings in question, and such distances (graph geodesics) are always metric (i.e., triangular): You can't take a shortcut (breaking the triangle inequality) without simultaneously discovering a shorter path (a contradiction).

The problem is that actually computing the Damerau–Levenshtein distances is tricky, and you may see algorithms that compute something similar (optimal string alignment, for example), but that don't actually find the minimal number of steps. If Damerau–Levenshtein with adjacent transpositions is OK for your application, you can use that. You'll find algorithms for computing it online (even in Wikipedia), and as long as your code computes the minimum number of steps, the triangle inequality is obeyed. (But note that, as stated, algorithms based on finding the Damerau–Levenshtein distance through optimal alignment will not obey the triangle inequality, but that is because they don't really find the true Damerau–Levenshtein distance.)

If you want the unrestricted Damerau–Levenshtein distance (without necessarily using adjacent transpositions): Fear not, there are ways of computing that as well! You could have a look at the work of Lowrance & Wagner, for example.

If you don't want to get into the details of that, you could simply use a heuristic algorithm such as $A^*$ to compute the distance, with plain Levenshtein distance as the lower-bounding heuristic, for example. Should be efficient enough for reasonably-sized strings, and will give you the corret Damerau–Levenshtein distance. And it will work with your BK-trees.


How to introduce recursion to Simply Typed Lambda Calculus while at the same time keeping strong normalisation?

Which of the following are you asking: are there ways of
enriching the simply-typed $\lambda$-calculus with
mechanisms (presumably by restricting the available forms of
recursion) such that

exactly the terminating programs are typable?
more terminating programs are encodable than with the simple
    restriction you are describing in your question?

The answer to (1), as pointed out by Toxaris, is: if you want
type-checking to be decidable, then no. This follows directly
from the uncomputability of the halting problem. The answer
to (2) is positive, and Dave Clarke's answer gives an
example. Indeed there are countless ways of doing so, some
ad-hoc: e.g. if you have a particular (terminating) program $M$
of type $\alpha$ you want to add to the simply-typed
$\lambda$-calculus, you simply add a rule $\Gamma \vdash M :
\alpha$ to your typing system. For a more interesting and
principled way you could look at Barendregt's $\lambda$-cube,
which presents three orthogonal axes of extending the
simply-typed $\lambda$-calculus, all of which make the
simply-typed $\lambda$-calculus strictly more expressive
without losing normalisation. Relatedly, you can look at
induction principles, which are related closely to recursion. Note that this is an active area
of research because the more expressive you make your typing system,
the harder it becomes to prove that the calculus indeed only
types normalising programs.

Note that the problem is usually not to find a fragment of total functions
that we can use to program our terminating programs in. The total
fragments of lambda-calculus given by more expressive parts of the
$\lambda$-cube (e.g. $F_{\omega}$ or the calculus of constructions)
are very expressive. The problem is usually that it is
often inconvenient to encode a terminating program in such a
fragment. R. Harper gives the example of the $gcd$ function computing
the greatest common divisor:
$$
\begin{align*}
\textit{gcd}(m,0) & = m \\
\textit{gcd}(0,n) & = n \\
\textit{gcd}(m,n) & = \textit{gcd}(m-n,n) \quad \text{if}\ m>n \\
\textit{gcd}(m,n) & = \textit{gcd}(m,n-m) \quad \text{if}\ m<n
\end{align*}
$$

It is easy to see that this function terminates, but expressing it
using simple recursion schemes is no fun. Most programs we care
about in daily programming life are terminating for simple reasons and can typically
be encoded using relatively simple recursion schemes (e.g. primitive recursion).
That's why it was a major insight of Ackermann's and Sudan's that primitive
recursion is not enough.
For this reason  powerful recursion schemes
(including the unrestricted recursion of most programming languages)
are typically a convenient device to make programming   simpler, rather
than necessary for expressivity. Note that in the presence of higher-order functions,
primitive recursion is quite powerful, and enables us to encode e.g. the Ackermann function:

$$
\begin{array}{lcl}
   \textit{Ackermann} \ 0 & = & \lambda x. x+1 \\
   \textit{Ackermann} \ ( m+1 ) & = & \textit{Iter}\ ( \textit{Ackermann}\ m ) \\
   \textit{Iter}\ f\ 0 & = & f\ 1 \\
   \textit{Iter}\ f\ ( n+1 ) & = & f\ ( \textit{Iter}\ f\ n )
\end{array}
$$

BTW, the simply-typed $\lambda$-calculus with primitive recursion is also known as Gödel's System T and its expressivity has been studied in great detail and is well understood: we can define exactly the recursive function whose totality can be
proved in first-order logic, starting from the usual axioms for the elementary data
types, eg the Peano axioms for natural numbers.

In this context, you may find the paper Total Functional Programming by DA Turner interesting.

Non-typing work on termination. There's also a lot of ongoing work, both theoretical and implementation oriented, on termination analysis that's
not using (compositional) typing systems, but static analysis
techniques. An example is Microsoft's T2 termination prover.


Examples where insight from geometry was useful for solving something completely non-geometric

A few more examples:

Sleator, Thurston and Tarjan used a geometric representation of trees as partitions of polygons, and hyperbolic geometry, to prove lower bounds for binary tree rotation. (Also, I believe the history of a dynamic binary search tree can be represented as a tetrahedralization.)

The reduction of least common ancestor to range minimum queries, due to Berkman and Vishkin, relates a data structures problem on trees to an arguably-geometric problem. (and thanks for the article David)

The reduction of a scheduling problem to max weight independent set of axis-parallel rectangles [1] or the reduction of a different scheduling problem to geometric set cover [2] might qualify.

The reduction of the largest common subsequence problem to finding layers of maxima is well-known (meaning, I'm too lazy to look up who actually thought of it).

[1] (Liane Lewin-Eytan, Joseph Seffi Naor and Ariel Orda)

[2] Nikhil Bansal, Kirk Pruhs. The Geometry of Scheduling, FOCS 2010.

[later edit] A couple more cases where a "geometric" view seemed surprising (though the "submission to SoCG" or "makes something to visualize" standards are probably not met):

algebraic topology applied to lower bounds for distributed computing

incorporating computability into Hausdorff dimension

defining a notion of distance for groups, then volume, then growth of volume as a function of distance, then using "polynomial growth"


Number of connected components of a random nearest neighbor graph?

For $n$ uniformly random points in a unit square the number of components is

$$\frac{3\pi}{8\pi+3\sqrt{3}}n+o(n)$$

See Theorem 2 of D. Eppstein, M. S. Paterson, and F. F. Yao (1997), "On nearest-neighbor graphs", Disc. Comput. Geom. 17: 263–282, https://www.ics.uci.edu/~eppstein/pubs/EppPatYao-DCG-97.pdf

For points in any fixed higher dimension it is $\Theta(n)$; I don't know the exact constant of proportionality but the paper describes how to calculate it.


Does univ : univ always lead to a contradiction in a dependently typed language?

U : U is inconsistent in a wide variety of settings. It is safe to say that it's inconsistent in any type theory. Deriving False from it is feasible by hand. The simplest version of this is called Hurkens' paradox:

Original source
Coq implementation.
Agda implementation.

The Coq source additionally describes the sufficient conditions for getting False. In short, we don't need U : U, it's enough to have two universes, where one is contained in the other, and both are closed under impredicative function types.


Does Wikipedia assume a solution to the halting problem in their description of universal one way functions?

You don't need to know whether it is quadratic on all $x$, only on the particular $x$ that is given as input. And it's easy to decide whether a machine runs in a given time bound on a fixed input $x$. Just simulate it for that many steps and check whether it stops before the time bound runs out.

Here, "at most quadratic" is a little sloppy. It should be read as meaning "at most $|x|^2$ steps", so that there is a concrete time bound to check against. But one should keep in mind that there is a tradeoff between writing that is perfectly rigorous, and writing that can easily be understood by non-specialists, and Wikipedia generally aims for the latter — see https://en.wikipedia.org/wiki/Wikipedia:Make_technical_articles_understandable and its specific guidance to "explain formulae in English".


Categorical equivalent of higher order logic

The structure you want is due to Andy Pitts, and is called a tripos. It extends the notion of hyperdoctrine, which gives a categorical model for first-order logic, with enough structure to model higher-order logic.
However, much more of the work in this part of categorical logic focuses on toposes instead of triposes, which are just a little bit more expressive than HOL (basically you get to form sets by comprehension, too, giving a model of set theory with bounded quantifiers).
References:

Andrew M. Pitts, The Theory of Triposes
Andrew M. Pitts, Tripos theory in retrospect


You should probably take a look at Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$? and Are Oracles Associative?. I don't know any canonical definition of $(A^B)^C$ hence I've got the same problem as Tsuyoshi Ito.

If only the $P$ machine has access to oracle $O$, then yes, ${(P^O)}^O=P^O$ by definition.

If both the $P$ machine and the oracle $O$ can both query the oracle $O$, then just take $O=EXP$ as a counterexample: $(P^{EXP})^{EXP} = TIME(2^{2^{n^{O(1)}}})$ whereas $P^{EXP}=TIME(2^{n^{O(1)}})$.


What podcast should everybody listen to?

Simons Institute for the Theory of Computing:
https://www.youtube.com/user/SimonsInstitute/featured
Institute for Advanced Study:
https://www.youtube.com/user/videosfromIAS/featured
Prinston TCS:
https://www.youtube.com/channel/UCyGLYDvZ5BD5oYCIVv995HA/featured
Stanford Computer Science Theory:
https://www.youtube.com/user/StanfordCSTheory/featured
Innovations in theoretical computer science 2020:
https://www.youtube.com/watch?v=LBEzB8M6F5A&t=137s
DIMACS:
https://www.youtube.com/channel/UCTKhyhoEPYyjU9PFW99A6Qw


These questions are discussed in detail in the paper

  Rahul Santhanam, Ryan Williams:
  "Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity"
  Electronic Colloquium on Computational Complexity (ECCC) 2013, #108
  https://eccc.weizmann.ac.il/report/2013/108/


Let machine M solves the $\Sigma_2^p$-complete problem. We can use  this  machine to solve
any "NP-Hard" optimization problem (which includes MAX-CLIQUE and MIN-COLORING)  in
additional time polynomial in size of input as follows:

The solution is described for MAX-CLIQUE but the same idea works for any NP-Hard optimization problem. Let G = (V, E) and

O = { $<G,k>$ : the size of largest clique in G is k }

D = { $<G,k>$ : there is a clique of size >= k in G  }

Observation 1: Problem of deciding language O can be solved by making $\log{|V|}$ calls
to  the machine that decides D [Using Binary search]

Reduce instance of O to instance of D by using observation 1
Reduce instance of D obtained to instance of $\sigma_2^p$ complete problem P
Solve P using M

The reductions are all polynomial time, so its easy to see that if M works in polynomial
time then we can compute MAX-CLIQUE using M with polynomial time overhead.

Using the above reduction we can also see that M is at least as powerful as the machine
that solves NP-hard optimization problems.


Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums

Can this be reformulated as follows (careful, I am sleep-deprived with a cranky toddler in the room):

We are looking at a random graph $G$ with 6000 weighted nodes, a subgraph $G'$ induced by about 4000 edges, and 140.000 other weighted edges of positive weight but strictly smaller than the nodes they connect to.

A satisfying assignment for $C$ induces a bipartite subgraph of $G'$ (all nodes with assignment 1 plus their immediate neighbors with assignment 0). So you are looking to optimize over the set of bipartite subgraphs of $G'$?

A few random thoughts:

How structured are $G$ and $G'$? I presume a random graph model is not a very good model? What is the distribution of degrees of nodes?
Are all nodes in $G'$?

Is there a way we can bound the sum of all $w_2$-induced weights for given node? We know that the node weight $w_1(v)$ is bigger than the edge weight $w_2(v, \centerdot)$, is there something to be said for $\sum_{v_2 \in V} w_2(v, v_2)$? That could give some information about whether "switching a node on" is worth it...

If nodes have a tendency to outweigh the sum of their edges, would that hint at a bigger bipartite subgraph being always better than a smaller one, and at the problem becoming one of maximizing the size of the bipartite subgraph?


Can we quantify the "degree of quantumness" in a quantum algorithm ?

It depends on the context.

 For quantum algorithms, the situation is tricky, since for all we know, P=BPP=BQP.  So we can never say that a quantum algorithm does something that no classical algorithm can do; only something that a naive simulation would have trouble with.  For example, if a quantum circuit is drawn as a graph, then there is a classical simulation that runs in time exponential in the treewidth of the graph).  So treewidth can be thought of as an upper bound to 'quantumness', although not a precise measure.

Sometimes measuring quantumness in algorithms gets conflated with trying to measure the amount of entanglement produced by an algorithm, but we now think that a noisy quantum computer could have computational advantages over classical computer even with so much noise that its qubits are never in an entangled state (e.g. the one clean qubit model).  So the consensus is now more on the side of thinking of the quantumness in quantum algorithms as related to the dynamics rather than the states generated along the way.  This can help explain why 'dequantizing' is not likely to be generally possible.

 For bipartite quantum states, where the context is two-party correlations, we have many many good measures of quantumness.  Many have flaws, like being NP-hard, or not additive, but nevertheless we have a pretty sophisticated understanding of this situation.  Here is a recent review.

 There are other contexts, such as when we have a quantum state and would like to choose between different incompatible measurements.  In this setting, there are uncertainty principles that tell us things about how incompatible the measurements are.  The more incompatible the measurements are, the more 'quantum' a situation we have.  This is related to cryptography and zero-error capacities of noisy channels, among many other things.


In your example, you consider a size optimizer, that is a program that

  takes a program $P$, and returns an equivalent program $P'$ such that there is no other program $P''$ also equivalent to $P$ but strictly smaller than $P'$.

With such a perfect size optimizer, you could build a decision procedure for this question

  Is an input program $P$ equivalent to any program of at most $33$ characters?

But this is a non trivial property of program semantics. Rice Theorem says that such properties are undecidable.


The problem is NP-Complete even for integer values. You can look up the "knapsack problem" to see why.

A pseudo-polynomial algorithm exists if you can map your N values to integers (if the number of decimal places are bounded by some constant)


Support size lower bound for $k$-wise uniform distribution

I believe this question was answered positively in three independent papers:

C. R. Rao (1947), "Factorial experiments derivable from combinatorial arrangements of arrays", Journal of the Royal Statistical Society 9:1, 128-139.

B. Chor, J. Friedman, O. Goldreich, J. Hastad, S. Rudich, and R. Smolensky (1985), "The bit extraction problem or t-resilient functions", 26th IEEE Symposium on Foundations of Computer Science, 396-407.

N. Alon, L. Babai, and A. Itai (1986), "A fast and simple randomized algorithm for the maximal independent set problem", Journal of Algorithms 7:4, 567-583.


Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)

Questions regarding real-number computation and infinite iteration, especially in analysis and topology, are studied in constructive and computable analysis. Most people who work in this area will tell you that while the BSS model can be useful for certain kinds of computational complexity, it does not properly reflect computability on real numbers. The trouble is with the decidable $<$ relation on the reals, which is a basic building block in the BSS model.

There are several computational models which capture both computation of (exact) real numbers and infinite computation. Your examples all reduce to computation of the limit of a convergent sequence whose rate of convergence is explicitly known. This is a well-studied situation.

Here is one possible way of understanding computation on real numbers. I will use Haskell just for fun (usually these things get explained in terms of Turing machines). Let us think of a real number as a convergent sequence of rational approximations,

  type R = Int -> Rational

where we require that the $k$-th approximation is at most $2^{-k}$ away from the limit (we could have chosen some other rate of convergence, too, or we could have equipped each approximation sequence with information about the rate of convergence--the important thing is that the rate of convergence has to be provided explicitly).

Addition can be defined as follows:

  add x y = \k -> x (k+1) + y (k+1)

Exercise: define multiplication and other arithmetic operations.

Now to get infinite iteration going, we need an operation lim which takes a Cauchy sequence and computes its limit. More precisely, lim takes two arguments: a Cauchy sequence $(a_n)_n$ and its modulus of convergence $m$, which is a map $m : \mathbb{N} \to \mathbb{N}$ such that $a_{m(k)}$ is at most $2^{-k}$ away from the limit of $(a_n)_n$. In Haskell:

  lim :: (Int -> R) -> (Int -> Int) -> R

  lim a m = \k -> a (m (k+1)) (k+1)

Exercise: compute $\sqrt{r}$ as the limit of the sequence obtained by Newton's method for finding the positive root of $x^2 - r$.

This is just a very brief outline on how to do things. To find out more, visit the CCA net web site, especially the Texts and Monographs page.


If I were going to illustrate unique games, I'd do something with a label-extended graph (similar to the suggestion you mentioned).

But specifically, I'd contrast the original constraint graph with the label-extended one. For instance, label edges in the constraint graph with the corresponding equation out of:

$x_1 - x_2 = 0\mod 3$

$x_2 - x_3 = 0\mod 3$

$x_3 - x_1 = 1\mod 3$

Then there will be a (hopefully visually appealing) "twist" between the $x_1$ and $x_3$ vertex clouds in the label-extended graph.


List of complexity classes closed under complement

Nonderministic Logspace (NL) is closed under complement. That is, $NL=coNL$. This non-trivial result is known as (or rather, is the consequence of) the Immerman–Szelepcsényi theorem.


Clique-Percolation Algorithm's "corner cases"

Finally, I've found that the answer is that exists the possibility of leaving out many nodes out of any resulting community. There isn't any specified way in the original CPM algorithm to deal with them.

For anyone interested on a possible way to handle the left out nodes, there is an interesting article explaining an extension of CPM to do that:

Extended Clique percolation method to detect overlapping community structure : http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6968420&pageNumber%3D33268%26rowsPerPage%3D100

It seems that the modularity score obtained with this extension is usually better than the produced by the original CPM, but it comes with a price: it's slower.


What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

The following is an obvious consequence:
$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ would imply $\mathsf{L} \subsetneq \mathsf{P}$ and therefore $\mathsf{L} \neq \mathsf{P}$.

By the space hierarchy theorem, $\forall \epsilon > 0: \mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon}$ .
If $\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ then $\mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$.


It is notation for Formal Proofs and specification of language grammar in Backus-Naur Form.


Find all hyperplanes separating unique sets of `k` points

If I understand well, you are interested in the $k$-set problem:
http://en.wikipedia.org/wiki/K-set_(geometry)

In general their number can be $O(n^{\lfloor d/2\rfloor}k^{\lceil d/2\rceil})$ and though I could not find references now, I think you can also compute them in about this much time.


Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in a digraph

As the question is stated, having $l$ as part of the input, the problem is $\mathsf{NP}$-hard. This follows as a special case of the classification of the class of patterns for which the directed subgraph homeomorphism problem is $\mathsf{NP}$-complete by Fortune, Hopcroft, and Wyllie's paper: The directed subgraph homeomorphism problem.

In particular the following problem is $\mathsf{NP}$-complete: Given a directed graph $G$ and vertices $s,t,v$, does there exist a (simple) $(s,t)$-path through $v$?


Number of simple paths between two vertices in a DAG

Every simple path is uniquely determined by the subset of vertices that it passes through: if you topologically order the DAG (arbitrarily) then a path through any subset of vertices must go through those vertices in the same order given by the topological order. So (since $s$ and $t$ must always be included) there are at most $2^{n-2}$ paths.

This bound is tight, for a complete DAG (one in which every pair of vertices is connected by an edge, oriented consistently with a single topological order).


Encoding an infinitely looping process with state in the pi-calculus

The process $P{\langle 0, c, d\rangle}$ in the context of a recursively defined process like

$$
P{\langle count, c, d\rangle}
   \quad\stackrel{\text{def}}{=}\quad
c(v).(\overline{d}\langle count+v \rangle\ |\ P{\langle count+v, c, d\rangle})
$$

does the job, although we might quibble about how exact it models the original program. However, there is no problem with a more explicit modelling of state.

Translation from recursion to replication is folklore, easy and already discussed in (1): let's assume you have a process $P$ and it uses recursive definitions $X_1\langle \vec{a}_1\rangle = Q_1$, ..., $X_n\langle \vec{a}_n\rangle = Q_n$, where for simplicity we assume that no $Q_i$ uses recursively defined processes. (This restriction is easy to lift.) Then any use of $X_i\langle \vec{a}\rangle$ in $P$ is replaced by an output $\overline{x_i}\langle \vec{a}\rangle$. Let's call the resulting process $P_{new}$. Now the process

$$
   (\nu x_1 ... x_n) ( P_{new} \ |\ !x_1(\vec{a}_1).Q_1 \ |\ ... \ |\ !x_n(\vec{a}_n).Q_n )
$$

does without recursion what $P$ does with recursion. We might say that each recursive equation is replaced by a 'recursion server'.
I'm glossing over a few details here. For more, see e.g. (2).

R. Milner, The Polyadic pi-Calculus: A Tutorial.
J. Aranda, C. Di Giusto, C. Palamidessi, F. D. Valencia, On
Recursion, Replication and Scope Mechanisms in Process Calculi.


Natural problem arising from diagonalization?

In some sense the halting problem satisfies this request (I was almost ready to say "There are no such examples!" when I thought of this one.) By doing diagonalization against computable sets, you can of course get sets of very high complexity, but the seemingly-most-natural way of diagonalizing against computable sets gives you a problem that is equivalent to the halting problem. As we now know, the halting problem is equivalent to many other computational problems, such as deciding many properties of TMs, telling whether a Diophantine equation has solutions, the word problem in finitely presented groups, telling whether a high-dimensional knot is the unknot, etc.

I am still ready to say that I would be surprised to see other examples (that aren't just, say, relativized versions of this).


Computational complexity of learning (classification) algorithms - fitting the parameters

"Training" a naive bayes classifier, assuming you're given the feature vectors, is $O(n)$, where $n = \sum_i nnz(x_i)$, where $nnz(x_i)$ is the number of nonzero features in data point $i$.

For logistic regression you have to solve an optimization problem, and this depends on the optimizer. With L-BFGS an iteration takes linear time on the size of the training set and I've never needed more than 100 iterations to converge to a reasonable value (but I'm not aware of any worst-case bounds).

For the $k$-nearest neighbor classifier there is no training, but classifying has a high cost, and depends on the search algorithm you're using. For linear search the complexity is (for fixed k) proportional to the size of the training set for each point you want to classify. With approximate algorithms this can be brought down considerably at the expense of accuracy.

For svms standard quadratic-programming solvers are $n^3$, but recent approaches are inverse in the size of the training set. More information in this quora answer.

If you really need fast learning the best approaches so far are those based on online learning, which can converge to classifiers that compete well against batch classifiers with only one pass over the training data. A very fast implementation is vowpal wabbit and a good algorithm is confidence-weighted learning.


Why do equalities between complexity classes translate upwards and not downwards?

I think the best way to get intuition for this issue is to think of what the complete problems for exponential time classes are.  For example, the complete problems for NE are the standard NP-complete problems on succinctly describable inputs, e.g., given a circuit that describes the adjacency matrix of a graph, is the graph 3-colorable?  Then the problem of
whether E=NE becomes equivalent to whether NP problems are solvable in polynomial time on the
succinctly describable inputs, e.g., those with small effective Kolmogorov complexity.   This is obviously no stronger than whether they are solvable on all inputs.  The larger the time bound, the smaller the Kolmogorov complexity of the relevant inputs, so collapses for larger time bounds are in effect algorithms that work on smaller subsets of inputs.

Russell Impagliazzo


Logspace algorithms on graphs with bounded tree width

Tutte polynomial is an example.

This is a generalization of the chromatic polynomial, which itself is a #P-hard problem in any reasonable formulation. In

  Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width, S. D. Noble,
  Combinatorics, Probability and Computing, 1998,

a polynomial time algorithm is given where the time complexity is about $O(f(k)n^{4+\epsilon})$, where $k$ is the treewidth and $n$ is the number of nodes.
Related works can be seen in here. For a survey, there are article on Arxiv,
where the complexity issue discussed in section 8.

It seems that the problem cannot be expressed in MSO2 directly, though I'm not familiar with the detailed definitions... Hope this problem is what you need!


There is a complete characterization of coverage functions in terms of such equations. For |X|>3 there are more equations than the ones pointed. Each of these equations can be thought as a constraint on discrete $k^{th}$ derivative.

Monotone increase function if and only if first order discrete derivative is +ve. i.e. $f(B)-f(A)\ge 0$  when $A\subseteq B$.

Submodularity if and only if second order discrete derivative is -ve. i.e. $(f(A\cup B)-f(B))-(f(A)-f(A\cap B))\le 0$.

Similarly if you have conditions on the next $n$ derivatives you get coverage functions. (I think the signs need to be +ve for even order derivative and -ve for odd order derivative)

Something similar was already known in probability. A coverage function can also be thought as a probability measure (upto a scaling constant). The only reference I was able to dig up was page 439 from Feller's book on probability.