Brute force search algorithm for semidefinite programming (representation of spectrahedron)

The question is not very well defined.  E.g., if the SDP has an optimal solution, then "searching" that one optimal solution is (trivially) enough to find a good approximate (in fact optimal) solution.  Similarly, any algorithm that solves the SDP in finite time will find a "good approximate solution" while considering only finitely many points of the SDP.

But if you mean to ask whether the feasible region of every SDP is the convex closure of finitely many extreme points, or whether, for any SDP, there is a finite set $S$ of points in the feasible region such that, for any linear objective, some point in $S$ is approximately optimal, the answer is surely no.

For example, fix $\epsilon>0$ and consider the SDP
$$\min \{\epsilon X_{11} + X_{22} :
X\in\mathbb{R}^{2\times 2},~X \text{ p.s.d.}, X_{12} = X_{21} = 1\}.$$
The feasible region consists of 2d p.s.d. matrices of the form $\left(\begin{array}{cc}x&1\\1&y\end{array}\right)$. The matrix is p.s.d. iff $x,y> 0$ and $xy\ge 1$.  So there are infinitely many matrices $X$ (those with $y=1/x$) in the feasible region that are not convex combinations of other matrices in the region.

Further, the unique optimal point has $(x,y)=(1/\sqrt{\epsilon}, \sqrt{\epsilon})$ and has value $2\sqrt{\epsilon}$.  The feasible region is independent of $\epsilon$, and, for any finite subset $S$ of that feasible region (where $S$ is independent of $\epsilon$), letting $x' = \min\{ X_{22} : X\in S\} > 0$, no point in $S$ has value less than $x'$.  So, for sufficiently small $\epsilon$ (where $\sqrt\epsilon \ll x'$), no point in $S$ approximates the optimum well.


Solve multiple instances of SAT with a 2-approximating #SAT query

Here's a sketch argument for constant $m$. I'll use $Z(\cdot)$ to denote the operator that takes a formula to its number of satisfying assignments. Let $T$ be a parameter to be determined later. You can easily construct formulae $\phi'_i$ with $Z(\phi'_i)=1+2^{2^iT}Z(\phi_i)$ for each $1\leq i\leq m$. Let $\phi$ be the conjunction $\phi'_1\wedge\cdots\wedge \phi'_m$ (renaming the variable sets to be disjoint if necessary). Then $Z(\phi)=\prod_{i=1}^m(1+2^{2^iT}Z(\phi_i))$, so $\frac 1 T \log_2 Z(\phi)$ is roughly the sum of $2^i$ over all $i$ such that $\phi_i$ is satisfiable. I believe the error term is $O(n/T)$ for fixed $m$ where $n$ is the total number of variables, so taking $T$ to be a sufficiently large $T$ polynomial in $n$, you can recover which $\phi_i$ are satisfiable from a $2$-approximation to $Z(\phi)$.


You may already be aware of this, but if f is a Bregman divergence, then this arg min always has an easy solution. The specific form depends on the order of the parameters, but if the expression being minimized is

$$ \arg\min_a \sum_i f(x_i, a) $$

where $f$ is a Bregman divergence, then the answer is always the mean of the $x_i$. If the order of parameters is the other way around, then you can use the duality of Bregman divergences. Specifically, if $f$ is generated by a strictly convex function $\phi$, then the solution is the $\phi$-mean $c$ given by $$\nabla \phi(c) = (1/n)\sum_i \nabla \phi(x_i)$$.

Another interesting case is when $f$ is the Euclidean norm (not squared). In that case, the arg min is the well known Fermat-Weber point, and has been extensively studied in operations research. There's a globally optimal iterative scheme to solve it, but no closed form expression.


Complex analysis in theoretical computer science

It's not a single problem, but the entire field of analytic combinatorics (see the book by Flajolet and Sedgewick) explores how to analyze the combinatorial complexity of counting structures (or even algorithm running times) by writing down an appropriate generating function and analyzing the structure of the complex solutions.


A fixed-depth characterization of $TC^0$? $NC^1$?

Barrington's Theorem ought to get you poly-size depth-3 circuits for $NC^1$ with a top gate that's not too strange (multiplies 5 cycles).


Can affine lambda calculus solve every problem in P?

Edit: my guess in the first paragraph below is wrong!  Ugo Dal Lago pointed out to me a later paper by Martin Hofmann (appeared in POPL 2002), of which I was unaware, showing (as a corollary of more general results) that the system from the ATTPL book is in fact complete for $\mathsf P$ (in spite of not being able to compute every function in $\mathsf{FP}$).  So, to my surprise, the answer to the main question is yes.

Concerning the system you are referring to (from the ATTPL book), I am pretty sure it cannot decide every language in $\mathsf P$.  It certainly cannot compute every function in $\mathsf{FP}$: as mentioned in the notes of that chapter, that system is taken from Martin Hofmann's LICS 1999 paper ("Linear types and non-size-increasing polynomial time computation"), in which it is shown that the representable functions are polytime and non-size-increasing, which excludes lots of polytime functions.  It also seems to give a serious limitation on the size of the tape of the Turing machines you can simulate in that language.  In the paper, Hofmann shows that you can encode linear space computation; my guess is that you will not be able to do much more, i.e., the class corresponding to that system is roughly the problems solvable simultaneously in polytime and linear space.

Concerning your second question, there are several $\lambda$-calculi that can solve exactly the problems in $\mathsf P$. Some of them are mentioned in the notes of the ATTPL chapter you are referring to (Sect. 1.6): Leivant's tiered $\lambda$-calculus (see his POPL 1993 paper, or the paper with Jean-Yves Marion "Lambda Calculus Characterizations of Poly-Time", Fundamenta Informaticae 19(1/2):167-184, 1993), which is related to Bellantoni and Cook's characterization of $\mathsf{FP}$; and the $\lambda$-calculi derived from Girard's light linear logic (Information and Computation, 143:175–204, 1998) or from Lafont's soft linear logic (Theoretical Computer Science 318(1-2):163-180, 2004). Type systems arising from these latter two logical systems and ensuring polytime termination (while still enjoying completeness) may be found in:

Patrick Baillot, Kazushige Terui. Light types for polynomial time computation in lambda calculus. Information and Computation 207(1):41-62, 2009.

Marco Gaboardi, Simona Ronchi Della Rocca. From light logics to type assignments: a case study. Logic Journal of the IGPL 17(5):499-530, 2009.

You'll find lots of other references in those two papers.

To conclude, let me expand on Neel Krishnaswami's remark.  The situation is a bit subtle.  All of the above $\lambda$-calculi may be seen as restrictions of more general calculi, in which you can compute much more than just the polytime functions, say for example system F.  In other words, you define a property $\Phi$ of system F programs $P:\texttt{string}\rightarrow\texttt{bool}$ such that:

soundness: $\Phi(P)$ implies that the language decided by $P$ is in $\mathsf P$;

completeness: for every $L\in\mathsf P$, there is a system F program $P$ deciding $L$ such that $\Phi(P)$.

The interest is that the property expressed by $\Phi$ is purely syntactic and, in particular, decidable.  Therefore, completeness can only hold in an extensional sense: if $L$ is your favorite language in $\mathsf P$ and if $P$ is your favorite algorithm for deciding $L$ expressed in system F, it may be that $\Phi(P)$ does not hold. All you know is that there is some other system F program $P'$ deciding $L$ and such that $\Phi(P')$ holds.  Unfortunately, it may happen that $P'$ is much more contrived than your $P$.  Indeed, completeness is proved by encoding polynomially-clocked Turing machines as system F terms satisfying $\Phi$. Therefore, the only guaranteed way of solving $L$ using your favorite algorithm is implementing that algorithm on a Turing machine and then translating it in system F using the encoding given in the completeness proof (your own encoding may not work!).  Not exactly the most elegant solution in terms of programming...  Of course, in many cases the "natural" program $P$ does satisfy $\Phi$.  However, in many other cases it does not: in the LICS 1999 paper mentioned above, Hofmann gives insertion sort as an example.

Intentionally complete type systems, which are able to type exactly the polytime programs of the wider language (system F in my example above) do exist.  Of course, they are undecidable in general.  See

Ugo Dal Lago, Marco Gaboardi. Linear Dependent Types and Relative Completeness. Logical Methods in Computer Science 8(4), 2011.


Is it reasonable to allow the type of a λ/∀-bound variable to refer to itself?

I have not seen this in a dependently-typed setting, but a similar notion is fairly well-known in weaker systems (e.g. System F) with subtyping, under the term "F-bounded quantification". This pops up prominently in type systems for object-oriented programming languages, which typically are heavy on (equi-) type recursion. This notion was originally introduced by this paper.

A standard use case is expressing forms of "binary methods" that need to be covariant in their argument types. For example, in those languages you see interface types like

interface Ordered<T> { less(x : T) : Bool }

with subtypes like

class Int extends Ordered<Int> { ... }

and usage patterns

class Queue<T extends Ordered<T>> { ... }

or

sort<T extends Ordered<T>>(array : Array<T>) : Array<T>

and so on. In the more type-theoretical rendering of System F-sub with F-bounded quantification and records these could be expressed as

Ordered = λ(T <: Top). {less : T → Bool}
Int <: Ordered(Int)
Queue = λ(T <: Ordered(T)). {...}
sort : ∀(T <: Ordered(T)). Array(T) → Array(T)


What is the best upper bound on the running time of the graph minor algorithm?

My answer was based on the explanation in paper of Adler et al for disjoint paths problem. That running time is not exactly what is in the Robertson and Seymour paper but it is the improved one by Kawarabayashi and Wollan. It’s been a long time ago and I am not sure if this is restricted to specific graph class. You may have a look at the corresponding reference.

https://arxiv.org/pdf/1310.2378.pdf


Is the following optimization problem NP-hard?

The new version of the problem is indeed NP-hard.

Reduction from set cover: Subsets are $S_1, S_2, ..., S_m$ and the universe is $U = \{ a_1, a_2, ..., a_n \}$. Construct a node-weighted directed graph $(N,S,c)$ as follows:

