The randomized query complexity of the conjoined trees problem An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of.  In this problem, we're given an exponentially-large graph like the one pictured below, which consists of two complete binary trees of depth n, whose leaves are connected to each other by a random cycle.  We're supplied with the label of the ENTRANCE vertex.  We're also supplied with an oracle that, given as input the label of any vertex, tells us the labels of its neighbors.  Our goal is to find the EXIT vertex (which can easily be recognized, as the only degree-2 vertex in the graph other than the ENTRANCE vertex).  We can assume that the labels are long random strings, so that with overwhelming probability, the only way to learn the label of any vertex other than the ENTRANCE vertex is to be given it by the oracle.

Childs et al. showed that a quantum walk algorithm is able simply to barrel through this graph, and find the EXIT vertex after poly(n) steps.  By contrast, they also showed that any classical randomized algorithm requires exp(n) steps to find the EXIT vertex with high probability.  They stated their lower bound as Ω(2n/6), but I believe that a closer examination of their proof yields Ω(2n/2).  Intuitively, this is because with overwhelming probability, a random walk on the graph (even a self-avoiding walk, etc.) will get stuck in the vast middle region for an exponential amount of time: any time a walker starts heading toward the EXIT, the much larger number of edges pointing away from the EXIT will act as a "repulsive force" that pushes it back toward the middle.

The way they formalized the argument was to show that, until it's visited ~2n/2 vertices, a randomized algorithm hasn't even found any cycles in the graph: the induced subgraph that it's seen so far is just a tree, providing no information whatsoever about where the EXIT vertex might be.

I'm interested in pinning down the randomized query complexity of this problem more precisely.  My question is this:

Can anyone come up with a classical algorithm that finds the EXIT vertex in fewer than ~2n steps---say, in O(2n/2), or O(22n/3)?  Alternatively, can anyone give a lower bound better than Ω(2n/2)?

