What is an equivalent definition of mP/poly in terms of a Turing machine? P/poly is the class of decision problems solvable by a family of polynomial-size Boolean circuits. It can alternatively be defined as a polynomial-time Turing machine that receives an advice string that is size polynomial in n and that is based solely on the size of n.

mP/poly is the class of decision problems solvable by a family of polynomial-size monotone Boolean circuits, but is there a natural alternative definition of mP/poly in terms of a polynomial-time Turing machine?

There is a notion of a monotone non-deterministic and, more generally, alternating Turing machine in the paper Monotone Complexity by Grigni and Sipser. Since polynomial time is the same as alternating logarithmic space, a machine characterization of uniform $\mathsf{mP}$ is the monotone alternating logspace Turing machine. Providing such a machine with polynomial advice will then give a machine definition of $\mathsf{mP/poly}$.


Does mathematical model for conccurent computations exist? Turing machines can represent any computation. Can they also represent concurrent computations? Eg. multiple computations that can happen at the same time?

If yes, how are the concurrent computations represented and is it possible to convert them into turing machine?

And do they mathematically describe things like race condition and deadlocks?

As already suggested above, process algebra or process calculus is the place to start. Quoting freely from the respective Wikipedia page,

  History

  In the first half of the 20th century, various formalisms were
  proposed to capture the informal concept of a computable function,
  with μ-recursive functions, Turing Machines and the lambda calculus
  possibly being the best-known examples today. The surprising fact that
  they are essentially equivalent, in the sense that they are all
  encodable into each other, supports the Church-Turing thesis. Another
  shared feature is more rarely commented on: they all are most readily
  understood as models of sequential computation. The subsequent
  consolidation of computer science required a more subtle formulation
  of the notion of computation, in particular explicit representations
  of concurrency and communication. Models of concurrency such as the
  process calculi, Petri nets in 1962, and the Actor model in 1973
  emerged from this line of enquiry.

  Research on process calculi began in earnest with Robin Milner's
  seminal work on the Calculus of Communicating Systems (CCS) during the
  period from 1973 to 1980. C.A.R. Hoare's Communicating Sequential
  Processes (CSP) first appeared in 1978, and was subsequently developed
  into a full-fledged process calculus during the early 1980s. There was
  much cross-fertilization of ideas between CCS and CSP as they
  developed. In 1982 Jan Bergstra and Jan Willem Klop began work on what
  came to be known as the Algebra of Communicating Processes (ACP), and
  introduced the term process algebra to describe their work.1 CCS,
  CSP, and ACP constitute the three major branches of the process
  calculi family: the majority of the other process calculi can trace
  their roots to one of these three calculi.


Problems in AM or in MA What are the examples of problems known to be in $\mathsf{AM}$ (resp. $\mathsf{MA}$) which are not known to be in $\mathsf{NP}$ nor in $\mathsf{BPP}$?

For $\mathsf{AM}$, I know the following two examples:

Graph non-isomorphism: Given two labeled graphs $G$ and $H$, are they the same graph up to permutation of the vertices?
Lower bound protocol: You are given a set $S\subset\{0,1\}^m$ such that you know that either $|S|\le\alpha|U|$ or $|S|\ge 4\alpha|U|$ for some $0\le\alpha\le 1$, and such that $S\in\mathsf{AM}$ (that is, given $y\in U$, checking whether $y\in S$ can be solved in $\mathsf{AM}$), and you have to decide whether $|S\ge 4\alpha|U|$.

For $\mathsf{MA}$, I do not know of any example.

My refined question: Do we know other problems in $\mathsf{AM}$ or $\mathsf{MA}$, not known to be in $\mathsf{NP}\cup\mathsf{BPP}$?

I am not interested in problems for which the only proof that they belong to $\mathsf{AM}$ is by using one of these two protocols.

Edit: My main motivation is to be able to give examples of $\mathsf{AM}$ or $\mathsf{MA}$ algorithms to explain what these classes are.

[I'm posting this as an answer despite being in $\mathsf{PromiseMA}$ because a) it exhibits a different kind of $\mathsf{MA}$-style algorithm, and b) @PeterShor asked  and it was too long for a comment.]
Over any finite field $\mathbb{F}$, the following problem is in $\mathsf{PromiseMA}$:

Input: A set of $\mathbb{F}$-polynomials $F_1(\vec{x}), \dotsc, F_m(\vec{x})$
Decide: Is there no solution to $F_1(\vec{x}) = \dotsb = F_m(\vec{x}) = 0$ over the algebraic closure $\overline{\mathbb{F}}$
Promise: Either there is a solution over $\overline{\mathbb{F}}$, or there is a poly-size $\mathbb{F}$-algebraic circuit $C(\vec{x}, y_1, \dotsc, y_m)$ such that $C(\vec{x}, \vec{0}) = 0$ and $C(\vec{x}, \vec{F}(\vec{x})) = 1$ (identically as polynomials)

The $\mathsf{MA}$-style algorithm guesses the circuit $C$, and then verifies the two conditions using polynomial identity testing, which is in $\mathsf{coRP}$ by Schwarz-Zippell-DeMillo-Lipton.
Note that, without the restriction of poly-size, Hilbert's Nullstellensatz guarantees that there is no solution if and only if there is some circuit $C$ satisfying the above two conditions. (On the other hand, assuming $\mathsf{NP} \not\subseteq \mathsf{coMA}$, there are systems of equations coming from algebrizations of 3SAT for which the above poly-size promise is violated.)
(This is the basis of an algebraic proof system from recent joint work with Toniann Pitassi, but for the purposes of this answer similar ideas go back to an earlier paper of Pitassi's as well as her 1998 ICM talk, and to the so-called Nullstellensatz and Polynomial Calculus proof systems.)


$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$ Stephen Smale claims in Mathematical Problems for the Next Century that

$$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}.$$

Can someone sketch the argument or provide a reference?

Is there any similar result in the reverse direction?

$NP_{\mathbb{C}}$ (definition) and $P_{\mathbb{C}}$ (definition) are NP and P over complex numbers $\mathbb{C}$ using the Blum–Shub–Smale machine model.

As proved in [1], Boolean languages computable in $\mathrm P_\mathbb C$ are in $\mathrm{BPP}$. (They state it for $\mathrm P_\mathbb R$ without inequality tests, which amounts to the same thing.) On the other hand, Boolean NP-languages are computable in $\mathrm{NP}_\mathbb C$, hence

$$\mathrm{NP}_\mathbb C=\mathrm P_\mathbb C\implies\mathrm{NP}\subseteq\mathrm{BPP},$$

which is another way to state Smale’s claim. While it is not directly relevant to the question, note that also

$$\mathrm{NP}\subseteq\mathrm{BPP}\iff\mathrm{NP}=\mathrm{RP}.$$

[1] F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and K. Werther: On real Turing machines that toss coins. Proceedings of ACM STOC’95, pp. 335–342, 1995. doi:10.1145/225058.225155; preprint


Is $\mathsf{MA}$ equal to $\mathsf{NP}^\mathsf{RP}$? I haven't been able to find a statement relating $\mathsf{MA}$ and $\mathsf{NP}^\mathsf{RP}$ in the literature; pointers would be appreciated.

I believe they are equal:

$\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP}$:
The $\mathsf{NP}$ machine guesses Merlin's string, and the $\mathsf{RP}$ oracle verifies the string as Arthur would.
$\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA}$:
Merlin guesses the accepting computation of the $\mathsf{NP}$ machine, including all calls, as well as the outcomes of these calls, to the $\mathsf{RP}$ oracle. Arthur then verifies that the computation is valid and that all the guessed outcomes of calls to the $\mathsf{RP}$ oracle were correct. He uses amplification and union bounds to bound the overall total probability of error.

Is this correct?

In the first bullet, we would need the oracle to answer

YES, if Arthur’s check succeeds with probability $1$ (assuming the MA protocol has perfect completeness),
NO, if Arthur’s check succeeds with probability $\le 1/2$.

This sounds like a coRP algorithm, but the catch is that there is no guarantee that one of these two conditions applies for every possible input to the oracle. Thus, the oracle does not compute a coRP language, but a coRP promise problem, and the whole argument only shows that $\mathrm{MA}\subseteq\mathrm{NP}^{\mathrm{promiseRP}}$.


Does this problem related to subset sum have a name? I'm looking for research into this problem -- computational complexity, solution algorithms, approximation algorithms, etc. If it has a canonical name, that would help me look into prior research.

Suppose there are two sets of integers S1 and S2 that are subsets of the positive integers.

The sum of all numbers in S1 equals the sum of all numbers in S2.

Find all subsets of S1 and subsets of S2 such that the the subsets sum up equivalently between the two. For example:

S1 = (1,2,3,4) S2 = (2, 2, 3, 3)

solutions:

(1+2 = 3, 3 = 3, 4 = 2+2)
(1+2+3 = 3+3, 4 = 2+2)
(1+2+3+4 = 2+2+3+3)
(1+3 = 2+2, 2+4 = 3+3)
(1+3+4 = 2+3+3, 2=2)
(2+3 = 2+3, 1+4 = 2+3)
etc.

You could also frame this in terms of making all numbers in S2 negative, collapsing them into one set, and finding all permutation subsets such that each subset adds up to 0.

If the numbers in S2 are expressed as negative numbers, the problem could also be expressed as a graph in which each node is an integer, and the goal is to find all possible disjoint sets such that the members of each set add up to 0.

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

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

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

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


IPS upper bound for subset sum axiom I am reading the following paper

Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson ,"Proof Complexity Lower Bounds from Algebraic Circuit Complexity", 2016.

IPS is defined as follows:

  (Ideal Proof System (IPS), Grochow-Pitassi [GP14]). Let $f_1(x), \ldots , f_m(x) ∈ F[x_1, \ldots , x_n]$ be a system of polynomials. An IPS refutation for showing that the polynomials $\{f_j\}_j$ have no common solution in $\{0, 1\}^n$ is an algebraic circuit $C(x, y, z) ∈ F[x, y_1, \ldots , y_m, z_1, \ldots , z_n]$
  such that

  $C(x, 0, 0) = 0$.
  $C(x, f_1(x), \ldots , f_m(x), x^2_1 − x_1, . . . , x^2_n − x_n) = 1$.

