On the complexity of a "list" datastructure in the RAM model

It appears that all of these operations can be performed in time $O(\log n/\log\log n)$ on a RAM, by combining methods for maintaining a dynamic labeling of the list elements by integers of polynomial magnitude (e.g. Bender et al, "Two Simplified Algorithms for Maintaining Order in a List", ESA 2002, https://erikdemaine.org/papers/DietzSleator_ESA2002/) with methods for ranking and unranking sets of small integers (Pătraşcu and Thorup, "Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search", FOCS 2014, https://arxiv.org/abs/1408.3045).

Operation 3 (get the value at a given position) is the simplest: it's just unranking. To insert or delete at a given position, use unranking to find which list element is there, do the insert or delete operations in your list at or near that element, use the order-maintenance structure to modify the numbering of elements, and then update the ranking-and-unranking data structure according to those modifications.

Update 2020-05-25: Kasper Green Larsen emailed me the following lower bound proof and suggested I post it here:

We can prove the following lower bound: Let $t_u$ denote the update time and $t_q$ the query time of a data structure for the list problem. Both are worst case times. Then we have the following lower bounds (when the word size is logarithmic): If $t_u$ is polylog$(n)$, then $t_q = \Omega(\log n/\log\log n)$. If $t_q$ is polylog$(n)$, then $t_u = \Omega(\log n/\log\log n)$.

The proofs follow by reduction from 1-bit partial sums; see Pătraşcu and Demaine (SODA'04) [DE: See also Fredman and Henzinger, "Lower bounds for fully dynamic connectivity problems in graphs", Algorithmica 1998]. In 1-bit partial sums, we have a bit vector of length $n$. An update flips the value of a bit. A query asks for the parity in a prefix of the array. In that paper, they prove exactly the above lower bounds for 1-bit partial sums, although their lower bound also holds if we change to amortized update and query time. The reduction I have loses that property (it can probably be fixed, see comment at the end). To give the reduction, we need to carefully examine the proof of Pătraşcu and Demaine to realize that their lower bound for partial sums holds even if the data structure is allowed to perform an arbitrary amount of preprocessing before seeing any updates or queries, as long as the word size is logarithmic, we have the lower bound (this observation is not necessary for the fix for amortized vs worst case). The initial input array in partial sums is all-0s and the sequence of operations for which they prove their lower bounds has only $n$ operations on the array.

We will reduce from 1-bit partial sums in an array of size $\sqrt n$ (and thus only $\sqrt n$ operations in the hard sequence) to the list problem in a list of up to $n$ elements. It goes as follows:
As a preprocessing step, set the list to contain $\sqrt n$ batches of the numbers $0,\dots,\sqrt{n} - 1$, i.e. the list looks like:

$$0,1,\dots,\sqrt{n}-1,0,1,\dots,\sqrt{n}-1,\dots,0,1,\dots,\sqrt{n}-1$$

with a total of $n$ elements.

Upon an update to flip the $i$th bit of the partial sums array, we remove element $i \sqrt n$ from the list.

To compute the prefix sums up to index $i$ in the array, we retrieve element $i\sqrt n$ from the list and return its parity.

Let us see that the reduction works. First observe that before any updates are made to the list, a prefix sums query for an index $i$ will retrieve the "0" element in the $i$th batch. Moreover, since we have only $\sqrt n$ operations, and all operations remove at most one element from the list, a prefix sums query for element $i$ will always retrieve an element that comes from the original $i$th batch. Finally, observe that when we delete the $(i\sqrt n)$th element of the list, all prefix sums queries for entries $j<i$ are unaffected since the first part of the list doesn't change. Also, for all queries $j\ge i$, we will now return the next element of the list since the list indices on or after $i\sqrt n$ all change by one. This next element will come from the same original batch and have a value one larger than before because we haven't deleted from this part of the original batch (this is where we use that we have $\sqrt n$ copies in each batch). Thus the answers to all queries $j\ge i$ correctly have their parity flipped.

The lower bound for 1-bit prefix sums on arrays of size $\sqrt n$ is the same as on arrays of size $n$ since $\log n$ only changes by a factor $2$. Also, the lower bound holds even if we ignore all time that was spend during preprocessing, so we get our sought lower bound.

The reason why we lose the amortized lower bound is that we need to do $n$ initial operations to create the list. Thus even if we spend $\sqrt n$ time on each of the operations after preprocessing, the amortized time to process the whole sequence is only $O(1)$ per operation. This can probably be fixed as follows: Run $\sqrt n$ copies of the hard distribution for 1-bit partial sums, where after each sequence of $\sqrt n$ operations, we re-insert all elements that have been deleted. Then we get a total of $n$ updates and queries that all have a large amortized lower bound from 1-bit prefix sums. This is not completely formal, but I'm certain it can be formalized.


Help needed on method to use for anomaly detection

First of all, I warn that things aren't that simple. Up until now, researchers haven't came up with a perfect algorithm to do that (and I'm almost sure they never will!)

However, there are many competing approaches to do what you want. They compete in efficiency, false-positive rate, false-negative rate, and so on.

The model is as follows: Assume you have a number of algorithms (fuzzy, genetic, neural net, etc.) which process (possibly different) streams of data, and generate alerts if they find anomaly. You then have a stream of alerts, which must be correlated by another algorithm. Unsurprisingly, such algorithm is called alert correlation.

You can find hundreds of papers on this subject here. While this term is usually applied to IDS algorithms, there's nothing preventing you from applying it to antivirus algorithms.


What is logic programming and does it really add anything new to the logic?

I will just write what Frank Pfenning taught me (all mistakes go on my account).

A traditional formal system in logic, such as natural deduction, is descriptive in the sense that it tells us what valid deductions are, but it does not tell us how we are supposed to look for them.

The starting point of logic programming is to take the rules of deduction and reformulate them in such a way that they can be read both as rules of deduction and an evaluation strategy for a computation. This way a strong connection between deduction and computation is created. Both logic and theory of computation benefit from it, and it is perhaps a bit pointless to ask whether logic programming "really adds" anything new to logic. Logic and computation are not separate entities anyway.


Number of strings with unique substrings

You mean that each nonzero n-bit substring occurs once, and the all-zero n-bit substring occurs no times, right? Essentially, what you are looking for is a De Bruijn sequence.

The number of de Bruijn sequences should be in OEIS somewhere but I'm having trouble finding it. My guess is that it grows doubly exponentially, since it is the number of Hamiltonian cycles in an exponential sized graph (the de Bruijn graph) and graphs tend to have exponentially many such cycles when they have any.


Terminology and references for a learning model

The related work I know of is experimental, but a similar setup has been called Learning from Label Proportions: https://link.springer.com/article/10.1007/s13278-017-0478-6


What tools do you use to give presentations?

For drawing diagrams, there's tikz in latex, and, if you have a Mac and a bit of cash, Omnigraffle. Both produce high quality diagrams.


Can choice or sequential execution be expressed with other basic operators of the pi calculus?

This is a really interesting question and only partially understood.
The $
\newcommand{\OUT}[2]{\overline{#1} #2 }
$ precise answer to such questions depends in subtle ways on exactly what the ambient $\pi$-calculus is and exactly what feature you are encoding.

For sums  you need to realise that there are different kinds of sums for example input guarded sums like $x(v).P + x(v).Q$ or $x(v).P + y(v).Q$, or
mixed sums like $x(v).P + \OUT{y}{v}.Q$ or even $x(v).P + \OUT{y}{v}.Q + \tau.R$. What you can and cannot encode really depends on what sums you have. The groundbreaking study (1) gives hard limits to 'good' encodings. Simplifying greatly, what (1) shows is that adding mixed sums to a calculus strictly increases expressivity. This it cannot be encoded (in a nice way). The reason is that mixed sums allow a certain form of symmetry breaking that is not achievable in conventional $\pi$-calculi without mixed choice.

With sequential composition $P; Q$ the situation is less complicated, but you need to be clear exactly what sequential means for parallel processes and replication/recursion:

Should $R$ begin to execute when one or both of $P$ and $Q$ terminate in $(P|Q); R$?
What is the meaning of $(!x(v).P); R$?

If $(P|Q); R$ means that both $P$ and $Q$ must terminate before $R$ goes to work, and if we disallow sequential composition like $(!x(v).P); R$ with replication, then $P; Q$ is easily encodable, and by (1) it cannot simulate general forms of sums that include mixed sums.

The curse of Turing completeness. There is a further complication. Process calculi typically are  Turing-complete, hence any feature can be 'somehow' be encoded. So you need to be very precise about what you mean when you ask if some calculus is "equivalent" to some other. The usual approach to making this precise is to constrain admissible encodings, e.g. to require them to be compositional, or preserve termination, or be closed under renaming, or any number of other interesting structural properties. For different concepts of admissible encoding you tend to get different answers.
None of this is germane to process calculi, Turing's curse affects all programming languages, but process calculi are especially subtle, since they can do so much more than mere sequential computation.

For an overview of the state-of-the art in process calculus expressivity, see (2, 3).

(1) C. Palamidessi, Comparing the Expressive Power of the Synchronous and the Asynchronous π-Calculi.

(2) D. Gorla, Comparing Communication Primitives via their Relative Expressive Power.

(3) D. Gorla, A Taxonomy of Process Calculi for Distribution and Mobility.


Inferring simplest method to convert bit array 1 to bit array 2

There is clearly an algorithm, since the finite search space can be explored using brute force.  This takes a long time...

Instead of considering $f \colon \{0,1\}^n \to \{0,1\}^n$, one can look at the Boolean function $f' \colon \{0,1\}^{2n} \to \{0,1\}$ defined by $f'(xy) = 1$ iff $f(x) = y$.

No polynomial-time algorithm is known to find a minimum-size circuit for a Boolean function, which is known as the Minimum Circuit Size Problem (MCSP).  However, MCSP is in NP.

If MCSP were in P, then one could factor in average time $2^{n^\epsilon}$ time (for any $\epsilon > 0$) numbers that are products of two primes, each of which is congruent to 3 modulo 4.  These numbers are quite hard to factor in practice, so this would be quite surprising.

On the other hand, if the MCSP is NP-complete, then this would imply strong circuit lower bounds for the class E = DTIME($2^{O(n)}$), which we don't currently know how to do.

Valentine Kabanets and Jin-Yi Cai, Circuit Minimization Problem, STOC 2000, 73–79. doi:10.1145/335305.335314 (preprint)

So no polynomial-time algorithms seem likely for your problem, unless you can exploit special features of the functions you are interested in.


Is conversion of PRAM to parameter number of processors trivial

here are my answers to your questions.

1) In general, you can not come up with efficient schemes for scaling down the number of processor from $n$ to $p < n$. Why ? Because, even without taking into account additional issues such as caches etc, the problem is strictly related to how you map tasks to processors, which is known to be an NP-complete problem. In particular, this is almost always application dependent, so you have to carefully evaluate this each time you want to scale down your parallel algorithm. The good news here is that, starting from a work-efficient algorithm you can obtain a scaled-down work-efficient algorithm, thus preserving its efficiency.

2) To the best of my knowledge there are no strong connections with parameterized complexity, at least I am not aware of any significant published paper discussing this relation. I may be wrong of course.


any connection between binary/integer multiplication and matrix multiplication?

Here is a relevant reference and Sasho has graciously added a high-level summary.

A Group-theoretic Approach to Fast Matrix Multiplication by Cohn and Umans. (2004, arxiv).

  There is a close analogy between the framework we propose in this paper and the well-known algorithm for multiplying two degree n polynomials in O(n log n) operations
  using the Fast Fourier Transform (FFT). In this section we
  elucidate this analogy to give a high-level description of our
  technique.

On a very high level, the FFT-base polynomial multiplication algorithm can be seen as the following strategy: 1) embed the polynomials as elements of the group algebra of a not-too-large abelian group; 2) apply the DFT to the group algebra elements in order to embed them as complex-valued diagonal matrices; 3) multiply the diagonal matrices.

