What is the complexity of (possibly succinct) Nurikabe?

You seem to be really asking: is Nurikabe in NP?

Nurikabe is NP-hard, since one can build polynomial-size gadgets that can be used to reduce an NP-complete problem to a Nurikabe decision problem.  This is what Holzer, Klein, and Kutrib do, and also McPhail and Fix in their poster (both referenced from the Wikipedia article).

Both groups of authors assume that the problem is trivially in NP, and wave away the question of membership.  Your unease about succinct instances seems spot on -- I do not believe the problem is in NP.  Consider the following way to formalise the decision problem:

  BINARY NURIKABE
  Input: integers m and n in binary, representing a Nurikabe board, and a list of triples, each indicating a position on the board and a positive integer written in that position.
  Question: can the remaining board positions be coloured with two colours, respecting the Nurikabe constraints?

If $m$ and $n$ are instead specified in unary, then the decision problem of determining if there exists some (not necessarily unique) solution to a given Nurikabe instance is in NP, as a solution can be specified in at most $mn$ bits which is then polynomial in the input size.

In contrast, with a binary encoding, there is a problem (as you point out): if one has just one large constraint (say, the number $(m-2)(n-2)$ placed in the middle of the $m \times n$ board), then a solution will require $mn-1$ bits to represent, which is exponential in the size of the input $\Theta(\log\, m + \log\, n)$.  This means that the problem is not in NP, unless small certificates always exist.

Your question then becomes: do there exist polynomial-sized certificates for all binary Nurikabe instances, which can be checked in polynomial time?

It is not obvious to me that such certificates necessarily exist.  Nor is it obvious how one would go about proving that succinct, quickly-verifiable certificates cannot exist.

However, the restriction to unique solutions means that the problem is actually US-hard, so co-NP-hard, and therefore unlikely to be in NP.  The point is that if one regards "has a unique solution" as a Nurikabe constraint (as opposed to a desirable feature of instances that are presented to humans), then it is not sufficient to demonstrate that there is a solution, but one must also demonstrate that no other solutions are possible.  This requirement alone is then enough to ensure the problem is probably not in NP.  This is true even for the unary version of the problem.

In summary: if one relaxes the unique solutions requirement, and specifies the board size in unary, then the decision problem is in NP; with non-unique solutions and binary board size, it is unclear whether the decision problem is in NP; and with unique solutions the decision problem is US-hard and therefore unlikely to be in NP, for either encoding of the board size.


Is there any research on Turing machines with transition relation homomorphic to given algebraic structure?

There are results about algebraic properties of languages (as opposed to the machines accepting the languages). For example, regular languages can be characterised using monoids. The Myhill-Nerode theorem relates an algebraic structure with the transition relation of a specific class of finite automata. You could look up those and subsequent results.

Rather than homomorphisms, bisimulation and simulation relations are the notion of choice for relating the structure of transition systems. Checking language equivalence between pushdown automata is undecidable but deciding equivalence of languages accepted by deterministic PDAs was open until 2001 when Gerard Sénizergues showed it was decidable. His proof uses algebraic ideas. Colin Stirling later gave a simplified proof (writeups and slides are available on his homepage).

  Sénizergues, Géraud, The equivalence problem for deterministic pushdown automata is decidable, Degano, Pierpaolo (ed.) et al., Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7--11, 1997. Proceedings. Berlin: Springer-Verlag (ISBN 978-3-540-63165-1/pbk; 978-3-540-69194-5/ebook). Lecture Notes in Computer Science 1256, 671-681 (1997). ZBL1401.68168.


Equivalent formula for LTL with and without past operators

The "equally expressive" statement means that if a formula of PLTL is a statement about the future, i.e. if it's evaluated at the first instant $0$ of the time domain $\mathbb N$, then there exists an equivalent LTL formula.
This means that nesting future and past operators is not more expressive than nesting just future operators, as long as the global meaning of the whole formula is solely about the future.

Here are some examples of this equivalence:

$\lozenge\square\lozenge^-\varphi\equiv\lozenge\varphi$
$\lozenge(\alpha\wedge (\varphi \mathcal S \psi)) \equiv \lozenge (\psi \wedge (\alpha\vee \bigcirc (\varphi \mathcal U (\varphi\wedge \alpha)))$


There are two kinds of "best" SAT solvers, one for theory, one for practice.
Theory

Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki, "Improved Randomized Algorithms for 3-SAT", ISAAC 2010.

randomized $O(1.32113^n)$ for 3SAT.

Timon Hertli, Robin A. Moser, Dominik Scheder, "Improving PPSZ for 3-SAT using Critical Variables", 2011.

randomized $O(1.321^n)$ for 3SAT.

Konstantin Kutzkov, Dominik Scheder, "Using CSP To Improve Deterministic 3-SAT", 2010.

deterministic $O(1.439^n)$ for 3SAT.

Practice
Check SAT conference for competition results for each year.


Classic Neural Network Layout for regression: is the score function derivable?

It depends on what activation function you use.  With all standard activation functions, neural networks are continuous.  With ReLU activations (the most typical choice of activation function), they are piecewise differentiable.  The partial derivatives (the gradient) can be computed efficiently (using so-called "backpropagation"), and standard neural network frameworks will automate this process for you, as computing the derivative is part of how neural networks are trained.  Consequently, it is possible to use gradient descent methods to find $x$ that (approximately) minimizes $f(x)$, when $f(x)$ is instantiated as a neural network.  $f(x)$ is not convex so you are not guaranteed to find the global minimum but for many problems this may be adequate; in others, you can adjust gradient descent (e.g., using random restarts) to mitigate those problems.


NP-complete decision problems on deterministic automata

The decision version of the DFA identification problem  (find a possibly non-unique smallest DFA that is consistent with a set of given labeled examples) is NP-complete:

Input: Integer $k$ and sets $P, N \subseteq \Sigma^*$

Question: Is there a DFA $A$ with at most $k$ states such that $P \subseteq L(A)$ and $N \cap L(A) = \emptyset$. In other words $A$ accepts all words in $P$ and rejects all words in $N$.

See: E Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302–320, June 1978


Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?

One major application of topology in semantics is the topological approach to computability.

The basic idea of the topology of computability comes from the observation that termination and nontermination are not symmetric. It is possible to observe whether a black-box program terminates (simply wait long enough), but it's not possible to observe whether it doesn't terminate (since you can never be certain you have not waited long enough to see it terminate). This corresponds to equipping the two point set {HALT, LOOP} with the Sierpinski topology, where $\emptyset, \{HALT\}, and \{HALT, LOOP\}$ are the open sets. So then we can basically get pretty far equating "open set" with "computable property". One surprise of this approach to traditional topologists is the central role that non-Hausdorff spaces play. This is because you can basically make the following identifications

$$
\begin{matrix}
\mathbf{Computability} & \mathbf{Topology}\\
\mbox{Type} & \mbox{Space} \\
\mbox{Computable function} & \mbox{Continuous function} \\
\mbox{Decidable set} & \mbox{Clopen set} \\
\mbox{Semi-decidable set} & \mbox{Open set} \\
\mbox{Set with semidecidable complement} & \mbox{Closed set} \\
\mbox{Set with decidable equality} & \mbox{Discrete space} \\
\mbox{Set with semidecidable equality} & \mbox{Hausdorff space} \\
\mbox{Exhaustively searchable set} & \mbox{Compact space} \\
\end{matrix}
$$

Two good surveys of these ideas are MB Smyth's Topology in the Handbook of Logic in Computer Science and Martin Escardo's Synthetic topology of data types and classical spaces.

Topological methods also play an important role in the semantics of concurrency, but I know much less about that.


Is there a way to detect search engine bias?

This is obviously a very open ended question, but so as to stay on topic, here is one CS theory approach to the idea of "fairness" and how to enforce it.

"Fairness Through Awareness" Dwork, Hardt, Pitassi, Reingold, Zemel
http://arxiv.org/abs/1104.3913


What's the point of stack judgement in CBPV?

The point of stacks is that they are in a sense the dual concept to computations.

A computation does not run in a vacuum. It is always "surrounded" by some sort of an environment, or evaluation context, telling us what the current "state of progress" is, or is recording "where we are, and where we're going". Often this sort of information has stack-like behavior, so we can call it simply a stack.

The duality between computations and stacks can be made quite precise and is useful in formalizing and discovering various mathematical aspects of computation. I am not sure where you're expecting a more technical answer, but that's the gist of it.


Spectral techniques for genus of a graph

It is NP-hard to approximate the genus of a graph to within an additive error of $O(n^\epsilon)$.  There are polynomial-time algorithms that compute an embeddings of genus $O(g\sqrt{n})$ or  $\max\{4g, g+4n\}$, where $g$ is the true genus and $n$ is the number of vertices.  A significantly better approximation algorithm, spectral or otherwise, would be a significant breakthrough!

See: Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky. A note on approximating graph genus.  Information Processing Letters 61(6):317–322, 1997.


Hamiltonian cycle on a subset of 2D points, constrained by maximum total length

As RB mentioned, this is the Orienteering problem. For points on a plane, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.92.5979 gives a PTAS.


Difficulty of Getting into Top Graduate Program in TCS

Disclaimer: I am just a student, so I cannot speak authoritatively about admissions. I haven't been on an admissions committee, but I can tell you my understanding of how it works.

A PhD admissions committee looks at an application and asks "will this person do well in our PhD program?" Doing a PhD is first and foremost about doing novel research. So the question is: "Can this person do research?"

Your application has several parts, which together need to convince the committee that the answer is yes. Below are my thoughts on the various aspects.

Recommendation Letters: These are extremely important. A good recommendation letter comes from someone who knows you well in a research setting and who is an established researcher. Such a person should be in a good position to judge your ability to do research and their opinion will carry a lot of weight.
 A strong recommendation letter will talk about research-level work you have done and speak about your skills as a researcher, particularly your ability to be self-directed. A letter that only talks about how you did in class is not strong.
 To get strong recommendation letters, you should try to do research projects with professors either at your college or at a different college through an REU program or similar. If you do well, those professors will be able to write strong letters for you. (Make sure to work with research-active professors. e.g. work with a professor that has current PhD students. The more well-known your letter writer is, the more weight their recommendation carries.)
 Publications: If you already have written research articles, that is a clear sign that you can do research. Don't worry too much about this. If your recommendation letters say that the work you did is of publishable quality, that already says a lot, even if it hasn't been published yet.
 GPA and Transcript: Having a good GPA and transcript matters, but is not decisive on its own. It shows that you are hardworking and that you have the appropriate background, which are necessary attributes for a PhD student.
More important than overall GPA is which courses you took and how well you did in them. Getting a B in art history will not sink your Theoretical Computer Science PhD application, whereas a B in Algorithms or Linear Algebra is a red flag.
Taking more computer science and math courses, particularly at higher levels, and getting good grades makes your application look solid.
 Your College: Being an undergraduate at a top research university is an advantage because it gives you exposure to a research environment and gives you opportunities to do research, which leads to strong recommendation letters. If you are at, say, a liberal arts college, you will need to be more proactive about finding research opportunities (e.g. by doing a REU at a research university over the summer).
 Admissions committees will not discount your application based on your undergraduate institution.
Personal Statement: The personal statement should convince the committee that you have the right motivation for doing a PhD. In particular, it should tell them why you want to do research.Do not talk about what you did when you were 10 years old --- that's completely irrelevant. Talk about your recent research experiences; talk about scientific questions that excite you.
 You do not need to choose a subfield when applying. However, it looks good if you can discuss some subfields that interest you; it shows that you have thought seriously about what you want to do. Read up on the professors at the school you are applying to. If one of them does something that excites you, mention it (and why).
GRE scores: Everyone knows the GRE is flawed, but it is the only standardized information available. Top programs receive far too many applications, so they may use the GRE to "filter" applications. As long as your GRE score is passable, it is not a problem.
Writing Sample: A few places ask for a writing sample. They want to know if you can write clearly --- this is important when writing research articles.  Just make sure this has been appropriately proofread. Bad spelling and grammar or rambling are a bad look. (This applies to your whole application!)
CV: This should be a concise overview of your skills and experiences.
Web Presence: Some professors will google you. So your web presence can matter.You can take control of your web presence by setting up a homepage. This doesn't need to be fancy. As a bonus, you can set up analytics and see who is googling you.

The fact that you are thinking about this as a sophomore is a promising sign that you are on the right track.

Don't worry too much! Get some research experience --- this is also useful to you, as it gives you useful experience and helps you figure out whether you will enjoy doing research full time. Otherwise, just work hard and take courses that interest you.

One final piece of advice: Ask people to read over your application, e.g. the people writing your recommendation letters. They can tell you if you have missed something.

TL;DR: Do research!


Was this complexity measure studied before?

What you call the "revealing complexity" is sometimes called the (deterministic) query complexity of exact learning with membership queries.

Exact learning refers to the fact that you have to exactly identify $x\in C$ at the end, as opposed to being (say) probably approximately correct (as in PAC learning). Membership queries refers to the fact that you can query the individual bits of $x$ (as opposed to being given a random sample according to some distribution, as in PAC learning).

See this related question where I explain some of what's known about this complexity measure.
For example, we know that the deterministic query complexity of exactly learning a concept class $C\subseteq \{0,1\}^n$ with membership queries is characterized up to a factor of $\log |C|$ by the complexity measure defined in this paper by Servedio and Gortler or the extended teaching dimension of Hegedus. Both measures are combinatorial in nature. Whether there is a combinatorial measure that captures this complexity without a $\log|C|$ factor is unknown to me (and probably an open problem).


How to design concurrent data structures?

While I have not read deeply in this area, I found The Art of Multiprocessor Programming by Maurice Herlihy and Nir Shavit to be a helpful introduction and survey of techniques.  It explores different algorithms, reasons about how they work and examines the trade-offs, features and limitations of the different approaches.  While it has some formalism I expect it is a fairly introductory and accessible text.

For a flavor of the text, here is the introduction to the section on Atomic Registers from the 2008 edition:

  The obvious place to begin is to ask whether we can solve consensus
  using atomic registers.  Surprisingly, perhaps, the answer is no.  We
  will show that there is no binary consensus protocol for two threads.
  We leave it as an exercise to show that if two threads cannot reach
  consensus on two values, then n threads cannot reach consensus on
  k values, where n > 2 and k > 2.


[Moved from comment]

The paper "Sparsest cuts and bottlenecks in graphs" by David W. Matula, Farhad Shahrokhi gives a reduction from max-cut problem. Max-cut's proof of hardness can be found in Garey Johnson.


Complexity lower bound for regular languages

I'll answer my own question -- the conjectured lower bound is false. Consider
$L_n=\Sigma^* 0 \Sigma^n$ (that is, the collection of all strings with a $0$ in the $n$th location from the end). It's easy to see that there is an $O(n)$ size NFA for $L_n$, but the minimal DFA for $L_n$ is exponential. Here is a TM that decides membership in $L_n$ in time $O(|x|+n)$: scan $x$ to the end (time $|x|$) and read $n$ steps back to see if that letter is $0$.


Good resources to learn loopy belief propagation

The following tech-report (a simplified version of an earlier paper by the same authors) on general BP (not only loopy-BP), but has fantastic insights.
It's a great place to start, if you already haven't.

http://www.merl.com/publications/docs/TR2001-22.pdf

Another good place is this book:
Information, Physics, and Computation - by Mezard and Montanari.


What do we know about checking real-stability of multivariate complex polynomials?

Here is at least some upper bound: treat the polynomial $\mathbb{C}^n \to \mathbb{C}$ as $\mathbb{R}^{2n} \to \mathbb{R}^2$, and then ask in the first order theory of the reals if $p(x)=0$ implies that the imaginary part of each coordinate of $x$ is nonpositive. This can be solved in $\mathsf{PSPACE}$ (e.g. http://en.wikipedia.org/wiki/Existential_theory_of_the_reals).

Of course, the existential theory of the reals is $\mathsf{NP}$-hard, so taking this route in general won't get you below $\mathsf{NP}$...


What is the fastest algorithm for calculating nth term of Fibonacci sequence?

According to this Project Nayuki link, Fast doubling is even faster than Fast Matrix, because redundant calculations are removed.


An easy case of SAT that is not easy for tree resolution

It sounds like you are interested in all-different constraints (and your last sentence is on the right track).  These are non-trivial instances of the pigeonhole principle, where the number of pigeons is not necessarily greater than the number of holes, and in addition some pigeons may be barred from some of the holes.

All-different constraints can be decided by matching in low-order polynomial time.

Jean-Charles Régin, A filtering algorithm for constraints of difference in CSPs, AAAI 1994, 362–367.
D. E. Knuth and A. Raghunathan, The problem of compatible representatives, SIAM J. Discrete Math. 5 422–427, 1992.  doi:10.1137/0405033

When all-different constraints are expressed (using one of several encodings) as SAT instances, then conflict-driven clause learning usually quickly finds a solution if it exists.  However, pure resolution for the PHP has to build a superpolynomially large set of clauses to show that the instance is unsatisfiable.  This bound clearly holds for this more general problem.  On the other hand, recall that Cook's encoding of the PHP allows polynomial-sized extended resolution refutations.

S. A. Cook, A short proof of the pigeon hole principle using extended resolution, SIGACT News 8 28–32, 1976.  doi:10.1145/1008335.1008338

Recent work along these lines is Chapter 5 of Sergi Oliva's thesis, which formed the basis of a paper with Alberto Atserias at CCC 2013.

I expect you are aware of Cook's classic result, so perhaps you meant to restrict the power of the proof system in your third condition?


What Topics Are Suggested for Ph.D. Research?

It is an extremely broad question, and probably the wrong question, but I actually think the answer is pretty short. I'll just give you the advice that I was given (from multiple people), and the advice that most people I know would give:

http://matt.might.net/articles/phd-school-in-pictures/

In other words, you start with an interest, and that interest develops into a specialty. You deepen that interest, and then you expand a small amount on it in your PhD. Telling you what to do not only in some ways would defeat the purpose of you actually getting a PhD (i.e., you picking a specialty and pursuing it because you like it), but it says some pretty strong things about a PhD: that is, I personally think it's more helpful to think of a PhD not as the crowning achievement of your career, but as a good start, and since yours will almost certainly not be revolutionary (like, say Syntactic Structures), it is much more descriptive to explain the process than it is to tell you what specifically to do.

Good luck, though!


Sure, here's a basic checklist. It would make for a very dry read to actually follow these to the letter, but maybe you should first try to write extremely formally, then see where it's reasonable to relax the writing without risk of misunderstanding or vagueness.

Preface. The high-level goal of formality is to make your proof closer to "machine-checkable". You want to allow people of a variety of different backgrounds, knowledge levels, abilities, and intuitions to be able to read your definitions, claims and proofs, understand what they say, and verify that they are correct.

Just as a computer cannot execute a program that is vague and skip steps, so it is difficult for a human to verify a proof with the same flaws.

However, a caveat is that mathematical formality is not perfectly aligned with conveying understanding. Notice I said "verify" above, not "understand". But even if the goal is to convey understanding, it is important to at least be able to formalize what one writes, since you want to convey to others the ability to formalize it.

Define terminology and notation precisely. For example, this is informal:

  each vertex gets a weight $w_v$ whenever it gets matched, and $W$ is
  the total of all the weights.

This is formal:

  the graph $G$ has a set of vertices $V$. For each vertex $v \in V$, the algorithm is given its weight $w_v$. For an algorithm $A$, let $S_A \subseteq V$ be the vertices matched by $A$. $S_A$ is a random variable depending on the random choices of $A$. Let $W_A = \mathbb{E} \sum_{v \in S_A} w_v$ where the expectation is over the randomness of $A$.

Why bury ourselves in so much notation? For one thing, notice that in the formal rewrite, we realized $W$ wasn't well-defined because it depended on the algorithm (and even its randomness), so we had to introduce and define notation to capture that. We had to introduce notation $S_A$, but it will come in handy later anyway.

Try not to feel frustrated or annoyed if things that sound simple take up a lot of space and require a lot of notation when written formally. Don't think of this as dirty work, think of it as a valuable part of the process to deeply understanding what you're writing.

Do not use a technical term if you have not defined it yet, and do not use nontechnical terms in a technical discussion or proof. For example, do not say "because $G$ is an expander, ..." as part of a step of a proof if a precise definition of expander has not yet appeared. But it's okay to say "intuitively, $G$ is acting like an expander". Do not say as part of a proof, "if the algorithm has made enough matches, then ..." unless you have precisely defined what that means. Better is to define a threshold $R(t)$ at each time $t$, then say "if the number of matches at time $t$ is at least $R(t)$, then...."
State results precisely using a logical sentence. Any proposition / lemma / theorem should really be a logical sentence such as "For all $x$ such that $P(x)$, there exists $y$ such that $Q(x,y)$. For example, "There exists a constant $c$ such that the following holds: For all input graphs on $n$ nodes, there exists $m$ such that Algorithm 4 runs in $m$ steps and $m \leq c n^3$."

First make sure you can write the result you are stating in this form, then see if you're willing to relax it to someting like "Algorithm 4 runs in time $O(n^3)$ on graphs of $n$ vertices". I would avoid something like "Algorithm 4 runs in cubic time" since it's unclear (cubic in what?).
Understand what a "step" of a proof is and use them well. A step in the proof starts with what has already been shown so far and applies a simple, known fact, axiom, or result (properly cited/stated) to get a new statement. For example, if we have already shown that $M \leq (1+x)^n$, then we can apply the fact that $1+x \leq e^x$ for all $x$ to deduce $M \leq e^{nx}$.

Even there I left out a step: $(e^x)^n = e^{nx}$. When in doubt, do not omit any step bigger than that. You can always cut them down later.

Your proof should be a sequence of steps of this kind, where the first step only uses assumptions stated in the claim, each step uses only statements shown in previous steps, and the last step derives the statement in the claim.

You should also split proofs into lemmas and so on, but that's beyond my scope.
In particular, each step should be short and easy to follow. If you are trying to write formally as a beginner, don't skip a bunch of lines of calculation and expect the reader to trust you. (If for some reason you do, at least tell the reader that's what you're doing!) The reader should be able to see immediately why this step is correct.

A big mistake beginning proof-writers make (also experienced ones) is to not bother writing why a seemingly-obvious step is true. This is a big red flag. Sit down and go through the math convincing yourself why that "obvious" step is true, then put that into the proof! Do not ever write "clearly" or "obviously". Give me the fact for why it's clear ("Because probabilities are at most $1$, $\sum p_i \leq n$").
When you proofread, do so extremely slowly, carefully, and pretend you're explaining to someone who has never seen your paper. Read it out loud if you have to. If you proofread in your head fast, you're just reminding yourself of what you intended it to say. A step or definition left out of the paper won't be noticed because it will still be in your head. You want to check that each sentence makes sense given (only) what came before it.


An example of a locally monotone function is $g(x,y) = x \cdot (1-y)$. In this example $g$ is monotone increasing in $x$ and monotone decreasing in $y$.

An example of a function that is not locally monotone is $h(x,y) = x \oplus y$.
Let's see why it is not locally monotone. Look at the $x$ variable. (1) It is neither monotone increasing in $x$ since $h(0,1) > h(1,1)$, (2) nor is it monotone decreasing in $x$ since $h(0,0) < h(1,0)$.

Locally monotone functions are called also unate functions.


I think that the gap is at most exponential, and this follows from a simple duality argument. (My original answer used the upper bound theorem: thanks to Emil Jeřábek for pointing out that this is completely unnecessary.)

Let $K$ be a polytope with $m$ facets in $d$-dimensional space ($d \le m-1$), whose orthogonal projection on some subspace $W$ of dimension $k$ is the polytope $L$ with $n$ facets. Without loss of generality, we can assume that $K$ and $L$ contain the origin $0$. Let $K^\circ = \{y: \langle y, x \rangle \le 1 \ \ \forall x \in K\}$ be the polar (dual) polytope to $K$. The vertices of $K^\circ$ are exactly the normal vectors to the facets of $K$, so $K^\circ$ has $m$ vertices. Then
$$L = \{x: \langle y, x \rangle \le 1 \ \ \forall y \in K^\circ \cap W\},$$
and the vertices of $K^\circ \cap W$ are exactly the normals to the $n$ facets of $L$. (In other words, $L^\circ = K^\circ \cap W$.) Every $(d-k)$-dimensional face of $K^\circ$, when intersected with $W$, gives at most one vertex of $K^\circ \cap W$, so, $n \le f_{d-k}(K^\circ)$, where the right hand side is the number of $(d-k)$-dimensional faces of $K^\circ$. Since any face of $K^\circ$ is the convex hull of the set of vertices it contains, so it is uniquely determined by them, we have $f_{d-k}(K^\circ) \le 2^m$. So, an upper bound is $n \le 2^{m}$, i.e. the extension complexity of a polytope with $n$ facets is at least $\lceil\log_2(n)\rceil$.


In homotopy type theory, is there a IsManifold predicate?

I'm afraid I don't have a clear answer to your question. As I imagine you know, the basic definition of being a manifold cannot even be formulated in HoTT, since it crucially relies on the topology of the space in question, which does not exist for every type!

The primitive notion in HoTT is that of the path space $I_X$ of a type $X$. But, as far as I know, this does not in general define a topology over $X$, which is required in the usual definition of manifolds.

Another point is the property vs structure problem that seems to underly your question. It is certainly possible to define a manifold structure over a type: a manifold is a tuple $(X, T, A)$ where $X$ is a type, $T$ is a topology over $X$, and $A$ is an atlas, etc.

Given such a structure (which may include proofs of the various properties that underlie the structure), you can of course ask whether it is homotopy equivalent to another $Y$, as a homotopy type. This means that being a manifold is first defined as being a structure, and only then can you ask the question whether another type has the property of being homotopy equivalent to some manifold.

This is just what you do in "ordinary" math though, and doesn't seem to nicely use the synthetic properties of HoTT. As far as I can tell, the machinery required to talk about manifolds in a synthetic way is still being worked out, and certainly hasn't been well explored yet in any of the current (semi-)implementations of HoTT. This is an exiting avenue of research though. It seems to be structural, and thus requires adding constructs to "ordinary" HoTT.

The most notable proponent of this approach is Urs Shreiber (though Mike Shulman certainly is a close second, and might be able to give a more informed answer), and some pointers can be found here and here (n-Cat Lab).


It is not $O(n)$ unless $k=3$. For $k$ even, the maximum length of a cycle in the complete bipartite graph $K_{n,k/2}$ is $k$, and the number of length-$k$ cycles is $(\frac{k}{2}-1)! n^{k/2}=\Theta(n^{k/2})$. For instance, $K_{2,n}$ has a quadratic number of 4-cycles, but no cycles longer than 4.

On the other hand, for any constant bound $k$ on the length of the longest cycle, the number of triangles really is $O(n)$. Here's a quick proof: in a depth first search tree, each edge goes from the lower of its two endpoints to an ancestor at most $k-1$ steps back, so any leaf of the tree has degree at most $k-1$ and belongs to at most $\binom{k-1}{2}$ triangles. Now remove the leaf and induct.


Fast convolution over small finite fields

A recent paper by Alexey Pospelov appears to give the state of the art.  (It isn't the first to achieve the bounds I'll quote, but it achieves them in a unified way for arbitrary fields, and equally importantly, it states the bounds clearly, see p. 3.)

$\bullet$ We can multiply two degree-$n$ polynomials over an arbitrary field $\mathbb{F}$ using $O(n \log n)$ multiplications in $\mathbb{F}$ and $O(n \log n \log \log n)$ additions in $\mathbb{F}$.  This is originally due to Schonhage-Strassen (for char. $\neq 2$) and Schonhage for char. 2.  As I mentioned, this implies the same bounds for cyclic convolution.  Pospelov also states,
"We are currently not aware of any algorithms with an upper bound of [the above] that are not based on consecutive DFT applications..."

$\bullet$ Cantor and Kaltofen generalized these results, showing the bounds hold for arbitrary algebras (not just fields).

$\bullet$ If $\mathbb{F}$ supports Discrete Fourier Transform of appropriate order, that is, if $\mathbb{F}$ has a primitive $N$-th root of unity where $N$ is large enough (I believe $N = O(n)$ suffices) and $N$ is a power of 2 or 3, then we can do polynomial multiplication with $O(n)$ multiplications and $O(n \log n)$ additions.  Various other improvements are possible for fields with other special properties.

$\bullet$ It seems to be plausible, but unknown, whether Furer's recent improvement in integer multiplication (reproved in a different way by De et al.) can help lead to faster polynomial multiplication algorithms, over finite fields say.  Can anyone comment?

Todd Mateer's thesis also seems like an excellent resource to understand the FFT literature and applications to polynomial multiplication (thanks Jug!); but you have to dig more to find what you're looking for.


Lower bound on the worst-case unbiased coin flips to sample a distribution?

Fix such a distribution, and an element $k$ showing its non-triviality. In particular, $\Pr[X=k]= (2m+1)/2^p$ for some integer $m$.

Suppose by contradiction you have an algorithm A to sample from the distribution given $p-1$ i.i.d. unbiased bits. Such an algorithm is, given the realization of the coins, deterministic: i.e., it is equivalent to a partition of the leaves of the complete binary tree of height $p-1$, each output $x$ corresponding to a different set $S_x$ in the partition.

As such, since all leaves have probability $1/2^{p-1}$, any output $x$ has probability $|S_x|/2^{p-1}$, i.e., of the form $2\ell/2^p$ for some integer $\ell$. That cannot be equal to $(2m+1)/2^p$.


Computing the Löwner-John ellipsoid of a polyhedron

According to Boyd, it's NP-hard: http://youtu.be/mNzu42FrlHo?t=41m3s


How small can be a layered boolean circuit for a function with circuit complexity $s$?

As far as I know, three classes of layered circuits have been studied. In all of these definitions arcs are allowed only between two adjacent layers.

A circuit is called synchronous (Harper 1977) if all gates are arranged into layers, and inputs must be at the layer 0. (An equivalent definition: for any gate $g$, all paths from the inputs to $g$ have the same length.)
A circuit is locally synchronous (Belaga 1984) if each input occurs exactly once but at an arbitrary layer.
A circuit is layered (Gál, Jang 2010) if gates and inputs are arranged into layers, inputs can occur multiple times at different layers. (An equivalent definition: for any  gate $g$ and output gate $o$, all directed paths from $g$ to $o$ have the same length.)

It is easy to see that the three classes are listed from the weakest to the strongest (and the class of unrestricted circuits is even stronger).

Regarding the size of a layered circuit computing an unrestricted circuit of size $s$ we know the following:

Any circuit of size $s$ can be computed by a synchronous/locally synchronous/layered circuit of size $s^2$ (Wegener 1987, Section 12.1).
It should be hard to find an explicit function which requires a synchronous/locally synchronous/layered circuit of size $\omega(s\log{s})$. Indeed, every circuit of size $s$ and depth $d$ can be computed by a synchronous circuit of size $O(sd)$ (Wegener 1987, Section 12.1). Thus, even if we have an explicit function $f$ which requires synchronous circuits of size $\omega(n\log{n})$ (regardless of its complexity in the class of unrestricted circuits), then $f$ cannot be computed by a circuit of depth $O(\log{n})$ and size $O(n)$, which answers a long-standing open question in circuit complexity (Valiant 1977).
There exist explicit functions

3.1. with $\Omega(n\log{n})$ lower bound for synchronous circuits but $O(n)$ upper bound for locally synchronous circuits (Turán 1989).

3.2. with $\Omega(n\log{n})$ lower bound for locally synchronous circuits but $O(n)$ upper bound for layered circuits (Turán 1989).

It is important to note that these two separation results by Turán are proven for functions with one output. It is often much easier to find a function with $n$ outputs which separates two such classes.

As an example, consider the function $f\colon\{0,1\}^n\to\{0,1\}^n$ where the $i$th output bit is an XOR of all inputs except for the $i$th one. This function can easily be computed by a layered circuit of size $O(n)$: First compute an XOR of all inputs in $\log{n}$ layers of total size $n$, then compute all outputs in one layer of size $n$. On the other hand, $f$ requires synchronous circuits of size $\Omega(n\log{n})$. Indeed, in order to compute a parity of length $n-1$, the circuit depth must be at least $\Omega(\log{n})$. On the other hand, each layer must transmit $n$ bits of information, thus its size must be at least $n$.


Would a proof assuming a physical law be considered sufficient?

It seems at least possible to me, but currently very unlikely. To sum up the below, it's because the current mathematical statement of (say) P vs NP is completely independent of any laws of physics, so one would need to describe new models of computation that do depend on physics axioms.

The key point that Peter Shor made in his comment is that CS theory questions, such as P vs NP, refer to very simple and stylized mathematical models. They aren't statements about the real world. They just say "in this mathematical model, ___ is true".

Now, one does often have empirical laws, such as the Church-Turing thesis, that state that the real world acts like these mathematical models. But that's a one-way connection (it doesn't mean that mathematical models must act like the real world!). To flesh out Peter Shor's example, the Pythagorean theorem only needs the ideas of real numbers and the Euclidean plane/distance. The model is much simpler than the real world and doesn't involve e.g. gravity, electromagnetism, thermodynamics, etc. And even if the Pythagorean theorem were sometimes false in reality because of these complications, this would not affect its mathematical truth.

Similarly, the model for the Turing machine and the definitions of P, NP, etc are much simpler than the real world. The model does not involve things like gravity, thermodynamic entropy, etc. The truth of P vs. NP does not depend on whether computation can actually happen efficiently in the real world.

Now, it seems to me hypothetically possible that in the future, we could discover closer connections between laws of physics and laws of computation. What would happen then is that the mathematical model of the Turing Machine would have to be expanded to account for these connections. One would then have to formulate new definitions of P and NP for this new model and argue that these are "better" than the old model and definitions. Then, in this new physics-aware model, one could have physics axioms that are used in proofs. But this seems very unlikely / far from happening, at least to me.


Interactive proofs for levels of the polynomial hierarchy

Even for giving an IP for coNP, using current techniques, one needs to arithmetize, i.e. use counting, which means essentially the full power of #P.  Any weaker prover even for coNP would be very interesting, I think (in particular would imply a new non relativing technique.)


Is there a name for a hashtable with a tree for each bin instead of a list?

Yes, there is a name for it: Hashtable.

You can have whatever you want for collision bins: Lists, trees, hashtables, whatever you fancy.


Your problem is NP-complete.
Take an instance $G'=(V',E')$ of the (NP-complete) max-cut problem. Let $m=|E'|$.

Create two new vertices $x_1$ and $x_2$, create the edge between $x_1$ and $x_2$, and all edges between $V'$ and $\{x_1,x_2\}$.
The edge $[x_1,x_2]$ receives positive weight $1000m$
All edges $[x_i,v]$ with $i=1,2$ and $v\in V'$ receive negative weight $-2m$
All edges in $E'$ receive positive weight $1$

It can be easily seen that your optimal coloring for this graph

assigns two distinct colors to $x_1$ and $x_2$ (say color 1 to $x_1$ and color 2 to $x_2$)
and colors every vertex $v\in V'$ with one of these colors 1 or 2

Hence, the two-coloring on $V'$ induces a max-cut in $G'$.


Quantum Fourier Transform question regarding measurement

In fact the QFT and the DFT are very different. In the DFT we have $N$ complex values stored in several bits per value, which could be called the standard coefficients of this vector in $\mathbb C^N$, and the Fourier transform produces the Fourier coefficients, which are the coefficients of the same vector in a different basis. In this case the coefficients are stored with finite precision and in general precision will be lost in the change of basis.

The QFT is not the same algorithm implemented with quantum gates; in fact the whole encoding of the state changes. The coefficients are not encoded in qubits: if $N = 2^n$ we now need only $n$ qubits to hold the data, and the coefficients of our element of $\mathbb C^N$ are encoded as the coefficients of the general entangled state of these $n$ qubits together (so we have the restriction that they have to sum 1). In theory no precision is lost in the transform.

As you already remarked, the Fourier coefficients encoded in this way are not accessible to us, and indeed I don't see either how it would be useful to compute a product (I assume you meant product rather than sum) of two polynomials (I am not saying it is not useful for that, just that I don't see how).