Then:

  We then consider the subset-sum axioms, previously considered by Impagliazzo, Pudlak, and Sgall [IPS99], and show that they can be refuted in polynomial size by the C-IPS_LIN proof
  system where C is either the class of roABPs, or the class of multilinear formulas.

The subset-sum axiom is defined as follows:

  That is, we give such refutations for whenever the polynomial $\sum
_i α_ix_i − β$ is unsatisfiable over the boolean cube $\{0, 1\}^n$, where the size of the refutation is polynomial in the size of the set $A := \{\sum_i α_ix_i : x ∈\{0, 1\}^n\}$.

They have given a polynomial size refutation for the subset-sum axiom. Polynomial-size proofs for the complement of subset-sum should imply
NP=coNP, doesn't it? What am I missing?

First, Kaveh is correct that the verification for IPS is randomized, so all it would show is $\mathsf{NP} \subseteq \mathsf{coAM}$ (not $\mathsf{NP} = \mathsf{coNP}$). However, this alone would still be enough to collapse the polynomial hierarchy.

Second, I think the actual thing you are missing here is that the IPS proofs they give have size polynomial in the size of $|A| = |\{\sum_i \alpha_i x_i : \vec{x} \in \{0,1\}^n\}|$, which can be exponential in $n$, in general.


Is it right to call $2^{\sqrt{n}}$ "exponential"? In his answer to a previous question, Sadeq Dousti recalled the following terminology:

$f(n) = n^{\omega(1)}$ is called super-polynomial. (e.g. $n^{\log n}, 2^n, 2^{2^n}$.)
$f(n) = 2^{n^{\Theta(1)}}$ is called exponential. (e.g. $2^n, 3^{n^4}$.)
$f(n) = 2^{n^{o(1)}}$ is called sub-exponential. (e.g. $2^{n^{1/n}}, n^{\log n}$.)

Is this standard terminology?

In particular, I am interested to know whether it is OK to call $2^{\sqrt{n}}$ and other functions in $2^{n^{\Theta(1)}}$ exponential or not.

Edited after 1st answer: Yes! The issue is when you have a $2^{\sqrt{n}}$ lower bound. Can you say that this is an "exponential" lower bound?

I am thinking here of a lower bound for a combinatorial value, not for some time complexity where one has standard definitions for $\mathsf{E}$ and $\mathsf{EXPTIME}$. I now realize I probably picked the wrong keywords.

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

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

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

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

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


Are there variants of visibly pushdown automata that allow pushing of words onto the stack? I'm wondering, are there any papers or research dealing with visibly pushdown automata, but allowing words, rather than single letters, to be pushed onto the stack.

Alternately, a construction which allowed for symbols to be pushed on $\epsilon$-transitions could achieve the same goal.

Obviously, such variations can be formed, but I'm wondering if it ruins the closure and decidability properties that make VPAs interesting.

I'm looking at a construction where use the stack as a counter, incrementing it by constants based on the initial symbols read, then counting down based on other symbols read.

For anyone who doesn't know, visibly pushdown automata are ones where the alphabet can be divided into pushing symbols, popping symbols, and symbols not affecting the stack at all. The choice of pushing versus popping is entirely determined by the current symbol being read. They're closed under intersection, union, concatenation, star and complement, giving them a wealth of decidable properties.  See this paper for more.

With epsilon pushes

For the version with pushes on epsilon-transitions, the undecidability proof of universality of pushdown-automata can be adapted to this new setting, so we lose at least the following properties: closure under complementation, determinizability, decidability of universality and inclusion.

Proof scheme:
Take a Turing Machine $M$, we want to build a VPA $A$ with epsilon-pushes such that it is universal if and only if M has no accepting run.

We design $A$ such that a word is not accepted if and only it is of the form:

$$\#C_0\&C_0\$(\overline{C_0})^R\#C_1\&C_1\$(\overline{C_1})^R\#C_2\&C_2\$(\overline{C_2})^R\dots\#C_n\&C_n\$(\overline{C_n})^R$$
where

Each $C_i$ encodes a valid configuration of $M$
$C_0$ is initial, $C_n$ is accepting
$u^R$ is the reverse of a word $u$
$\overline{u}$ is a copy of $u$ using pop letters
$\#,\&,\$$ are special separation symbols not in the alphabet of $M$
$C_i\to C_{i+1}$ is always a valid transition of $M$

The VPA $A$ is forced to do pop on factors of the form $C_i^R$. $A$ can non deterministically guess a violation of either property, and verify it. The key is that it can either push on $C_i$, or do nothing, which allows to verify all conditions (actually guess their violations). In particular, it can guess that the first (or second) occurence of $C_i$ does not match $(\overline{C_i})^R$, by ignoring the other component. It can also guess that $C_i\to C_{i+1}$ is not a valid transition, by pushing both occurences of $C_i$, then popping one, push no $C_{i+1}$, and compare $(\overline{C_{i+1}})^R$ to the stack content. For other $C_j$ that are not part of the guessing, one component is pushed and the $(\overline{C_j})^R$ is popped.

Pushing words

As for the variants where words are pushed, it seems that the determinizability proof in the original paper on VPAs can be adapted to this setting. It suffices to adapt the construction so that stack symbols are of the form $(S,R,u)$ where $u\in A^*$ is a prefix of a word that can be pushed according to the transition function. When popping a letter $a$, $(S,R,va)$ is turned to $(S',R',v)$, where $S'$ and $R'$ are updated normally to reflect the current powerset construction status.
However, this time we a priori get a deterministic pushdown automaton that is not visibly pushdown. At least this means that equivalence and universality are decidable.


What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy? Background

  It is known that there exists an oracle $A$ such that, $PSPACE^A \neq PH^A$.

  It is even known that the separation holds relative to a random
  oracle.  Informally, one may interpret this to mean that there are
  many oracles for which $PSPACE$ and $PH$ are separate.

Question

  How complicated are these oracles that separate $PSPACE$ from $PH$.
  In particular, is there an oracle $A \in DTIME(2^{2^{n}})$ such that
  $PSPACE^A \neq PH^A$?

  Do we have any oracle $A$ such that $PSPACE^A \neq PH^A$ and $A$ has a known complexity upper bound?

Note: the existence of such an oracle may have ramifications in structural complexity theory.  See the following update below for further details.

Update with details on a lower bound technique

Claim: If $PSPACE = PH$, then for all oracles $A \in P/poly$, $PSPACE^A = PH^A$.

  Proof Sketch: Suppose that $PSPACE = PH$.

  Let an oracle $A \in P/poly$ be given.  We can build a polynomial time
  $\Sigma_2$ oracle Turing machine $M$ that for a given length $n$,
  guesses a circuit of size $p(n)$ using an existential quantification
  and verifies that the circuit decides $A$ by comparing the evaluation of the circuit and the query result for every length $n$ string
  using a universal quantification.

  Further, consider a decision problem that I'm referring to as
  quantified Boolean circuit (QBC) where you are given a quantified
  boolean circuit and want to know if it valid (similar to QBF).  This
  problem is PSPACE-complete because QBF is PSPACE-complete.

  By assumption, it follows that QBC $\in PH$.  Let's say $QBC \in
\Sigma_k$ for some $k$ sufficiently large.  Let $N$ denote a
  polynomial time $\Sigma_k$ Turing machine that solves QBC.

  We can intermingle the computation of $M$ and $N$ (similar to what is
  done in the proof of the Karp-Lipton theorem) to get a polynomial time
  $\Sigma_k$ oracle Turing machine that solves $QBC^A$.

  Informally, this new machine takes as input an oracle QBC (that is a
  QBC with oracle gates).  Then, it computes a circuit that computes
  $A$ on inputs of length $n$ (simultaneously pealing off the first two
  quantifiers).  Next, it replaces the oracle gates in the oracle QBC
  with the circuit for $A$.  Finally, it proceeds to apply the remainder
  of the polynomial time $\Sigma_k$ algorithm for solving $QBC$ on this
  modified instance.

Now, we can show the conditional lower bound.

Corollary: If there exists an oracle $A \in NEXP$ such that $PSPACE^A \neq PH^A$, then $NEXP \nsubseteq P/poly$.

  Proof Sketch: Suppose that there exists $A \in NEXP$ such that $PSPACE^A \neq PH^A$. If $NEXP \subseteq P/poly$, then we would get a contradiction.

  In particular, if $NEXP \subseteq P/poly$, then by the claim above we
  have $PSPACE \neq PH$.  However, it is known that $NEXP \subseteq P/poly$ implies that $PSPACE = PH$.

  (see here for some details on known results for P/poly)

I believe if you trace through the argument given, e.g., in Section 4.1 of Ker-I Ko's survey, you get an upper bound of $\mathsf{DTIME}(2^{2^{O(n^2)}})$. In fact, we can replace $n^2$ here with any function $nf(n)$ where $f(n) \to \infty$ as $n \to \infty$. This isn't quite what was asked for, but it's close.

In particular, using the translation between oracle separations and circuit lower bounds, and following Ko's notation, we have the following:

