Comparing the Kolmogorov complexity of theories

I'll try and give an answer to this question, and try to clear up some confusion as to the exact form of the question.

The first point I want to make: the $L$ in the statement of Chaitin's constant is indeed a function of $T$. In the absolute sense, it is monotonic in the expressiveness of $T$: if $L(T)$ is the smallest natural number for which
$$T\not\vdash K(s)\geq L(T)$$
for any string $s$, then if $T'$ is a consistent theory stronger than $T$ ($T\vdash\varphi$ implies $T'\vdash\varphi$ for any arithmetic sentence $\varphi$) then $L(T')\geq L(T)$. The argument is very simple: if there exists $s$ such that $T\vdash K(s)\geq L$ then $T'\vdash K(s)\geq L$ by hypothesis.

However, this is only true if $L(T)$ is the absolute Chaitin constant. In particular, if $T'$ proves $\mathrm{Con}(T)$, then
$$ T'\vdash \exists L\forall s\ \lceil T\not\vdash K(\overline{s})\geq \overline{L}\rceil $$

by internalizing Chaitin's argument. However, a concrete $l$ for which

$$ T'\vdash\forall s\ \lceil T\not\vdash K(\overline{s})\geq\overline{l}\rceil$$

will in general not be equal to $L(T)$. In particular it may be much larger, generally proportional to the size of the proof of $\mathrm{Con}(T)$ in $T'$. This can easily be seen in the proof of the theorem itself, which crucially relies on the consistency of $T$.

So while $Q^*$ can prove consistency of the system with bounded induction, the length of these proofs gets longer the closer you get to $Q^*$ in expressiveness (one way to understand the incompleteness theorems is that the length becomes infinite when you reach $Q^*$, thus it has no finite proof of consistency in $Q^*$ itself). Thus the same applies to the various upper bounds on the internal $L(T)$s $Q^*$ can describe for each sub-theory.

So here is the short answer to your question: $L(T)$ is bounded uniformly for all subtheories of $Q^*$, but $Q^*$ itself cannot show that this bound holds for all such sub-theories. This was the crucial mistake Nelson made (buried under several layers of formalism) and that Tao pointed out here.


It's fixed-parameter tractable in the natural parameter, the distance. So if two trees have distance $k$ you can find the distance in time polynomial + $f(k)$ for some function $f$. The proof is a kernelization that produces a kernel of size $O(k)$ so putting that together with the naive method of finding a shortest path in the flip graph gives time singly exponential in $k$. See "Rotation distance is fixed-parameter tractable", Cleary & St. John, Inf. Proc. Lett. 2009, and "An improved kernel size for rotation distance in binary trees", Lucas, Inf. Proc. Lett. 2010. See also "A linear-time approximation for rotation distance", Cleary & St. John, JGAA 2010.


This is an open question. If it is to be true the consequences would imply the collapse of the ${\bf Counting-Hierarchy}$, ${\bf CH}$ for short. In the paper "On the closure properties of #P in the context of PF o #" by Ogihara, Toda, Watanabe and Thierauf" on proposition 2.1 it is stated that

${\bf NP ^{PP}} \subseteq {\bf P^{\#P^{[1]}}} $ if and only if ${\bf CH} = {\bf P^{\#P^{[1]}}} $ if and only if ${\bf FP ^{CH}} \subseteq {\bf FP^{\#P^{[1]}}} $.


Parallel algorithms to find the optimum of polynomials

To the best of my knowledge, parallelization of this problem is not done as you suggested, i.e., searching in parallel the whole space to determine extremal points. A much faster parallelization method for multi-variate polynomials (when appropriate) may be based on the use of parallel automatic differentiation, the (parallel) solution of the resulting system of equations and finally the study of the related Hessian.

However, you may consider non trivial the paper "Polynomial Optimization via Recursions and Parallel Computing", which deals with the problem of finding the global minimum for a special class of dominated real valued polynomials.

"A Parallel-Computing Solution for Optimization of Polynomials" provides a parallel algorithm for determining polynomial positivity.


Difference between a cyclic and a left-recursive context-free grammar?

A context-free grammar is cyclic if there exists a non-terminal $A$ and a derivation in one or more steps $A\Rightarrow^+ A$.  It is left-recursive if there exists a non-terminal $A$, a mixed sequence of terminals and non-terminals $\gamma$, and a derivation in one or more steps $A\Rightarrow^+ A\gamma$.

Hence cyclic implies left-recursive, but the converse does not hold.  Note that a cyclic grammar can have infinitely many parses for a single terminal string---that might be problematic---, while there is little interest in having cycles in the applications I know (natural language processing and programming languages syntax), thus they are usually removed.


Precise definition of syntatic categories / syntatic domains in abstract syntax

Most people avoid giving precise descriptions of what a syntactic category is, because if you do it properly with all the details, the ratio of insight to necessary mathematical sophistication ends up being very, very low. John Reynolds' book Theories of Programming Languages has one of the more comprehensive explanations in its chapter 1, as does Robert Harper's Practical Foundations of Programming Languages.

The intuition you should have is that a syntactic category is the set of trees generated by a context free grammar. Given such a definition for a set of trees, you can define functions on this set using structural recursion, and prove properties about them using structural induction: i.e., by case-analyzing all the different ways that a tree could be constructed.

For example, suppose that we have a language of arithmetic operations given by the following grammar:

e ::= zero | succ(e)| add(e, e)

Then, we can define an interpretation function eval which takes a term and gives you an integer, by cases on the ways we can construct a term:

eval : Expr -> Int
eval zero     = 0
eval succ(e)  = 1 + eval e
eval add(e, e') = eval e + eval e'*

Note that we have completely defined this function by giving one clause for each possible way we could have generated an expression from the grammar. The fact that this is a complete definition of a function is called the principle of structural recursion.

We can also prove properties about this function by using structural induction -- by doing an inductive analysis for each case. For example, we can prove that for every e, eval e ≥ 0.

Proof. By structural induction on e.
- Case e = zero:
  By the definition of eval, eval zero = 0.
  We know 0 ≥ 0 by reflexivity of ≥.

- Case e = succ(e'):
  By induction, we know that eval e' ≥ 0
  So we also know that 1 + eval e' ≥ eval e'.
  By transitivity, 1 + eval e' ≥ 0.
  But eval succ(e') = 1 + eval e'.
  So eval succ(e') ≥ 0.

- Case e = add(e', e'').
  By induction, we know that eval e' ≥ 0.
  By induction, we know that eval e'' ≥ 0.
  By properties of addition, we know that eval e' + eval e'' ≥ 0.
  By the definition of eval, eval add(e',e'') = eval e' + eval e''.
  So eval add(e',e'') ≥ 0.

The fact that considering just the cases for how expressions could be formed constitutes a proof is called the principle of structural induction.

Now, it's a fact that one can define functions by structural recursion and prove properties by structural induction for any grammar. However, proving this rigorously requires a certain amount of category theory; you need to formalize syntactic categories as initial algebras of a certain class of functors, and then prove that such initial algebras always exist for that class.

This is really heavyweight tooling for proving such an "obvious" result, and so I recommend just trusting your intuition about how structural definitions work, and then only bothering with their detailed semantics if you decide to become a professional logician.


Maximum subgraph problem with unknown complexity

look at this paper Lewis-Yannakakis where it is proved that for all non-trivial hereditary properties, it is NP-complete, and see Cai where it is proved that with parameter $\ell$, the problem is FPT for hereditary properties with finite number of obstructions.


Longest path from every vertex in a tournament

This is really just an elaboration of Sasho Nikolov's comment, but the subsequent comment makes clear that it needs elaboration and this doesn't fit within a comment itself.

If you topologically order the strongly connected components of your tournament, then the longest path from any vertex $v$ contains all vertices of the component containing $v$ and all vertices of later components.

To see this, we need the known facts that

Each strongly connected component contains a Hamiltonian cycle.
Condensing the strongly connected components to a single vertex per component produces a directed acyclic graph, which must itself be a tournament.
Any acyclic tournament is totally ordered by the orientations of its edges, so the topological ordering of components is uniquely defined.

So, start from $v$, and follow the Hamiltonian cycle within its own component. Then, when the cycle would return to $v$, instead follow any edge to the next component in the total ordering of the components (there's an edge to that component because there's an edge to every vertex and because the edges connecting the current component to the next component are all oriented in the direction you want to go). Then continue the same way in each successive component.


Maximum matching M with the condition G[M] is 2K_2-free

Surprise! (for me).
This type of matchings are already studied in the literature. They are called connected matchings.

They were introduced by Plummer, Stiebitz and Toft in their study on Hadwiger conjecture. See the chapter "Connected Matchings" by Cameron in the book "Combinatorial Optimization – Eureka, You Shrink!"

The status of connected matchings in bipartite graphs (not necessary balanced) is open to the best of my knowledge (i shall update). The weighted version of the problem is NP-complete for bipartite graphs. The problem is polynomial time solvable for chordal bipartite graphs.

Update: the problem is NP-complete for balanced bipartite graphs (i.e., the exact problem asked in the question). This is proved in the paper "Multitasking Capacity: Hardness Results and Improved Constructions" by Alon et al.  They also report that finding the size of a largest connected matching is hard to approximate within a factor of $n^{1-\epsilon}$ unless NP = co-RP.

Notes added earlier (kept for interested people):
"Connected matchings in chordal bipartite graphs" by Jobson et al. (doi:https://doi.org/10.1016/j.disopt.2014.06.003) and "Connected matchings in special families of graphs" by Caragianis (thesis) are two notable references.


Rigorous security proof for Wiesner's quantum money?

It seems like this interaction can be modeled in the following way:

Alice prepares one of the states $|000\rangle$, $|101\rangle$,$(|0\rangle+|1\rangle)|10\rangle/\sqrt{2}$, $(|0\rangle-|1\rangle)|11\rangle/\sqrt{2}$, according to a certain probability distribution, and sends the first qubit to Bob.
Bob performs an arbitrary quantum channel that sends his qubit to two qubits, which are then returned to Alice.
Alice performs a projective measurement on the four qubit on her possession.

If I am not wrong about this (and sorry if I am), this falls within the formalism from Gutoski and Watrous presented here and here, which implies that:

From Theorem 4.9 in the second of those, it is optimal to Bob to act independently  when Alice repeats this process with several qubits in an independent way, if the objective of Bob is to always fool Alice.
It is possible to obtain the value of c from a small semidefinite program. You can find more details of how to obtain this program in Section 3 here. See the comments for the cvx code for the program and its value.


How to generate Extended Finite State Machines Randomly with some properties?

You can generate a random automaton naively (i.e., every state sends a directed edge uniformly at random to every other state, including itself) and then remove the unreachable states. If you start with $n$ states, you will end up with roughly $cn$ states (where $c$ is explicitly computable), and this is tighly concentrated:
https://dl.dropboxusercontent.com/u/3198145/rand-dfa.pdf

Thus, if your goal is $n$ states, start with, say, $n/c$ states, generate a random automaton, and remove unreachable states. Note that this process does not sample uniformly from all $n$-state automata, but you didn't ask for a uniform distribution. See also references in that linked paper for generating random automata with various properties.


Does this problem related to subset sum have a name?

I've never heard of this problem before, but it's clearly NP-hard.

There's a simple polynomial time reduction from subset-sum to this problem.  All you have to do is take an instance of subset-sum such as:  {x1, x2, x3, ... , x_n} ...and map it to this instance of the problem you describe:  S1 = {x1, x2, x3, ..., x_n}; S2 = {0}.

(I initially misread your question and thought that you were talking about a decision problem; since that was not what you meant, I cannot say anything beyond whether or not it is NP-hard except that it is EXPTIME.  It is likely not NP; see the comments below.)

Either way, I don't think you are going to find any good solution or approximation algorithms.


Resources on Cryptographic Applications of Expander Graphs

I suggest you look at a survey by Oded Goldreich, called A computational perspective on sampling. In that survey he presents some basic facts on expanders (along with pointers to more extensive material). These facts seem to be sufficient to at least understand the "Security Preserving Amplification of Hardness" paper. In particular, in appendix A he surveys random walks on expanders, and in C.4 he presents the expander hitter, which is what is essentially done in that paper.


I briefly reviewed some areas here, trying to focus on ideas that would appeal to someone with a background in advanced mathematical logic.
Finite Model Theory
The simplest restriction of classical model theory from the viewpoint
of computer science is to study structures over a finite universe.
These structures occur in the form of relational databases, graphs,
and other combinatorial objects arising everywhere in computer
science. The first observation is that several fundamental theorems of
first-order model theory fail when restricted to finite models. These
include the compactness theorem, Godel's completeness theorem, and
ultraproduct constructions. Trakhtenbrot showed that unlike classical
first order logic, satisfiability over finite models is undecidable.
The fundamental tools in this area are Hanf locality, Gaifman
locality, and numerous variations on Ehrenfeucht-Fraisse games. The
topics studied include infinitary logics, logics with counting, fixed
point logics, etc. always with a focus on finite models. There is work
focusing on expressivity in finite-variable fragments of first-order
logic and these logics have characterisations via pebble-games. Another direction of enquiry is to identify properties of classical logics that survive the restriction to finite models. A recent result in that direction from Rossman shows that certain homomorphism preservation theorems still hold over finite models.

Finite Model Theory, Ebbinghaus and Flum
Elements of Finite Model Theory, Libkin
On winning strategies in Ehrenfeucht-Fraisse games, Arora
and Fagin, 1997.
Homomorphism preservation theorems, Rossman

The propositional $\mu$-calculus
A line of work from the late 60s showed that numerous properties of
programs could be expressed in extensions of propositional logic that
supported reasoning about fixed points. The modal-$\mu$ calculus is
one logic developed in this period that has found a wide range of
applications in automated formal methods. A lot of formal methods is
connected to temporal logic, or Hoare-style logics and much of this
can be viewed in terms of the $\mu$-calculus. In fact, I have heard it
said that the $\mu$-calculus is the assembly language of temporal
logics.
In his paper introducing the $\mu$-calculus, Kozen gave an
axiomatization and only proved it sound and complete for a restricted
fragment of the logic. The completeness proof was one of the great
open problems in logical computer science until Walukiewicz gave a
proof (based on infinite automata). The model theory of the
$\mu$-calculus has many rich results. Similar to van Benthem's theorem
for modal logic, Janin and Walukiewicz proved that the $\mu$-calculus
is expressively equivalent to the bisimulation invariant fragment of
monadic second order logic. The $\mu$-calculus has also been
characterised in terms of parity games and automata over infinite
trees. The satisfiability problem for this logic is EXPTIME complete
and Emerson and Jutla showed that the logic has the small model
property. Bradfield showed that the alternation hierarchy of the $\mu$-calculus is strict, while Berwanger showed that the variable hierarchy is also strict. Important classical tools used in this area are Rabin's theorem and
Martin's determinacy theorem.

Results on the propositional $\mu$-calculus, Kozen, 1983
Rudiments of $\mu$-calculus Arnold and Niwinski, 2001
Completeness of Kozen's Axiomatisation of the Propositional
$\mu$-Calculus, Walukiewicz 1995
Modal logics and $\mu$-calculi, Bradfield and Stirling, 2001
The modal mu-calculus alternation hierarchy is strict, Bradfield, 1996
The variable hierarchy of the mu-calculus is strict, Berwanger, E. Grädel, and G. Lenzi, 2005

Linear Temporal Logic
Linear temporal logic was adopted from philosophical logic into
computer science for reasoning about the behaviour of computer
programs. It was considered a good logic because it could express
properties such as invariance (absence of errors) and termination. The
proof theory of temporal logic was developed by Manna and Pnueli (and
others, later) in their articles and books. The model checking and the
satisfiability problem for LTL can both be solved in terms of automata
over infinite words.
Pnueli also proved fundamental resuls about LTL in his original paper
introducing the logic for reasoning about programs. Vardi and Wolper
gave a much simpler compilation of LTL formulae into Buchi automata.
The connection to temporal logic has led to intense study of
algorithms for efficiently deriving automata from LTL, and for
determinization and complementation of Buchi automata. Kamp's theorem
shows that LTL with since and until modalities is expressively
equivalent to monadic first-order logic with an order relation. There
is ongoing work extending these results to logics over dense linear
orders and time intervals. Etessami and Wilke developed a variation of Ehrenfeucht-Fraisse games for LTL and used them to show that the until hierarchy is strict. Another line of work is to extend LTL to express arbitrary $\omega$-regular properties. This leads to the linear-time $\mu$-calculus, a linear-time counterpart of the modal $\mu$-calculus. Unlike the modal counterpart, the linear-time alternation hierarchy collapses at level 2.

The temporal logic of programs, Pnueli 1977
From Church and Prior to PSL, Vardi, 2008
An automata-theoretic approach to linear temporal logic,
Vardi and Wolper, 1986
The Temporal Logic of Reactive and Concurrent Systems:
Specification, Manna and Pnueli
An Until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic, Etessami and Wilke, 2000

Computational-Tree Logics
Instead of a linear notion of time, the behaviour of a computer
program can be understood as a tree, leading to the notion of
computational tree logics. The simplest such logic, Computational Tree
Logic can be viewed as an alternation-free fragment of the
$\mu$-calculus. The difference between LTL and CTL led Emerson and
Halpern to develop CTL*, which allows reasoning about both properties
of states and traces.
The model checking problem for CTL over finite structures is in
polynomial time. The model checking problem for CTL* is EXPTIME
complete. The axiomatization of CTL* was a challenging open problem
that was finally resolved by Reynolds 2001. The analogue of van
Benthem's theorem for modal logic and Kamp's theorem for LTL is given
for CTL* by a theorem of Hafer and Thomas showing that CTL*
corresponds to a fragment of monadic second order logic over binary
trees. A later characterisation by Hirschfeld and Rabinovich is that
CTL* is expressively equivalent to the bisimulation-invariant fragment
of MSO with path quantification.

"Sometimes" and "not never" revisited: on
branching versus linear time temporal logic, Emerson and Halpern,
1986
On the Expressive Power of CTL, Moller, Rabinovich, 1999
Computation tree logic CTL* and path quantifiers in the monadic
theory of the binary tree, Hafer and Thomas, 1987
An Axiomatization of Full Computation Tree Logic, Reynolds,
2001

Languages of Infinite Words
The connection to LTL and the necessicity of modelling infinite
behaviour led to an intense study of $\omega$-languages, which are languages in which words are defined as functions from natural numbers to a finite alphabet. The community has studied properties of regular languages over infinite
words and developed several results analogous to the finite-word case. There are several surprises that show up, so we cannot just lift the finite-word results to the infinite-word case.
Some of my favourite results are the characterisiation of $\omega$-regular languages in terms of regular languages and analogues of the
Myhill-Nerode theorems. Staiger showed that you do not just get infinite word automata from an appropriately defined equivalence relation. This holds only for a specific sub-family of $\omega$-regular languages. Alpern and Schneider formalised the intuitive notions of safety and liveness of computer programs in terms of  prefix-closed and limit-closed sets of $\omega$-words. Moreover, using elementary topology, they showed that every linear-time property can be expressed as the intersection of a safety and a liveness property. This result has significant practical consequences because it means that rather than build complex property checkers, it suffices to build a safety and a liveness checker. A further reduction shows that it is enough to build an invariance checker and a termination checker. The safety-liveness characterisation was extended to trees by Manolios and Trefler and more recently to sets of traces, in the hyperproperties framework, by Clarkson and Schneider.

Infinite Words: Automata, Semigroups, Logic and Games, Perrin and Pin, 2004
$\omega$-Languages, Staiger, 1997
Beyond $\omega$-Regular Languages, Bojanczyk, 2010
On syntactic congruences for ω—languages, Maler and Staiger, 1993

Automata on Infinite Words
Where there are languages, computer scientists will have automata. Enter the theory of automata over infinite words and infinite trees. It is extremely sad that although automata over infinite words appeared within two years of automata on finite words, this fundamental topic is rarely covered in standard computer science curricula. Automata over infinite words and trees provide a very robust approach to prove decidability of satisfiability for a very rich family of logics.
A fundamental result is that the different acceptance criteria for
infinite word automata are all equivalent. The basic problems of
union, intersection, and complement for $\omega$-automata are more
involved than their finite word counterparts and the details differ
with the acceptance criterion used. Safra gave a famously complex determinization algorithm for Buchi automata and significant work has been devoted to deriving a new and simpler construction. Rabin famously proved that the monadic second order theory of the binary tree is decidable. His proof uses automata and the cornerstone result is the determinization of Rabin automata. I have heard tell that Rabin's theorem is the mother of all decidability results in program verification.

Decidability of Second-Order Theories and Automata on Infinite Trees, Rabin, 1969
Automata on infinite objects, Thomas, 1988
Automata: From Logics to Algorithms, Vardi, 2007

Infinite Games
Logical and infinite games are an active area of research. Games-theoretic notions show up in computer science all over the place in the duality between non-determinism and parallelism (alternation), a program and its environment, universal and existential quantification, box and diamond modalities, etc. Games turned out to be a great way to study properties of the various types of non-classical logics listed above.
As with acceptance criteria for automata, we have different winning conditions for games and many can be shown to be equivalent. Since you asked about classical results, the Borel Determinacy theorem and Gale-Stewart games often lie discreetly in the background of several game models we study. One pressing question of our times has been about the complexity of solving parity games. Jurdzinski gave a strategy-improvement algorithm and showed that deciding the winner was in the intersection of the complexity classes UP and coUP. The precise complexity of Jurdzinski's algorithm was open until Friedmann gave it an exponential-time lower bound in 2009.

Deciding the winner in parity games is in UP ∩ co-UP, Jurdzinski, 1998
Games for the μ-calculus, Niwinski and Walukiewicz, 1996
An Exponential Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it, Friedmann, 2009


Yes, every regular expression can be converted into an unambiguous one by converting to a DFA and then to a regular expression. And no, there aren't any inherently ambiguous regular languages in the sense described in the question. This is a classic result in automata theory:
 R. Book, S. Even, S. Greibach and G. Ott, Ambiguity in graphs and expressions, IEEE Transactions on Computers 20(2) (1971) 149–153.
See also this question over at MO for more details and a reference: https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous


[I made it into a proper answer b/c somebody gave it -1]

If any clause is allowed to be added, then the language is empty -- clearly to any satisfiable formula $F$ you can add a 3-clause $c$ made up of variables that do not appear in $F$: $F \cup \{ c \}$ will be satisfiable.

If the added clauses must use variables of $F$, then the language is in P.

Justification is as follows:

Take any $F \in L$, i.e. $F \in SAT$ and for any 3-clause $c$ on variables of $F$, $F \cup \{c\} \in UNSAT$. Say $c = l_1 \lor l_2 \lor l_3 \notin F$, where $l_i$ is a literal. Since $F \cup \{ c \}$ is UNSAT, all models of $F$ must have $l_i=0$ (for $i=1,2,3$) - because if some model had e.g. $l_1=1$, then it would satisfy $c$ and so $F \cup \{c\}$. Now, assume that there exists another clause $c'$ that is exactly like $c$, but with one or more literal flipped and such that $c' \notin F$, say $c' = \neg l_1 \lor l_2 \lor l_3$. Then by the same argument all models of $F$ must have $l_1 = 1$. Thus, the necessary condition for $F \in L$ is that for each clause $c \in F$ there are exactly 6 other clauses in $F$ that use the three variables of $c$ -- lets call these 7-clause subsets of $F$ blocks. Note that each block implies a unique satisfying assignment to its variables. When this necessary condition is satisfied, $F$ is either uniquely satisfiable or unsatisfiable. The two cases can be distinguished by testing whether the assignments implied by the blocks of $F$ clash, which can clearly be done in linear time.


Algorithm Suggestion for Scoring System - weighted solution

I don't think this question is related at all with approximation algorithms, or theoretical CS.

Please take the following as some free, non-exhaustive, thoughts on your question.

It seems to me that what you want is just the probability that a given sequence of words contains only valid words.

Let me assume that each word is chosen independently (which it isn't true).
Suppose we have $k$ words, call $\sigma_i$ the i-th of such words.
Call $A_i$ the event "$\sigma_i$ is a valid word" and $A$ the event "all words are valid".

Under this assumptions you have:
$$
P(A) = \prod_{i=1}^{k}P(A_i)
$$

so you only need to assign a probability to each word (and you've already given such a distribution in you question).
However you may want to apply some smoothing: if you set $P(A_i)=0$ for some $A_i$ then also $P(A)$ will be $0$ (if you are sure that a word is not valid, then then the whole phrase cannot be valid).

A bayesian approach only requires conditional independency. For example you can compare the following two quantities (and choose the highest):

$$
P(A | \sigma_1, \dots, \sigma_k) \propto  P(\sigma_1, \dots, \sigma_k | A) P(A) = \prod_{i=1}^{k}P(\sigma_i|A) P(A)
$$
$$
P(A^C | \sigma_1, \dots, \sigma_k) \propto  P(\sigma_1, \dots, \sigma_k | A^C) P(A^C) = \prod_{i=1}^{k}P(\sigma_i|A^C) (1 - P(A))
$$

where $P(\sigma_i|A)$ is the probability that the word $\sigma_i$ appears in a valid phrase, $P(\sigma_i|A^C)$ is the probability that $\sigma_i$ appears in an invalid phrase and and P(A) is the probability that a valid phrase shows up.

In the above we are just differentiating "valid" from "invalid" phrases. If you want to account for "completely valid", "completely invalid" and "mixed up" phrases you can do something similar.

You'll need to assign three probabilities to each word $\sigma_i$: $P(\sigma_i|valid)$, $P(\sigma_i|invalid)$, $P(\sigma_i|mixed)$ and three "a priori" probabilities, for example:

$P(valid) = 0.55$  (most likely)
$P(invalid) = 0.40$ (likely)
$P(mixed) = 0.05$ (not likely)


Families of LDPC codes with constant error fraction corrected

Here are a few examples:

There are the expander codes of Spielman (not to be confused with Sipser-Spielman):
http://www.cs.yale.edu/homes/spielman/Research/ITsuperc.pdf

There are the linear-time codes of Guruswami-Indyk:
https://www.cs.cmu.edu/~venkatg/pubs/papers/lin-zyablov.pdf

There are the expander codes of Zemor:
https://courses.engr.illinois.edu/cs598sgt/zemor.pdf


Techniques for showing non-derivability in logics and other formal proof systems

IME, the following list is easiest to hardest (of course, it's also least to most powerful):

If your system is sound, and you can prove $\lnot \phi$, then you have a nonderivability result, of course.
If you have a lattice-theoretic semantics for your logic, relative to which all your proof rules are valid, then if the meaning of a proposition is not the topmost element of the lattice, then it is not a derivable proposition.
If you know that your logic is complete with respect to a class of models, check to see if there is a particular model in that class which invalidates $\phi$.
Sometimes you can get away with a translation into another logic, and show that derivability over here implies a known nonderivability result over there.
If you have a natural deduction or sequent calculus, check to see if there is a cut-elimination result known, or if you can prove one. If there is, then you can often exploit the subformula property to give simple inductive arguments about nonderivability. (Eg., consistency via cut-elimination is just the statement that there are no cut-free proofs of false, and so if all cuts can be eliminated then there are no inconsistencies.)
If nothing else works, then you can often show consistency/nonderivability results via a logical relations argument. This is the big gun, which works when nothing else does -- in set-theoretic terms, it boils down to a use of the axiom of Replacement, which lets you show huge sets are well-ordered. (This is why you can use it to prove things like normalization of System F.)


A bounded-independence variant of the Berry-Esseen theorem

There are variants of Berry-Esseen for bounded independence, although I have not seen one which is as general as the original theorem. For example Theorem 5.1. in Diakonikolas, Kane, Nelson implies a Berry-Esseen theorem for weighted sums of Bernoulli random variables with bounded independence, as long as none of the weights is too large. If you want error $\varepsilon$ (i.e. Kolmogorov distance from the Gaussian distribution), then $\Theta(1/\varepsilon^2)$-wise independence is necessary and sufficient.


If you are having trouble with the concept of least fixed point, I would recommend spending some time getting a background in more general order theory.

Davey and Priestley, Introduction to Lattices and Order is a good intro.

To see why the transitive closure is the least fixed point, imagine building up the closure from an empty set, applying the logical formula one step at a time.  The least fixed point arrives when you can't add any new edges using the formula.

The requirement that the formula be positive ensures that the process is monotonic, i.e. that it grows at each step.  If you had a negative subformula, you could have the case where on some steps the set of edges would decrease, and this could lead to a non-terminating oscillation up and down, rather than a convergence to the LFP.


Is it possible to decide $\beta$-equivalence within System F (or another normalizing typed λ-calculus)?

No, it's not possible. Consider the following two inhabitants of the type $(A \to B) \to (A \to B)$.

$$
\begin{array}{l}
M = \lambda f.\;f \\
N = \lambda f.\;\lambda a.\; f\;a
\end{array}
$$

These are distinct $\beta$-normal forms, but cannot be distinguished by a lambda-term, since $N$ is an $\eta$-expansion of $M$, and $\eta$-expansion preserves observational equivalence in a pure typed lambda calculus.

Cody asked what happens if we mod out by $\eta$-equivalence, also. The answer is still negative, because of parametricity. Consider the following two terms at the type $(\forall \alpha.\;\alpha \to \alpha) \to (\forall \alpha.\;\alpha \to \alpha)$:

$$
\begin{array}{lcl}
M & = & \lambda f:(\forall \alpha.\;\alpha \to \alpha).\;\Lambda \alpha.\lambda x:\alpha.\;f \;[\forall \alpha.\;\alpha \to \alpha]\;(\Lambda \beta.\lambda y:\beta.\;y)\;[\alpha]\;x\\
N & = & \lambda f:(\forall \alpha.\;\alpha \to \alpha).\;\Lambda \alpha.\lambda x:\alpha.\;f\;[\alpha]\;x
\end{array}
$$

They are distinct $\beta$-normal, $\eta$-long form, but are observationally equivalent. In fact, all functions of this type are equivalent, since $\forall \alpha.\;\alpha \to \alpha$ is the encoding of the unit type, and so all functions of the type $(\forall \alpha.\;\alpha \to \alpha) \to (\forall \alpha.\;\alpha \to \alpha)$ must be extensionally equivalent.


Partition refinement in transition state systems (bisimulation contraction)

From both states in $\{n_1,n_2\}$, action $\pi_1$ takes you to $n_2$, while action $\pi_2$ takes you to states in $\{n_3,n_4\}$.  Hence no refinement of that block takes place.  The second block doesn't refine either; therefore the partition refinement terminates.

At this point you have proved that $n_1$ and $n_2$ are bisimilar and $n_3$ and $n_4$ are bisimilar.  You have computed the maximal bisimulation relation on the states of the given structure.  You then proceed to build a quotient structure, with one state for each equivalence class of the bisimulation relation.

This seems to be the part that puzzles you, but it's really simple: it's just another step in the procedure.  The upper state of the result represents the equivalence class $\{n_1,n_2\}$.  Unsurprisingly, action $\pi_1$ takes you back to that state, and so on.  In general, all states in one block of the partition agree on the block containing the destination state of transitions labeled by a certain action.  Hence constructing the quotient structure is straightforward.

A state of the quotient structure is an initial state if and only if at least one state of its equivalence class is initial.  Then, the structure you build is bisimilar to the one given.

Note that I've used "bisimilar" in two related, but slightly different ways here: bisimilar states, and bisimilar structures.  In this example, first we compute a bisimulation relation on the states of the original structure, then we build a structure that is guaranteed to have the following property: the maximal bisimulation on the states of the two structures matches each initial state of one structure to at least one initial state of the other structure.  A structure with this property is said to be bisimilar to the original one.


Is "two or zero" matching in a bipartite graph NP complete?

The answer here seems to imply there is a more general result. For this particular case, here is a self contained way to reduce the problem to maximum weight perfect matching. Assume $k$ is even.

Given $G=(L\cup R, E)$, we construct a new graph $G'=(V',E')$ as follows, let $|R|=n$.

Add vertices in $R$ to $V'$.
For each vertex $v \in L$, add vertices $v_1,v_2$ to $V'$.
Add vertices $t_1,\ldots,t_{n-k}$ to $V'$.
Add edge $v_1v_2$ to $E'$ for each $v\in L$. It has weight $0$.
Add edge $v_iu$ to $E'$ for each $vu\in E$,$u\in R,v\in L,i\in \{1,2\}$. It has weight $1$.
Add edge $ut_i$ for each $u\in R$ and $1\leq i\leq n-k$. It has weight $0$.

Claim: The maximum weight perfect matching in $G'$ has value $k$ iff the "two or zero" matching has a solution of at least $k$ edges.


Ok, since there's still nothing here in the way of an answer, let me at least make a couple of simple observations:

For graphs of bounded treewidth it should be possible to find a densest minor (or even a minor with specified numbers of edges and vertices) by the usual sort of dynamic program on the tree decomposition, where each state of the dynamic program keeps track of the number of edges and vertices in the part of the minor living in a subtree of the decomposition, the subset of vertices in the bag of the decomposition that participate in the minor, the equivalences between vertices in this subset caused by the minor contractions in the whole graph, and a refinement of this equivalence relation caused by the contractions in the part of the minor living in the subtree.

If so, it would follow that, when the density is below three, it should be possible to find the densest minor in polynomial time (with a constant factor that depends on how close to three the density is). For, the graphs whose densest minor has density $\le 3-\epsilon$ have planar forbidden minors and therefore bounded treewidth.


Can one prove the discovery of a P versus NP solution without actually revealing it?

Or Meir’s comment is almost but not quite right, since it would be satisfied by a proof that P vs. NP is not independent even if the prover didn’t know which. A corrected version is “X is either the hash of a proof that P = NP or the hash of a proof that P $\ne$ NP”, where hash is SHA256, say.  Running that statement through a zero knowledge proof system gives the desired evidence.

However, if I was given such a proof, I would assign higher probability to someone having found a bug in the logical system being used.  It would be quite difficult to surmount that qualification in practice, since bugs in proof systems are fairly common.


Finite-State Automata over a real-valued alphabet

Automata over infinite alphabets have been studied in many contexts (see e.g., this paper as a starting point).
Usually, the model is somewhat different than what you suggest, since just having an infinite alphabet is not very interesting, for the following reason:
Given an automaton with $n$ states, there are only $2^{n^2}$ transition matrices. Thus, if your alphabet has more than $2^{n^2}$ letters, then some letters will induce the same transitions. That is, you can partition them to classes of equivalent symbols.
This essentially reduces the model back to finitely many letters.
Note that the final weights do make a difference, but this has more to do with the standard model of weighted automata.
Typically, we're interested in infinite alphabets in the context of data words: these are words over a finite domain $D$, that represents variables whose range is an infinite domain. Then, a common model is that of variable automata, which have been studied a lot (e.g., this paper and references therein).


Randomness and small circuits complexity classes

Most nonuniform complexity classes—$\mathrm{NC^1}$ included—are closed under the $\mathrm{BP}$ operator by the same argument as $\mathrm{BPP\subseteq P/poly}$: using the Chernoff–Hoeffding bound, the probability of error can be reduced below $2^{-n}$ by running $O(n)$ instances of the circuit with independent random bits in parallel, and taking a majority vote; then by the union bound, a sequence of random bits gives the correct result for all $2^n$ inputs of length $n$ simultaneously with nonzero probability, and in particular, there exists such a sequence. We can hardwire it into the circuit.

This argument applies to any class of circuits that is closed under taking majority of $O(n)$ parallel copies of a circuit, and fixing input gates to constants. In practice, this means any decent nonuniform class above $\mathrm{TC^0}$, as majority is computable in $\mathrm{TC^0}$.

The proof is more complicated for $\mathrm{AC^0}$, because this class does not compute the majority function. (While I haven’t seen the Ajtai and Ben-Or paper, I’d guess they use some sort of approximate majority.)


Algorithm for K-best NON perfect bipartite matchings

After some thinking, I found an answer. If one has a better one I'll accept it.

From a cost matrix of shape $n\times m$ with $n<m$, it is easy to add nodes that will not change anything by giving all their incident edges the same weight $w$, that is adding $(m-n)*m$ edges.


How to compute powers of square matrices?

As you note, computing $A^m$ can be done in $O(\log m)$ times the number of operations for matrix multiplication on $N \times N$ matrices. The answer to your second question is no, at least for asymptotic complexity -- matrix squaring and matrix multiplication have equivalent time/arithmetic complexity (up to constant factors). Reducing squaring to matrix multiplication is obvious. To reduce multiplication to squaring, suppose we wish to compute the product of $A$ and $B$. Form the $2n \times 2n$ matrix $C$ with the block structure:

$[0~~A]$

$[B~~0]$

That is, $C$ has an $n \times n$ all-zeroes matrix in its upper-left quadrant and lower-right quadrant. Note that $C^2$ contains $A\cdot B$ in its upper-left quadrant.


Is it possible to encrypt something in such a way that it can be decrypted by two different keys?

This is possible, for instance using the following straight-forward approach (where $E(\cdot,\cdot)$ is some encryption function and $H(\cdot)$ is a cryptographic hash function):

Input: A message $m$ and a set of keys $\{k_1,\dots,k_n\}$.
Generate a random ephemeral key $k_e$ that is used to encrypt $m$ only.
Output (for instance):
$$(H(k_e), n, (E(k_1,k_e),\dots,E(k_n,k_e)), E(k_e,m))\text.$$

A message's recipient can subsequently decrypt all the encrypted keys $E(k_1,k_e)$ to $E(k_n,k_e)$
using his key $k$ and check whether the result's hash matches $H(k_e)$. If it does, he (highly likely) found the right $k_e$ and can proceed to decrypt $m$.

On the other hand, an adversary who does not have one of the keys $k_1,\dots,k_n$ learns nothing about $k_e$ from the hash $H(k_e)$ (as long as $H$ is not broken) nor any of the encryptions of $k_e$ (as long as $E$ is not broken), so he can't decrypt the message $m$ (as long as $E$ is not broken).

Drawbacks:

This approach leaks the number of keys for which a message is encrypted, which may not be desirable.
The method doesn't scale well if you need to support a larger number of keys, but it should do for as few as two. A possibility to avoid having to decrypt all encryptions of $k_e$ until one matches is to add some key ID (for example, a hash of the corresponding recipient's key) to each encrypted key that a recipient can compare to a hash of his own key, at the expense of a slightly longer ciphertext and potential correlation of the recipients' identities.


What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?

I think for getting 1.99-approximation algorithm this paper by Manurangsi and Trevisan, has the current fastest algorithm.


A clarification in Signature schemes for Strong Unforgeability.

Their comment was not meant to apply to all signature schemes, just the specific construction they are talking about in that paragraph. (Also, it was not meant as a formal statement; it was just mentioned as part of the intuition for their construction.)


Low space computation and branching program

Denoting the class of functions computed by branching programs of size $f(n)$ by $\text{BP}(f)$,
the best known bound seems to be the trivial $\text{DSPACE}(S(n)) \subseteq \text{BP}(2^{O(S(n))})$.
This matches the known inclusions $\text{DSPACE}(\log n) = \text{L} \subseteq \text{L}/poly = \text{BP}(poly)$; if a better bound were known then I would expect it to have been noted by Razborov in his FCT 1991 survey (preprint), or in Jukna's 2012 BFC textbook.


Models of random graphs, for real computer networks

This survey, The structure and function of complex networks by Newman, reviews techniques and models for real complex networks including concepts such as small-world effect, degree distributions, and random graph models. Also, the same author has a nice paper, Random graphs as models of networks, about adaptations of random graphs to model real networks.

References:

1) Random graphs as models of networks, M. E. J. Newman, in Handbook of Graphs and Networks, S. Bornholdt and H. G. Schuster (eds.), Wiley-VCH, Berlin (2003)

2) The structure and function of complex networks, M. E. J. Newman, SIAM Review 45, 167-256 (2003)


How to approximate minimum clique edge cover

Here is a paper that deals with this problem:

John M. Ennis, Charles M. Fayle, and Daniel M. Ennis: Assignment-minimum clique coverings. Journal of Experimental Algorithmics 17(1), 2012.

It also gives some heuristics and experimental results. They don't give worst-case approximation ratios; minimizing the number of cliques instead of the sum of their sizes has only fairly weak approximation guarantees, so I guess it would be similar here.


Textbook/resources for a beginning researcher in (Machine) Learning Theory

People are going to recommend

http://www.cs.nyu.edu/~mohri/mlbook/

and

http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf

-- so I might as well do it first :)

I still think the Anthony-Bartlett is a better start for the mathematically oriented beginner.


A combinatorial version for the polynomial Hirsch conjecture

A friend of mine and me have decided to try the brute-force method and compute some values of $t$ for small values of $n$ and $d$. This is totally impossible without employing pruning, and we hope that the tricks we have found will give some insight in the rest of the problem. So far, we have not managed to get the doubly-exponential running time of the brute force method down significantly (roughly $3^{2^n}$ is our best bound so far) and hence we have not yet reached our original goal of somehow predicting the function behind $f$ from its first few values. We have also not studied all the comments of the previous threads in detail, so some of this may already be known - we basically had fun making our code fast and wanted to post our results somewhere, if I had a functioning LaTeX environment I would have put this on the ArXiV.

Code (it's not exactly production code...): http://pastebin.com/bSetW8JS. Values:

f(d=2, n)=2n-1 for n <= 6

f(d=3, n=3) = 6
{} {0} {01} {012} {12} {2}

f(d=4, n=4) = 8
f(d=3, n=4) = 8
{} {0} {01} {1,02,03} {2,13} {123} {23} {3}
{} {0} {01} {2,013} {1,02,03} {023} {23} {3}

f(d=5, n=5) = 11
f(d=4, n=5) = 11
f(d=3, n=5) = 11
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {012,3} {02,12,013,014} {13,023,04,124} {123,024} {23,24} {234} {34} {4}
{} {0} {01} {012,13} {02,12,013} {03,123,014,024} {023,124} {23,24} {234} {34} {4}

We say that the sequence ${\cal F}_1, ..., {\cal F}_t$ is convex if (*) holds. Our approach constructs convex sequences by appending families to shorter convex sequences, essentially using that if ${\cal F}_1, ..., {\cal F}_t$ is convex, then ${\cal F}_1, ..., {\cal F}_{t-1}$ is convex. We note that ${\cal F}_1, ..., {\cal F}_t$ is convex if and only if for all $A \in {\cal F}_t$ we have that ${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$ is convex. We say that $A$ is compatible with ${\cal F}_1, ..., {\cal F}_{t-1}$ if ${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$ is convex - we save computation time by computing the sets that are compatible with a sequence and then taking the elements of their powerset as the new ${\cal F}_t$, rather than determining if ${\cal F}_1, ..., {\cal F}_t$ is convex directly.

Our next speedup is essentially dynamic programming. We try to find an equivalence relation $\sim$ on convex sequences with the following two properties. First, if ${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$ for two convex sequences, then $A$ is compatible with ${\cal F}_1, ..., {\cal F}_t$ if and only if it is compatible with ${\cal F}'_1, ..., {\cal F}'_t$. Second, if ${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$ and ${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$ is convex, then ${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1} \sim {\cal F}'_1, ..., {\cal F}'_t, {\cal F}_{t+1}$. Furthermore, we would like it if we can determine whether a set is compatible with elements from an equivalence class, and determine a representative of the equivalence class of ${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$ given ${\cal F}_{t+1}$ and a representative of the equivalence class of ${\cal F}_1, ..., {\cal F}_t$. The ensuing dynamic programming algorithm is then obvious. The number of equivalence classes (along with the time taken by the above two operations) then gives a bound on the running time of the obvious dynamic programming algorithm.

For the equivalence we use to get our bound, we use a characterization of convexity that is based on `intervals' as follows. Given a subset $A$ of $\{ 1, \dots, n \}$, we say $A$ is contiguous with respect to a (not necessarily convex) sequence ${\cal F}_1, ..., {\cal F}_t$ if $\{ k \mid \exists B \in {\cal F}_k : A \subseteq B \} = \{ i, \dots, j \}$ for some integers $1 \leq i \leq j \leq n$. We say that $(i, j)$ is the interval for $A$ w.r.t. this sequence. It is easily seen that ${\cal F}_1, ..., {\cal F}_t$ is convex if and only if all subsets of $\{ 1, \dots, n \}$ are contiguous with respect to the sequence.

Now, given a convex sequence ${\cal F}_1, ..., {\cal F}_t$, we mark all subsets of $\{ 1, \dots, n \}$ as not touched, disallowed or active as follows: all elements of ${\cal F}_t$ are active, all elements of ${\cal F}_1, ..., {\cal F}_{t-1}$ are disallowed and all supersets $B$ of sets $A$ whose interval with respect to ${\cal F}_1, ..., {\cal F}_{t-1}$ is $(i, j)$ with $j < t - 1$ are also disallowed. It is immediate that a set $A$ is compatible with the sequence if and only if it is marked as not touched. We define two sequences as equivalent under $\sim$ if their marking is equal. It is easily seen that this equivalence relation satisfies our two properties. For computing whether a set $B$ should be disallowed by the interval condition, we can use the equivalent condition 'there exists a set $C \in {\cal F}_t$ such that for no set $D \in {\cal F}_{t+1}$, $B \cap C \subseteq D$'. $3^{2^n}$ is an immediate bound on the number of equivalence classes.

We also use various extra prunings. We only consider antichains for ${\cal F}_{t+1}$ and we require that the elements of its elements come from ${1, \dots, i}$. Lastly, we use the optimization that ${\cal F}_1 = \{ \{ 1 \} \}, {\cal F}_2 = \{ \{ 1, 2 \} \}$ for optimally long sequences (and similar for ${\cal F}_{t-1}$ and ${\cal F}_t$). We imagine that investigating the behaviour of ${\cal F}_3$ may result in more drastic savings.


What is the complexity of decision tree complexity?

If you have an oracle for $f$, you can compute the optimal decision tree for $f$ in $O(3^nn)$ time and $O(3^n)$ space. Consider a function $g$ that takes as input a partition of the variables into three sets $T$, $F$, $S$ and outputs the size of the smallest decision tree for $f$ when the variables in $T$ are restricted to $1$ and the ones in $F$ are restricted to $0$ (and the remaining ones, in $S$, are unset). The following recurrence holds for $g$:
$$g(T,F,S) = 1 + \min_{v \in S} g(T \cup {v},F,S\setminus \{v\}) + g(T,F \cup {v},S\setminus \{v\}).$$
The base case is that the function $f$ is constant with the given restriction, in which case $g$ is $0$. This recurrence directly leads to a dynamic programming algorithm. If, instead you are looking to compute the minimum depth of a decision tree then the following recurrence does the trick.
$$g(T,F,S) = 1 + \min_{v \in S} \max\big{[}g(T \cup \{v\},F,S\setminus \{v\}), g(T,F \cup \{v\},S\setminus \{v\})\big{]}.$$

On the lower bound side, if $f$ is given in $k$-CNF then deciding whether the decision tree complexity is non-zero amounts to checking satisfiability which is hard to do in time $2^{o(n)}$ assuming Exponential Time Hypothesis (ETH) and in $1.999^n$ time assuming the Strong ETH.


The problem can be solved via the assignment problem/network flow. Create a bipartite graph with the left side consisting of $N$ vertices $a_1,\ldots,a_N$ corresponding to the sets $A_1,\ldots,A_n$. The right side has $m$ vertices $u_1,\ldots,u_m$ one for each element in $U$. Connect $a_i$ via directed arcs of capacity $1$ to each element vertex that $A_i$ contains. Now add a source vertex $s$ and connect it via an arc of capacity $k_i$ to $a_i$. Connect each $u_j$ to a sink vertex $t$ with an arc capacity of $1$. The problem has a solution if and only if there is an $s$-$f$ flow of value $\sum_i k_i$ in this network. An integral flow would give you a desired solution.


Can an oracle allowing errors be non-relativizing?

When considering variations of a computation model, let alone one that is not natural and might confuse our intuition, definitions are of the essense. Your oracle might be in #P but that doesn't mean that is representative of that class. Since you have changed the definition of the function the oracle computes, you will have to either prove the new problem #P-complete or find another appropriate class for which the problem is complete.

Fooling around the complexity zoo, it seems that such a class has already been defined: http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#modp and http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#modkp , depending on how you choose N.


I am still unclear about the precise objective you want to optimise over, but you could look at

Peter Brucker,
Andreas Drexl,
Rolf Möhring,
Klaus Neumann, and
Erwin Pesch,
Resource-constrained project scheduling: Notation, classification, models, and methods,
European Journal of Operational Research
112
3–41,
1999.
doi:10.1016/S0377-2217(98)00204-5

for a comprehensive interdisciplinary overview of related terminology for many such problems.  These kinds of problems are studied in operational research, management science, computer science, and statistics.  There is an extensive literature about nearly every kind of such problem, but it can be hard to find the right terms and to translate between the different styles of exposition.  Good luck!


What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$?

I'm not sure how to answer (1), but (2) is known to imply circuit lower bounds against NQP (non-deterministic quasi-polynomial time). This is from Cody Murray and Ryan Williams' STOC 2018 paper.

In fact, they show that these lower bounds follow from faster algorithms for what they call Gap Circuit Unsatisfiability: given a circuit $C$ on $n$ variables and the promise that either (a) $C$ is unsatisfiable, or (b) $C$ has at least $2^n/4$ satisfying assignments, determine which of (a) and (b) is the case. This problem is easily solved with randomness, so this hypothesis is perhaps more likely than a faster algorithm for Circuit Satisfiability.

Ryan has a very nice talk on this thread of work; a recording in two parts is available here and here.


Practical example: how to formally verify "file name" implementation from a spec?

In general, the technique used is known as "fuzzing". Not all errors are equally likely. Let's consider two hypothetical errors:

System A incorrectly rejects a filename if it contains an | anywhere.
System A incorrectly rejects a filename if it contains a prime number of b characters.

Errors of the second type are much, much rarer, but this is not explained by Computer Science. It's a result from how humans construct software. Fuzzing tries to focus on typical human bugs. In this case, we can predict the following types of errors are more likely:

Very short paths and very long paths may have boundary errors.
Errors near the begin or end of the path are more common than errors at the end
Many characters can be organized into classes which are treated identically, such as lowercase characters. All characters in this class are treated equally, so whether a filename is valid does not depend on a substitution within the class.
Some characters are a priori known to be problematic and each should be treated as a class on its own. (Examples: <>/\&:")
Duplicating characters is more likely to cause bugs the closer they're together.

Fuzzing aims to generate a smaller set of strings by omitting irrelevant variations. We obviously generate an initial set of testcases of all possible lengths (1-200). This checks rule 1. We then expand this set by varying a few characters near both ends. We might try varying the 150th character of the 170 character testcase, but we won't bother with all 254 variations. Nor will we add a variation in the 151th character.


Making a minimum-width tree decomposition lean in polynomial time

Here is a formal reason why the problem is not poly-time solvable unless P=NP. We know that finding the treewidth of a given graph is NP-Hard. Given a graph $G$ we can add a disjoint clique of size $V(G)+1$ to create a new graph $G'$. A min-width tree-decomposition of $G'$ can be obtained as follows: it has two nodes with one bag containing all the nodes of the clique and the other containing all the nodes of $G$. Now making this tree-decomposition lean would require finding a lean-tree decomposition of the original graph $G$ which would, as a by-product, give the treewidth of $G$.


Getting started with Hashing for Information retrieval

Probably this may help you. May not cover all but I found this as a great place to start. http://burtleburtle.net/bob/hash/


Is the integer factorization problem harder than RSA factorization: $n = pq$?

As far as I can see, an efficient algorithm for factoring semiprimes (RSA) does not automatically translate into an efficient algorithm for factoring general integers (FACT). However, in practice, semiprimes are the hardest integers to factor. One reason for this is that the maximum size of the smallest prime is dependent on the number of factors. For an integer $N$ with $f$ prime factors, the maximum size of the smallest prime factor is $\lfloor N^\frac{1}{f} \rfloor$, and so (via the prime number theorem) there are approximately $\frac{f N^\frac{1}{f}}{\log(N)}$ possibilities for this. Thus increasing $f$ decreases the number of possibilities for the smallest prime factor. Any algorithm which works be successively reducing this space of probabilities will then work best for large $f$ and worst for $f=2$. This is borne out in practice, as many classical factoring algorithms are much faster when the number being factored has more than 2 prime factors.

Further the General Number Field Sieve, the fastest known classical factoring algorithm, and Shor's algorithm, the polynomial time quantum factoring algorithm, work equally well for non-semiprimes. In general, it seems much more important that the factors by coprime than that they be prime.

I think part of the reason for this is the decision version of factoring co-primes is most naturally described as a promise problem, and any way of removing the promise of the input being semiprime is to either

introduce an indexing on the semiprimes (which in itself I suspect is as hard as factoring them), or
by generalising the problem to include non-semiprimes.

It seems likely that in the latter case the most efficient algorithm would solve FACT as well as RSA, though I have no proof of this. However, a proof is a little to much to ask for, since given an oracle for RSA proving that this cannot efficiently solve FACT amounts to proving that $P\neq NP$.

Lastly it is worth pointing out that RSA (the cryptosystem, not the factoring problem you defined above) trivially generalizes beyond semi-primes.


Communication complexity of Independent Set game?

Yes, there is a large 0-fooling set.
It is enough to prove this for $r=2$, as we can add (the same) $r-2$ independent vertices to all graphs in our construction.
For $r=2$, take every graph that has exactly ${n\choose 2}/2$ edges.
Everyone will fool around with its complement.


No such matrix exists.

The Desnanot-Jacobi identity says that for $i \neq j$,
$$
\det M_{ij}^{ij} \det M = \det M_i^i \det M_j^j -\det M_i^j \det M_j^i
$$
so using this, we get
$$
\det M_{12}^{12} \det M = \det M_{1}^{1} \det M_{2}^{2} - \det M_{1}^{2} \det M_{2}^{1}
$$
But your requirements force the left-hand-side to be 0 (mod 2) and the right-hand-side to be 1 (mod 2), showing they are incompatible.


Advantages of ANN classifiers over the AdaBoost

from comments, by request:

In terms of running time, performance, something else? In terms of error rates, these two methods are hard to compare theoretically. AdaBoost's performance depends on the choice of a base learner and whether the weak learning assumption is satisfied in the particular instance. ANN will work for some problems/distributions but not others. I think this question would be better answered in a different forum.


Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

The Hamiltonian path problem on grid graphs with maximum degree 3 is NP-complete. The proof is in C. H. Papadimitriou and U. V. Vazirani, On two geometric problems related to the travelling salesman problem, Journal of Algorithms, Volume 5, Issue 2, June 1984, Pages 231–246 (Theorem 2)


You can improve this bound by grouping the arms into "almost optimal" arms (arms whose expected payoffs are within a fixed $\Delta$) and the rest of the arms.  So you can bound the regret contributed by the almost optimal arms by $O(T \Delta)$, which actually implies that the worst-case setting of $\Delta$ is approximately $\sqrt{N/T \log T}$, and not a value arbitrarily close to $0$.

This is explained, for example, in section 1.3 of these lecture notes.


"Send Once"-One way Multiparty Communication Complexity

There are several flavors of communication complexity.  It sounds like your "send once" model is uses one-way communication and private messages.  For concreteness, I give short synopses of some different communication complexity variants below.

Say there are k players who wish to jointly compute a function f(x_1,...,x_k) on k different inputs.  Some different variants:

(1) One-way complexity vs interactive communication:  In this setting, player 1 sends a single message, then player 2, etc.  Player k computes the output of the protocol.  With interactive communication, players may speak back and forth.

(2) Broadcast vs. private-messages models:  In the broadcast model of communication, each message is received by all players.  In the private-messages model, messages are sent point-to-point i.e., a message can come from player i to player j.  In this model, if player i wants to communicate with all players, he must send individual messages to each other player.  Broadcast messages is a stronger model, so lower bounds in the broadcast model will give you lower bounds in the private-messages model, and upper bounds for private-messages will give you upper bounds in the broadcast model.

(3) NIH vs. NOF complexity:  In the Number-in-Hand (NIH) communication model, player i sees only x_i.  In the Number-on-the-Forehead (NOF) communication model, player i sees all inputs except x_i.  NOF lower bounds are harder to show, because players share inputs.  Intuitively, this should allow players to compute a function using less communication, thus making lower bounds harder to prove.

As I said, I sense that you're looking for one-way communication with private messages (and perhaps importantly you're assuming the private messages only go from player i to player i+1).
This setting is not very well-studied, but the NIH version of this setting is extremely well-motivated:  The standard reduction from communication complexity to one-pass streaming algorithms naturally gives you a one-way protocol where player i sends a single (private) message to player i+1.  Thus, lower bounds in this setting yield streaming algorithm lower bounds.

There are a couple of reasons why the one-way private-message model is not-as-studied, despite having such strong motivation.  First, there's a longer history and more established toolbox for proving lower bounds in the broadcast model.  Second, the lower bounds achieved from the broadcast model are typically very close to the upper bounds you get from the streaming algorithms, so it's not always necessary to use private-messages for your lower bounds.

One example where the communication bound crucially uses private-messages and not broadcast messages is the following bound for estimating the length of the longest increasing subsequence in a stream:

Gal, Gopalan SIAM Journal of Computing 2010. Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence

Note that their communication bound is for deterministic protocols.  Determining the space complexity of randomized streaming algs for estimating LIS is a big open problem.

For the private messages NIH communication model, there is a recent paper by Woodruff and Zhang that gives several strong communication lower bounds, as well as good applications towards distributed functional monitoring.   They mostly cover interactive (rather than one-way) communication complexity, but it's worth reading.

Woodruff, Zhang STOC12. Tight Bounds for Distributed Functional Monitoring


The keywords you want to look into are "AC Unification," "ACU Unification," and "Associative-commutative unification." People have been looking into this for a long time (see this 1987 paper, for example).


Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

There are many links between discrepancy theory and computer science, and Bernard Chazelle has beautifully surveyed some of them in his book. A number of links have been found more recently as well, for example Kunal's blog post talks about the connection to differential privacy from [MN] and [NTZ]. Another example is Larsen's idea of using discrepancy to prove update/query time lower bounds for dynamic data structures. Many of these links can be instantiated with homogeneous arithmetic progressions (HAPs). This would give:

upper bounds on the $\varepsilon$-samples for range spaces of HAPs
lower bounds on time required to update/query a dynamic data structure for HAP range counting
lower and upper bounds on the error required to privately answer HAP queries

However, there two things that you must realize with respect to these links. One is that it is not clear that range spaces of HAPs are very natural. When do you expect to have input that is a multiset of integers and want to answer how many elements of a HAP are in the input? I cannot think of a situation when this comes up, but maybe I am missing something.

Another thing that you must realize is that all these applications rely on the notion of hereditary discrepancy. This notion is more robust than discrepancy which makes it more tractable: there are stronger lower bounds available for it, it is approximable to within polylogarithmic factors, and it is approximately equal to the value of a convex optimization problem. The result Kunal talks about in the blog post (paper is here) and the construction by Alon and Kalai that Kalai wrote about in this blog post together essentially settle the hereditary discrepancy of HAPs. As Kunal explains, intuition for the lower bound on the hereditary discrepancy of HAPs came from the tight connection between hereditary discrepancy and differential privacy, together with prior results in differential privacy.

However EDP is about the discrepancy of HAPs. Discrepancy is much more brittle than hereditary discrepancy, and that makes it harder to lower bound. This also makes it less useful in applications than hereditary discrepapncy. And this is why EDP is still wide open while the hereditary discrepancy question is fairly well understood.

Let me finish with one approach to attack EDP that is inspired by computer science ideas. There is a way to relax discrepancy to a semidefinite program, see the survey by Bansal for details. The optimal value of the semidefinite program is lower bounded by the value of any feasible solution to its dual program. So one can attempt to prove EDP by exhibiting a family of dual solutions to this semidefinite relaxation of discrepancy, and showing that the value of the dual solutions goes to infinity. I see no reason why such an attack cannot work, in particular we do not know how to construct solutions to the semidefinite relaxation that have constant value for arbitrarily large instances. In fact a lot of the effort in polymath5 was centered around finding or ruling out dual solutions with particular structure.

The discrepancy of arbitrary arithmetic progressions is $\Theta(n^{1/4})$ in the worse case: the lower bound is known as Roth's 1/4 Theorem. Lovasz gives a proof of the theorem using semidefinite programming (although by arguing directly about the primal rather than by constructing dual solutions). For the proof, see Section 5.2. of his SDP survey.


Verifying consistency of strict and non-strict partial orders constraints

You may find it helpful to think of your problem in terms of equalities and strict inequalities.

In the case of the constraints being equalities or disequalities there is a simple saturation procedure based on transitivity of equality.  Strict inequalities can be represented by directed edges in a graph. You can then compute strongly connected components to reason about dependencies between sets of variables. If you have uninterpreted functions, you can use congruence closure.

I would imagine that the first results date to the 50s or at least the 70s, but I do not have a good reference for you. Recent literature in which these ideas occur is the paper below.

  An Interpolating Decision Procedure for Transitive Relations with Uninterpreted Functions, Georg Weissenbacher.


Can words in regular languages be generated by automata in a unique way?

Maybe I misunderstood your question, but wouldn't a Deterministic Finite Automaton do what you want?


Is it right to call $2^{\sqrt{n}}$ "exponential"?

In general I agree with usul's summary: for upper bounds $2^{\sqrt{n}}$ is certainly at most exponential, and for lower bounds it's more context-dependent and less clear. Let me offer a couple more examples from different contexts, and provide the term "moderately exponential" for your consideration.

In the literature on graph isomorphism (which is typically dealing with upper bounds), $2^{\sqrt{n} poly(\log n)}$ (or even just $2^{n^c}$ with $c < 1$) is often referred to as moderately exponential (though I understand this term has a different meaning the context of exact algorithms for $\mathsf{NP}$-complete problems; for the relation between the two, see the Appendix to Paolo Codenotti's Thesis). In some sense one can view this as very humble, but not belittling, terminology: it recognizes how far such algorithms are from polynomial (or even quasi-polynomial) while still acknowledging that it represents quite significant progress over the brute force $n!$ algorithm, or even over singly-exponential ($2^{\Theta(n)}$) algorithms.

Referring to a $2^{\sqrt{n}}$ lower bound as moderately exponential could serve a similar function: humble enough to differentiate it from $2^{\Omega(n)}$ lower bounds, but significant enough to distinguish it from merely super-polynomial. On the other hand:

$2^{n^{O(1/d)}}$ lower bounds for depth $d$ Boolean circuits (or the corresponding Frege classes in proof complexity) are often referred to as "exponential lower bounds" to distinguish them from "merely" super-polynomial or quasi-polynomial lower bounds. However, as getting a $2^{\Omega(n)}$ lower bound in these situations can be quite important, the latter may sometimes be referred to as "strong exponential lower bounds" or sometimes "truly exponential lower bounds" to distinguish it from the "merely" $2^{n^{c}}$ lower bounds (with $c < 1$).
In the context of depth 4 algebraic circuits, $2^{\tilde{\Omega}(\sqrt{n})}$ lower bounds have been referred to as exponential. Note that getting any stronger lower bounds would separate $\mathsf{VP}$ from $\mathsf{VNP}$.

(Even in the context of Graph Isomorphism, I could see someone, perhaps informally, referring to a $2^{\sqrt{n}}$ lower bound as "exponential", since it would be understood that there is a $2^{O(\sqrt{n \log n})}$ upper bound so essentially no stronger exponential lower bound could be hoped for...)


Language and automata textbook, free or low cost?

Maheshwari and Smid's Introduction to Theory of Computation is free, with a Creative Commons license. It has some computability and complexity theory as well but seems to be primarily on languages and automata.


When does an FO property kill off NL-hardness?

Let me call the property in your "Actual Problem" $\text{NODIAG}$. The following mapping reduces $\text{CYCLE}$ to $\text{CYCLE} \cup \text{NODIAG}$:

For a given $G=(V,E)$, replace every vertex $v$ in $G$ by two copies $v$ and $v'$, and if there is an edge $(u,v)$ in $E$, let $G'$ have edges $(u,v), (u,v'), (u',v)$ and $(u',v')$.
Thus for every $G$ the graph $G'$ satisfies $\neg \text{NODIAG}$.

Moreover, $G'$ has a cycle iff $G$ has a cycle, therefore $G'$ satisfies $\text{CYCLE} \cup \text{NODIAG}$ iff $G$ satifies $\text{CYCLE}$. Therefore $\text{CYCLE}\cup \text{NODIAG}$ is NL-hard.

I think a similar construction would work for every purely universal property.


Multidimensional arithmetic progression variant

The book Additive Combinatorics by Terence Tao and Van Vu discuss arithmetic sequences in depth from a mathematical point of view.  They establish the existence of arithmetic sequences under various conditions of your set $X$.

Example: Szemeredi Theorem

If a subset positive "density"  in your lattice it has infinitely many arithmetic progressions of arbitrary length.

$$\displaystyle \mathrm{density}(E) =  \limsup_{N \to \infty}  \frac{|E \cap [1,N]| }{N} \geq 0$$

Let $E \subseteq \mathbb{N}$ be set of positive upper density, then $E$ has a non-trivial $k$-term arithmetic progression.

You could totally imagine looking for vectors arranged in various patterns rather than restrict your attention to $\mathbb{Z}$.

The book simplifies very technical Fourier analysis and probability replacing it with less technical Fourier theory and probability.   They break down the heavy duty math into lemma and theorem that are useful for more specific problems.

Example Consider a random set $E \subset [1,N]$ with probability $\mathbb{P}[k \in E] = \frac{1}{2}$.  Any  3 evenly spaced numbers elements $a, a+d, a+2d \in \mathbb{N}$ will chosen inside $E$ with probability $\frac{1}{8}$, so we can expect many arithmetic progressions in the random set $E$.

On the other extreme is using the floor function  $\{[n \sqrt{7}] : n \in \mathbb{Z}\} = \{ [  0,   2,   5,   7,  10,  13,  15,  18,  21,  23,\dots \}$.  This is about as "ordered" as you can get, and it will also have many arithmetic progressions of arbitrary length.

Then it would be up to you to consider the run-time aspects of the algorithms they are implying.  It may not necessarily be easy to find arithmetic sequences in the prime or square free numbers even if we know they exist.


Can Isorecursive types capture mutually recursive data types?

In general, for any type (or domain, or complete lattice) $X$ we can consider the least fixed-point operator $\mu_X : (X \to X) \to X$. For recursive types we take $X = \mathsf{Type}$, i.e., we apply $\mu$ at the universe of all types. Given a system of mutually recursive equations
\begin{align*}
A &= F(A, B)\\
B &= G(A, B)
\end{align*}
where $F, G : X \times X \to X$, rewrite this as a single equation
\begin{align*}
(A,B) = (F(A,B), G(A,B))
\end{align*}
and then define $H : X \times X \to X \times X$ by $$H(A,B) = (F(A,B), G(A,B))$$ so that the original system becomes an ordinary fixed point equation
$$P = H(P)$$
where $P = (A, B)$. This shows that mutual recursion at $X$ is ordinary recursion at $X \times X$. In terms of the $\mu$-operator we may therefore solve the original system as
$$(A,B) = \mu_{X \times X} P . (F(P), G(P)).$$
In the case of recursive types, just set $X = \mathsf{Type}$.

We may further wonder whether we can replace $\mu_{X \times X}$ with two nested applications of $\mu_X$, i.e., perhaps it is the case that
$$\mu_{X \times X} P . H(P) = \mu_X A . \mu_X B . H(A, B),$$
or something like it. Indeed, Bekić's Lemma [1] explains how to compute the fixed point on $X \times X$ in terms of fixed points on $X$, namely
$$\mu_{X \times X} (A,B) .(F(A,B), G(A,B)) = (A_0, B_0)$$
where
\begin{align*}
A_0 &= \mu_X A . F(A, \mu_X B . G(A,B)), \\
B_0 &= \mu_X B . G(A_0,B).
\end{align*}
Note however that the inner $\mu_X$ in $A_0$ computes a fixed point in the presence of a free parameter $A$, which may be tricky depending on the exact situation.

In summary, you have a choice in solving systems of recursive type equations: either you generalize $\mu$ to pairs of types, or you allow parameters to appear when you apply $\mu$.

[1]: Hans Bekić (1969) Definable operations in general algebras, and the theory of automata and flowcharts. Published posthumously in: Jones C.B. (eds) Programming Languages and Their Definition. (1984) LNCS, vol 177.


A recent one, presented at ICALP is

Markus Lohrey, Christian Mathissen: Isomorphism of Regular Trees and Words. ICALP (2) 2011: 210-221

You will find the paper both on arxiv
and here.

Another example is  Mostowski epimorphism (see P-completeness and efficient parallelization by Satoru Miyano, and the paper by Dahlhaus):

Dahlhaus E, Is SETL a suitable language for parallel programming - a theoretical approach, Computer science logic, 1st Workshop, CSL ’87, Karlsruhe/FRG 1987, Lect. Notes Comput. Sci. 329, 56-63, 1988)

Instance: a directed acyclic graph $D = (V, A)$ satisfying the axiom of extensionality and two vertices $x_1, x_2 \in V$

Problem: Decide whether $M_D(x_1) = M_D(x_2)$, where $M_D$ is the Mostowski epimorphism for $D$.


Quantum GCD circuit: On reversibility and clearing ancillae

It looks like they just directly translated the algorithm into a circuit, so it's not too hard to reproduce.

Write out the binary gcd algorithm as a loop:

def gcd(a, b):
    let shift = 0
    while a != 0 or b != 0:
        let pa = a & 1
        let pb = b & 1
        let pc = a >= b

        if pa == 0 and pb == 0:
            a >>= 1
            b >>= 1
            shift++
        elif pa == 0:
            a >>= 1
        elif pb == 0:
            b >>= 1
        elif pc:
            a -= b
            a >>= 1
        else:
            b -= a
            b >>= 1

    return (a | b) << shift

Keep track of any intermediate values so you can uncompute them instead of leaking them. Also switch to a fixed number of iterations to avoid leaking the size of the inputs.

def gcd(a, b, len_a, len_b):
    let shift = 0
    # Note: >> and << are now bit rotations instead of bit shifts
    for i in range(len_a + len_b):
        let g = a > b
        let pa = (a & 1) == 0
        let pb = (b & 1) == 0

        if pa and pb and a != 0 and b != 0: shift++
        if pa: a >>= 1
        if pb: b >>= 1
        if not pa and not pb:
            if g:
                a -= b
                a >>= 1
            else:
                b -= a
                b >>= 1

        # We can't clear these yet, so just set them aside until later
        push g, pa, pb

    let result = (a | b) << shift

    # Uncompute intermediate values
    for i in range(n + m):
        pop pb, pa, g

        if not pa and not pb:
            if g:
                a <<= 1
                a += b
            else:
                b <<= 1
                b += a
        if pb: b <<= 1
        if pa: a <<= 1
        if pa and pb and a != 0 and b != 0: shift--

        unlet pb = (b & 1) == 0
        unlet pa = (a & 1) == 0
        unlet g = a > b

    unlet shift = 0
    return result

Convert to a circuit.

(Edit: oops, I forgot the shift part. You'll have to add that part in yourself.)

It takes $O(n)$ iterations to guarantee the inputs have been reduced all the way down, and each iteration requires $\Omega(\lg n)$ depth and $O(n)$ gates so the overall bound is $O(n^2)$ gates and $O(n \lg n)$ depth.

Now, all that being said, you need to be wary of the fact that the result is not totally coherent. Before doing interference-y stuff with it, I'd want to be a lot more careful about ensuring the stashed ancilla are independent of the computed gcd. Also you'd want to do any computation in the middle so that the result doesn't have to co-exist with the inputs.

But I hope this gives the general idea.


Find the maximum subset contained by a ball of radius R

Here is a slightly-better-than-raw-brute-force algorithm for $D$-dimensional Euclidean space. It's about as trivial as you can get with this kind of problem short of "check all subsets of points for being in a disk of radius at most $R$", but I figure it's nontrivial enough to serve as a baseline for future answers.

Suppose you have a disk that contains a collection of points, say the optimal disk that you're looking for. Unless there are points on its boundary, you can wiggle this disk around/shrink its radius to contain the exact same collection of points. Hence there can be many optimal choices of the disk. The main idea here is to focus only on disks that are easy to describe, namely those which are determined by some points on the boundary. With this restriction, we'll only need to consider a finite number of disks, and the rest of the algorithm will just be to enumerate all of these disks and count how many points each contains.

So now focus on a particular disk containing a fixed set of points. With translations, you can get one point on the boundary. We now consider some cases, which I'll outline for $D = 3$, though they generalize.

If we have exactly one point on the boundary, imagine moving the center of the disk toward that boundary point and shrinking the radius so that the boundary point stays on the boundary. As we do this, one of two things happens: either the radius gets to zero without any other points crossing the boundary (in which case the disk contained only a single point in the first place), or else some other point enters the boundary.
If we have exactly two points on the boundary, this forces the center to lie in the plane of points equidistant to the two points on the boundary. Now imagine moving the center toward the midpoint of the two boundary points, and adjusting the radius accordingly. One of two things happens: the center reaches the midpoint of the two boundary points without any additional points crossing the boundary, or else some point enters the boundary. In the first case, we have two antipodal points on the sphere (which determines the disk); in the second case, we now have a collection of three (non-colinear) points on the boundary.
There are three non-colinear points on the boundary, but every collection of four or more is coplanar. Consider the plane defined by the boundary points, and draw the circle defined by them within this plane. This circle is included in the boundary of the disk, and moreover the center of the disk must lie on the line perpendicular to the plane running through the center of the circle. Consider moving the center of the sphere along this line, toward the center of the circle, and adjusting the radius accordingly. One of two things happens: either the center of the disk reaches the center of the circle without any points crossing the boundary, or else a new point (not on the plane defined by the initial boundary points) enters the boundary. In the first case, we have some three non-colinear points on a greater circle on the disk (which determines the disk); in the second case, we have at least four non-coplanar points on the boundary.
Finally, the case where we have at least four non-coplanar points on the boundary. Here (in $D = 3$), this completely determines the disk.

It follows that you can enumerate every collection of $1, 2, \ldots, D+1$ points, compute the appropriate disk, check that its radius is at most $R$, and then count the number of points in it. You can compute the disk in time $O(D)$ in each case, and you can naively count the points inside the sphere in $O(n\cdot D)$ time. This gives an overall time of $O(D\cdot n^{D+2})$.

If you know some more information about what your input looks like, there are very likely to be some heuristic optimizations you can put on top of this algorithm. A simple example is ignoring any collection containing two points with distance greater than $2\cdot R$.


Computational Complexity:

If you are looking for recent complexity textbooks. The following two are must have.

Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak (Textbook homepage)
Computational Complexity: A Conceptual Perspective by Oded Goldreich (Textbook homepage)

The majority of the content between these two books is comparable. However, some key differences exist: Goldreich devotes more space to exploring the conceptual and philosophical basis of complexity theory, whereas Arora/Barak covers a wider selection of topics, including concrete models of complexity, quantum computation, and circuit lower bounds that are mostly absent from the former.

Another option, an older but timeless textbook in complexity is:

Computational Complexity by Christos Papadimitriou

Papadimitriou's book is notable for chapters covering first-order logic as well as the classes SNP, MaxSNP$_0$, and APX (the theoretical foundations of hardness of approximation), which are missing from the more modern texts.

Another (comparatively) old, but quite notable classic is:

Introduction to the Theory of Computation by Michael Sipser

This is one of the few/first textbooks that explicitly includes "Proof Idea:" between "Theorem:" and "Proof:", and is one of the best-written mathematical textbooks on any topic. On the other hand, it is only an intro to complexity, devoting only one 50-page chapter to "advanced topics" (including approximation, probabilistic algorithms, IP=PSPACE, and crypto). As a first book on complexity, or as an example of truly excellent writing, this book is great.

The Nature of Computation by Cristopher Moore and Stephan Mertens

Scott Aaronson writes that this book has "the fun of a popular book with the intellectual heft of a textbook." It tells stories and gives lots of entertaining examples and references (Game of Life, and lots of other examples for Turing-complete machines).
It doesn't go too deep into complexity theory but has great breadth. Especially of note are its connections to statistical physics.


How can non-terminating $\lambda$-terms be turned into fixed-point combinators?

There are several aspects to this very nice question, so I will structure this answer accordingly.
$\newcommand{\setof}[1]{\{#1\}}$
$\newcommand{\thra}{\twoheadrightarrow}$
$\newcommand{\codeof}[1]{\lceil #1 \rceil}$

1.
The answer to the boxed question is no.  The term $\Omega_3 = (\lambda x.xxx)(\lambda x.xxx)$ suggested by your friend is indeed a counterexample.

It was earlier noticed in the comments that one has counterexamples like the "ogre" $K^\infty=Y K$, until the question is restricted to terms without weak head normal form.  Such terms are known as zero terms.  These are terms which never reduce to a lambda, under any substitution.

For any fixed point combinator (fpc) $Y$, $Y I$ is a so-called mute (AKA "root-active") term: every reduct of it reduces further to a redex.

$K^\infty$ is not mute; neither is $\Omega_3$ $-$ as is manifest by inspecting its set of reducts, which is
$$\setof{\Omega_3 \underbrace{(\lambda x. xxx) \cdots (\lambda x. xxx)}_k \mid k \in \mathbb{N}}$$

Rather than give a precise argument why $Y I$ is mute for all fpcs $Y$ (indeed, for any looping combinator) $-$ which may be laborious yet hopefully clear enough $-$ I will treat the obvious generalization of your question, restricting to mute terms as well.

Mute terms are a subclass of zero terms which are a subclass of unsolvable terms.  Together these are perhaps the most popular choices for the concept of "meaningless" or "undefined" in the lambda calculus, corresponding to the trivial Berarducci, Levy-Longo, and B\"ohm trees, respectively.  The lattice of notions of meaningless terms has been analyzed in detail by Paula Severi and Fer-Jan de Vries. [1] The mute terms constitute the bottom element in this lattice, i.e., the most restrictive notion of "undefined".

2.
Let $M$ be a mute term, and $Y$ be a looping combinator with the property that $YI = M$.

First we argue that, for a fresh variable $z$, $Yz$ actually looks a lot like the $Y_M$ you described, obtained by "sprinkling $z$ around" some reduct of $M$.

By Church-Rosser, $YI$ and $M$ have a common reduct, $M'$.  Take a standard reduction $R : YI \thra_s M'$.  Every subterm of $M'$ corresponds to a unique subterm of $YI\equiv Yz[z:=I]$ under this reduction.  For any subterm $C[N]=M'$, $R$ factors as $YI \thra C[N_0] \thra_{wh} C[N_1] \thra_i C[N]$, where the middle leg is a weak head reduction (and final leg is internal).  $N$ is "guarded" by a $z$ iff this second leg contracts some redex $I P$, with $I$ a descendant of the substitution $[z:=I]$.

Obviously, $Y$ has to guard some subterms of $M$, for otherwise it would be mute as well.  On the other hand, it must be careful not to guard those subterms which are needed for non-termination, for otherwise it could not develop the infinite B\"ohm tree of a looping combinator.

It thus suffices to find a mute term in which every subterm, of every reduct, is needed for non-normalization, in the sense that putting a variable in front of that subterm yields a normalizing term.

Consider $\Psi = W W$, where $W = \lambda w. w I w w$.  This is like $\Omega$, but at every iteration, we check that the occurrence of $W$ in the argument position is not "blocked" by a head variable, by feeding it an identity. Putting a $z$ in front of any subterm will eventually yield a normal form of shape $zP_1\cdots P_k$, where each $P_i$ is either $I$, $W$ or a "$z$-sprinkling" of these.  So $\Psi$ is a counterexample to the generalized question.

THEOREM.  There is no looping combinator $Y$ such that $YI = \Psi$.

PROOF.  The set of all reducts of $\Psi$ is $\setof{WW,WIWW,IIIIWW,IIIWW,IIWW,IWW}$.  In order to be convertible with $\Psi$, $YI$ must reduce to one of these.  The argument is identical in all cases; for concreteness, suppose that $YI \thra IIWW$.

Any standard reduction $YI \thra_s IIWW$ can be factored as
\begin{align*}
YI \thra_w P N_4, P \thra_w Q N_3, Q \thra_w N_1 N_2, \text{thus }
YI \thra_w N_1 N_2 N_3 N_4\\
N_1 \thra I, N_2 \thra I,
N_3 \thra W, N_4 \thra W
\end{align*}

Let us refer to the reduction $YI \thra_w N_1 N_2 N_3 N_4$ as $R_0$, and the reductions starting from $N_i$ as $R_i$.

These reductions can be lifted over the substitution $[z:=I]$ to yield
\begin{align*}
R^z_0 : Yz \thra z^k(M_1 M_2 M_3 M_4)\\
N_i \equiv M_i[z:=I]
\end{align*}
so that $R_0$ is the composition $YI \stackrel{R^z_0[z:=I]}{\thra} I^k(N_1 \cdots N_4) \thra^k_w N_1 \cdots N_4$.

Similarly, we can lift each $R_i : N_i \thra N \in \setof{I,W}$ as
\begin{align*}
R^z_i : M_i \thra N^z_i\\
R_i : N_i \stackrel{R^z_i[z:=I]}{\thra} N^z_i[z:=I] \thra_I N
\end{align*}

The second leg of this factorization of $R_i$ consists precisely of contracting those $I$-redexes which are created by the substitution $N^z_i[z:=I]$.  (In particular, since $N$ is a normal form, so is $N^z_i$.)

$N^z_i$ is what we called a "$z$-sprinkling of $N$", obtained by placing any number of $z$s around any number of subterms of $N$.  Since $N \in \setof{I,W}$, the shape of $N^z_i$ will be one of

\begin{align*}
&z^{k_1}(\lambda x. z^{k_2}(x))\\
&z^{k_1}(\lambda w.
  z^{k_2}(
    z^{k_3}(
       z^{k_5}(
         z^{k_7}(w)
         z^{k_8}(\lambda x. z^{k_9}(x))
       )
       z^{k_6}(w)
    )
    z^{k_4}(w)
  ))
\end{align*}

So $M_1 M_2 M_3 M_4 \thra N^z_1 N^z_2 N^z_3 N^z_4$, with $N^z_i$ a $z$-sprinkling of $I$ for $i =1,2$ and of $W$ for $i=3,4$.

At the same time, the term $N^z_1 N^z_2 N^z_3 N^z_4$ should yet reduce to yield the infinite fpc Bohm tree $z(z(z(\cdots)))$.  So there must exist a "sprinkle" $z^{k_j}$ in one of the $N^z_i$ which comes infinitely often to the head of the term, yet does not block further reductions of it.

And now we are done.  By inspecting each $N^z_i$, for $i \le 4$, and each possible value of $k_j$, for $j \le 2+7\lfloor \frac{i-1}{2} \rfloor$, we find that no such sprinkling exists.

For example, if we modify the last $W$ in $IIWW$ as $W^z = \lambda w. z(wIww)$, then we get the normalizing reduction
$$ IIWW^z \to I W W^z \to WW^z \to W^z I W^z W^z
\to z (I I I I) W^z W^z \thra z I W^z W^z $$

(Notice that $\Omega$ admits such a sprinkling precisely because a certain subterm of it can be "guarded" without affecting non-normalization.  The variable comes in head position, but enough redexes remain below.)

3.
The "sprinkling transformation" has other uses.  For example, by placing $z$ in front of every redex in $M$, we obtain a term $N = \lambda z. M_z$ which is a normal form, yet satisfies the equation $N I = M$.  This was used by Statman in [2], for example.

4.
Alternatively, if you relax the requirement that $Y I = M$, you can find various (weak) fpcs $Y$ which simulate the reduction of $M$, while outputting a chain of $z$s along the way.  I am not sure this would answer your general question, but there are certainly a number of (computable) transformations $M \mapsto Y_M$ which output looping combinators for every mute $M$, in such a way that the reduction graph of $Y_M$ is structurally similar to that of $M$.  For example, one can write
$$
 Y \codeof{M} z =
\begin{cases}
z (Y \codeof{P[x:=Q]} z)
&M\equiv (\lambda x.P)Q\\
Y \codeof{N} z &M \text{ is not a redex and }M \to_{wh} N
\end{cases}$$

[1] Severi P., de Vries FJ. (2011) Decomposing the Lattice of Meaningless Sets in the Infinitary Lambda Calculus. In: Beklemishev L.D., de Queiroz R. (eds) Logic, Language, Information and Computation. WoLLIC 2011. Lecture Notes in Computer Science, vol 6642.

[2] Richard Statman. There is no hyperrecurrent S,K combinator. Research
Report 91–133, Department of Mathematics, Carnegie Mellon
University, Pittsburgh, PA, 1991.


Comparing SAT to MCSP reduction class separations and faster SAT class separations?

If SAT is in polylog space then PH should also be in polylog space, since the typical complete problems work under logspace reductions. By padding this implies e.g. Sigma3EXP is in PSPACE. So yes, in this case PSPACE is not in P/poly but moreover PSPACE has functions requiring maximum circuit complexity. At any rate the algorithmic hypothesis here is a lot more unlikely than the lower bound conclusion, in my mind, so I'm not sure how interesting this implication is.

(Note SAT in QuasiP would imply EXP has functions of maximum circuit complexity, for similar reasons.)

Definitely if SAT has fast enough algorithms then MCSP has faster algorithms due to SAT's NP-completeness. Beyond that I don't see an immediate connection


Is there a sense in which we can say error returned from a function is the reverse of context?

A duality between exceptions and states was observed and worked out by Jean-Guillaume Dumas, Dominique Duval, Laurent Fousse, and Jean-Claude Reynaud.

TL;DR: Reader and exception monads are obviously dual.

In your setup, I think it works as follows. Let $S$ be the type of environments in which a program might run (you call them contexts, but I'd rather save that word for typing contexts), and let $E$ be a type of errors that a program may raise. The environments here are read-only.

A program which runs in environment of type $S$, takes input of type $A$, and outputs a result of type $B$ has type
$$S \times A \to B.$$
A program which may raise an error of type $E$, takes input of type $A$, and outputs a result of type $B$ has type
$$A \to E + B.$$
We clearly have a duality here. If we imagine that this is all hapenning in some category $\mathcal{C}$, then $X \times A \to B$ in $\mathcal{C}$ is the same thing as $B \to X + A$ in the dual category $\mathcal{C}^\mathrm{op}$.