If you want to make use of the QFT, it has to be in applications where you are not necessarily interested in the values of all coefficients; e.g. in Shor's algorithm for factoring (or rather period finding) you start out with a (long) periodic sequence of coefficients, and its Fourier transform (possibly after collapsing it to a vector that is 0 everywhere except at some regularly spaced coefficients) will have most coefficients close to 0 but some that are high (and exactly 0 when the period is a divisor of the number of coefficients). You cannot read out the values of the coefficients, but if you look at the qubits (i.e. you measure their values), you will most likely see one of the high coefficients. That gives you a lot of information about the period.

I hope this is (related to) what you  were asking.


Can a natural graph problem be universally hard?

The definition of "natural" is a bit fuzzy, but there's a trivial reason the answer here is likely "no". Suppose to the contrary that there is such a problem, $P$. If $P$ only acts on the first component of the provided graph, then $P$ is easy on the class of graphs where the first component is an instance of $P$ and the second component encodes a certificate of $P$ holding on the first component. Further, this class of graphs is polytime recognizable. Indeed, the same holds true if we can designate a portion of the graph as a "this is a certificate and not part of the problem component", in the sense that we can sneak this certificate in without affecting the true answer.

Most "natural" problems, as far as I can tell, allow for the designation of such a piece of the graph. Here are a few examples