Nodes are $N = \{ a_1, a_2, ..., a_n, S_1, S_2, ..., S_m, S'_1, S'_2, ..., S'_m \}$.
Edges are: $(a_j,S_i)$ iff $a_j \in S_i$, and $(S_i,S'_i)$ for all $i$.
Weights are: $w(a_j) = M$ for all $j$, and $w(S_i) = 1$ and $w(S'_i) = 0$ for all $i$.

Now if there is a set cover $X$ of size at most $k$, we can get the benefit of at least $nM + m - k$ as follows:

For each $a_j$ pick one set $S_i \in X$ in the cover with $a_j \in S_i$, and choose the edge $(a_j,S_i)$; we get the benefit of $M$ from $a_j$.
For each $S_i \notin X$ we choose the edge $(S_i, S'_i)$; we get the benefit of $1$ from $S_i$.

Conversely, if we can get the benefit of at least $nM + m - k$, then we have at most $k$ nodes in $\{S_1, S_2, ..., S_m\}$ and all of the nodes in $U$ must have outgoing edges; this gives a set cover of size at most $k$.


What is the origin of logical relations?

Plotkin used logical relations in his unpublished but nevertheless widely circulated and influential 1973 paper "Lambda Definability and Logical Relations". I have a copy of this note on my webpage.

I used to think that this is where the name came from, but when I asked Rick Statman about this, he told me that Mike Gordon coined the term logical relation to describe Tait's method, and that he and Gordon Plotkin picked it up from him. I think this is how it entered programming language jargon, though you could make sure by asking Plotkin.


Comparing two products of lists of integers?

(I understand the description of the problem so that the input numbers are bounded by a constant, so I will not track dependence on the bound.)
The problem is solvable in linear time and logarithmic space using sums of logarithms. In more detail, the algorithm is as follows:

Using binary counters, count the numbers of occurrences of each possible input number in both lists.

This takes time $O(n)$, and the counters use space $O(\log n)$, as each counter is bounded by $n$ in value.
Let $p_1,\dots,p_k$ be the primes below the $O(1)$ bound. By distributing each counter for a number $a$ to the prime factors of $a$ (with appropriate multiplicity), and subtracting the counts for one list from the other list, we obtain the following in time $O(\log n)$:

Compute integers $\beta_1,\dots,\beta_k$ with $O(\log n)$ bits such that the problem is equivalent to determining the sign of $\Lambda:=\sum_{i=1}^k\beta_i\log p_i$.

If $\beta_1=\dots=\beta_k=0$, answer that the products are equal.

Otherwise $\Lambda\ne0$. By Baker’s theorem, we can lower bound
$$|\Lambda|>2^{-C\log n}$$
for a certain constant $C$. Thus, the following correctly computes the sign of $\Lambda$:

Output the sign of $\sum_{i=1}^k\beta_i\pi_i$, where $\pi_i$ is an approximation of $\log p_i$ to $m:=C\log n+k+1$ bits of accuracy.

Let $M(m)$ be the cost of multiplication of two $m$-bit integers. The current best bound is $M(m)=O(m\,\log m\,2^{O(\log^* m)})$, but here it would not make much difference even if we use the trivial $O(m^2)$ multiplication algorithm. We can compute $\log p_i$ to $m$ bits of accuracy in time $O(M(m)\log m)$ using AGM iteration (see e.g. here), and then evaluating $\sum_i\beta_i\pi_i$ takes time $O(M(m))$. Overall, step 4 takes time $O(M(m)\log m)\subseteq O(\log n\,\mathrm{poly}(\log\log n))$.
Thus, the running time of the algorithm is dominated by $O(n)$ of the first step.


Is this problem mappable to 3SAT or is it weaker than 3SAT?

And one way of trying to solve such a problem is to do a form of backtracking, or what is also called "branch-and-bound". (Sorry, this was too long for a comment.)

Here's one possible heuristic:

(1) Choose some variable $x$ that is "most" constrained in some sense (maybe it occurs the most often). Suppose its integer range is $[L,R]$, and let $M$ be the midpoint of that interval. Now try to recursively solve the problem when $x < M$ is assumed, and separately when $x \geq M$.

(2) In each recursive call, relax the predicate to be a linear program (i.e., the solutions to the variables are over the rationals), and include all range constraints such as $x \geq L$ and $x \leq R$. Check if the resulting linear program is still feasible over the rationals. If it isn't feasible over the rationals, then it won't be feasible over the integers either, so you can stop and backtrack. If it is feasible over the rationals, continue with step (1).

Note: not all possible constraints (e.g. quadratic polynomials like $x(1-x) = 0$) can be neatly expressed as linear constraints; one possible "solution" to this is to simply leave those constraints out (or, replace these "hard" constraints with linear constraints that are consequences of the hard constraint being true... for example, $x(1-x)=0$ has the consequence that $x \geq 0$ and $x \leq 1$).

That's about as much detail as a CS theory site can give you ;)


Thanks for the question; I had similar questions few years ago, before starting in research (I'm not necessarily assuming that's your case).

I've looked at a couple of the links, and they don't really look like research papers in form; I mostly can't really tell if their technical content could be made into a paper because I'm not an expert in the field, but I'm guessing "no". If you compare your links to a paper, you'll notice several differences. But highlighting them and their rationale might help.

The key concepts are:

Scientists learn new knowledge for humankind, and then share what they learn through research papers.
Moreover, we live in information overload, so readers only have time for the most important knowledge.

As a consequence, research papers have some key features.

A research paper contributes new knowledge in a field (novelty). To convince readers of this new information, it provides appropriate evidence to argue for it. What's appropriate evidence varies depending on the field and on what the paper claims.
In fact, since a paper must be novel, it must also argue that its content is novel (though that's done somewhat implicitly). That's done by comparing to related works in the field; if another work looks similar to a submission, the author must explain what's the novelty in his work. Moreover, no paper is entirely novel, so a paper must also say what was already known by citing its invention (except for things that are standard). As a rule, technical articles don't do that; they typically don't claim to be novel. Sometimes the author invented the technique by himself, but it was already known.
Good call for papers mention the criteria for judging papers — this one mentions novelty, importance, evidence and clarity.
A good research paper should also contribute knowledge that is "interesting", and explain it clearly to the reader. What's interesting varies according to the publication venue.
In fact, my favorite intro to research in book form is The craft of research, though what I've read is parts of this condensed version. I'd recommend to start reading it from the Amazon preview.

Example

The above is not really specific to computer science, so let's have an example.
Since most of your examples are in algorithms, I'll try to show what the above means for an algorithm paper (even though I'm not an expert in that area, so I hope I won't get it too wrong). Such a paper might claim that some algorithm is fast, and prove that through complexity analysis or experiments. That paper better claim that the algorithm computes something useful (otherwise, who cares that it's fast?), often because it's correct; appropriate evidence is then a correctness proof. Moreover, this algorithm probably reuses ideas already known to experts (which should be cited), but has some key differences from any similar works (which should also be cited) — maybe it has the same complexity but is more general, or is simpler to implement, or has any other virtues that experts have agreed are interesting.

By contrast, a paper on, say, programming languages would have different claims and different evidence, but would still follow the same basic structure.


Partial soundness proofs for pragmatic static analyses

Program analysis is an inherently applied field, so for many practitioners, the final word on the utility of an analysis is how it performs in practice.

The approach you are suggesting would make explicit situations in which the analysis is sound. However, isolating these situations requires the analyst to know about the semantics of the programming language, the semantics of the static analyzer and further identify the gaps between the two. In my experience, several people  interested in designing a practical analysis find the overhead of studying semantics (and soundness) excessive, and people who focus on semantics and soundness tend not to investigate heuristics required to make the analysis work on large families of practical examples. This may explain the dearth of material.

That said, there are people who care about both practical utility and soundness, and even the specific problem you speak of (soundness with respect to points-to-analysis results). I think you will have more luck searching with the terms conditional soundness or relative soundness or parameterized soundness.

SAFECode: Enforcing Alias Analysis for Weakly Typed Languages, Dinakar Dhurjati, Sumant Kowshik, and Vikram Adve, PLDI 2006
Pointer Analysis, Conditional Soundness, and Proving the Absence of Errors, Christopher L. Conway, Dennis Dams, Kedar S. Namjoshi, Clark Barrett, SAS 2008
A posteriori soundness for non-deterministic abstract interpretations, Matthew Might and Panagiotis Manolios, VMCAI 2009.

The first two papers are directly related to your question, and the third is just a slightly different approach to soundness, which may interest you in this context.

The soundness/utility trade-off is an active concern for the problem of call graph construction. In the presence of reflection and dynamic class loading, call graph construction is a non-trivial problem and it is difficult to achieve sound and useful results.

  Papers citing Call graph construction in object-oriented languages as determined by Google Scholar.

A lot of those papers are not relevant for this discussion, but there are quite a few which contain relevant discussions, so I prefer to let you choose.


Data representation affecting problem complexity

Although not (yet) getting all the way down to $\mathsf{P}$, Group Isomorphism and other algebraic problems can depend heavily on the format of the input, in a way that is far more subtle than merely padding. For example, when the groups are given by multiplication tables, there is a trivial $n^{\log n + O(1)}$-time algorithm to test isomorphism. When the groups are given by generating sets (say, of permutations, or of matrices over finite fields), there are slightly sub-exponential algorithms, but the problems are at least as hard as Graph Isomorphism. When the groups are given by generators and relations, the problem is undecidable (indeed, when given by generators and relations, even telling if the group is trivial or not is undecidable, whereas this particular task is trivial in the other mentioned formats).

Another algebraic example is provided by Grobner bases. Most questions about ideals in polynomial rings become comparatively easy if you're given a Grobner basis for the ideal instead of an arbitrary generating set. But computing a Grobner basis is $\mathsf{EXPSPACE}$-complete. (This is perhaps not as good an example, since it is a property of the input, rather than a the format of the input that is affecting complexity here. But I thought I'd mention it anyways.)


Confusions about the technique for verifying implementations of linearizable objects in [Herlihy and Wing, 1990]

Herlihy and Wing write on p. 477:

  In conclusion, the rep invariant $\mathbf{I}$ must be continually satisfied and the abstraction function continually defined, not only between abstract operations, but also between rep operations implementing abstract operations. The abstraction function maps each rep value to a nonempty set of abstract values:
  $$
\mathbf{A}: \mathrm{REP} \to 2^{\mathrm{ABS}}
$$

I am tempted to read into this that even when an abstract operation is implemented by a sequence of multiple rep operations, the rep invariant has to hold after each of those rep operations, and when it holds, then the rep value must have at least one abstract counterpart.

Many people have addressed some of the challenges posed in this paper. One of the more interesting and recent developments is  R Jagadeesan and J Riely's Quantitative Quiescent Consistency [http://arxiv.org/abs/1402.4043].


Is multiprocessing possible on a Turing Machine?

This is a subtle question.

TMs are very much a sequential model of computation. So in some sense, TMs cannot (directly) model multiprocessing. However, TMs can do step-by-step simulations of the reductions a multiprocessor is carrying out. So TMs can do a sequential simulation of a parallel computation. Whether this a genuine model of parallel computation is debatable.

See also the discussion Applicability of Church-Turing thesis to interactive models of computation.


Is one definition of the word paradox, "something that can be used to prove the halting problem undecidable?"

It sounds like you are looking for a characterisation of the features required to capture diagonalization arguments.  Lawvere's Diagonal Arguments and Cartesian Closed Categories unified each of the main diagonal arguments back in 1969, including Cantor's and Rice's Theorems, the halting problem, and Gödel's first incompleteness theorem.

Yanofsky's 2003 tutorial discussion A Universal Approach to Self-referential Paradoxes, Incompleteness and Fixed Points provides a nice overview of Lawvere's ideas  (arXiv:0305282).

More recently, Samson Abramsky and Jonathan Zvesper have been taking this further (arXiv:1006.0992).


You can multiply $r$ by $(1+2^{-k})$ by adding $r$ to $r$ shifted right by $k$ positions. To find the factors of a number $s$, you can start setting $r:=1$ and for $k=0,1,2,\ldots$, test if $r(1+2^{-k})\leq s$. If the test succeeds, set $r:=r(1+2^{-k})$. Along the way you can calculate $\log s$ by summing $\log 1+2^{-k}$ for every factor found.


Sorting algorithm, such that each element is compared $O(\log n)$ times, and doesn't depend on a sorting network

Upon discussing this with Michael T. Goodrich, it seems that the parallel sorting algorithm by Cole for EREW PRAM does the job. See

Richard Cole: "Parallel Merge Sort". SIAM J. Comput. 17(4): 770-785 (1988).

In that algorithm there are $O(\log n)$ rounds and in each round each element participates in $O(1)$ comparisons. (One has to understand the algorithm to see that we do not abuse of making copies of each element.)

An extension of that algorithm for parallel pointer machine is given in

M.T. Goodrich, S.R. Kosaraju: "Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation". J. ACM 43(2): 331-361 (1996).


Why is there an enormous difference between SAT solvers?

Yes, there is a major difference between MiniSAT and WalkSAT. First, let's clarify - MiniSAT is a specific implementation of the generic class of DPLL/CDCL algorithms which use backtracking and clause learning, whereas WalkSAT is the general name for an algorithm which alternates between greedy steps and random steps.

In general DPLL/CDCL is much faster on structured SAT instances while WalkSAT is faster on random k-SAT. Industrial and applied SAT instances tend to have a lot of structure, so DPLL/CDCL is dominant in most modern SAT solvers. Instance to instance one technique may win out, though, which is one reason why portfolio solvers have become popular.

I take a lot of issue with your claim that WalkSAT is much faster than MiniSAT on the instances on that page. For one thing, there are gigabytes of SAT instances there - how many did you try comparing them on? WalkSAT is not at all competitive on most structured instances which is why it's not often seen in competitions.

On a side note - Vijay is right that MiniSAT is still relevant. Actually, because it's open source and well-written, MiniSAT is the solver to beat in order to show that a given optimization has promise. Many people tweak MiniSAT itself to showcase their optimizations - take a look at the "MiniSAT hack" category in the recent SAT competitions.


What is computational complexity of calculating the Variance-Covariance Matrix?

Your conjecture is correct.

If $X\in \mathbb{R}^{N \times n}$ with $N$ as number of datapoints and $n$ being the number of features, then you can obtain the covariance matrix by $X^TX$ (apart from the mean subtraction which can be ignored from a complexity perspective).

Thus, covariance matrix computation is matrix multiplication which is naively indeed in $\mathcal{O}(Nn²)$ see here, since you have to do roughly $2N$ operations to fill every of the $n²$ positions in your covariance matrix $X$. In practice, matrix multiplication is speeded up to $\mathcal{O}(n^{2.73})$ for quadratic matrices (see the link).


The analogue of the $\mathsf{NC}$ hierarchy for algebraic circuits is known to collapse to the second level. That is, algebraic circuits of size $n^{O(1)}$ computing a polynomial of degree $n^{O(1)}$ can be rebalanced to have depth $O(\log^2 n)$ while only increasing the size by a polynomial factor. This is due to Valiant, Skyum, Berkowitz, and Rackoff. It is open whether $\mathsf{NC}^1 \stackrel{?}{=} \mathsf{NC}^2$ in this setting, but I believe the popular opinion is that $\mathsf{NC}^1 \neq \mathsf{NC}^2$ here.
If one further restricts to syntactically multilinear algebraic circuits, then we in fact know $\mathsf{NC}^0 \subsetneq \mathsf{NC}^1 \subsetneq \mathsf{NC}^2 = \mathsf{NC}$ unconditionally. The fact that $\mathsf{NC}^1 \subsetneq \mathsf{NC}^2$ is due to Raz, and the fact that $\mathsf{NC}^2 = \mathsf{NC}$ is due to Raz and Yehudayoff.
Raz, Ran, Separation of multilinear circuit and formula size, Theory Comput. 2, Paper No. 6, 121-135 (2006). ZBL1213.68301.
Raz, Ran; Yehudayoff, Amir, Balancing syntactically multilinear arithmetic circuits, Comput. Complexity 17, No. 4, 515-535 (2008). ZBL1188.68367.
Valiant, L. G.; Skyum, S.; Berkowitz, S.; Rackoff, C., Fast parallel computation of polynomials using few processors, SIAM J. Comput. 12, 641-644 (1983). ZBL0524.68028.


This is very unlikely to hold, but (as usual) impossible to rule out using current techniques, as we can’t even prove $\mathit{PSPACE}\ne P$.

However, we can at least show that no relativizing argument proves such an inclusion, i.e., there are oracles $X$ such that randomized polynomial-time with a $(\Sigma^P_{(\log n)^c})^X$ oracle does not include $\#P^X$. Better yet, there are oracles where it does not even include $\oplus P^X$ (which is included in $P^{\#P^X}$): otherwise, there would exist $O((\log\log n)^c)$-depth quasipolynomial-size unbounded fan-in circuits that approximate parity with error, say, $1/4$, contradicting Håstad’s theorem.


Distributing a binary relation into bins such that each element is in a small number of bins

This is not an answer.  It is just the somewhat trivial observation that WLOG you can relax the requirement that there be exactly $p$ edge subsets $\{E_i\}_i$ of exactly the same size, and instead just look for any number of edge subsets of of size $O(\textsf{the desired size})$.  Maybe this helps think about the problem.

Fix any graph $G=(V,E)$ and integer $p\ge 1$.  Let $s=\lceil |E|/p\rceil$

Lemma. Suppose there are subgraphs $\{G'_j=(V'_j,E'_j)\}_j$ such that $\{E'_j\}_j$ partitions $E$ into (any number of) parts of size $O(s)$.
Let $$M = \max_{v\in V} |\{j : v\in V'_j\}|$$
be the maximum number of parts that any vertex is in.

Then there are $p$ subgraphs $\{G_i=(V_i,E_i)\}_i$ such that $\{E_i\}_i$ partitions $E$ into exactly $p$ parts each of size at most
$s=\lceil |E|/p\rceil$, and
$$\max_{v\in V} |\{i : v\in V_i\}| = O(M).$$

Proof.  Starting with the sequence $E'_1, E'_2, \ldots, E'_{p'}$, replace each part $E'_j$ in the sequence by any ordered sequence of the edges contained in that part.  Let $e_1, e_2, \ldots, e_m$ be the resulting sequence (a permutation of $E$ such that each part $E'_j$ is some "interval" $\{e_a, e_{a+1}, \ldots, e_b\}$ of edges in the sequence).  Now partition this sequence into $p$ contiguous subsequences such that each except the last has size $s$, and let $E_i$ contain the edges in the $i$th contiguous subsequence.  (So $E_i = \{e_{i\,s+1}, e_{i\,s+1}, \ldots, e_{(i+1)s}\}$ for $i<p$.)

By assumption each part $E'_j$ has size $O(s)$, and by design each part $E_j$ except the last part $E_p$ has size $s$, so (because of the way $\{E_i\}_i$ is defined) the edges in any given part $E'_j$ are split across $O(1)$ parts in $\{E_i\}_i$.  This, and the assumption that each vertex occurs in at most $M$ of the parts in $\{E'_j\}_j$, imply that each vertex occurs in at most $O(M)$ of the parts in $\{E_i\}_i$.  QED


Polynomial-time algorithms with huge exponent/constant

Here are two screenshots from An Energy-Driven Approach to Linkage Unfolding by Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben,  James F. O’Brien, SOCG 2004:


Typechecking liveness properties of coprograms

To expand on pedagand's answer: productivity is the term used for the computational dual (in some precise sense) of termination. Formally, a program f : CoData is productive if running the computation f eventually produces a constructor of CoData, and every (recursive) sub-term of that constructor is also productive.

For example

primes = filterBy prime [0..]

in haskell is productive, since there is an infinite number of prime numbers and so computing primes will always eventually produce a cons constructor.

There has been a number of works on using types to check for productivity of a given definition. One nice overview is Abel, Iteration and Coiteration Schemes for Higher-Order and Nested Datatypes from 2005.


What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?

I think that what you want to know about is quantum analogs of classes of function problems.  (Thanks to Peter Shor for pointing out this concise description in a comment.)

An abstract process which takes a quantum state of fixed size as the input and produces a quantum state of fixed size as the output is called a quantum channel.  In your situation, we do not want to fix the input size or the output size, and therefore we naturally consider a family of quantum channels as the quantum analog of functions from classical strings to classical strings.

It is clearly possible to define the class of families of quantum channels which can be implemented/approximated by families of efficient quantum circuits (with suitable notions of efficiency, uniformity, and approximation).  I do not know if this class has any standard name (but see Peter Shor’s comment for a suggestion).

In my speculation, classes of quantum channels are not often studied because one of the reason to consider complexity classes is in order to compare the powers of different computational models, and classes of quantum channels cannot be used to compare classical and quantum computational models.  However, it is perfectly fine to define and talk about such classes if anything interesting can be proved about them.


Terminology for types of universal computation

The key words you should search for are "naming systems", "representation", "notation", "numbering", ...

The usual concepts of computability are defined over strings (either unary which is usually stated as $\mathbb{N}$ or binary which is state as computability over $\Sigma^*$ where $\Sigma = \{ 0,1 \} $). (They can be extended to $\Sigma^\omega$ but here I will stick to the countable case.) A model of computation is called universal if it is Turing-complete (i.e. it can compute any Turing computable function).

If we want to talk about computability over other sets, then we need a naming system. A naming system for $M$ is a partial function from $\Sigma^*$ onto $M$. If we have two sets $Y$ and $M$, and a naming system for each of them, then we can talk about computability of functions from $Y$ to $M$.

One can define a partial order over naming systems of a set $M$. $\gamma \leq \gamma'$ iff some computable function can translate $\gamma$-names of objects in $M$ to $\gamma'$-names of them.

Let me give a simple example. Assume that $M$ is the set of Turing machines, and $\gamma$ is one of the common ways of encoding Turing machines as explained in computability/complexity books. Let $\gamma'$ be defined by adding a bit to the names telling if the corresponding TM halts. Then $\gamma'$-names can be translated to $\gamma$-names by a computable function but not vice versa. $\gamma'$-names contain more information. If fact, we we can solve the halting problem for Turing machines if we use $\gamma'$ as our encoding.

Obviously we don't want to have non-computable information coded inside the names of objects as above, so we use names which have the least amount of information in computability (assuming that they exist). (In complexity, the complexity of a problem can depend on the naming system that is used for the inputs, and different naming systems can be more suitable for different purposes. There is no least if we change the requirement for translation from being computable to say poly-time computable as is shown by padding arguments.)

After defining the computability over other sets using naming systems, one can talk about a universal model of computation over them w.r.t. fixed naming systems.

Now, if the names in a naming system contain non-trivial information, then it is not very interesting for a machine to be universal w.r.t. that naming system anymore.

For further information:

Yuri L. Ershov, Sergei S. Goncharov, Anil Nerode, "Handbook of Recursive Mathematics", vol I and II, 1998
Klaus Weihrauch, "Computable Analysis", 2000


Alon, Matias, and Szegedy proved that finding the frequency of the most frequent of $n$ items requires $\Omega(n)$ space in the worst case in the streaming model, even if you allow a constant number of passes over the input. Since finding the most frequent item gives you a two-pass algorithm for computing its frequency (find in the first pass, track its frequency in the second), we cannot find the most frequent item in sublinear space in the streaming model.

Usually the way to deal with such a lower bound is to relax the problem. The algorithms Massimo mentions are for the most popular relaxation: the $k$-Heavy Hitters problem ($k$-HH). The $k$-HH problem asks to output all items whose frequency is at least $\frac{m}{k}$, where $m$ is the total frequency of all items (i.e. the length of the stream, in the simplest streaming model). So in $k$-HH we ´expect to see an item only if it actually is very frequent. This problem requires linear space to solve exactly as well: i.e. an algorithm which outputs all and only the items of frequency $\geq \frac{m}{k}$ requires $\Omega(n)$ space in the worst case. For this reason, the problem is usually relaxed a little further: we expect a $k$-HH algorithm to output all items of frequency at least $\frac{m}{k}$ and no items of frequency less than $\frac{(1-\varepsilon)m}{k}$. All algorithms Massimo lists actually do that.

Cormode and Hadjieleftheriou gave a very nice overview of the known $k$-HH algorithms, with brief descriptions, space complexity, and experimental results for performance.


The number of clauses in an unsatisfiable CNF

For arbitrarily large number $n$ of variables, the following CNF formula $\phi$ is not satisfiable, has only three clauses, and a $2K_2$-free clause-variable incidence graph:
$C_1=(x_1)$, $C_2=(\neg x_1)$, $C_3=(x_1,\ldots,x_n)$.
Thus, to get more interesting lower bounds one needs to make assumption about the minimum clause size or about the size of classes of clauses that contain the same variables (i.e. that have identical neighborhoods in the clause-variable incidence graph).
Observe that when the minimum clause size is $k$, then the example above can be adapted to give formulas with $2^k+1$ clauses and arbitrarily large number of variables $n$ that are not satisfiable. Moreover, when the number of clauses is $m<2^k+1$, then the formula is satisfiable even for arbitrarily large $n>k$: Let $C_m$ be the clause that has is incident with the largest set of variables. Since $n>k$, there is a variable $y$ that is not contained in the variable set of $C_1$, the clause with the smallest set of incident variables. Now, as for $k$-CNF formulas, the clauses $C_1,\ldots,C_{m-1}$ can be satisfied via an assignment of the first $k$ variables (which they all contain) and $C_m$ can be satisfied via the appropriate assignment of $y$.


Complexity of type inference in the simply typed lambda calculus

Type inference for simply typed lambda calculus is complete for polynomial time, as elegantly explained in section 1 of Harry Mairson's Linear lambda calculus and PTIME-completeness.
To be a bit more precise, here "type inference" is taken to mean the problem of computing the principal simple type of an untyped lambda term. This is strictly speaking a functional problem ("Given a term $t$, compute its principal type"), but Mairson shows that the corresponding decision problem ("Given a term $t$ and type $A$, is $A$ the principal type of $t$?") is PTIME-hard, by reduction from the circuit value problem.  This implies PTIME-completeness, since simple type inference can be performed efficiently using first-order unification.  Moreover, Mairson's encoding of the circuit value problem has the property that the terms representing boolean circuits are affine (variables used at most once), and in Section 2 of the paper he gives another encoding that produces linear terms (variables used exactly once).  So his proof implies PTIME-completeness of simple type inference even when restricted to affine/linear lambda terms.


In the classic PAC learning (i.e., classification) model, rare instances are not a problem. This is because the learner's test points are assumed to come from the same distribution as the training data. Thus, if a region of space is so sparse as to be poorly represented in the training sample, its probability of appearing during the test phase is low.

You'll need a different learning model, which explicitly looks at type-I and type-II errors, or perhaps some combined precision-recall score. Here again, I don't think there are any results indicating that a specific class of algorithms is particularly poorly suited for this task, but I could be wrong.

The closest I can think of is sensitivity to outliers --- AdaBoost is known to have this property, for example.


How does the CHC Algorithm deal with child populations with lower fitness?

CHC never has a next generation's population with lower fitness than the current one due to the use of a truncation selection step. It combines the parents and offspring, sorts by fitness, and takes the best $n$ individuals. So if including any child would lower the fitness of the population, it would just select the parents as the next generation and the average fitness would stay the same.

In principle, you could indefinitely select the same two parents over and over, continually producing inferior offspring. But generally you're running CHC with a population size of 50 or more, so you don't expect to continually pair the same two parents. Also, it's technically an infinite loop anyway, as most GAs are. In practice you define some stopping condition based on evaluation count or wall clock time or whatever.


Finding the smallest DFA that separates two words without using brute force search?

If I had to do this in practice, I would use a SAT solver.

The question of whether there is a DFA with $k$ states that accepts $x$ and rejects $y$ can be easily expressed as a SAT instance.  For instance, one way is to have $2k^2$ boolean variables: $z_{s,b,t}$ is true if the DFA transitions from state $s$ to state $t$ on input bit $b$.  Then add some clauses to enforce that this is a DFA, and some variables and clauses to enforce that it accepts $x$ and rejects $y$.

Now use binary search on $k$ to find the smallest $k$ such that a DFA of this sort exists.  Based on what I've read in papers on related problem, I would expect that this might be reasonably effective in practice.

Other encodings of this as SAT are possible.  For instance, we can use a trace encoding:

If $x$ is of length $m$, you could add $m\lg k$ boolean variables: let $s_0,s_1,\dots,s_m$ be the sequence of states traversed on input $x$, and represent each $s_i$ using $\lceil \lg k \rceil$ boolean variables.
Now for each $i,j$ such that $x_i=x_j$, you have the constraint that $s_{i-1}=s_{j-1} \implies s_i=s_j$.
Next, extend this to handle $y$: let $t_0,\dots,t_n$ be the sequence of states traversed on input $y$, and represent each $t_j$ using $\lg k$ boolean variables.  For each $i,j$ such that $y_i=y_j$, add the constraint that $t_{i-1}=t_{j-1} \implies t_i=t_j$.
Similarly, for each $i,j$ such that $x_i=y_j$, add the constraint that $s_{i-1}=t_{j-1} \implies s_i=t_j$.
Both traces must start from the same starting point, so add the requirement that $s_0=t_0$ (WLOG you can require $s_0=t_0=0$).
To ensure that the DFA uses only $k$ states, require that $0 \le s_i < k$ and $0 \le t_j <k$ for all $i,j$.
Finally, to encode the requirement that $x$ is accepted and $y$ is rejected, require that $s_m \ne t_n$.

All of these requirements can be encoded as SAT clauses.

As before, you'd use binary search on $k$ to find the smallest $k$ for which such a DFA exists.


Approximation Ratio of Local search for $k-$center problem

Local search (with a single swap) doesn't give you a good approximation factor in the worst case for $k$-center, as illustrated by the following example.

Take a simplex in $\mathbb{R}^{k-1}$, and put $k$ points at each of the $k$ vertices, for a total of $k^2$ points.

Note that between each pair of vertices of the simplex the distance is 1.  The optimal solution takes one point from each vertex, obtaining cost zero.  And that's the only way to obtain cost zero.. any other type of solution has cost 1.

So if you start local search with $C$ being any solution that is more than one swap away from such an optimal solution, no local improvement (in one step) is possible.  For example, start local search with $C$ containing all $k$ of the points at a single vertex.  That solution has cost 1, and no single swap (or even $k-2$ swaps) can reduce the cost below 1.


When are all facets rank facets? (for independence system polyhedra)

On (1): The case of stable sets in graphs may clarify the situation (a stable set of a graph is a set of pairwise non-adjacent vertices). For each graph $G$, let $\mathcal{S}(G)$ be the set of stable sets of $G$.

The graphs $G$ for which the non-trivial facets of $P(V(G),\mathcal{S}(G))$ (i.e the stable polytope) are all rank-facets are called rank-perfect graphs (see Wagler). They include line graphs (by Edmonds' matching polytope theorem), perfect graphs, series-parallel graphs and more. Wheels with an even number of at least 6 vertices provide a basic example of non-rank-perfection.

To my knowledge, no characterization of rank-perfect graphs is known, and the problem of their recognition may be difficult. Pêcher and Wagler have several partial results on rank-perfect webs. By contrast, Wagler showed that the complements of webs are all rank-perfect.

On (2): the answer is negative as shows the following example. Let $G$ be the claw (i.e the complete bipartite graph $K_{1,3}$). It is well-known that since $G$ is bipartite, the non-trivial facets of $P(V(G),\mathcal{S}(G))$ are the edge-inequalities and hence are rank-facets.

Now, suppose by contradiction that $\mathcal{S}(G)$ is the set of common independent sets of two matroids. Using the weak circuit axiom of matroids in each matroid (that is, for each distinct circuits $C_1$ and $C_2$ of a matroid $M$ and each $e\in C_1\cap C_2$, there is a circuit in $(C_1\cup C_2)-e$), it is straightforward to check that a clique of size 2 must belong to $\mathcal{S}(G)$: a contradiction.

The same argument shows an example with more vertices but no claw: the circuit with 5 vertices.


Is the basis of parity functions the only orthonormal basis for Boolean functions?

I don't think parities are the only orthonormal Boolean basis, for example Paley basis provides a Boolean orthonormal basis in some cases. It's natural to ask if such bases, interpreted as Boolean functions, have any interesting applications.


Divesh Aggarwal and Noah Stephens-Davidowitz very recently posted a preprint improving the constant in the upper bound of Banaszczyk's theorem: https://arxiv.org/abs/1907.09020. Specifically, they show that $\lambda_1(\Lambda)\mu(\Lambda^*) \leq (0.1275 + o(1)) n$, which combined with the upper bound $\lambda_n(\Lambda^*) \leq 2 \mu(\Lambda^*)$ implies that $\lambda_1(\Lambda)\lambda_n(\Lambda^*) \leq (2 \cdot 0.1275 + o(1)) n$. (Here $\mu$ denotes the covering radius of a lattice.)

Note that you state the upper bound with constant 1 (as is commonly done for convenience), whereas Banaszczyk's original work already shows that the bound holds with the improved constant $1/\pi$. In other words, the bound that you state is already off by a factor larger than 2.

Oded Regev's lecture notes also give a self-contained proof without worrying about getting the best possible constant. (It seems that you're likely already aware of these notes.)


As Venkat told in comments, it seems hard to understand your definition for oracle which aren't defined as some machine characterisation.

Let $A^{(B^C)}$ would be the set of TM in $A$ with an oracle which is a machine in ($B$ with an oracle in a machine in $C$). It is obvious that a machine in $A$ can call $C$: it just calls the machine in $B$ and asks it to carry the message directly to $C$.

I guess ${(A^B)}^C$ would be a machine in $A$ that can call an oracle in $C$ or an oracle which is (a machine in $B$ that can call a machine in $C$) so it's exactly the same definition.

Finally, you may want $A^{B,C}$, which is certainly different from the other two (just take $B=C=NP$ and $A=P$, then $A^{B,C}=NP\cup coNP$ whereas $A^{(B^C)}=\Sigma_2^P\cup\Pi_2^p$.


Comparing Two Algorithms for 3SUM problem over Integers

The first paper essentially gives a subquadratic algorithm if we know that every input number has $w$ bits and we can add two $w$ bit numbers in one step. This was not a very surprising result and it did not rule out an $\Omega(n^2)$ bound.

The second paper does not use any such assumptions and improves the exponent of $n$ for decision trees, which is a surprise, although not as big as it would be for all algorithms, for which they have only improved slightly (thus disproving the strongest conjecture). I would guess that more results will follow shortly.


Giving a finite collection of infinite words "complex" enough with respect to automata measure

It is possible. Consider all languages $L_1,\dots,L_m$ recognizable by automata with at most $n$ states.

Now to each $x=x_1\dots x_m\in\{0,1\}^m$ we associate a (possibly empty) language $$L_x=\bigcap_{1\leq i\leq m} L_i^{x_i},$$ where $L^0$ is the complement of $L$ and $L^1=L$.

Let $Y=\{x\in\{0,1\}^m~|~ L_x\neq\emptyset\}$.
For each $x\in Y$, we choose $\xi_x\in L_x$. This gives a finite family $\{\xi_x~|~x\in Y\}$, we show that this family satisfies the wanted property.

Take any $\eta\in X^{\mathbb N}$, and for each $i\leq m$ let $y_i$ be defined as $0$ if $\eta\notin L_i$ and $1$ if $\eta\in L_i$.
We have $y=y_1y_2\dots y_m\in Y$, since nonemptiness of $L_y$ is witnessed by $\eta$. We show that $\xi_{y}$ satisfies the condition. Indeed, for any $L$ recognized by an automaton with at most $n$ states, $L$ does not separate $\eta$ from $\xi_y$, by definition of $\xi_y$.

Notice that this family is optimal in size, since if some signature $x\in Y$ is not represented by some $\xi_x$, the property fails. Its size is at most doubly exponential in $n$.


Formalization of proofs and computational complexity paradox?

$\def\mc{M_\mathit{const}}\def\mp{M_\mathit{paradox}}$Let me for the record write up the answer to Q1, so that it doesn’t live only in the comments.

The reasoning given in steps 1–5 in the question is correct in the real world. Thus, $\mc(\mp)$ outputs NO, and $\mp(x)$ halts in constant time, but there is no short enough proof of this in ZFC.

When trying to formalize this argument in ZFC, the problematic step is 2: here, we need to assert, in ZFC itself, the implication

  (1) If ZFC proves ‘$\mp$ halts in constant time’ by a proof of length $\le|\mp|^2$, then $\mp$ halts in constant time.

In general, statements of the form

  (2) If ZFC proves $\phi$, then $\phi$.

are known as instances of the reflection principle for ZFC, and by Löb’s theorem (a generalization of Gödel’s 2nd incompleteness theorem) they are never provable in ZFC itself, except for the trivial case when ZFC already proves $\phi$. Notice that the consistency statement for ZFC is a special case of the reflection principle, for $\phi=\bot$; in general, reflection principles are strictly stronger than consistency.

In our case, $\phi$ is the $\Sigma^0_2$ formula “$\mp$ halts in constant time”, so step 2 apparently makes an appeal to the $\Sigma^0_2$-reflection principle for ZFC, unprovable in ZFC.

However, we have to our disposal an extra restriction that we ignored so far, namely that we have a bound $\le|\mp|^2$ on the length of the purported ZFC-proof of $\phi$. Crucially, at this point, $\mp$ is a fixed explicit Turing machine, hence this bound is a standard integer constant (and likewise, $\phi$ is a fixed sentence). Thus, (1) is actually an instance of the finitistic reflection principle

  (3) If $\phi$ has a ZFC-proof of length $\le s$, then $\phi$.

This is actually provable in ZFC: if $\phi$ does, indeed, have a ZFC-proof of length $\le s$, then we can just take it, and derive (3) by ignoring the premise; if not, then for each string $|w|\le s$, we can “by inspection” produce a ZFC-proof that ‘$w$ is not a ZFC-proof of $\phi$’, and concatenating all these together, we obtain a proof of (3) (specifically, a proof of negation of its premise).

This brute-force proof will have length exponential in $s$, i.e., in our case, $2^{O(|\mp|^2)}$. There are in fact proofs of (3) of length polynomial in $s$ and $|\phi|$: this was proved by Pudlák [1] using efficient partial truth predicates. The improvements in [2] are only stated for consistency statements, but I believe they apply to more general reflection principles as well. Thus, there are ZFC-proofs of (1) of length $O(|\mp|^2)$.

However, this is still not enough to get a contradiction, as it seems any reasonable proof of (3) needs length more than $s$ (though the lower bounds in [1,2] are not quite that strong). Thus, ZFC-proofs of (1) will need length more than $|\mp|^2$. This cannot be fixed by raising the bounds in $\mc$ or by padding $\mp$, as these will just raise the length parameter $s$ in the same way. Thus, there is no paradox.

So, to summarize: ZFC proves that $\mc(\mp)$ outputs NO and that $\mp(x)$ halts in constant time, but the proofs are a little too long.

It is also worth mentioning that nothing in these arguments depends on ZFC specifically. The same reasoning will work for many other theories, for example Peano arithmetic. (Basically, we need a sequential theory axiomatized by finitely many axioms or nice schemata, see Pudlák’s papers for details.)

[1] Pavel Pudlák, On the length of proofs of finitistic consistency statements in first order theories, in: Logic Colloquium ’84 (Paris, Wilkie, Wilmers, eds.), Studies in Logic and the Foundations of Mathematics vol. 120, 1986, pp. 165–196, doi: 10.1016/S0049-237X(08)70462-2.

[2] Pavel Pudlák, Improved bounds to the length of proofs of finitistic consistency statements, in: Logic and Combinatorics (Simpson, ed.), Contemporary Mathematics vol. 65, American Mathematical Society, 1987, pp. 309–331, doi: 10.1090/conm/065.


Size bound on Büchi automaton for complement

Once you have the bound $2^{2n^2}$ on the number of classes, you can note that each state in the complement automaton corresponds to an $\omega$-regular language of the form $L_{f}L_{g}^\omega$, with $L_f$ and $L_g$ being functions from $Q$ to $2^Q\times 2^Q$.

Each such language is determined by $L_f$ and $L_g$, and there are $2^{2n^2}$ options for these functions, so you get a total of $(2^{2n^2})^2=2^{4n^2}$ options.

UPDATE FOLLOWING COMMENT:
The correspondence of the number $2^{4n^2}$ to the states of the constructed automaton is not exact. Observe that for every language $L_f$, we can construct a nondeterministic NFA $A_f$ (as is done in Theorem 1 in the Wikipedia link you posted). Moreover, the size of $A_f$ is polynomial in the size of the original NBW $A$. Thus, the size of an NBW for $L_fL_g^\omega$ is polynomial. You then take a union of $2^{4n^2}$ such automata, and obtain the complement NBW, so the size of the complement NBW is:
$$2^{4n^2}\cdot poly(n)=2^{4n^2 +\log poly(n)}=2^{O(4n^2)}$$
So it's a little less tight than $O(2^{4n^2})$, but it's still only singly exponential (perhaps there is a tighter analysis, but I'm not aware of one).


Extended Church's thesis and internal parametricity

Internal parametricity does not entail any version of extended Church's thesis. To see this, consider a presheaf model of internal parametricity, for example this one, and observe that in any presheaf model of type theory the extended Church's thesis fails (both the internal and the external one) because the object $\mathbb{N}^\mathbb{N}$ has uncountably many global points.


A lottery that you can be convinced that it is fair

If I am understanding the problem correctly, it would seem to amount to public flipping a $k$-sided coin. There seem to be lots of ways to do this if you assume bit commitment. One example would be having each party generate a random integer between 0 and $k-1$, using bit commitment to publicly commit to that bit string. Then once each agent has committed, they all publicly reveal their secret integer. The winning agent is then the one indexed by the sum of the integers modulo $k$. If even one agent is honest, then the flip must be random.

Of course one problem with this is that it requires bit commitment. Information theoretic schemes for bit commitment are impossible for both classical and quantum computing (though Adrian Kent recently proposed a scheme exploiting relativity). However, secure bit commitment can be achieved with computational assumptions.


Complexity of Model Enumeration in function free, equality free, First Order Logic with only Unary Predicates?

Reading the discussion below the other answer made me realize that it’s not immediately obvious what is the complexity of translation of FO sentences in this language to equivalent FO1 sentences. While the quoted fact that satisfiability of these sentences is NEXP-complete (whereas satisfiability of FO1 sentences is in NP) implies that any such translation has an at least exponential blow-up, common methods establishing the collapse of FO to FO1 only give a doubly exponential upper bound: any sentence is equivalent to a boolean combination of sentences of the form $\exists x\,\bigl(\bigwedge_{i\in I}P_i(x)\land\bigwedge_{j\in J}\neg P_j(x)\bigr)$; there are $2^n$ such existential sentences, hence their boolean combinations may have size $\approx2^{2^n}$.
So, let me show that one can perform the translation in time $2^{O(n)}$ after all. I will work more generally with any FO language without equality using at most unary symbols (relations and functions, including constants).
Given an FO sentence $\phi$, we first rewrite it so that no variable is quantified more than once, and then we construct an equivalent FO1 sentence $\phi^*$ by induction on the complexity of $\phi$:

If $\phi$ is quantifier-free, $\phi^*=\phi$.

If $\phi$ is a boolean combination of $\phi_0,\dots,\phi_{n-1}$, we make $\phi^*$ the corresponding boolean combination of $\phi_0^*,\dots,\phi_{n-1}^*$.

If $\phi=\exists x\,\psi(x)$, let $A_x$ be the set of all atomic subformulas of $\psi$ that contain $x$ (and therefore no other variable). For each $I\subseteq A_x$, let $\psi_I$ denote the sentence obtained from $\psi(x)$ by replacing all occurrences of $\alpha\in I$ with $\top$, and all occurrences of $\alpha\in A_x\smallsetminus I$ with $\bot$. Then we define
$$\phi^*=\bigvee_{I\subseteq A_x}\Bigl[(\psi_I)^*\land\exists x\,\Bigl(\bigwedge_{\alpha\in I}\alpha(x)\land\bigwedge_{\alpha\in A_x\smallsetminus I}\neg\alpha(x)\Bigr)\Bigr].$$

The soundness of this translation follows from the tautologies
$$\bigwedge_{\alpha\in I}\alpha(x)\land\bigwedge_{\alpha\in A_x\smallsetminus I}\neg\alpha(x)\to(\psi(x)\leftrightarrow\psi_I).$$
Let $n=|\phi|$. Since we expanded each quantifier to a disjunction of $2^n$ formulas, the size of the formula is roughly multiplied by $2^n$ for each quantifier, giving a total size about $2^{n^2}$. But counting more precisely, the expansion of $\exists x$ multiplied the size by $2^{|A_x|}$; since each element of $A_x$ is an atomic subformula of the original formula, and distinct quantifiers correspond to disjoint sets $A_x$ by our assumption on quantified variables, the overall multiplicative factor is only $2^{\sum_x|A_x|}\le2^n$, thus $|\phi^*|=2^{O(n)}$, and it is easy to see that it is computable in time polynomial in $|\phi^*|$.
One can also show using a similar argument that given an FO sentence with equality in a language with unary predicates and constants, we can compute in time $2^{O(n)}$ an equivalent sentence that is a boolean combination of sentences of the form $\exists^{\ge k}x\,\theta(x)$, where $\theta$ is a conjunction of atomic and negated atomic formulas, and $k\le n$.

Concerning the model enumeration problem: I assume the problem is, given a sentence $\phi$ and a number $n$ in unary, count the number of models of $\phi$ with domain $[n]$, but it is not clear to me if you want $\phi$ to be fixed, or to be part of the input.
If $\phi$ is part of the input, the problem is in PSPACE (more precisely, FPSPACE) by the brute force enumeration algorithm (this works for arbitrary FO languages). Conversely, it is PSPACE-hard even if $n=2$ is fixed, and the language consists of a single unary predicate: indeed, a QBF
$$Q_0p_0\,Q_1p_1\,\dots\,Q_mp_m\,\theta(p_0,\dots,p_m)$$
is true iff the sentence
$$\exists x\,P(x)\land\exists x\,\neg P(x)\land Q_0x_0\,Q_1x_1\,\dots\,Q_mx_m\,\theta(P(x_0),\dots,P(x_m))$$
has a model (of size $2$).
If $\phi$ is fixed, the enumeration problem is solvable in polynomial time, and even in $\mathrm{TC}^0$: in fact, the number of models of size $n$ is
$$\sum_{i=0}^Kc_ii^n$$
for some integer constants $K$ and $c_0,\dots,c_K$ determined by $\phi$. To see this, a model with $k$ unary predicates on domain $[n]$ can be identified with a mapping $M\colon[n]\to[2^k]$, assigning to each element the bitstring stating which unary predicates it satisfies. The truth of a sentence $\exists x\,\bigl(\bigwedge_{i\in I}P_i(x)\land\bigwedge_{i\notin I}\neg P_i(x)\bigr)$ in $M$ is then determined by the presence of the corresponding bitstring in $\mathrm{Im}(M)$. Thus, there is a set $T_\phi\subseteq\mathcal P([2^k])$ such that
$$M\models\phi\iff\mathrm{Im}(M)\in T_\phi,$$
and the number of models of $\phi$ of size $n$ is
$$\sum_{E\in T_\phi}\bigl|\{M\colon[n]\to E\mid M\text{ is onto}\}\bigr|
=\sum_{E\in T_\phi}|E|!\,S(n,|E|)
=\sum_{E\in T_\phi}\sum_{i=0}^{|E|}\binom{|E|}i(-1)^{|E|-i}i^n$$
where $S(n,k)$ are Stirling numbers of the second kind.


Complexity of validity problem for Monadic First Order Logic?

According to:

Leo Bachmair, Harald Ganzinger, Uwe Waldmann: Set Constraints are the Monadic Class. LICS 1993: 75-83

the problem of checking if a formula of the Monadic Predicate Calculus is satisfiable is NEXPTIME-complete. So your problem (formula validity) is coNEXPTIME-complete.

As cited in the paper, the $NTIME(c^{n / \log n })$ upper and lower bounds  (using different $c > 0$ constants) for the Monadic Predicate Calculus satisfiablility were established in:

Harry R. Lewis: Complexity Results for Classes of Quantificational Formulas. J. Comput. Syst. Sci. 21(3): 317-353 (1980) [pdf download]


For the first question, it is open whether finding a tree decomposition for planar graphs can be done in polynomial time. The best approximation algorithm may be the RatCatcher algorithm by Seymour and Thomas, which computes the branchwidth of the planar graph, so it has a 1.5 approximation ratio by the relation between branchwidth and treewidth.

For the second one, we have the following theorem about the treewidth of $k \times k$ grids:

  Theorem. A $k \times k$ grid has treewidth $k$.

And the bags can be taken with size $k+1$, with a total $k(k-1)$ bags. I'm not sure if this is what you want, so feel free to do it if you modify the definition of "optimal".


Are there non-constructive algorithm existence proofs?

Consider the function (taken from here)

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

Despite the looks, $f$ is computable by the following argument. Either

$0^n$ occurs for every $n$ or
there is a $k$ so that $0^k$ occurs but $0^{k+1}$ does not.

We do not know which it is (yet), but we know that $f \in F = \{f_\infty, f_0, f_1, \dots \}$ with

$f_\infty(n) = 1$ and
$f_k(n) = [n \leq k]$.

Since $F \subset \mathsf{RE}$, $f$ is computable -- but we can not say what  $f$ is.


Combination of Disjointness and Gap Hamming Distance communication complexity

Yes, because (1) KLLRX prove $\Omega(n)$ information lower bound for Gap Hamming (for distribution over both YES and NO inputs), and (2) Theorem 3 in GJPW shows any such information lower bound holds also wrt distribution over NO inputs, and (3) BJKS paper shows that composing any function with m-bit OR increases the information complexity over NO inputs m-fold.


Is there a polynomial-time algorithm to solve graph isomorphism for Delaunay graphs of (finite) hexagonal tessellations?

I guess all those subgraphs will be planer graphs. And I think that there is efficient algorithm for isomorphism of planer graphs.
ref: Linear time algorithm for isomorphism of planar graphs by     J. E. Hopcroft
J. K. Wong
NOTE: I am not an expert and might not be making any sense.


EXP-Complete Problems vs Subexponential Algorithms

Due to popular demand, I’m converting my comment to an answer.

A simple padding argument shows that for every constant $\epsilon>0$, there exist EXP-complete problems in $\mathrm{DTIME}(2^{n^\epsilon})$. Indeed, fix an arbitrary EXP-complete problem $L$, and assume that it is computable in time $2^{n^c}$. Let $d>c/\epsilon$, and consider the problem
$$L'=\left\{0^m\#w:w\in L,m\ge|w|^d\right\}.$$
On the one hand, $L$ is polynomial-time${}^\dagger$ reducible to $L'$ via the function $w\mapsto0^{|w|^d}\#w$, thus $L'$ is EXP-hard.

On the other hand, $L'$ is computable in time $2^{n^\epsilon}$: given an input of size $n$, we first check (in polynomial time) that it is of the form $0^m\#w$ for $m\ge n'^d$, where $n'=|w|$. Then we check if $w\in L$, which takes time $2^{n'^c}\le2^{m^{c/d}}\le2^{m^\epsilon}\le2^{n^\epsilon}$.

${}^\dagger$ Actually, the reduction as given is even uniform $\mathrm{AC}^0$, and it can be made DLogTime if we replace $|w|$ with an upper bound that is a power of two.


Is there any task where classical computers outperform quantum computers?

If you're asking whether a quantum computer can compute any function that a classical computer can compute without using many more elementary computational steps, then the answer is yes: a quantum computer can perform any reversible classical computation, and if you keep the input around, any classical computation can be made reversible at a cost of multiplying the number of steps by a small constant factor.

If you're asking whether a quantum computer can compute any function that a classical computer can without using many more resources, the answer is much less clear. The construction that lets you make a $T$-step computation reversible using $O(T)$ steps also takes $O(T)$ space (i.e., memory cells). You can achieve a smaller blow-up in space at the cost of a superlinear number of steps. See Time/Space Trade-Offs for Reversible Computation by Charles H. Bennett.

For an actual physical quantum computer, it's very likely that you might also be able to make it faithfully simulate a classical computer by letting it lose coherence, but in this case it's no longer really working as a quantum computer, and if you try to use a quantum computer that is operating this way as a subroutine in a quantum computation, it might not work properly.


Empirical probability of k-SAT satisfiability

see eg sec 4.7.4 p103 of this thesis where a finite-size scaling formula based on a power law is applied and coefficients fit with experimental data.

PHASE TRANSITIONS OF BOOLEAN SATISFIABILITY VARIANTS, Bailey 2004


Emptiness of complement of subspace arrangement

Your problem is coNP-hard.
Take a 3SAT instance with variables $X$ and clause set $C$.

Set the dimension in your problem to $n:=|X|$.
For every clause $c\in C$, introduce a corresponding $(n-3)$-dimensional subspace $S(c)$ by restricting the three dimensions that correspond to the three variables in $c$.
If a variable occurrs positively in $c$, then fix the corresponding coordinate at 0.
If a variable occurrs negatively in $c$, then fix the corresponding coordinate at 1.
A 0-1 truth assignment (to the variables in $X$) violates clause $c$, if and only if the vector corresponding to the truth assignment lies in subspace $S(c)$.
A 0-1 truth assignment (to the variables in $X$) satisfies all clauses,
if and only if the vector corresponding to the truth assignment lies in none of the subspaces $S(c)$.


Error correction that adapts to different error rates

This is impossible as stated.  Consider $M = N, K = N/2$.  Up to $\epsilon$, we're asking to be able to recover the whole input from the whole code, and the first half of the input from either the first half of the code or the second half.  But if we can recover the first half of the input from the first half of the code, this implies we can recover the second half of the input from the second half of the code, and vice versa.  Thus we can recover both halves of the input from the first half of the code, which is impossible.


At Aaron's suggestion, here is my second comment from the complexity blog, warts and all.  Italics are (linked) quotes from earlier comments.

  I've seen candidates publishing more than 15 papers a year and then a question was asked whether these 15+ papers are good or not.

  ...because more often than not, the answer is no. Most of the
  uncharacteristically long CVs I've seen in hiring committee meetings
  are chock full of crap. Or they're good in the aggregate, but appear
  to advance their research in too many incremental steps. Even if there
  are diamonds in the slurry, I have to ask—why did they publish all
  that other stuff? Why didn't they make one big splash instead of this
  long, meager dribble? Did they not notice that most of their papers
  were weak? Are they publishing so many papers to advance the state of
  the art, or only to make their CV longer? Are they going to value
  quantity over quality in their own PhD students? Or am I in fact
  witnessing a miracle candidate?

  Despite what Dr. Anonymous two steps above me suggests, these are not irrelevant
  issues. I don't want my department associated with someone known to
  publish reams of crap, or who wastes my colleagues' time reviewing
  tons of incremental papers, or who thinks they're Thor's gift to
  computer science when they're not, or who tries to convince PhD
  students that their CVs need to look like the Manhattan Yellow Pages.
  Those aren't the people I want to work with; that's not the culture I
  want to work in; that's not (in my opinion) what's best for the
  Advancement of Knowledge™.

  And notice I said “suspicious”, not “deadly”. Of course we read
  recommendation letters and search citation indices and even (gasp)
  read the actual papers. Sometimes that's enough to allay my
  suspicions; yes, there are miracle candidates. But just often enough
  for me to keep my suspicions, they're proven right.

  So where exactly does the long CV comes in as a negative, rather than
  the fact that the person does not have significant contributions?

  The problem isn't just that they may not have significant
  contributions, but also that they may have too many not-significant
  contributions. (See my
  earlier comment about "max" vs "sum".)

  Sounds like you guys are rationalizing a case of paper envy, rather
  than following sound academic decisions.

  What the hell is “paper envy”? Result envy or impact envy or
  reputation envy I could get behind, but paper envy? Really? Since when
  are papers something to be envious about?

  Also: Not publicly taking credit for your opinions? Deeply suspicious.


How to write the introduction of a research paper?

Simon Peyton Jones has an excellent web page devoted not only to advice on writing introductions, but whole papers, and there is a cool video as well. On page 18 of his slides he says that the purpose of an introduction is to:

Describe the problem.
State your contributions.

He then goes on for a while to explain what precisely that means in pracrtice. But there is much more to his talk, I highly recommend it.
My personal piece of advice: never ever start your paper by saying "In the recent years the foo technology has become important [1, 2, 3, 7, 10, 12, 13, 21] for saving the world peace, taking photos of kittens, and obtaining academic promotions. But all the people who did foo before us missed a minute point, which we are going to talk about at length in this paper. But first, let us bore you with a review of all the foos out there." Just get to the point, please.


Why is 2-connectedness characterized by the existence of an ear decomposition ?

"Ear decomposition" is not a term I've heard before but it's incorrectly defined, as you've observed, since it doesn't require that the graph be connected, let-alone 2-connected.  An "ear" needs to be defined as having each endpoint adjacent to at least one further vertex of $G$.  (Actually, each endpoint would have to be adjacent to at least two further vertices, or the path wouldn't be maximal.)

With the correct definition, the theorem is true.


Termination checking for Scott-encodings in System F with positive-recursive types

I'll first point you to Types for the Scott Numerals by Plotkin, Cardelli and Abadi, where they show how to encode Scott numerals in plain old system F. This at least shows that you can write the "natural" recursion principles on Scott numerals, and because they correspond to recursors in this encoding, they are guaranteed to terminate.

However, if you want to work directly with the recursive type formulation, you can apply the classical theory of termination of system F augmented with the theory of positive inductive types, comprehensively treated in Ralph Matthes' dissertation, admittedly a technical read.

I'm not 100% sure those techniques apply here though. I think the recursor you'd get for the Scott encoding would be something like

recNat : forall P. ((forall t. t -> (P -> t) -> t) -> P) -> (Nat -> P)

For fixing ideas I wrote a definition in Haskell which was a bit tedious:

rectNat f n = f $ \z s -> n z (\ n' -> s (recNat f n'))

Of course in a Matthes like system, the recursor is primitive and the Haskell definition is simply the operational semantics of the recursor.

and you would write addition by specializing P to Nat -> Nat and implementing the first argument of recNat by:

\n -> n (\m -> m) (\add_n m -> succ $ add_n m)

which I think works out to the correct addition when applied to the recursor.

If you're really adverse to recursors, you can apply standard termination analysis techniques in system F or Calculus of constructions, see e.g. Abel's dissertation which is a real tour-de-force.

Finally, I must caution you against a strange counter example in the realm of recursion with positive inductive types: consider the type

I = (forall t. (t -> t)) -> I

which is positive, since a fortiori it does not even contain recursive arguments! Then one might be tempted to accept the recursive function:

Y :: I -> I
Y i = i Y i

There is no obvious reason to reject this program, since Y is not being recursively applied to any smaller arguments. However, applying Y to the identity function will loop.

All this to say that there are strange counter-examples when dealing with positive inductive types in impredicative settings. However, Scott encodings with structural recursive functions do not seem to trigger these counter-examples, and I believe that they are handled by the standard theory of termination from the literature.


Average-degree Bounded Graphs are no harder than Maximum-degree Bounded Graphs (for distance oracles with purely multiplicative stretch)

Here is, perhaps a more understandable, proof. Let me start with the following claim:

  Let $G=(V,E)$ be an undirected weighted graph with $n$ vertices
      and $m$ edges. For any integer $k \geq 3$, one can convert $G$
      into a graph $H$ with maximum degree $k$ with $m' = (1+2/(k-2))m$
      edges and $n' = n + 2m/(k-2)$ vertices. Furthermore, for any two
      vertices $u$ and $v$ in $G$, the distance between any copy of $u$
      to any copy of $v$ in $H$ is equal to the distance of $u$ and $v$
      in $G$. This conversion can be done in $O(n + m)$ time.

Here is a rough proof to the above claim:

We start with a copy $H$ of $G$. We scan the vertices of $H$ one by one. If a vertex $v \in V(H)$ has degree $\leq k$ then we leave it as it is. Otherwise, consider $v$ and the edges coming out of it. We replace $v$ by a list of $\lceil \deg(v)/(k-2) \rceil$ vertices,    all of them connected by a new path of edges having weight $0$.    Each of these new vertices is assigned at most $k-2$ edges that    were adjacent to $v$ (these reassigned edges keep their original
    weight).  We repeat this process till the degrees in the new graph
    are bounded by $k$.

The number of new vertices created during this process to replace a single vertex $v$ is $ \lceil \deg(v) /(k-2) \rceil$. The number of    new edges created for $v$ is $ \lceil \deg(v) /(k-2) \rceil - 1$.    Clearly, the new graph has $\sum_{v \in V(G)} \lceil \deg(v)/(k-2) \rceil \leq n + \sum_{v \in V(G)} \deg(v) /(k-2) \leq n +
    2m/(k-2)$ vertices. The number of new edges added because of $v$
    is at most $2m/(k-2)$.

In the new graph, we replace every vertex by a path (with all its
    edges having weight $0$), and kept the original edges. As such,
    the distance between two vertices in the modified graph is the
    same as the distance between the corresponding vertices in the
    original graph.

A corollary of the above claim is:

  Let $G=(V,E)$ be an undirected weighted graph with $n$ vertices,
      $m$ edges, and average degree $\mu = 2m/n$. Then one construct
      an equivalent graph with maximum degree $k = \lceil {\mu +2} \rceil$, such
      that the new graph has $2n$ vertices, $m+n$ edges, and has the
      same distances between any pair of vertices as the distance in the
      original graph between the corresponding vertices. The new graph can
      be computed in $O(n + m)$ time.

The above implies that given a graph with average degree $\mu$, we can
replace it with a graph with maximum degree $\mu + 2$, and build the
distance oracle on this new graph instead of the original graph.


How is Lambda Calculus a specific type of Term Writing system?

The answer is it depends what you mean by Term Rewrite System.

When it was introduced, the concept of Term Rewrite Systems, or TRSes, described what is now called first order TRSes, which is simply a set of computation rules of the form

$$ l\rightarrow r $$

where $l$ and $r$ are first order terms of the form

$$ t :=\ x\ \mid\ f(t_1,\ldots,t_n) $$

where $x$ is a variable and $f$ is a function symbol taken from some arbitrary, but fixed set $\Sigma$, called the signature, which also fixes a number of arguments for each $f\in\Sigma$.

There are a couple of common restrictions imposed on rules, e.g. $\mathrm{Var}(r)\subseteq\mathrm{Var}(l)$ but we don't need to go into them here.

With this definition, the usual lambda calculus, with the $\beta$ rule:
$$ (\lambda x. t)\ u \rightarrow t[u/x]$$
cannot be expressed, as the constructor "$\lambda$" binds the occurrence of $x$ in $t$ (application is fine though). One possible solution, and one which is older than the theory of rewriting systems itself, is to turn each $\lambda$ term into another kind of term, which does not involve binding.

One way is the famous $SK$ combinator calculus, which is a rewrite rule with the signature $\Sigma=\{S,\ K, \mathrm{app}\}$ and the rules
$$ \mathrm{app}(\mathrm{app}(K,x),y)\rightarrow x$$
and
$$\mathrm{app}(\mathrm{app}(\mathrm{app}(S, x), y), z)\rightarrow \mathrm{app}(\mathrm{app}(x, z),\mathrm{app}(y, z)) $$

There is another, more intuitive encoding which involves lambda terms with de Bruijn indices and explicit substitutions, but I won't go into it here.

Despite the first order encodings, it became clear that the technical issues with the reduction behavior of the $\lambda$ calculus were better addressed by extending the notion of TRS to include constructors with binders. This is often referred to by the term Higher Order Rewrite Systems. Terms are now taken of the form

$$ t\ :=\ x(t_1,\ldots, t_n)\ \mid\ f(x^1_1\ldots x^1_{i_1}.t_1,\ldots,x^n_1\ldots x^n_{i_n}.t_n) $$

Where again $f\in\Sigma$, but now each $x^i_j$ is bound in $t_i$. Signatures need to specify how many variables are bound by each argument. Now we can write $\mathrm{abs}(x.t)$ for the term representing $\lambda x.t$. With a little work, you can define appropriate notions of substitution.

Here there is less consensus about what constitutes a rewrite rule. One issue is that we want rewriting to be decidable, and so it needs to be decidable whether a left hand side matches a term. But this is usually taken to be modulo $\beta\eta$ which is believed to be decidable, but with only extremely complex and slow algorithms (and just $\beta$ is undecidable!).

Therefore left-hand sides are restricted to be in some nice subset, often the "Miller patterns". A number of results for the first-order case generalize, though there are a few nasty surprises.

It's also common to just take first order systems, and simply add $\lambda$ and application to the term structure, along with ad hoc $\beta$ and $\eta$ reductions. This yields rather reasonable systems, at the cost of (some) generality.

Of course the usual $\lambda$ calculus can be directly written in these systems. For example the $\beta$ rule:

$$\mathrm{app}(\mathrm{abs}(x.y(x)),z)\rightarrow y(z) $$

A pretty decent overview of the definitions and basic results is given by Nipkow and Prehofer here.


The area you want to look at is called "implicit complexity theory". A random and incomplete fistful of names to Google for are Martin Hofmann, Patrick Baillot, Ugo Dal Lago, Simona Ronchi Della Rocca, and Kazushige Terui.

The basic technique is to relate complexity classes to subsystems of linear logic (the so-called "light linear logics"), with the idea that the cut-elimination for the logical system should be complete for the given complexity class (such as LOGSPACE, PTIME, etc). Then via Curry-Howard you get out a programming language in which precisely the programs in the given class are expressible. As you might expect from the mention of linear logic, these all these systems then give rise to monoidal closed categories of various flavors, which leaves you with a purely algebraic and machine-independent characterization of various complexity classes.

One of the things that make this area interesting is that neither traditional complexity nor logical/PL methods are entirely appropriate.

Since the categories involved typically have closed structure, the combinatoric methods favored by complexity theorists often break down (since higher-order programs tend to resist combinatorial characterizations). A typical example of this is the failure of syntactic methods to handle contextual equivalence. Similarly, the methods of semantics also have trouble, since they are often too extensional (since traditionally semanticists have wanted to hide the internal structure of functions). The simplest example I know here is the closure of LOGSPACE under composition: this is AFAIK only possible due to dovetailing and selective recomputation, and you can't treat the problems as pure black boxes.

You will likely also want to have some familiarity with game semantics and Girard's Geometry of Interaction (and their precursor, Kahn-Plotkin-Berry's concrete data structures) if you get seriously into this area -- the ideas of token-passing representations of higher-order computations used in this work supply a lot of the intuitions for ICC.

Since I've pointed out the central role of monoidal categories in this work, you might reasonably wonder about the connections to Mulmuley's GCT. Unfortunately, I can't help you here, since I simply don't know enough. Paul-André Melliès might be a good person to ask, though.


What is known about NP hard problems that access preprocessed information?

Precomputation is often related to the class P/poly which captures problems solvable in polynomial time by Turing machines with access to some poly-sized advice string, that only depends on the size of the instance, but not the instance itself. The Karp-Lipton theorem states, that NP is not contained in P/poly, unless the PH collapses to the second level, which is considered unlikely by many complexity theorists.


Forbidden minors for bounded treewidth graphs

In Sparse obstructions and exact treewidth determination, Lucena states that in the PhD thesis of Sanders, "75 or so minimal forbidden minors for treewidth $\leq 4$ are given, and it is believed though not proven that this may constitute the entire obstruction set."


Complexity of MAX-ONEs Monotone 2-SAT with $n^{3/2}$ or $C n^2$ clauses?

In both questions the answer is the same for any exponent $1 < \alpha < 2$.
For the first question, we can use a degeneracy based algorithm to find an independent set of size $\Omega(\frac{n}{n^{\alpha-1}}) = \Omega(n^{2-\alpha})$ in polynomial time. Therefore we get an FPT algorithm for every constant $\alpha$ simply by outputting YES if $k < c n^{2-\alpha}$ for some constant $c$, and otherwise solving the problem with bruteforce in $2^n = 2^{O(k^{1/(2-\alpha)})}$ time.
For the second question, we can prove that the problem is NP-hard for all $1 < \alpha < 2$ by reducing from maximum independent set problem in 3-regular graphs, which is NP-hard [1].
For some constant $\beta$ we make $n^\beta$ copies of each vertex, making the set of copies a clique for each vertex. Now the new graph has exactly the same maximum independent set as the old graph. It is $4 n^\beta - 1$ regular and has $n^{\beta+1}$ vertices, so we can choose $\beta \approx \frac{\alpha-1}{2-\alpha}$ to make it work for any $1 < \alpha < 2$.
[1] Garey, Michael R., David S. Johnson, and Larry Stockmeyer. "Some simplified NP-complete problems." STOC 1974.


Which results make quantum space interesting?

I think Amnon Ta-Shma's new result is a good answer to my own question.

Amnon Ta-Shma: Inverting well conditioned matrices in quantum logspace. STOC 2013: 881-890. (copy from author's website)

  ...  We show that the inverse of a well conditioned matrix can be approximated in quantum logspace with intermediate measurements. This should be compared with the best known classical algorithm for the problem that requires $\Omega(\log^2 n)$ space. We also show how to approximate the spectrum of a normal matrix, or the singular values of an arbitrary matrix, with $\epsilon$ additive accuracy, and how to approximate the singular value decomposition (SVD) of a matrix whose singular values are well separated. ...


Problems that can be used to show polynomial-time hardness results

Yes, the best known algorithm for $k$-SUM runs in $O(n^{\lceil k/2 \rceil})$ time, so it's very possible that you could argue some $n^7$ problem is difficult, because if it's in $n^{6.99}$ then you can solve $14$-SUM faster.

Note the $k$-SUM problem gets "easier" as $k$ increases: given an improved algorithm for $k$-SUM, it's fairly easy to get an improved algorithm for $2k$-SUM: take all $O(n^2)$ pairs of $n$ numbers in your given $2k$-SUM instance, replacing each pair with the sum of the two, and look for a sum of $k$ numbers out of those that equal $0$. Then, an $O(n^{k/2-\varepsilon})$ algorithm for $k$-SUM implies an $O(n^{k-2\varepsilon})$ algorithm for $2k$-SUM. Put another way, a tight lower bound for $2k$-SUM is a stronger assumption than a tight lower bound for $k$-SUM.

Another candidate for a hard problem is $k$-Clique. See my $O(\log n)$-Clique answer for more on that. If you can show (for example) that a better algorithm for your problem implies an $O(n^2)$ algorithm for $3$-clique, then a super-breakthrough would be required to improve on your algorithm. Parameterized complexity gives many examples of other problems like this: $k$-Clique is hard for the class $W\[1\]$, and $k$-SUM is hard for $W\[2\]$.

Let me warn you that although problems like this are very convenient to work with, problems like $3$-SUM are not among the "hardest" in $TIME[n^2]$, e.g., it is very unlikely that every problem in $TIME[n^2]$ can actually be linear-time reduced to $3$-SUM. This is because $3$-SUM can be solved with $O(\log n)$ bits of nondeterminism in linear time, so if everything in quadratic time can be reduced to $3$-SUM, then $P \neq NP$ and other fantastic consequences results. More on this point can be found in the article "How hard are $n^2$-hard problems?" (At some point, "3SUM-hard" was called "$n^2$-hard"; this SIGACT article rightly complained about that name.)


I think I can now demonstrate a nontrivial lower bound. The idea is to implement any such program with a family of comparison branching programs. The `read-only' assumption means that our family of branching programs uses little, i.e. $O(\log n)$, space. Then we apply the lower bound $ST=\Omega(n^2)$ proved by Borodin et al. in "A Time-Space Tradeoff for Sorting on non-oblivious Machines." This gives us a $n^2/\log n$ lower bound for the time.

In a bit more detail: We can dispense with operation 5 above. Loosely speaking, if we can already compare the heads of two lists and print the head of a list, then there is no need for us to isolate the head of a list on a particular register. Assuming this, we see that every register in the machine only ever stores a final substring of the input.

Suppose our register program has $\ell$ lines of code and $k$ registers, $X_1,\dots,X_k$.

Fix $n$. We construct the comparison branching program for strings of length $n$ as follows. Create a node for each tuple $(i,d_1,\dots,d_k)$ where $1\le i\le \ell$  and $0\le d_1 ,\dots, d_k \le n$. The idea is, computations in the register machine correspond to paths in the branching program, and we're at node $(i,d_1 ,\dots, d_k)$ if we're at line $i$ in the register machine and the length of the string stored in $X_i$ is $d_i$. Now, we have to define the directed edges of the branching program

If line $i$ is of the form

if $X_u<X_v$ then goto $i_1$ else goto $i_2$

then for all $d_1,\dots,d_k$, node $(i,d_1,\dots,d_k)$ is labelled by comparing the $d_u$-th and $d_v$-th element of input, and having the "true" edge go to $(i_1,d_1,\dots,d_k)$, and the "false" edge to $(i_2,d_1,\dots,d_k)$.

If line $i$ is of the form

$X_1 \leftarrow tail(X_2)$, goto line $i'$

then there is an arrow from any node $(i,d_1,\dots,d_k)$ to $(i',d_2-1,\dots,d_k)$.

If line $i$ is of the form

$print(head(X_u))$, goto line $i'$

then there is an arrow from any node $(i,d_1,\dots,d_k)$ to $(i',d_1,\dots,d_k)$ which is labelled by the $d_u$-th node of the input.

Hopefully these examples make it clear how I intend to construct my branching program. When all is said and done, this branching program has at most $\ell\cdot n^k$ nodes, so it has space $O(\log n)$


Can true randomness (provably) be replaced with Kolmogorov randomness for RP?

I think the question being asked here is roughly "is there a sense in which we can replace the sequence of random bits in an algorithm with bits drawn deterministically from an appropriately long Kolmogorov random string?" This is at least the question I will attempt to answer! (The short answer is "Yes, but only if you amplify the error probability first")

Yes...

We can certainly say something here. Let $L$ be some language and let $A$ be an algorithm which takes as input $x$ and a random string $r\in U_{f(|x|)}$ (the uniform distribution over $\{0,1\}^{f(|x|)}$) s.t. $\Pr[A(x,r)=L(x)]>1-\epsilon(x)$. In other words, $A$ is an algorithm which errs with probability at most $\epsilon(\cdot)$.

Notice now that if $A$ gives the wrong answer on $(x,r)$ ie, $A(x,r)\not=L(x)$, this gives us some means of describing $r$, in particular, we can describe it as the $i$-th string which causes $A$ to err on $x.$ To do this, we simply make the machine which has hard-coded $x$, $A$, $i$, and a bit $b=1\iff x\in L$, and simply enumerates choices of $r'$ from $\{0,1\}^{f(|x|)}$ until it finds the $i$-th choice of $r'$ such that $A(x,r')\not= b$.

So now that we know we can leverage being a bad choice of random string into a description, let's observe some conditions which are sufficient for turning our description of $r$ into a compression. To describe $r$, we require enough bits to describe $x$, $i$, $b$, and then the code for our procedure (the code for $A$ and the routine we described), giving as a description of length $$|x|+|i|+O(1)=|x|+\log_2(2^{f(|x|)}\epsilon(x))+O(1)=|x|+f(|x|)-\log(1/\epsilon(x))+O(1).$$

Recall that $r$ is length $f(|x|)$, so this is a compression of $r$ if $$\log(1/\epsilon(x)) = |x|+\omega(1),$$ for example, when $\epsilon(x)=1/2^{2|x|}$.

Finally, observe that if $r$ were a Kolmogorov random string, then we could have no such compression, so as long as the error probability of $A$ is sufficiently small, a Kolmogorov random string in place of the sequence of random bits will cause $A$ to answer correctly!

Notice that the only thing we leverage about $A$ is that its error probability is small. We don't care if $A$ has an extremely long run time or if $A$ has one or two sided error.

Bringing this back to the question of $RP$ (or $coRP$ or $BPP$), this says that as long as we amplify the error probability of our algorithms, we can use Kolmogorov random strings in place of their random bits.

...But only if we amplify first.

A followup question may be "can I do this without amplifying the error probability?" Consider the following algorithm $A$ which decides $\{0,1\}^*$ and has error probability $1/2^n$.

On input $x$:

Generate a string $r\in\{0,1\}^n$
If $r=x$, reject.
Accept.

Notice that for every choice of $r$, there is some choice of $x$ such that $A$ errs on $x$, namely the choice of $r$ that is $x$, so we can not replace the random sequence of bits used by $A$ with a Kolmogorov random string without amplifying it's error probability!

A note about the source: I'm not sure if any of this is novel, but I included the first argument in my writeup for my qualifying exam which will eventually be available online after I finish revising it.


According to the 59th slide of the following pdf:

https://grow2015.sciencesconf.org/file/174789 (A talk by D.Kratsch at GROW 2015)

we have that

  A vertex in a graph is weakly simplicial if its neighborhood is an
  independent set and the neighborhoods of its neighbors form a
  chain under inclusion.

See the slide for an illustration. The context where this definition is found in the slides is chordal bipartite graphs, so I guess this might be what you are looking for.


How does one determine if a mixed bipartite quantum state is entangled or not?

In http://arxiv.org/pdf/quant-ph/0303055v1.pdf, it is shown that the weak membership problem for the set of separable states is NP-hard. As you can see in Definition 6.2 (page 18), this amounts to deciding if a state has a separable decomposition up to accuracy $\delta$.

If you want to convert this to a search problem, you can thus do so by using a $\delta$-net on the set of all separable decompositions and doing an exhaustive search.  Note that the maximal number of terms required in such a decomposition is bounded by $(d_Ad_B)^2$ (where $d_A$ and $d_B$ are the dimensions of the two systems).

In particular, such a decomposition to accuracy $\delta$ can be used as a proof for weak membership in the set of separable states, proving that the problem is in NP.

Note that the problem clearly remains NP-hard for any higher accuracy (i.e. any accuracy which increases with the problem size).  On the other hand, since any separable decomposition with $N$ digits of accuracy can be verified in $\mathrm{poly}(N)$ time, the problem remains inside NP (and thus NP-complete) even with an exponential precision.


Would it be possible for a compiler to convert a recursive sum into the average formula?

I assume you are asking whether a "reasonable" system exists that can express these functions and also also decide whether any two expressible function definitions define the same function. (An unreasonable system would be, for example, the language which has only the two function definitions above in it...)

Both of functions are expressible in Buss's bounded arithmetic, so yes, to your first question, though I'm not aware that anyone has actually converted these systems into practical computer languages. For one thing, the algorithm should exist, but are (almost?) certainly unfeasible unless P==NP. (Almost: I'd guess that the problem of function equivalence in any of Buss's systems is at least NP hard, but I have no proof.)

For your second question, I guess we would have to define "reasonable" meant more carefully. It seems plausible to me that one could create a "combinatorics expert system" that could recognize and "automatically optimize" many such simple functions -- perhaps it would look something like "Mathematica" :) -- but I assume that isn't what you are talking about.


This is a special case of the Travelling Salesman with Neighborhoods (TSPN) problem. In the general version, the neighborhoods need not all be the same.

A paper by Dumitrescu and Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, addresses your question. They give a constant factor approximation algorithm for a slightly more general problem (case 1), and a PTAS when the neighborhoods are disjoint balls of the same size (case 2).

As a side comment, I think Mitchell has done a lot of work on geometric TSP variants, so you might want to look at his other papers.


What are the criteria for inviting conference papers (e.g. SODA) for special issue?

You may want to refer to the editorials introducing recent special issues:

SODA 2016: https://dl.acm.org/citation.cfm?id=3230647

SODA 2017: https://dl.acm.org/citation.cfm?id=3319426

They both start with essentially the same paragraph:

  We are delighted to present a Special Issue of ACM Transactions on Algorithms, containing full
  versions of seven papers that were presented at the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) in Barcelona, Spain, on January 16–19, 2017. These papers, selected
  on the basis of their high rating by the conference program committee, have been thoroughly
  reviewed according to the journal’s highest standards.

(Emphasis mine.)

For something more detailed about the selection process, you probably want to follow Josh's suggestion from the comments: contact the PC chair directly, and ask for a brief explanation, ideally printed on official letterhead. My experience is that the process of selecting the special issue papers is not standardized, but usually involves identifying the papers that received the highest scores, and/or collecting suggestions from PC members, and then possibly having some voting procedure.