References can be found in martinschwarz's answer, but here's a summary of a couple reductions.

The symmetric group $S_n$ acts on graphs of n vertices by permuting the vertices.  Determining whether two graphs are isomorphic is polynomial-time equivalent to computing a polynomial-size generating set for $Aut(G)$.

Reduction to the HSP over the symmetric group $S_n$ (where $n$ is the number of variables in the graph).  The function $f$ is $f(p)=p(G)$ where $p$ is a permutation in $S_n$, and $p(G)$ is the permuted version of $G$.  Then $f$ is constant on cosets of $Aut(G)$ and distinct on distinct cosets (note that the image of $f$ consists of all graphs isomorphic to $G$).  Since the hidden subgroup is exactly $Aut(G)$, if we could solve this HSP then we would have the generating set for $Aut(G)$, which is all we need to solve GI (see above).

Reduction to the HSP over $S_n \wr \mathbb{Z}/2\mathbb{Z}$.  If we want to know if two graphs $G$ and $H$ on $n$ vertices are isomorphic, consider the graph $K$ which is the disjoint union of $G$ and $H$ on $2n$ vertices.  Let $\mathbb{Z}/2\mathbb{Z}$ act on the vertices by swapping $i$ with $n+i$ for $i=1,...,n$.  Either $Aut(K) = Aut(G) \times Aut(H)$ or $Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$.  As before, let $f(x)=x(K)$ where $x$ is now an element of $S_n \wr \mathbb{Z}/2\mathbb{Z}$ that acts on $K$ as described.  The hidden subgroup associated to $f$ is exactly $Aut(K)$, as in the previous reduction.  If we solve this HSP, we get a generating set for $Aut(K)$.  It is then easy to check whether the generating set contains any element that swaps the copy of $G$ with the copy of $H$ inside $K$ (has nontrivial $\mathbb{Z}/2\mathbb{Z}$ component).


Sample complexity of distinguishing two Gaussian distributions?

I don't have a solution to this problem, but the analogous case where the two distributions are discrete has been analyzed in the cryptographic literature.

Suppose we want to distinguish between two distributions $\mathcal{D}_0$, $\mathcal{D}_1$, where these two distributions are "close".  Suppose we have $n$ observations (i.e., a sequence of $n$ numbers that are sampled from either i.i.d. $\mathcal{D}_0$ or i.i.d $\mathcal{D}_1$), and we want to distinguish whether they came from $\mathcal{D}_0$ or from $\mathcal{D}_1$.  Let $d = 0.5 n/D(\mathcal{D}_0 ||\mathcal{D}_1)$, where $D(\mathcal{D}_0 ||\mathcal{D}_1)$ is the Kullback-Leibler divergence between these two distributions.  Then the optimal distinguisher has a probability of error approximately $\Phi(-\sqrt{d}/2)$, where $\Phi(t)$ is the pdf of the standard normal distribution.

See Theorem 6 from How Far Can We Go Beyond Linear Cryptanalysis?, Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.

I have no proof that this is valid for multivariate Gaussian distributions as well, but it seems reasonable to conjecture that it might.

Stepping away from discrete distributions, in your particular case of normal distributions, the one-dimensional case ($p=1$) has also been studied in the cryptographic literature.  If you want to distinguish $\mathcal{N}(\mu_0,\sigma_0^2)$ from $\mathcal{N}(\mu_1,\sigma_1^2)$ given a single observation, the optimal distinguisher has probability of error $\text{erfc}(z)$ where $z = (\mu_1-\mu_0)/(\sigma_0+\sigma_1)$.  I don't recall what happens when you get to see $n$ samples from either $\mathcal{N}(\mu_0,\sigma_0^2)$ from $\mathcal{N}(\mu_1,\sigma_1^2)$, but I imagine this case has been worked out before as well.

See https://cstheory.stackexchange.com/a/22339/5038.

In the multivariate case, the Kullback-Leibler divergence between two multivariate Gaussians is known: see https://en.wikipedia.org/wiki/Multivariate_normal_distribution#Kullback.E2.80.93Leibler_divergence.