Max Clique: just ensure that the certificate portion of the graph does not have a large clique (eg. encode it using a matching)
Hamiltonian Path: the tail node is replaced by a certificate graph which has an easy-to-find Hamiltonian path of its own
Hamiltonian Circuit: same as Hamiltonian path except some designated vertex is replaced with a certificate graph containing a Hamiltonian cycle
Max Cut: this doesn't affect the solution as long as there are no edges to the rest of the graph, so we just ensure that the max cut here is easy to find (eg. we encode using a matching)
Vertex cover: the certificate is again encoded by a matching

We ensure that the certificate portion of the graph is designated as such, so to not lose it in the rest of the graph (though designating them implicitly via the graph structure is probably easy enough for most "natural" problems).

Since NP-complete problems cannot be sparse unless $P=NP$ (Mahaney's theorem), neither can this construction, satisfying your non-triviality constraint.


Many search problems in artificial intelligence (such as searching the game tree of a chess game, or searching for solutions to puzzles like the Rubik's cube, or more generally searching for sequences of actions to perform in order to accomplish some desired goal) are, in effect, algorithms on infinite graphs, even though the desired answer is a finite path. It is certainly possible to perform algorithms on such graphs, if they are represented implicitly.

But it is also true that mathematics may be useful even if it is not the mathematics of problems that can be solved by algorithms. Infinite graphs can be used to model birth and death processes (e.g. how do our rules for inheritance of names, and the rates at which people are born and die, lead to nonuniform distributions of family names among different human cultures?), to give a framework for approaching questions about mathematical symmetries (via Cayley graphs, which are often infinite), to provide models for reasoning about systems of logic (see Rado graph and saturated model), etc.


Complexity of computing generalised determinants. (P - #P transition)

I extend my comment in an answer.

By rewriting $e^{i \cdot sgn(\mu)\theta} = \cos(sgn(\mu)\theta)+i\sin(sgn(\mu)\theta) = \cos(\theta)+i \cdot sgn(\mu)\sin(\theta)$ we have: $Det_\theta(A) = \cos(\theta)Perm(A)+i\sin(\theta)Det(A)$. Thus, if $\cos(\theta) \neq 0$, we have $Perm(A) = (Det_\theta(A)-i\sin(\theta)Det(A))/\cos(\theta)$, meaning that $Det_\theta$ is $\#P$-hard (and $VNP$-complete over $\mathbb{C}$).

Several generalizations of the determinant have been studied however. Peter Bürgisser studies the complexity of immanants in his Habilitationschrift "Completeness and Reduction in Algebraic Complexity Theory" (http://math-www.uni-paderborn.de/agpb/work/habil.ps). Nicolas de Rugy-Altherre studied the complexity of one of them, the Fermionant, and proves other $VNP$-completeness results for such functions in "Determinant versus Permanent: salvation via generalization? The algebraic complexity of the Fermionant and the Immanant", https://arxiv.org/abs/1309.2156.

Hyperdeterminants (https://en.wikipedia.org/wiki/Hyperdeterminant) is a generalization of determinants to tensors. See "New algorithms for linear k-matroid intersection and matroid k-parity problems" by A. Barvinok for identities and algorithms on hyperdeterminants.


Can recursion be replaced with a finite set of higher-order functions?

You may replace recursion with computation of fixed points, so all you need is a fixed-point operator

fix : (a -> a) -> a

which satisfies

fix f = f (fix f)

Then, given a recursive definition of f : a -> b,

f = Φ(f)

we may define f as

f = fix (λg.Φ(g))

Here fix has type ((a -> b) -> (a -> b)) -> (a -> b).

You may consider this to be cheating, but the question is not really research-level precisely because the connection between recursion and fixed points is a basic piece of knowledge. I am guessing that maybe you did not know about the connection.


Making an adjacency matrix positive semidefinite

Your question is too imprecise.  What does it mean to "transform a matrix"?  Are you asking whether there is an algorithm that takes as input a symmetric matrix and finds the minimal total weight that can be added to diagonal entries so as to make the new matrix positive semi-definite?

If this is your question, the answer is yes, since it is an SDP.  If you restrict to adding integer values to diagonal elements ("self loops"), then I do not know the complexity of finding the minimum number of self loops needed.

You might want to look into Gershgorin's circle theorem if you are trying to do this by hand.


Surprising Results in Complexity (Not on the Complexity Blog List)

Here is the guest post by Bill Gasarch with help from Harry Lewis and Richard Ladner:
http://blog.computationalcomplexity.org/2005/12/surprising-results.html


Have you seen Arthur Charguéraud's PhD thesis, Characteristic Formulae for Mechanized Program Verification?

Rather than building the type system and small-step semantics as inductive relations, he gives a technique for converting Caml programs into characteristic formulas. This are basically a generalization of predicate transformer semantics to support a very large subset of Ocaml -- notably, including unsafe casts like Obj.magic. To quote from his thesis:

  I have focused on a subset of the OCaml programming lan-
  guage, which is a sequential, call-by-value, high-level programming language. The
  current implementation of CFML supports the core λ-calculus, including higher-
  order functions, recursion, mutual recursion and polymorphic recursion. It supports
  tuples, data constructors, pattern matching, reference cells, records and arrays. I
  provide an additional Caml library that adds support for null pointers and strong
  updates.

It's a very appealing approach if you want to prove a particular Caml program correct (less so if you are interested in its metatheory, though).


What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem?

I believe that some version of this connection can be tied back to Turing's seminal paper on computability.

Namely, Turing makes the following two claims:

"The results of Section 8 have some important applications. In particular, they can  be used  to  show that  the  Hilbert Entscheidungsproblem can  have no solution."
"If the negation of what Godel has shown had been proved, i.e. if, for each $U$ either $U$ or $\neg U$ is provable, then  we should have an immediate solution of the Entscheidungsproblem."

The conclusion, I believe, follows from Modus Tollens.


Splitting a graph into minimum number of subpaths

Your problem (as stated) seems to be NP-hard.  Here is a reduction from Partition.

Given an instance of Partition (a collection $x_1,\ldots,x_n$ of positive integers), construct a graph with $n+1$ vertices $v_1,\ldots,v_{n+1}$ and, for each $i$, two edges from $v_i$ to $v_{i+1}$: one of cost zero, one of cost $x_i$.

Suppose the Partition instance is satisfiable. That is, there is a subset $S$ of $[n]$ such that $\sum_{i\in S} x_i = \sum_{i} x_i/2$.  Then there are two paths that together cover all the edges, with each path costing $L=\sum_{i} x_i/2$.

Conversely, if there are two paths each of cost at most $L$ (that cover all the edges), the two paths together must cover each $x_i$ exactly once, and the total weight on each must be exactly $L$. So there must be a subset $S$ such that $\sum_{i\in S} x_i = \sum_i x_i/2$.  That is, the Partition instance is satisfiable.

Perhaps you have further restrictions (e.g. polynomially bounded integer edge weights)?


Distributed file storage system - theoretical approaches

A simple approach to achieve reliability and fast lookup in a "well connected" network $G$ is to replicate each file $f$ on a set $V_f$ of $\Theta(\sqrt{n}\log n)$ nodes and use random walks to efficiently find members of $V_f$.

When searching for a file $f$, we start $c\sqrt{n}\in \Theta(\sqrt{n})$ random walks of length $\tau$ from some particular node, where $\tau$ is the mixing time of a random walk on $G$. That is, after taking $\tau$ steps, a random walk has probability in $[1/2n,3/2n]$ of being at any particular node in $G$.
Even if some $\epsilon\sqrt{n}\log n$ (for some small $\epsilon>0$) nodes have failed, the probability that at least one of these random walks encounters a node in $V_f$ is at least $$1-\left(1-\frac{\log n}{2\sqrt{n}}\right)^{c\sqrt{n}} \approx 1-\frac{1}{n^{c'}},$$
where $c'$ is a constant $>2$. Of course, this approach only makes sense if $\tau$ is sufficiently small - that's what I meant above when saying "well connected" network. This is the case in networks with sufficiently large (i.e. constant) spectral gap since $\tau \in O(\log n)$. A similar approach is taken in [1].

After some time, most of the $\Theta(\sqrt{n}\log n)$ could have been removed. Thus it is necessary to estimate the current size of $V_f$ periodically and replenish the removed members of $V_f$ by replicating $f$ on new nodes.

[1] Ruggero, Bhattacharjee, Srinivasan, Marsh.
 Efficient lookup on unstructured topologies.


What are the algorithms and the data structures for GUIs and input management?

I'll first restate your question, and then try to answer it. As I understand it, the question you are trying to answer is, "if I have a scene graph/widget tree, and I get an event, how can I figure out how to dispatch that event to the appropriate subnodes of the tree?"

The answer is that the data structures you have outlined are not sufficient by themselves to do the job; you need a bit more information.

The primitive events the OS produces tell you the positions of the mouse, and the scene graph gives you a logical decomposition of the structure of the GUI. Therefore, you need some additional data structures to translate between the widget tree and what it looks like geometrically.

The simplest case is when every widget is an axis-aligned rectangle. What you do then is:

Every widget node stores its position and shape.
In addition to the widget tree, you keep  a separate doubly-linked list storing all of the clickable widgets in their z-order, so that the widget which is visually "on top" is at the head of the list.
You also keep track of the current mouse position (you have to do this anyway, because the OS only gives you relative position changes).

When an event occurs, what you do is:

When an event occurs you iterate through the z-order list, doing a simple hit test for the bounding box of each widget.
The first time the hit test succeeds, you know where the event occurred, and can do event dispatch.

With fancier graphics geometry (say with vector graphics), each widget will store a data structure representing the shape, and your hit test gets more complicated to match. The things to Google for:

"collision detection" or "hit detection".
"spatial indices" -- often these data structures are variants of quadtrees and the like. It really does work pretty well, even though the geometric data can be quite large, because user events are generally relatively infrequent.


Yes, people have looked at this and related groups, though not a whole lot as far as I can tell. For example:

Morozov, A. S. Turing reducibility as algebraic embeddability. Siberian Math. J. 38 (1997), no. 2, 312–313. Let $G_d$ denote the group of permutations of $\mathbb{N}$ computable below the Turing degree $d$. Morozov shows that $d_1 \leq_{T} d_2$ if and only if $G_{d_1} \hookrightarrow G_{d_2}$. (Note that a permutation and its inverse always have the same Turing degree. This no longer holds if we restrict to primitive recursive or poly-time reductions.)

Kent, C. F. Constructive analogues of the group of permutations of the natural numbers. Trans. Amer. Math. Soc. 104 (1962) 347–362.

In fact, if I recall correctly, the primitive recursive permutations generate the group of all computable permutations. (If you restrict attention to the group of permutations $\pi$ such that both $\pi$ and $\pi^{-1}$ are primitive recursive, you get a smaller group.) Furthermore, every computable permutation can be written as a word of length six in the primitive recursive permutations and their inverses. I think the same result holds if you replace "primitive recursive" by "polynomial time." [I don't recall the reference just now, but I have a physical copy of the paper at home. I will post the reference when I return from traveling.]

Slightly different but related:

Combarro, E. F. Classification of subsets of natural numbers by computable permutations. Siberian Math. J. 45 (2004), no. 1, 125–135.

The group of computable permutations is not finitely generated (Is that what you meant by "Are there generators to this group?" Every group has generators, for example, the entire group...). If it were, then there would be a c.e. set $I$ of indices such that the set $\{\varphi_i : i \in I\}$ was exactly the set of computable permutations (where $\varphi_i$ is the $i$-th computable function in some acceptable enumeration). It then takes a little argument to show that this cannot happen (start from the fact that the set of all indices of computable permutations is $\Pi^0_2$-complete).


Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

I think it is "easy" to come up with an assumption that implies one but not necessarily the other... (just write down a condition that is equivalent to P=ZPP)... however, a "natural" and non-uniform assumption (e.g. some weak form of PRG) seems harder, since (for example) hitting set generators (the non-uniform thing you need for P=RP) imply pseudorandom generators (what you need for P=BPP).

Just to give an idea of how annoying the problem is, here is a "natural" non-uniform condition that implies P=ZPP but (oops) also implies hitting sets, so it also implies P=BPP.

Say a circuit pair $(C,C')$ is good for length $n$ if $C$ and $C'$ have the same number of inputs, and for every input $x$ of length $n$,

$(Pr_y[C(x,y)=1]>2/3 \wedge Pr_y[C'(x,y)=0]=1)$ XOR $(Pr_y[C'(x,y)=1]>2/3 \wedge Pr_y[C(x,y)=0]=1)$.

Intuitively, these pairs can model any $RP \cap coRP = ZPP$ function.

To prove $P=ZPP$, it would suffice to have for all $\epsilon > 0$, a polynomial time function which given $1^n$, prints a set $S$ of $poly(n)$ strings of length up to $n$ such that for all circuit pairs $(C,C')$ with size $n$ that are good for length $m=n^{\epsilon}$, and all $x$ of length $m$, $(\exists y \in S)[C(x,y)=1 \vee C'(x,y)=1]$. (This should suffice, since by definition of "good", for all $x$, it cannot be that both $C$ and $C'$ have some input $y$ making them accept. I set $m=n^{\epsilon}$ to keep the condition from being too strong for other reasons.)

The main point is that the hitting set $S$ above "only" has to work for good circuit pairs. Nevertheless, this constraint isn't enough to keep from getting a full hitting set. Consider any circuit $C$ with $\Pr_x[C(x)=1]>2/3$. Write the inputs of $C$ over "$y$-variables" instead of $x$-variables. Look at the circuit pair $(0,C)$, where $0$ is the circuit which outputs zero on all inputs $(x,y)$. This pair trivially satisfies the goodness condition ($C$ and $0$ have the same behavior on all inputs $x$, because they do not depend on $x$ at all). And if there is always an $a \in S$ such that $[C(x,a)=1 \vee 0(x,a) = 1]$ is true, then $S$ is just a hitting set.

You could try to require some "non-trivialness" condition on top of that (say that each circuit in the pair can't be trivial), but the patches I can think of could also be circumvented.

It would be interesting if there is a more general way to formalize this problem, so that one could convincingly show that any hitting set for anything resembling "ZPP circuits" is just a hitting set.


Longest path in Complete Directed Graphs

Sage's implementation of it for instance :-)

http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.longest_path

Nathann


Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?

Here are some examples of problems which I believe have a reasonable claim of being "natural" (at least, they can be stated concisely) which (when phrased as decision problems) do not appear to be known in P nor known NP-complete. So if you want a dichotomy theorem you either need to be more precise about what you mean by "natural" in a way that excludes examples like these, or you need to look for more precisely defined subclasses of the natural problems (e.g. MSO formulas with the second-order quantification restricted to be existential and outside everything else) for which there might be more hope of a dichotomy.

I've made this community wiki because I think it could be a large list.

Are there evenly many 3-edge-colorings? (Should be $\oplus P$-complete)
Who wins at strings-and-coins? (Might be PSPACE-complete)
What is its list coloring or list edge coloring number? (Might be $\Pi^p_2$-complete)
Is it a unit disk graph? A unit distance graph? (Might be $\exists \mathbb{R}$-complete)
Given two cubic Halin graphs with the same labeled outer face, how few steps does it take to convert one to the other by alternatingly contracting an interior edge and then uncontracting it the other way? (Equivalent to the open problem of computing rotation distance on binary search trees; might also be interesting for broader classes of cubic graphs)


Determining the Class of a given Cellular Automata structure

No. See

Culik, Karel, II; Yu, Sheng.
Undecidability of CA classification schemes.
Complex Systems 2 (1988), no. 2, 177–190.


Constraint types (IBM/X10) compared to dependent types

As they explain in the related work section of the 2008 paper, the constraint types they describe are most closely related to refinement types. I wont give references, as there are plenty in the bibliography of the aforementioned paper, but I can give a quick overview.

Refinement types are a language that allow the expression of refinements of the values of a given type $C$: if $C$ is identified with the expressions of that type, then a refinement $R$ of $C$ is simply a subset $R\subseteq C$.

This is extremely helpful, as may allow the expression of invariants that the code needs to satisfy: say you have a type Rectangle with three fields, width, height and area. You are interested in the type in which area = width*height, which you might write:

{ x :: Rectangle | x.area == x.width*x.height)

This is useful for expressing pre and post-conditions on your code. Again, a trivial example would be the head function, which only makes sense on non-empty lists.

head :: NonEmptyList<A> -> A

In this respect, refinement types capture the notion of contracts, and are also related to axiomatic semantics or Hoare logic.

So here's the real issue: what is the language for expressing refinements? Say we authorize linear constraints, in wich we can have

n :: { x : Int | x < 2 }

and on the other hand we have a function of type

f :: { x : Int | x <= 1+1 } -> Bool

It is clear that f can safely be applied to n. However, for this to be statically verified, we need to prove the statement:
$$ x < 2 \Rightarrow x \leq 1+1$$
So this imposes a restriction on the expressivity of the refinement language: either the statements that need to be proven to verify type-safety are decidable (linear arithmetic and the theory of equality is a common choice in this case), or there need to be dynamic casts that are verified at runtime.

The traditional approach to dependent types, however, allows for arbitrarily complex constraints on types, with the following caveat: the onus of verification is placed on the programmer rather than on the compiler.

In this setting, an element of { x : Int | x < 2 } is not an integer less than 2, but a pair (n, e) where n is an integer and e is evidence that n<2 holds. Therefore the compiler only has to check the evidence at compile time, rather than building it herself.

Note however that some computational inferences can be performed, typically $1+1$ can be seen to be identical to $2$ (but $x<2$ can not be seen to imply $x\leq 2$ without some contribution from the user).

The obvious advantage is that arbitrarily complex constraints on the code can be verified, and the programmer may have access to automatic tools to assist the production of the required evidence (the famous "tactic language" of Coq is an example of this).

This is the main difference between refinement types and dependent types. The Haskell extensions tend to be in the second category, where evidence has to be provided by the programmer.

I do need to qualify all this: there is no hard line which differentiates refinement types from dependent types; in dependent types there may be a significant amount of information inferred by the compiler, and systems with refinement types may require information to be supplied by the developer. In fact the interaction between the communities contains IMHO some of the most interesting developments of type theory applied to practical software engineering.


Most of the patterns in my collection at http://www.ics.uci.edu/~eppstein/ca/replicators/ were found with a somewhat different heuristic search process, that was intended to find puffers but also turns out to work for replicators:

Pick a small random seed pattern
Simulate a moderate number of steps of a modified version of the cellular automaton rule, starting with that seed. The modification is: if you find a small enough set of live cells, separated by far enough from the rest of the pattern, delete them.
If the simulation finds two states that have the same pattern of cells (but possibly shifted with respect to each other), check it against a collection of known repetitions and shifts and, if it seems new, report it. See https://en.wikipedia.org/wiki/Cycle_detection for efficient methods of finding repeated patterns that don't involve testing all against all.

Many replicators eventually reach a state with just two copies of the replicator far from each other, after which the modification to the rule deletes one of them and you get a repetition.


On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$

You can check the following paper:

Translational lemmas, polynomial time, and $ (\log n)^j$-space by Ronald V. Book (1976).

Figures 1 and 2 in the paper give the summary of what is known and what is unknown.

I put Theorem 3.10 in the paper here:

$ DTIME(poly(n)) \neq DSPACE(poly(\log n)) $;
for every $ j \geq 1 $, $ DTIME(n^j) \neq DSPACE(poly(\log n)) $;
for every $ j,k \geq 1 $, $ DTIME(n^j) \neq DSPACE( (\log n)^k ) $.


What's new in compiler optimization techniques over last few years?

I'm not sure how novel it is, or if it's too much on the applied side for your interest, but Hoopl shows how a control/data flow optimization can be modularised, with propagation of facts about control-graph vertices being independent of the language and specific optimization.

They reference a 2002 algorithm of Lerner, Grove and Chambers which composes simple optimizations into a "superoptimization".


What is the relationship between intuitionistic logic, combinatory logic and lambda calculus?

I don't understand exactly what you are looking for, I'll try to explain the Curry-Howard correspondence in a nutshell, you'll let me know if it helps.

The Curry-Howard correspondence (or isomorphism, if you wish) definitely links the three objects you mention: it actually tells that two of them, IL and $\lambda$c, are the same thing.  The term is used today in a broad sense and often without referring to a specific technical statement, but it can be formulated precisely in at least two frameworks:

Hilbert-style deduction for intuitionistic logic and SK combinators;
Gentzen's natural deduction and the $\lambda$-calculus.

The first is actually the "original" correspondence, dating back to the late 50s when Curry observed that the types you would give to the SK combinators
$$
\begin{align*}
S &:(A\rightarrow B\rightarrow C)\rightarrow(A\rightarrow B)\rightarrow A\rightarrow C \\
K &:A\rightarrow B\rightarrow A
\end{align*}
$$
are exactly the axioms of implicational propositional intuitionistic logic in Hilbert-style deduction.  Note that this latter has only modus ponens as a rule for building proofs; accordingly, terms in combinatory logic are built using only application.

That's it for the combinatory logic side.  It took another decade before Howard fully formulated the correspondence in the second guise, which I think looks best:

on the logical side, you have $\mathbf{NJ}^{\Rightarrow,\land}$, Gentzen's natural deduction system for the negative fragment of propositional intuitionistic logic. You have propositional formulas defined by $A,B::=\alpha\mathrel{|} A\Rightarrow B\mathrel{|} A\land B$ (atom, implication and conjunction), proofs built from introduction and elimination rules for each connective, and you have proof normalization, which consists in 2 rewriting rules replacing what Prawitz calls "detours" (an introduction of a connective immediately followed by its elimination) with more explicit pieces of proof. This rewriting procedure closely corresponds to cut-elimination in sequent calculus, also introduced by Gentzen.
On the computational side, you have the simply-typed $\lambda$-calculus $\Lambda^{\rightarrow,\times}$, with types defined by $T,U::=o\mathrel{|}T\rightarrow U\mathrel{|} T\times U$ (base, function space and pairs), terms built from constructors ($\lambda$ for $\rightarrow$ and pairing for $\times$) and destructors (application for $\rightarrow$ and projections for $\times$), and $\beta$-reduction, which consists of 2 rewriting rules: the usual one and one for handling projections acting on a pair.

The Curry-Howard correspondence, which is the subject of the book you are reading, has three levels:

formulas = types: just change the notation swapping $\alpha/o$, $\Rightarrow/\rightarrow$ and $\land/\times$;
proofs = terms: more precisely, introduction rule=constructor, elimination rule=destructor;
normalization = reduction: this is harder to write inline, but it's obvious once you write the rewriting rules of the two systems side by side. The correspondence is one-to-one, i.e., one step in $\mathbf{NJ}^{\Rightarrow,\land}$ corresponds to exactly one step in $\Lambda^{\rightarrow,\times}$ and vice versa.

At this level, I hesitate to call this an "isomorphism" because it is not entirely clear what structures are being preserved.  Here's where category theory may be of help: if you formulate $\mathbf{NJ}^{\Rightarrow,\land}$ and $\Lambda^{\rightarrow,\times}$ as categories (without being too precise: formulas/types as objects and normal proofs/normal terms as morphisms), then they are isomorphic as Cartesian-closed categories (CCC). Indeed, as I defined them, they both are the free CCC on one object ($\alpha$ if you are a logician or $o$ if you are a computer scientist).  So, there you go, you now have a third object into the picture and you get what Robert Harper calls the Holy Trinity (logic, programming languages and categories).

Actually, the above categorical view hides a bit what I think is the most important aspect of the Curry-Howard correspondence, which is normalization = reduction.  Somewhat annoyingly, this is left out in current alternative terminologies for the correspondence: people say "proofs as programs" or "formulae as types", nobody says "cut-elimination as computation".  To properly accommodate the third level, you'd have to climb a bit up on the higher-dimensional ladder and make $\mathbf{NJ}^{\Rightarrow,\land}$ and $\Lambda^{\rightarrow,\times}$ into 2-categories, or even more (things make sense up to dimension 3 at least).

If you're looking for concrete examples, the above framework isn't very rich but already gives you an idea.  Take the second-order definition of natural number: $$\mathsf{Nat}(x):=\forall\alpha.(\forall y.\alpha(y)\Rightarrow\alpha(\mathsf{s}y))\Rightarrow\alpha(0)\Rightarrow\alpha(x)$$
($x$ is an integer if it satisfies every property $\alpha$ which is true for $0$ and is true for $y+1$ as soon as it is true for $y$). Now, erase all first-order information and second-order quantification.  You get
$$(\alpha\Rightarrow\alpha)\Rightarrow\alpha\Rightarrow\alpha$$
Translated in types, this is
$$\mathsf{N}:=(o\rightarrow o)\rightarrow o\rightarrow o.$$
Guess who are the normal forms of type $\mathsf N$?  Exactly the (typed version of the) Church numerals.  So every term $\mathsf{N}\rightarrow\mathsf{N}$ is a function on integers.  If you keep the first and second order information, you get much more.  For instance, the proof in second-order Peano arithmetic that addition is total, i.e., that
$$\vdash\forall x.\forall y.\mathsf{Nat}(x)\land\mathsf{Nat}(y)\Rightarrow\mathsf{Nat}(x+y)$$
gives you a $\lambda$-term of type $\mathsf{N}\times\mathsf{N}\rightarrow\mathsf{N}$. Guess what functions it computes? Well, addition, of course (see Krivine's book "Lambda-calculus: Types and Models"). Cool, isn't it?

Another classical source to learn about Curry-Howard is Girard, Lafont and Taylor's book "Proofs and Types" (but you may already know that, it's in the bibliography of the book you are reading).


Resources (books, etc) to learn about concurrency theory

There are not that many books on this subject, as it continues to evolve at a rapid pace.

Classic books on process calculi (that don't focus on π-calculus-like mobility) are:

C. A. R. Hoare, Communicating Sequential Processes.
A. W. Roscoe, The Theory and Practice of Concurrency.
M. C. B. Hennessy, Algebraic Theory of Processes.
R. Milner, Concurrency and Communication.

There are two main books on π-calculus:

R. Milner, Communicating and Mobile Systems: The Pi Calculus.
D. Sangiorgi, D. Walker, The Pi-Calculus: A Theory of Mobile Processes.

The Sangiorgi/Walker book is not easy reading. The others books above can be used by a learner.

All of the books above are (mostly) about untyped processes. There is a single book on types for interactive processes (from June 2017).

S. Gay, A. Ravara, Behavioural Types: from Theory to Tools.

Regarding recommendations, that would depend on your background and specific goals. The Milner and Hoare books should be easy to access. After those you can read the original papers.


Is square removal easier than factoring?

We can show that if all $\alpha_i$ are different, then square removal and factoring of $n$ are equally hard.

It is obvious, that if we can factor $n$, we can also compute square removal of $n$.

The other direction is a bit more tricky. First compute the square removal of $n$ and let's call this $m$. From the definition it follows that $m$ divides $n$. Divide by $m$ repeatedly until we reach a number, which is not divisible by $m$, I'll call this $x$

$$x = \frac{n}{m^b}$$

Now compute $p = \frac{m}{\gcd(x, m)}$, if $p$ had more than one prime factor, those would have identical $\alpha_i$ in the original product $n$, which contradicts the assumption about all $\alpha_i$ being different, hence $p$ is a prime factor in $n$.

Knowing one prime factor in $n$ it is possible to reduce the problem to factoring a smaller $n'$, which satisfy the same criteria, so the algorithm can be repeated.

We can also show that if all $\alpha_i$ are equal, then square removal is easy. That's because $\alpha_i$ can only have logarithmic size in $n$, and every possible $\alpha_i$ can be tested by computing the $\alpha_i$th root of $n$.

However the result obtained that way will be incorrect if the $\alpha_i$ were not equal. The obtained result will be correct iff it is square free. And @joro pointed out, that no polynomial algorithm is known to decide if a number is square free.

So for some $n$ square removal and factoring is equivalent. For other $n$ square removal is easy. Telling those two cases apart appears to be hard.


How to define the formal and informal semantics of an algorithm as accurately as possible?

I don't know how you can define the informal semantics as accurately as possibly, but there does exist machinery for defining semantics that is purely, well, semantic.

Your semantics could be based on mathematical functions, relations, or domains. Indeed, the style of semantics known as Denotational Semantics builds upon these (and other) semantic notions by mapping the syntax in a compositional fashion to some semantic domain.

If you don't want syntax for your programming language, then start directly with the semantic domains (for example, those from Domain Theory). In this setting, each type in your programming language will be represented by a semantic domain and algorithms will then be functions from one type to another.


From Extractors to Pseudorandom Generators?

Salil Vadhan wrote to me that the answer to my question is known, and PRGs are equivalent to extractors.

Quoting him:

"See Proposition 21 and the discussion following it in my survey http://people.seas.harvard.edu/~salil/research/unified-icm.pdf
(There's a typo - "black-box hardness amplifier" should be "black-box PRG construction")

It says extractors are equivalent to black-box PRG constructions where you only care about the amount of advice, and not the running time, in the reduction.  Asking for bounded running time amounts to asking for extractors with "local list-decoding"."


I think the answer is no, assuming $\mathsf{P}_{\mathbb{R}} \neq \mathsf{NP}_{\mathbb{R}}$ (I believe I give a proof below, but there are enough potentially nitpicky definitional issues here that I'm being cautious about my claims).

Proof that the answer is no assuming $\mathsf{P}_\mathbb{R} \neq \mathsf{NP}_{\mathbb{R}}$: In fact, I believe the following stronger statement holds:

Lemma: For any BSS decision problem $L$ over $\mathbb{R}$, if $L$ poly-time-BSS$_{\mathbb{R}}$ reduces to a problem on integer inputs, then $L \in \mathsf{P}_\mathbb{R}$.

Proof of lemma: Suppose there were a polynomial-time BSS$_{\mathbb{R}}$ reduction from $L$ to a problem on integer inputs, given by a machine $M$. For inputs consisting of $n$ real parameters, unroll the computation of $M$ into an algebraic computation tree. There are only finitely many leaves, and the result at each leaf is a single rational function in the input parameters. In order for a rational function of real inputs to always output an integer value, it must be a constant function, and therefore not depend on the input. However, which constant function is used at each leaf can, of course, depend on the branches. However, since $M$ is a uniform machine, there can be only $O(1)$ output nodes, and thus only $O(1)$ output values. Thus $M$ can be trivially modified to in fact decide $L$ in polynomial time. QED

Now, take $L$ to be real feasibility of real polynomials. If $\mathsf{P}_{\mathbb{R}} \neq \mathsf{NP}_{\mathbb{R}}$, then $L \notin \mathsf{P}_{\mathbb{R}}$, and by the Lemma there is no reduction from $L$ to any problem on integer inputs (in particular, to real feasibility of integer polynomials).

Promise problem issue?: Another potential issue with your question is that real feasibility of integer polynomials may not be in $\mathsf{NP}_{\mathbb{R}}$, but only in its promise version. The issue here is that to verify that an input (such as the coefficient of a polynomial $f_i$) is an integer takes time that depends on the magnitude of $x$, whereas the set of instances (all instances, not just yes-instances) for an $\mathsf{NP}_{\mathbb{R}}$ decision problem should be decidable in $\mathsf{P}_\mathbb{R}$, the latter meaning that it takes polynomial time in the number of parameters, and not their magnitudes. This is, I believe, closely related to the fact that the integers are not first-order definable within the reals. (Essentially the best a BSS$_{\mathbb{R}}$-machine can do to test if an input $x$ is an integer is to compute the integer part of $x$ by computing powers of $2$ and doing "binary search." Once it's computed the integer part of $x$, it just checks whether that is equal to $x$.) So I think the probleam of real feasibility of integer equations is in $\mathsf{PromiseNP}_{\mathbb{R}}$ but probably not in $\mathsf{NP}_{\mathbb{R}}$ (or at least it seems nontrivial to prove that it is in $\mathsf{NP}_{\mathbb{R}}$).


Is sliding blocks linear space complete?

Yes, sliding blocks, Rush Hour, and many other puzzles with reversible moves are (deterministic) linear space complete.  By contrast, many puzzles with irreversible moves, including Sokoban, are complete for nondeterministic linear space.

Sliding blocks is in linear space because the state has $O(n)$ bits and the moves are reversible (and undirected graph connectivity is in logspace).

In the other direction, the above paper first uses a reduction from nondeterministic constraint logic (NCL), and then reduces QBF to NCL.  The NCL to sliding blocks reduction is space-efficient (at least if the wiring of NCL is based on a two dimensional grid of cells with $O(1)$ gates per cell, which suffices).  However, even if the QBF to NCL reduction is efficient, known simulations of linear space use approximately quadratic size QBF.

Fortunately, a later paper offers a different reduction.  "[Parameterized Complexity of Graph Constraint Logic]"(https://arxiv.org/abs/1509.02683) by Tom van der Zanden shows that NCL (even for bounded width corresponding to an nxk board) can simulate H-Word Reconfiguration (which can be used to simulate string rewriting with a finite set of reversible length-preserving rules).  While the paper does not say it, H-Word Reconfiguration can be used for space-efficient (up to a constant factor) simulation of reversible Turing machines.  In turn, given unbounded time, reversible Turing machines (as a computational model) are space-efficient. (However, it remains open whether some problems in $\mathrm{TimeSpace}(n^{O(1)}, O(n))$ take exponential time for linear space reversible Turing machines.)

For appropriate board representations, we even have, for every problem in linear space, a deterministic finite state transducer that reduces instances to solvability of sliding blocks.  The transducer gives an nxk board; if we want an mxm board, linear time logspace reductions remain sufficient.


The power of randomized logspace with two-way access to the random tape

Well, here are a couple of observations. There's a famous PRG by Nisan that fools $\mathsf{BPL}$-type algorithms with seed length $O(\log^2 n)$. Given two-way access to the seed, Nisan's PRG can be computed in space $O(\log n)$. Therefore, every language in $\mathsf{BPL}$ can be decided by a $\mathsf{BP}^*\mathsf{L}$-type algorithm that only uses $O(\log^2 n)$ random bits.

In fact, you can get the best of both worlds. By using the same technique that Nisan used to show $\mathsf{RL} \subseteq \mathsf{SC}$, one can show that every language in $\mathsf{BPL}$ can be decided by a $\mathsf{ZP}^*\mathsf{L}$-type algorithm that only uses $O(\log^2 n)$ random bits.

So in terms of the state of the art, two-way randomness is more powerful both qualitatively (two-sided error vs. zero-sided error) and quantitatively (polynomially many random bits vs. polylogarithmically many random bits). However, it seems likely that $\mathsf{L} = \mathsf{BP}^*\mathsf{L}$ and hence the two models are actually equivalent.


Complexity of permutation related problems

Let $g_1, \ldots, g_k, g \in S_n$ where $S_n$ is the permutation group on $n$ elements. Testing whether $g \in \langle g_1, \ldots, g_k \rangle$ can be done in $\text{NC} \subseteq \text{P}$ by [1]. Let $u, v \in \Gamma^n$, then simply guess $g \in S_n$, test in polynomial time whether $g \in G$ and whether $g(u) = v$. This yields an $\text{NP}$ upper bound.

To complement this answer:

  Group membership was shown to belong to $\text{P}$ (Furst et al. 1980), then to
  $\text{NC}^3$ for abelian groups (McKenzie & Cook 1987; Mulmuley
  1987), to $\text{NC}$ for nilpotent groups (Luks & McKenzie 1988), solvable
  groups (Luks & McKenzie 1988), groups with bounded non-abelian
  composition factors (Luks 1986), and finally all groups (Babai et al.
  1987). A similar complexity classification of  aperiodic monoids
  membership owes to (Beaudry 1988; Beaudry et al. 1992; Kozen 1977),
  who show that membership for any fixed aperiodic monoid variety is
  either in $\text{AC}^0$ , in $\text{P}$, in $\text{NP}$, or in $\text{PSPACE}$ (and complete for
  that class with very few exceptions).

[1] L. Babai, E. M. Luks & A. Seress. Permutation groups in NC. Proc. $19^\text{th}$ annual ACM symposium on Theory of computing, pp. 409-420, 1987.


Counting sum of parities of cycle covers in cubic, planar, bipartite graphs

Let $A, B$ be the bipartition of $G$ and $|A| = |B| = n.$

Claim: $c_1 + c_2 + c_3 \equiv n \pmod{2}.$

To show this, we can naturally associate each matching $M_i$ to a permutation $\sigma_i \in S_n.$

Define $f: S_n \to \{0, 1\}$ such that $f(\sigma) = 0$ iff $\sigma$ is an even permutation, and define $c: S_n \to \mathbb{N}$ so that $c(\sigma)$ is the number of cycles in $\sigma.$ We know that $c(\sigma) \equiv n-f(\sigma) \pmod{2}.$

Now, it is direct to see that the number of cycles in $M_i \cup M_j$ is simply $c(\sigma_j^{-1}\sigma_i) \equiv n-f(\sigma_j^{-1})-f(\sigma_i) \equiv n-f(\sigma_j)-f(\sigma_i) \pmod{2}.$ Summing gives us that $$c_1+c_2+c_3 \equiv 3n-2f(\sigma_1)-2f(\sigma_2)-2f(\sigma_3) \equiv n \pmod{2}$$ as claimed.

So you question really is: are there planar cubic graphs with an odd number of vertices on each side of the bipartition? At this point it's not hard to draw out an explicit counterexample; I'll give a sketch of how to find one.

Make 3 hexagons, so that $G$ would have $9$ vertices on both sides of its bipartition. Now, we have to add 9 more edges, 3 between each pair of hexagons that preserves the graph being bipartite and is planar. It isn't hard to just draw 9 such edges by hand. Ask if you are still having trouble, I can explicitly describe the graph then.


Relation between different "complexity theories" and complex systems theory

For the relation between first and second look up descriptive complexity theory and finite model theory. This is a established branch of complexity theory and logic.


Capacitated multiple vehicle routing problem with handovers

These problems are studied but with different terminology such as drop-off. See below and references therein.

The Finite Capacity Dial-A-Ride Problem,
M. Charikar and B. Raghavachari,
in Proceedings of the 39th Annual IEEE Conference on Foundations of Computer Science (1998)

Algorithms for Capacitated Vehicle Routing
M. Charikar, S. Khuller and B. Raghavachari,
in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (1998).

Dial a Ride from k-forest
ACM Transactions on Algorithms, 6(2):2010
Anupam Gupta, MohammadTaghi Hajiaghayi, Viswanath Nagarajan, and R. Ravi


Time-bounded Kolmogorov complexity and non-random strings

I suspect that there is something that can be said generally, but off the cuff, the best I can see is that as $t$ increases, the number of compressible strings increases as well.

On the other hand, we certainly cannot pick a $t$ such that $f$ is polynomial.  Notice that if $t(|x|)<|x|$, then there isn't enough time to write anything.  On the other hand, strings of the form $yyz$ can be generated by programs of length $|y|+|z|<|x|$ and there are at least $2^{|x|/2}$ of those.  So by monotonicity, $f$ will always be at least this large.


Learning k-parities with Membership Queries and Persistent Noise

If I understand correctly, this is exactly equivalent to local decoding of the Hadamard code.

We can think of the oracle (with the noise) as being chosen beforehand, and after that we can view the oracle as a corrupted codeword of the Hadamard code. Learning the parity in this case is exactly the task of local decoding the original message from the corrupted codeword.

This is well-known to be possible using $O(n \log n/\delta)$ queries, using the Goldreich-Levin theorem, e.g.:
https://lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/

On the other hand, it clearly can not be done using $o(n)$ queries, since the algorithm has learn $n$ bits about the parity - i.e., its attributes.


What is the precise definition of Random K-SAT?

As was pointed out at the beginning of this discussion in the comments, there is not necessarily a single "right" definition for random $k$-SAT.

That said, the two most common variants of random $k$-SAT are both fixed clause length (FCL) models, meaning that exactly $k$ literals appear in each clause. These variants both disallow repeated variables and literals within a clause, but differ in whether they allow repeated clauses within a formula. Nevertheless, they are essentially the same as will be discussed below.

Two main models:

The Selman random model - Repeated clause are allowed. Kyle gave this nice reference in the comments to his answer, but incorrectly assumed that the model disallowed repeated clauses. The linked (slightly different) version of the paper contains a more detailed discussion of the random model in Section 3: "This method of generation allows duplicate clauses in a formula... However, as N gets large duplicates will become rare because we generally select only a linear number of clauses."

The Achlioptas random model - Repeated clauses are disallowed. We treat generating a random formula as selecting $m$ clauses u.a.r. from the $2^k {n \choose k}$ total possible clauses without replacement. See Ch.8 of the Handbook of Satisfiability [1]  (Random SAT by Achlioptas) as a reference. This model seems more prevalent in the theoretical literature, possibly because so much of it was written by Achlioptas himself.

Equivalence of phase transition locations:

However, the phase transition (50% satisfiability threshold) occurs at the same clause-to-variable ratio regardless of which of these models is chosen for essentially the reason that Selman et al. noted in their paper.

Let $A(n,m,k)$ denote the expected number of identical pairs of clauses in a Selman random $(n,m,k)$-SAT instance. The probability of a given pair of clauses being identical is $p = 1/(2^k {n \choose k})$, whereas the total number of pairs of clauses is $N = {m \choose 2}$. By the linearity of expectation, $A(n,m,k) = p \cdot N = {m \choose 2}/{2^k {n \choose k}}$.

By Theorem 3 in  [1], the provable upper bound on the location of the $k$-SAT phase transition, using the Achlioptas model occurs when $m = O(2^k n)$. Fixing $k \geq 3$ and setting $m = O(2^k n)$ we get

$A(n,m,k) = {m \choose 2}/{2^k {n \choose k}} = O(m^2)/O(n^k) = O(n^2)/O(n^k)$.

Then, because $k \geq 3$, $\displaystyle \lim_{n \rightarrow \infty} O(n^2)/O(n^k) = 0$, meaning that in expectation there will be zero repeated clauses around the $k$-SAT phase transition when generating random SAT formulas using the Selman model.

Shameless self promotion - I discuss these topics briefly in Section 4.1 of my master's thesis.

Random QBF

As it turns out, the situation is much more interesting for random QBF. What are AFAIK the first three papers on random QBF each proposed a new random model, critiquing their predecessor.

See the following papers:

Cadoli et al. "Experimental Analysis of the Computational Cost of Evaluating Quantified Boolean Formulae." AI*IA 1997
Gent + Walsh "Beyond NP: the QSAT phase transition." AAAI/IAAI 1999
Chen + Interian "A Model for Generating Random Quantified Boolean Formulas." IJCAI 2005


This is called run-length-limited coding, there has been lots of research done on it by the information theory community, and I will just refer you to the existing literature. After a brief glance at the wikipedia article I linked to, my impression is that you shouldn't rely on the references it contains, but do your own search of the literature.

One simple thing you could do that does better than doubling the string size is:

(1) add a 0 to the end of the original sequence,
(2) break the original sequence greedily into blocks of either 0, 10, or 11,
(3) encode using the encoding

     0 → ab
  10 → abb
  11 → abbb

Step (2) is always possible, since after step (1) the sequence ends with a 0. Except for step (1), which adds at most two bits to your encoded sequence, this cannot do worse than double the string size, and generally does better.

For example, you encode
0110100101 → 0.11.0.10.0.10.10 → ababbbababbababbabb,
taking 10 characters into 19.

If I did my calculations right, starting with $n$ random bits, this encoding gives an expected length of 11/6 $n$ bits, which is only slightly more than the optimal value of around 1.813 $n$ bits.


Let $v_0, v_1, \ldots, v_n \in \mathbb{Z}_2^m$. The problem is to determine whether the following system has a solution:

$$
\begin{pmatrix}
v_1 & \cdots & v_n
\end{pmatrix}
\begin{pmatrix}
x_1 \\
\vdots \\
x_n
\end{pmatrix}
=
v_0 \, (\text{mod } 2)
$$

This problem is known to be $\oplus L$-complete by [Damm90, BDHM92], thus inside $\text{NC}^2 \subseteq \text{P}$.

[Damm90] Carsten Damm: Problems Complete for $\oplus L$. Inf. Process. Lett. 36(5): 247-250 (1990)
[BDHM92] Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Structure and Importance of Logspace-MOD Class. Mathematical Systems Theory 25(3): 223-237 (1992)


Short version: You want a crypto system that, with keys of length $k$, is secure against attackers with running time $2^{k^\epsilon}$, or even $2^{\Omega(k)}$. Most schemes that anyone would want to use in practice are conjectured to satisfy such bounds. Of course, we can't prove that they satisfy bounds like that without, at the very least, separating P from NP.

Longer version:
"Concrete security" provides the kind of theory I think you are looking for, since it foregoes coarse categorizations (polynomial versus not) in favor of specific bounds.

For example, you can define a public-key cryptosystem to be $(t,\epsilon)$ secure if no attacker running in time $t$ has probability more than $1/2 + \epsilon$ of winning a chosen-plaintext indistinguishability game. Because the running time includes calls to the underlying encryption schemes, this provides security for messages of length roughly $t$. If you want to be even more precise, you can track running time ($t$) and queries to cryptosystem ($q$) separately. Under sufficiently strong assumptions about the primitives (e.g. exponentially hard to invert one-way permutations), one can construct cryptosystems that are $(t,\epsilon)$-secure for very large $t,q$ (close-ish to $2^{key\ length}$) and very small $\epsilon$.

These types of bounds are used a lot in research papers (especially in the symmetric-key world). They appear less often in lecture notes and textbooks, because they introduce extra bookkeeping and can tax the notation-absorption skills of students.

Luca Trevisan's lecture notes on crypto, though, use this notation; they might be a good resource to start with.


I agree with Artem, but perhaps this paper on a quantum circuit model for constructing conditional statements may be of some relevance to what you are trying to figure out.


Problems still "hard" in the SMP/Referee model with shared randomness?

If A has a pointer (of length $\log n$) to a bit of B (whose input has length $n$), that requires, $\Theta(\log n)$ one-way communication, even with a public-coin. On the other hand, the referee needs $\Theta(n)$ bits to solve the problem, even with a public-coin. Or did I misunderstand something?


Formal theory about explaining algorithms

This might not be what you're looking for, but I think this is somewhat covered by the theory of dependent types, specifically intrinsically typed data structures.
The idea is that, instead of having an algorithm along with a proof of correctness, you start with a type that describes the properties of a solution. Then you simply write a program of that type, and you are guaranteed that it is correct.
Does this mean that you get correctness for free? Certainly not. But now the "why" at each stage is clear. The presentation of the algorithm and the explanation are one and the same. The notion of of correctness is formalized, and baked into the language itself.
For intros on this, see:

https://cs.ru.nl/~wouters/Publications/ThePowerOfPi.pdf
http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf
https://www.manning.com/books/type-driven-development-with-idris
https://mitpress.mit.edu/books/little-typer