(Note: the group algebra here is the algebra of formal "linear combinations" of group elements with complex or real coefficients).

The same approach almost works for matrix multiplication. Step 1) becomes hard, where it was trivial with polynomials. The embedding can be done with abelian groups of size $n^3$, and no better, so for $n^{2 + o(1)}$ size groups you need to abandon commutativity. Then 2) turns out to still be doable with non-abelian groups using the appropriate generalization of DFT that you get from representation theory, but the resulting object is a block-diagonal matrix rather than a diagonal matrix. Then 3) is no longer the trivial pointwise multiplication operation, but multiplication of smaller matrices. Bounding the sizes of these matrices is a question about dimensions of irreducible representations of the group we used.

See also the follow-up Group-Theoretic Algorithms for Matrix Multiplication by Cohn, R. Kleinberg, Szegedy, and Umans (2005, arxiv).

Perhaps there have been advancements (or even a survey) since then. Of course this probably doesn't answer your question about how the complexities of the problems are related....


Survey on algorithms/complexity of linear algebra

Two references you might find to be helpful:

  D. Bini and V. Pan.  Polynomial and matrix computations, Volume 1: Fundamental Algorithms.  Progress in Theoretical Computer Science, Birkhauser, 1994.

  J. von zur Gathen. Parallel linear algebra. In J. Reif, editor, Synthesis of Parallel Algorithms, chapter 13. Morgan Kaufmann Publishers, Inc., 1993.

They aren't necessarily recent, but they're a good starting point.


Problems that are counter-intuitively solvable in practice?

Highly structured SAT instances (even on millions of variables) can often be solved in practice. However, random SAT instances near the satisfiability threshold with even a few hundred variables are still open (meaning, even in practice, if you generate such a thing you may never know in the lifetime of the universe whether the thing you generated is satisfiable or not using current SAT solvers). You might be interested in this related question and its answers.
Clique finders are also shockingly good "in practice"

With respect to clique finders, (part of the) explanation is given
by an average case analisys of the algorithms in question.

See https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub

Integer programming and mixed integer-linear programming (with some rational and some integer variables) are the focus of whole Operations Research departments, and can often (but not always) be solved in practice
From what I understand, many $\mathsf{PSPACE}$-complete problems that arise in verification can often be solved in practice, but "in practice" usually implies "on highly structured instances". (In contrast, we still don't know who wins for pretty small instances of the game of Go, which is another $\mathsf{PSPACE}$-complete problem.)
Many problems in computational algebraic geometry can be solved in practice on small instances using Grobner bases, but these fail miserably on larger instances, or even small instances that have high "complexity" (as measured by the Castelnuovo-Mumford regularity). And these problems are even $\mathsf{EXPSPACE}$-complete!
As already pointed out in the comments by D. W., Graph Isomorphism can pretty much be solved in practice. It is very hard to stump modern GI software such as nauty, bliss, saucy, etc.


If you're totally lost, you might not have the needed background to get much use out of the paper.  The paper draws on many concepts and foundational ideas from theoretical cryptography (including how to formalize notions of security for various cryptographic tasks), and it assumes familiarity with those ideas.  If the definition looks confusing, it's probably because you don't have that familiarity; the paper's intended audience was cryptographers who already have that familiarity.

You might want to spend a few weeks studying theoretical cryptography (foundations of cryptography), e.g., from Lindell-Katz, the Goldreich book, and/or many lecture notes online on the foundations of cryptography.  You'll find that this kind of definition is routine, and studying that material will prepare you to be able to understand this material and work through the definitions on your own.


Enumerating Planar Graphs of Bounded Treewidth

There is a nice software which generates small planar graphs with respect to isomorphism which might help. As I see one of the problem was to generate non-isomorphic planar graphs and most of those planar graphs (on less than 15 vertices) are of small treewidth.

For checking whether their treewidth is smaller than given value $k$, one way is to use heuristic algorithms to speed up this calculation, just in the case that exact algorithms are not practical. e.g in a planar graph $G$ first we can find a diameter of $G$ and the corresponding path $P$ of length $d$ (which is a diameter). Then find a vertex $v\in P$ which has shortest longest distance ($l$) to any other vertex $u\in G\setminus P$ among all vertices $w\in P$. The treewidth of $G$ is at most $d+l$, if this is smaller than $k$ then we are done otherwise either apply some other heuristic algorithms or run the exact algorithm.

For less than 3-connected graphs it's also possible to apply heuristics by finding cut vertices and then fixing those vertices and finding the tree width of a remaining graph. But as the number of nodes is small ($15$) if the graph is $4$-connected then the diameter is not big and I think the first heuristic should work there. (I don't know if there is any 5 connected planar graph on at most 15 vertices, but as we know there is no $t$-connected planar graph for $t>5$)

As the size of largest obstruction for tree width $k$  is not known we cannot simply guess the upperbound value of treewidth of a given graph $G$. But it seems that at least for planar graphs it should not be so big (one should give a proof for this).


Run Dijkstra's algorithm twice to detect negative-weight cycles?

The mistake is in

  This can only be true if there are no negative-weight cycles reachable from the source.

Actually, this can only be true if there are no negative-weight edges reachable from the source.

So the "double Dijkstra" suggested above may wrongly return false in a graph with negative-weight edges but no negative-weight cycles, whereas Bellman-Ford will correctly return true.


maximize edges minus vertices in a weighted graph