We will diagonalize over strings of length $t(n) = p_n(m(n))$ where $p_n(x) = x^n + n$ is "the" $n$-th polynomial (in some enumeration of poly-time algorithms) and $m(n)$ will be specified below.
Translating into circuit lower bounds, this means we're considering bounded-depth circuits on $2^{t(n)}$ inputs.
The requirement (see p. 15 of Ko) we need $m(n)$ to satisfy $\frac{1}{10} 2^{m/(d-1)} > d p_n(m(n))$ for all $n$. Here $d$ is the depth of the circuits we want to diagonalize against, or equivalently the level $\mathsf{\Sigma_d^p}$ of $\mathsf{PH}$ we want to diagonalize against. To diagonalize against all of $\mathsf{PH}$, simply choose $d$ to be a function of $n$ that is $\omega(1)$; we may choose such a $d$ that grows arbitrarily slowly, though (perhaps subject to some computability assumption on $d(n)$, but that should be no obstacle). If we make the guess that $d(n)$ is constant (even though it's not, but it will grow arbitrarily slowly), then we see that $m(n)$ around $2^n$ should work.
This means that $t(n) \sim 2^{n^2}$, so we are looking for a lower bound against circuits with $\sim 2^{2^{n^2}}$ inputs.
Trevisan and Xue (CCC '13) showed that one can find an assignment on which a given bounded-depth circuit on $N$ inputs doesn't compute PARITY with a seed of $polylog(N)$ length.
For us $N=2^{2^{n^2}}$, so $polylog(N) = 2^{O(n^2)}$. We can brute force over such seeds in $2^{2^{O(n^2)}}$ time and use the first one that works.

To replace the $n^2$ with $nf(n)$, just let $p_n(x) = x^{f(n)} + f(n)$ instead.

Interestingly, if I'm understanding correctly, I believe this implies that if one could improve the Trevisan-Xue...

...to a pseudodeterministic/Bellagio algorithm (see Andrew Morgan's comment below), one would get that $\mathsf{BPEXP} \not\subseteq \mathsf{P/poly}$; or
...to a nondeterministic algorithm that guessed $polylog(N)$ bits but then ran in $poly(N)$ time, and such that on any accepting path it makes the same output (cf. $\mathsf{NPSV}$), it would imply $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$; or
... to a deterministic algorithm, one would get $\mathsf{EXP} \not\subseteq \mathsf{P/poly}$.

On the one hand, this suggests why derandomizing the switching lemma further should be hard - an argument which I'm not sure was known before! On the other hand, this strikes me as a kind of interesting take on hardness versus randomness (or is this actually a new thing, oracles versus randomness?).


Isolation in Turing-complete reversible cellular automata I don't know much about the terminology and the results on cellular automata, but I would like to ask a question about an conjecture I thought.

Consider Turing-complete reversible cellular automata.

For instance, Wolfram's Rule 110 cellular automaton is Turing-complete, but, if I understand correctly, it's not reversible. However, it can be made reversible by converting it into a second-order cellular automaton and then implementing the second-order CA as a first-order CA with a larger cell state space.

My question is whether it's possible to define a finite region of cells that is completely isolated from the outside.

More specifically: if there exist an initial state of a finite connected region of cells (let's call it Vault), which is composed of a connected region Interior surronded by another region Wall, such that the state of the Interior at any time t depends only on the previous state of Interior.

My conjecture is that such isolated regions are impossible.

My intuition stems from the fact that Turing-complete reversible CA can be considered very simple models of physical reality (and proponents of the digital physics hypothesis argue that the physical world is actually a cellular automaton). If I understand correctly, totally isolated physical systems can't exist, thus I conjecture by analogy that this should also apply to all Turing-complete reversible CA.
(Turing-incomplete or irreversible CA can have isolated regions, but they are probably not good models of fundamental physical reality)

Has anybody already proved or disproved this assertion? Or do you have any thoughts about it?

UPDATE:

As Shor pointed out in the comments, the conjecture as stated above is false, since it is possible to use some states which are not required for Turing-completeness to achieve isolation.

I will try to reformulate the question in a way that the conjecture may possibly hold by adding more requirements on the cellular automaton.

I'm thinking of two reformulations based on two different additional requirements:

Minimal universality: As noted by Grochow, we can define a Turing-complete CA to be "Minimally universal" iff the CA obtained by removing one cell state (and the corresponding rules) is no longer Turing-complete.Thus, the conjecture is: There does not exist a minimally universal reversible CA such that isolated regions can be defined.
Total harnessability: We may say that the computational power of a Turing-complete CA is totally harnessable iff there exist undecidable properties regarding all cell states.More specifically, we define a CA to be totally harnessable iff $\forall s \in CellStates \ \exists$ a computable initial configuration $x(t_0,\,i)$, a finite set of cell indexes $Q$, a vector of cell states $\bar{q}$ containing $s$ and predicate $p(x,\,t)\ \equiv\ \bigwedge_{i \in Q}x(t,\,i)=q_i $ such that the question "$\exists t:\ p(x,\,t)=True$" is undecidable, and the question obtained by removing from predicate $p$ the conditions on state $s$ is decidable.Thus the conjecture is: There does not exist a totally harnessable Turing-complete reversible CA such that isolated regions can be defined.

The conjecture is not only false, but false for standard and seemingly-minimal models of reversible CA. Specifically, in Margolus' billiard ball model (with the Margolus neighborhood), suitably aligned large blocks of live cells act as barriers and mirrors, isolating anything beyond them.


Confluently Persistent String Data Structure I'm looking for a confluentially persistent data structure for a string - so far I'm looking at finger trees. That is, how would I resolve two edits to the same base tree, and would I be able to preserve the undo history? I'm assuming that some mutations would be mutually exclusive, and I'd need to reject one. That is, I'm under the impression that order matters.

Some specifics - I'll have a copy of the tree in each thread - each will be sending updates to a central thread that updates all the others. Each thread will be based on the central thread's tree.

What you seem to be looking for is not a data structure for strings themselves, but a grammar for representing concurrent actions on strings. The field of study for this is Operational Transformation: http://en.wikipedia.org/wiki/Operational_transformation


Size of complement of context-free language Let $L$ be a context-free language, $\bar L$ be its complement and $\bar L_n$ be the length $n$ words in $\bar L_n$.

  What is known about $|\bar L_n|$?

Note that it is known that $|L_n|$ is either polynomial (if $L$ is bounded$~$), or grows exponentially.
I wonder if anything similar might be true about $|\bar L_n|$.
Warning, $L$ is allowed to be ambiguous!

From the proof that determining if a CFL ${L}$ = $\Sigma^*$ is undecidable, the set of strings $ID_0\#ID_1^R\#ID_2\#ID_3^R\#\ldots\#ID_t$ where $ID_0,ID_1,\ldots,ID_t$ is a list of the configurations of an accepting nondeterministic TM, is the complement of a context-free language. So $|\overline{L}_n|$ can basically be any computable function less than exponential.


Proving properties about a compilation from one problem into another Say I have two problems A and B.

A is the shortest path problem with positive weights

B is the shortest path problem (with potentially negative weights)

I would like to show: There is no mapping m, from B to A such that for every instance I_B of B the exact solutions for m(I_B) is the same as for I_B.

What I would like to know is where can I find proofs of this kind?
How would you approach something like this?

Let's assume that the weights are integers (for both A and B), and that m must be onto.  You could also assume that m must be a bijection (i.e., one-to-one and onto) and it would make no difference; the proposition you present is still false.

The reason is that all weighted digraphs (I'm assuming that's what you mean, not that it matters) are isomorphic to each other.

Let's prove:  There exists a mapping m : B -> A s.t. for all instances I_B of B, the solution S(m(I_B)) = S(I_B).

To show this, we will construct this mapping m.  Further, we'll show that m is a bijection.

We will divide the set of all digraphs into partitions.  Each partition will contain all graphs of a particular number of nodes N, and a particular solution structure that makes all graphs in the partition isomorphic to each other, in the sense that all solutions paths are the same.  (We index each node in an N-node graph from 1 to N, and consider two solution paths to be identical iff they contain exactly the same indexes in the exact same order and both have N nodes.)

Observe that each such partition has a countably infinite cardinality, due to the fact that there are infinitely many weight possibilities for each edge.  (Proof omitted.)

Thus, to construct m, all we must do is map every member of a partition (in B) to another member of the corresponding partition (in A).  Obviously, B contains extra graphs, but both have all partitions with the same cardinality as the set of natural numbers.

Now, we have that m is a bijection because every element in each partition of B maps to a unique element in the corresponding partition of A...and every element of every partition of B can be mapped to for each partition of A.


The role of symmetry in geometric complexity theory? I'm not well versed in geometric complexity theory so my question could be trivial. I understand that GCT program  studies the symmetries of determinant and permanent to prove Valiant's Hypothesis: $VP\ne VNP$

  In simple terms, What is the invariant property? Which mapping (transformation) is applied to the determinant and permanent? How is the symmetry of permanent used to explain the difficulty of computing the permanent?

As for what invariant properties are being used, and what transformations are being applied to the permanent and determinant, see the answer to a related question.

As for how the symmetry is used to explain computational hardness: it's not. First, it's not just symmetry that is being used, but characterization by symmetries.  As discussed in another question of yours, symmetry can very well make a function easier to compute.

Second, even characterization by symmetries does not explain hardness - since both $det$ and $perm$ are characterized by their symmetries, but $det$ is easy. The idea instead is this: it should be easier to understand the algebro-geometric and representation-theoretic properties of functions that are characterized by their symmetries, and hence to carry out the GCT plan of attack.

Since most functions are not characterized by their symmetries, using characterization by symmetries in a crucial way also gives some hope of bypassing the natural proofs barrier, as discussed here.

(That characterization by symmetries should make understanding easier can be formalized a  tiny bit more as follows. Since GCT is studying the orbits of $det$ and $perm$, and there is a sort of duality between orbits and stabilizers, functions that are characterized by their stabilizers should have "special" orbits in some sense. I guess this alone doesn't actually say anything about how difficult it should be to understand these orbits. But understanding "generic" orbits can be very hard; having a nice property like characterization by symmetries at least gives us something to grab on to that we can try to use to gain more understanding.)


Does there exist an ontology for algorithms? It appears that algorithmic complexity theory has already figured out Kolmogorov complexity, when applied to representations of programs themselves, can already serve as a solid theoretical metric of enumeration and comparison for programs, given a common basis language.

Does there exist an online database that attempts to enumerate algorithms similar to the Human Genome Project according to a basis encoding or language?

[More of an extended comment.]

I think I disagree with the premise of your first paragraph... That being said, while I don't know of a database, there has been some work systematically studying small Turing machines. See Small universal monotone Turing machines, https://cstheory.stackexchange.com/a/20980/129, https://cstheory.stackexchange.com/a/11614/129. While some of this is interesting, I would say it has yet to "bear much fruit (i.e., understanding)." I hope someday it will.

There's also a mismatch between listing small Turing machines and understanding algorithms that are built by people (much as there is still a gap between listing all genes and understanding what they do, though not quite the same). Namely, an ontology of algorithms that are built by people should including things like those mentioned in Thomas Klimpel's comment. (Note: it should also include holographic algorithms, a relatively recent surprise in the ontology of algorithms!) But an ontology of small TMs looks completely different. Given how small a corner of the space of algorithms people have explored, and given the uncomputable problems involved, I highly doubt there would ever be a "complete" ontology of algorithms - either in the sense of small TMs or in the sense of all algorithms people would build. But I suppose having a partial one might still be interesting for some purposes...


How can one construct a densest graph with no k-clique? Given integers $k$ and $n$ with $2 \le k < n$,
  how does one construct a graph on $n$ vertices
  that contains no $k$-clique and has the maximal
  number of edges?

This sounds like basic combinatorics, but I don't know where to find the result.  Pointers would be welcome if this is well-known.

Ideally I would like a deterministic procedure to construct such a maximal graph in $n^{O(1)}$ time.

One graph with $n$ vertices that is guaranteed not to contain $K_k$ is $\overline{K_{n-k+2} + \overline{K_{k-2}}}$, the complement of the graph formed by the disjoint union of $K_{n-k+2}$ and $k-2$ isolated vertices.  Whenever one picks $k$ vertices from it, at least two of these must be from the subset which is completely disconnected, so they cannot form a clique.  This can clearly be constructed in polynomial time, and is quite dense for $k$ close to $n$.  However, this construction yields rather sparse graphs when $k$ is small relative to $n$, so it seems unlikely to be the optimal construction.

Turan's theorem exactly characterizes the densest graphs on n vertices with no k clique. The Turan graphs are the maximal graphs, and they're very easy to construct. Is this what you want?


Reference for Dudley's chaining integral Dudley's chaining integral is commonly used to bound Rademacher complexities.
I recall seeing several papers give this as the reference

@ARTICLE{MR512411,
  author = {Dudley, R. M.},
  title = {Central limit theorems for empirical measures},
  journal = {Ann. Probab.},
  year = {1978},
  volume = {6},
  pages = {899--929 (1979)},
  number = {6},
  coden = {APBYAE},
  fjournal = {The Annals of Probability},
  issn = {0091-1798},
  mrclass = {60F05 (28C20 60B10 60F17)},
  mrnumber = {MR512411 (81k:60029a)},
  mrreviewer = {P. R{\'e}v{\'e}sz}
}

but I don't think the result in question actually appears in that paper.
Could anyone point me to the definitive reference?

I think the proper reference is:

@article{Dudley1967290,
    Author = {R.M Dudley},
    Doi = {http://dx.doi.org/10.1016/0022-1236(67)90017-1},
    Issn = {0022-1236},
    Journal = {Journal of Functional Analysis},
    Number = {3},
    Pages = {290 - 330},
    Title = {The sizes of compact subsets of Hilbert space and continuity of Gaussian processes},
    Url = {http://www.sciencedirect.com/science/article/pii/0022123667900171},
    Volume = {1},
    Year = {1967},
    Bdsk-Url-1 = {http://www.sciencedirect.com/science/article/pii/0022123667900171},
    Bdsk-Url-2 = {http://dx.doi.org/10.1016/0022-1236(67)90017-1}}

See Theorem 3.1. for the relevant result, although stated in terms of continuity of Gaussian processes.


Website with TCS Fun Facts This interesting paper http://www.math.hmc.edu/~su/papers.dir/leitzel.pdf is about how to motivate students during a course.

One of the idea is to add some "fun facts" during the course for some reasons explained in the paper. The author give the address of the following website:
http://www.math.hmc.edu/funfacts/
which is only for maths.

Are you aware of a similar website for TCS?

Here are some interesting anecdotes about TCS giants. Some of them are dark, quite possibly the opposite of 'fun', but you also might get something you're looking for. This also might work best as a community wiki.

Kurt Gödel:

Gödel was concerned with developing a mathematical framework for describing the effectively computable. Both he and Alonzo Church developed candidate frameworks (Recursion and Lambda Calculus respectively), but neither satisfied him. In fact, Gödel acted very much as the ultimate skeptic - no proposal which satisfied all of his contemporaries seemed to satisfy him. He involuntarily became the de facto litmus test for effective computation. Alan Turing's A-Machines (we later began to call these Turing Machines...) were the first idea to satisfy Gödel, and this launched a lot of the original interest in Turing's paper. Curiously, Gödel later wished to revoke his support but things were already set in motion.
Gödel was a good friend of Einstein. In fact, they purportedly walked together often when they were both at Princeton. Supposedly Einstein once made a comment to a colleague implying his work meant very little to him; that the reason he chose to stay at Princeton was for his walks with Gödel.
He purported to have a proof that God exists.
Gödel was a very suspicious individual. His own work in Physics and Philosophy convinced him that work of Leibniz was suppressed by a conspiracy against him despite a lack of any solid evidence. In his later years he became increasingly frightened of being poisoned to death and would only eat food his wife taste-tested for him. At one point his wife became hospitalized for an elongated period, during which time he was afraid to eat anything and starved himself to death. It's interesting, but perhaps not fruitful, to speculate about Turing's suicide by poison and what role this may have played in Gödel's conspiracy theory.

Alan Turing:

The "Father of Computer Science". Turing's original work involved describing mathematically what we should think of as effective computation. Right before publication, having just learned of the lambda calculus of Alonzo Church, he scrawled down a proof which showed equivalence between his machines and Church's calculus.
Turing was a student of Bertrand Russel and also a Philosophy student of Wittgenstein. I believe I have heard Turing became very frustrated at his inability to penetrate Wittgenstein's philosophy and eventually retreated from the subject.
He is considered a war hero. Turing's machines, and in particular his modifications to the Bombe, helped the Bletchey Park code breaking effort in WWII to crack the German Enigma machines.
Because Turing was a homosexual and also likely because of his once high security clearance, the British Government striped him of his status and forced him to undergo extreme hormone treatment. Due to this persecution and other factors Turing commit suicide, by consuming an apple he had laced with cyanide. There is speculation as to why Turing chose to commit suicide this way. The British Government just recently released a formal apology for their actions, 70 years later.

John Von Neumann:

With influences well beyond Computer Science, Von Neumann may have been the last well known poly-mathematician. His work helped to develop quantum physics, game theory, theoretical computer science, PDEs, microscopy, systems architecture, functional analysis and more.
Von Neumann was entirely unimpressed by John Nash's seminal contributions to Game Theory. Von Neumann is reported to have shrugged and said, "[Nash Equilibrium] is just a fixed point theorem."
Von Neumann was known for his terrible driving. Supposedly the cause of many of his car accidents was the fact he insisted on reading at the wheel.
Unlike many other scientists in the Manhattan Project, including Einstein, who would later come to regret their involvement in the project and actively protested nuclear programs/stockpiling, John Von Neumann never had any regrets. He continued to work on the nuclear proliferation of the United States for some time.


Quantum Fourier Transform question regarding measurement When we use the quantum fourier transform, for a function, the output is entangled, so if a measurement is made on the output, the result may not be that of the function that one wanted in the first place. For a trivial example, consider addition of two polynomials, using DFT, or even FFT, this is straight forward, but if we consider the same setting in the quantum case, where FFT, or DFTs are substituted with Quantum gates, how can the result of the addition two polynomials be accomplished.

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

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

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

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

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


Formal representation of rings in computations While reading a paper about using algebraic methods to detect some induced subgraphs, it appears that edge ideal is an important tool connecting commutative algebra and graph theory. Since I'm not familiar with computations of algebraic objects, is there any good references or books on this topic? Particularity in representing a ring R on a Turing machine, and the complexity of deciding basic properties on R (say, the height of an prime ideal in R.)

Your questions are related to a field (no pun intended) called "Computer Algebra". I myself was looking for comprehensive surveys when I was working on algebraic methods to calculate various graph centrality metrics. I could not find good surveys, but this book was partially helpful. The research papers on this "topic" are scattered all over and often not explicitly categorized as "computer algebra". Reading algorithmic papers on isomorphism, factoring (integers/polynomials) and graph algorithms based on matrix multiplication might give you more insights.


How Univalence can be used for proofs about algorithm correctness I read a book on homotopy type theory. HoTT has the univalence axiom. This axiom seems to simplify working in category theory, but which other fields of mathematics it simplifies? I.e. how can I use it, for example, to simplify a proof of correctness of an implementation of red-black trees?

The univalence axiom is not a magic wand that solves all problems.

Univalence has an immense explanatory power because it makes mathematically precise the intuition that "isomorphic structures can be used interchangably". Mathematicians casually use this intuition to pretend that two isomorphic things are actually equal when they are not. Univalence formally justifies the practice.

In the HoTT book you will find many applications of the univalence axiom which simplify or improve the standard approaches, especially in combination with the higher-inductive types.

The computation of the fundamental group of the circle.
Development of category theory, as you observed.
The definition of cardinals is conceptually clean and well-motivated when we use truncation to define them, see chapter 10.
Some homotopy-theoretic theorems, such as Blakers-Massey and the Freudentahl suspenion theorem.

Please note that in order to measure "simplification" you have to include the background theory as well. For example, the standard treatment of the fundamental group of the circle includes: construction of real numbers, basic general topology, the topology of euclidean spaces, and the theory of covering spaces.

We do not at the moment have direct applications of the Univalence axiom in theoretical computer science because we do not have a good computational interpretation of univalence. There is the constructive cubical sets model which an important step forward, but some time will probably be needed before applications to specific problems in computer science appear.


Does there exist a polynomial time algorithm to determine whether an equation is a consequence of (x+y)*(y+z)=(x*y)+(y*z)? Consider the identity $C$
$$(x+y)\times(y+z)=(x\times y)+(y\times z).$$

Is the problem of determining whether an identity is a consequence of $C$ in universal algebra a polynomial time problem? This problem is in PSPACE since if $p=q$ is a consequence of $C$, then the terms $p$ and $q$ must have the same length and $q$ can be obtained from $p$ by just repeatedly replacing the operation $+$ with $\times$ and vice versa.

Algebras that satisfy identity $C$ are precisely the algebraic structures that can be used to produce commuting one-dimensional cellular automata (these cellular automata have two dimensions of time).

Note: We do not assume that the operations $+,\times$ are associative, commutative, or distributive in any way.

Moore, Cristopher; Boykett, Timothy. Commuting cellular automata. Complex Systems 11 (1997), no. 1, 55–64.

Yes, this problem is decidable in polynomial time.

Let $R$ denote the term-rewriting system given by reductions of the form
$$(r+s)\times(s+u)\longrightarrow(r\times s)+(s\times u).$$
Clearly, $R$ is strongly normalizing: indeed, each reduction step decreases the number of occurrences of $+$ in the term, hence any reduction sequence terminates after at most $n$ steps.

I claim that $R$ is confluent. By Newman's lemma, it sufices to show it is weakly confluent. Thus, consider a pair of single-step reductions $t\to t_0$ and $t\to t_1$; we need to find $t'$ such that $t_0\stackrel{*}{\to}t'$ and $t_1\stackrel*\to t'$. This is easy to do by case analysis of possible redexes. The trivial cases are when the redexes are disjoint (as then we can perform the two reductions in arbitrary order) and when they coincide (as then $t_0=t_1$).

The remaining case is when one redex is strictly contained in the other. Now, this means that one redex is of the form $(r+s)\times(s+u)$, and the other one is a subterm of $r$, $u$, or of one of the two occurrences of $s$. In the first two cases, the two reduction again commute, and we are done. This also works in the third case after we duplicate the second reduction to apply to both occurrences of $s$.

So, each term has a unique $R$-normal form, which can be computed in polynomial time just by applying reductions in arbitrary order until the term becomes reduced. Finally, $t=s$ is a consequence of $C$ if and only if the normal forms of $t$ and $s$ coincide.


How can the actor model be applied to allow pure functional languages to have side-effects? I just read this blog post which argues that monads might be too obscure or difficult to understand as the default "interface to the impure world" in purely functional programming languages; instead, it suggests that the actor model would be more comprehensible when it comes to pedagogy.  That may be true -- I do think that actors are easier to understand than monads -- but the post leaves a lot to be desired.  In particular, the author offers no examples of what this sort of actor-based purely-functional language would look like, and he doesn't seem to have followed up on the blog post since it was written a few years ago.

So my question is:  in what way can actors be leveraged to capture side-effects in a purely functional way?  How would source code in that hypothetical language look?  What advantages/disadvantages would that approach offer in comparison to monads (outside of the cosmetic differences)?

Erlang is an example. I actually don't know Erlang, so I'm going to use some pseudocode:

Suppose you have two threads, Alice and Bob. They talk by calling each other's Send member route, which blocks until the other end replies. Alice can keep some "mutable state" for a single integer as follows:

Alice:
  function main_loop(state):
     message = Receive()
     if message == "get":
        Reply(state)
     else
        Reply("Okay")
        main_loop(message)
  main_loop(0)

Bob:
  Alice.Send(100) // Store 100 into the mutable state
  Alice.Send("get") // obtain the 100
  Alice.Send(200) // Store 200
  Alice.Send("get") // get the 200


Understanding the No Free Lunch Theorem I came across the No Free Lunch Theorem via Jürgen Schmidhuber's paper on Universal Search and there were a couple remarks on NFL which stood out
to me. The first was that we can't define a uniform distribution on an infinite number of objects. Second, Schmidhuber argues that there's nothing inherently natural about the uniform distribution and I'm inclined to agree on this point as well.

Although I'm aware of maximum-entropy arguments in favour of uniform distributions, on an infinite number of objects it's more natural to observe an exponential distribution. Might there be a well-known counter-argument in the optimisation literature
to the points raised by Jürgen Schmidhuber?

Optimal Ordered Problem Solver
No Free Lunch Theorem

You're asking about optimization and universal search, BUT machine-learning is tagged and you're wondering about "a uniform distribution on an infinite" discrete set so perhaps this will be helpful. There's a classic No-Free-Lunch result in PAC learning which says that you cannot learn the concept class of all boolean functions on the integers in a distribution-free fashion. Meaning: there is no function $m=m(\epsilon,\delta)$ such that if you request $m$ or more iid labeled examples from any unknown distribution, you'll be able to guarantee an $\epsilon$-accurate classifier with $\delta$-confidence. The proof proceeds by taking a uniform distribution over a large enough support size -- big enough to thwart any given purported sample complexity $m(\epsilon,\delta)$. A shorthand for saying this might be "take the uniform distribution over the integers". Now we all know that's absurd, and the explanation above is the only way I know to make sense out of it (and also jibes with the No-Free-Lunch context).


Data Strcuture to represent dependencies amongst modules Consider several software modules $m_1, m_2, ... m_n$. Each module has some inputs and outputs and the inputs to some of the modules are dependent on the outputs of some other modes. For example, in the figure, module $m_3$ and $m_4$ are dependent on the output of module $m_1$. If we are given a set if inputs $I$ and a set of outputs $O$, the objective is to find a set of modules which produce this output.

For example, if the output set $O$ is $\{o_1, o_2\}$ then all of the modules would have to be used. However if the output set $O$ is $\{o_2\}$ then only $\{m_2, m5, m_7\}$ needs to be used.

A graph is a natural model for such an objective. Are there any alternative data structures to represent this description?

Consider a modification to the earlier example as shown in the figure below, where all the outputs produced are $o_1$ and the output set required is also $O = \{o_1\}$. In this scenario we have two possible set of modules which satisfy our goal of $O$ :  $\{m_2, m_5, m_7\}$ and $\{m_1, m_3, m_4, m_6\}$. We wish to select the set which minimizes the number of modules used, hence the set $\{m_2, m_5, m_7\}$ would be our desired set $O$. Would a graph still be the most natural representation of such a scenario or some other data structure would be better off?

Your problem is the following:

Given a dag $G$, with labels $\ell:V\to L$ on the vertices, and a set $O \subseteq L$, find the smallest subset $S \subseteq V$ of vertices such that for each $o \in O$, there is a vertex in $S$ labelled $o$.

This problem is NP-hard, by reduction from set cover.

(The reduction: given sets $T_1,\dots,T_n$ and universe $U$, define a dag with one source vertex for each $T_i$, one sink vertex per element of $U$, labelled with that element, and an edge $T_i \to t$ for each $t \in T_i$; and set $O=U$.  Then the smallest subset of vertices that meets the requirements is also the minimum set cover.)

Since it is NP-hard, you'll need to use any of the standard methods for dealing with NP-hardness: heuristics, an approximation algorithm, an exponential-time algorithm, etc.  I suggest reducing this to integer linear programming.  Add a zero-or-one boolean variable $x_v$ for each vertex $v$; for each edge $v \to w$, add the inequality $x_v \ge x_w$; for each label $o \in O$ in the output set, add the inequality $\sum_{\ell(v)=o} x_v \ge 1$, where the sum ranges over all vertices with label $o$; and then minimize the objective function $\sum_{v \in V} x_v$.  Then, apply an off-the-shelf ILP solver.  Of course this may be exponential time in the worst case, but I suspect it's about as you're likely to get in practice, within any reasonable amount of programming effort.

The data structure to use is a graph.  The problem remains NP-hard no matter what data structure you use, so choice of an appropriate data structure isn't going to make the problem any easier.


Number of permutations which have the same Kendall-Tau distance Input: The number of elements $m$ and an (positive) integer distance $d$.
Ouput: The number of permutations of $m$ elements which have Kendall-Tau distance $d$ from a fixed permutation.

I think there should be a closed formula. Does anybody know a good reference?

This StackOverflow question answers your question. You might also be interested in this OEIS sequence.


Face-splitting product of two Vandermonde matrices: When is is invertible? Let $A$ and $B$ be two $n^2 \times n$ Vandermonde matrices with coefficients $\alpha_1,\ldots,\alpha_{n^2}$ and $\beta_1,\ldots,\beta_{n^2}$. Let $M$ be the face-splitting product of $A$ and $B$, that is, the $n^2 \times n^2$ matrix whose $(i,kn+l)$ entry is $A_{i,k+1} \times B_{i,l} = \alpha_i^{k} \beta_i^{l-1}$ for $0 \leq k \leq n-1$ and $1 \leq l \leq n$.
Question: When does $M$ have full rank? Or, alternatively, what is the determinant of $M$ as a function of the $\alpha$s and $\beta$s?
I have tried to compute the determinant as one usually does with a Vandermonde matrix but this quickly becomes very messy, and so I was wondering if there was a simpler way of obtaining that.
Edit: Actually the answer in the special case where $\beta_i = \alpha_i - 1$ for all $1 \leq i \leq n^2$ would be sufficient for my needs.
(Just to give some context, I am trying to show that a certain problem is #P-hard; I can do polynomial interpolation from counting the number of perfect matchings of a graph, but I end up on a matrix that is similar to $M$ and now I need it to be invertible.)

Sorry if I am missing something, but isn't it always singular in your special case? The first column is identically $1$, the second column is $(\beta_1,\ldots,\beta_{n^2})^T$, and the $n+1$'th column is $(\alpha_1,\ldots,\alpha_{n^2})^T$. If $\beta_i=\alpha_i-1$ for all $1\leq i\leq n^2$, then the $n+1$'th column is a linear combination of the first and second columns, so it is singular, right?
EDIT: in response to the amended question in the comments, I think it becomes nonsingular if and only if the $\alpha_i$ are distinct (note that one direction is obvious; if $\alpha_i=\alpha_j$ for some $i\neq j$, then clearly there are two equal rows).
To see the other direction, suppose that the $\alpha_i$ are distinct, but the matrix is singular. This means the $n+1$'th column is a linear combination of the previous $n$ columns. Defining $f_i(x)=x^i(x-1)^{n-i}$ for $i=0,\ldots,n$, this means there exists $\lambda_0,\ldots,\lambda_{n-1}\in \mathbb{F}$ not all zero such that for all $i=1,\ldots,n+1$,
\begin{equation}
f_{n}(\alpha_i) = \sum_{j=0}^{n-1} \lambda_j f_j(\alpha_i);
\end{equation}
as this holds at $n+1$ distinct points, and both sides have degree $n$ in $x$, this means that $f_n = \sum_{j=0}^{n-1} \lambda_j f_j$ as formal polynomials, as well as functions (the injectivity of the map between polynomials of degree at most $n$ and functions, when the field has at least $n+1$ elements, is essentially the nonsingularity of the Vandermonde matrix in the first place).
To see that this is not possible, note that evaluating both sides at $x=0$ shows that $\lambda_0 = 0$, for all other terms vanish, so this coefficient must be zero because $f_0(0)\neq 0$. Because all remaining terms are now divisible by $x$, we may safely divide through and keep this linear relationship, and then apply the same argument to deduce that $\lambda_1=0$, and so on. But this implies $f_n$ is formally the zero polynomial, which clearly does not hold. Therefore, the matrix has full column-rank and so is invertible.


Is the Presburger arithmetic decision problem known to be outside of BQP or BPP? Presburger arithmetic is well-known to be decidable but intractable, requiring doubly exponential time even with nondeterminism (Fischer and Rabin, 1974).  I am wondering if it is also known whether the Presburger arithmetic decision problem remains intractable with quantum computation or even just randomized computation, and specifically whether it falls outside of BQP or BPP.  It would be profoundly humbling if such a seemingly weak mathematical theory, which doesn't even allow multiplication, gives rise to provably intractable problems.

Let $~{\mathrm{PRESARITH}}$ denote the decision problem of the truth of statements in Presburger Arithmetic. As you note, [Fischer+Rabin 1974] (PS manuscript) show that the nondeterministic time complexity of $\mathrm{PRESARITH}$ is at least $2^{2^{\Omega(n)}}$. In particular, $\mathrm{PRESARITH} \notin \mathsf{NEXP}$.
However, we have the containments
$$ \mathsf{
BPP \;\subseteq\; BQP \;\subseteq\; PP \;\subseteq\; PSPACE \;\subseteq\; EXP \;\subseteq\; NEXP
}
$$

Thus, it directly follows that $\mathrm{PRESARITH} \notin \mathsf{BQP}$, and in particular it is not in $\mathsf{BPP}$ either.


Graph rewriting with one-to-many pattern matching? In the single-pushout approach to graph rewriting, many nodes in a pattern graph can be matched to a single node of a target graph.

My question is if there is a notion of graph rewriting where the inverse is true: that a single node in the pattern graph can match to many nodes of the target graph. For example, the pattern graph $A \rightarrow B$ should be able to match a subgraph isomorphic to $X \rightarrow Y \leftarrow Z$, with the mapping $A \mapsto \{ X, Z \}, B \mapsto \{Y$}.  I'm especially interested in a definition where $A \mapsto \{X\}, B \mapsto \{ Y\}$ would not be a valid match for any graph that contains $X \rightarrow Y \leftarrow Z$ as a subgraph.

As an example application, consider the problem of for-loop desugaring. This for-loop:

for (int i = 0; i < n; i++) {
  if ( i % 3 == 0) {
    printf("Divisible by 3\n");
    continue;
  }
  printf("%d\n", i);
}

desugars to:

int i = 0;
while (i < n) {
  if (i % 3 == 0) {
    printf("Divisible by 3\n");
    i++;
    continue;
  }
  printf("%d\n", i);
  i++;
}

A key part of this desugaring -- that the "step" part of the for loop be inserted at the end of the loop and before every "continue" statement -- is most easily expressed as a rewrite on the control-flow graph, where that statement is inserted before every predecessor of the condition (except for before the loop runs).

Belatedly posting this answer:

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

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

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


FPT algorithm for mixed integer program It is known that every integer linear program parameterized by the number of variables is FPT (fixed parameter tractable). Is every mixed integer program parameterized by the number of integer variables also FPT?

The complexity of Lenstra's algorithm for mixed-integer programming in his paper runs as  $2^{O(n^3)}*poly(d, \phi)$  where there are $n$ integer variables, $d$ continuos variables, and $\phi$ is the binary encoding size of the problem.  This is not stated very explicitly in his paper, but the main thing to notice is that the complexity is primarily guided by the number of subproblems, which is $2^{O(n^3)}$.  Certain improvements allow a Lentra-type algorithm to have a complexity of $2^{O(n log(n))}$.  Other techniques allow for even n^n in terms of the number of integer variables.

Note that the method of Lenstra is easily applied to convex mixed integer optimization provided certain separation oracles exist.  This dates back to a book of Gretchel, Lovasz, and Schrijver.  Other results on semi-algebraic convex optimization exist for the pure integer case as an FPT.


Lengths of "all-accepted" words in Context Free languages If $L$ is a Context Free language, it can happen that for some $n$, all words of length $n$ are in $L$. If we consider the
set $A_L$ of such lengths represented in unary, we may guess that such set is Context Free (and hence regular), but it is not the case.
More formally; if $L \in CF$ define:
$A_L = \{ 1^n \mid |w|=n \Rightarrow w \in L \}$
There are CF languages for which $A_L \notin REG$.
The example I have in mind uses the sequence of tape configurations (alternating straight/reverse order like in the proof of the undecidability of $L = \Sigma^*$) of a valid Turing machine computation that on input $x$ (in binary), writes $1^x$ on the tape and halts.
Before spending more time in formalizing it, I wonder if there is a simpler example, or if I can find it in some books/papers (I made some searches but probably I'm using the wrong terms).

The shortest word in $A_L$ is not bounded by a recursive function in the size of a given context-free grammar describing $L$. See here for more results in that direction:
https://doi.org/10.4230/LIPIcs.STACS.2020.16


Approaches to GI inspired by knot problem GI and Knot Problem both are problem of deciding structural equivalence of mathematical objects. Are there any results establishing connections between them? Nice connections of knot problem to statistical physics have been explored via knot polynomials, are there similar results for $GI$?

It would be particularly helpful to know if there are any standard results/warnings/suggestions/comments before one start looking into $GI$ motivated by knot problem. Actually, I was wondering if its recommended to explore in this direction for my master's thesis. I am interested in quantum/classical approaches to $GI$ and algebraic problems. Any other suggestions are welcome.

One connection is that graph isomorphism and knot isomorphism are both special cases of 3-manifold homeomorphism. In the knot case, two knots are isomorphic if their complements (manifolds formed by deleting the points of the knot from 3-space) are homeomorphic.

And in the graph case it's possible to transform graphs into manifolds in such a way that the graphs are isomorphic if and only if the manifolds are homeomorphic. I wrote a comment about this on a Google+ post last December, but unfortunately not on a post I can share. The construction is to start with a manifold for each vertex v, in the form of the complement in a 3-sphere of a bouquet of degree(v) loops (connected together at a common vertex). For each edge uv, connect the manifolds for u and v together by a surgery, and link one loop from u and one loop from v across the surgery ball. Then every isomorphism of graphs lifts to a homeomorphism of the resulting manifold (this would be true even if we just used surgery on 3-spheres without the bouquets) and the bouquets prevent the manifold from having extra homeomorphisms that don't come from the graph.


Succinct data structures survey? Fischer's paper this month reminded me how little I know about the art of succinct data structures, and algorithms to use them.

For those that don't know about succinct data structures:

  Given a combinatorial structure, with
  a(n) distinct configurations, and a
  known "useful" representation $R(n)$.
  Is there a "succinct" data structure
  that takes storage of around
  $\lg(a(n))$ bits yet lets us perform
  operations as fast as we can with the
  normal representation $R$?

The top ones I am interested in if anyone would like to entertain a discussion

Suffix Arrays. They are a subset of all permutations.
Ordered Trees. They are a subset of all binary "parenthesis" strings (the matched variety).
All nearest smaller values, as in the paper (1). Not only can you compress in both dimensions; the allowable "smaller value" arrays in one direction are a small subset of lists $\{0,...,n-1\}^n$ , and thus you need to store less than $n \lg(n)$ bits.

Also check out the thesis of Ankur Gupta, with emphasis on compressible data.


Number of cycles in a Graph How many cycles $C_k$ $(k \geq 3)$ are there in a $n $ vertex graph such that graph doesn't have any cycle $C_m$ $(m>k)$.

For example $n=5$, $k=3$, then graph will have at most two $C_3$'s so that $G$ will not have any $C_k (k > 3).$

I am thinking that there are $O(n)$ cycles will be there satisfying above conditions.

Can some one help me out.

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

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


Data structure that allow efficient tag based lookups I am looking for a highly efficient data structure for storage of data similar to the following.

Id    Tags   Order1 Order2
--------------------------
1     1,2     1      1
2     2,5     2      3
3     1,7     4      7
4     6       3      0

I need to be able to query this structure in such a way that it would give me a list of all ids containing an expression of tags - supporting AND and OR and NOT operations. Eg. ((1 or 2) and not 7)

I also need to be able to specify the ordering of the results (Order1 or Order2) and be able to specify maximum rows returned with an optional offset. Performance for the fetch of the first 30-100 results is key.

Finally, I need a cheap way to lookup "tag relations" for example I want to know which tags "relate" to tags (1 OR 2) and in what frequency. Meaning which tags appear in the same set as 1 OR 2 ... ordered by frequency.

Any idea of what data structure (or set of structures) would be highly efficient for this kind of work?

(I would like to use this as a proof of concept for redesigning the tagged pages of the SE family of sites)

This is not exactly an answer of an efficient data structure, but rather an elaboration on the comments of @bbejot and @Kaveh giving a hand-waving argument for why given the current question we should not expect something that does a lot better than searching the whole database. The argument is based on a reduction from SAT, the exponential time hypothesis, and a lot of hand-waving.

Assume we have upto $n$ different tags, then we can think of each id as being associated with a bitvector $x$ of length $|x| = n$ where $x_j = 1$ if we have the $j$-th tag, and $x_j = 0$ otherwise. Since there is no real restrictions on what the database looks like, I can assume it has ids $1$ through $2^n$ with the $k$-th id having an associated tag vector of $k$ written in binary. The order fields can be arbitrary, since they only make the problem harder. Now, if we are given an arbitrary query of $AND$, $OR$, and $NOT$s then this is just asking a SAT question on $n$ variables. By the exponential time hypothesis, we can't expect this to be much faster than $2^n$... or in other words, we can't expect this to be much faster than searching the whole database.

We shouldn't expect efficient search in the length of the query (by reduction to SAT). We also shouldn't expect much better than looking at all the items in the database by the exponential time hypothesis.

To hope for an efficient data-structure for this question, we will have to make some serious assumptions on the structure of the database that are not made in this question. For instance, if we assume a special structure on the queries (such as CNF) then we can hope for something more efficient. An alternative assumption is on the structure of the database. We could probably assume that given $n$ tags, only a small fraction of the tags will be present on any given id (say a logarithmicly few $1$s). This is not an unreasonable assumption given the application of tagged questions (what use are tags if almost every single tag is used for a question).


Analytic solutions in semidefinite programming (SDP) From my experience in the application of semidefinite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For example, there are SDPs whose solution is the fidelity of two operators or the trace norm of an operator. Does anyone know of more examples? Or more importantly, is there a general theory behind this notion of analytic solutions?

There are many examples in quantum information and computation where quantities of interest are expressible as optimal values of semidefinite programs. Here are a few beyond those mentioned in the question:

The optimal probability to correctly distinguish states chosen from a known ensemble is expressible as an SDP. (See arXiv:quant-ph/0205178 .)
The general adversary bound, which characterizes the number of queries needed to compute a function by a quantum algorithm in the query model, is represented by a semidefinite program for each possible input length of the problem being considered. (See arXiv:1011.3020 for further details and references.)
There exists a hierarchy of semidefinite programs that characterizes the set of separable density operators. (See arXiv:quant-ph/0308032 .)
Quantum interactive proof systems and the study of quantum coin-flipping protocols are closely tied to semidefinite programming. Suppose you have an interaction between two parties, say Alice and Bob, who exchange quantum information. If you fix one of the two parties, say Alice, and you ask what the optimal probability is for Bob to force Alice to output a particular result, then you can phrase this optimal probability as a semidefinite program. (There are many references here, including http://dl.acm.org/citation.cfm?id=335387, arXiv:quant-ph/0403193, arXiv:0907.4737, arXiv:quant-ph/0611234, arXiv:1003.0038, arXiv:0711.4114, arXiv:1104.1140 .)
The optimal probability for cooperating players Alice and Bob to win an XOR game can, through the use of a well-known theorem of Tsirelson, be phrased as a semidefinite program. This leads to a perfect parallel repetition theorem for quantum provers in XOR proof systems. (See arXiv:quant-ph/0608146 .)
The completely bounded trace norm (or diamond norm) of a mapping from matrices to matrices can be expressed as an SDP. This norm is useful for defining a physically motivated measure of distance between quantum channels.
(See arXiv:0901.4709 for the SDP.)

These SDPs do not all necessarily have analytic solutions, but they have the same flavor as the examples mentioned in the original question in that they represent interesting and arguably fundamental quantities in quantum information and computation. There are other examples as well -- these just happen to be ones I'm familiar with.

The original question asks if there is a general theory behind the existence of analytic solutions to SDPs. I am not aware of such a theory, and cannot see much hope for one to exist. If you write down a random SDP, there will probably not be a nice closed form for the solution.

The reality, at least as I view it, is that things work in the other direction. The SDPs for the fidelity and trace norm mentioned in the original question were specifically designed to represent those quantities: it is not an accident that the optimal solutions were given by such nice and important functions. If you have another quantity in mind, you might be able to express it as an SDP in a simple way by using some thought to come up with the SDP... but going in the other direction, from an SDP to an analytic solution, seems certain to be hard in general.


Do we have any nontrivial uniform circuits? Given an algorithm running in time $t(n)$, we can convert it into a "trivial" uniform circuit family for the same problem of size at most $\approx t(n)\log t(n)$.
On the other hand, it might be that we have much smaller uniform circuits for that problem, even if $t(n)$ is an optimal running time. The circuits may take longer than $t(n)$ to generate, but they are small.
But do we actually know how to build such things? I think the initial question to ask is

(1) Do we have any constructive examples of nontrivial uniform circuits, i.e. uniform circuits whose size is smaller than the best-known running time of any algorithm for the same problem?

Now, I believe that if a problem is in $\mathsf{DTIME(t(n))}$, then we have an exponential-time algorithm to find optimal circuits using an exhaustive search: Given $n$, we write down the answers on all $2^n$ inputs (taking time $(2^n)t(n)$); then we enumerate all circuits on $n$ inputs in increasing size until one is found that gives all the correct answers. The search terminates at either the size of the trivial conversion, $t(n) \log t(n)$, or the truth table of the function, $2^n$ if outputs are $\{0,1\}$. (Edit: Thomas points out that the bound is $O(2^n/n)$ due to Shannon/Lupanov.)
So we have an unsatisfactory "yes" to question (1): Take a language that is hard for any time above $2^n$, but still decidable; the above procedure outputs a truth table of size $2^n$.
So we should refine question (1). I think the two most interesting cases are

(2) Do we have any constructive examples of polynomial-size nontrivial uniform circuits? (Even if they are generated by very slow algorithms.)
(3) Do we have any constructive examples of polynomial-time generatable, polynomial-size nontrivial uniform circuits?

This may be too much to ask. How about an easier question: Do we even know that such a thing is possible? Perhaps no nontrivial uniform circuits exist?

(4) Is the following statement known to be false for any $s(n) = o(2^n)$? (Edit: $o(2^n/n)$, thanks Thomas.) "If a language $L$ has uniform circuits of size $O(s(n))$, then it also has algorithms running in time $\tilde{O}(s(n))$." (If so, then what about when "uniform" is replaced with "polynomial-time-uniform", "logspace uniform", etc?)

Finally, if the above questions are too hard,

(5) Do we have any constructions of uniform families of circuits that are not simply conversions of algorithms into circuits (or writing down the truth table)?

Postscript. An expert I asked about this mentioned "On Medium-Uniformity and Circuit Lower Bounds" (pdf), Santhanam and Williams 2013, which maybe is the most closely related work, but it proves lower bounds (that poly-time-generatable circuits are not too powerful). I'd be interested in any other related work!

Here are answers to your last two questions.

(5) Sorting networks are uniform circuits that sort as fast as the best RAM algorithms, but are definitely not just conversions of RAM algorithms (e.g. quicksort). [AKS83,G14]

(4) Yes, for any $s(n)=(1+\varepsilon) \cdot 2^n/n$ with $\varepsilon>0$, but for a silly reason: Every function is computed by a circuit of size $(1+o(1)) \cdot 2^n/n$. (Shannon proved this up to a constant and Lupanov got the optimal constant.) By the time hierarchy theorem, there exists a function $f$ with uniform time complexity between $\Omega(3^n)$ and $O(n \cdot 3^n)$. This gives a counterexample: $f$ has circuits of size $O(2^n/n)$ (which I think are computable in $2^{\mathrm{poly}(n)}$ time) but is not computable in $\tilde{O}(2^n/n)$ time. You should probably ask for $s(n) = o(2^n/n)$.

This is an interesting question; I hope someone can answer (1)-(3).


Proving skip-lists strongly weight-balanced in expectation Given a skip list of height $n$, what is its expected length, to within a constant (multiplicative) factor?

In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are defined as:

  For some constant $d$, every node $v$ at height $h$ has $\Theta(d^h)$ descendants.

They claim:

  Search trees that satisfy Properties 1 and 2 include weight-balanced B-trees,
  deterministic skip lists, and skip lists in the expected sense.

I asked already about the claim for deterministic skip lists. This question is about the claim for skip lists.

I believe that skip lists have this property in expectation, but I can't find a rigorous reason. The probability the other way around (what is the height, given the length) can be calculated directly to within a constant factor. A sophisticated analysis is given in The binomial transform and the analysis of skip lists.

Edit:

There are several different notions for defining "descendants" in skip lists; this term is not used in Pugh's original paper. Some possible interpretations of "descendants" come from viewing skip lists as trees. Different ways of doing this are included in

A limit theory for random skip lists
Deterministic skip lists
Skip trees, an alternative data structure to skip lists in a concurrent approach
Exploring the Duality Between Skip Lists and Binary Search Trees

Using the notion from "Deterministic skip lists", I think this is another way of asking the same question:

If I take a fair coin, then flip it some number of times such that my last result is tails, and the longest continuous sequence of heads was of length $n$, what is the expected value of the number of times I saw tails?

I'd also be interested in non-constructive proofs of strong weight-balance in expectation, even without a closed form solution for $d$.

As you asked it, the question about the expected length (given the height) does not make sense without a prior distribution on the length of the string.

You should instead consider the number of times you get tails before you get $h$ heads in a row, since this will give you the number of descendants of a node of height $h$ in a skip list.  Let's represent this value with the random variable $X=X(h)$.  When we start, or right after we get tails, the probability of starting and finishing a run of $h$ or more heads before getting tails again is $2^{-h}$.  If we hit tails before getting $h$ heads in a row, we're back to square one.  Thus $X$ is actually distributed as $\mathrm{Geometric}(2^{-h})$ and we have $\mathrm{E}(X) = (1-2^{-h})2^h$.

Edit:

Sorry, this gives you the expected number of towers in the left subtree.  The number of nodes in the left subtree will be of the same order of magnitude though, since towers in between the first and last will have geometrically distributed height with expected value 2.  Also, if you want to consider the right subtree as well, which probably makes more sense, you simply go until you get $h+1$ heads in a row instead of just $h$.  In this case you get the number of descendants as defined in Devroye's paper that you linked to.


What is the parameterized complexity of following model checking problem? Input: Graph $G$ and formula $\varphi_1(\vec x),\varphi_2(\vec x)$

Parameter: $tw(G)+|\varphi_1|+|\varphi_2|$

Problem: Decide if $|\varphi_1(G)|=|\varphi_2(G)|$

where $tw(G)$ is the treewidth of $G$ and $\varphi(G):=\{\vec a|(G,\vec a)\models\varphi\}$.

What is the parametrized complexity of this problem for $\varphi_i\in FO$ or $\varphi_i\in MSO$?

This problem is $\mathsf{FPT}$ for $\varphi_i \in MSO$ (and hence also for $\varphi_i \in FO$).

More precisely, Courcelle et al. prove in [1] the following:

  Theorem [1, Thm. 32]
  Let $\mathcal{C}$ be a class of graphs which is of bounded tree-width $k$.
  Then any $MSO_2$ definable counting problem, given by $\varphi$, can be solved in time $c_k \cdot \mathcal{O}(|V| + |E|)$, where $c_k$ is a constant which depends only on $\varphi$ and $k$.

$MSO_2$ stands for monadic second-order logic where the universe is $V \cup E$ (vertices and edges), and we are given a binary relation $R(v,e)$ for the incidence between a vertex $u$ and an edge $e$. This is a quite natural representation of graphs, sufficiently powerful to e.g. define Hamiltonicity.

[1]: B.Courcelle, J.A.Makowsky, U.Rotics. On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics 108, pp. 23-52 (2001)


Average-degree Bounded Graphs are no harder than Maximum-degree Bounded Graphs (for distance oracles with purely multiplicative stretch) I'm trying to understand a specific part from an article of Agarwal and co.
It is about Distance Oracles but there is a specific explanation of How to convert from average-degree graph to maximum-degree bounded graph with linear complexity.
I can't understand it so I need a simple language explanation...
This is the link to the article: http://arxiv.org/pdf/1201.2703.pdf and the specific explanation is in section 5.
From the article: (I don't understand the reduction)

Let G = (V, E) be a connected graph with average degree ∆. Given G, we
will first create a ∆-degree bounded graph G∆ = (V∆ , E∆ ). Then, we
show how can be used on G∆ to return stretch-s paths on G.
The Reduction: For each node v ∈ V , create α v = ⌈deg(v)/∆⌉ nodes v1 , v2
, . . . , vαv in V∆ . For each edge e = (u, v) ∈ E, if deg(u) ≤ ∆ and
deg(v) ≤ ∆, create an edge e = (u1 , v1 ) in E∆ . For each node v ∈ V
, we arbitrarily distribute N (v) in G to the nodes corresponding to v
in G∆ such that for i = 1, 2, . . . , (α v − 1), |N (v) ∩ N (vi )| = ∆
and |N (v) ∩ N (vαv )| = (deg(v) − (α v − 1) · ∆). Finally, for each
pair vi , vi+1 , we create an edge in E∆ of weight 0.
In order to answer an approximate distance query for any pair of nodes u, v ∈ V , we use D to answer approximate distance queries between u1 , v1 ∈ V∆
in G∆ and let the length of the path returned by the data structure be
δ′ . We output the distance δ′ as an approximate distance for the pair
of nodes in G.

Thanks!

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

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

Here is a rough proof to the above claim:

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

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

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

A corollary of the above claim is:

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

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


Finding whether $n$ polytopes have nontrivial intersection from pairwise comparisons I have a set of $n$ convex polytopes of the form

$$\mathcal{L_i} = \{ \beta \mid C_i \beta \leq 0 \}$$

where $C$ is a matrix and $\beta$ is a vector. I know that for each pair of polytopes $$(\mathcal{L}_k, \mathcal{L}_j)$$ there is a point of intersection other than the trivial solution $\beta = 0$. Additionally, I know that $C_i$ is such that each entry of $\beta$ must be greater than or equal to zero. What I want to know is whether this implies that there exists a nontrivial point of intersection of all $n$ polytopes, or if there is some counterexample?

Thanks!

Your question is related to how to represent the geometric intersection objects. Pairwise comparisons can get a geometric intersection graph, however, the problem is that two objects are possibly not close to each other in this intersection graph, even originally their geometric distance is very short. So it is easy to find counterexamples for the specific question you asked: whether this implies that there exists a nontrivial point of intersection of all $n$ polytopes.

Given a geometric intersection graph, deciding which graph class it belongs to, the so-called recognition problem is not easy: Shaefer [1] proved that for intersection graphs of convex sets, the recognition problem is  $\exists \mathbb{R}$-complete(It lies between NP and PSPACE).

[1] M. Schaefer. Complexity of some geometric and topological problems. In Proc. 17th Int. Symp. Graph Drawing (GD), pages 334–344, 2009.


Empirical probability of k-SAT satisfiability Given a random instance $I_m = I_m(n,k)$ of $k$-SAT with $n$ variables and $m$ clauses, what's the probability $I_m$ is satisfiable?

It's believed that there's a threshold above which satisfiability becomes less likely as $m/n$ increases. The reverse is true as $m/n$ decreases.

Is there an empirical formula for $3$-SAT and other $k$'s that describe the rate at which satisfiability becomes more/less likely as you move away from the threshold?

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

PHASE TRANSITIONS OF BOOLEAN SATISFIABILITY VARIANTS, Bailey 2004


Variable wire weights in DLOGTIME-uniform circuits The definition of a $DLOGTIME$-uniform circuit family is based on a Turing machine that accepts the language $\langle t, a, b \rangle$, where gate $a$ is of type $t$ and has gate $b$ as a child, according to Barrington et. al's paper "On Uniformity Within $NC^1$" (1). However, this definition assumes that whether there is a wire or not between two gates is a binary choice. While this is true for $AND/OR$-based circuit classes like $AC^0$, other circuit classes like $CC^0$ and especially $TC^0$ assume that circuits can have an arbitrary constant or even $O(n)$ number of wires between two gates.
My questions are:

Is there a standard way in the literature to extend the definition of dlogtime-uniformity with wire weights greater than 1?
Is there a standard way to add this feature to logical characterizations of these families (e.g. $FO[bit]$)?

After re-reading Barrington et al., it seems that the case of $CC^0$ can be handled by using "group quantifiers", which allow for quantifiers to act over finite groups (i.e. $\mathbb{Z}/m\mathbb{Z}$) directly, while still using a binary representation under the hood so that the original definition of $DLOGTIME$-uniformity can still be used. With group quantifiers, wire weights (or any arbitrary constant-size function) can be simulated with a formula over the bits of the representation. I am still unsure how this might extend to a class like $TC^0$ that operates over an infinite monoid/group (or at least one that grows with $n$), but this answers the core of the question I had.


Finding small sets of integers in which every element is a sum of two others This is a follow-up to this question on math.stackexchange.

Let us say that a non-empty set S ⊆ ℤ is self-supporting if for every a ∈ S, there exist distinct elements b,c ∈ S such that a = b + c. For positive integers n, simple examples include the ideal S = nℤ, or (for n>3) the integer interval [−n, n].

We'll say that S is strongly self-supporting if S is disjoint from −S: that is, if a ∈ S, then −a ∉ S. Neither of the above examples are strongly self-supporting, because they are in fact closed under negation.
There exist finite sets which are strongly self-supporting: for instance, the sets
{−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23} and  {−10, −8, −6, −2, 1, 3, 4, 5}.

Question #1. For a positive integer N>0, does there exist a poly(N)-time [or polylog(N)-time] algorithm to either (i) produce a strongly self-supporting set whose maximum absolute value is N, or (ii) determine that no such set exists? [Edit: as pointed out in the oldest answer + my comment on it, there always exists such a set for N ≥ 10.]

Question #2. For N>0, can you construct the strongly self-supporting set with maximum absolute value N, and which has the fewest possible elements?

I suppose a linear time algorithm should be possible for Question #1) (and if you are willing to deal with a different representation, an O(1) time algorithm)

Given any N >= 23, we construct a strongly self supporting set which contains 1 and N.

We can do that easily if we construct the same for N-1, and then add N to the resulting set.

For the base case of 23, we can start with your example set.

To bring the size down, we should be able to use a similar approach:

Construct sets which contain 1, N and N-1.

We use these constrained sets and do this construction recursively to bring the size down to O(logN) as follows:

If N is even, to construct a set containing 1,N and N-1, recursively construct a set containing 1, N/2 and N/2-1 (i.e. set corresponding to N/2) and add N and N-1 to resulting set. Since N-1 = N/2 + N/2-1 and N = 1 + N-1, this is a valid set.
If N is odd construct a set for N-1 and N to resulting set.

For the base cases, we can start with {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} for N=24. For 24 < N <= 47, we can use the above linear time algorithm and build upon the set for N=24. For N>=48 we switch to reducing by half.

In fact, for composite N, we can bring the size further down to the size required for one of the small primes which divides N: Find a set for the small prime, and just multiply all numbers by a suitable factor.

It might be interesting to prove some lower bounds in the case N is prime.


The Equivalency of Two Definitions of Completeness & Soundness in Interactive Proof Systems The completeness and soundness in interactive proof systems are informally defined as:

Completeness: If a statement is true, the honest prover can convince the honest verifier of this fact w.h.p.
Soundness: If a statement is false, the cheating prover cannot convince the honest verifier (of the validity of the false statement) w.h.p.

The term "w.h.p." is either interpreted as "with probability greater than (say) 2/3," or "with probability greater than the reciprocal of any polynomial." It seems immaterial to the following discussion as what interpretation of "w.h.p." to choose.

The tricky part is how the probability is computed: In some sources, the probability is taken over the random coins of both the prover and the verifier. In other sources, the probability is only computed over the random coins of the verifier. The latter is usually justified as: "whatever the random coins of the prover are, the verifier makes the right decision."

To me, both definitions of probability seem equivalent; yet I can't prove this. Am I right? Can you prove them equivalent?

The prover is "all-powerful and possesses unlimited computational resources" so it has no need of random bits. Thus the only randomness is the randomness of the verifier.

If the prover uses random bits, it should replace them with the random bit string that is most likely to make the verifier accept (this is true for both the honest and any dishonest prover). Furthermore, the prover can determine this optimal bit string because the prover is "all-powerful".


Simple spatial ordering or TSP algorithms? I'm not sure if this is the right place to ask, but I suppose you'll tell me.

I'm writing a program that produces a series of points on a map, and I need to put the points in some linear order so that adjacent points in the list are usually near each other. I just want to tack this on as a minor feature, so I need a simple algorithm that won't be hard to implement, and won't take more than O(N2) time.

I don't need much accuracy so maybe Z-order or Hilbert order would suffice, but the points are floating-point, and I only know how to implement Z-order for integer coordinates.

So, what algorithm would you suggest?

A relatively simple way of implementing this would be to simply divide your map recursively into a quad-tree until every node of the quad-tree is either empty or contains at most one point.

Now simply apply your Z-ordering to the nodes of the quad-tree.