(Note that, by the birthday paradox, it's not hard to find cycles in the graph after O(2n/2) steps.  The question is whether one can use the cycles to get any clues about where the EXIT vertex is.)

If anyone can improve the lower bound past Ω(2n/2), then to my knowledge, this would provide the very first provable example of a black-box problem with an exponential quantum speedup, whose randomized query complexity is greater than √N.  (Where N~2n is the problem size.)

Update: I've learned from Andrew Childs that, in this note, Fenner and Zhang explicitly improve the randomized lower bound for conjoined trees to Ω(2n/3).  If they were willing to accept constant (rather than exponentially-small) success probability, I believe they could improve the bound further, to Ω(2n/2).

I think I have a deterministic algorithm that finds the exit in $O(n2^{n/2})$ oracle calls.

First, find the labels for all the vertices of distance $n/2$ from the entrance. This takes $O(2^{n/2})$ queries. Then, start from the entrance and walk $n+1$ steps to get to a node $X$ of distance $n+1$ from the entrance. We will try to reach the exit from this node.

We have two options of where to go from $X$, and we wish to choose the one closer to the exit. To do this, pick one of the options arbitrarily, arriving at a node $Y$. Then explore all the $O(2^{n/2})$ ways of walking $n/2$ steps from $Y$. If one of them gives a label of distance $n/2$ from the entrance, we know that going from $X$ to $Y$ was the wrong choice. Otherwise, $Y$ was the right choice. Thus in $O(2^{n/2})$ we found a node $X_2$ of distance $n+2$ from the entrance.

We can keep proceeding this way. To find a node of distance $n+3$ from the entrance, we start at $X_2$ and walk two arbitrary steps. We then explore all options of walking $n/2$ additional steps (while never walking backwards), and check if any of them have distance $n/2$ from the entrance. This will happen if and only if the first step we walked from $X_2$ was wrong.

Getting to the exit requires doing this $n$ times, for a total of $O(n2^{n/2})$ oracle calls. In addition, perhaps surprisingly, this algorithm is deterministic.

Edit: Just to clarify, to get from $X_t$ to $X_{t+1}$, we walk $t$ arbitrary steps, then run a search of depth $n/2$, for a total of $t+2^{n/2}$ steps. If the first step lead away from the exit, then all the first $t$ steps did, and we therefore find a label of distance $n/2$ from the entrance. This means $t+2^{n/2}$ steps suffice for determining the next single step to take from $X_t$.


Two Decision Problems About Graphs --- Original Results? I have a couple of short but pleasing results. I was wondering (a) if they're original (b) if so whom should I tell?

I don't have easy access to any standard texts that would help me out here. Nor indeed do I work in the field (but it would still be advantageous as well as personally satisfying if I could get a note in some journal or other). Anyway, enough prolog, on with the results.

Consider these two closely related problems:

PROBLEM 1: A complete digraph has its edges labeled with numbers. The "average score" of a circuit (not necessarily a cycle) in the graph is defined as the sum of the numbers along the edges traversed divided by the number of edges in the circuit. Is there a non-self-intersecting circuit having an average score greater than a given number?

PROBLEM 2: The same problem, except with the additional constraint that the circuit must pass through a given vertex of the graph.

Problem 1 can be solved in polynomial time. Problem 2 is NP-complete.

Thank you for your comments.

Problem 1 is an exercise in CLRS (2nd ed., page 617).


Are Oracles Associative? This question may have an obvious answer ... but here's the question anyway. Intuitively, it is the following plausible statement - "a machine with a subroutine A which in turn has a subroutine B is the same as a machine with a subroutine A which has access to subroutine B".

To define this problem formally, I'll use some unconventional notation. When I say $A^B$, I am giving $A$ an oracle for a $B-Complete$ problem. e.g $NP^{NP}=NP^{SAT}=\Sigma_2$. With this "new" notation, it's possible to define $A^{B^C}$, and so on. My question is, is

is this a valid way of thinking about oracles?
is $(A^B)^C = A^{(B^C)}$

For example, $(NP^{NP})^{NP} = \Sigma_2^{NP} = NP^{\Sigma_2}=NP^{({NP}^{NP})}$

I can't think of any obvious counterexamples to this rule. Anyone?

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

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

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

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


Constructing vectors in general position Let a real $k\times n$  ($k\le n$) matrix ${\bf A}$ with the property that any collection of $k$ columns is full rank.

Q: Is there an efficient way to deterministically find a vector ${\bf a}$ such that the augmented matrix ${\bf A}' = [{\bf A}\;{\bf a}]$ preserves the same property as ${\bf A}$: any $k$ columns are full rank.

Relevant Sidenote: A matrix that has this property is the generator of an $(n,k)$ Reed-Solomon Code: adding columns that preserve its Vandermonde structure preserves the rank property.

If you choose $\mathbf{a}$ uniformly at random from the hypercube $[0,1]^n$, the matrix $[\mathbf{A}~ \mathbf{a}]$ will have the desired property with probability $1$.


Complexity of determinant of k-minors Let $A$ be an $n \times n$-matrix, and let $1 \leq k \leq n$. Which algorithms do exist, or what is know about the complexity of computing determinants of all $k \times k$-minors?

The naive algorithm has complexity $\Theta( {n \choose k}^2 k! )$. If we apply Gaussian elemination for each minor $\Theta( {n \choose k}^2 k^3 )$. Of course, there is a dynamic programming approach, too, but I am not firm enough to compute its complexity.

I am also interested whether there is a lower bound actually known.

Not quite answering what you want, but if you want the gcd of all $k\times k$ minors, then you can compute it in $O(n^\omega)$ or up to logarithmic factors. This is known as Smith Normal Form. For any matrix over principal ideal ring (or PID), the $k$ invariant factor of Smith normal form is the ${\rm gcd}$ of all $k\times k$ minors.


Isometric embedding of L2 into L1 It is known that given an $n$-point subset of $\ell_2^d$ (that is, given $n$ points in ${\mathbb R}^d$ with Euclidean distance) it is possible to embed them isometrically in $\ell^{n\choose 2}_1$.

Is the isometry computable in (possibly, randomized) polynomial time?

Since there are finite-precision issues, the precise question is

Given a set $X$ of $n$ points in ${\mathbb R}^d$ and $\epsilon >0$, is there a mapping $f: X \to {\mathbb R}^{n\choose 2}$ computable (possibly, using randomness) in time polynomial in $n$ and logarithmic in $1/\epsilon$ such that for every $x,y\in X$ we have
$|| f(x)-f(y)||_1 \leq ||x-y||_2 \leq (1+ \epsilon) \cdot || f(x)-f(y) ||_1$

(Note: I am aware that a mapping with distortion $(1+\epsilon)$ can be found with high probability in time polynomial in $n$ and $1/\epsilon$ by projecting on $O(\epsilon^{-2} \cdot \log n)$ random lines, but I am not sure if the number of dimensions can be constructively reduced to $n\choose 2$ or even $O(n^2)$ when $1/\epsilon$ is much larger than $n$, and I don't know if there is a polynomial time method to handle the case in which $1/\epsilon$ is exponential in $n$.)

Suresh asked me to assemble my comments above into an answer, so here it is. I'm not really sure it's an answer to the original question, though, since it's not obvious how to make it polynomial time when the dimension of the input Euclidean space is non-constant. It does at least have the advantage of avoiding any problem with large $1/\epsilon$ as the original question asks, because it doesn't involve any approximation, and it looks polynomial for constant $d$.

Anyway: from integral geometry, there is a standard measure on sets of hyperplanes in $d$-dimensional Euclidean space that is invariant under Euclidean congruences. It has the property that the length of any bounded-length curve $C$ is proportional to the measure of the hyperplanes that cross $C$ (with multiplicity, meaning that if a hyperplane crosses $C$ twice then it contributes twice to the total measure of the hyperplanes crossing $C$). In particular if $C$ is a line segment then the multiplicity complication doesn't arise and we can normalize the measure on the hyperplanes crossing $C$ to be exactly the length of $C$. (The hyperplanes containing $C$ have measure zero, so don't worry about infinite multiplicity.)

Now, given a set of n points in d-dimensional space, make an $\ell_1$ coordinate for each of the partitions of the points into two subsets induced by a hyperplane that doesn't pass through any of the points. Give the points on one side of the partition coordinate value zero and the points on the other side of the partition coordinate value equal to the measure of the set of hyperplanes inducing that partition.

If $p$ and $q$ are any two of the $n$ points, let $K$ be the set of hyperplanes crossing line segment $pq$, and let $K_i$ be the subsets of $K$ formed by each possible hyperplane partition that has $p$ on one side and $q$ on the other. Then $K$ is the disjoint union of the $K_i$, and the coordinate differences between $p$ and $q$ are just the measures of the subsets $K_i$. Therefore, the $\ell_1$ distance between the coordinatizations of $p$ and $q$ (the sum of the measures of the $K_i$) is the measure of $K$, which is just the original $\ell_2$ distance between $p$ and $q$.

For computational geometers, an alternative description of the same construction may be helpful: use projective duality to transform the $n$ input points into $n$ hyperplanes, and separating hyperplanes into points. The integral geometry measure on sets of hyperplanes is then transformed into a more standard measure on sets of points, the distance between $p$ and $q$ dualizes to the measure of the double wedge between two hyperplanes, and the hyperplane arrangement partitions this double wedge into smaller cells. The coordinate value for a point is either the measure of one of the cells in the arrangement (if the dual hyperplane is below that coordinate's cell) or zero (if the dual hyperplane is above the cell). Therefore, the $\ell_1$ distance between $p$ and $q$ is just the sum of the measures of the cells in the double wedge, which is the same as the measure of the whole double wedge. This dual point of view also makes it easy to calculate the dimension of the embedding found in this way: it's just the number of cells in the hyperplane arrangement, which is $O(n^d)$, or more precisely at most $\sum_{i=0}^d{n\choose i}$.

So far, this gives a completely deterministic and exact embedding in $\ell_1^{O(n^d)}$. But we wanted a smaller dimension, $\ell_1^{n\choose 2}$. Here's where Luca's comment about Carathéodory's theorem comes in. The set of $\ell_1$-representable metrics forms a polyhedral cone in the $n\choose 2$-dimensional space of all functions from unordered pairs of points to real numbers, and the geometric argument above says that the Euclidean metric belongs to this cone. The points on the extreme rays of the cone are one-dimensional $\ell_1$ pseudometrics (in which the points are split into two sets, all distances within a single set are zero, and all distances across the split are equal), and Carathéodory says that any point within the cone (including the one we care about) can be represented as a convex combination of points on extreme rays whose number is at most the dimension of the ambient space, $n\choose 2$. But a convex combination of at most $n\choose 2$ one-dimensional $\ell_1$ metrics is a $\ell_1^{n\choose 2}$ metric.

Finally, how can we go about actually computing the $n\choose 2$-dimensional embedding? At this point we have not just a point in the $n\choose 2$-dimensional convex cone of $\ell_1$ metrics (the distance metric we started with), but we also have a set of $O(n^d)$ extreme points of the cone (corresponding to the partitions of the input into two subsets induced by hyperplanes) such that our metric is a convex combination of these extreme points — for small $d$, this is a big improvement over the $2^n-2$ extreme rays that the cone has overall. Now all we need to do is apply a greedy algorithm that gets rid of extreme points from our set, one by one, until only $n\choose 2$ of them are left. At each step, we need to maintain as an invariant that our metric is still inside the convex hull of the remaining extreme points, which is just a linear programming feasibility problem, and if we do this Carathéodory will ensure that there always remains a set of $n\choose 2$ extreme points whose convex hull contains the input metric.


Clarification of leftmost maximal periodicities Main describes an algorithm for detecting all 'leftmost maximal' periodicities in a string in linear time, using the following definitions:

A periodicity of a string $x$ a nonempty substring of $x$ of the form $p^mq$ with $m\ge2$ and $q$ a proper prefix of $p$.
A leftmost periodicity of $x$ is a periodicity $x[i] \dots x[j]$ such that if $x[i] \dots x[j] = x[i'] \dots x[j']$ then $i \le j$.
A periodicity $x[i] \dots x[j]$ with period $k$ is maximal if:

$i = 1$ or $x[i - 1] \dots x[j]$ is not a periodicity with period $k$, and
$j = |x|$ or $x[i] \dots x[j + 1]$ is not a periodicity with period $k$

Main goes on to present a theorem (3.4): given an s-factorisation of a string $x=u_1 \dots u_k$ and let $r$ be a periodicity of $x$, with leftmost occurrence of $r$ at $x[i] \dots x[j]$, and with the $j^{th}$ position of $x$ within $u_h$, then the $i^{th}$ position of $x$ occurs before $u_h$.

This theorem forms the basis of the algorithm for computing 'leftmost maximal' periodicities of a given string $x$. The algorithm finds all maximal periodicities of $t_hu_h$ for $2 \le h \le k$ where $t_h$ is a substring of length $2|u_{h-1}| + |u_h|$ that immediately precedes $u_h$, such that each periodicity begins in $t_h$ and ends in $u_h$.

My question concerns the meaning of "leftmost maximal", particularly if this should be read "periodicities that are both leftmost and maximal", or "maximal periodicities that are leftmost". To clarify the distinction, consider the string $x=aaabcaabd$. Clearly the periodicity $aaa$ starting at $x[1]$ is leftmost maximal under both interpretations, but is the periodicity $aa$ starting at $x[6]$ also leftmost maximal? According the the first interpretation, it isn't, and $x$ only has one leftmost maximal periodicity. According to the second, it is, and $x$ has two leftmost maximal periodicities.

It seems to me that Main's algorithm gives 'leftmost maximal' periodicities of the first kind: the s-factorisation of $aaabcaabd$ is $a|aa|b|c|aab|d$, hence the second $aa$ periodicity starting at $x[6]$ will not be included as it is contained entirely in a single s-factor ($u_5 = aab$).

However, as best as I can tell, the result of Kolpakov and Kucherov, for computing all maximal periodicities of string in linear time, assumes the second definition. Kolpakov and Kucherov use Main's result as a key component of their algorithm.

Main explicitly states that his algorithm may output some nonleftmost or nonmaximal occurrences of periodicities. Indeed, theorem 3.4 only guarantees that every leftmost maximal periodicity will be reported at least once and that total size of the output is linear in size of input string. Namely,

It may report some nonmaximal periodicity, which is suffix of $t_h u_h$ and still can be extended to the right.
There might be several occurrences of the same substring such that none of them fit into a single s-factor.

Kolpakov and Kucherov slightly modify Main's algorithm to exclude suffixes of $t_h u_h$ but allow either $t_h$ or $u_h$ to be empty. This way the algorithm never reports nonmaximal periodicities and at the same time finds every occurrence of maximal periodicity that either spans several s-factors or touches their boundaries.

So, Kolpakov and Kucherov don't rely on the notion of leftmost occurrences at all. They only need to find every periodicity that is not strictly inside single factor of s-factorization. (And prove that there will be only linear number of occurrences in total, of course.)


What are the most known database disk storage layout algorithms? I can list for example algorithms used in databases:

append only b-trees (MVCC like used in CouchDB)
merged logs (like used in Big Table, Hbase, Cassandra)
paged storages grouped in extents (like in InnoDB engine of MySQL)
fractal trees (like used in TokuDB engine of MySQL)

Are there any others? similar or totaly different?

The Fractal Trees I have seen overviewed in Tokutek talks are Cache-Oblivious Lookahead Arrays (COLAs), which are at the intersection of two motivating storage layout ideas. If you're looking for similar layouts, you might be interested in them:

Decreasing insertion time at the cost of increased search time. See Buffered Repository Trees and $B^{\epsilon}$ trees.
Cache-oblivious data structures.

The COLAs paper discusses another data structure at this intersection, as does a more recent improvement.

Implementation-wise, I only know of one other DBMS that uses cache-oblivious data structures: EaseDB, which is in-memory and appears to no longer be under active development.


why is Linear Datalog interesting? For those doesn't know about linear datalog, linear datalog is a datalog rule in which the number of IDB predicate in each rule is less or equal than one.

My question is, why is this interesting? What differ this with the "normal" datalog program?

NB: I put this question also in math.stackexchange. According to my experience, I am afraid that this question shouldn't be in this site, but I don't see any reason why I should put  deductive database question in math section.

Linear Datalog has a lot of connections with the complexity of constraint satisfaction and logic. Like @ian said, the intuitive way to view a linear Datalog program is a Datalog program who's proof trees are basically paths.

In constraint satisfaction, we are interested in problems of the following form. Let $\mathbf{B} = (B, R_1^{\mathbf{B}}, R_2^{\mathbf{B}}, \ldots, R_n^{\mathbf{B}})$ be a relational structure (that is, a domain $B$ with a family of relations over that domain). We ask, what relational structures $\mathbf{A} = (A, R_1^\mathbf{A}, R_2^\mathbf{A}, \ldots, R_n^\mathbf{A})$ admit a homomorphism to $\mathbf{B}$ (i.e. a function $f: A \rightarrow B$ such that if $(a_1, a_2, \ldots, a_n) \in R_i^{\mathbf{A}}$ then $(f(a_1), f(a_2), \ldots, f(a_n)) \in R_i^\mathbf{B}$)? We will denote this decision problem by CSP($\mathbf{B}$).

It turns out that the complexity of CSP($\mathbf{B}$) can be neatly characterized by linear Datalog. Namely, if co-CSP($\mathbf{B}$) can be expressed in linear Datalog, then CSP($\mathbf{B}$) is in $\mathsf{NL}$. This characterization of the expressibility of the complement problem in linear Datalog is equivalent to a number of different properties, such as $\mathbf{B}$ having bounded pathwidth duality, a winning strategy in a certain kind of pebble game, and expressibility in certain fragments of infinitary logic (logics extended with infinite conjunctions).

For more information, see

V. Dalmau. Linear Datalog and Bounded Path Duality of Relational Structures. Available at Logical Methods in Computer Science (here), 2005.

Another good survey paper with a section devoted to this would be

A. Bulatov, A. Krokhin, B. Larose. Dualities for Constraint Satisfaction Problems. Lecture Notes in Computer Science, Vol. 5250:93-124, 2008. Available here.


What's the relation and difference between Calculus of Inductive Constructions and Intuitionistic Type Theory? As stated in the title, I wonder any relation and difference between CIC and ITT. Could someone explain or point to me some literature that compares these two systems? Thanks.

I've already answered somewhat, but I'll try to give a more detailed overview of the type theoretical horizon, if you will.

I'm a bit fuzzy on the historical specifics, so more informed readers will have to forgive me (and correct me!). The basic story is that Curry had uncovered the basic correspondence between simply-typed combinators (or $\lambda$-terms) and propositional logic, which was extended by Howard to cover first-order logic, and IIRC independently discovered by de Bruijn in investigations around the hugely influential Automath system.

The Automath system was a refinement of Church's simple type theory which itself was a dramatic simplification of Russel and Whitehead's type theory with universes and the axiom of reducibility. This was relatively well-known logical terrain by the 1960s.

However, giving a coherent, simple, foundational system that encompassed both proof and term systems was still a very open question by 1970, and a first answer was given by Per Martin-Löf. He gives a very philosophical overview On the Meaning of the Logical Constants and the Justification of Logical Laws. He reasons that both in logic and mathematics, the meaning of constructions can be given by examining the introduction rules which allow the formation of those constructions as judgements, e.g. for conjunction
$$ \frac{\vdash A\quad \vdash B}{\vdash A\wedge B}$$

Determines the corresponding elimination rule. He then gave a very powerful foundational system based on such judgements, allowing him to give a foundational system similar to Automath using very few syntactic constructions. Girard found that this system was contradictory, prompting Martin-Löf to adopt "Russel-style" predicative universes, severely limiting the expressiveness of the theory (by effectively removing the axiom of reducibility) and making it slightly more complex (but had the advantage of making it consistent).

The elegant constructions allowing for the definition of the logical symbols didn't work anymore though, which prompted M-L to introduce them in a different form, as inductively defined families. This is a very powerful idea, as it allows defining everything from judgmental equality and logical operators to natural numbers and functional data-types as they appear in computer science. Note that each family we add is akin to adding a number of axioms, which need to be justified as consistent in each instance. This system (dependent types + universes + inductive families) is usually what is referred to as ITT.

However there was some lingering frustration, as the powerful but simple foundational system was inconsistent, and the resulting system was more complex, and somewhat weak (in the sense that it was difficult to develop much of the modern mathematical framework in it). Enter Thierry Coquand, who with his supervisor Gerard Huet, introduced the Calculus of Constructions (CoC), which mostly solved these issues: a unified approach to proofs and data-types, a powerful (impredicative) foundational system and the ability to define "constructions" of the logical or mathematical variety. This eventually matured into an actual implementation of a system designed as a modern alternative to Automath, culminating in the Coq system we know and love.

I highly suggest this foundational paper on CoC, as Thierry knows a ridiculous amount about the historical development of type theory, and probably explains this much better than I. You might also want to check out his article on type theory, though it doesn't explain the C-H correspondence in much detail.


Inductive types for large countable ordinal notations. I'm looking to build notations for large countable ordinals in a "natural way".  By "natural way" I mean that given an inductive data type X, that equality should be the usual recursive equality (the same that deriving Eq in Haskell would produce) and the order should be the usual recursive lexicographical order (the same that deriving Ord in Haskell would produce), and there is a decidable predicate that determines if a member of X is a valid ordinal notation or not.

For example, ordinals less than ε0 can be represented by hereditarily finite sorted lists and satisfies these requirements. Define X to be μα. μβ. 1 + α×β, a.k.a. hereditarily finite lists.  Define isValid to check that X is sorted and all members of X are isValid.  The valid members of X are all ordinals less than ε0 under the usual lexicographical order.

I conjecture that μα0.… μαn. 1 + α0×…×αn can be used to define ordinals less than φn + 1(0), where φ is the Veblen function, in a similar way.

As you can see I run out of μ quantifiers at φω(0). Can I build larger ordinal notations satisfying my requirements?  I was hoping to get as far as Γ0.  Can I get larger ordinals if I drop my decidability requirement on my validity predicate?

Hermann Ruge Jervel has a nice system that goes all the way to the Bachmann-Howard ordinal based on labelled trees.  See: http://folk.uio.no/herman/logsem.pdf

I also like his book on proof theory, which discusses this system: http://folk.uio.no/herman/bevisteori.ps


What is the underlying physical principle behind quantum fault tolerance in quantum computation? What is the underlying physical principle behind quantum fault tolerance in quantum computation?

I am trying to follow the mathematical steps behind quantum fault tolerance, and while I can just manage to do so, I have to admit I fail to see the underlying principle behind them, or the motivation for just why it works. I kind of understand how entanglement swapping with a heat sink lies behind quantum error correction, but what underlying principler lies behind quantum fault tolerance?

I would encourage you to think of error correction not as entanglement-swapping, per se, but the stimulated dissipation of excitations from a carefully engineered Hamiltonian — not the Hamiltonian which governs the unitary evolution, but a different Hamiltonian in whose ground-state manifold one thinks of trying to keep the state of the system, by dissipating excitations into a system of low temperature. Then we can describe fault tolerance as the threshold at which the rate of stimulated dissipation is such that the probability of an uncontrolled spontaneous dissipation can be efficiently suppressed by any desired factor.

Against the role of entanglement — per se — in error correction

The picture of 'entanglement swapping' which you describe brings to mind the question of coherence, and the issue of the state of the computation being isolated from the environment: in the quantum circuit model, we would quite like (short of what transformations are being applied) for the state of the computation to be essentially closed off from the outside world. This is the classic catch-22 behind the engineering problem of designing a quantum computer: to be open to the environment only when you want it to be (because you are part of the environment), and to control when it is open to the environment (from within the environment). It invites us to think of the problem in terms of a double-bind. Furthermore, not all errors necessarily would manifest as entanglement with the environment: an environment which deterministically performs Pauli operations on each of our qubits in some order would not be entangling and would be just as bad from an error perspective as anything which did involve entanglement.

Error correction as a form of Hamiltonian engineering

An alternative view is that the error correcting process is a sort of dissipative process.

Each detectable error corresponds to a sort of excitation of the system — an event corresponding perhaps to a projector onto a partial error syndrome — and what we are attempting to determine is whether the state of the system has become "excited" because it has a substantial overlap with the 'signature' of some error due to interaction with an environment with non-zero temperature.

In the case of stabilizer codes, for instance, you could think of the Pauli generators $S_1, S_2, \ldots$ of the code as giving rise to projectors $P_j = \tfrac12(\mathbf 1 - S_j)$. The Hamiltonian is then $H = \sum_j P_j$, and the codespace is the ground state manifold — that is, the lowest-energy eigenspace: the zero eigenspace, i.e. the joint zero eigenspace of the projectors, as opposed to the joint +1-eigenspace that one often considers. The error syndrome is then a description of a collection of commuting excitations of the projectors $P_j$ representing energy contributions — the error-free syndrome corresponding to the highly degenerate ground-state manifold, $\mathrm{null}(H)$.
What we attempt to do is to measure the energy terms in the Hamiltonian frequently enough, not to mention accurately enough, to detect the excitations (errors). Then, we attempt to dissipate away these excitations (correct the errors) the dissipation process being the efficient transmission of the excitation (error) out of the state of the computation and into some auxiliary system.
Furthermore, we would like to do it quickly enough so that the system
does not accumulate too much error, and then spontaneously and uncontrollably dissipate the excitations. For the error correcting code to be useful, it has to encode a highly degenerate subspace: thus, the error-excitations which we are trying to dissipate are excitations of a highly degenerate Hamiltonian. Because of the degeneracy of the ground-state manifold, there is a risk that a spontaneous relaxation of an excited state to a ground state could give rise to a non-trivial transformation of the ground-state manifold: an uncorrectable encoded error.

In all of the above, entangled states will sometimes be involved, and one may think of codes such as the Shor 9-qubit code as exploiting entanglement (correlations in multiple bases of measurement) to represent a quantum analogue of a simple repetition code. But in all this, entanglement is an incidental feature of the more fundamental phenomenon of correlations of multi-qubit observables representing excitations (or lack of them) in a physical process. That is, the role of entanglement here is the same as in many-body systems: it just so happens that the ground states of Hamiltonians may be entangled, but the mere presence or absence of entanglement is not what makes the states ground-states.

Competing dissipation processes

Above, I talk about spontaneous versus stimulated dissipation. However, this is a distinction of engineering, not of physics: the fact that the 'stimulated' process is under our control is not relevant from a physical perspective. Physically, we merely have two interaction/dissipation processes with the computational system: an uncontrolled 'noise' process with a bath, and a controlled dissipation process which we might think of as happening with a cold reservoir (corresponding to the ancillas which we prepare to aid with the error correction process). The error rate per unit time is the interaction of the bath with the computational system; the error rate per gate is the effective three-way interaction of the bath with the reservoir and computational system. The error correction is the interaction of the computational system with the cold reservoir alone.

In this picture, what would it look like if we could make the interaction with the reservoir dominate these interactions of the computational system with the bath, or the bath-system-reservoid interaction? It would look as if any interaction of the bath with the system would be more and more efficiently transmitted into the cold reservoir, with the computational system left essentially undisturbed.

This is how we can interpret what the threshold theorem tells us — if the interaction of the system with the warm bath is sufficiently low, we can simulate a bath at arbitrarily low temperature by simulating a coupling of the computational system with a cold reservoir, where the transmission of excitations from the system to the reservoir is arbitrarily swift; and furthermore the resources to do so is $\mathrm{poly} \log(\varepsilon)$, where $\varepsilon > 0$ is the factor of suppression of noise in the computational system.


Scope of natural proofs barrier The natural proofs barrier of Razborov and Rudich states that under credible cryptographic assumptions one cannot hope to separate NP from P/poly by finding combinatorial properties of functions that are constructive, large, and useful.  There are several well-known results that manage to evade the barrier.  There are also several papers discussing possible loopholes to the three conditions, such as a result of Chow showing the barrier is sensitive to weak violations of largeness, and a recent paper of Chapman and Williams suggesting how to potentially avoid the barrier by relaxing the usefulness condition.  My question is whether there are any examples, or even the possibility, of avoiding the natural proofs barrier not by violating constructiveness, largeness, or usefulness, but by falling entirely outside its scope.  That is, it is not at all obvious to me why every potential method of proof should need to be based on finding combinatorial "properties" and then partitioning all functions into those that do and don't meet the property.  Why must this framework of operation apply to all possible proofs, and if it doesn't then what would other types of proofs look like?

Let $f: \{0,1\}^* \rightarrow \{0,1\}$ be a function, and let $C$ be a class of algorithms working on finite slices of $f$. Every circuit lower bound whatsoever is a proof that $f \notin C$, for some $f$ and some $C$. Consider the "combinatorial property of Boolean functions" ${\cal P}_f$, such that

${\cal P}_f(f) = 1$ and ${\cal P}_f(g) = 0$ for all $g \neq f$.

A proof that $f \notin C$ is a proof that ${\cal P}_f$ is useful against $C$, in the terminology of Razborov and Rudich. That is, "usefulness" is totally unavoidable -- there is no way to "fall outside its scope." If you have proved a circuit lower bound at all, you have given some useful property.

Note that, if $f \in TIME[2^{O(n)}]$, then ${\cal P}_f$ is also constructive as well, in the terminology of Razborov and Rudich. So for functions $f$ computable within $E$ but not in (say) $P/poly$, constructivity would also apply to at least one property of Boolean functions that is useful against $P/poly$.

So, Razborov and Rudich is more fundamental than you might initially think.


Busy Beavers: quadratic relation of output size and running time? When glancing at the running times and output sizes of some Busy Beaver candidates on this page, I find that there seems to be a rough (up to some small power of 10) quadratic relation between output size and running time. Do you know a heuristic argument or even proof for this? Is it related to the computational model of Turing machines, or is it some more general principle?

Because (under the assumption of a computational model where the binary description of the algorithm and the algorithms' length can be read out and operated on by the program) no program can decide the halting problem for all programs a little bit longer than itself and access to the busy beaver program of some length entails ability to solve the Halting problem for that length by checking whether a given program runs longer than the busy beaver, it can't be that this is somehow a test (for said programs with efficient access to memory) that will vastly constrain the possible candidates for all sizes, as then a smaller number of supplied bits would suffice to generate the busy beaver and thee would be a program could solve the halting problem for somewhat bigger programs. If you sharpen the notion of "vastly", this reasoning will also apply to Turing machines.

It's true, all current busy beaver candidates have a quadratic relationship between output size and steps. As Ross points out, this has to do with how they act. They move back and forth across much of the output every time they increase the output size by some constant. That means that to get to size N they must run for approximately 1 + 1 + 2 + 2 + 3 + 3 + ... = N(N+1) steps.

However, there are many other types of Turing machines. For example, there are ones often called counters which move back and forth across a section of output, each time incrementing a binary (or other base) counter. These take exponential time to increase the size of the output. One interesting one is Brady's "Surprise in a Box" http://www.drb.insel.de/~heiner/BB/simAB3Y_SB.html which expands quadratically for a little while and then moves completely within the "box" until it halts.

There are also machines which have a sort of recursive "back and forth" behavior so that it takes them N^2 steps to increase the size of the tape. They have a cubic relationship between output size and steps.

I suspect that for larger values busy beavers will not have this relation because they will get more complex in their behavior, but I don't know of any proofs.


Hard-looking algorithmic problems made easy by theorems I am looking for nice examples, where the following phenomenon occurs: (1) An algorithmic problem looks hard, if you want to solve it working from the definitions and using standard results only.
(2) On the other hand,  it becomes easy, if you know some (not so standard) theorems.

The goal of this is to illustrate for students that learning more theorems can be  useful, even for those  who are outside of the theory field (such as software engineers, computer engineers etc). Here is an  example:

   Question:  Given integers $n, k, l, d$, does there exist an $n$-vertex graph (and if so, find one), such that its vertex connectivity is $k$, its edge connectivity is $l$, and its minimum degree is $d$?

Note that we require that the parameters are exactly equal to the given numbers, they are not just bounds. If you want to solve this from scratch, it might appear rather hard. On the other hand, if you are familiar with the following theorem (see  Extremal Graph Theory  by B. Bollobas), the situation becomes quite different.

  Theorem:  Let $n, k, l, d$ be integers. There exists an $n$-vertex graph with vertex connectivity $k$, edge connectivity $l$, and minimum degree  $d$, if and only if one of the following conditions is satisfied:
    $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$,
   $1\leq 2d+2-n\leq k\leq l = d< n-1$
   $k=l=d=n-1.$

These conditions are very easy to check, being simple  inequalities among the input parameters, so the existence question can be answered effortlessly. Furthermore, the proof of the theorem is constructive, resolving the construction issue, as well. On the other hand, this result does not appear standard enough, so that you can expect everybody to know about it.

Can you provide further examples in this spirit, where knowing a (not so standard) theorem greatly simplifies a task?

If I understand your question correctly, a canonical example would be deciding if a graph $G$ has an Eulerian circuit: equivalent to checking that $G$ is connected and every vertex has even degree.


How to generalize VC dimension? Let's try to generalize the $VC$-dimension (of the class of hyperplanes) to include accuracy/error.  Let $S$ be a set of points in $R^d$ and $t$ in $[0,1]$.  We say that the class of hyperplanes $t$-shatters $S$ if for every binary labeling of the points in $S$, there exists some hyperplane which separates $S$ with accuracy at least $t$ (i.e., at least $t*|S|$ of the points in $S$ are classified correctly by the hyperplane).  We then define the $VC(t)$-dimension of the class of hyperplanes (in a feature space of dimension $d$) to be the size of the largest set $S$ which the hyperplanes $t$-shatter, i.e.,

$VC(t) = max_{S \subset R^d}{|S|}$, subject to the constraint that the hyperplanes $t$-shatter $S$.

For example, the usual VC-dimension is $VC(1)$.  So $VC(1)=d+1$.  $VC(t)$ is clearly nonincreasing in $t$.  $VC(0)=\infty$ (in fact, I think $VC(0.5)=\infty$).

Question:  Have people studied this generalization of VC-dimension, or something similar?  If so, what is it called, and can you point me to resources about it?  What is the best lower bound on $VC(t)$?  Thanks!

Edit: Here's the motivation for my question.  For any set of non-coplanar $d+1$ points in $R^d$, and any binary labeling of these points, there is a linear classifier (a hyperplane) which classifies these points with 100% accuracy.  More generally, given $n>d+1$ points (satisfying some "weak" condition like non-coplanarity) and a binary labeling of them, what can we say about the accuracy of a linear classifier for these points?  If $t \in [0,1]$ and $VC(t) \geq n$, then we know that for any $n$ points in $R^d$ (satisfying some "weak" condition) and any labeling of these points, there is a linear classifier which has accuracy at least $t$ on these points.

If the $VC$-dimension is $d$, then the number of sets that can be cut out from $m$ points by your family is $(em/d)^d$. (This is called the shatter function.)
Every set that you can cut out, can be changed at most $\sum_{i=0}^{tm} \binom mi$ ways to contribute to the $t$-shattering.
So if you want to $t$-shatter a set of size $m$, then you need $2^m\le (em/d)^d \sum_{i=0}^{tm} \binom mi\le(em/d)^d 2^{H(t)m}$ (if $t\le 1/2$) where $H(t)=-t\log_2 t-(1-t)\log_2(1-t)$ is the binary entropy.
From this we get $VC(t)\lessapprox d/(1-H(t))$.
Also note that $VC(t)\ge d/(1-t)$ holds trivially.
Of course, these bounds are general and not only for halfspaces.


How powerful is $ACC^0$ circuit class in average case? We know that $NEXP$ is not in $ACC^0$ .

Does the result that $NEXP$ is not in $ACC^0$ also hold in average case?

That is given a boolean function in $NEXP$ is it known that for every input length $n$ we cannot have $\frac1{n^c}$ ($c>0$) fraction of possible computable in $ACC^0$?

Tying up with communication complexity I think what I seek could be the following. Since $NEXP$ is not in $ACC^0$ is known could it be that any $NEXP$ complete function has superpolylogarithmic communication complexity in NOF model with superpolylogarithmic number of players?

Then the query is could the randomized complexity still be just logarithmic. Is this possible?

Generally speaking what is the smallest class $\mathcal C$ that is known such that given a boolean function in $\mathcal C$ it is known that for every input length $n$ we cannot have $\frac1{n^c}$ ($c>0$) fraction of possible inputs computable in $ACC^0$?

There seem to be typos in what you wrote; I take it you're asking: is there a function $f \in NEXP$ such that for all polynomials $p$ and infinitely many $n$, no ACC0 circuit of $p(n)$ size can compute $f_n$ on more than $1-1/p(n)$ inputs of length $n$?

As far as I know, this is open. But here is a possible path to doing it. We know that every $NEXP$-complete function $f$ does not have ACC0 circuits of polynomial size. Perhaps an arithmetization of some $f$ (representing $f$ naturally as a family of multilinear polynomials) over a large field of finite characteristic (e.g. characteristic two) would work. (Arithmetizations can typically give you average-case hardness "for free" ... but one would have to carry out the finite field arithmetic in ACC0, presumably.) Cite me if you figure it out. ;)


Infinite process balls in bins problem Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the maximum load, and throw them to random bins.

What the expected number of balls in the bin with the maximum load is converges to?

A variation of the problem is described in https://www.cs.tau.ac.il/~azar/box.pdf, where instead of taken  the bin with the maximum load, a random ball is  selected at random.

In addition, by my experiments, it seems that for $n=\Theta(m)$ the bin with the maximum load converges $2n/m+1$ balls. I am trying to prove  it.

This exact question is answered in this paper: https://arxiv.org/abs/1807.01804


Can addition be carried out in less than depth 5? Using carry look ahead algorithm we can compute addition using a polynomial size depth 5 (or 4?) $AC^0$ circuit family. Is it possible to reduce the depth? Can we compute the addition of two binary numbers using a polynomial size circuit family with depth less than that obtained by carry look ahead algorithm?

Are there any super polynomial lowerbounds for the size of $AC^0_d$ circuit families computing addition where $d$ is 2 or 3?

By depth I mean alternation depth.

According to Theorem 3.1 in Alexis Maciel and Denis Therien Threshold Circuits of Small Majority-Depth there is indeed a depth-3 circuit for computing the addition of two numbers.

The precise bound is $\Delta_2 \cdot \mathsf{NC}^0_1$ where $\Delta_2 = \Sigma_2 \cap \Pi_2$ are problems which have depth-2 $\mathsf{AC}^0$ circuits with both $\vee,\wedge$ gates at top and $\mathsf{NC}^0_1$ circuits are $\mathsf{NC}^0$ circuits of depth one (see the paper for a detailed explanation of the notation).

The main proof ideas are:

First, express the Carry-lookahead circuit as $\mathsf{NC}^0\cdot\Delta_2\cdot\mathsf{NC}^0$
Next, invoke closure properties of $\Delta_2$ to write this as $\Delta_2\cdot\mathsf{NC}^0$
Finally, use the fact (also proved in the paper) that $\mathsf{NC}^0 \subset \Delta_1\cdot\mathsf{NC}^0_1$


Example of something that’s different for generic and random oracles? Let $G$ be a generic oracle in the sense of Cohen / Baire category.
Let $R$ be a random oracle.

Are there complexity classes A and B with
$$\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^R$$
or the other way around,
$$\mathrm{A}^G\ne\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R= \mathrm{B}^R\text{?}$$

The question was inspired by a comment by Scott Aaronson.

P = UP with a generic (assuming P = PSPACE) but they are separate relative to a random oracle.

In the other direction P = Promise-BPP relative to a random but separate relative to a generic. Can't think of a non-promise class off the top of my head.

I can track down some references if you need.

Update: If you want a non-promise version, $P^{NP} = S^p_2$ with a random oracle (because $S^p_2 \subseteq ZPP^{NP}$) but they separate with a generic oracle (example in my paper with Yamakami).


Maximum clique algorithm on undirected graph Recently I learned about maximum cliques. For fun I came up with an algorithm (described below) to find the maximum cliques in an undirected graph. I'd just like some help constructing a graph s.t. the algorithm returns an incorrect result.

Consider an undirected graph $G$ represented by an adjacency matrix $A$. If there exists an edge directly connecting node $i$ and node $j$ then $A[i][j] = 1$, $A[i][j] = 0$ otherwise.

Construct a hashtable $H$ where the keys are nodes in $G$ and the values are lists of nodes directly connected to the given node. For example a simple triangle graph with nodes $a$, $b$ and $c$ would have $H$ with key-values pairs $(a, [b, c])$, $(b, [a, c])$ and $(c, [b, a])$.
Traverse all keys in $H$. For each key traverse the corresponding value and check if every node in the list is connected to every other node in the list. If a node $i$ is not connected to any single node $j$ then remove $i$ from the list.
Traverse the keys in $H$ again. Keep track of the maximum count $m$ of all values. $m$ will be the size of the maximum clique(s) in $G$.
Traverse the keys in $H$ again. This time print the contents of the value for a given key if value.count equals $m$.

I've tried a variety of graphs as inputs and so far I haven't found a good counter example.

Regarding the algorithm's runtime:

step one can be done in $O(N^2)$ time. This requires visiting every entry of the $NxN$ adjacency matrix $A$. Inserting an entry into $H$ can be done in amortized constant time.
step two takes $O(N^3)$ time. Traverse every key in $O(N)$ time. For a given key $k$ checking all the directly connected nodes takes $O(N^2)$ time.
step three runs in linear time
step four runs in $O(N^2)$ time (when accounting for printing the nodes)

So the overall runtime is $O(N^3)$ where $N$ is the number of nodes in $G$.

From some research it doesn't sound like finding maximum cliques in an undirected graph (without any constraints on the graph) can be done in polynomial time. Hence there's probably some nice corner cases for the above algorithm. Please help find some.


Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time Recently I've begun considering how one could generate and solve an $n \times n\times n$ Rubik's cube for $n$ well over 10,000. To solve such a cube is feasible; easily implementable parallelizable algorithms to solve such large cubes can be created with the methods listed here:

link 1

link 2

Such can be executed in $O(n^2)$ time, considering that they rely on short sequences of moves that only displace a couple of cubes, and do not have to compute individual rotations. But scrambling is another story. Given that a randomly executed move takes time $\Omega(n)$ and the diameter of the graph of the group of Rubik's cubes is $\Theta(n^2/\log n)$, a naive scramble would take $\Omega(n^3/ \log n)$, which is not at all feasible. Given that, is there an algorithm for scrambling large Rubik's cubes which:

Takes $O(n^{2+\epsilon})$ time
Produces every possible reachable configuration with positive probability, and only produces such configurations
Is not extremely skewed

Well, the easy answer is that you don't traverse the graph of moves, you just generate a random group element directly.  A non-face-center cubie in an NxNxN cube will have an orbit of size 8, 12, 24 or 48, with 8 being possible only for corner cuties and 12 only being possible for edge-center cubies with N odd.  Divide the cubies into orbits, then generate a random permutation for each orbit with the restriction that the total permutation across all orbits must be even.  Then generate orientations for all edge and corner cubies, with a mod-2 parity restriction on each edge orbit and a mod-3 parity restriction on the corners.
I believe that covers all of the parity issues with the order-N Rubik's cube group, which means this method would generate random cubes uniformly distributed across the group.
This takes $O(N^2)$ time.


Top-k frequent items in data stream Paper "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" introduce an efficient algorithm which can help to estimate distinct items in large data set.

I am thinking about few related question:

Given a large data set (total data size is known), how to find top k frequent items? better to use less space.
Simple approach(count frequency of each item in data set, and sort) requires lots of space
What about finding top k frequent items in data stream?

Is there any near-optimal algorithms avaiable? or, can we prove relationship between space requirement and error ratio?

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

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

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


Is it possible to find a non-cut vertex in O(|V|) time? Let $G = (V, E)$ be an undirected connected graph, which is represented by an adjacency list. A vertex is called a cut vertex if removing this vertex with its incident edges from $G$ makes the graph disconnected. Finding a cut-vertex can be done in linear time.

My question is as follows: is it possible to find a non-cut vertex in $O(|V|)$ time?

My idea is to find a spanning tree of $G$, since all leaves of the spanning tree are non-cut vertices. However, I cannot find a spanning tree in $O(|V|)$ time.

Although I can find a cycle in $O(V)$ time, finding a non-cut vertex in a cycle seems not obvious to me.

I am wondering whether this problem has been solved, and I would appreciate any pointers provided by anyone.

It's not possible for a deterministic algorithm: an adversary can always either fool the algorithm or make it look at $\Omega(n^2)$ entries of the adjacency lists.

Let $H$ be a disjoint union of two $n/4$-regular complete bipartite graphs. The adversary will remove a path of three vertices (not revealed to the algorithm) from each of the two components of $H$, and then replace these four removed edges by a different four edges that reconnect the two components, preserving $n/4$-regularity. It can do this in either of two ways:

Swapping the middle vertices of each path results in a graph $H'$ with no non-cut vertices.
Replacing one path by an edge connecting its endpoints, and splicing its former middle vertex into the interior of the other path, results in a graph $H''$ with one cut vertex. The cut vertex can be made to be either of the two former middle vertices.

However, by employing the strategy of making the removed path be in the last place the deterministic algorithm will look for it, it can force the algorithm to either not find the path (and not be able to distinguiish $H'$ from $H''$) or examine $\Omega(n^2)$ edges of the graph. In particular, as long as it is possible to answer a query (what is the $i$th entry of the adjacency list for vertex $v$) consistently with $H$, the adversary does so. Once the adversary is forced to choose the remaining path edges, it makes this choice arbitrarily, along with the choice of $H'$ or $H''$, and then answers the remaining queries according to the choice it made.

In order to force the adversary to choose between $H'$ or $H''$, the deterministic algorithm must see a set of edges that covers all two-edge paths on at least one of the two components on $H$. But each component of $H$ has $\Omega(n^2)$ disjoint two-edge paths, so the deterministic algorithm must see $\Omega(n^2)$ edges before it covers them all. And if it doesn't force the adversary to choose, then it is unable to distinguish graphs that have a cut vertex from those that don't, or to tell which vertex is the cut vertex.


Weighted SAT: is this a known problem? Given an arbitrary SAT instance, I would like to find the solution with the minimum weight. The weight of a valid assignment is computed using a function.

Is this a known problem or are there other problems that I can reduce this one to?

If the function is linear, then you can reduce to MaxSAT. Then there are some related formalisms like pseudo-boolean optimizatin (PBO) or integer linear programming (ILP).


Transitioning from quantum to classical random walks on the line Quick version

Are there models of decoherence for the quantum walk on the line such that we can tune the walk to spread as $\Theta(t^k)$ for any $1/2 \leq k \leq 1$?

Motivation
Classical random walks are useful in algorithm design, and quantum random walks have proven useful for making a number of cool quantum algorithm (sometimes with provable exponential speed-ups). Thus, it is important to understand the difference between quantum and classical random walks. Sometimes, the easiest way to do this is to consider toy models, such as walks on the line.
There is a physics motivation as well: it is interesting to know how quantum mechanics scales to classical mechanics. But this is not very relevant to cstheory.
My personal motivation is completely orthogonal: I am trying to match some experimental data with a model that transitions smoothly from quantum to classical and is relatively intuitive.
Background
When considering quantum and classical walks on the integer line, a key difference is that the standard deviation (of the position distribution) of the quantum walk goes as $\Theta(t)$ and classical ones as $\Theta({t^{1/2}})$ where $t$ is the number of steps for a discrete model, or time in a continuous model. Note that this is not restricted to the line, and for many graphs you will see a similar quadratic relationship between the quantum and classical mixing time, I consider the restricted case of the line since I think it is easier to analyze.
As we introduce decoherence to a quantum walk (either through measurement or noise) the walk starts to behave more classically. In fact, for most measurements, we just end up with a classical walk that spreads as $\Theta(t^{1/2})$ if viewed from the right timescale. For other forms of decoherence (such as dephasing the coin, or introducing imperfections in the line) there is usually a sharp threshold below which the walk behaves quantumly (spread as $\Theta(t)$) and above which the walk starts to be classical (spread as $\Theta(t^{1/2})$). In fact, this scaling has even been suggested as the definition of a quantum walk.

Long version of question
Are there models of decoherence for a random walk on the line, such that as we vary the amount of decoherence we can achieve a standard deviation in position that scales as $\Theta(t^k)$ for any $1/2 \leq k \leq 1$? Alternatively for other graphs with a gap in mixing or hitting time, is there forms of decoherence so that we can have the mixing/hitting/standard deviation that goes as $f(t)$ for any $f \in \Sigma(g(t))$ and $f \in O(h(t))$ where $g(t)$ is the classical mixing/hitting/STD and $h(t)$ is the pure quantum. If this is not possible then is there a deeper reason why we see this sort of one-or-the-other behavior?

Great question. Actually, the same question popped up in something I was working on a few months ago (arXiv:1011.1217). It seems that any natural kind of decoherence leads to behaviour that looks initially balistic, but which becomes diffusive as time increases, so you are transitionioning between a $t$ regime and a $t^{\frac{1}{2}}$ regime. See figure 2 in the above paper for an example of this. This seems to be the natural behaviour as your state gradually loses coherence.

This would seem to suggest that the variance only ever scales as $t$ or $t^2$, and hence the walk spreads as $t^{\frac{1}{2}}$ or $t$.

However, exactly the same thing happens in quantum metrology when noise is introduced, but can be overcome to yield an intermediate scaling (see for example J. A. Jones et al, Science, 324, 5931 (2009), arXiv:1103.1219, arXiv:1101.2561, etc.). One way this can be achieved is by making intermediate measurements.

Imagine you measure the position of the walker after every period of time $T$ collapsing the wavefunction, and allow free evolution in between. Now, imagine we want to evolve the system for total time $t=nT$. Then the variance in the position of the walker after this time will be $\mbox{Var}(x(nT)) = \sum_{i = 1}^n \mbox{Var}(x(T)) = n \mbox{Var}(x(T))$. In the absence of other decoherence we know the walker moves ballistically, and hence $\mbox{Var}(x(T)) = T^2$, and so the $\mbox{Var}(x(t)) = n T^2$. However, as $t=nT$, we can take $n\propto t^k$ and $T\propto t^{1-k}$. Thus $\mbox{Var}(x(t)) = t^{2-k}$. This way you can achieve any intermediate scaling, by chosing the measurement interval appropriately.


Hilbert's Tenth Problem and nonrecursive Diophantine sets In her paper Defining Integers, Alexandra Shlapentokh presents the following as an immediate corollary of the undecidability of Hilbert's Tenth Problem --- that is, the language $\{p : p$ is a polynomial with integer coefficients with at least an integer root $\}$:

Corollary 1.5. There are undecidable Diophantine subsets of $\mathbb{Z}$

I'm not sure this is a consequence of the undecidability of HTP, so maybe I misread, and what the author is saying is that this is a consequence of the correspondence between recognizable sets and Diophantine sets.

Question: Is Corollary 1.5 a direct consequence of the undecidability of HTP?

Question (rephrased): Suppose every Diophantine set is decidable; does this imply that HTP is decidable?

Looking at the paper, I believe that what Shlapentokh is saying is that "there is an undecidable Diophantine subset of $\mathbb Z$" is an immediate consequence of "there is an r.e. set that is not recursive" and the MRDP theorem, where by the "MRDP theorem" is meant "A set is Diophantine if and only if it is r.e."  Nothing deeper than that.


Throwing Balls into Bins, estimate a lowerbound of its probability This is not a homework, though it looks like. Any reference is welcome. :-)

Scenario: There are $n$ different balls and $n$ different bins (labled from 1 to $n$, from left to right). Each ball is thrown independently and uniformly into bins. Let $f(i)$ be the number of balls in the $i$~th bin. Let $E_i$ denote the following event.

  For each $j\le i$, $\sum_{k\le j}{f(k)} \le j-1$

That is, the first $j$ bins (the most left $j$ bins) contains less than $j$ balls, for each $j\le i$.

Question: Estimate $\sum_{i<n}{Pr(E_i)}$, in terms of $n$? When $n$ goes infinity. A lowerbound is preferred. I do not think an easily calculated formula exisit.

Example: $\lim\limits_{n\to\infty}{Pr(E_1)}=\lim\limits_{n\to\infty}{(\frac{n-1}{n})^n}=\frac{1}{e}$.  Note $Pr(E_n)=0$.

My guess: I guess $\sum_{i<n}{Pr(E_i)}=\ln n$, when $n$ goes infinity. I considered the first $\ln n$ items in the summation.

The answer is $\Theta(\sqrt{n})$.

First, let's compute $E_{n-1}$.

Let's suppose we throw $n$ balls into $n$ bins, and look at the probability that a bin has exactly $k$ balls in it. This probability comes from the Poisson distribution, and as $n$ goes to $\infty$ the probability that there are exactly $k$ balls in a given bin is $\frac{1}{e} \frac{1}{ k!}$.

Now, let's look at a different way of distributing balls into bins. We throw a number of balls into each bin chosen from the Poisson distribution, and condition on the event that there are $n$ balls total. I claim that this gives exactly the same distribution as throwing $n$ balls into $n$ bins. Why? It is easy to see that the probability of having $k_j$ balls in the $j$th bin is proportional to $\prod_{j=1}^n \frac{1}{k_j!}$ in both distributions.

So let's consider a random walk where at each step, you go from $t$ to $t+1-k$ with probability $\frac{1}{e}\frac{1}{k!}$. I claim that if you condition on the event that this random walk returns to 0 after $n$ steps, the probability that this random always stays above $0$ is the probability that the OP wants to calculate. Why? This height of this random walk after $s$ steps is $s$ minus the number of balls in the first $s$ bins.

If we had chosen a random walk with a probability of $\frac{1}{2}$ of going up or down $1$ on each step, this would be the classical ballot problem, for which the answer is $\frac{1}{2(n-1)}$. This is a variant of the ballot problem which has been studied (see this paper), and the answer is still $\Theta\left(\frac{1}{n}\right)$.
I don't know whether there is an easy way to compute the constant for the $\Theta\left(\frac{1}{n}\right)$ for this case.

The same paper shows that when the random walk is conditioned to end at height $k$, the probability of always staying positive is $\Theta(k/n)$ as long as $k = O(\sqrt{n})$. This fact will let us estimate $E_s$ for any $s$.

I'm going to be a little handwavy for the rest of my answer, but standard probability techniques can be used to make this rigorous.

We know that as $n$ goes to $\infty$, this random walk converges to a Brownian bridge, i.e., Brownian motion conditioned to start and end at $0$. From general probability theorems, for $\epsilon n < s< (1-\epsilon)n$, the random walk is roughly $\Theta(\sqrt{n})$ away from the $x$-axis. In the case it has height $t>0$, the probability that it has stayed above $0$ for the entire time before $s$ is $\Theta(t/s)$. Since $t$ is likely to be $\Theta(\sqrt{n})$ when $s = \Theta(n)$, we have $E_s \approx \Theta(1/\sqrt{n})$.


Does the $\mathsf{TC^0}$ hierarchy collapse? Do we know that the $\mathsf{TC^0}$ hierarchy does not collapse ($\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ for all $d$)?

The Zoo entry for $\mathsf{TC^0}$ only mentions the separation between depth 2 and 3.

Also is there a standard reference for the fact that $\mathsf{AC^0_d}$ hierarchy does not collapse?

We know of no good lower bounds (meaning, say, a superpolynomial lower bound for a language in $\mathsf{NEXP}$) for depth 2 threshold circuits (unbounded weights). Depth 3 circuits built from majority gates, i.e. $\mathsf{TC}^0_3$ contains this class, and thus we know no good lower bounds for this class either.


Define the properties of a grammar that is the fastest to parse It's possible to define the properties of a grammar that is fast to parse as it is indeed possible to classify algorithm based on their complexity ?

In other words it's possible to evaluate and define grammars based on their "computational" properties/behaviour ?

Your question is unclear. When you write "parse", do you actually mean
to produce a parse structure (one, or all possible ones). How do you define
it ? For example, some grammars have a parse tree that differs from the
derivation tree. Or did you mean that the language must be fasted to
recognize?  Regular grammars give you languages that are recognized
in linear time. What qualifies as a grammar? Actually, if you are just
interested in recognition, you are looking for properties of languages
rather than properties of grammar (though they can be related).

You can certainly build hierarchies of grammars according to
complexity criteria if you clarify the above.

For example in the case of Context-Free grammar, the is nearly a well
defined concept of parsing (up to specifying whether you want one
parse tree or all possible parse trees).

The complexity is at worst $O(n^3)$ for parsing and $O(n^{2.373})$ (due to valiant, with a looser bound at the time) for
recognition (wich is only asymptotic, and not the fastest in any
realistic situation). There are CF grammar that will parse in linear
time (notably deterministic grammars), others  will parse in $O(n^2)$
time, and others are believed to require more (though the exact
complexity bound is not known), even for simple recognition.

I do not really know if these complexity hierarchies have been
identified precisely.

The usual hierarchies studied for context-free grammars are often more
related to the applicability of techniques that can be used to build
parsers for these grammars.

As the question is stated, I guess there is one language that is faster than any other to recognize. That is the Babel language invented (nearly) by Jorge Luis Borges and containing all possible string (Borges was unfortunately limited to a finite size due to paper shortage, which would invalidate what I am saying). With all strings of any size, recognition is easy. You start in an accepting state and terminate in 0 steps.
The empty language is recognized as fast. I believe these are the only ones recognized in 0 steps (for a given alphabet). This establishes that, if the alphabet is fixed, the class of languages recognizable in 0 time is closed under complementation.

This is of course in jest, but you can see from it that one can define languagesn and corresponding grammars, that can be recognized in constant time, by putting constraints only on a finite prefix of strings. They are not much more interesting. The problem is in the statement of the question.

I guess the fasted interesting class of CF grammars is the class parsable in linear-time. Deterministic CF grammars are clearly member of that class, so that is a sufficient property. However many non-deterministic languages, having no deterministic grammars, can also be parsed in linear time.


Is induced subgraph isomorphism easy on an infinite subclass? Is there a sequence of undirected graphs $\{C_n\}_{n\in \mathbb N}$, where each $C_n$ has exactly $n$ vertices and the problem

  Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$?

is known to be in class $\mathsf{P}$? (For example, when $C_n=K_n$, this is the NP-complete clique problem.)

If I'm not mistaken your question was answered by Chen-Thurley-Weyer-2008 modulo parameterized complexity assumptions.

I didn't read the paper carefully yet, but as far as I understood, there is a dichotomy in the sense that if $C$ is finite then the problem is in $P$, but if $C$ has an infinite number of graphs then the induced subgraph isomorphism is $W[1]$ complete (Corollary 4, page 6).

Thus it seems that unless the first level $W[1]$ of the $W$ hierarchy collapses to $FPT$, there is no such an infinite class of graphs whose induced subgraph isomorphism is in $P$.

There is another interesting result stating that if $P\neq NP$ then there are classes for which the induced isomorphism is neither in $P$ nor $NP$ complete.


What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture? There are many inapproximability results which rely on the unique games conjecture.  For example,

  Assuming the unique games conjecture, it is NP-hard to approximate the maximum cut problem within a factor R for any constant R > RGW.

(Here RGW = 0.878… is the approximation ratio of the Goemans–Williamson algorithm.)

However, some people prefer to use the term “UG-hard” as:

  It is UG-hard to approximate the maximum cut problem within a factor R for any constant R > RGW.

Is the latter just a shorthand for the former, or do they mean different statements?

An earlier version of this answer was originally posted as an answer to the question “Consequences of Unique Games being a NPI problem” by NicosM.  Because it turned out that it did not answer what he wanted to ask, I moved it to this question.

Short answer: They mean different statements.  The latter implies the former, but the former does not necessarily imply the latter.

Long answer: Recall that the unique game problem is the following promise problem.

Unique game problem with parameters k∈ℕ and ε, δ > 0 (1−ε > δ)
Instance: A two-player one-round unique game G with label size k.
Yes-promise: G has value at least 1−ε.
No-promise: G has value at most δ.

The unique games conjecture states:

  Unique games conjecture.  For all constants ε and δ, there exists a constant k such that the unique game problem with parameters k, ε, and δ is NP-complete.

Consider results of the following form:

  (1) Assuming the unique games conjecture, problem X is NP-hard.

(An example of X is the problem of approximating maximum cut within some constant factor R > RGW.)

Most (if not all) of the results of the form (1) actually prove the following fact:

  (2) There exist constants ε and δ such that for every constant k, the unique game problem with parameters k, ε, and δ is reducible to X.

It is easy to verify that (2) implies (1).  However, (2) implies more than (1): for example, suppose that one day we can prove that a variant of the unique games conjecture where “NP-complete” is replaced with “GI-hard.”  Then (2) implies that X is also GI-hard.  (1) does not imply this.  This is why some people consider that statement (1) is not the best way to state the theorem: (1) is weaker than what is actually proved, and the difference might be important.

Although (2) is a more accurate statement of what is proved, it is clearly mouthful.  This is why people have come up with a shorthand for it: “Problem X is UG-hard” is a shorthand for (2).


Building a decision tree to approximate a known function (not to learn an unknown function) I have a function $f: \mathbb{D} \rightarrow \{0,1\}$ where $\mathbb{D} \in \mathbb{R}^{5000}$.

I would like to approximate $f$ using a decision tree.

Up to now I have only found literature in the context of machine learning, where $f$ is unknown, some samples $(x_i,\ y_i=f(x_i) + \mathrm{noise})$ are available and $f$ is estimated using a decision tree. That is a learning problem.

In my case I have a known (non trivial) expression for $f$ and I want to obtain the shortest binary decision tree for an arbitrarily good approximation (up to a specific error $\epsilon$). This seem to be a different problem than the learning problem (for instance, there is no regularization term to ensure generalization).

I suspect this problem to "hard". I assume some literature must exist on "no guarantees, greedy approaches" or similar, but I have not be able to find any.

Could any of you point me out some paper or book referring to this problem ?

Thanks for you answers.

For bitstring to boolean functions, people usually build binary decision diagrams instead of decision trees to represent functions compactly. If you want to find a small BDD and are willing to sacrifice correctness on a few inputs (as your question implies) then you might want to look into approximate BDDs as studied in the following two papers:

Hinsberger, U., Kolla, R., and Kunjan, T. [1997] "Approximative Representation of boolean Functions by size controllable ROBDD's"

Ravi, K., McMillan, K.L., Shiple, T.R., and Somenzi, F. [1998] "Approximation and decomposition of binary decision diagrams"

I am not sure if there is work that generalizes this for $\mathbb{R}^d \supset \mathbb{D}  \rightarrow \{0,1\}$ functions, but I would use those papers as a starting point and do a forward-reference search.


what are known bounds on complexity of nontrivial graph automorphism Given any simple undirected graph G, it is nontrivial to determine if G has nontrivial (non-identity) automorphisms. But what are results on upper/lower bounds of this decision problem?

Determining if a graph has a nontrivial automorphism Cook-reduces (polynomial time Turing) to Graph Isomorphism (determine if a pair of graphs is isomorphic) (exercise for the reader).  It is not known to be equivalent to graph isomorphism.

In turn, graph isomorphism can be solved in $2^{\tilde O(\sqrt{n})}$ time and lies in $NP \cap coAM$.  In particular, it is not $NP$-complete unless the polynomial hierarchy collapses.


Small number of inequalities defining integer hull of integer programming problem In integer programming problem, we often want to relax the integer programming problem to linear programming problem. So we want to find the integer hull of the problem. The number of inequalities to define this integer hull is exponential in general, but are there some conditions in which the number of inequalities to define the integer hull is relative small, say, polynomial to the number of constraints? Are there any research about this?

"Is there research on this". Well, a great share of the operation research consists in finding linear (or, now, semidefinite or other convex cone) relaxations of combinatorial problems, such that the linear relaxation matches or nearly matches the exact integer hull; so if it nearly matches, then one can perhaps prove some results such as "the optimum in the relaxation does not approximate the exact optimum by more than factor X".

An interesting approach is to lift the problem to a higher dimension. In general, the projection of a polyhedron to lower dimension may have many more constraints than the original, thus the converse (expressing a polyhedron as a projection of a higher dimension polyhedron) may be interesting so as to lower the number of constraints. This led to the family of methods known as "lift and project".


Quantum Channel Decoding Let a quantum channel $\Phi(\cdot)$ between two Hilbert spaces $\mathcal{H}_{in}$ and $\mathcal{H}_{out}$.
What is the quantum channel $\Phi_{inv}(\cdot)$ that best reverses $\Phi(\cdot)$ ?

$\forall $ states $\rho$, the state $\widetilde{\rho} \equiv \Phi_{inv}(\Phi(\rho))$ should be the best approximation of $\rho$ (according to some appropriate distance measure).

If we assume that the input state comes from a known probability distribution, according to the quantum data processing inequality there are cases, depending on the source entropy and the channel properties that allow for perfect decoding.

However, how do you perform decoding in cases where perfect decoding is not possible, and in particular if no source distribution is known (so you can't assume that the state has been encoded with an error-correcting code)? I presume somebody has already thought about this, but I can't find it in the literature.

First, your two criteria (that it is a quantum channel and that for all input states, the inverse channel gives the best approximation of the input state) aren't compatible. If they were, then the optimal inverse channel would be independent of whether you choose to optimize the worst-case fidelity or the average-case fidelity. It's not.

There are quite a few papers on this question. Here's one Andrew Fletcher, Moe Win, and I wrote. It shows you can use a semidefinite program to optimize the recovery channel when the criterion to be optimized is the entanglement fidelity, and you assume a specific entangled input state and a specific channel $\Phi$. You should be able to find other papers by looking at our bibliography and using some forward citation tool.


Total flow using minimum number of edges on a bipartite network If I have a set of sources $S$ with total capacity $C$ and a set of sinks $T$ with the same capacity $C$, but not necessarily the same cardinality, is there an efficient way to find the minimum number of direct edges between sources and sinks and their required capacity, assuming $flow=C$?

TIA, Luis

Your problem is NP-hard.
Consider a partition problem instance with input $a_1,\ldots,a_n$.
We create a complete bipartite graph with $2$ source vertices each with capacity $\frac{1}{2} \sum_{i=1}^n a_i$, and $n$ sink vertices, where the $i$th vertex has capacity $a_i$. Each edge has infinite capacity.

It's easy to verify there is a partition with equal sum if and only if the solution to your problem on $G$ has $n$ edges.


Minimal number of hyperplanes needed to separate sets of points from one other set Let $\mathbb{R}^d$ be our space. We have a single good set of points $g$, and a collection of bad sets of points $B$.

We assume that for all $b \in B$ the convex hulls of $g$ and $b$ are disjoint. This means that there exist a hyperplane separating $g$ and $b$ (which we can find  in poly time with linear programming). We could repeatedly cut our space, eliminating one $b$ at a time, and be left with a subspace that only contains $g$ from our initial sets - this is what we want.

But we can do (a lot) better - we could separate multiple $b \in B$ from $g$ simultaneously with a single hyperplane. Is there an efficient algorithm that finds the minimal number of hyperplanes needed (and the partition of $B$ into groups you eliminate simultaneously)?

Your problem is NP-complete, even in the following two highly restricted cases:

The dimension $d$ is part of the input, and the question is whether you can separate set $B$ from set $G$ by $k=2$ hyperplanes.
The dimension is $d=2$ (and the number $k$ of separating hyperplanes is part of the input).

This has been proved in:

  Nimrod Megiddo
  On the Complexity of Polyhedral Separability
  Discrete and Computational Geometry 3, pp 325-337, (1988).


Equivalent embeddings of a graph I have difficulties finding a good definition of two embeddings of a (planar) graph in the plane being equivalent.
Intuitively I mean by equivalent that the embeddings look the same up to homeomorphism of the faces.

The only definition I found was:

Two embeddings of a graph are equivalent if for each vertex all
incident edges have the same circular clockwise order in both embeddings.

But this is not strong enough to match my intuitive view, since this notion of equivalence allows connected components to be arbitrarily contained in each other.

[Reposting comment as an answer, based on the OP's response to the comment.]

For a combinatorial definition, it seems like what you're looking for is a circular ordering around the vertices together with a map $f$ from the set of components to the set of faces such that $f(C_i)$ is the face of the graph that contains the component $C_i$.

If you prefer a topological definition, I believe what you're looking for is that the map between the graphs can be extended to a map from the plane to itself that is isotopic to the identity. (Isotopy is, for example, the topological relation typically used to define two knots as being equivalent.)


Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$ Consider the problem that receives two trees $T_1$, $T_2$, and asks to find a minimum size tree $T$ such that there exists a subtree of $T_1$ which is isomorphic to $T$, but there is no such isomorphic subtree in $T_2$.

  What is known about the complexity of this problem?

You can put a tree into a cannonical form in $O(n)$ with leaf contractions. Read, Ronald C. (1972), "The coding of various kinds of unlabeled trees", Graph Theory and Computing, Academic Press, New York, pp. 153–182

When $T_{1}$ and $T_{2}$ are isomorphic you can solve it in $O(n)$.

Shamir's paper has $O({k^{1.5}\over log\ k}n)$ for testing if one tree is a subtree of the other, https://www.cs.bgu.ac.il/~dekelts/publications/subtree.pdf

Not sure if that helps.


Partial soundness proofs for pragmatic static analyses I was reflecting on a comment by Rob Simmons on unsound static analyses:

  An analysis that is neither sound nor complete is called pragmatic by Jaspan, as there aren't any theorems to be proved about such an analysis: they can be justified only by their utility in practice.

This is a pretty unsatisfying way to evaluate a static analysis; surely, we can make stronger claims than statistical correlations. Could we, perhaps, show that analyses are sound given some additional assumptions on the program?

Consider the classic example of determining if a variable in a C program is constant.  A sound analysis requires a points-to analysis; an unsound analysis requires only a syntactic scan. It seems that it would be straightforward to prove the soundness of this analysis if we also assume that, at every assignment through a pointer, that pointer does not refer to the variable of interest. Such a proof should easily turn into an analysis that also outputs a finite list of assumptions made about specific program points to guarantee its soundness. Indeed, I already see comments on unsound analyses such as "This system is unsound because it assumes the inputs are unaliased," which suggests the theorem that the system is sound if the inputs are unaliased.

A search for "partial soundness" turns up a type theory paper, but no analysis papers. Systems such as CCured that generate dynamic checks upon the failure of the analysis seem related, but I've not seen them interpreted this way. Is there prior work along these lines?

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

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

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

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

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

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

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

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


Explicit balanced matrix Is it possible to build an explicit $N \times N$ $0/1$-matrix with $N^{1.5}$ ones such that every $N^{0.499} \times N^{0.499}$ submatrix contains less than $N^{0.501}$ ones?

Or probably it is possible to build an explicit hitting set for such property.

It is easy to see that random matrix has this property with probability exponentially close to $1$. Also, expander mixing lemma is not sufficient to derive this property.

I guess pseudorandom generators that fool combinatorial rectangles could help here, but they are designed for uniform distributions and I basically need $B(N^2, N^{-0.5})$ here.

What you are looking for is a one-bit extractor for two independent sources: a function $E:[N]\times [N]\to \{0,1\}$, such that, provided X,Y are random variables with min-entropy 0.499*log(N), E(X,Y) is almost balanced.

It's a notorious hard problem. For the parameters you want, I believe it was solved by Bourgain. See here:
http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf


Revision Tracking Graph Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it. C(x) contains all edges on all paths from a node 0 ( C(0) = {} ). Each edge can be in a set at most once!

You can also describe this data structure by the rules for its growth:

Start with node 0 with associated empty set C(0) = {} = creating new object
For any node x create a new node y where (x,y) is oriented edge from x to y and C(y) = C(x) union { (x,y) } = versioning and branching
For any nodes f and t, create node r, where (f,r) and (t,r) are oriented edges and C(r) = C(f) union C(t) union { (f,r), (t,r) } = merging

Note: You can see there is no mathematical difference between creating new version and a branch. It is a semantical difference depending on whether there is already an edge leading from the node or not.

Base node is defined as a node b, such as C(b) = C(f) intersect C(t), where f and t are nodes representing two versions to be merged.

Simple Merge equation Result=To + (From-Base) = means that if we subtract every edge in C(b) from C(f) and add all edges in C(t) we get a resulting C(r) minus (f,r) and (t,r) edges exactly. No edge would appear twice and all edges in C(f) and C(t) would be represented. = 3-way merge

Complex merge equation Result = To + Sum(i=1..n) for (Fi-Bi), where Fn = From. Each edge can be in exactly one of the sets To, (Fi-Bi). For n=1 this turns into a simple merge equation. In case there exist no base in simple case, we might find sequence of F,B nodes to fit the complex equation. (1+2n)-way merge

I have actually several questions pertaining to this data structure. I am posing the first 3 for "frame of mind", as I already know the answers. And I believe question 4 directly leads to answering question 5, which I really try to get answered.

  Prove there can be no circles in the graph
  Prove that for certain graphs there are such nodes F,T for which base cannot be found as specified in simple equation.
  Create algorithm to find B in simple case where n = 1.
  Prove that for each RTG and each pair of nodes F and T, there is a set of n pairs of nodes Fi,Bi, where i=1..n to fit the complex merge equation.
  Create algorithm to find minimum n and Fi,Bi for i=1..n where n > 1.

If you insist that the edges in the complex merge equation don't appear twice (eg. that the + you use is actually a disjunctive union), and you only subtract sets that are superset of one another (*), I think the assertion you want to prove (4) is actually false. Imagine RTG with 5 vertices and 6 edges:
V = { 0, a, b, c, d }
E = { (0,a), (0,b), (a,c), (a,d), (b,c), (b,d) }

now, if To = c and F = d: C(c) contains already all the edges except (b,d) and (c,d), So Sum (Fi-Bi) has to be exactly those edges. Since these edges are only contained in C(d), they must be (not necessarily both) contained in summand d-B for some B. But that is not possible, because whatever B we choose, we add also edges that are already in C(To).
(*) otherwise the assertion (2) is actually false: Result = To + (From - To) satisfies the simple merge equation for all From and To (even if it looks bizarre).
Long story short: You gave inadequate or incomplete definitions.

Q: Why do we have to state definitions rigorously if the proofs are usually trivial if the definitions are right?
A: The definitions are almost always wrong.


Evidence that there is some problem in BQP distinct from BPP? Are there any evidences (1 physics, 2 mathematics AND 3 computer science) that particular problems such as integer factorization, discrete logarithm are in BQP but not in BPP? There do not seem to be any classical collapse results if these problems are in BPP. Is there reason to think BQP is certainly a class different from BPP?

Scott Aaronson has been addressing this topic: http://arxiv.org/abs/0910.4698

Related hardness results:

Boson sampling: http://arxiv.org/abs/1011.3245
Commuting circuits: http://arxiv.org/abs/1005.1407
DQC1 model: http://arxiv.org/abs/1509.07276
Extended Clifford circuits: http://arxiv.org/abs/1305.6190


Minimum equidecomposable decomposition Given two polyhedra $P$ and $Q$, $P$ and $Q$ are are equidecomposable if there are finite sets of polyhedra $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ such that $P_i$ and $Q_i$ are congruent for all $i$, $P = \cup_{i=1}^n P_i$ and $Q = \cup_{i=1}^n Q_i$. It is known that if $P$ and $Q$ are polygons of equal area, such an equidecomposition always exists and that this does not hold in general for higher dimensions.

I am curious as to the complexity of the minimum equidecomposition problem:

  For two polygons $P$ and $Q$, find a equidecomposition $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ that minimizes $n$.

Are there algorithms (exact, polynomial, exponential, approximation) for this?  Is the complexity known?

For disconnected one-dimensional regions with integer coordinates, equidecomposition into a minimum number of pieces is strongly NP-hard via an easy reduction to 3SUM: if one shape has segments whose lengths are the 3SUM inputs and the other has segments whose lengths are the bins you have to pack them in, then you can do it with no additional cutting iff the 3SUM instance is solvable. For two-dimensional polygons it remains hard, even for connected regions: thicken the segments of a one-dimensional problem to unit-height rectangles and connect them by thin "strings" that have too small an area to affect the 3SUM part of the problem but are easy to handle in the decomposition.

(Disclaimer: I borrowed this reduction idea from some not-yet-published joint work with many other people on hardness of some other problems.)


Constant Depth Circuit Computing Threshold Function One of the most basic result in circuit complexity is the constnat depth cirdcuit lower bound computing PARITY function using the switching lemma.

Another popular function MAJORITY has also lower bound $exp (\Omega (n^{1/(d-1)}))$ and matching upper bound $exp (O (n^{2/(d-1)}))$.

My question is about upper bound of Threshold function which is a natural generalization of majority function.

The formal definition of the threshold function is the following one.

DEFINITION:

$THR(x_{1},...,x_{n})=
  \begin{cases}
    1 & a_{1}x_{1}+\cdots +a_{n}x_{n} \geq t \\
    0 & otherwise
  \end{cases}
$

We assume that each weight $a_{i} \in \mathbb{Z}$ is at most $2^{O(n)}$

QUESTION1:
The depth $d$ circuit with unbounded fanin AND OR NOT gates to compute the above function has size $2^{n^{\epsilon}}$ ?

Where $\epsilon $ can depend on $d$ like $2^{n^{1/100d}}$ .

QUESTION2

Can we $\textit{relax}$ the assumption that   $a_{i} \in \mathbb{Z}$ is at most $2^{O(n)}$ ?

For example, even if we assume that  $a_{i} \in \mathbb{R}$ is at most $2^{2^{O(n)}}$ and give the strong power of each threshold gate, does uppwer bounds  $2^{n^{\epsilon}}$  holds ?

General weight threshold gates can be computed by polynomial size depth 2 circuits built from majority gates. An efficient construction of this is e.g. given by Amano and Maruoka. Then you can just compute each of these by constant depth circuits built from AND and OR gates.
You can always assume weights are integers of magnitude at most $(n+1)^{(n+1)/2}/2^n$. See Muroga, Toda and Takasu