This problem can be reduced to the Project Selection problem: suppose you have a set $P$ of projects each has an associated revenue $p_i \in \mathbb Z$ and you have dependencies between projects represented by a directed graph $G$ where the vertices are the projects and an edge $(i, j)$ means that project $i$ can only be selected if project $j$ is selected as well. We need to choose a feasible set of projects $A \subseteq P$, where a set is feasible if for every $u \in A$ we have all the out-neighbors of $u$ also in $A$ (note that this induces a subgraph $G'$ of the set of all projects in $A$ as vertices and the edges joining any two vertices in $A$), and the goal is to choose a feasible set of projects to maximize $\sum_{i \in A} p_i$.

Our reduction is as follows: given a directed graph $G=(V, E)$ with weights on the edges $w$ and weights on the nodes $h$, we define a new graph $G'=(V', E')$ as follows: we create a vertex $v_i$ in $V'$ for every node $i \in V$ and assign it cost $p_{v_i} = - h(i)$, then for every edge $e = (i, j)$ in $E$ we create a node $u_e$ in $V'$ with cost $p_{u_e} = w(e)$ and we create two edges $(u_e, v_i)$ and $(u_e, v_j)$ in $E'$ (these indicate that this edge can only be chosen if both vertices are). To prove that this is correct, note that for a given feasible set of projects in this new problem we can immediately find the corresponding subgraph of $G$, $G_A = (V_A, E_A)$ and we see that it maximizes
$$ \sum_{i \in A} p_i = \sum_{e \in E_A} p_{u_e} + \sum_{i \in V_A} p_{v_i} = \sum_{e \in E_A} w(e) - \sum_{i \in V_A} h(i)$$
which is our original goal. The Project Selection problem can be solved by maxflow algorithms, see Kleinberg and Tardos Section 7.11 for the solution (and a more thorough description of the problem). There is code for this here, Problem 1082G which does a similar reduction and solves the corresponding max flow problem.


This is something that min-wise independent hashing is good for. (See a wikipedia explanation here.
The idea is to use a family $\mathcal{H}$ of hash functions so that when you pick a random function $h\in H$ from the family, for any set $S$ of $n$ elements, for any $x\notin S$,  $\Pr_{h\in \mathcal{H}}[h(x) < \min_{y\in S} \{h(y)\}] = \frac{1}{n+1}$. This means that every element in $S$ has the same likelihood of being the only one with the smallest hashed value.

As you scan the stream, keep track of the smallest hashed value that you have seen, and whichever element was mapped to that value is your sample. There are families of hash functions that are almost minwise independent families. For example a paper by Dahlgaard and Thorup  .
If you want to sample $k$ elements you could do this naively using $k$ hash functions, but you could also use ideas from bottom-$k$ sketching with only one function. See this paper by Thorup.


State transducers for generating permutations

If you allow an auxiliary work tape, then it is easy to customize the Turing machine model to suit your needs. The Turing machine has two tapes: input/output and work. The work tape operates as usual, while on the input/output tape, all you can do is switch two adjacent values. This is enough since the transpositions $(i \quad i+1)$ generate all of $S_n$.

If you don't allow a work tape, then the goal might be impossible. Let $f$ be a recursive function not computable in $O(n\log n)$ space. We can think of $f$ as a reordering function as follows: convert the $n$ input bits into a permutation in $S_{2n}$ conforming to the regular expression $(12+21)(34+43)\cdots$. The output is read, say, from whether the first element is smaller than the second element or vice versa. In many reasonable models, a computation is convertible to a Turing machine computation with space $O(n\log n)$. (Though a "copy" operation might invalidate this.)

Finally, you ask whether this class of transducers has been researched. Since you want this class to encompass all partial recursive reorderings, it is fair to say that recursion theory is the study of these reorderings and their non-recursive generalizations.


Questions about special types of partial assignments

Answer to your primary question: You have posed a Yes/No question. By definition, a Yes/No answer suffices. There is no requirement to produce any kind of assignment as an answer. If you modify the problem to require a certificate for the Yes/No answer, the answer will depend on what constraints you impose on the certificate and the certification algorithm (should it be linear-time verifiable, etc.).

Answer about terminology: The most common term I know of for what you call ``micromal'' is minimal assignment. I do not have a good sense for how standard this terminology is. If the partial assignments are represented as formulae, you obtain the very standard notion of prime implicants.

There is some confusion about terminology in your answer so I will expand on this issue below.

Assignments and Partial Assignments

  A partial assignment is a partial function in $\mathit{Var} \to \{\mathsf{true}, \mathsf{false}\}$.

A partial assignment $\pi$ refines a partial assignment $\theta$ if for every variable $x$ on which $\theta$ is defined, $\pi$ is also defined and $\theta(x) = \pi(x)$. This definition allows $\pi$ to assign values for variables not assigned to by $\theta$.

A total assignment is a partial assignment that is a total function. A partial assignment represents the set of total assignments that refine it (meaning, that extend it). Observe that these definitions make no reference to formulae.

You can define the truth value of a formula under a partial assignment in a fairly standard manner. The only difference to defining the truth value of a formula under an assignment is that a formula may be $\mathsf{true}$, $\mathsf{false}$ or $\mathsf{unknown}$ under a partial assignment.

Minterms and Cubes

A literal in propositional logic is a Boolean variable or its negation. A cube is a conjunction of literals. A cube is a minterm is a cube in which every variable occurs exactly once.

There is a correspondence between minterms and partial assignments. Every partial assignment  $\pi$ defined on exactly $k$ variables can be represented by a minterm $\ell_0 \land \cdots \land \ell_{k-1}$, such that $\ell_i = x_i$ if  $\pi$ is defined on $x_i$ and sends $x_i$ to $\mathsf{true}$ and $\ell_i = \neg x_i$ if $\pi$ sends $x_i$ to $\mathsf{false}$. Observe that a total assignment $\sigma$ refines a partial assignment $\pi$ exactly if the assignment $\sigma$ satisfies the cube representation of $\pi$. We can similarly move in the other direction and represent cubes as partial assignments.

Prime Implicants and Minimal Assignments

Everything above was stated without needing the notion of a formula which is being solved. Let $F$ be a Boolean formula.

An implicant $C$ of a formula $F$ is a cube that implies $F$. The implicant $C$ is a prime implicant if there is no smaller cube that is an implicant.

The dual notion is of an implicate. An implicate $C$ of a formula $F$ is a clause $C$ that is implied by $F$. A prime implicate is an implicate that with no sub-clause that is an implicate.

The connection to your question is: If a partial assignment $\pi$ represents an implicant for a formula $F$, then every total assignment that refines $\pi$ satisfies $F$. Moreover, if no $\theta$ refined by $\pi$ represents an implicant, then $\pi$ represents a prime implicant. The literature on prime implicants is vast, but you only need to follow work that is based on modern SAT solvers because they will be using partial assignments.

Formalizing your question

I think it would help to use more precise terms in formalizing your question. Here are some examples.

Consider a partial assignment $\pi$ and a formula $F$.

What is $\pi$ called if every total assignment $\theta$ that refines $\pi$ satisfies $F$? That is, $\pi$ represents a subset of the satisfiying assignments of $F$.
What is $\pi$ called if every total assignment $\theta$ that satisfies $F$ also refines $\pi$? That is, $\pi$ represents a superset of the satisfying assignments of $F$.

Some comments. There is a unique, maximally defined partial assignment that contains a superset of all satisfying assignments to $F$. You can construct this by taking the conjunction of all literals implied by $F$.

There is no unique partial assignment that represents only satisfying assignments of $F$. There are multiple, maximal ones, corresponding to prime implicants.

References about implicants

These references are within a model checking context as I am more familiar with that context. There are discussions of minimizing assignments and manipulation of implication graphs in both these papers.

Minimal Assignments for Bounded Model Checking, Ravi and Somenzi, 2004. (I did not find a freely available PDF, but maybe you can mail the authors if you don't have Springer access).
Applying SAT Methods in Unbounded Symbolic Model Checking, McMillan, 2002.

About your algorithm

There are certain things you are doing in your algorithm which makes me wonder if you are familiar with modern SAT algorithms.  You are describing a mix of the original Davis-Putnam and the Davis-Logeman-Loveland algorithm from the 60s. Specifically, Steps 4 and 5 are implemented differently today in what is called the unit rule.

Please confirm if this is what you mean by  reliable assignment.

  A partial assignment $\pi$ is reliable for a formula $F$ if some
  extension of $\pi$ satisfies $F$.

I think that this definition is equivalent to yours but much much shorter. A better term would be feasible. Note that a partial assignment that is not reliable in the sense defined here is called a conflict.

I would suggest looking at the following CS Theory answers. (and all have answers shamelessly from me)

Starting SAT solver papers
CNF Rule Hierarchy Discovery
Good reference about approximate methods for solving logic problems


You might want to check out g-tries. This is essentially the data structure you're looking for, but designed for use with general graphs instead of just trees. As such, I'm not sure that g-tries have good theoretical guarantees -- I think they use a graph canonization algorithm as a subroutine -- but in practice they seem to work well.

(Don't be scared that the linked paper is about "network motifs in biological networks": the g-trie is a perfectly good abstract data structure for graphs.)


You can edge color faster than applying the fastest vertex coloring algorithm to the line graph: see http://arxiv.org/abs/1007.1161 for one such algorithm. What interests me is why can't we find something that is much faster...


Initial conditions for universal Rule 110

the rule 110 initial condition constructions are extremely intricate even for simple computations and generally cannot be constructed by hand. one would generally start with a real/concrete TM [turing machine] built to compute your problem, ie the complete state table (TMs are of course alluded to in thousands of TCS papers but rarely actually built directly).

generally the papers build initial conditions using complex algorithmic conversions to tag systems. the cook paper cited by DE in comments above[1] does improve the simulation time by a polynomial instead of exponential construction. in other words, theres more than one way to create suitable initial conditions. another recent construction with emphasis on regular languages by martinez et al can be found[2]. the authors of the papers generally do not seem to release code they used to construct their paper results [scanning the two papers below], a legitimate complaint that could be made of much research papers in TCS which tend to give short shrift to experimental approaches[3] even as they seem to focus on them.

so once you have the TM alphabet and state table one runs the conversion algorithms described but not really explicitly/manifestly implemented in the papers [because no code is given, only a prose description of the algorithm(s)] which take the TM alphabet and state table as input and then output a tag-system setup and 110 initial tape conditions that simulates the TM. my understanding is that in some cases, an infinite periodic starting "tape" pattern may be required.

in their papers they do not even seem to mention what coding languages they use for their simulations/experiments. they might release code if you contact them directly. therefore wolframs release/publishing of some mathematica code you mention above [nice but now rather dated based on later developments in the area] seems to be an exception in this area. therefore to actually independently construct concrete machines built using these techniques a researcher might have to reimplement the algorithms described in the papers.

footnote: the exact TM problem must be defined with some care because in your case, does a TM that simply erases and outputs 2 to its tape compute 1+1? you probably want a TM that computes $a+b$ and starts with input 1,1 on the tape.

[1] A concrete view of rule 110 computation by matthew cook

[2] Reproducing the cyclic tag system
developed by Matthew Cook with
Rule 110 using the phases fi_1 by Martinez et al

[3] Is "Experimental Complexity Theory" being used to solve open problems?


For general $m$, exactly-m-sat is strictly harder than u-sat (thus does not reduce to it) unless the PH collapses.  The reason is that PP can be obtained using an existential quantifier over exactly-m-SAT queries (exists m>(half of the assignments) such that exactly-m-SAT), thus if exactly-m-sat is in the k'th level of PH, then PP is in the (k+1)'st level, and then the hierarchy collapses (since P^PP contains PH).  But u-sat is clearly in the second level of PH (actually in a subclass called DP).

On the other hand, as @Tsuyoshi mentioned above, if $m$ is polynomial, then exactly-m-sat is many-one reudcible to u-sat.


Generalizing Parsing Expression Grammar for Context Sensitive Grammars

PEGs are unambiguous exactly because at each choice point, i.e, alternatives of a grammar rule, you can choose one and never change it. Context-free grammars, or to be more precise general parsing algorithms like Early or GLR, explore all the alternatives which can lead to ambiguity.

We have to also distinguish between ambiguity and non-determinism. PEGs reduce non-determinism at runtime, which guarantee at most one parse result, but at the same time, they can lead to parse errors even when there is no ambiguity. For example, consider the grammar:

A ::= 'a'
    | 'a' 'b'

and the input 'ab'. This will lead to a parse error because the parser made a premature choice. This is the main shortcoming of PEGs.

About general parsing algorithms, it is not possible to guarantee un-ambiguousness, but at the same time guarantee that the correct (intended) parse tree is returned. There are many disambiguation techniques that try to reduce non-determinism at runtime, and as a result remove ambiguities, but there no guarantee. The underlying grammar may be ambiguous.

What do you mean by context-sensitive grammars? Something like Python that has indentation-sensitivity? If you are looking for such features, the answer to your first question is yes. You can take a look into monadic parser combinators (with limited backtracking). They are essentially PEGs and allow threading of values into the parsing state to simulate context-sensitiveness. I am not aware of any formalism that allows you to write arbitrary context-sensitive grammars with more than one nonterminal on the left-hand side.

The answer to the second question is also yes. If you always select one alternative and never backtrack, you will get at most one parse tree, but it may not be the one you want or you can get a parse error.

You can also look into one of my previous work on data-dependent GLL Parsing where we describe how to deal with context-sensitivity in general parsing. The paper has a good discussion (IMO) of different parsing techniques.


Is it possible to determine if a reduction is correct?

I don't know what your "oracle" is, but without further information what you are asking is whether the following language is decidable:

$L:=\{ (t,u)\in\Lambda\times\Lambda \mathrel{|} t \rightarrow^* u, u \textrm{ normal}\}$

(with $\Lambda$ being the set of $\lambda$-terms). This is obviously not the case: for every Turing machine $M$, there is a $\lambda$-term $t_M$ (effectively computable from the description of $M$) such that $t_M$ reduces to a fixed normal form $u$ if $M$ terminates on the empty string and has no normal form otherwise; therefore, if $L$ were decidable, we would be able to decide the halting problem for $M$ on empty input by asking whether $(t_M,u)\in L$.

If your "oracle" gives more information, then of course the situation may very well be different.  For instance, if the oracle also gives an upper bound to the number of reduction steps needed to reach the purported normal form, then it is obviously decidable whether the oracle's answer is correct.

If you are actually asking about proof-carrying code (like D.W. suggests), please modify your question accordingly and I'll be happy to modify/remove my answer.


How to find the "best vectors" in a given matrix whose sum of products is as small as possible?

The problem is NP-complete.
I sketch a reduction from 3-SAT.

Consider Boolean variables $x_1,\ldots,x_n$ and clauses $c_1,\ldots,c_m$ over these variables, so that each clause consists of three literals.  The question is to decide whether there exists a truth setting of the variables so that every single clause is satisfied (and hence contains at least one true literal).

We construct a matrix with $n+m+1$ rows and $2n+1$ columns.

There is a special row $R^*$, and there is a special column $C^*$.
For every clause $c_j$, there is one corresponding row $R(c_j)$.
For every variable $x_i$, there is one corresponding row $R(x_i)$.
For every variale $x_i$, there are two corresponding columns $C^+(x_i)$ and $C^-(x_i)$.

Let $Z=100(m+n)^{100}$ be a huge integer.

The entry at the crossing of special column $C^*$ and special row $R^*$ is $1/Z^n$. All other entries in row $R^*$ take value $Z$.
All entries at a crossing of $C^*$ with a clause row $R(c_j)$ are $Z$.
All entries at a crossing of $C^*$ with a variable row $R(x_i)$ are $1/Z$.
The crossings of variable row $R(x_i)$ with columns $C^+(x_i)$ and $C^-(x_i)$ take value $Z$; all remaining entries in row $R(x_i)$ are $1$.
If clause $c_j$ contains the positive literal $x_i$, then the crossing of row $R(c_j)$ and column $C^+(x_i)$ is $1/Z$; all other entries in row $R(c_j)$ are $1$.
If clause $c_j$ contains the negative literal $\lnot x_i$, then the crossing of row $R(c_j)$ and column $C^-(x_i)$ is $1/Z$; all other entries in row $R(c_j)$ are $1$.

It can be shown that the 3-SAT instance is satisfiable, if and only if the column selection problem has a solution $S$ for which the sum of products is at most $v=n+m+1$. Some comments:

The set $S$ must contain the special column $C^*$; otherwise the contribution of the special row $R^*$ to the objective function (sum of products) is at least $Z>v$.
The set $S$ can contain at most one of the two columns $C^+(x_i)$ and $C^-(x_i)$; otherwise the contribution of row $R(x_i)$ to the objective function will be at least $(1/Z)\cdot Z\cdot Z>v$.
For every clause $c_j$, the set $S$ must contain some column $C^+(x_i)$ and $C^-(x_i)$ so that the corresponding literal $x_i$ respectively $\lnot x_i$ satisfies $c_j$. Otherwise, the contribution of row $R(c_j)$ to the objective function will be at least $Z>v$.


Remove edges from bipartite graph subject to degree restrictions

This problem is NP-hard as 3DM (3-dimensional matching problem) reduces to it. Just pick M=N=3, Y to be the points of the underlying base set, and X to be the triples on them.


How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts?

One natural thing would be to try a separator kind of trick. If the Voronoi cells are fat, and of similar size then a randomly shifted grid of the right side would do reasonably well. in particular, there is a paper by Miller and Thurston (and some other people - their names escape me) about finding a separator if you have fat regions covering space, and every point is covered only a constant number of times. It is essentially an extension of their proof of the existence of a planar separator to these more general settings.


Summary. A logical framework is a meta-language for the formalisation of deductive systems, where deductions become syntactic objects.

Of course what counts as a meta-language is quite vague, and it is helpful to understand the historical development of logical frameworks.
The first logical framework was de Bruijn's Automath (1), which is based on $\lambda$-calculus. Many of the ideas from the Automath language family have found their way into modern logical frameworks. Martin-Löf's work on constructive type-theories, also based on $\lambda$-calculi, has also been influential.

Edinburgh's LF (2) is a very influential logical framework.
Edinburgh LF is what you get when you enrich the simply typed $\lambda$-calculus with type-dependency. That's all. In order to make type-dependency precise, one needs to replace the function space operator $A \rightarrow B$ on types with type-abstraction, usually written $\Pi x^A. B$, and introduce the kind of types, as well as kind abstraction.
In terms of rules, the key is in the elimiation rule for $A \rightarrow B$, resp. $\Pi x^A. B$:

$$
\newcommand{\TYPES}[3]{#1 \vdash #2 : #3}
\newcommand{\SUBST}[2]{\{#1/#2\}}
\frac{
   \TYPES{\Gamma}{\color{red}{M}}{A \rightarrow B}
      \qquad
   \TYPES{\Gamma}{\color{red}{N}}{A}  }{
 \TYPES{\Gamma}{\color{red}{MN}}{B}   }
      \qquad
\frac{
   \TYPES{\Gamma}{{\color{red}M}}{\Pi x^A. B}
      \qquad
   \TYPES{\Gamma}{\color{red}{N}}{A}  }{
 \TYPES{\Gamma}{{\color{red}{MN}}}{B\SUBST{{\color{red}N}}{x}}   }
$$

On the left we have the rule for the simply typed $\lambda$-calculus, on the right the
rule that generalises the left with type dependency. We see that a value 'flows' into the
type in the conclusion on the right.

I think the interactive proof assistant Isabelle uses intuitionistic second order logic based on $\lambda$-calculus, without any numbers or recursive data types as logical framework. Various others have been proposed.

One advantage of using $\lambda$-calculi as logical framework  is that binding constructs like universal quantifiers can be implemented using the framework's $\lambda$-binder. Note that most logical frameworks are expressively weak: the frameworks  support object-level reasoning, but are insufficient to perform much meta-theoretic reasoning beyond the fact that a particular object-level statement is a theorem. In fact the metal-logic is usually so weak that even proving the deduction theorem for a Hilbert-style object logic is impossible. Of course nothing prevents you from using more powerful type-theories as a logical framework.

For these practical and historical reasons, most logical frameworks in use today are typed $\lambda$-calculi, i.e. type-theories. See (3, 4) for more in-depth discussions of logical frameworks.

N. de Bruijn: The Mathematical Language AUTOMATH, Its Usage, and Some of Its Extensions.
R. F. Harper, F. Honsell, G. Plotkin: A Framework for Defining Logics.
F. Pfenning: Logical frameworks.
F. Pfenning: Logical frameworks -- A Brief Introduction.


Is it known whether hypergraph minimal covers are P-enumerable?

You are looking for an output-polynomial algorithm for enumerating minimal transversals of hypergraphs (or hitting sets for set systems). According to Golovach et al. (ICALP 2013),

  The question whether the minimal transversals
  of a hypergraph can be enumerated in output polynomial time is a fundamental and
  challenging question; it has been open for several decades and has triggered extensive
  research. [...]

  Whether or not all minimal transversals of a
  hypergraph can be listed in output polynomial time has been identied as a fundamental
  challenge in a long list of seminal papers, e.g., [10, 11, 12, 13, 14, 19, 30], and it remains
  unresolved despite continuous attempts since the 1980's.


What is the "question" that programming language theory is trying to answer?

The overall purpose of PLT is to make industrial software
engineering (in a general sense) cheaper (also in a general sense), through optimising the most
important tool (programming languages) and associated tooling
ecosystem.

Some reasons why maths is involved:

PLs are highly non-trivial, and it's not clear that  they
do the right thing without proof. The maths gives a simplified model
of real programming languages. This model lets us study real programming languages in a much simplified setting, removing (hopefully) most problems already at the model level. Real programming languages are currently mathematically intractable. In other words: lambda-calculus is the fruit-fly, the E.Coli, the spherical cow of PLT.
PLT lacks suitable empirical methods, which would be nice / better
to have, so maths is done as a substitute.
The maths is beautiful and deep.
The maths gives a simple, tried and tests research methodology, which  is  important for helping one's  PhD students graduate. Typically, some variant of e.g.:
Investigate PL feature XYZ through adding it to lambda-calculus.
Add simple types for XYZ and prove type-soundness.
Add generics for XYZ and prove type-soundness.
Prove a parametricity theorem for XYZ generics.
Add dependent types for XYZ and prove type-soundness.
Develop a partial type-inference for XYZ dependent types.
Add gradual types for XYZ and prove type-soundness.
Add contracts for XYZ.
Each of those is a paper.  You can stop if your PhD student or postdoc runs out of time.  Each of the above is interesting and will yield insight about generics, parametricity, type inference etc.  This pipeline is a great way of navigating the difficult waters of all possible programming languages. A second way of learning is implementing languages in a compiler, but that's less tractable for an individual.

Whether PLT is needed is an interesting question. Most working
programmers seem to think it's not. They are wrong: most languages developed by
working programmers without a PLT background    (e.g. Javascript, PHP)
start out terrible, and make all the mistakes that PL theorists
long learned how to avoid. If a PL developed by an amateur hits the
mainstream, PL theorists need a decade or so fixing the obvious flaws
(e.g retrofitting a static typing system, see Typescript). Let me summarise this situation:

 Every successful programming language ends up being ML! Either because
 it was designed by a PL theorist as ML from the start, or because a
 decade of painful evolution removes all the obvious flaws, leaving ML. ;-)

Aside:
This state of affairs is entirely   the fault of PLT because because most of them have no industrial programming
experience, so don't really know what the pain points of working
software engineers are. In particular, for sociological reasons, most
PL theorists think that pure functional programming in languages like
Agda is the solution to all problems, which does not stand up to scrutiny.


Given a set of distances (no info regarding what points the distances correspond to) from a complete graph, is the realization of the graph unique?

I think the following example with four points answers your question (though it gives multi-sets of distances). See Reconstructing Sets From Interpoint Distances by Skiena, Smith, and Lemke for more information.


It's common to say that $f$ and $g$ commute with respect to composition (where the property is known as commutativity). See, e.g., http://en.wikipedia.org/wiki/Function_composition.


We did some research on the problem of proving in tree-like Resolution whether a fixed graph $G$ has a clique of size $k$ (where $k$ is usually small). In particular we discovered that refutations of size $n^{\Omega(k)}$ are needed for a large class of graphs.

You can find the paper Parameterized Complexity of DPLL Search Procedures at this link.


I guess you already had a look at Breiman's 2001 paper about RF. I can just point out a few other references:

Empirical comparisons of different RF simplifications that allow proving theorems:  Narrowing the Gap: Random Forests In Theory and In Practice

This is the newest reference I can provide. In this paper you can also find some citations of Biau's papers about initial work on theoretical results for RF.

If you are interested in theoretical results about variable importance in RF: Understanding variable importances in forests of randomized trees

Actually I just found out that last paper's author (Gilles Louppe) just posted on arxiv his PhD thesis (v2): Understanding Random Forests: From Theory to Practice


If the hash function is collision-resistant, it doesn't affect security.

Another way to put it: it affects security, in the sense that you are now reliant upon the security of the hash function to resist collisions.  But if it is infeasible to find collisions in the hash function, and if the underlying signature scheme is secure, then signing a hash of the message is also secure.


Does there exist a sentence of first-order logic that is satisfiable only in infinite models that do not have a finite algorithmic representation?

One possible answer to your question is Tennenbaum's Theorem. It states that no non-standard model of arithmetic can have only computable operations, i.e. either addition or multiplication will be non-computable given any recursive description of the elements of the model.

Now the remaining difficulty is having a single formula which has as models only non-standard models of arithmetic. Note that while arithmetic isn't finitely axiomatizable, there are conservative extensions of PA which are finite.

Now it's easy to build an infinite axiomatization of (an extension of) PA which has only non-standard models: add to PA a constant $c$ and the axioms
$$ c\neq 0,\ c\neq S(0),\ c\neq S(S(0)),\ldots$$

There's a trick to turn this into a finite axiom. Add the binary predicate $\mathrm{NS}$ to your language, along with the axiom
$$ \forall xy,\ \mathrm{NS}(x, y)\leftrightarrow x\neq y\wedge \mathrm{NS}(x, S(y))$$
Then the above schema is expressed by $\mathrm{NS}(c, 0)$.

Important edit: It is crucial that the induction schema (as axiomatized by your finite theory) does not apply to formulas containing $\mathrm{NC}$! Otherwise it is quite easy to show $\forall y,\ c\neq y$ and conclude $c\neq c$, a contradiction. I think that if you exclude those formulas from the induction principle, the above reasoning should go through without trouble.


Simulating nondeterministic space-bounded computation using randomness

My comment was incorrect, and in fact the answer to your question is YES. From Wikipedia:

  Suppose C is the complexity class of
  problems solvable in logarithmithic
  space with probabilistic Turing
  machines that never accept incorrectly
  but are allowed to reject incorrectly
  less than 1/3 of the time; this is
  called one-sided error. The constant
  1/3 is arbitrary; any x with 0 ≤ x <
  1/2 would suffice.

  It turns out that C = NL. Notice that
  C, unlike its deterministic
  counterpart L, is not limited to
  polynomial time, because although it
  has a polynomial number of
  configurations it can use randomness
  to escape an infinite loop. If we do
  limit it to polynomial time, we get
  the class RL, which is contained in
  but not known or believed to equal NL.


Complexity of the coset intersection problem

Moderately exponential time and $\mathsf{coAM}$ (for the opposite of the problem as stated: Coset Intersection is typically considered to have a "yes" answer if the cosets intersect, opposite of how it's stated in the OQ.)

Luks 1999 (free author's copy) gave a $2^{O(n)}$-time algorithm, while Babai (see his 1983 Ph.D. thesis, also Babai-Kantor-Luks FOCS 1983, and a to-appear journal version) gave a $2^{\tilde{O}(\sqrt{n})}$-time algorithm, which remains the best known to date. Since graph isomorphism reduces to quadratic-sized coset intersection, improving this to $2^{\tilde{O}(n^{1/4-\epsilon})}$ would improve the state of the art for graph isomorphism.


Certified compiler and optimizations in Coq/Agda

this paper by Yves Bertot, Benjamin Gr´egoire, and Xavier Leroy builds an optimizing compiler for a C-like language based purely on the Coq specification.  some of this technology is apparently utilized in the CompCert C compiler.

A structured approach to proving compiler
optimizations based on dataflow analysis

it considers the correctness of two optimizations, constant propagation (CP) and common subexpression elimination (CSE), section 4. these optimizations are more advanced than those that are associated with the non Coq-based compiler(s) for the same language. see eg this benchmark chart compared to gcc. (the Coq-based compiler is presumably slower to compile although this is rarely mentioned!)

  An original aspect of ConCert is that most of the compiler is written directly
  in the Coq specification language, in a purely functional style. The executable
  compiler is obtained by automatic extraction of Caml code from this specification.

however at the end of the paper they do note that there are some compiler optimizations in real compilers that cant be modelled in their framework.

improved optimization is not the only element of consideration here, another aspect is that compiler optimization logic can be subject to subtle defects esp due to its complex nature. over the years gcc has been found to have bugs in its numerous optimization logic routines. eg gcc bug?


Aside from the cycle graph, I think a nontrivial class of graphs with $\Omega(n^2)$
distinct min cuts are cactuses. A cactus  is a connected graph in which every block (a maximal 2-connected subgraph) is a chordless cycle.

EDIT: In case the considered cactus has $n$ nodes and $b$ blocks of order $n_1, n_2, \ldots, n_b$, the number of min cuts is $\Omega\left(\sum_{i=1}^b n_i^2\right)$.
As $\sum_{i=1}^b n_i^2 \ge \frac{1}{b} n^2$, the number of min cuts is $\Omega(n^2)$,
provided the number of blocks $b$ is bounded.


How to judge the definition of computational complexity of reals is natural or suitable?

I am not exactly sure what the question is here, but I can try to say a bit to clean up possible misunderstandings.

First of all, if we are talking about complexity of a map $f : \mathbb{R} \to \mathbb{R}$, it makes no sense to ask "What is a good representation for $\sqrt{2}$?" Instead, you have to ask "What is a good representation for all inputs of $f$?". Compare the situation with an easier one in discrete math: when you discuss an algorithm which takes a graph as an input, you do not ask "Should we represent the Petersen graph as as an adjancency list or as a binary matrix?" but instead you automatically think of a uniform representation which will work for all graphs.

Another word of warning. By changing the representation of the input data we can always make any problem (including a non-computable one) trivially computable: in order to make $f : A \to B$ computable, represent the elements of $A$ as pairs $(a, f(a))$. Then you can "compute" $f$ by the second projection. This shows that we need clear criteria of what it means to represent data.

I have written on several occasions about what it takes to represent the elements of $\mathbb{R}$. The answer depends on what structure of $\mathbb{R}$ you are trying to capture. If you are trying to capture no structure, then you can represent all reals with the empty list, for example. A reasonable list of conditions for a representation of $\mathbb{R}$ is that it needs to be such that:

The arithmetical operations $+$, $\times$, $-$, $/$ are computable, as well as the absolute value $|{-}|$.
There is a program which takes (the representation of) a real $x$ and $k \in \mathbb{N}$ and outputs integers $p, q$ such that $|x - p/q| \leq 2^{-k}$, i.e., it is possible to compute arbitrarily good rational approximations.
There is a program which takes (representations of) reals $x$ and $y$ and terminates if, and only if, $x < y$, i.e, the strict order is semidecidable.
Given a sequence (of representations of) $(x_n)_n$ such that $|x_{n+1} - x_n| \leq 2^{-n}$ a representation for the limit $\lim_n x_n$ can be computed.

There are old theorems (see introduction to this paper for references) which explain why these conditions are the correct one. These theorems also show that any two such representations of reals are computably isomorphic, that is, we can translate between them with programs. This sets up some criteria for correctness that throw out faulty ideas.

For example, I hear people say things like "rational numbers can be represented by finite information, so let's use that for rational numbers, and the irrational numbers will have to be represented by infinite information". This sort of thing does not work because it breaks the fourth condition above (consider a limit of irrational numbers -- how will you tell that it is converging to a rational?).

Another example which the above conditions eliminate is the Blum-Shub-Smale model because in it you cannot compute limits of sequences. It is better to say that the BSS model works on a discrete ordered subfield of reals (generated by whatever parameters are present), not on the reals themselves.

Among the correct representations of reals some are more efficient than others, although this is a somewhat difficult topic to discuss because real numbers are infinite objects. Matthias Schröder pointed out that for a reasonable theory of complexity one has to pay attention to the topological properties of the representation.

Finally, how should we measure the complexity of a map $f : \mathbb{R} \to \mathbb{R}$, assuming we have a good representation of $\mathbb{R}$? Because $x \in \mathbb{R}$ is represented by a function, or an infinite stream of information, or some such, we should be using one of the higher-type notions of complexity. Which one probably depends on the representation you are using.

The BSS model  is a also a reasonable circuit complexity model in which we count arithmetical operations. It's just good to keep in mind that this model is not about real numbers, but about something else.


You will need to make some assumptions about what kinds of functions are allowed to get anywhere with this.

The version of the problem where the elements of $S$ are linear functions from $\mathbb{R}$ to $\mathbb{R}$ has been studied, in a projectively dual form: if you think of each linear function $y=ax+b$ as being coordinatized by the pair of parameters $(a,b)$, and reinterpret that pair as the Cartesian coordinates of a point, then finding the minimizer for a given $x$ becomes the problem of minimizing a linear function over a dynamic set of two-dimensional points. This can be handled in polylog time per update by a dynamic convex hull data structure, such as the one by Overmars and van Leeuwen 1981 or its more recent improvements by Timothy Chan.

Piecewise-linear functions can be handled by using a weight-balanced segment tree on the set of breakpoints of the functions to replace each query on a set of piecewise-linear functions by logarithmically many queries on subsets of linear functions. This duality approach can also be generalized to higher degree polynomials instead of linear functions but at the expense of turning the problem into a range searching problem in more than two dimensions, for which the time per update will be significantly higher.


Consequences of a distillation algorithm for PSPACE

Theorem 15.3 of the recent "Parameterized Algorithms" textbook by Cygan et al. states the following:

"Let $L, R ⊆ \Sigma^*$ be two languages. If there exists an OR-distillation of L into R, then $L\in coNP / poly$"

So, I think that if there exists an OR-distillation from a PSPACE-complete language $L$ to itself, then $PSPACE \subseteq coNP/poly$, i.e. not only does the polynomial-hierarchy collapse, but also PSPACE collapses with it.


What is the correct name for the space of genotypes and fitness?

In the context of evolution and evolutionary algorithms it's called a fitness landscape.  In other areas such as statistical physics it's called an energy landscape.

If you have a continuous landscape (in evolution you typically don't) things are fairly straightforward.  From Wikipedia:

  In mathematical terms, an energy landscape can be defined as a pair $(X, f)$ consisting of a topological space $X$ representing the physical states or parameters of a system together with a continuous function $f: X → \mathbb{R}$ representing the energies associated to these states or parameters such that the image of $f$ represents a hypersurface in $\mathbb{R}^n$."

In discrete landscapes things are more complicated since we need to specify which states neighbour each other, essentially giving us a graph underlying the set of solutions.  What you end up with is not as clean as you'd like.  It's a triple $(X,N, f)$, where $X$ is the set of solutions (i.e., possible genotypes), $N:X\to 2^X$ is a neighbourhood function, and $f:X\to\mathbb{R}$ is the fitness function.

For a treatment of these discrete fitness landscapes that should satisfy you with regard to mathematical rigour I would direct you to this survey paper by Reidys and Stadler.


Canonisation of boolean matrices under row and column permutations

This problem is precisely the canonization problem for isomorphism of bipartite undirected graphs. While the lexicographically maximum form may be harder, any canonical form will be GI-hard (and so, in particular, it doesn't matter whether the $P$ and $Q$ are restricted to satisfy $P=Q^{-1}$ or not, as asked in a comment above).

In particular, there is a canonization procedure that takes only $2^{\tilde{O}(\sqrt{n})}$ time (much better than $n! \sim 2^{\Theta(n \log n)}$), by Babai-Luks 1983, though in practice I'd recommend just using nauty.


Quickly finding empty-string producing nonterminals in a CFG

Can't one implement that algorithm in linear time as follows? (Warning I haven't proof-read this too carefully, so bugs are likely.)

In what follows whenever I say "production" I mean to include only those that include no terminals.
Build a list, for each non-terminal, of the productions it appears in. For every production $i$ let $c_i$ count how many distinct non-terminals in the right hand side are currently marked non-nullable. Let $Q$ denote a queue of non-terminals that have been marked nullable but not yet processed. Initialize all $c_i$ to the number of distinct non-terminals in the right hand side of production $i$. Initialize all non-terminals to not nullable. For every non-terminal $Z$ generated by production $i$ with $c_i=0$ add $Z$ to $Q$ and mark $Z$ as nullable.

While $Q$ is non-empty, remove an arbitrary non-terminal $X$ from $Q$ and process it as follows. For every production $j$ that $X$ is in, decrement $c_j$. If a $c_j$ becomes zero, check to see if the corresponding non-terminal $Y$ has been marked nullable already. If not, mark $Y$ nullable and add $Y$ to $Q$.


Sparsification Lemma for k-SAT and Exponential Time Hypothesis

I think your confusion might come from misquoting the statement of ETH.

  $3$-SAT instances (with $n$ variables and $m$ clauses) cannot be solved in time $poly(n)\cdot 2^{o(n)}$.

This statement is not ETH, but rather its weak (but often very useful) corollary. The ETH claims the following:

  There exists a $\delta>0$ such that no algorithm with running time $poly(m)\cdot 2^{\delta n}$ can solve $3$-SAT.

Now we can actually use the Sparsification Lemma to prove the following:

  If ETH holds, then $3$-SAT instances cannot be solved in time $poly(m)\cdot  2^{o(n+m)}$.

Assume that there is an algorithm $A$ which solves $3$-SAT in time $poly(m)\cdot  2^{o(n+m)}$. For any $\delta>0$, we'll construct an algorithm $B_\delta$ which solves $3$-SAT in time $poly(m)\cdot 2^{\delta n+o(n)}$. (This contradicts ETH and finishes the proof.)

First, the algorithm $B_\delta$ takes an input formula $\phi$, applies the Sparsification Lemma with $\varepsilon=\delta$, and in time $poly(m)\cdot 2^{\delta n}$ produces $2^{\delta n}$ formulas $\phi_i$, such that $\phi$ is satisfiable if and only if $\exists i\colon \phi_i$ is satisfiable. Now the algorithm $B_\delta$ solves each of $\phi_i$ using the algorithm $A$. Note that by Sparsification Lemma the number of clauses in $\phi_i$ is $O(n)$, thus, each $\phi_i$ is solved by $A$ in time $2^{o(n)}$. Now the total running time of $B_\delta$ is $$poly(m)\cdot 2^{\delta n} + poly(m)\cdot 2^{\delta n}2^{o(n)}=poly(m)\cdot 2^{\delta n+o(n)}\; .$$


About the origin of the names "immune" and "simple"

I don't know the history, but "immune" always struck me as fairly appropriate terminology. ("Simple" never really did, but I never thought of the analogy with simple groups before - it's nice, even though it's not quite a perfect fit.) The English word immune has two general uses: (1) biological (immune to disease), and (2) more general ("not affected or influenced by something"), and both of these seem to fit with the computability definition. Immune sets are immune (in the non-technical sense) to the effects of (containing infinite) ce sets, in some sense.

It also ties well with "productive", as immune sets are somewhat the opposite of productive sets, and in that context, I think of the use of productive as in "productive cough."


Reference Request: Computational Learning Theory

Another good introductory book is "Foundations of Machine Learning" by Mohri et al.: https://www.amazon.com/Foundations-Machine-Learning-Mehryar-Mohri/dp/0262039400/.  It has a large overlap with the Shai and Shai book, but also quite a bit of content that they don't cover.

There are also good books and surveys on more advanced or specialized topics:

Szepesvári and Lattimore have a nice book on bandits:
https://tor-lattimore.com/downloads/book/book.pdf
Cesa-Bianchi and Lugosi have a difficult but rewarding book on
learning and games: https://www.amazon.com/Prediction-Learning-Games-Nicolo-Cesa-Bianchi/dp/0521841089/
Schapire and Freund have a wonderful book on boosting: https://mitpress.mit.edu/books/boosting

There are more, but I hope this is a good start.


What should a proof of correctness for a typechecker actually be proving?

That's a good question! It asks what we expect from types in a typed language.

First note that we can type any programing language with the unitype: just pick a letter, say U, and say that every program has type U. This isn't terribly useful, but it makes a point.

There are many ways to understand types, but from a programmer's point of view the following I think is useful. Think of a type as a specification or a guarantee. To say that $e$ has type $A$ is to say that "we guarantee/expect/demand that $e$ satisfy the property encoded by $A$". Often $A$ is something simple like int, in which case the property is simply "it's an integer".

There is no end to how expressive your types can be. In principle they could be any kind of logical statements, they could use category theory and whatnot, etc. For example, dependent types will let you express things like "this function maps lists to list such that the output is a sorted input". You can go further, at the moment I am listening to a talk on "concurrent separation logics" which allows you to speak about how concurrent programs work with shared state. Fancy stuff.

The art of types in programming language design is one of balancing expressivity and simplicity:

more expressive types allow us to explain in more detail (to ourselves and to the compiler) what is supposed to be going on
simpler types are easier to understand and can be automated more easily in the compiler. (People come up with types which essentially require a proof assistant and user's input to do type checking.)

Simplicity is not to be underestimated, as not every programmer has a PhD in theory of programming languages.

So let us come back to your question: how do you know that your type system is good? Well, prove theorems that show your types to be balanced. There will be two kinds of theorems:

Theorems which say that your types are useful. Knowing that a program has a type should imply some guarantees, for instance that the program won't get stuck (that would be a Safety theorem). Another family of theorems would connect the types to semantic models so that we can start using real math to prove things about our programs (those would be Adequacy theorems, and many others). The unitype above is bad because it has not such useful theorems.
Theorems which say that your types are simple. A basic one would be that it is decidable whether a given expression has a given type. Another simplicity feature is to give an algorithm for inferring a type. Other theorems about simplicity would be: that an expression has at most one type, or that an expression has a principal type (i.e., the "best" one among all types that it has).

It is difficult to be more specific because types are a very general mechanism. But I hope you see what you should shoot for. Like most aspects of programming language design, there is no absolute measure of success. Instead, there is a space of design posibilities, and the important thing is to understand where in the space you are, or want to be.


The obliviousness of the Turing machine is very crucial for Cook-Levin construction to run in time $t(n) \log t(n)$. If the Turing machine is not-oblivious (that is the head position at $i^{th}$ step of computation is not a function of input length ) then, on different inputs, the head position at $i^{th}$ step can be at various positions. But then writing a constant size formula which depends only on the two cells adjacent to head position and head position itself, to ensure correctness of transition from one configuration to the next, cannot be written without knowing the input(As Kaveh pointed out, it is easy to get a $t(n)^2$ formula without the TM being oblivious). But whereas if the Turing machine is oblivious, we can know the position of head at step $i$ on a input of length $n$. Hence can write this formula for correctness between two adjacent configurations. So I guess you should be asking for a better simulation of oblivious Turing machines which beats $O(m \log m)$. It is already asked here : Oblivious Turing Machine emulation lowerbound.


Regarding your last question: The paper Size-Depth Trade-offs for Threshold Circuits shows that the parity function requires depth-$d$ threshold circuits with $\ge n^{1+\epsilon(d)}$ wires, which is tight up to the function $\epsilon$.  But for gates not even $\Omega(n)$ lower bounds are known.


Characterising invisible equivalences by confluent rewrite rules

Yes.  With M=(λx.x x) per the question, consider the rewrite ζ that takes M M p to M M.

It is confluent, and so characterises a reduction system over the lambda calculus.  Argument sketch for confluence: since M M is closed, we only need to consider critical pairs of the form M M N1 ... Nk.  These can be resolved.

It is an invisible equivalence, because terms of the form M M I ... I (with zero or more I s) are closed unsolvable terms that reduce only to themselves in the base lambda calculus, thus are distinct, and so the infinite set of these terms is nontrivial, and is obviously equated by ζ.

I don't like accepting my answer to my question, so I'll accept an answer from someone who provides a less absurdly incomplete confluence argument.


How can I use my computational theory and analysis powers for the greater good?

Please read William Thurston's answer to the question What's a mathematician to do? on mathoverflow. Just to convince you that it is a must-read, let me quote him.

  The product of mathematics is clarity and understanding. Not theorems, by themselves. Is there, for example any real reason that even such famous results as Fermat's Last Theorem, or the Poincaré conjecture, really matter? Their real importance is not in their specific statements, but their role in challenging our understanding, presenting challenges that led to mathematical developments that increased our understanding.

  The world does not suffer from an oversupply of clarity and
  understanding (to put it mildly). How and whether specific mathematics
  might lead to improving the world (whatever that means) is usually
  impossible to tease out, but mathematics collectively is extremely
  important.

I have great sympathy for your question. I did a PhD in logic as applied within computer science and experienced a crisis of utility at the end. It seemed that the strongest skills and deepest knowledge I had, everything I had trained myself in for was completely irrelevant for obtaining a non-academic job. When Matt Welsh , a tenured faculty member at Havard, posted about leaving for Google there was a discussion in which David Patterson from UC Berkeley made the following comment:

  I don't think most systems people are going to industry for the money nor are those going to academia so that they can be called Professor. We're fortunate to have chosen a field were there are great jobs in industry as well as academia.

I felt, on reading this, that doing a PhD in theoretical computer science was the antithesis of his statement. Now, I have been applying for engineering (not research) jobs in the industry and I have discovered that there is place for us out there.

Algorithms are important and relevant in industry. Several problems in industry require good algorithms. You also need solid engineering and infrastructure to make things work. The number of performance bottlenecks to effectively solving real problems is never ending. If you're good at analyzing time and memory consumption of a real system and improving it, there is a lot of work for you.
Clarity in problem solving is an invaluable skill. You have training in getting to the mathematical essence of a problem and ignoring distracting baggage. You may also be able to implement a good solution, or implement a reduction to a form that can be solved efficiently.
Aesthetics has value. This comment is based on limited exposure but after looking at code that has been open sourced by places like Google and facebook, I see that effort has been made to exercise logical hygiene. If you care about mathematical aesthetics then I expect you may have similar discipline when you program and my impression is that such discipline is valued.
Randomization is at its empowering best in a real system. There are so many situations ranging from protocol design to uses of Bloom filters and clever design of caching mechanisms that rely on randomization to scale. To me seeing randomization in action is as fascinating as seeing it in a theorem and even more satisfying.

There are many people with powers that come with a theoretical computer science education who have gone on to have successful industrial careers. I am not concluding that it is this specific knowledge that made them successful, but it definitely didn't impede them.

In the mid 1970s, an undergraduate at Havard university and an assistant professor wrote a paper titled Bounds for sorting by prefix reversal. When Christos Papadimitriou called up the student to inform him the paper was accepted to Discrete Mathematics, William H Gates had already moved to Albuquerque to start a company.
Ashok K. Chandra, coauthor of the 1979 conference and later 1981 journal paper Alternation is in the industry.
The Algorithms and Theory Group in Google has a lot of formidable theoreticians who, as far as I can tell, work on applied problems as well.

This is just a random and tiny list. My aim is not to be comprehensive but to point out that there are theoreticians everywhere. I hope you enjoy coding, because that is an indispensable skill, and I believe it is one of the few common denominators across computer scientists. Of course, you will not use everything you know on a day-to-day basis. But I don't expect this to be the case even if you stay in academia, unless you continue to work on exactly the same set of problems for years on end. If you were thinking otherwise, try Matthew Might's Illustrated Guide to the PhD.


Maximum Crossing number of topological graph

As Vinicius Santos has already said, this doesn't make sense without further restrictions (you can make any single edge cross itself as many times as you like). But a well-studied variant of this arises if you only allow each pair of edges to cross at most once, and not at all if they share an endpoint. Then, the graph drawings in which every possible crossing exists are called thrackles, and it's a longstanding open problem to characterize them.


Is cubic complexity still the state of the art for LP?

It seems that K.M.Anstreicher has improved the result to $O((n^3/\ln n)L)$ in Anstreicher, Kurt M. "Linear programming in O ([n3/ln n] L) operations." SIAM Journal on Optimization 9, no. 4 (1999): 803-812.. I have not read this paper, but I hope that this answer will help you in some extent.


Open problems related to Graph isomorphism

For the first question: Graph Isomorphism has been considered for at least the following parameters for which fixed-parameter tractability is still open.

pathwidth / treewidth (see [2], has been asked here), maybe solved: http://arxiv.org/abs/1404.0818
cutwidth / bandwidth [1]
treewidth-k vertex deletion set size (feedback vertex set number in [7])
tree / path distance width (see [1]), connected tree distance width (see [3], however you can get quite close to the last one, see section 6.4. of my diploma thesis ) : solved by Y. Otachi  and P. Schweitzer : http://arxiv.org/abs/1403.7238
clique-width / shrub-depth (or SC-depth) (see [4])
maximum degree [5]
genus [6] / crossing number [8]

Note that there is active ongoing research for some them.

[1] : K. Yamazaki, H. L. Bodlaender, B. de Fluiter and D. M. Thilikos. Isomorphism
for graphs of bounded distance width. Algorithmica 24.2 (1999)

[2] : H. L. Bodlaender. Polynomial algorithms for graph isomorphism and chro-
matic index on partialk-trees. Journal of Algorithms 11.4 (1990)

[3] : Y. Otachi. Isomorphism for Graphs of Bounded Connected-Path-Distance-
Width. Algorithms and Computation. Springer, 2012

[4] : http://www.fi.muni.cz/~hlineny/res-en.html#recent

[5] : L. Babai and E. M. Luks. Canonical labeling of graphs. STOC '83.

[6] : I. S. Filotti and J. N. Mayer. A polynomial-time algorithm for determining the
isomorphism of graphs of fixed genus. STOC '80 /
G. Miller. Isomorphism testing for graphs of bounded genus. STOC '80

[7] : S. Kratsch and P. Schweitzer. Isomorphism for graphs of bounded feedback vertex set number. SWAT 2010

[8] : http://math.mit.edu/news/summer/SPURprojects/2012Velednitsky.pdf


You just have to solve the following problem: Find a matching of size exactly $k$ with minimum weight.

It can be solved by reducing to min weight perfect matching. See the paper by Ján Plesnı́k. There is a constant blow up in the number of vertices. So your original problem can be solved in $O(n^3)$ time.


But this no-change-to-q property does not actually hold!

Consider {emp} x := alloc(0) {x |-> 0}.  Now, if I frame in y |-> 3, I get

{y |-> 3} x := alloc(0) {x |-> 0 * y |-> 3}

but, by the rule of consequence, I could change the postcondition to

{y |-> 3} x := alloc(0) {(x |-> 0 /\ x != y) * y |-> 3}

To make this more concrete, suppose y is the number 37.  When I run the allocation command in a completely empty heap, it's possible that I will end up allocating address 37, so that x = 37.  But, if I instead start with a heap containing a single cell at address y = 37, this outcome is no longer possible!  Adding a frame to the precondition has pruned some of the nondeterminism in the postcondition.

The paper "Local action and abstract separation logic" (Calcagno, O'Hearn, and Yang) is all about understanding the frame rule from a deeper, semantic perspective.  The key definition of the paper is locality for "actions", where an action is (the semantic representation of) a program.  Locality says that when you add in some frame heap, the only way that the original postcondition can be changed is by pruning some nondeterminism as above.  And, in fact, pruning only arises because of allocation.


NP complete graph problems about structural properties

I think there are lot of similar problems. Here are two in vertex version and one in edge version:

1) Does a given graph have an independent feedback vertex set? (we don't care about the size of the set).
This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in
Garey, Johnson & Stockmeyer.

2) Does a given graph have a vertex cover that induces a tree? (we don't care about the size of the set).
This paper
gives an NP-completeness proof for this problem (Theorem 2); even for bipartite graphs.

3) Does a given graph have a dominating edge set the edges of which form an induced $1$-regular subgraph?
(also known as dominating induced matching or efficient edge dominating; the vertex version is given in the
second answer by Mohammad.
Again, we don't care about the size of the set).
This problem is NP-complete (well-known, first proved here), even for planar bipartite graphs.

The first two problems are particular examples of the problem class called stable-$\pi$:
Let $\pi$ be a graph property. Does a given graph have a vertex cover satisfying $\pi$?
More NP-complete cases as well as polynomially solvable cases can be found in
this
and in this paper
(and the refs given there) .


Primary source for the equivalence of non-deterministic polynomial time and deterministic polynomial time verification

[An extended comment] I think that the "roots of verification" are already contained in Karp's milestone paper "Reducibility Among Combinatorial Problems" (1972):

  ...
  Let $P^{(2)}$ denote the class of subsets $\Sigma^* \times \Sigma^*$ which are recognizable in polynomial time. Given $L^{(2)} \in P^{(2)}$ and a polynomial $p$, we define $L$ as follows:

  $L = \{ x \mid $ there exists $y$ s.t. $\langle x,y \rangle \in L^{(2)}$ and $\log(y) \leq p(\log(x)) \}$

(however Karp doesn't call $y$ a "certificate")

  ... We refer to $L$ as the language derived from $L^{(2)}$ by $p$-bounded existential quantification.

  Definition 4. $NP$ is the set of languages derived from elements of $P^{(2)}$ by polynomial-bounded existential quantification.

  There is an alternative characterization of NP in terms of nondeterministic Turing machines ... [definition of computation of a nondeterministic Turing machine] ...

and

  ... Theorem 1: $L \in NP$ if and only if $L$ is accepted by a nondeterministic Turing machine which operates in polynomial time ...


Thanks to @emil's comment and this stackoverflow answer, I now know that POSIX extended regular expressions are solvable in O(n) but backreferences are at least NP-hard and maybe NP-complete.


Graph rewriting with one-to-many pattern matching?

Belatedly posting this answer:

This is called set node or multi-object matching. This is implemented in tools like Henshin https://www.eclipse.org/henshin/publications.php and described informally in http://www.cs.le.ac.uk/people/rh122/papers/2006/Hec06Nutshell.pdf, see 3.2.

A more formal account is in "Formal foundation of consistent EMF model transformations by algebraic graph transformation."

Thanks to Reiko Heckel for providing me this answer 1 year ago.


I don't know the answer to Question (1)---I suspect there is no such reduction.  But I have a couple of points to make.

A non-adaptive random self-reduction (to the uniform distribution) is a poly-time randomized algorithm $R$ which, given an arbitrary instance $x$ of length $n$ for the decision problem for $L$, produces a list $y^1, \ldots, y^{q(n)}$ of instances of some second length $\ell(n)$.  We have the properties that

(i) each $y^i$ generated by $R$ is individually uniformly distributed, for any fixed input $x$ (although there may be complicated dependence between the $y^i$s, which in some way "encodes" $x$);

(ii) there is a second poly-time algorithm $R'$ which, given $y^1, \ldots, y^q$ along with their $L$-membership values $b^1, \ldots, b^q$ ($b_i = [y_i \in L]$), outputs the desired value $[x \in L]$.

Feigenbaum and Fortnow prove that if an $NP$-complete language has such a reduction then the Polynomial Hierarchy collapses. The argument applies to other target distributions, not just the uniform distribution.

Now my first point (regarding your Question (2)) is that their result directly gives evidence for the difficulty of showing a worst-case to average-case connection for proof systems certifying unsatisfiability of Boolean formulas.  Because the most natural way you'd try to argue that random unsatisfiable formulas are hard to refute (assuming $NP \neq coNP$), is by exhibiting a random self-reduction as above.  Now in the study of proof systems, it might be natural to allow the recovery algorithm $R'$ to be nondeterministic, for example; I believe the [FF] analysis techniques would still apply, but this would take verification after defining things carefully.

My second point is that non-adaptive random self-reductions as above are not the only way to establish average-case hardness of a language $L$ (assuming its worst-case hardness).  There is also the more general notion of a self-correction reduction, which converts any mostly-correct algorithm for $L$ into a fully-correct algorithm, but which does not guarantee that its individual queries be distributed according to any particular distribution (they may depend heavily on the input $x$).  Bogdanov and Trevisan proved that non-adaptive self-correctors for $NP$-complete languages would also collapse the Polynomial Hierarchy.
But it is completely open whether adaptive self-correctors exist for $NP$-complete languages.  I believe the question of adaptive random self-reductions for SAT is also open.
Even if all of these could be ruled out (under the assumption $PH$ does not collapse, say), there might conceivably still be some other, less constructive proof of a worst-case to average-case hardness connection for $NP$.  Bogdanov-Trevisan give a good discussion of the issues here (see also their survey on average-case complexity).


Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?

We assume that vertex weights can be arbitrary positive integers, or more precisely, they can be positive integers at most 2n.  Then the current task cannot be performed even in a slightly weaker time bound O(n2), unless the transitive closure of an arbitrary directed graph can be computed in O(n2) time, where n denotes the number of vertices.  (Note that an O(n2)-time algorithm for the transitive closure will be a breakthrough.)  This is the contrapositive of the following claim:

Claim.  If the current task can be performed in time O(n2), the transitive closure of an arbitrary directed graph given as its adjacency matrix can be computed in O(n2) time (assuming some reasonable computational model).

Proof.  As a preprocessing, we compute the strongly connected component decomposition of the given directed graph G in time O(n2) to obtain a DAG G′.  Note that if we can compute the transitive closure of G′, we can reconstruct the transitive closure of G.

Now assign the weight 2i to each vertex i of the DAG G′ and use the algorithm for the current problem.  Then the binary representation of the sum assigned to each vertex i describes exactly the set of ancestors of i, in other words, we have computed the transitive closure of G′.  QED.

The converse of the claim also holds: if you can compute the transitive closure of a given DAG, it is easy to compute the required sums by additional work in time O(n2).  Therefore, in theory you can achieve the current task in time O(n2.376) by using the algorithm for the transitive closure based on the Coppersmith-Winograd matrix multiplication algorithm.

Edit: Revision 2 and earlier did not state the assumption about the range of vertex weights explicitly.  Per Vognsen pointed out in a comment that this implicit assumption may not be reasonable (thanks!), and I agree.  Even if arbitrary weights are not needed in applications, I guess that this answer might rule out some approaches by the following line of reasoning: “If this approach worked, it would give an algorithm for the arbitrary weights, which is ruled out unless the transitive closure can be computed in time O(n2).”

Edit: Revision 4 and earlier stated the direction of edges incorrectly.


Is { ww' | HamDist(w,w')>1 } context-free?

The intersection with $R=\{0^*10^*10^*10^*\mid$ even length words$\}$ is context-free, because a PDA can remember two positions, in a way. Anyhow, let's first see what this language $L$ is. Its complement is
$R\setminus L=\{0^a10^b10^c10^d\mid b=n/2 \vee c=n/2 \vee a+d=n/2\}$. Therefore,
$L=\{0^a10^b10^c10^d\mid b\ne n/2 \wedge  c\ne n/2 \wedge a+d\ne n/2\}$. We can rewrite this as
$L=\{0^a10^b10^c10^d\mid b> n/2 \vee  c> n/2 \vee a+d> n/2 \vee b,c,a+d<n/2\}$.

The first $3$ cases can be easily verified, and so can the fourth one.

$b>n/2$: Start putting in the stack until the first 1, then start popping from the stack until it's non-empty. After it's empty, again start putting in the stack until we reach the second 1. From then on pop the stack.

$c>n/2$: Same.

$a+d>n/2$: Start putting in the stack until the first 1, then start popping from the stack until it's non-empty. After it's empty, again start putting in the stack until we reach the third 1. From then on pop the stack.

$b,c,a+d<n/2$: Start putting in the stack until the first 1, then start popping from the stack until it's non-empty. After it's empty, again start putting in the stack until we reach $a+n/2$ (guessed non-deterministically, somewhere between second and third 1). From then on pop the stack.


http://en.wikipedia.org/wiki/Partition_problem mentions two textbooks which cover the subject:

Hans Kellerer; Ulrich Pferschy; David Pisinger (2004), Knapsack problems, Springer, p. 97, ISBN 9783540402862

Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. 105–136. ISBN 0-471-92420-2. MR 1086874.


quasiP-Natural Property again SIZE($n^e$) for fixed e.

If $G: \{0,1\}^k \rightarrow \{0,1\}^{2k}$ is a polynomial time computable pseudorandom generator with security $t(k)$, that is such that every adversary running in time $\leq t(k)$ has distinguishing probability $\leq 1/t(k)$, then we can construct a family of functions $f: \{0,1\}^n \rightarrow \{0,1\}$ such that each function is computable by circuit of size $k(n)^c$, where $c$ is an absolute constant, but the truth-table of a random function from the family is indistinguishable from the truth-table of a truly random function by properties computable in time roughly $t(k(n))$, where we are free to choose $k(n)$ any way we want. Such a family of function contradicts the existence of a natural property computable in time $t(k(n))$ and useful against circuits of size $k(n)^c$.

Now it is a matter to instantiate the parameters. If we believe that there are one-way functions secure against sub-exponential adversaries, then we can take $t(k) = 2^{k^{\epsilon}}$ for an absolute constant $\epsilon >0$. If there were a quasi-polytime natural property that is useful against size($n^e$) for every $e$, then we can take $k(n)= n^{e}$ for every $e$, and the property would still be able to distinguish  our family of functions computed by circuits of size $n^{ce}$ from truly random functions, even though no property computable in time $\leq t(k(n)) = 2^{n^{\epsilon e}}$ can do that. This quasi-polytime computable property is computable in time $\leq 2^{n^d}$ for some absolute constant $d$, and we reach a contradiction when $e > d/\epsilon$. (Recall that $d,\epsilon$ are absolute constants and that we can take $e$ as large as we want.)

The point here is the order of quantifiers. If you are looking for a specific polynomial circuit size, like $n^{10}$, you can have a quasi-polytime natural property that is useful against those circuits, because you can actually explicitly check in time roughly $2^{n^{10}}$ if a given function is computable by a circuit of size $n^{10}$. If, however, you want a quasy-polytime natural property that is simultaneously useful against all circuit sizes $n^e$ for all $e$ (that is, for each $e$, the property becomes useful after a sufficiently large $n$), then you are impyling the existence of sub-exponential distinguishers for pseduroandom generators and sub-exponential inverters for one-way functions.


Results about computability power or limitations of shared read/write registers

You might want to look at the work of Gadi Taubenfeld. Many of his papers deal with  impacts of different progress conditions such as (generalized) wait-freedom or obstruction-freedom on the computability power of shared objects in distributed systems, which includes registers.


Deciding satisfiability and non-validity

For (propositional) intermediate logics, a decision procedure for satisfiability cannot generally be turned into a decision procedure for (non)validity, because all intermediate logics happen to have the same set of satisfiable formulas, namely, the set of classically satisfiable formulas, whereas some (a majority of) intermediate logics are undecidable.

(To make sense of the juxtaposition, all of the intermediate logics should be considered in the language of the weakest one, i.e., $\land$, $\lor$, $\to$, and $\neg$ or $\bot$.)

The coincidence of SAT's for these logics is a consequence of Glivenko theorem (which can be paraphrased by asserting that $\neg\varphi$ is provable classically iff it is provable intuitionistically, for any formula $\varphi$). See also this post.


The correspondence theory of modal logic is concerned with the study of specific types of relations definable by modal formulae. My one sentence description does not do justice to the numerous motivations behind correspondence theory; consider it an explanation of why it relates to your sentence.

Specific examples arising in correspondence theory are the following.

The modal formula $\Box p \implies p$ is true in a frame if and only if the frame is reflexive.
The formula $\Box p \implies \Box \Box p$ is true in a frame if and only if the frame is transitive.

So the types of relations you are asking for can be viewed as being defined by a finite set of modal formulae. These formulae can in turn be viewed as the axioms of a logic, so your question is directly related to the study of modal logics. You can look up material on the model theory of modal logic for more details.

Modal Correspondence Theory, van Benthem
Modal Logic, Blackburn, de Rijke, Venema
Model Theory of Modal Logic, Goranko and Otto


Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$

@Chandra, @Emil, and myself solved the question in the comments. The solution is $$f(n) = 2^{\Theta(n \log \log n / \log n)} \ .$$

To see the lower bound, apply the recurrence definition $\log n$ times, to get $$f(n) = 2f(n - \log n) + f(n - \log n - 1) + \ldots + f(n - 2 \log n) \ge \log n \cdot f(n - \log n) \ .$$
Use this inequality $n / \log n$ times, and we get that the solution is $2^{\Omega(n \log \log n / \log n)}$.

To get the upper bound, use the recurrence $\log n$ times and get that $$f(n) \le (\log n + 1) \cdot f(n - \log n) \ . $$
Use this inequality $n / \log n$ times, and we get that the solution is $2^{O(n \log \log n / \log n)}$.


Can differential equations be classed into their own complexity classes?

A first observation in the direction of decidability of ODEs is this paper by Avigad, Clarke and Gao, which classifies the complexity of $\delta$-decidability, in which solutions are to be found within a certain bounded error (the "delta") in one direction.

one of the main results is that $\delta$-solvability of (Lipschitz-continuous) ODEs is $\mathrm{PSPACE}$-complete.


What are the must-read search trees paper?

Sleator-Tarjan '85 and Demaine et al '09 definitely belong on any such list.
There is a lot of other recent work related to splay trees and dynamic optimality, for instance:

Applications of forbidden 0-1 matrices to search tree and path compression-based data structures, Seth Pettie, SODA 2010
An O (log log n)-competitive binary search tree with optimal worst-case access times, Bose et al, SWAT 2010
Upper bounds for maximally greedy binary search trees, Kyle Fox, WADS 2011.
De-amortizing binary search trees, Bose et al, ICALP 2012
Pattern-avoiding access in binary search trees, Chalermsook et al, FOCS 2015
Weighted dynamic finger in binary search trees, Iacono and Langerman, SODA 2016

On more classical lines, I think

Rank-balanced trees, Haeupler, Sen, and Tarjan, ACM TALG 2015

is worth including as an elegant unification of AVL and red-black trees.


Complexity of Turing self-reducibility of Clique problem?

This is not a reference, but an NP-complete problem cannot have a polynomial-time self-reduction which halves the input size unless NP has a nO(log n)-time algorithm, even if we allow Turing reductions.

Suppose there is a p(n)-time Turing reduction from an NP-complete problem L to itself such that given an input of length n, the reduction only makes queries to strings of length at most n/2.  Then you can convert this reduction to a standalone deterministic algorithm for L by using recursion.  By writing down a recurrence relation for the running time of this deterministic algorithm, it is not hard to see that it runs in time nO(log n).


Hierarchies in NP (under the assumption that P != NP)

Yes! In fact, there is provably an infinite hierarchy of increasingly harder problems between P and NP-complete under the assumption that P!=NP. This is a direct corollary of the proof of Ladner's Theorem (which established the non-emptiness of NP\P)

Formally, we know that for every set S not in P, there exists S' not in P such that S' is Karp-reducible to S but S is not Cook-reducible to S'. Therefore, if P != NP, then there exists an infinite sequence of sets S1, S2... in NP\P such that Si+1 is Karp-reducible to Si but Si is not Cook-reducible to Si+1.

Admittedly, the overwhelming majority of such problems are highly unnatural in nature.