Also, the Kullback-Leibler divergence is additive when you have $n$ i.i.d. samples, so the Kullback-Leibler divergence of the product distribution will be $n$ times the KL divergence for a single sample: $D(\mathcal{D}_0^n ||\mathcal{D}_1^n) = n \times D(\mathcal{D}_0 ||\mathcal{D}_1)$.  This is a very handy property of the KL divergence, and it will let you calculate the KL divergence between $n$ samples of $\mathcal{N}(\mu_0,\Sigma)$ vs $n$ samples of $\mathcal{N}(\mu_1,\Sigma)$.  (As a conjecture, I would guess that the distinguishing advantage becomes significant only when this KL divergence becomes significant, though I don't know any proof of this.)

Finally, you might be interested in Pinsker's inequality, which connects the total variation distance to the Kullback-Leibler divergence.  The total variation distance measures (twice) the advantage of the optimal distinguisher.

Unfortunately, depending on your goals, Pinsker's inequality might "go the wrong way".

See also https://stats.stackexchange.com/q/17300/2921 and https://math.stackexchange.com/q/72721/14578 and https://stats.stackexchange.com/q/42992/2921

Update: All of this assumes the two distributions are known.  I just noticed that you want to consider a version of the problem where the distributions are not known to the algorithm.  This can only make the problem harder, but I don't know how much harder, and I don't know of anyone who has studied that variant.


Does a noisy version of Conway's game of life support universal computation?

Here are some "nearby best" references, for what it's worth. It would seem the way to go on this question is to reduce it to a question on "noisy Turing machines", which have been studied (somewhat recently), and which are apparently the nearest relevant area of the literature. The basic/general/reasonable answer seems to be that if the TM can resist/correct for noise (as is demonstrated in these references), it's quite likely the CA can also, within some boundaries/thresholds.

The question of how to reduce a "noisy CA" to a "noisy TM" (and vice versa) is more open. It may not be hard but there does not appear to be published research in the area. Another issue is that the noisy TM is a new model and therefore there may be multiple (natural?) ways to represent a noisy TM. For example, the following papers look at disruptions in the state transition function, but another natural model is disruptions in the tape symbols (the latter being more connected to noisy CAs?). There may be some relation between the two.

Fault-tolerant Turing Machine by Ilir Capuni, 2012 (PhD thesis)

  The Turing machine is the most studied universal model of computation. This thesis studies the question if there is a Turing machine that can compute reliably even when violations of its transition function occur independently of each other with some small probability.

  In this thesis, we prove the existence of a Turing machine that with a polynomial overheadcan simulate any other Turing machine, even when it is subject to faults of the above type, thereby answering the question that was open for 25 years.
  A Turing Machine Resisting Isolated Bursts Of
  Faults by Ilir Capuni and Peter Gacs, 2012
  Noisy Turing Machines by Eugene Asarin and Pieter Collins, 2005

  (Another question: could there be some connection between noisy TMs and probabilistic Turing Machines?)


Maximum subset of words with Hamming distance ≥ D

In coding theory, the quantity you are looking for is called $A_q(n, d)$, where $n$ is the length of vectors, $d$ is the minimum distance between them, and $q$ is the alphabet size (omitted when $q=2$). Characterizing $A_q(n,d)$ is a challenging open problem (with many basic questions remaining unanswered) but various asymptotic and non-asymptotic upper and lower bounds are known. See Chapter 17 of the book "The Theory of Error-Correcting Codes" by MacWilliams and Sloane for a summary of the most important ones.


Regular safety properties and bad prefixes of $\omega$-regular properties

Your construction for bad prefixes is not correct on NBA's.
For instance take the NBA on alphabet $A=\{a,b\}$ with two initial states $q_a$ and $q_b$ where for both $x\in A$, $q_x$ goes to an accepting sink if the first letter is $x$ and to a rejecting sink if the first letter is not $x$.

Then the language recognized is $A^\omega$, but the set of "bad prefixes" you compute is $A^*$ i.e. all finite words.

Your construction works if you first determinize the automaton. Then the new final states are the ones which cannot reach a component $C$ accepting some infinite word. Careful though, the deterministic automaton is no longer Büchi, it is a parity automaton, so it is a little more complicated to check if a component has empty language.

As for your question about closure, you are essentially asking if for any regular language $L$, $Closure(L)$ is the set of words containing no bad prefixes of $L$. This is true: a word is in the closure of $L$ iff it is arbitrarily close to words in $L$ iff it does not contain a bad prefix.


How come Wikipedia says that Random Turing Machines can provide uncomputable output?

It's not uncommon for Wikipedia to say dubious things.  Don't trust it as a primary reference.  Beware that hypercomputation is potentially a "crank-adjacent" subject, so the Wikipedia article on it might be especially at risk of containing material of uncertain reliability.  When you find something in Wikipedia you don't understand, my advice is to look at primary sources, such as good textbooks on the subject.
The statement "the output of a random Turing machine is uncomputable" does not look accurate to me.  It's not even clear to me what that would mean.  I'm not sure how computability would be defined for probabilistic machines -- that would need to be specified before such a statement can be assigned any truth value.
No, in computer science "random" does not mean the same thing as "unknown".  In lay language "random" can mean "arbitrary" or "I don't understand it" or "hard to predict" or "I don't know what's going on here" or "I don't see an obvious pattern", but in computer science "random" has a  specific technical meaning taken from probability theory.  See, e.g., https://cs.stackexchange.com/q/13893/755, https://cs.stackexchange.com/q/7729/755.


Advice for Graduate School in Computer Science

I want to disagree slightly with Dave Clarke and Lev Reyzin.  At least in my department, PhD admission standards for students with MS degrees are higher than for students with only bachelor's degrees.  Additional experience can be a disadvantage, if it isn't enough additional experience.

All else being equal, my department expects any applicant with an MS to have a publication, or at least a publishable result, before we will consider them for admission to the PhD program.  (And by "published", I mean in a reputable peer-reviewed web-accessible conference proceedings or journal, not just a master's thesis, internal technical report, student research conference, or The Inaccessible Chinese Journal of Computer Science.)  Working a full time job is unlikely to leave you enough time—or more importantly, enough mental energy—to do publishable research.

Of course, ceterus is never paribus.  We do soften the de facto publication requirement for  MS applicants who have switched major fields.  But then you're in the uncomfortable position of explaining a perceived weakness.  (On the other hand, I'm not sure switching from mathematics to theoretical computer science counts as "major".)

My advice is not to put your eggs in one basket.  First, talk to people you might work with in the programs you are interested in.  Let me emphasize the plurals here — talk to multiple people in multiple departments.  Second, in the absence of specific contradictory advice from target departments, apply to both MS and PhD programs.  (Some universities, or at least their web forms, stupidly make you pick one or the other, in which case you must talk directly to the admissions office of your target department.)  Sane PhD programs let incoming students from other fields take undergrad CS courses for remediation.


Is $AC^0/poly \cap NP$ contained in $P$?

Answer to your first question: Seems unlikely.

Theorem: If $NP \cap AC^0/poly \subseteq P$ then $NEXP = EXP$.

Given a circuit $C$ that outputs a bit, define the decompression of C to be the bit string obtained by evaluating $C$ on all possible inputs. That is, the decompression is $C(0^n) C(0^{n-1}1) C(0^{n-2}10) \cdots C(1^n)$.

Define the Succinct 3SAT problem as: given a circuit $C$ of size $n$, does its decompression encode a satisfiable Boolean formula? Succinct 3SAT is well-known to be $NEXP$ complete.

Now consider the language

$L = ${$1^n | $the integer $n$ written in binary is a yes-instance of Succinct 3SAT}.

$L$ is clearly in $AC^0/poly$, since you can just hardcode whether $1^n$ is in $L$, for each $n$.

$L$ is also in $NP$: the integer $n$ written in binary has length about $\log n$, so the decompression of this circuit has length no more than $O(n)$. Hence the satisfying assignment has length at most $O(n)$.

But by the same observations, if $L \in P$, then $NEXP=EXP$, because it means that you
have an $O(n^c)$ time algorithm for deciding every instance of Succinct 3SAT of length $\log n$.

Your second question is wide open (and open-ended).


What you wrote is correct. The actions $\textit{coin}$ and $\textit{ret_coin}$ do not change the values of the variables $\textit{Var} = \{\textit{nsoda}, \textit{nbeer}\}$, i.e., the number of soda and beer cans in the machine.

Inserting a coin is only possible in the $\textit{start}$ location, and with this action the location changes to $\textit{select}$. If you’re wondering how the machine keeps track of payment at all, this is it: By the PG's two locations.
Only after the user selects a beverage, a can is dispensed, and the variable evaluation changes (the effect of $\textit{[sb]get}$).

Similarly, returning the coins (which can only happen in the case the vending machine has neither beer nor soda cans) does not change the number of cans.

You could propose a different model that does track the exact amount of coins inserted as a variable, and define

$\textit{Effect}(\textit{coin},η) = η[\textit{coins_inserted} := \textit{coins_inserted} + 1]$ as well as
$\textit{Effect}(\textit{ret_coin},η) = η[\textit{coins_inserted} := 0]$

but the example given does not do so.


Is there an algorithm that finds the forbidden minors?

The answer by Mamadou Moustapha Kanté (who did his PhD under supervision of Bruno Courcelle) to a similar question cites A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals (1997) by B. Courcelle, R. Downey, and M. Fellows for a non-computability result (for MSOL-definable graph classes, i.e. classes defined by a Monadic Second order formula) and The obstructions of a minor-closed set of graphs defined by a context-free grammar (1998) by B. Courcelle and G. Sénizergues for a computability result (for HR-definable graph classes, i.e. classes defined by a Hyperedge Replacement grammar).

The crucial difference between the computable and the non-computable case is that (minor-closed) HR-definable graph classes have bounded treewidth, while (minor-closed) MSOL-definable graph classes need not have bounded treewidth. In fact, if a (minor-closed) MSOL-definable graph class has bounded treewidth, then it is also HR-definable.

The treewidth seems to be really the crucial part for separating the computable from the non-computable cases. Another known result (by M. Fellows and M. Langston) basically says that if a bound for the maximum treewidth (or pathwidth) of the finite set of excluded minors is known, then the (finite) minimal set of excluded minors becomes computable.

It is not even known whether the (finite) minimal set of excluded minors for the union (which is trivially minor-closed) of two minor-closed graph classes each given by their respective finite set of excluded minors can be computed, if no information about treewidth (or pathwidth) is available. Or maybe it has even been proved in the meantime that it is non-computable in general.


About learning a single Gaussian in total-variation distance

Essentially, this follows from three facts:

learning a Gaussian in total variation distance $\delta$ is equivalent to learning its two parameters, $\mu,\Sigma$, to (respectively) $\ell_2$ and relative Frobenius norms $O(\delta)$. (Since then the "empirical Gaussian" with the mean and covariance you estimated will be $\delta$-close to the true Gaussian).
learning the mean $\mu$ to $\ell_2$ distance $\delta$ can be done with $O(\frac{n}{\delta^2})$ samples. (This is tight)
learning the covariance to relative Frobenius distance $\delta$ can be done with $O(\frac{n^2}{\delta^2})$ samples. (This is tight)

I suggest you try to prove these yourself. The first one follows from relatively "standard" facts about Gaussians [1], the second two are good exercises.

(If you really want a specific reference, I can try to dig some up.)

[1] Theorem 1.3 in this recent paper is overkill, but will do the job. https://arxiv.org/abs/1810.08693


Why may the right hand sides in Chomsky Hierachy type 1 be larger?

It is not allowed to be larger, it has to be larger! If you allow the right side being shorter, you have context sensitive deleting grammars which have the same power as unrestricted grammars, thus leaving the realms of CSL.

The space limitation you mention relates to the automaton concept that is equivalent to context sensitive grammars, not the grammars itself.


Lower bounds for Polynomials computing the boolean functions

Regarding Question C: Number of monomials is essentially the same thing as circuit size of depth-2 algebraic circuits (unless the polynomial is a product of linear polynomials, in which case one could also consider a depth-2 circuits with a multiplication gate at the top).

Degree is very closely related to the depth of algebraic circuits, as in the results of Hyafil and Valiant-Skyum-Berkowitz-Rackoff.


Difference between syntax and semantic error in programming languages

In the strictest sense, there is no real difference between syntax errors and semantics errors, at least as far as language theory is concerned: the only salient difference is the complexity of the automaton required to recognize that language, with, e.g.

Context-free languages only requiring pushdown automata (PDA)
General recursive languages requiring full Turing machines (TM)

If every "syntactic task" merely required pushdown automata and every "semantic task" something more, then the matter would be settled, but unfortunately there are many tasks that are associated with programming language syntax that cannot be handled by PDA alone, and conversely, some semantic tasks which seem to require only weak computation power. Still, the distinction provides some intuition.

Pragmatically, compilers are designed in phases, which makes managing the task of generating executable code manageable. I particularly like this diagram from the Compcert website.

Typically, the first 1-3 phases turn what is essentially a stream of bytes or tokens into something more naturally seen as a tree structure. Everything before the tree creation will be labelled as "syntax" and everything after as "semantics".

In C, the syntactic phases are typically tokenization, macro expansion and parsing, everything after that will be semantics. Again, opinions may differ, since there is no accepted formal distinction.

I think there's a larger discussion to be had about how to distinguish syntactic notions from semantic notions in the field of formal logic, but I'm not sure I feel qualified to have it.


Transform a CNF into an equivalent 3-CNF defined on the same variables

(From the comment above)
The problem seems coNP-hard; the simple reduction is from 3CNF-UNSAT (which is coNP-complete):
given a 3CNF formula $\varphi = C_1 \land ... \land C_m$, extend it adding a new clause with 4 new variables:

$$\varphi' = (y_1 \lor y_2 \lor y_3 \lor y_4) \land C_1 \land ... \land C_m$$

$\varphi'$ has an equivalent 3CNF formula defined on the same variables if and only if the original formula $\varphi$ is unsatisfiable.

($\Leftarrow$) the 3CNF formula $(y_1 \lor y_2 \lor y_3) \land (y_1 \lor y_2 \lor y_4) \land C_1 \land ... \land C_m$ is equivalent to $\varphi'$

($\Rightarrow$) suppose that $\varphi'$ has an equivalent 3CNF formula $\varphi''$ and that $\varphi$ is satisfiable.
Pick a satisfying assignment $X = \langle \dot{x}_1,...,\dot{x}_n \rangle$ of $\varphi$, and simplify both $\varphi'$ and $\varphi''$ replacing the variables $x_i$ with
the corresponding truth values $\dot{x}_i$. We get $\varphi'_X$ which is satisfiable if and only if $\varphi''_X$ is satisfiable
(both contain only variables $y_i$).
Clearly $\varphi'_X = (y_1 \lor y_2 \lor y_3 \lor y_4)$. Every clause of $\varphi''_X$ contains at most three variables,
so we can pick one of them, e.g. $(y_1 \lor \lnot y_2 \lor y_3)$, and use it to build a satisfying assignment for $\varphi'$:
$\langle y_1=false, y_2=true, y_3=false,y_4=true,\dot{x}_1,...,\dot{x}_n \rangle$ which is not a satisfying assignment for $\varphi''$,
leading to a contradiction.


Is there a notion of "sequential" idempotence?

Your question would probably fit better on MathsStackExchange, but here is an answer.

I don't think there is any specific name for your definition. Since any semigroup is isomorphic to a transformation semigroup, your question is about finitely generated semigroups that are quotients of the semigroup $S_n$ with presentation
$$
\langle a_1, \ldots, a_n \mid a_1^2 = a_1, (a_1a_2)^2 = a_1a_2, \ldots, (a_1 \dotsm a_n)^2 = a_1 \dotsm a_n \rangle
$$
It turns out that $S_n$ is infinite for $n > 1$, but I don't know whether it has been studied in the literature.


Are provable quantum speed-ups possible for classes larger than NP?

For total functions it is impossible to achieve more than a polynomial separation (i.e. $D(f) = O(Q^6(f))$) in the quantum query model, for more info see this cstheory blog post. With promise problems, you can have exponential seperations between the quantum and classical query complexity. However, classical query complexity is sometimes very deceptive in its correspondence to complexity classes; as are partial functions in general. If you don't allow promise problems, you can't get exponential separations and your relevance to the big classes is questionable. You can never expect more than an exponential seperation, because a quantum algorithm can be simulated by a classical computer with exponential overhead (actually, in PSPACE so looking above that is dubious).


Does the MIP* = RE proof work for limited provers?

I believe our result shows that if the prover is capable of solving NTIME[poly(T)] problems, and has the ability to manipulate polylog(T) qubits, then they can convince the verifier of YES instances of NTIME[T] problems.

In other words, roughly speaking NTIME[2^poly(Q)] = MIP*[Q] where MIP*[Q] denotes the provers being limited to Q qubits of entanglement.


Is it possible to model maximization in a petri net without using inhibitor arcs?

I know almost nothing about Petri nets, so watch out for any mistakes.  The terminology in this answer follows Wikipedia.

Theorem.  There is no Petri net with two distinguished source transitions S1 and S2 and one distinguished sink transition T such that if S1 fires a times and S2 fires b times, then T fires max{a,b} times eventually but T cannot fire more than max{a,b} times.

Proof.  Suppose that there is such a Petri net, and let M0 be the initial marking.  Let n be the number of places in this Petri net.  A marking can be viewed as an element in ℕn, where ℕ={0,1,2.…}.

Define markings M1, M2, … recursively as follows.  Starting with Ma (a=0,1,…), let S1 fire once, and wait for T to fire.  Let Ma+1 be the marking after T fires.

By Dickson’s lemma, there exist indices i<j such that Mi≤Mj.  Consider the following scenario.  Starting with Mi, let S2 fire i+1 times.  Counting from the beginning, S1, S2 and T have fired i times, i+1 times and i times, respectively.  Therefore, from this situation, T will eventually fire.  Now consider another scenario.  Starting with Mj, let S2 fire i+1 times.  Then there exists a firing sequence which leads to T firing because Mi≤Mj (and the Petri net does not have inhibitor arcs), but this contradicts the assumption because counting from the beginning, S1, S2 and T have fired j times, i+1 times and j+1 times, respectively, and j+1>max{j, i+1}.  QED.

Edit: The proof in revision 1 contained an error, which was pointed out by mweerden in a comment.  Now it is fixed.  Thanks, mweerden!


Finding the Length of the shortest Accepting path of a NDTM

Your problem is $\mathsf{NP}$-complete, and you can find a proof for instance here (I gave a sketch in comments).

A remark: If you consider $\{\langle M,x,t\rangle : M$ halts on $x$ in $t$ steps $\}$, then you can only show it is $\mathsf{NP}$-hard. But as you mention that you consider $t$ polynomially bounded (in the sizes of $M$ and $x$, I guess), then your problem belongs to $\mathsf{NP}$.


$DTIME(n^{polylogn})$ is known as $QP$ (quasi-polynomial).

It is widely believed that $NP\not \subset QP$, although it is a stronger statement than $P\neq NP$.

Some common conjectures, such as the  Exponential Time Hypothesis imply $NP\not \subset QP$.


Analogue of $k$-wise independence for other distributions than uniform

I met once a similar notion to what you want in one paper by Mark Zhandry's paper under the name $k$-wise equivalent. I cannot find further references or pointers from that paper, but I think this name nicely describes your something.
Concretely, the original definition in the paper is about the distributions over the functions $f: X\rightarrow Y$, and define the size-$k$ marginal by its marginal distribution for any size-$k$ subset $W$ of $X$. The notion $k$-wise equivalence is defined accordingly, that is, two distributions are identical on any $k$-marginal.
It is not directly addressing your main question, but we can say that your desired distribution is $k$-wise equivalent to the uniform random permutation. It also, unfortunately, does not give any efficient construction for equivalent distribution as well.


Take a look at Toom-Cook multiplication and see if that is helpful for what you need. The complexity is $O(n^{1+\epsilon})$ for any fixed $\epsilon>0$.


Linear Function Representation of Neural Network

It would seem to depend on the complexity of your neural network. A single perceptron is a linear separator. On the other hand, it is known that multilayer feed-forward neural networks are universal approximators (see here: http://dl.acm.org/citation.cfm?id=70408 ): i.e. they can approximate any function to arbitrary accuracy. Obviously for such a network, you should not expect to be able to express its outputs as a linear function of its inputs.


Is it still open to determine the complexity of computing the treewidth of planar graphs?

As far as I know the NP-completeness of computing the treewidth of a planar graph is still open. The most recent reference I know is a survey by Bodlaender from 2012 called `Fixed-Parameter Tractability of Treewidth and Pathwidth' that appeared in the festschrift for Mike Fellows' 65th birthday. The problem is listed in the conclusion of the survey.


Verification: how 'formal' is a tool like Java Modeling Language (JML) compared to certified libraries and model checking?

This is a strange comparison. Your question is comparable to asking "how expressive is the ANSI C language specification compared to stdlib and compilation". The comparisons don't make sense.

The Java Modelling Language can be used as a specification language to specify properties of code. The language alone does not solve the problem of verifying whether these properties are satisfied.
A model checker allows you to check if a system with a transition system semantics satisfies a logical formula. The formula is typically written in a propositional temporal or modal logic though first-order and other extensions exist. Nonetheless, most model checkers used in practice do not support specification languages with quantifiers. I do not know of a model checker that supports a specification language as rich as JML.
A certified library contains code that provides certain guarantees. Those guarantees may have been provided using a theorem prover, or a model checker, or by doing a  manual proof.

If you want a mathematical comparison, to me, it's like comparing the formulae of first order arithmetic (a language), the principle of induction (a proof technique) and a collection of theorems in a number theory textbook. They are related concepts but they do not achieve the same goal so comparing them does not make sense.


Equivalent formulation of complexity theory in Lambda Calculus?

As you point out, the λ-calculus has a seemingly simple notion of time-complexity: just count the number of β-reduction steps. Unfortunately, things are not simple. We should ask:

 Is counting β-reduction steps a good complexity measure?

To answer this question, we should clarify what we mean by complexity measure in the first place. One good answer is given by the Slot and van Emde Boas thesis: any good complexity measure should have a polynomial relationship to the canonical notion of time-complexity defined using Turing machines. In other words, there should be a reasonable encoding tr(.) from λ-calculus terms to Turing machines, such that for each term $M$ of size $|M|$: $M$ reduces to a value in $poly(|M|)$ exactly when $tr(M)$ reduces to a value in $poly(|tr(M)|)$.

For a long time, it was unclear if this can be achieved in the λ-calculus. The main problems are the following.

There are terms that produce normal forms in a polynomial number of
steps that are of exponential size. See (1). Even writing down the
normal forms takes exponential time.
The chosen reduction strategy
plays an important role, too. For example there exists a family of terms
which reduces in a polynomial number of parallel β-steps (in the
sense of optimal λ-reduction (2), but whose complexity is
non-elementary (3, 4).

The paper (1) clarifies the issue by showing a reasonable encoding that preserves the complexity class PTIME assuming leftmost-outermost Call-By-Name reductions. The key insight appears to be that the exponential blow-up can only happen for uninteresting reasons which can be defeated by proper sharing of sub-terms.

Note that papers like (1) show that coarse complexity classes like PTIME coincide, whether you count β-steps, or Turing-machine steps. That does not mean lower complexity classes like O(log n) also coincide. Of course such complexity classes are also not stable under variation of Turing machine model (e.g. 1-tape vs multi-tape).

D. Mazza's work (5) proves the Cook-Levin theorem (-completeness of SAT) using a functional language (a variant of the λ-calculus) instead of Turing machines. The key insight is this:

$$
  \frac{\text{Boolean
circuits}}{\text{Turing machines}}=\frac{\text{affine
  $\lambda$-terms}}{\text{$\lambda$-terms}}
  $$

I don't know if the situation regarding space complexity is understood.

B. Accattoli, U. Dal Lago, Beta Reduction is Invariant, Indeed.
J.-J. Levy, Reductions correctes et optimales dans le lambda-calcul.
J. L. Lawall, H. G. Mairson, Optimality and inefficiency: what isn't
a cost model of the lambda calculus?
A. Asperti, H. Mairson,
Parallel beta reduction is not elementary recursive.
D. Mazza, Church Meets Cook and Levin.


Number of words of length n in a context-free language

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:

Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.

This has been shown for instance in:

Roberto Incitti:
"The growth function of context-free languages"
Theoretical Computer Science 255 (2001), Pages 601-605
Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64 (2002), Pages 308-310

And for a given context-free grammar, one can decide in polynomial time whether the generated language has polynomial or exponential growth:

Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
"Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time.
International Journal of Foundations of Computer Science 21 (2010), Pages 597-618


Look up the concept of anticodes. Some bounds exist.

Also if you have a linear $t-$error correcting code over $GF(q)$ with length $n$ and covering radius $r$ and use homogeneity under translations by adding vectors $n-d=n-2t-1$ would seem to be your answer but I haven't checked carefully. Cohen and Litsyn have a book on covering codes.

A Simple Construction

Fix $k\geq 1$ and let $v=\lceil n/k \rceil$ and consider the strings as $GF(q)^n.$ Generate all $k-$tuples over $GF(q)$ to obtain $M=q^k$ codewords. Map these codewords to $GF(q)^n$ by expanding by $v$ for the first $k-1$ coordinates and expanding by $n-(k-1)v$ for the last coordinate. For example, let $q=3,$ $n=5$ and $k=2.$ Your codewords are
$$
\begin{array}{cc}
0&0\\
0&1\\
0&2\\
1&0\\
1&1\\
1&2\\
2&0\\
2&1\\
2&2\\
\end{array}
$$

which become upon expansion with $v=4$

$$
\begin{array}{c}
0000~000\\
0000~111\\
0000~222\\
1111~000\\
1111~111\\
1111~222\\
2222~000\\
2222~111\\
2222~222\\
\end{array}
$$
Now, for any possible vector in $GF(3)^7$ there is a codeword which is quite far from it.
Namely, if there are fewer than 2 symbols for that vector in a block, there is a codeword which is at Hamming distance $v$ from it. If all 3 symbols occur, there is a codeword at Hamming distance $\geq \lfloor 2v/3 \rfloor$ from it. Since all possible constant blocks occur, for any possible vector in $GF(3)^7$ there is a codeword in this code of only $M=9$ codewords which is at Hamming distance $\geq k \lfloor (q-1)v/q \rfloor \approx n(1-\frac{1}{q}).$ Choosing $v$ a multiple of $q$ will make this more efficient.


Deciding if a wildcard string is completely matched by another wildcard string in a set

How about using a finite-state automaton? The language $S$ is finite and therefore regular. Even after the transformations below it will still be regular. So after the usual steps to convert the regular expression into a deterministic finite-state automaton, you will have a recognizer for what you want that operates in $O(k)$ time. Hopefully this idea will still be workable if there are bugs in what is proposed below.

The wrinkle is how to deal with the wildcard operator: ?. A wildcard in a wildcard string matches a 0 or 1 in a test string. But since we're trying to recognize wildcard strings, a wildcard in a wildcard string matches 0, 1, or ? in another wildcard string. This set is still regular, so we transform every occurrence of ? to the regular expression (0|1|?) where the vertical bar is the usual alternation operator. So if your whole set $S$ is {10??1, 0?1?0}, the resulting regular expression will be (10(0|1|?)(0|1|?)1 | 0(0|1|?)1(0|1|?)0)

As for adding strings to the machine, there's some recent work on changing a finite-state automaton incrementally. See this paper by Daciuk et al: "Incremental Construction of Minimal Acyclic Finite-State Automata".

Does this help?


Idea for a white-box PIT deterministic algorithm in polynomial time

Would this work? What is wrong?

No proof sketch that this is a polynomial time algorithm is given. The point where the algorithm might stop being a polynomial time algorithm is step 3:

  Being a univariate polynomial, it is trivial to normalise this polynomial and check if it is identically 0 or not.

Even so normalising a univariate polynomial is trivial from a conceptual point of view, it's unclear whether it can be done in polynomial time (or even polynomial space). For multivariate polynomials, it's obvious that polynomials like $(1+x_1)(1+x_2)\dots(1+x_n)$ can't be normalized in polynomial space. For univariate polynomials, the details of the problem formulation become important. If the input polynomial is given by an arithmetic circuit and the coefficients are from $\mathbb Z$, then repeated squaring will give you abundant examples of polynomials which cannot be normalized in polynomial space. (PIT is often done over finite fields, which avoids this sort of space explosion.)

The proof sketch that the algorithm works as intended has too many holes for being a valid mathematical proof. However, it is quite possible that there is a proper mathematical proof showing that the proposed algorithm works as intended, and this wouldn't even be a surprise. Here are some of the holes:

  $f$ should be a union of hypersurfaces (homogeneous polynomial)

This reads like a claim that $f$ is a homogeneous polynomial iff $f=0$ is a union of hypersurfaces (through the origin). But $f(x,y,z)=x^2+y^2-z^2$ is a homogeneous polynomial for which $f=0$ is not a finite union of hypersurfaces.

  Supposing $f$ is an homogenous polynomial (worst case), each hypersurface is able at best to make $f=0$ along $n−1$ of the Vandermonde line-vectors.

This seems to assume that $f(x_1,\dots,x_n)=\prod_i(\sum_j a_{ij}x_j)$, which might be yet another interpretation of "union of hypersurfaces". The hole in the proof here is that the "(worst case)" claim isn't proved. Note that $f(x,y,z)=x^2+y^2-z^2$ is a homogeneous polynomial, but it cannot be written in the assumed form.


Should reductions make us more or less optimistic for the tractability of a problem?

What is missing from the analogy is some notion of the relative distances involved.  Let's replace Alaska in our analogy with the moon:

You're an explorer, searching for a bridge between the North American and Asian continents. For many months you have tried and failed to find a land bridge from the mainland United States area to Asia. Then you discover that the mainland US is connected by land to the moon.  You are already confident that the moon is a vast distance away from Asia, so you can now be confident that North America is also a vast distance away from Asia by the triangle inequality.


Are there links between Geometry of Interaction and Geometric Complexity Theory?

No one knows if there are connections between GoI and GCT.

It's quite plausible, since both are used to analyze complexity, and since GoI is formulated in terms of monoidal categories and GCT is based on representation theory. However, to my knowledge there aren't any researchers who understand both well enough to say for certain.


Where does a C-like language without heaps belong in the automata hierarchy?

Assuming we have an unbounded stack and pointers, it's a Turing machine. Since the stack is unbounded, we can get by very easily using a CPS-like style. Whenever we need to allocate memory, we'll just do it on a stack frame, then continue with the computation on the next. If our stack frames were bounded in size, of course we'd be a finite state machine. Here's a little example machine with no imports whatsoever (including no malloc). Of course on a real computer we'll eventually get a stack overflow with this. This model could be easily adjusted to have correct space usage, by adding a new stack frame only once we need to allocate.

#define NULL 0

typedef enum {
    ZERO,
    ONE,
} symbol;

typedef struct tape {
    struct tape* left;
    symbol sym;
    struct tape* right;
} tape;

typedef enum {
    A, B, DONE
} state;

int handle(tape* tape, state state);
int move_right(tape* tape, state state);
int move_left(tape* tape, state state);

int main() {
    tape start = {NULL, ZERO, NULL};
    return handle(&start, A);
}

int handle(tape* tape, state state) {
    // do some stuff
    switch (state) {
        case B:
            switch(tape->sym) {
                case ZERO:
                    return move_left(tape, DONE);
                case ONE:
                    tape->sym=ONE;
                    return move_left(tape, A);
            }
            break;
        case A:
            switch(tape->sym) {
                case ZERO:
                    tape->sym=ONE;
                    return move_right(tape, B);
                case ONE:
                    tape->sym=ZERO;
                    return move_right(tape, B);
            }
            return move_right(tape, state);
        case DONE:
            return tape->sym;
    };
};

int move_right(tape* tape0, state state) {
    tape new_tape;

    if (tape0->right == NULL) {
        new_tape = (tape){tape0, ZERO, NULL};
        tape0->right = &new_tape;
        return handle(&new_tape, state);
    } else {
        return handle(tape0->right, state);
    }
};

int move_left(tape* tape0, state state) {
    tape new_tape;

    if (tape0->left == NULL) {
        new_tape = (tape){NULL, ZERO, tape0};
        tape0->left = &new_tape;
        return handle(&new_tape, state);
    } else {
        return handle(tape0->left, state);
    }
};


An invariance theorem for algorithmically random data in statistical learning

I think this is a similar approach to Shnor's Martingale characterisation of algorithmic randomness, I have sent you an email with more info, but it is a potential nice non-overfitting test and also alternative characterisation.


Here's a proof that the language is not Turing-complete: its Halting problem can be solved for all programs in your language. This language contains only single loops in sequence, and each loop consists of a finite number of numeric changes to the tape contents. I will gloss over the fact that BF is an 8-bit language, and grant you that the tape contents are all numbers $z \in \mathbb{Z}$. Let $(\alpha_k, \beta_k) \in \mathbb{Z}^{2}$ denote the interval of the tape walked on in statement #k, and let $\nabla_k \in \mathbb{Z}$ denote the amount the tape head moves during each iteration of statement #k. For example, for statment <+>>->+\n, $(\alpha_k, \beta_k) = (-1,3)$ because it moves one item to the left and 2 to the right, plus 1 for the position on which it started, and the net position change is $\nabla_k = 2$. Now, every statement can only increase and decrease its surrounding tape with some vector $v_k \in \mathbb{Z}^{\beta_k-\alpha_k}$, so the program reduces to following simple code:

Input: Infinite tape of zeros, except for a sequence $x$ of numbers starting at position 1

p = 1; // initial tape position

for k = 1..n {

$\quad$while (Tape[p] != 0) {

$\quad\quad$Tape[$p - \alpha_k$ : $p + \beta_k-1$] += $v_k$;

$\quad\quad$p += $\nabla_k$;

$\quad$}

}

Of particular interest is $v_{k,\nabla_k}$ and $v_{k, 2\nabla_k}$ and so forth, because they are the amount the machine will change the items it will inspect next. Now it is easy to solve the Halting problem for any program in your language. Suppose we are have arrived at statement #k and have tape contents Tape, with the tape head at $p$. If $\nabla_k$ = 0, then the head does not move in this loop, and we need only check whether T[$p$] - $m \times v_{k,-\alpha_k} = 0$ for some integer m. If $\nabla_k \not= 0$, then the machine will move across the tape at constant speed. Two things can happen: Tape[$p$] can become zero before the tape head reaches the end of the thus-far written tape - which can be checked in finite time - or it moves past the end of the tape into the unwritten region, at which point it must start repeating itself, which can also be checked in finite time (note that this must be on the positive side of the tape, with $p>0$, otherwise the head has fallen off the tape. It is possible to consider a two-way infinite tape for your language, but the argument still holds). It must start repeating itself in the sense that the contents in Tape[$p - \alpha_k$ : $p + \beta_k$ - 1] must be equal to that of the pervious iteration of loop #k. This is because once arrived in the unwritten region, Tape[$p + \beta_k$] = $v_{k, \beta_k}$, and Tape[$p + \beta_k - \nabla_k] = v_{k,\beta_k} + v_{k, \beta_k - \nabla_k}$, and so forth.

Solving this problem for all statements in a program decides whether that program halts. It is an interesting language nonetheless, and I wonder whether there are programs which have worst-case running times of $\Omega(|x|^2)$, although probably not, and where in the complexity landscape lies the set of languages decided by programs in this BF variant.


In [1], the authors formally define the notion of an "extended regex" with the intent of capturing the back-reference capability of POSIX/perl/emacs/etc style regexes. Exactly how closely their definition matches the exact POSIX specification is an exercise left to the reader.

Under their definition, extended regexes are a proper subset of Type 1 (context-sensitive) languages and incomparable with Type 2 (context-free) languages. They show that extended regexes are a subset of Type 1 languages by showing how to construct an equivalent LBA for any extended regex. They prove that they're incomparable with Type 2 languages by showing that $\{a^nba^nba^n|n \geq 1\}$ (which is not context-free) can be recognized by an extended regex while $\{a^n b^n | n \geq 0\}$ (which is context-free) cannot.

Câmpeanu, Cezar, Kai Salomaa, and Sheng Yu. "A formal study of practical regular expressions." International Journal of Foundations of Computer Science 14.06 (2003): 1007-1018.


Janson-type inequality, limited dependence

I'm posting a suitable answer that I found for this problem. The approach linked here does not exploit the fact that no $t$-tuples of elements of $\Omega$ are present in too many subsets $Y$ (for arbitrary $t$), but it does end up giving me a good enough bound anyway.


Are finite state automata with one register storage equivalent to push down automata?

As pointed out in the comments, the power of such devices depends on the operations that they are allowed to perform on the ''register''. Here is a classic example of a class that captures all regular, but not all context-free languages.

If you restrict a PDA so that there is only one stack symbol, apart from the bottom-of-the-stack, the device is called a one-counter automaton.
I'm unsure what a standard reference is, but you can have a look, for instance, at this paper by Valiant and Paterson in LNCS, vol. 2 (1973).

For such a device, the set of all possible stack configurations is infinite (non-negative integers), but when it comes to operations on the stack, you can only increment and decrement the value by $1$ and test for $0$. This class of automata is strictly less powerful than the class of all pushdown automata; restricting it further with determinism results in an even weaker class. Also note that if you go for two counters instead of one, then even with deterministic machines you reach undecidability (even for the word problem, i.e., given a word, decide whether it is accepted).

Some proofs and additional information can be found here and here.


Why should we believe that $NEXP \not \subset P/poly$

The best evidence is in my opinion follows due to the results of Ryan Williams on even a mild speed up of $CIRCUITSAT$ provides $NQP\not\subset P/poly$ which is an extremely strong result compared to $NEXP\not\subset P/poly$. It indicates to me that either we are missing something trivial which would separate $NEXP$ from $P/poly$ or (remotely plausibly) anything that separates $NEXP$ from $P/poly$ would separate any class slightly bigger than $NP$ from $P/poly$.
Update It seems all the more likely if we do not reach $NEXP\not\subset P/poly$ by speeding up GapCircuitSAT or CircuitSAT problems we might achieve a separation via embedding $NP$ problems in $MCSP$ in $PTIME$ or $LOGSPACE$. It is unclear if speeding up $SAT$ has anything to do with embedding or vice versa. Please refer Comparing SAT to MCSP reduction class separations and faster SAT class separations?.


This solution is by Gerhard Woeginger.

In order to prove that this problem belongs to NP,
we provide a polynomial-size certificate,
and then we show how to check it in deterministic polynomial time.

The certificate is just the following:
a set of integers $\{x_{u,v}\mid (u,v)\in E\}$.
Intuitively, $x_{u,v}$ is the number of times the solution path
traverses $(u,v)$.

We now describe the
verification algorithm.

We consider the subset $E'$ of edges of $G$, $E':=\{(u,v)\in E\mid x_{u,v}>0\}$. We check whether $E'$ induces a strongly (undirected)
connected subgraph of $G$.
We check whether

$\sum_{(u,v)\in E'} x_{u,v}=\sum_{(v,w)\in E'} x_{v,w}$, for all $v \in V\setminus\{s,t\}$;
$\sum_{(u,s)\in E'} x_{u,s}=\sum_{(s,w)\in E'} x_{s,w}-1$;
$\sum_{(u,t)\in E'} x_{u,t}=\sum_{(t,w)\in E'} x_{t,w}+1$.

For all $v \in V\setminus\{s\}$, we define $y_v:=\sum_{(u,v)\in E'} x_{u,v}$, i.e., the number of times the solution path gets into $v$. Moreover,
$y_s := \sum_{(s,u)\in E'} x_{s,u}$.
We check whether there exist real values $z_v$, for every $v \in V$, such that

$d_{min}(v)\cdot y_v \leq z_v \leq d_{max}(v)\cdot y_v$ (here $d_{min}(v)$ and $d_{max}(v)$ denote resp. the lower and the upper
bound of the rational interval $d(v)$), and
$\sum_{v \in V} z_v = h$.

We now sketch the correctness:

Steps 1. and 2. together check that the values $x_{u,v}$ for the arcs specify
a directed Eulerian path from $s$ to $t$ (we refer to http://www.maths.manchester.ac.uk/~mrm/Teaching/DiscreteMaths/LectureNotes/EulerianMultigraphs.pdf)

Steps 3. and 4. calculate $z_v$, for all $v\in V$, which is the total waiting time of the path on the node $v$. We observe that the (in)equalities of step 4.
form a linear program (LP), which can be solved in deterministic polynomial time (e.g., using the ellipsoid algorithm).


Set of functions computable in polynomial time

The notation $m^{O(1)}$  just denotes the set of functions of polynomial growth rate, so that would be indeed confusing. The class of functions computable in polynomial time is usually denoted $\mathsf{FP}$.


Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?

LMN theorem shows that if f is a boolean function$(f:\{-1,1\}^n \rightarrow \{-1,1\})$ computable by an $\text{AC}^0$ circuit of size M,

$$\sum_{S:|S|> k} \hat f(S)^{2} \leq 2^{-\Omega(k/(\log M)^{d-1})}$$

$\Rightarrow \hat f([n])^{2} \leq 2^{-\Omega(n/(\log M)^{d-1})}$

$\Rightarrow |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}$

$|\hat f([n])|$ is nothing but the correlation of f with the parity function $(\prod_{i = 1}^{n}x_i)$. Let $\delta$ be the fraction of inputs where $f$ differs from $PARITY$.

\begin{align}
1 -2 \delta \leq |1 - 2\delta| &= |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}\\
\Rightarrow \delta &\geq 1 - 2^{-\Omega(n/(\log M)^{d-1})}
\end{align}

So, if M is $poly(n)$, for $f$ to be equal to $PARITY$,

\begin{align}
\delta &\leq \frac{1}{2^n}\\
\Rightarrow 2^n &\geq 2^{(cn/(\log M)^{d-1})}\\
\Rightarrow (\log M)^{d-1} &\geq (c-1)n \\
\Rightarrow M &\geq 2^{\Omega (n^{1/d-1})}
\end{align}

So, LMN theorem not only proves that $PARITY$ cannot be computed by $AC^{0}$ circuits, it also shows that $PARITY$ has low correlation with $AC^{0}$ circuits.


Cvetcovic et all in Section 3.3 of "Recent results in the theory of graph spectra" goes over  algorithms for constructing graphs given spectrum in some special cases


Complexity of computing shortest paths in the plane with polygonal obstacles

Maybe I miss something, but if we consider the "easy" case, where all obstacles are points, then we have the problem of computing the shortest path between two vertices in a planar graph, which, if I am not wrong, it is known as sums-of-square-roots-hard.

PS. I wanted to add a comment and not an answer, but I can't find how. I apologize for that. Can the admins please help me with this.


How to treat dynamic memory allocation in algorithm analysis?

You want to read

Wilson et al., Dynamic Storage Allocation: A Survey and Critical Review, 1995

and references therein, especially those to papers by Robson. Here is a quote that answers your question:

  Robson put [in 1974] a fairly tight upper and lower bounds on the
  worst-case performance of the best possible allocation algorithm. He
  showed that a worst-case-optimal strategy's worst-case memory usage
  was somewhere between $0.5M\log_2 n$ and about $0.84 M\log_2 n$.

Here, $M$ is the live memory, and $n$ is the ratio of the largest to the smallest block.

(So, if your algorithm allocates blocks of wildly different sizes, then you may want to think more carefully about how memory allocation works. This doesn't seem to be the case for the example given in the question.)

PS: I was searching for a link to Robson's article and I found this related CSTheory question: Data structure for dynamic memory allocation


Can we perform an n-d range search over an arbitrary box without resorting to simplex methods?

No.

Rotated-box queries and simplex queries are both generalizations of slab queries, where a slab is the volume between two parallel hyperplanes.  Most lower bound proofs for simplex range searching actually assume that all query simplices are slabs of constant thickness.  In particular, Chazelle [2] proved the following theorem.

  Let $P$ be a random set of $n$ points, generated independently and uniformly in the unit hypercube $[0,1]^d$.  With probability at least $1/2$, any data structure of size $s$ that answers queries in $P$ for slabs of width $1/24$ in time $t$ in the semigroup arithmetic model must satisfy the inequality $st^d = \Omega((n/\log n)^d)$, or $st^2 = \Omega(n^2)$ when $d=2$.

The constants $1/2$ and $1/24$ are not particularly important here; different choices merely change the constant hidden in the $\Omega(\,)$ notation.  Thus, if you are allowed only linear space, your query time must be $\Omega(n^{1-1/d} / \operatorname{polylog} n)$; on the other hand, if you require polylogarithmic query time, you must use $\Omega(n^d / \operatorname{polylog} n)$ space.

More recently, Arya, Mount, and Xia [2] proved nearly identical lower bounds (under some reasonable assumptions about the underlying semigroup) for the even simpler case of halfspace queries, where a halfspace consists of all points on one side of a single halfplane.

tl;dr: Don't rotate your boxes.

Sunil Arya, David M. Mount, and Jian Xia.  Tight lower bounds for halfspace range searching.  Discrete & Computational Geometry 47:711–730, 2012.
Bernard Chazelle.  Lower bounds on the complexity of polytope range searching.  Journal of the AMS 2(40):637–666, 1989.


SMT solving with less-than theory and monotonic functions

I can think of 2 straight forward approaches

Directly add $\forall xy (x < y \Rightarrow f(x) < f(y))$.
Or Akcermannize the problem and add these as axioms for all pairs of terms.


Minimal context-free grammar for a regular language

Note that a CFG with $n$ non-terminals can generate a language consisting of a single (highly repetitive) word of length $2^n$, something that only a FSA with $2^n$ states will recognize. Hence in some case your minimal CFG will be much smaller than any FSA for $L$.

Actually, one can get much bigger reduction "factors". Take a deterministic Turing machine $M$ that happens to halt. One can define a CFG $G_M$ that recognizes exactly all words that are not (encodings of) the single run of $M$. This is a language $L$ consisting of all words except the single run, hence a regular language. The size of $G_M$ is polynomial in the size of $M$ while the size of a FSA for $L$ can be enormous (i.e., the single run can be very long, think Busy Beaver). Thus a regular language that requires an enormous FSA can be represented by a tiny grammar.

Your question evokes some notion of compression of regular languages. Indeed, the most popular schemes for compressing long words can be seen as some kind of CFGs,
see J. A. Storer and T. G. Szymanski,
Data compression via textual substitution.


Are there languages that are not in RE nor CO-RE?

Yes, there are some. There is actually an infinite hierarchy of languages which are less and less decidable, namely the Arithmetical hierarchy. Recursively Enumerable languages and their complements are at its level 1. An example of language which isn't RE or coRE is the set of Turing machines computing total functions.


List of theorems stating that P does not equal NP if and only if

Here is a one:

Mahaney's Theorem: There is no sparse NP-complete set if and only if $P \ne NP $
(under Karp reduction).

Another one is:

$P \ne NP$ if and only if $P \ne PH$


Why do computer scientists on the whole work under the assumption that P ≠ NP?

As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to have a solution found.
Other than this, this topic has been discussed at several other places, see https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP or https://rjlipton.wordpress.com/conventional-wisdom-and-pnp/.

Update: Or the very recent Chapter 3 here: http://www.scottaaronson.com/papers/pnp.pdf


Do good PCPs for NP give us good PCPs for the entire polynomial hierarchy?

The truth of a statement is different from it having a (short) proof in a proof system. The language is expressive but it doesn't mean that all valid statements in the language have short proofs in the system.

The theorem doesn't say that you can check the truth of a statement or even the correctness of an arbitrary long proof or of arbitrary theorems. It is for proofs of membership in an $\mathsf{NP}$ set, which by definition have polynomial size proofs (certificates) of membership. The theorem only says that you don't need to read the full (polynomial size) proof of membership in an $\mathsf{NP}$ set to decide its correctness.

One implication of the theorem is applying it to the set of theorems in an arbitrary language which have short (i.e. an arbitrary polynomial) proofs in an efficient proof system (i.e. it is decidable in polynomial time if a given string is a proof of a given statement). For example, theorems of ZFC which have proofs of size $n^{100}$ where $n$ is the size of the formula. If the proof system is sound then you can probabilistically verify the correctness of the theorems which have short proofs with reading a small part of their proofs. I think this is the intend meaning of the informal statement "proofs written up in strict mathematical language can be checked efficiently to any desired degree of accuracy without the requirement of reading the entire proof".


Transitive closure of an affine relation

An answer in case the monoid generated by $A$ for matrix multiplication is finite: Alain Finkel and Jérôme Leroux, How to Compose Presburger-accelerations: Applications to Broadcast Protocols, in FSTTCS 2002 (Foundations of Software Technology and Theoretical Computer Science)
Lecture Notes in Computer Science 2556, pages 145--156, DOI: 10.1007/3-540-36206-1_14, 2002 (see also the many references there).  The relation $R^k$ is represented by an effectively computable Presburger formula.

A more recent reference on the subject of actually computing the transitive closure is Marius Bozga, Radu Iosif and Filip Konečný, Fast Acceleration of Ultimately Periodic Relations, in CAV 2010 (Computer Aided Verification), Lecture Notes in Computer Science 6174, pages 227--242, DOI: 10.1007/978-3-642-14295-6_23, 2010.


Techniques for lower bounding spectral gaps in the quantum adiabatic algorithm

You might find the techniques here useful too:
http://arxiv.org/abs/1203.5801

A generalization of the above is on its way.

There are various references that give bounds for mixing times of Markov chains. Sometimes the gap of the quantum systems can be related to a the gap (largest to second largest) of a Markov chain, in which case the techniques such as rapidly mixing, high conductivity, gap upper bounds of Markov chains become relevant . Eg.
Persi Diaconis and Laurent Saloff-Coste, 'comparison theorems for reversible markov chains'

RM


This is $\Pi_2^p$-complete. Let D be the usual reduction from SAT to CLIQUE. Let w be a string in CLIQUE. Consider a $\Pi_2^p$ language $L$ expressed as the set of $x$ such that for all $y$ there is a $z$ with $(x,y,z)$ in $A$ for some $A$ in P (with polynomial-length bounds on the $y$ and $z$). Let $\phi_{x,y}$ be the formula that will be satisfiable if there exists a $z$ such that $(x,y,z)$ is in $A$.

Define $C_x(\phi)$ as follows: If $\phi=\phi_{x,y}$ for some $y$ then let $C_x(\phi)=w$ otherwise set $C_x(\phi)=D(\phi)$.

Then $x$ is in $L$ if and only if $C_x$ is a reduction from SAT to CLIQUE.


Ever used a tool like grep/awk/sed? Regular expressions form the heart of these tools.
You'll be surprised how much coding you can avoid by principled use of regular expressions - in "practical projects", like an email server.
If you're a CS major, you'll definitely be writing a compiler/interpreter for a (at least a small) language. If you've ever tried this task before and got stuck, you'll appreciate how much a little theory (aka context free grammars) can help you. This theory has made a once impossible task into something that can be completed over a weekend. (And it won the inventor a Turing award - google BNF).
If you're a CS major, at some point, you need to sit back and think about the philosophical foundations of computing, and not just about how cool the next version of the Android API is. On a related note, it is the job of the university not to prepare you for the next 5 years of your life, but to prepare you for the next 50. The only thing they can do in this regard is to help you think - think of automata theory as one of those courses.


Comparing Shannon-Fano and Shannon coding

Unfortunately, I also don't have an exact answer. After an initially wrong statement in my lecture notes, currently I do not provide a good bound on the Fano code (version 3.1 of lecture notes). I do, however, have a proof that shows that the Fano codes has an expected average codeword length of less than H(U)/log(2) + 1 - 2p_{min}. Unfortunately, I only have the proof for the case of a binary code, not a general D-ary code. This is why I haven't included this yet into the lecture notes. But I'm still working on it and hope that I will eventually be able to fix it in my lecture notes.

Note, however, that my result does NOT compare Shannon codes with Fano codes. It only gives a general upper bound on the Fano codes. I think it is very difficult to compare the two codes directly. In particular, I do not understand the proof given above and I have my doubts that it can be made rigorous, particularly not for D>2.


Information Theory used to prove neat combinatorial statements?

Moser's proof of the constructive Lovasz Local Lemma.  He basically shows that, under the conditions of the local lemma, the second-simplest algorithm for SAT you can think of works.  (The first simplest might be to just try a random assignment until one works.  The second simplest is took pick a random assignment, find an unsatisfied clause, satisfy it, then see what other clauses you broke, recurse, and repeat until done.)  The proof that this runs in polynomial time is perhaps the most elegant use of information theory (or Kolmogorov complexity, whatever you want to call it in this case) I've ever seen.


Natural theorems proven only "to high probability"?

$
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\maj}{maj}
$
This is not an example of what you are asking for, but it suggests how such an example can come about. Some combinatorial identities can be encoded as identities about polynomials of bounded degree $d$. If the polynomials are univariate, to prove the identity it is enough to verify it on $d+1$ points. However, if the polynomials are multivariate, and the degree is at least moderately large, the Scwartz-Zippel lemma may be the only practical way to verify the identity.

For an example of the univariate case, check this article by Zeilberger, resolving a question of Knuth. He proves a statement about statistics of permutations. For a permutation $\pi \in S_n$, let $\inv(\pi)$ be the number $|\{(i, j): i < j, \pi(i) > \pi(j)\}|$ of inversions of $\pi$, and let the major index $\maj(\pi)$ of $\pi$  be the sum of all integers in the set $\{i: \pi(i+1) < \pi(i)\}$ . Zeilberger proves that, for all $n$, the covariance of the two statistics is

$$
\mathbb{E}[(\inv(\pi) - \mathbb{E}[\inv(\pi)])\cdot(\maj(\pi) - \mathbb{E}[\maj(\pi)])] = \frac{1}{4}{n \choose 2},
$$
where all expectations are over a uniformly random $\pi$ in $S_n$. Zeilberger's proof is just a computer verification for $n \in \{1, 2, 3, 4, 5\}$, and an observation that the statement is equivalent to an identity between polynomials in $n$ of degree at most $4$.


Average message complexity for the election problem on graphs

I don't know of any results in distributed computing that state bounds on
average message complexity that are independent of the network topology.

Let's assume you have an algorithm $A$ with average message complexity
$\Theta(f(n))$, for some function $f(n)$. While such a universal bound
sounds quite powerful, the problem (as I see it) is that this tells you
very little about $A$. If someone implemented $A$ for a specific class of
networks, the $\Theta(f(n))$ bound becomes meaningless, as it is the
average over all network topologies and unique id assignments, whereas
worst/best-case bounds would still apply.


Natural computation based on fundamental forces

At present, quantum computation is the most powerful of computational model based on known physics to have been experimentally realised, and can efficiently simulate Maxwell's equations, and pretty much every other physical phenomenon you encounter in day to day life. As the others have mentioned, one exception to this is general spacetimes allowed as solutions in general relativity.

There has been quite a lot of interest in the computational power of computers with access to closed time like curves, for example. However there is absolutely no evidence that these exist in nature or that they can be created artificially. So, while there are potentially interesting computational models that incorporate general relativity in some form, there is significant doubt over whether such models can be realised, and before we can have the most general model of physical computation we need a solid theory of quantum gravity.

Further the interesting features of general relativity tend to only show up in regions of high curvature, which is very different from the almost flat region of spacetime we inhabit and the effects of relativity in such flat(ish) space offer no computational advantage.


$\mathcal{Z}(H)$ is the set of graphs obtained from $H$ by splitting vertices of degree $>3$ (the reverse operation to contracting an edge between two vertices, both of degree $\ge 3$, and where the contracted edge is not in any triangle). So (at least when all graphs are assumed to be finite) $\mathcal{Z}(H)=\{H\}$ iff $H$ has maximum degree 3.


Alternate notion of complexity based on gap between brute-force and the best algorithm?

One problem with formalizing the question is that the phrase "solution space for Problem A" is not well-defined. The definition of a solution space needs a verifier algorithm which, given an instance and a candidate solution, verifies whether or not the solution is correct. Then, the solution space of an instance wrt to a verifier is the set of candidate solutions that make the verifier output "correct".

For example, take the problem SAT0: given a Boolean formula, is it satisfied by the all-zeroes assignment? This problem is trivially in polynomial time, but its solution space can vary wildly, depending on which verifier you use. If your verifier ignores the candidate solution and just checks if all-zeroes works on the instance, then the "solution space" for any SAT0 instance on that verifier is trivial: it is all possible solutions. If your verifier checks to see if the candidate solution is a satisfying assignment, then the solution space of a SAT0 instance can actually be quite complex, arguably as complex as any SAT instance's solution space.

That said, the problem of "avoiding brute-force search" can be formalized in the following way (as seen in the paper "Improving exhaustive search implies superpolynomial lower bounds"). You are given a verifier algorithm that runs in time $t(n,k)$, on instances of size $n$ and candidate solutions of $k$ bits. The question is, *on arbitrary instances of size $n$, can we determine if there is a correct solution (wrt this verifier) with at most $k$ bits, in much less than $O(2^k t(n,k))$ time?

Note $O(2^k t(n,k))$ is the cost of trying all strings of length up to k, and running the verifier. So the above can be seen as asking whether we can improve on brute-force search for the given verifier. The area of "exact algorithms for NP-hard problems" can be seen as a long-term effort to study the difficulty of improving on brute-force search for certain very natural verifiers: e.g. the question of finding better-than-$2^n$ algorithms for SAT is the question of whether we can always improve over brute-force search for the verifier that checks if the given candidate solution is a satisfying assignment to the given SAT instance.

The paper shows some interesting consequences of improving on brute-force search for some problems. Even improving on brute-force search for "polynomial-size solution spaces" would have interesting consequences.


Distributed Elections using Logical Clocks (hints and tips)

Your example mostly needs the machines to agree on a "consensus" for which machine should be the leader. There are a lot of consensus protocols (proven to be correct). On top of consensus (with a proper failure detector) you can construct a "total ordering broadcast". I am no expert in this field so I can't recommend a particular paper but you can pick up one from this google search result
http://scholar.google.com/scholar?hl=en&q=total+ordering+broadcast+consensus&btnG=Search&as_sdt=2000&as_ylo=&as_vis=0


Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model

There is a question of why one would want to define black-box ZK in the random oracle model.
There are at least two reasons why people suggested the definition of black-box zero knowledge:

1) For a positive result, when you say that a simulator is "black-box zero knowledge" it automatically gives you a nice bound on its running time (i.e., $poly(|x|) \cdot time(V*)$ as opposed to $poly(time(V*))$) and it also may be useful to know that the simulator doesn't "look at the guts' of $V*$ and doesn't care if $V*$ is implemented using RAM, circuit, etc... While a random-oracle model simulator may be efficient, it's obviously not black-box, because it's supposed to somehow look at the execution of $V*$ and understand from it when $V*$ is evaluating a hash function. For this reason, there is a sense in which it doesn't make sense to say that a random-oracle model simulator is "black-box".

2) For a negative result, people use "black-box simulator" to capture a large class of proof techniques. In this case you can define black-box simulator also in the random oracle model and the definition that makes sense is what David said. In fact, for a negative result even not in the random oracle model, it's best if the result holds even if you allow the simulator $poly(time(V*))$ running time. Indeed, although it's not always stated, the negative results I'm aware of all have this property, since the cheating verifier $V*$ is typically a fixed polynomial algorithm that runs some pseudorandom functions, while the simulator can have any polynomial running time.


The problem is equivalent to online knapsack problem. Let $n$ represents the number of items. Let the knapsack has capacity $B$. Every item $i$, has value $v_i=1$ and weight $w_i=p_i$.

The offline optimal solution:

Sort the items in increasing order of their weights ($p_{\sigma(1)}\leq p_{\sigma(2)}\leq \cdots \leq p_{\sigma(n)}$ for some permutation $\sigma$).
Let $S\gets\emptyset$.
For $i\gets1$ to $n$: add $\sigma(i)$ to $S$ unless $\sum_{i\in S}p_i>B$.
For each $i\in S$, bid $b_i=p_i$ and for each $i\notin S$, bid $b_i=0$.

Claim: No online algorithm can achieve any non-trivial competitive ratio [1].

If we assume that $p_i=o(B)$ and $L\leq p_i\leq U$, then there is a competitive ratio of $\ln(U/L)+1$ [2].

For the regret, I don't know if there is some algorithm that achieves low regret (under some assumptions).


What's the difference between reduction strategies and evaluation strategies?

A reduction strategy is a function on Lambda that picks one redex (reducible expression) from all possible redexes -- depending on what you define as a redex.

Informally, an evaluation strategy is the order in which a language evaluates its arguments. A parameter-passing strategy is what the language hands to the function.

To understand the connection among these, study Plotkin's paper on Call-by-name, call-by-value, and the lambda calculus. He clearly spells out that you want to choose distinct AXIOMS depending on which order of evaluation you want. For Cb-name you want the old beta axiom and for cb-value you want a beta-value axiom. If you do that, all meta-theorems work out the same for both flavors. I showed later on (with many collaborators) that this idea generalizes to everything the world of PL has studied.

It's all technical, not some poem that can be interpreted. Just read up on it.

-- Matthias Felleisen

p.s. I will say that I think people will have an easier time understanding Plotkin's paper from Part I in our Redex book. But yes, it's 3x as long.


Jointly Establishing a Shared Random String for NIZK proofs of knowledge

I'm not sure the solution you have given works.

However, it can be adapted to work -- both for NIZK proofs and proofs of knowledge -- by using a coin-tossing protocol where "secure" here means in the sense of general secure two-party computation. This can be done based on one-way functions in polynomially many rounds, or based on stronger assumptions in constant rounds.

A good reference is Lindell's paper on coin tossing.


Deciding whether a 2nfa halts on every input on every branch

Lemma 1. $H_{\textsf{2nfa}}$ is decidable.

Proof.  Decide it as follows.  Given as input a two-way non-deterministic finite automaton $M_{\textsf{2nfa}}$:

Convert $M_{\textsf{2nfa}}$ into a two-way alternating finite automaton $M_{\textsf{2wafa}}$ such that the language of $M_{\textsf{2wafa}}$ is
$$L(M_{\textsf{2wafa}}) = \{x \in \Sigma^* : \text{ all execution paths of $M_{\textsf{2nfa}}$ on input $x$ halt }\},$$
that is, the set of inputs $x$ to $M_{\textsf{2nfa}}$ such that all execution paths of $M_{\textsf{2nfa}}$ on $x$ halt.  (An alternating finite automata has $\exists$-transitions and $\forall$-transitions.  Here we make every (non-deterministic) transition of $M_{\textsf{2nfa}}$ into a $\forall$-transition in $M_{\textsf{2wafa}}$, we don't use $\exists$-transitions, and we make the accept states of $M_{\textsf{2wafa}}$ be the halting states of $M_{\textsf{2nfa}}$.)
Convert $M_{\textsf{2wafa}}$ into an equivalent one-way NFA $M_{\textsf{nfa}}$. (See e.g. here.  I assume but have not verified that this conversion is computable. It appears to be computable, see the proof of Lemma 1, p. 296.)
Convert $M_{\textsf{nfa}}$ into an equivalent DFA $M_{\textsf{dfa}}$, and check whether $L(M_{\textsf{dfa}}) = \Sigma^*$ (all using standard techniques). Accept if so.  $~~\Box$


Since you are accessing $f$ in a black box manner, you have to query $f(x)$ at all $2^n$ points. Since otherwise, you can design two functions $f_1$ and $f_2$ that are consistent at all query points yet have different number of zeros.


On proving it is hard to compute $g^{rb}$ with knowledge of $r$, given $g, g^a, g^{ab}$

Here, I cranked out the black box optimum to detect any subgroup of $S_{n}$, still exponential but much faster than brute force over all $n!$ permutations.

Your problem is around $O(n  \log  rb)$ with repeated doubling if you have $g$ given to you as a permutation in $S_{n}$.


Here's how you could come up with tree-width concept yourself.

Suppose you want to count the number of independent sets in the following graph.

Independent sets can be partitioned into ones where top node is occupied, and ones where it is unoccupied

Now, notice that knowing whether top node is occupied, you can count number of independent sets in each subproblem separately, and multiply them. Repeating this process recursively gives you an algorithm to count independent sets based on graph separators.

Now, suppose you no longer have a tree. This means separators are bigger, but you can use the same idea. Consider counting independent sets in the following graph.

Use the same idea of breaking the problem into subproblems on the separator you get the following

Like in the previous example, each term in the sum decomposes into two smaller counting tasks across the separator.

Note that we have more terms in the sum than in the previous example because we have to enumerate over all configurations on our separator, which can potentially grow exponentially with size of the separator (size 2 in this case).

Tree decomposition is a data-structure to compactly store these recursive partitioning steps. Consider the following graph and its tree decomposition

To count using this decomposition you'd first fix values in nodes 3,6 which breaks it into 2 subproblems. In the first subproblem you'd additionally fix node 5, which breaks its part into two smaller subparts.

Size of the largest separator in an optimal recursive decomposition is precisely the tree width. For larger counting problems, size of the largest separator dominates the runtime, which is why this quantity is so important.

As to the notion of tree-width measuring how close graph is to a tree, one way to make it intuitive is to look at the alternative derivation of tree decomposition -- from correspondence with chordal graphs. First triangulate the graph by traversing vertices in order and interconnecting all "higher ordered" neighbors of each vertex.

Then construct tree decomposition by taking maximal cliques and connecting them iff their intersection is a maximal separator.

Recursive separator and triangulation based approaches of constructing tree decomposition are equivalent. Tree width+1 is the size of the largest clique in optimal triangulation of the graph, or if the graph is already triangulated, just size of the largest clique.

So in a sense, chordal graphs of treewidth tw can be thought of as trees where instead of single nodes we have overlapping cliques of size at most tw+1. Non-chordal graphs are such "clique trees" with some clique edges missing

Here are some chordal graphs and their tree-width.


Conditioning Probability on a Language With Measure 0

I don't know of a general approach to handle this, but in the case of $\omega$-regular languages, this has been done.
One approach, which I think is first introduced in the paper Computing Conditional Probabilities
in Markovian Models Efficiently is the following:
Given the language $L$, let $D$ be a DPW for it. Now, start by constructing a Markov chain $M$ that captures your distribution on $\Sigma^\omega$ (uniform, in your case).
Then take the product of $M$ and $D$.
Now, in the product MC, you have the property that the probability that the run is accepting is exactly the probability of $L$ (0, in your case, but it works for any $L$).
We now modify the product by "redistributing" the probability: whenever the MC reaches an end-component (ergodic component) in which the probability of acceptance is 0, the run restarts in the initial state. This ensures that all $0$-probability-of-acceptance runs get "another chance".
You can use this to essentially restrict yourself only to words in $L$, and now you can ask what the probability of another language is, in this MC, and this provides a reasonable definition of conditional probability.
I'm slightly sketchy on the details, but I think this should work.
I've used this technique in a paper here: https://arxiv.org/abs/1608.06567.


An excellent book is Rudiments of $\mu$-calculus. It's not cheap though. You'd be better of learning from survey articles such as

Bradfield, Julian and Stirling, Colin. Modal mu-calculi. In: P. Blackburn, J. van Benthem and F. Wolter (eds.), The Handbook of Modal Logic pp. 721-756. Elsevier (2006) or
Bradfield, J. C. and Stirling, C. P. Modal logics and mu-calculi: an introduction. In Handbook of Process Algebra (eds. J. Bergstra, A. Ponse and S. Smolka) 293--330. Elsevier (2001).


What is special about $2^{32}/\phi$ in cryptography?

One reason that $\varphi$ makes a particularly useful 'magic number' in this context is that the multiples $n\varphi$ are guaranteed to be 'maximally far' from integers (this has to do with the lack of large terms in the continued fraction for $\varphi$), and thus the sequence $\{n\varphi\}$ (or more accurately, its initial segments) is more uniformly distributed mod 1 than the sequence $\{n\alpha\}$ for any other irrational $\alpha$.

To give an example: suppose we choose a magic constant $C_\pi = \lfloor {2^{32}/\pi}\rfloor = 1367130551$.  Then $(355C_\pi)\mod {2^{32}} = 41157$, an unexpectedly small result for such a small multiple of our magic constant.  By contrast, if we use the magic constant $C_\varphi = \lfloor {2^{32}/\varphi}\rfloor = 2654435769$, then the smallest $n$ for which $|(nC_\varphi)\mod {2^{32}}| \leq 2^{16}$ (abusing notation a bit) is $n=28657$.  In practice, this can conceivably lead to things like unexpectedly large correlations between the values $X_n$ and $X_{n+k}$ of a linear congruential random number generator for some smallish $k$; for the most part, though, it's folkloreish black magic, based more on the intuition that 'small multiples of this number being small mod $2^{32}$ will be bad' than on any specific theoretical results.


Is $AC^0$ with bounded fanout weaker than $AC^0$?

A bound on fan-out of input bits and gates will make the size of the circuit linear. Let $k$ be a bound on the fan-out of the gates and inputs. It is a DAG with max out degree bounded by $k$ and max path of length $d$. The number of available wires in each level can increase $k$ times, and the number of available wires at top is $kn$, so the total number of wires in the circuit is at most $kn \sum_{i=0}^d k^i \leq k^{d+1} n$ which is $O(n)$.

Any $\mathsf{AC^0}$ function which requires super-linear size will separate the class of functions with bounded fan-out (applied also to input bits) from $\mathsf{AC^0}$. Here are some examples:

[CR96]: An $\mathsf{AC^0}$ function that need super-linear size is the $\frac{1}{4}$-approximate selector. A $\frac{1}{4}$-approximate selector is any function whose value is:

$0$ whenever the number of $1$s is at most $\frac{n}{4}$,
$1$ whenever the number of $0$s is at most $\frac{n}{4}$,
can be either $0$ or $1$ otherwise.

[Ros08] shows that the $k$-clique has $\mathsf{AC^0}$ functions complexity $n^{\Theta(k)}$ ($n^2$ input bits are possible edges of a graph with $n$ vertices). This gives a super line size lowerbound for $k\gt 2$.
It is probably possible to generalize the example in 2 can to existence of any nontrivial (requiring more than one bit) fixed induced substructure in a given unordered structure, e.g.:

existence of a path of length 2 in a given graph,
$\#_1(x)=2$,

since they require super constant number of gates depending on a bit which is not possible in $\mathsf{AC^0_{bf}}$.
The easiest example is a duplicator gate, i.e. a gate that creates $\omega(1)$ copies of its input bit. This is not possible in $\mathsf{AC^0_{bf}}$ since only $O(1)$ of gates can depend on each input bit.

Also any $\mathsf{AC^0_{bf}}$ circuit of size $S$ can be turned into a formula of size at most $k^dS$ and therefore has a $\mathsf{AC^0_{bf}}$ formula of size $k^{2d+1}n$ so any function of superlinear $\mathsf{AC^0}$ formula complexity will not be in $\mathsf{AC^0_{bf}}$.

References:

[CR96] S. Chaudhuri and J. Radhakrishnan, "Deterministic Restrictions in Circuit Complexity", 1996

[Ros08] Benjamin Rossman, "On the Constant-Depth Complexity of k-Clique", 2008

[Juk] Stasys Jukna, "Boolean Function Complexity: Advances and Frontiers", draft


Can all mathematical operations be encoded with a Turing Complete language?

But I've come away looking for proof. How do we know all this covers all computable functions? Is there an obvious branch of Mathematics for which this is not covered? Is there a shortcoming in Lambda Calculus where it is yet to cover off obscure Mathematical operations?

These are excellent questions! The best answer your question is for you to read Turing's 1936 paper On Computable Numbers, With an Application to the Entscheidungsproblem. It's a very surprisingly readable and accessible paper, and it is concerned with precisely this question.

To gloss the paper, there is no way to give a purely mathematical characterization of the computable functions, because what is computable is partly a question of physics -- it matters what sorts of computers we can build to compute with.

But something we can do is to think about the operations humans perform when doing computations, and once we have a list of these, then we can build a mathematical model of a machine performing these kinds of actions (as a state-transition system). Then we can mathematically analyze this model, of course -- for example to compare it with other proposed formalisms. Turing performed such an analysis, and built a model of the situation where you have a piece of paper and a pencil, and are permitted to write on the paper, and to read what you have written and perform new actions based on what you have read.

All of these operations are obviously physically realizable, and it turns out that (for number-computability) that all the various proposed models of computation, such as Turing machines, Church's lambda calculus, Post's rewriting systems, and Godel's systems of guarded equations are all equivalent.

So that's why people think that Turing-completeness = computability. However, note that it is not a priori impossible that we might discover some new physical principle letting us build machines that could let us decide the halting problem. If we did, then we would be compelled to revisit our definition of computability. (Or more likely, have the super-intelligent noncomputable AI we build using such exotic physics revisit the definitions for us!)


Dominations under oracles which is closed under complement?

For a given choice of complexity classes $\mathsf{C}$ and $\mathsf{O}$, by which we mean sets of languages and nothing else, the class $\mathsf{C}^{\mathsf{O}}$ is not well-defined: we need the definition of $\mathsf{C}$ to determine how oracle queries are defined.  Sometimes even then there could be ambiguities that need to be resolved, or the definition might not provide a reasonable notion of an oracle query at all.  (Attaching oracles to space-bounded complexity classes is one example in the first category, where the relativized classes we obtain are very sensitive to the exact capabilities of the oracle tape and whether we consider that it contributes to our space bounds.)

So, I don't think you can possibly say anything about $\mathsf{C}^{\mathsf{O}}$ without using the definitions of the classes, because if you don't use the definition of $\mathsf{C}$ you aren't working with a well-defined mathematical object.

If I have misunderstood your question, please clarify what sort of properties of $\mathsf{C}$ and $\mathsf{O}$ you permit to be used.


Will core decomposition get a maximal clique?

No. The illustration shows a graph (the graph of a cube with one corner truncated) and a valid removal sequence such that the vertices left at the point when the minimum degree equals $|S|-1$ (the two red vertices) do not form a maximal clique.

In this example, some other valid removal orderings could still produce a maximal clique. Probably there are more elaborate versions of this example that force the remaining clique to be non-maximal for all valid removal orderings.


Minimum BoundingBox on n-dimensional case

See chapter 18 here http://goo.gl/pLiEO. If the dimension is really high then bounding box is the wrong creature to work with. A better choice is the ellipsoid. See chapter 16 about John's ellipsoid - it can be computed efficiently using quadratic programming in some cases.


Assigning edge weights under shortest path constraints

Yes.

Consider an exact assignment as described in your second paragraph.

If any edge has a weight $w_{a,b} > c_{a,b}$ there must be an indirect path with total path weight $c_{a,b}$, This means the direct edge $ab$ will not be part of any minimal path.  We can lower the weight to $w_{a,b} = c_{a,b}$ without changing this.

Therefore, if an exact assignment exists, $w_{a,b} = c_{a,b}$ (for all a,b) will be an exact assignment.

It is clear that this is the unique assignment with minimal total weight.


Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?

It's NP-complete by a reduction from cliques in graphs. Given an arbitrary graph $G$, construct a bipartite graph from its incidence matrix, by making one side $U$ of the bipartition correspond to the edges of $G$ and the other side correspond to the vertices of $G$. Then $G$ has a clique of size $\omega$ if and only if the constructed bipartite graph has a set of $\binom{\omega}{2}$ vertices in $U$ that has at most $\omega$ neighbors on the other side of the bipartition.


Are there any intersections between Theory A and Theory B?

One cool example of work that straddles things that are typically considered theory A and things typically considered theory B are the lower bounds on the running time of the simplex algorithm with randomized pivoting rules, due to Friedmann, Hansen, and Zwick. The lower bounds rely on lower bounds for policy iteration algorithms for parity games, which are a tool used in formal verification and automata theory.


Maybe I am mistaken but I think it is possible to make the example from https://math.stackexchange.com/a/78835/131224 Eulerian. Just take an octahedron and place 3 new vertices on each of its faces, connected to each other and also to two of the vertices of the face in a circular order. So if the face was $abc$, then add $def$ and connect $d$ to all but $a$, $e$ to all but $b$ and $f$ to all but $c$. The same reasoning works but now every degree is even.


Necessary and sufficient conditions for the existence of a combinatorial algorithm for a given problem.

Some people in combinatorial optimization use the word "combinatorial algorithm" to mean "algorithm without using ellipsoid method (or interior-point methods)."  For example, Schrijver's Fulkerson-prize-winning paper has a title "A combinatorial algorithm minimizing submodular functions in strongly polynomial time."  The co-winners (Iwata, Fleischer, and Fujishige) also have "A combinatorial strongly polynomial algorithm for minimizing submodular function."

As far as I see the field of combinatorial optimization, people there actually try to give an answer to the posed question, and still struggle.  Cunningham's survey "Matching, matroids, and extensions" (Mathematical Programming B91 (2002) 515-542) is a bit old by now, but you can see how generalizations of Edmonds' blossom algorithm and concepts on matroid lead to combinatorial polynomial-time algorithms for other problems.  Please note that the field has been advanced since the survey, and good sources are probably some papers from IPCO (Integer Programming and Combinatorial Optimization).

I would like to point out that an big open problem is to find a combinatorial algorithm for the maximum independent set problem for perfect graphs running in strongly polynomial time.


Necessary condition for a graph to be Non-Hamiltonian

Asking whether a graph is non-Hamiltonian is CoNP-Complete so it is doubtful that such an algorithm exists.

If you are satisfied with a heuristic that provides a certificates of non-Hamiltonicity, see Bondy and Murty's book (page 53) for a sufficient, but not necessary, condition for non-Hamiltonicity:  If $G$ is Hamiltonian then, for every nonempty subset, $S$, of $V$:

$$ \omega(G - S) \le |S| $$

Where $\omega(G - S)$ is the number of connected components left in $G$ after removing the vertices in $S$.  A simple counterexample for the converse is the peterson graph: It passes the above test but is not Hamiltonian.


What are the classic papers from the recursion theoretic area of complexity theory?

Hajek, P. Arithmetical hierarchy and complexity of computation. Theoret. Comp. Sci. 8 (2): 227-237, 1979.  Started the study of the complexities of index sets (where their "complexities" often lie somewhere in the arithmetical hierarchy; see this answer to another question.)

On the study of polynomial-time degrees (buzzword="polynomial-time degree theory", for the sake of future searches) I'd say these papers are of interest (several of them are based on Ladner's technique):

Homer, S. Minimal degrees for polynomial reducibilities.  J. ACM 34(2):480-491, 1987.
Schöning, U. Minimal pairs for P. Theoret. Comp. Sci. 31: 41-48, 1984.
Downey, R. Nondiamond theorems for polynomial time reducibility. Journal of Computer and System Sciences 45(3):385-195, 1992.
Downey, R. and Fortnow, L. Uniformly hard languages. Theoret. Comp. Sci. 298(2): 303-315, 2003.
Fenner, S., Homer, S., Prium, R. and Schaefer, M. Hyper-polynomial hierarchies and the polynomial jump. Theoret. Comp. Sci. 262: 241-256, 2001.

Probably a forward and backwards reference search will find several more papers in the same area (though it's not that big an area!).


Looking for an online community specializing in the Z specification language, where I can ask questions

There is the comp.specification.z newsgroup, available on Google Groups.
There are some mailing lists:

ZFORUM mailing list
Zed Freelists mailing list

Additionally, there are mailing lists for tools that support the Z notation.  For tools that support ISO Z (or a similar dialect), I doubt anyone would object to a question about the notation itself if the above sources are not useful.  For example:

Community Z Tools (CZT) mailing lists
ProofPower mailing list


You can (without too much work) find a number $K$ such that if $|x| > K$ then $|a_n x^n| > \sum_{k<n} |a_k x^k|$, and so all roots are inside $(-K,K)$ and the distance between them is smaller than $2K$.


Well, this can be formulated as the problem of finding the ground state of an Ising-like Hamiltonian with 3-local terms. These don't occur naturally, but you would expect them to cool similarly to other systems, so simulated annealing should work just fine for the weighted version.


Your problem is in fact in $\textsf{DP}$-complete. (For $\textsf{DP}$, see: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp.)

You can show membership in $\textsf{DP}$ by reducing your problem to the $\textsf{DP}$-complete problem SAT-UNSAT, which consists of all pairs $(\varphi_1,\varphi_2)$ of propositional formulas such that $\varphi_1$ is satisfiable and $\varphi_2$ is unsatisfiable. Given an instance $(\varphi,T_0,k)$ of your problem, we construct an instance $(\varphi_1,\varphi_2)$ of SAT-UNSAT. The problem of deciding whether there is some $T_1$ such that $T_1$ differs from $T_0$ in at least $k$ places and $T_0(\varphi) \neq T_1(\varphi)$ is in $\textsf{NP}$, so (by $\textsf{NP}$-completeness of SAT) we can construct some $\varphi_1$ in poly-time that is satisfiable if and only if an appropriate $T_1$ exists. Similarly, the problem of deciding whether for all $T_2$ that differ from $T_0$ in at most $k-1$ places it holds that $T_2(\varphi) = T_0(\varphi)$ is in $\textsf{coNP}$, so (by $\textsf{coNP}$-completeness of UNSAT) we can construct some $\varphi_2$ in poly-time that is unsatisfiable if and only if this property holds for all suitable $T_2$.

$\textsf{DP}$-hardness can be shown by a reduction from SAT-UNSAT, that I will sketch here. Let $(\varphi_1,\varphi_2)$ be an instance of SAT-UNSAT. Without loss of generality, assume that $\varphi_1$ contains exactly one variable more than $\varphi_2$. Let $x_1,\dotsc,x_{n+1}$ be the variables occurring in $\varphi_1$, and let $y_1,\dotsc,y_{n}$ be the variables occurring in $\varphi_2$. Then let the formula $\varphi'_1$ be $\varphi_1 \wedge \bigwedge_{i=1}^{n+1} (x_i \leftrightarrow \neg x'_i)$, where $x'_1,\dotsc,x'_n$ are fresh variables. Similarly, let the formula $\varphi'_2$ be $\varphi_2 \wedge \bigwedge_{i=1}^{n} (y_i \leftrightarrow \neg y'_i)$, where $x'_1,\dotsc,x'_n$ are fresh variables. We then define the formula $\varphi$ as $\varphi'_1 \vee \varphi'_2$. We let $T_0$ be the truth assignment that sets all variables to false. Finally, we let $k = n+1$. We know that $T_0(\varphi) = 0$. Satisfying $\varphi$ by flipping $k-1$ bits in $T_0$ can be done iff $\varphi_2$ is satisfiable, and satisfying $\varphi$ by flipping $k$ bits can be done iff $\varphi_1$ is satisfiable. Together, $k$ is the minimal number of bits to flip to satisfy $\varphi$ if and only if $(\varphi_1,\varphi_2) \in$ SAT-UNSAT.


Computing size of permutation group from generators

The most efficient (and also simplest) algorithms for this are based on the notion of a strong generating set, introduced by Sims. Strong generating sets can be computed efficiently using the Schreier-Sims algorithm. Essentially any introductory book that talks about computational group theory should have a decent introduction to this (and if it contains an introduction to this that isn't decent, I'd think it's not a very good book). While the standard deterministic algorithm for this takes quadratic time, there is a randomized nearly-linear time algorithm. See Seress's book "Permutation Group Algorithms," Chapter 4 (the nearly-linear time Monte Carlo algorithm is Theorem 4.5.5).


Confusion in 2012 paper by Austrin and Håstad regarding hardness of approximating GLST

Following Emil's suggestion and using trial and error, define $P'(x_1, x_2, x_3, x_4) \equiv P(-x_1, x_2, x_3, x_4)$

Instances of $\text{CSP}(P')$ are isomorphic to instances of $\text{CSP}(P)$, via adding a negation in every constraint where $x_1$ appears. Then we apply the theorem on $P'$ after checking that the $\{3,4\}$ fourier coefficient is still positive. We can conclude $P'$ is resistant and therefore $P$ is as well.