Theory of Computing Blog Aggregator

So, the Templeton Foundation invited me to write a 1500-word essay on the above question.  It’s like a blog post, except they pay me to do it!  My essay is now live, here.  I hope you enjoy my attempt at techno-futurist prose.  You can comment on the essay either here or over at Templeton’s site.  Thanks very much to Ansley Roan for commissioning the piece.

by Scott at July 22, 2014 01:27 PM UTC

We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On the other hand, Say and Yakary?lmaz showed that computation with just 1 classical CTC bit gives the power of “postselection”, thereby upgrading classical randomized computation (BPP) to the complexity class BPP path and standard quantum computation (BQP) to the complexity class PP. It is natural to ask whether increasing the number of CTC bits from 1 to 2 (or 3, 4, etc.) leads to increased computational power. We show that the answer is no: randomized computation with logarithmically many CTC bits (i.e., polynomially many CTC states) is equivalent to BPP_path. (Similarly, quantum computation augmented with logarithmically many classical CTC bits is equivalent to PP.) Spoilsports with no interest in time travel may view our results as concerning the robustness of the class BPP_path and the computational complexity of sampling from an implicitly defined Markov chain.

at July 22, 2014 11:48 AM UTC

How to find approximate page rank fast, among other things


Jennifer Chayes is the current director of a research lab in Cambridge—that is Cambridge Massachusetts—for a company called Microsoft. She is famous for her own work in many areas of theory, including phase transitions of complex systems. She is also famous for her ability to create and manage research groups, which is a rare and wonderful skill.

Today Ken and I wish to talk about how to be “shifty” in algorithm design. There is nothing underhanded, but it’s a different playing field from what we grew up with.

Ken first noted the paradigm shift in 1984 when hearing Leslie Valiant’s inaugural talk on “Probably Approximately Correct” learning at the Royal Society in London. Last year Leslie wrote a book with this title. That’s about learning, while here we want to discuss the effect on algorithm design.

We illustrate this for a paper (ArXiv version) authored by Chayes and Christian Borgs, Michael Brautbar, and Shang-Hua Teng. It is titled, “Multi-Scale Matrix Sampling and Sublinear-Time PageRank Computation.” Since PageRank is a vital application, they don’t want their algorithms to be galactic. They trade off by not having the algorithms “solve” the problems the way we used to.

In The Good Old Days

I, Dick, recall the “good old days of theory.” When I first started working in theory—a sort of double meaning—I could only use deterministic methods. I needed to get the exact answer, no approximations. I had to solve the problem that I was given—no changing the problem. Well sometimes I did that, but mostly I had to solve the problem that was presented to me.

In the good old days of theory, we got a problem, we worked on it, and sometimes we solved it. Nothing shifty, no changing the problem or modifying the goal. I actually like today better than the “good old days,” so I do not romanticize them.

One way to explain the notion of the good old days is to quote from a Monty Python skit about four Yorkshiremen talking about the good old days. We pick it up a few lines after one of them says, “I was happier then and I had nothin’. We used to live in this tiny old house with great big holes in the roof.” …

{\mathsf{FIRST \ YORKSHIREMAN}}: You were lucky. We lived for three months in a paper bag in a septic tank. We used to have to get up at six in the morning, clean the paper bag, eat a crust of stale bread, go to work down t’ mill, fourteen hours a day, week-in week-out, for sixpence a week, and when we got home our Dad would thrash us to sleep wi’ his belt.

{\mathsf{SECOND \ YORKSHIREMAN}}: Luxury. We used to have to get out of the lake at six o’clock in the morning, clean the lake, eat a handful of ‘ot gravel, work twenty hour day at mill for tuppence a month, come home, and Dad would thrash us to sleep with a broken bottle, if we were lucky!

{\mathsf{THIRD \ YORKSHIREMAN}}: Well, of course, we had it tough. We used to ‘ave to get up out of shoebox at twelve o’clock at night and lick road clean wit’ tongue. We had two bits of cold gravel, worked twenty-four hours a day at mill for sixpence every four years, and when we got home our Dad would slice us in two wit’ bread knife.

{\mathsf{FOURTH \ YORKSHIREMAN}}: Right. I had to get up in the morning at ten o’clock at night half an hour before I went to bed, drink a cup of sulphuric acid, work twenty-nine hours a day down mill, and pay mill owner for permission to come to work, and when we got home, our Dad and our mother would kill us and dance about on our graves singing Hallelujah.

{\mathsf{FIRST \ YORKSHIREMAN}}: And you try and tell the young people of today that ….. they won’t believe you.

{\mathsf{ALL}}: They won’t!


Those were the days. I did feel like I sometimes worked twenty-nine hours a day, I was paid by Yale, but so little that perhaps it felt like I paid them. Never had to drink a cup of sulphuric acid—but the coffee—oh you get the idea.

Now today, in the 21st century, we have a better way to attack problems. We change the problem, often to one that is more tractable and useful. In many situations solving the exact problem is not really what a practitioner needs. If computing X exactly requires too much time, then it is useless to compute it. A perfect example is the weather: computing tomorrow’s weather in a week’s time is clearly not very useful.

The brilliance of the current approach is that we can change the problem. There are at least two major ways to do this:

{\bullet } Change the answer required. Allow approximation, or allow a partial answer. Do not insist on an exact answer.

{ \bullet } Change the algorithmic method. Allow algorithms that can be wrong, or allow algorithms that use randomness. Do not insist that the algorithm is a perfect deterministic one.

This is exactly what Chayes and her co-authors have done. So let’s take a look at what they do in their paper.


In their paper they study PageRank, which is the definition and algorithm made famous by Google. It gives a way to rank webpages in response to a query that supplements criteria from the query itself. An old query-specific criterion was the number of matches to a keyword in the query. Rather than rank solely by this count, PageRank emphasizes a general page score. The score is sometimes interpreted as a measure of “popularity” or “authority,” leading to the following circular-seeming definitions:

{\bullet} A webpage is popular if it has a healthy number of links from popular pages.

{\bullet} A webpage is authoritative if it is well cited, especially by other authoritative pages.

What the PageRank score actually denotes mathematically is the likelihood that a person randomly traversing links will arrive at any particular page. This includes a frequency {\alpha} with which the person will stop clicking, do something healthier like ride a bicycle, and start again on a “random” webpage.

The situation can be modeled by the classic random walk on a directed graph. We have a graph {G} on {N} nodes and an {N \times N} matrix {M} that is row-stochastic, meaning the entries in each row are non-negative and sum to {1}. Given that the web-walker is at node {i}, the entry {M[i,j]} is the probability of going next to node {j}. If node {i} has out-degree {b}, then

\displaystyle  M[i,j] = \frac{\alpha}{N} + \begin{cases} (1 - \alpha)\frac{1}{b} & \text{if~} i \text{~links to~} j\\ 0 & \text{otherwise.}\end{cases}

We can tweak this e.g. by modeling the user hitting the “Back” button on the browser, or jumping to another browser tab, or using a search engine. We could also set {\alpha} higher in case page {i} has few or no outgoing links. We still get an {M}, and since the use of {\alpha} effectively makes the graph strongly connected and averts certain pathologies, we get a beautiful conclusion from random-walk theory: There is a unique stationary distribution {P}, which is the unique left-eigenvector for the largest eigenvalue, which as normalized above is {1}:

\displaystyle  P M = P.

Then the PageRank of node {i} is {P(i)}. It is remarkable that this simple, salient idea from the good old days works so well. A further fact from the theory (and use of {\alpha}) is that if you start at any node, in the long run you will find yourself on page {i} with frequency {P(i)}. Here is Wikipedia’s graphical example:


The issue is: how to compute {P(i)}? In the good old days this was a trivial problem—just use linear algebra. But now the issue is that {N} is really big, let alone {N \times N} being unspeakably big. The {N} is too big even to get an approximation via the “further fact,” that is by simulating a random walk on the whole graph, and classical sparse-matrix methods might only help a little. This is where Chayes and company change the game: let us care about computing {P(i)} only for some {i}‘s, and even then, let us be content with fairly rough approximation.

The Shifted Problems

The approximation to PageRank is called SignificantPageRank. The paper gives a randomized algorithm that solves the following problem.

Let us be given a graph. Then, given a target threshold {\Delta} and an approximation factor {c > 1}, we are asked to output a set {S} of nodes such that with high probability, {S} contains all nodes of PageRank at least {\Delta}, and no node of PageRank smaller than {\frac{1}{c}\Delta}.

This is a perfect example of the shift. The algorithm is random, and the problem is to find not the nodes with a given PageRank, but those that are not too far away.

The nifty point is that the algorithm can tolerate fuzzing the matrix {M}, in a manner called SARA for “sparse and approximate row access”:

Given {i} and {\epsilon}, return a set {S} of {O(1/\epsilon)} columns {j} and values {p_j} such that for all {j}:

  • {j \in S \implies |p_j - M[i,j]| \leq \epsilon}, and

  • {j \notin S \implies M[i,j] \leq \epsilon}.

It is important to use this for different values of {\epsilon}. The cost of a query {(i,\epsilon) \rightarrow S} is {\Theta(|S|) = O(1/\epsilon)}.

If we picture “{N}” as “exponential” and take {\epsilon = 1/\mathsf{poly}(n)} where {n = \log N}, then this becomes an approximative version of {M} being succinct, which we just talked about. In this scaling of {\epsilon} we are effectively limiting to a {\mathsf{poly}(n)} local portion {S} of the graph around node {i}. Since we also have {\frac{\alpha}{N} \ll \epsilon}, under SARA entries outside {S} would become effectively zero, so that the chance of “teleporting” outside {S} on the whole would be regarded as negligible. In fact the paper also researches the case where each Web user always starts afresh at a “home node” {u} in that portion, making {M[i,u] = \alpha} just for that user. Then the {\alpha}-related probability is not negligible, and the resulting user-dependent estimate is called PersonalizedPageRank.

The problem they need to solve for SignificantPageRank then becomes “SignificantColumnSums”:

Given {M} and {\Delta,c} as above, find a set {S} of columns such that for all columns {j}:

  • {\sum_i M[i,j] \geq \Delta \implies j \in S};

  • {\sum_i M[i,j] \leq \frac{1}{c}\Delta \implies j \notin S}.

An even simpler problem which they use as a stepping-stone is “VectorSum”:

Given a length-{N} vector {P} with entries in {[0,1]}, and {1 \leq \Delta \leq N} and {c > 1}:

  • output yes if {{}\text{~}\sum_i P(i) \geq \Delta};

  • output no if {{}\text{~}\sum_i P(i) \leq \frac{\Delta}{c}}, don’t-care otherwise.

The goal is always to avoid looking at all {N} nodes or entries, but only an {N^{1 - \gamma}} or so portion of them, where {\gamma > 0}. Thus the problem shift is necessitated by {N} being huge. This isn’t my good-old-days idea of solving a problem, but can be called “{(\Delta,c)}-solving” it.

Multi-Level Sampling and Results

Ken and I are interested because these are similar to problems we have been encountering in our quest for more cases where quantum algorithms can be simulated in classical randomized polynomial time. Thus any new ideas are appreciated, and what catches our eye is a multi-level approximation scheme that exploits the requirement of SARA to work for different {\epsilon}. The situations are different, but we hope to adapt them.

The situation for VectorSum is that a probe {(i,\epsilon) \rightarrow P(i)} still costs order-of {1/\epsilon}, and returns {0} unless {P(i) \geq \epsilon}. A simple-minded use of a set {S} of random probes for the same {\epsilon} would yield the estimate

\displaystyle  \frac{N}{|S|} \sum_{i \in S: P(i) \geq \epsilon} P(i).

The resulting error has order {N\epsilon}, so we need {\epsilon \approx \frac{\Delta}{N}} which is rather demanding. Indeed the total cost would have order {\frac{|S|N}{\Delta}}, where {S} needs to be so large as to kill any hope of making the cost {N^{1 - \gamma}} or even {o(N)}. In the pivotal case where {\sum_i P(i) = \Delta}, we would need {|S| \approx \frac{N}{\Delta}}, incurring cost on the order of {(\frac{N}{\Delta})^2}.

However, they show that by using a different precision {\epsilon_t \approx \frac{t}{|S|}} for each random probe, they can get acceptable error with a reasonably small number of probes. The case {t = 1} where we have {\epsilon \approx \frac{1}{|S|} = \frac{\Delta}{N}} occurs only once, so its {\frac{N}{\Delta}} cost can be tolerated. Other probes have smaller cost, and while their precisions are looser, the aggregate precision on the estimate becomes good enough for the following result:

Theorem 1 Given {P,c,\Delta} as above and {\delta > 0}, VectorSum can be {(\Delta,c)}-solved with probability at least {1 - \delta} and cost

\displaystyle  O\left(\frac{N}{\Delta}\left(\frac{1}{c-1}\right)^2 \log\left(\frac{N}{\Delta(c-1)}\right)\log\left(\frac{2}{\delta}\right)\right).

Well in the good old days before LaTeX we wouldn’t even have been easily able to write such a formula with a typewriter, let alone prove it. But it is certainly better than {(\frac{N}{\Delta})^2}, and allows taking {\Delta = N^{\gamma}} to meet the goal of runtime {\tilde{O}(N^{1 - \gamma})}. As usual, for the details on SignificantColumnSums and the application problems, see the paper.

Open Problems

Do you miss the good old days? Or do you like the current approaches? What shifts, what new types of changing the goals, might we see in the future? For clearly today will one day be the “good old days.”

[changed qualifier on "certain pathologies", may as well footnote here that the "Back" button creates a Markov Chain with memory.]

by Pip at July 22, 2014 04:50 AM UTC

Authors: Sanguthevar Rajasekaran, Sudipta Pathak
Download: PDF
Abstract: The closest pair problem (CPP) is one of the well studied and fundamental problems in computing. Given a set of points in a metric space, the problem is to identify the pair of closest points. Another closely related problem is the fixed radius nearest neighbors problem (FRNNP). Given a set of points and a radius $R$, the problem is, for every input point $p$, to identify all the other input points that are within a distance of $R$ from $p$. A naive deterministic algorithm can solve these problems in quadratic time. CPP as well as FRNNP play a vital role in computational biology, computational finance, share market analysis, weather prediction, entomology, electro cardiograph, N-body simulations, molecular simulations, etc. As a result, any improvements made in solving CPP and FRNNP will have immediate implications for the solution of numerous problems in these domains. We live in an era of big data and processing these data take large amounts of time. Speeding up data processing algorithms is thus much more essential now than ever before. In this paper we present algorithms for CPP and FRNNP that improve (in theory and/or practice) the best-known algorithms reported in the literature for CPP and FRNNP. These algorithms also improve the best-known algorithms for related applications including time series motif mining and the two locus problem in Genome Wide Association Studies (GWAS).

at July 22, 2014 12:41 AM UTC

Authors: Troy Lee, Nikos Leonardos, Michael Saks, Fengming Wang
Download: PDF
Abstract: Information-theoretic methods have proven to be a very powerful tool in communication complexity, in particular giving an elegant proof of the linear lower bound for the two-party disjointness function, and tight lower bounds on disjointness in the multi-party number-in-the-hand (NIH) model. In this paper, we study the applicability of information theoretic methods to the multi-party number-on-the-forehead model (NOF), where determining the complexity of disjointness remains an important open problem.

There are two basic parts to the NIH disjointness lower bound: a direct sum theorem and a lower bound on the one-bit AND function using a beautiful connection between Hellinger distance and protocols revealed by Bar-Yossef, Jayram, Kumar and Sivakumar [BYJKS04]. Inspired by this connection, we introduce the notion of Hellinger volume. We show that it lower bounds the information cost of multi-party NOF protocols and provide a small toolbox that allows one to manipulate several Hellinger volume terms and lower bound a Hellinger volume when the distributions involved satisfy certain conditions. In doing so, we prove a new upper bound on the difference between the arithmetic mean and the geometric mean in terms of relative entropy. We then apply these new tools to obtain a lower bound on the informational complexity of the AND_k function in the NOF setting. Finally, we discuss the difficulties of proving a direct sum theorem for information cost in the NOF model.

at July 22, 2014 12:40 AM UTC

Authors: Aaron Bohy, Véronique Bruyère, Jean-François Raskin
Download: PDF
Abstract: When treating Markov decision processes (MDPs) with large state spaces, using explicit representations quickly becomes unfeasible. Lately, Wimmer et al. have proposed a so-called symblicit algorithm for the synthesis of optimal strategies in MDPs, in the quantitative setting of expected mean-payoff. This algorithm, based on the strategy iteration algorithm of Howard and Veinott, efficiently combines symbolic and explicit data structures, and uses binary decision diagrams as symbolic representation. The aim of this paper is to show that the new data structure of pseudo-antichains (an extension of antichains) provides another interesting alternative, especially for the class of monotonic MDPs. We design efficient pseudo-antichain based symblicit algorithms (with open source implementations) for two quantitative settings: the expected mean-payoff and the stochastic shortest path. For two practical applications coming from automated planning and LTL synthesis, we report promising experimental results w.r.t. both the run time and the memory consumption.

at July 22, 2014 12:41 AM UTC

Authors: Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos
Download: PDF
Abstract: The algorithm for Lov\'{a}sz Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects that satisfy a system of constraints. We present an alternative and simpler analysis of the algorithm that does not involve counting witness-trees.

at July 22, 2014 12:41 AM UTC

Authors: Edouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora
Download: PDF
Abstract: The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of Grundy Coloring, the problem of determining whether a given graph has Grundy number at least $k$. We show that Grundy Coloring can be solved in time $O^*(2^n)$ on graphs of order $n$. While the problem is known to be solvable in time $f(k,w)n$ for graphs of treewidth $w$, we prove that under the Exponential Time Hypothesis, it cannot be computed in time $O^*(c^w)$, for every constant $c$. We also consider two previously studied variants of Grundy Coloring, namely Weak Grundy Coloring and Connected Grundy Coloring. We show that Weak Grundy Coloring is fixed-parameter tractable with respect to the weak Grundy number. In stark contrast, it turns out that checking whether a given graph has connected Grundy number at least $k$ is NP-complete already for $k=7$.

at July 22, 2014 12:41 AM UTC

Authors: Anupam Gupta, Marco Molinaro
Download: PDF
Abstract: We consider the problem of solving packing/covering LPs online, when the columns of the constraint matrix are presented in random order. This problem has received much attention: the main open question is to figure out how large the right-hand sides of the LPs have to be (compared to the entries on the left-hand side of the constraint) to get $(1+\epsilon)$-approximations online? It is known that the RHS has to be $\Omega(\epsilon^{-2} \log m)$ times the left-hand sides, where $m$ is the number of constraints.

In this paper we give a primal-dual algorithm to achieve this bound for all packing LPs, and also for a class of mixed packing/covering LPs. Our algorithms construct dual solutions using a regret-minimizing online learning algorithm in a black-box fashion, and use them to construct primal solutions. The adversarial guarantee that holds for the constructed duals help us to take care of most of the correlations that arise in the algorithm; the remaining correlations are handled via martingale concentration and maximal inequalities. These ideas lead to conceptually simple and modular algorithms, which we hope will be useful in other contexts.

at July 22, 2014 12:41 AM UTC

Authors: Gábor Braun, Cristóbal Guzmán, Sebastian Pokutta
Download: PDF
Abstract: We present an information-theoretic approach to lower bound the oracle complexity of nonsmooth black box convex optimization, unifying previous lower bounding techniques by identifying a combinatorial problem, namely string guessing, as a single source of hardness. As a measure of complexity we use distributional oracle complexity, which subsumes randomized oracle complexity as well as worst-case oracle complexity. We obtain strong lower bounds on distributional oracle complexity for the box $[-1,1]^n$, as well as for the $L^p$-ball for $p \geq 1$ (for both low-scale and large-scale regimes), matching worst-case lower bounds, and hence we close the gap between distributional complexity, and in particular, randomized complexity, and worst-case complexity. Furthermore, the bounds remain essentially the same for high-probability and bounded-error oracle complexity, and even for combination of the two, i.e., bounded-error high-probability oracle complexity. This considerably extends the applicability of known bounds.

at July 22, 2014 12:40 AM UTC

Authors: William Gasarch
Download: PDF
Abstract: Let COLk be the set of all k-colorable graphs. It is easy to show that if a<b then COLa \le COLb (poly time reduction). Using the Cook-Levin theorem it is easy to show that if 3 \le a< b then COLb \le COLa. However this proof is insane in that it translates a graph to a formula and then the formula to a graph. We give a simple proof that COLk \le COL3.

at July 22, 2014 12:40 AM UTC

Authors: Harsh Ranjan, Sumit Agarwal
Download: PDF
Abstract: This paper introduces a new comparison base stable sorting algorithm, named RS sort. RS Sort involves only the comparison of pair of elements in an array which ultimately sorts the array and does not involve the comparison of each element with every other element. RS sort tries to build upon the relationship established between the elements in each pass. Suppose there is an array containing three elements a1, a2, a3 and if a relationship exist such that a1<a2 and a2<a3 then it can be established that a1<a3 and so there is no need to compare a1 and a3. Sorting is a fundamental operation in computer science. RS sort is analyzed both theoretically and empirically. We have performed its Empirical analysis and compared its performance with the well-known quick sort for various input types.

at July 22, 2014 12:41 AM UTC

Authors: Michael Horton, Joachim Gudmundsson, Sanjay Chawla, Joël Estephan
Download: PDF
Abstract: A knowledgeable observer of a game of football (soccer) can make a subjective evaluation of the quality of passes made between players during the game. We investigate the problem of producing an automated system to make the same evaluation of passes. We present a model that constructs numerical predictor variables from spatiotemporal match data using feature functions based on methods from computational geometry, and then learns a classification function from labelled examples of the predictor variables. Furthermore, the learned classifiers are analysed to determine if there is a relationship between the complexity of the algorithm that computed the predictor variable and the importance of the variable to the classifier. Experimental results show that we are able to produce a classifier with 85.8% accuracy on classifying passes as Good, OK or Bad, and that the predictor variables computed using complex methods from computational geometry are of moderate importance to the learned classifiers. Finally, we show that the inter-rater agreement on pass classification between the machine classifier and a human observer is of similar magnitude to the agreement between two observers.

at July 22, 2014 12:41 AM UTC

The diagram below describes a finite state machine that takes as input a description of an indifference graph, and produces as output a 1-planar drawing of it (that is, a drawing with each edge crossed at most once).

Indifference graphs are the graphs that can be constructed by the following process. Initialize an active set of vertices to be the empty set, and then perform a sequence of steps of two types: either add a new vertex to the active set and make it adjacent to all previous active vertices, or inactivate a vertex (removing it from the active set but not from the graph). Thus, they can be represented by a sequence of binary values that specify whether the next step is to add or inactivate a vertex. These values are the input to the finite state machine.

In a paper at WADS last year with Bannister and Cabello, we showed how to test 1-planarity for several special classes of graphs, but not for indifference graphs. Some of our algorithms involved proving the existence of a finite set of forbidden configurations, and that idea works here, too: an indifference graph turns out to be 1-planar if and only if, for every K6 subgraph, the first three vertices of the subgraph (in the activation order) have no later neighbors outside the subgraph, and the last three vertices have no other earlier neighbors. K6 is 1-planar, but it has essentially only one drawing (modulo permutation of the vertices), and any example of this configuration would have a seventh vertex connected to four of the K6 vertices, something that's not possible in a 1-planar drawing.

At one level, the state diagram above can be viewed as a diagram for detecting this forbidden configuration. Every right-going transition is one that adds an active vertex, and every left-going transition is one that removes an active vertex. If a transition of either type does not exist in the diagram, it means that a step of that type will lead to an inescapable failure state. But the only missing transitions are the ones that would create a six-vertex active set by a sequence of transitions that does not end in three consecutive right arrows (creating a K6 in which one of the last three vertices has an earlier neighbor) or the ones that would exit a six-vertex active set by a sequence of transitions that does not begin with three consecutive left arrows (creating a K6 in which one of the first three vertices has a later neighbor). So, this automaton recognizes only the graphs that have no forbidden configuration.

On another level, the drawings within each state of the diagram show how to use this finite state machine to construct a drawing. Each state is labeled with a drawing of its active vertices, possibly with a yellow region that represents earlier inactive parts of the drawing that can no longer be modified. The numbers on the vertices give the order in which they were activated. For each left transition, it is always possible to remove the oldest active vertex from the drawing and replace the parts of the drawing surrounding it by a yellow region to create a drawing that matches the new state. Similarly, for each right transition, it is always possible to add one more active vertex to the drawing, connect it to the other active vertices, and then simplify some parts of the drawing to yellow regions, again creating a drawing that matches the new state. Therefore, every graph that can be recognized by this state diagram has a 1-planar drawing.

Since the machine described by the diagram finds a drawing for a given indifference graph if and only if the graph has no forbidden configurations, it follows that these forbidden configurations are the only ones we need to describe the 1-planar graphs and that this machine correctly finds a 1-planar drawing for every indifference graph that has one. This same technique doesn't always generalize: A result from my WADS paper that it's NP-complete to test 1-planarity for graphs of bounded bandwidth shows that, even when a class of graphs can be represented by strings of symbols from a finite alphabet it's not always going to be possible to find a finite state machine to test 1-planarity. But it would be interesting to find more graph classes for which the same simple technique works.

at July 21, 2014 11:54 PM UTC

Authors: Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart
Download: PDF
Abstract: We consider ancestry labeling schemes: Given a rooted tree T, assign a binary string (label) to each node, such that given the labels of any two nodes, one can determine whether the first is an ancestor of the second in T.

Recently, Fraigniaud and Korman [STOC'10] showed that such labels can be assigned using log n + O(loglog n) bits per label, solving a long standing open question and matching a lower bound of log n + Omega(loglog n) due to Alstrup et al. [SODA'03]. In this paper we present an alternative ancestry labeling scheme using log n + 2loglog n + O(1) bits. Similar to the previously known schemes, our scheme relies on intervals and can encode any tree in O(n) time. Rather than using complicated decompositions, our scheme uses approximate interval sizes, which gives a clean algorithm that is simple enough to be taught and implemented.

at July 21, 2014 12:40 AM UTC

Authors: Attila Bernáth, Zoltán Király
Download: PDF
Abstract: In this paper we fix 7 types of undirected graphs: paths, paths with prescribed endvertices, circuits, forests, spanning trees, (not necessarily spanning) trees and cuts. Given an undirected graph $G=(V,E)$ and two "object types" $\mathrm{A}$ and $\mathrm{B}$ chosen from the alternatives above, we consider the following questions. \textbf{Packing problem:} can we find an object of type $\mathrm{A}$ and one of type $\mathrm{B}$ in the edge set $E$ of $G$, so that they are edge-disjoint? \textbf{Partitioning problem:} can we partition $E$ into an object of type $\mathrm{A}$ and one of type $\mathrm{B}$? \textbf{Covering problem:} can we cover $E$ with an object of type $\mathrm{A}$, and an object of type $\mathrm{B}$? This framework includes 44 natural graph theoretic questions. Some of these problems were well-known before, for example covering the edge-set of a graph with two spanning trees, or finding an $s$-$t$ path $P$ and an $s'$-$t'$ path $P'$ that are edge-disjoint. However, many others were not, for example can we find an $s$-$t$ path $P\subseteq E $ and a spanning tree $T\subseteq E$ that are edge-disjoint? Most of these previously unknown problems turned out to be NP-complete, many of them even in planar graphs. This paper determines the status of these 44 problems. For the NP-complete problems we also investigate the planar version, for the polynomial problems we consider the matroidal generalization (wherever this makes sense).

at July 21, 2014 12:40 AM UTC

Authors: Michele Borassi, Pierluigi Crescenzi, Michel Habib
Download: PDF
Abstract: This paper will analyze several quadratic-time solvable problems, and will classify them into two classes: problems that are solvable in truly subquadratic time (that is, in time $O(n^{2-\epsilon})$ for some $\epsilon>0$) and problems that are not, unless the well known Strong Exponential Time Hypothesis (SETH) is false. In particular, we will prove that some quadratic-time solvable problems are indeed easier than expected. We will provide an algorithm that computes the transitive closure of a directed graph in time $O(mn^{\frac{\omega+1}{4}})$, where $m$ denotes the number of edges in the transitive closure and $\omega$ is the exponent for matrix multiplication. As a side effect, we will prove that our algorithm runs in time $O(n^{\frac{5}{3}})$ if the transitive closure is sparse. The same time bounds hold if we want to check whether a graph is transitive, by replacing m with the number of edges in the graph itself. As far as we know, this is the fastest algorithm for sparse transitive digraph recognition. Finally, we will apply our algorithm to the comparability graph recognition problem (dating back to 1941), obtaining the first truly subquadratic algorithm. The second part of the paper deals with hardness results. Starting from an artificial quadratic-time solvable variation of the k-SAT problem, we will construct a graph of Karp reductions, proving that a truly subquadratic-time algorithm for any of the problems in the graph falsifies SETH. The analyzed problems are the following: computing the subset graph, finding dominating sets, computing the betweenness centrality of a vertex, computing the minimum closeness centrality, and computing the hyperbolicity of a pair of vertices. We will also be able to include in our framework three proofs already appeared in the literature, concerning the graph diameter computation, local alignment of strings and orthogonality of vectors.

at July 21, 2014 12:40 AM UTC

Virginia Vassilevska Williams stunned the world of computer science by presenting the first improvement to the matrix multiplication constant \omega in twenty years (later it was found that a more modest progress had been obtained independently and slightly earlier by Andrew James Stothers). The current world record is held by François Le Gall, who showed that \omega < 2.3728639 by perfecting the methods of Vassilevska Williams. For an exposition of this line of work, check out my recent lecture notes. For the full details, I recommend Le Gall’s paper and the journal version of Stothers’ thesis (with his advisor A. M. Davie). The recent progress heavily builds on classic work by Coppersmith and Winograd. Briefly, they came up with a basic identity known as the Coppersmith–Winograd identity. Applying Strassen’s laser method with their own ingenious construction (relying on Salem–Spencer sets), they obtained the bound \omega < 2.388. Applying their method to the tensor square of the basic identity, they obtained the improved bound \omega < 2.376. That’s where things had been standing since 1990, until Stothers managed to perform the computations for the fourth tensor power, obtaining the bound \omega < 2.373 in 2010. A year later (but independently), Vassilevska Williams analyzed the eighth tensor power and obtained the bound \omega < 2.3729. Further progress was obtained by Le Gall, who analyzed the sixteenth and thirty-second tensor powers, obtaining the current world record stated above. Although taking ever higher tensor powers improves the bound on \omega, the improvements are diminishing, and it seems safe to conjecture that taking the Nth tensor power does not yield the conjectured \omega = 2 as N \to \infty. However, how can we be certain? Perhaps the improvements slow down, but like a slowly divergent series, eventually go all the way down to 2? In the rest of the blog post, we describe a recent result of Andris Ambainis and myself, which shows that the best bound that this method can produce is \omega < 2.3078, for any value of N. In fact, our result allows for a wider class of methods which utilize the Coppersmith–Winograd identity, and hint to a new technique which can potentially lead to better algorithms. Very recently, Le Gall was able to use our methods to show that the best bound that can be obtained by taking an Nth tensor power of the Coppersmith–Winograd identity is \omega < 2.3725, and so the current analysis of the identity is quite tight. The rest of this post assumes that the reader is versed in the basics of the theory of matrix multiplication algorithms. Specifically, we expect you to know the statement of Schönhage’s asymptotic sum inequality, which is described in my earlier blog post. The laser method Schönhage’s asymptotic sum inequality allows us to obtain an upper bound on \omega given an upper bound on the border rank of a disjoint sum of matrix multiplication tensors \langle n_i,m_i,p_i \rangle. Strassen’s laser method is a framework for achieving the same for non-disjoint sums of matrix multiplication tensors. It is best illustrated with the following example from the paper of Coppersmith and Winograd:

\displaystyle \epsilon^3 \sum_{i=1}^q (x_0^{[0]} y_i^{[1]} z_i^{[1]} + x_i^{[1]} y_0^{[0]} z_i^{[1]} + x_i^{[1]} y_1^{[1]} z_0^{[0]}) + O(\epsilon^4) =

\displaystyle \epsilon \sum_{i=1}^q (x_0^{[0]} + \epsilon x_i^{[1]}) (y_0^{[0]} + \epsilon y_i^{[1]}) (z_0^{[0]} + \epsilon z_i^{[1]}) -

\displaystyle \left(x_0^{[0]} + \epsilon^2 \sum_{i=1}^q x_i^{[1]}\right) \left(y_0^{[0]} + \epsilon^2 \sum_{i=1}^q y_i^{[1]}\right) \left(z_0^{[0]} + \epsilon^2 \sum_{i=1}^q z_i^{[1]}\right) +

(1-q\epsilon) x_0^{[0]} y_0^{[0]} z_0^{[0]}.

Here q is some integer parameter. The superscripts on the variables partition them into groups. For example, the two groups of x-variables are x_0^{[0]} and x_1^{[1]}, \ldots, x_q^{[1]}. We can write this identity succinctly as

\underline{R}(\langle 1,1,q \rangle^{0,1,1} + \langle q,1,1 \rangle^{1,0,1} + \langle 1,q,1 \rangle^{1,1,0}) \leq q+2.

The superscripts have the same meaning, for example the first constituent tensor \langle 1,1,q \rangle^{0,1,1} involves the x-variables from group 0, the y-variables from group 1, and the z-variables from group 1. Each constituent tensor uses all variables from each group, and this convention gives a unique interpretation of the short form of the identity.

Denote the tensor whose border rank is estimated by T. This tensor is a sum of three matrix multiplication tensors, but we cannot apply the asymptotic sum inequality since these constituent tensors are not disjoint: for example, the first two constituent tensors share the z-variables. Strassen’s idea was to take a high tensor power of the original identity, and zero variables so that the remaining constituent tensors are disjoint (Strassen actually considered a different operation, degeneration, instead of zeroing, but Coppersmith and Winograd preferred to use the simpler operation of zeroing). The Nth tensor power of T has 3^N constituent tensors, and border rank at most (q+2)^N. For example, when N=2, we obtain

T^{\otimes 2} = \langle 1,1,q^2 \rangle^{00,11,11} + \langle q,1,q \rangle^{01,10,11} + \langle 1,q,q \rangle^{01,11,10}

+ \langle q,1,q \rangle^{10,01,11} + \langle q^2,1,1 \rangle^{11,00,11} + \langle q,q,1 \rangle^{11,01,10}

+ \langle 1,q,q \rangle^{10,11,01} + \langle q,q,1 \rangle^{11,10,01} + \langle 1,q^2,1 \rangle^{11,11,00}.

The partition of the x-variables of T into two groups naturally corresponds to a partition of the x-variables of T^{\otimes 2} into four groups, indexed by 0/1 vectors of length 2. These indices are used above to form the index triples appearing as superscripts. In fact, the dimensions of any of the constituent matrix multiplication tensors can be recovered from its index triple, so we can “summarize” T^{\otimes 2} by giving a list of all nine index triples:

(00,11,11) \; (01,10,11) \; (01,11,10) \; (10,01,11) \; (11,00,11) \; (11,01,10) \; (10,11,01) \; (11,10,01) \; (11,11,00).

When taking the Nth tensor power, there will be 3^N index triples, each consisting of three vectors of length N. Our task is to zero out some groups of variables so that the surviving index triples correspond to disjoint matrix multiplication tensors, and as many of these as possible. Put differently, if we denote by L_N the list of index triples and by X,Y,Z the remaining variables, then we want L_N \cap X \times Y \times Z to consist of index triples in which no x-index repeats, no y-index repeats, and no z-index repeats. If we manage to accomplish this, generating C_N surviving index triples, then the asymptotic sum inequality gives the bound

C_N (q^N)^{\omega/3} \leq (q+2)^N.

(Since each of the constituent tensors \langle n,m,p \rangle in T satisfies nmp = q, each constituent tensor \langle n',m',p' \rangle in T^{\otimes N} satisfies n'm'p' = q^N.)

Let \kappa_N be the maximum of C_N over all legal choices of X,Y,Z. It turns out that \kappa = \lim_{N\to\infty} \kappa_N^{1/N} = 3/2^{2/3}, and so the asymptotic sum inequality shows that (3/2^{2/3}) q^{\omega/3} \leq q+2. When q = 8, this gives the bound \omega < 2.404. We call the limit \kappa the capacity.

Upper bounds on the capacity

Coppersmith and Winograd used an ingenious construction to show that \kappa \geq 3/2^{2/3}, but they neglected to mention a matching upper bound showing that their construction is optimal. This upper bound, whose philosophy is essential to our approach, appears curiously enough in the paper by H. Cohn, R. Kleinberg, B. Szegedy and C. Umans on group-theoritic algorithms for matrix multiplication. Their basic idea is to use the fact that after zeroing out variables, no x-index repeats, and so \kappa_N is at most the number of x-indices. Since there are at most 2^N x-indices, this gives \kappa_N \leq 2^N and so \kappa \leq 2, a bound not as good as the one we had hoped for (3/2^{2/3} \approx 1.88988).

To improve on this trivial bound, we divide the surviving index triples into types. An index triple (I,J,K) has type (t_a,t_b,t_c) if it results from t_a copies of (0,1,1), t_b copies of (1,0,1) and t_c copies of (1,1,0). Within each given type, the number of distinct x-indices depends on the type. For example, when t_a=t_b=t_c=N/3, the number of distinct x-indices is \binom{N}{N/3}. It is not hard to check that for each choice of t_a,t_b,t_c, either the number of distinct x-indices is at most \binom{N}{N/3}, or the same is true for either the number of distinct y-indices or the number of distinct z-indices. Since there are \binom{N+2}{2} different types, we obtain the bound

\kappa_N \leq \binom{N+2}{2} \binom{N}{N/3}.

Stirling’s approximation then shows that \kappa \leq 3/2^{2/3}; note that the number of types \binom{N+2}{2} disappears when computing the limit \kappa_N^{1/N} since \binom{N+2}{2} is polynomial rather than exponential in N.

The Coppersmith–Winograd identity

The Coppersmith–Winograd identity improves on the previous identity by computing three more products at no cost in the border rank:

\underline{R}(\langle 1,1,q \rangle^{0,1,1} + \langle q,1,1 \rangle^{1,0,1} + \langle 1,q,1 \rangle^{1,1,0} + \langle 1,1,1 \rangle^{0,0,2} + \langle 1,1,1 \rangle^{0,2,0} + \langle 1,1,1 \rangle^{2,0,0}) \leq q+2.

This identity is the fount and source of all improvements on \omega since 1989. The two groups of x-variables x_0^{[0]};x_1^{[1]},\ldots,x_q^{[1]} appearing in the previous identity are joined by a new group x_{q+1}^{[2]} consisting of a single variable. The curious reader can try to spell out the actual identity on her own, or she can look it up in my lecture notes. We denote the corresponding tensor by T_{CW}.

The laser method can be applied to this identity in much the same way as before. After taking the Nth tensor power, we are left with 6^N different constituent tensors \langle n_i,m_i,p_i \rangle, each represented by an index triple (I_i,J_i,K_i). If the index triple contains M factors of one of the forms (0,1,1);(1,0,1);(1,1,0) then n_im_ip_i = q^M. Our task is to zero out some variables so that the remaining constituent tensors \langle n_{i'} m_{i'} p_{i'} \rangle are disjoint, and the quantity C_N = \sum_{i'} (n_{i'} m_{i'} p_{i'})^{\omega/3} is maximized. Since we don’t know \omega, we maximize instead \sum_{i'} (n_{i'} m_{i'} p_{i'})^{\rho/3} for some parameter \rho. If \kappa_{\rho,N} is the maximum of this quantity for given \rho, then the asymptotic sum inequality shows that \kappa_{\omega,N} \leq (q+2)^N.

It turns out that for each \rho, the limit \kappa_\rho = \lim_{N\to\infty} \kappa_{\rho,N}^{1/N} exists, and the asymptotic sum inequality shows that \kappa_\omega \leq N+2. This reduces the analysis of T_{CW} to the determination of its associated capacity \kappa_\rho. Coppersmith and Winograd show that

\displaystyle \kappa_\rho \geq 2^{H(\tfrac{2-\alpha}{3},\tfrac{2\alpha}{3},\tfrac{1-\alpha}{3})} q^{\alpha\rho/3}, \text{ where } \alpha = \frac{-3+\sqrt{32q^{-\rho}+1}}{8q^{-\rho}-2},

where H is the base 2 entropy function. Amazingly, the method of Cohn, Kleinberg, Szegedy and Umans shows that this lower bound is tight! When q = 6 and \rho = 2.388, one checks that \kappa_\rho > q+2, and since \kappa_\omega \leq q+2 and \kappa_\omega is increasing in \omega, this shows that \omega < 2.388.

Powers of the Coppersmith–Winograd identity

Coppersmith and Winograd managed to get an even better bound on \omega by considering the tensor square T_{CW}^{\otimes 2} whose border rank is at most (q+2)^2. If we retain the old partition into groups (so there are now nine groups of each of the x-variables, y-variables and z-variables), then a quick consideration of the laser method reveals that we should obtain the exact same bound on \omega. Instead, Coppersmith and Winograd merge the original nine groups into five groups by putting the original group i_1i_2 into the new group i_1+i_2. This corresponds to the following partition of the original groups:

0 = \{00\} ;\; 1=\{01,10\} ;\; 2=\{02,11,20\} ;\; 3=\{12,21\} ;\; 4=\{22\}.

The original 36 constituent tensors are now grouped to 15 constituent tensors:

  1. 3 terms of the form \langle 1,1,1 \rangle^{0,0,4}.
  2. 6 terms of the form \langle 1,1,2q \rangle^{0,1,3} resulting from the merger of \langle 1,1,q \rangle^{00,10,12} and \langle 1,1,q \rangle^{00,01,21} into a single matrix multiplication tensor.
  3. 3 terms of the form \langle 1,1,q^2+2 \rangle^{0,2,2} resulting from the merger of three original constituent tensors: \langle 1,1,q^2 \rangle^{00,11,11}, \langle 1,1,1 \rangle^{00,20,02} and \langle 1,1,1 \rangle^{00,02,20}.
  4. 3 terms whose index triple is of the form (1,2,2) that are not matrix multiplication tensors, one of which results from merging \langle 1,q,1 \rangle^{10,10,02}, \langle 1,q,1 \rangle^{01,01,20}, \langle q,1,q \rangle^{10,01,11} and \langle q,1,q \rangle^{01,10,11}.

The idea is now to apply the same method, but we encounter a problem: there are three tensors which are not matrix multiplication tensors. However, each of these tensors is itself a sum of matrix multiplication tensors, and so can be analyzed using the same method. In this recursive fashion, Coppersmith and Winograd were able to analyze this second power, and obtained the bound \omega < 2.376. What Stothers and Vassilevska Williams did was to codify this recursive application of the laser method, and using this codification they were able to handle larger powers, using a computer for the calculations. Their method has one shortcoming: when analyzing higher powers, the capacity problems encountered are too hard to solve exactly. Instead, they employ costly numerical methods that produce a good lower bound on the relevant capacities. Le Gall came up with a more efficient method which produces slightly inferior bounds but is applicable to higher tensor powers. A different viewpoint: the laser method with merging Our main innovation is a different way of looking at the analysis of powers of T_{CW}. The recipe of the laser method consists of taking a high tensor power, zeroing groups of variables so that the remaining constituent tensors are disjoint, and applying the asymptotic sum inequality. We add an additional step: after zeroing groups of variables, we allow merging sets of constituent tensors, as long as each merged set forms a matrix multiplication tensor, and the resulting merged constituent tensors are all disjoint (before the merging step, the surviving constituent tensors don’t need to be disjoint). After the merging step, we apply the asymptotic sum inequality as before. We call this scheme the laser method with merging. We already saw some examples of the merging step in the analysis of T_{CW}^{\otimes 2}: for example, the two constituent tensors \langle 1,1,q \rangle^{00,10,12} and \langle 1,1,q \rangle^{00,01,21} are merged into the matrix multiplication tensor \langle 1,1,2q \rangle^{\{(00,10,12),(00,01,21)\}}. Coppersmith and Winograd’s analysis of T_{CW}^{\otimes 2} is an example of the laser method with merging applied to the original tensor T_{CW}. To see this, let us examine their analysis. They first merge some tensors in T_{CW}^{\otimes 2}, and are left with a sum of matrix multiplication tensors and three “complicated” tensors, which we denote by T_4,T_5,T_6, each of which is by itself a sum of matrix multiplication tensors. They proceed to take an Nth tensor power of T_{CW}^{\otimes 2}, and zero some groups of variables (each group corresponds to several original groups) so that the resulting constituent tensors are disjoint. Each surviving constituent tensor contains a factor of the form (T_4 \otimes T_5 \otimes T_6)^{\otimes M} (the powers of T_4,T_5,T_6 are always the same in their construction), and by zeroing out groups of variables internal to this factor, they reduce it to a disjoint sum of matrix multiplication tensors. After this second step of zeroing, we are left with a disjoint sum of matrix multiplication tensors, to which the asymptotic sum inequality is finally applied. Instead of first merging the constituent tensors of T_{CW}^{\otimes 2}, taking an Nth tensor power, and then zeroing variables in two steps, we can reverse the order of steps. Starting with T_{CW}^{2N}, we first zero out variables, and then do the appropriate merging. We end up with the exact same disjoint sum of matrix multiplication tensors as before. This hopefully convinces the reader that the analysis of Coppersmith and Winograd can be put in our framework. The analysis of higher power by Stothers, Vassilevska Williams and Le Gall adds more levels of recursion but is otherwise the same, so these also fall into our framework. If we could prove an upper bound on the corresponding notion of capacity, we would obtain a limit on the upper bound on \omega provable using this framework. Limits on the laser method with merging Let \kappa_{\rho,N} be the maximum of \sum_i (n_im_ip_i)^{\rho/3} over all direct sums \bigoplus_i \langle n_i,m_i,p_i \rangle which can be obtained from T_{CW}^N by zeroing out groups of variables and merging the surviving constituent tensors in sets. The asymptotic sum inequality shows that \kappa_{\omega,N} \leq (q+2)^N. It turns out that the limit \kappa_\rho = \lim_{N\to\infty} \kappa_{\rho,N}^{1/N} exists (essentially due to the easy fact \kappa_{\rho,N_1 N_2} \geq \kappa_{\rho,N_1} \kappa_{\rho,N_2}), and so the bound obtained by the method is \kappa_\omega \leq q+2. Our goal in this section is to obtain an upper bound on the capacity \kappa_\rho, which correspond to a lower bound on the solution of the equation \kappa_\rho = q+2. The first step is to understand which mergers are possible — which sets of constituent tensors of T_{CW}^{\otimes N} can be merged to form a matrix multiplication tensor. Let’s take a look at the mergers taking place in Coppersmith and Winograd’s analysis of T_{CW}^{\otimes 2}:

(00,10,12) \; (00,01,21)

(00,11,11) \; (00,02,20) \; (00,20,02)

In both cases, the x-indices of the merged index triples consist entirely of zeroes.This is not the most general possible form of merging. Indeed, consider the following example for N=4:

(0012,1000,1210) \; (0021,1000,1201) \; (0012,0100,2110) \; (0021,0100,2101)

This results from the tensor product of (00,10,12) \; (00,01,21) and its rotation (12,00,10) \; (21,00,01). In this example, the first two positions are always zero in the x-indices, and the last two positions are always zero in the y-indices.

Generalizing, we say that a set of constituent tensors of T_{CW}^{\otimes N} is merged on zeroes if for each of the N positions, either all the x-indices are zero at the position, or all the y-indices are zero at the position, or all the z-indices are zero at the position. Using this nomenclature, we see that Coppersmith and Winograd’s analysis of T_{CW}^{\otimes 2} always results in sets of constituent tensors merged on zeroes. Looking closely at the works of Stothers, Vassilevska Williams and Le Gall, we see that the same is true for their analyses. Indeed, we managed to prove that this is always the case.

Lemma. If q > 1 then any set of constituent tensors of T_{CW}^{\otimes N} which merge to a matrix multiplication tensor is merged on zeroes.

The interested reader can look at the proof in our paper (Lemma 4.1 on page 11).

Given the lemma, our upper bound on the capacity broadly follows the ideas in the upper bound of Cohn, Kleinberg, Szegedy and Umans. Given N, consider a collection of disjoint tensors resulting from starting with T_{CW}^{\otimes N}, zeroing out some groups of variables, and merging some of the surviving tensors. We call each merged set of tensors a line. Each line is associated with a line type (t_x,t_y,t_z), where t_x is the number of positions at which the x-indices are always zero. Each constituent tensor inside each line has a tensor type which corresponds to how many of the original six constituent tensors were used to form it. Since the number of types is polynomial, we can focus our attention on an arbitrary line type and tensor type.

Consider for simplicity the case where the line type is (N/3,N/3,N/3) and the tensor type is of the form (\alpha,\alpha,\alpha,\beta,\beta,\beta) (i.e., it gives the same weight to constituent tensors of similar shape). We can calculate the number P of distinct x-indices and the number Q of distinct x-indices which can appear in any given line; Q<P since some of the coordinates are fixed at zero. Each constituent tensor in each line has the same dimensions \langle M,M,M \rangle, where the value of M depends on the parameters \alpha,\beta. Convexity considerations show that it is advantageous for all lines to contain the same number R \leq Q of distinct x,y,z-indices. The total number of x-variables, y-variables and z-variables in each line is RM^2 of each (since each x-index corresponds to M^2 x-variables), and so the line is isomorphic to \langle \sqrt{R}M,\sqrt{R}M,\sqrt{R}M \rangle. The total number of lines is at most P/R (since different lines have disjoint x-indices), and so the total contribution to \kappa_{\rho,N} is (P/R) (\sqrt{R}M)^\rho = P R^{\rho/2-1} M^\rho \leq PQ^{\rho/2-1} M^\rho.

We can similarly bound the contributions of other line types and tensor types, and through this we obtain an upper bound on \kappa_{\rho,N} and so on \kappa_\rho.

Theorem. For q=5 and T_{CW}, the solution to \kappa_\rho = q+2 satisfies \rho > 2.3078.

We obtain similar results for other values of q. Curiously, the results deteriorate as q gets smaller.

Le Gall used our technique to analyze the merged version of the tensor T_{CW}^{\otimes 2}. For this tensor, he obtained a significantly improved bound.

Theorem (Le Gall). For q=5 and the merged version of T_{CW}^{\otimes 2}, the solution to \kappa_\rho = (q+2)^2 satisfies \rho > 2.3725.

His result encompasses the analyses of T_{CW}^{\otimes N} à la Stothers, Vassilevska Williams and himself for all values of N; no value of N can prove the bound \omega < 2.3725.

What next?

We have seen that the Coppersmith–Winograd identity cannot be used to prove \omega = 2, at least not using current techniques. Anybody who wishes to prove \omega = 2 should therefore either look for a different identity, or develop a new technique. The second avenue has been tried by Cohn and Umans, who suggested a technique based on groups. Cohn, Kleinberg, Szegedy and Umans showed how to match the bound \omega < 2.376 obtained by Coppersmith and Winograd using the group-theoretic approach; their construction heavily relies on the methods of Coppersmith and Winograd, and in particular they need to use Coppersmith and Winograd’s lower bound on the capacity, which is the difficult part of both proofs. It is fair to say that so far, the group-theoretic techniques have not yielded any better upper bounds on \omega. It thus seems that the most promising avenue for major improvement is finding better identities replacing the Coppersmith–Winograd identity, which has served us for 25 years. Perhaps computers can be enlisted for the search?

Until we find a new identity or a new technique, here is another suggestion for obtaining an improved upper bound on \omega, albeit not \omega = 2. Let \omega_W be the best bound that can be obtained by analysing T_{CW}^{\otimes W} according to the previous techniques, and let \omega_\infty = \lim_{W\to\infty} \omega_W. The bound \omega_W is obtained as the solution to \lim_{N\to\infty} \kappa_{\omega_W,W,N}^{1/N} = q+2, where \kappa_{\rho,W,N} is the restriction of \kappa_{\rho,N} in which each merged set of tensors is a cartesian product of tensors of width W. The best bound \omega' obtained by the laser method with merging applied to T_{CW}, in contrast, is the solution to \lim_{N\to\infty} \kappa_{\omega',N,N}^{1/N} = q+2. It could be that

\lim_{N\to\infty} \kappa_{\rho,N,N}^{1/N} > \lim_{W\to\infty} \lim_{N\to\infty} \kappa_{\rho,W,N}^{1/N},

and in that case \omega' < \omega_\infty. In other words, it could be the case that allowing the merging width to grow with N results in a better bound on \omega. Unfortunately, so far we haven’t been able to obtain an upper bound on \omega along these lines.

by Yuval Filmus at July 20, 2014 10:00 PM UTC

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).

enter image description here

by Scott Aaronson at July 19, 2014 03:32 PM UTC

Unfortunately the month of June was a very dry month for property testing. We could not find any papers on property testing (in ECCC or ArXiv) during the month of June. Hopefully we will have lots of papers in the month of July.

by Sourav Chakraborty at July 18, 2014 01:50 PM UTC

Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require $\Omega(n^2)$ space to solve. One of the few bright spots has been the development of semi-streaming algorithms for a handful of graph problems -- these algorithms use space $O(n \cdot \text{polylog}(n))$. In the annotated data streaming model of Chakrabarti et al., a computationally limited client wants to compute some property of a massive input, but lacks the resources to store even a small fraction of the input, and hence cannot perform the desired computation locally. The client therefore accesses a powerful but untrusted service provider, who not only performs the requested computation, but also proves that the answer is correct. We put forth the notion of semi-streaming algorithms for annotated graph streams (semi-streaming annotation schemes for short). These are protocols in which both the client’s space usage and the length of the proof are $O(n \cdot \text{polylog}(n))$. We give evidence that semi-streaming annotation schemes represent a substantially more robust solution concept than does the standard semi-streaming model. On the positive side, we give semi-streaming annotation schemes for two dynamic graph problems that are intractable in the standard model: (exactly) counting triangles, and (exactly) computing maximum matchings. The former scheme answers a question of Cormode. On the negative side, we identify for the first time two natural graph problems (connectivity and bipartiteness in a certain edge update model) that can be solved in the standard semi-streaming model, but cannot be solved by annotation schemes of “sub-semi- streaming” cost. That is, these problems are just as hard in the annotations model as they are in the standard model. Comment: The result on counting triangles was previously included in an earlier ECCC technical report (

at July 18, 2014 10:31 AM UTC

Authors: Yi Li, Xiaoming Sun, Chengu Wang, David P. Woodruff
Download: PDF
Abstract: We study the communication complexity of linear algebraic problems over finite fields in the multi-player message passing model, proving a number of tight lower bounds. Specifically, for a matrix which is distributed among a number of players, we consider the problem of determining its rank, of computing entries in its inverse, and of solving linear equations. We also consider related problems such as computing the generalized inner product of vectors held on different servers. We give a general framework for reducing these multi-player problems to their two-player counterparts, showing that the randomized $s$-player communication complexity of these problems is at least $s$ times the randomized two-player communication complexity. Provided the problem has a certain amount of algebraic symmetry, which we formally define, we can show the hardest input distribution is a symmetric distribution, and therefore apply a recent multi-player lower bound technique of Phillips et al. Further, we give new two-player lower bounds for a number of these problems. In particular, our optimal lower bound for the two-player version of the matrix rank problem resolves an open question of Sun and Wang.

A common feature of our lower bounds is that they apply even to the special "threshold promise" versions of these problems, wherein the underlying quantity, e.g., rank, is promised to be one of just two values, one on each side of some critical threshold. These kinds of promise problems are commonplace in the literature on data streaming as sources of hardness for reductions giving space lower bounds.

at July 18, 2014 12:40 AM UTC

Authors: Valerii Sopin
Download: PDF
Abstract: A determined algorithm is presented for solving the $rSUM$ problem for any natural $r$ with assessment of complexity of order of $n\log^{2} n$. In terms of an amount of memory used the obtained algorithm is of the linear order.

at July 18, 2014 12:00 AM UTC

Authors: Igor S. Sergeev
Download: PDF
Abstract: We construct explicit Boolean square matrices whose rectifier complexity (OR-complexity) differs significantly from the complexity of their complement matrices.

at July 18, 2014 12:40 AM UTC

Authors: Guy Even, Moti Medina
Download: PDF
Abstract: We present deterministic and randomized algorithms for the problem of online packet routing in grids in the competitive network throughput model \cite{AKOR}. In this model the network has nodes with bounded buffers and bounded link capacities. The goal in this model is to maximize the throughput, i.e., the number of delivered packets.

Our deterministic algorithm is the first online algorithm with an $O\left(\log^{O(1)}(n)\right)$ competitive ratio for uni-directional grids (where $n$ denotes the size of the network). The deterministic online algorithm is centralized and handles packets with deadlines. This algorithm is applicable to various ranges of values of buffer sizes and communication link capacities. In particular, it holds for buffer size and communication link capacity in the range $[3 \ldots \log n]$.

Our randomized algorithm achieves an expected competitive ratio of $O(\log n)$ for the uni-directional line. This algorithm is applicable to a wide range of buffer sizes and communication link capacities. In particular, it holds also for unit size buffers and unit capacity links. This algorithm improves the best previous $O(\log^2 n)$-competitive ratio of Azar and Zachut \cite{AZ}.

at July 18, 2014 12:40 AM UTC

New York Times, dateline June 11, 2019
With a near record-setting investment announced last week, the self-driving car service Elfdrive is the hottest, most valuable technology start-up on the planet. It is also one of the most controversial.
The company, which has been the target of protests across Europe this week, has been accused of a reckless attitude toward safety, of price-gouging its customers, of putting existing cabbies out of work and of evading regulation. And it has been called trivial. In The New Yorker last year, George Packer huffed that Elfdrive typified Silicon Valley’s newfound focus on “solving all the problems of being 20 years old, with cash on hand.”
It is impossible to say whether Elfdrive is worth the $117 billion its investors believe it to be; like any start-up, it could fail. But for all its flaws, Elfdrive is anything but trivial. It could well transform transportation the way Amazon has altered shopping — by using slick, user-friendly software and mountains of data to completely reshape an existing market, ultimately making many modes of urban transportation cheaper, more flexible and more widely accessible to people across the income spectrum.
Elfdrive could pull this off by accomplishing something that has long been seen as a pipe dream among transportation scholars: It has the potential to decrease private car ownership.
In its long-established markets, like San Francisco, using Elfdrive every day is already arguably cheaper than owning a private car. Elfdrive says that despite dust-ups about “elfpricing” at busy times, its cheapest service is usually 30 percent less expensive than taxis.
The competition between Elfdrive and its rivals is likely to result in more areas of the country in which self-driving becomes both cheaper and more convenient than owning a car, a shift that could profoundly alter how people navigate American cities.
Over the next few years, if Elfdrive do reduce the need for private vehicle ownership, they could help lower the cost of living in urban areas, reduce the environmental toll exacted by privately owned automobiles (like the emissions we spew while cruising for parking), and reallocate space now being wasted on parking lots to more valuable uses, like housing.
Paradoxically, some experts say, the increased use of self-driving cars could also spawn renewed interest in and funding for public transportation, because people generally use taxis in conjunction with many other forms of transportation.
In other words, if Elfdrive and its competitors succeed, it wouldn’t be a stretch to see many small and midsize cities become transportation nirvanas on the order of Manhattan — places where forgoing car ownership isn’t just an outré lifestyle choice, but the preferred way to live.
If you haven't guessed all I did was minor edits to a Farhod Manjoo piece on Uber. My point is that it all fits, there really isn't that much difference between a car driven by a magical AI elf or that driving by a real person, if it's all controlled by an app. You can start to see the effects of self-driving cars, the good and the bad, from what's going on now with ride-sharing services. The big difference with self-driving cars will be the complaints won't come just from the taxi drivers, but the truckers and delivery people as well.

by Lance Fortnow ( at July 17, 2014 01:24 PM UTC

Reingold, Trevisan, and Vadhan's breakthrough 2006 paper ( reduced the problem of showing $RL=L$ to producing pseudorandom walks on regular digraphs that are not consistently labeled.

Has any further progress on this problem been made since then?

by ruadath at July 17, 2014 08:00 AM UTC

An approach to complexity lower bounds?

Book source

Kurt Gödel did it all, succinctly. His famous 1938 paper “The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis” was {1\frac{1}{3}} pages long. Since the Proceedings of the National Academy of Sciences was printed on single-column pages in fairy large type, it would have been under one page in FOCS or STOC format. Only Leonid Levin has famously been that succinct.

Today Ken and I wish to advance another approach on complexity questions based on succinctness and Gödel’s brilliant idea. We have covered succinctness before, but now our angle is more arithmetical.

What Gödel showed is that if ZF is consistent then so is ZF + AC, where AC is the axiom of choice. He threw in GCH, the generalized continuum hypothesis, and two statements about analytic sets, but AC drew the most attention. Many were and remain worried about the Axiom of Choice. Gödel showed that AC is safe to use in the sense that a result employing it cannot reach a contradiction in set theory, unless set theory already is inconsistent without AC.

The proof method Gödel used is based on a notion of a set being constructible. Roughly, very roughly, a constructible set is one that can be built up inductively by simple operations. He then proved that if ZF has any model, then these sets are embedded inside it and form a model by themselves, in which AC, GCH, and the other two statements also hold.

Well, he didn’t exactly prove it. His paper begins with “THEOREM” but there is no “Proof” anywhere. Once he states his inductive definition, the rest is left to the reader as evident. Nor did Gödel feel a need to give us any more detail when he laid out his entire version of set theory on one little porta-board during the interview we published last November—see the “One Choice” section toward the end. When a definition accomplishes a proof by itself, that’s brilliance.

Constructible Sets

The ingredients of Gödel’s construction are ordinals {\alpha} and first-order formulas {\phi}. Once you know these ingredients, the definition is easy to figure out. For {\alpha = 0}, {L_\alpha = \emptyset}. Then a set {X} belongs to {L_{\alpha + 1}} if and only if there is a first-order formula {\phi} with one free variable {y} and quantified variables and constants ranging in {L_{\alpha}} such that

\displaystyle  X = \{y \in L_{\alpha} : \phi(y)\}.

And of course, if {\beta} is a limit ordinal, then

\displaystyle  L_\beta = \bigcup_{\alpha < \beta} L_\alpha.

This definition is so natural and nice that it does not appear in Gödel’s paper. It does not need to. The idea is clear enough. That is true brilliance. To be fair, the above undoubtedly came up in interaction with John von Neumann and others in the 1930s. Note, incidentally, that when {\alpha = 0} we get {X = \emptyset}, which gives {L_1 = \{\emptyset\}}, which is not the same as {L_0}. Thus Gödel’s sequence gets off the ground.

Today the notion of constructible sets is a huge part of logic and set theory. Ken and I ask, is there some way to make this notion useful for complexity theory? This involves a third ingredient: a set can be an element, even a number. Thus {\emptyset = 0}, {\{\emptyset\} = 1}, and {2} can be represented by {\{\emptyset,\{\emptyset\}\}} or by various other 2-element sets. There are also various ways to represent binary strings, ways that are naturally more compact than the representation {[n] = \{n-1\} \cup [n-1]} for numbers, but we will try to treat them all as numbers.

Constructive Integers, and Sets of Them

Our idea is to define a constructible number {x}, and then look at sets of such numbers. To distinguish from Gödel we now say “constructive.”

Let {x} be an integer of {n} bits, where {n = 2^k} for some {k}. In a natural way we can view {x} as a boolean function from {\{0,1\}^{k}} to {\{0,1\}} where the value {x(i)} is {x_{i}}. Say {x} is {s(n)}-constructive provided the Boolean function {x} has a circuit of size at most {s(n)}.

Clearly, this is only interesting if {s(n)} grows much slower than {n}, such as {s(n)} being polynomial—or at least sub-exponential—in {k}. We will discuss later trying to imitate Gödel’s definition further by using logical formulas in place of circuits. We keep it simple with circuits and numbers for now. Note that {k} increases only when {n} doubles, so if {s(n)} is really a function of {k}, then we get nesting finite sets {{\cal L}_k}. The following definitions are asymptotic, but have this concrete basis.

Definition 1 A set {A} of natural numbers is {s(n)}-constructive provided for each {x} in {A}, it is {s(|x|)}-constructive.

Definition 2 A set {A} is poly-constructive provided there is a {c} so that for each {x} in {A}, {x} is {s(n)}-constructive—where {s(n)} is bounded by {O(k^c) = O(\log^{c} n)}.

Thus a set {A} is poly-constructive if the members of the set each have a small circuit description. It does not require that {A} has a uniform circuit description, nor that the elements of {A} have circuits that are related to each other in any manner.

Let the universe of all poly-constructive sets be denoted by {\cal {PC}}.

Set Properties Of {\cal {PC}}

Let {A} and {B} be sets in {\cal {PC}}. Then we claim that the following are true:

{\bullet } The sets {A \cup B} and {A \cap B} are in {\cal {PC}}.

{\bullet } The set {A - B} is in {\cal {PC}}.

Thus the sets in {\cal {PC}} form a Boolean algebra. Even more, suppose that {S} is a subset of {A}, which is a set in {\cal {PC}}. Then {S} is also in {\cal {PC}}. This is just because for each {k}, we are talking about subsets of {{\cal L}_k}.

Next, let us consider bitwise operations. Regarding numbers {x,y} as {n}-bit strings, let {z = x \oplus y} be their bitwise-XOR. Now if {x,y} have circuits of size {s(n)} then {z} may need size {2s(n) + O(1)} including an XOR gate or gadget at the output. But asymptotically we still have poly constructiveness:

{\bullet} The set {A \oplus B = \{x \oplus y: x \in A \,\wedge\, y \in B\}} is in {\cal {PC}}.

Additive and Multiplicative Closure?

Now we turn to addition: {A + B = \{x + y: x \in A \wedge y \in B\}}. Note that unlike bitwise XOR, addition can increase the length of numbers by one, though this is not as important as with multiplication whereby lengths can double. The main issue is that the bits {z(i)} can depend on non-local parts of {x} and {y} via carries.

In the descriptive logic approach to complexity this is no problem, because the Boolean function {z(i)} can be defined by a first-order formula {\phi} in terms of the small indices {i,j,\dots} and fixed predicates denoting {x} and {y}. The formula is independent of {n}, so it is a single finite characterization of a set over all lengths {n}.

The problem is that the circuitry for simulating a first-order quantifier {\forall i} ranging over most of the indices {i} has size proportional to {n}, not to {k} or poly in {k}. So it might not stay succinct. We believe, however, that we can simulate it in poly({k}) size if parity counting can be done in polynomial time:

Theorem 3 (?) If {\oplus \mathsf{P} = \mathsf{P}}, then the universe of poly-constructive sets is closed under addition.

Contrapositively, if {{\cal{PC}}} is not closed under addition, then {\oplus \mathsf{P} \neq \mathsf{P}}, which is close to {\mathsf{NP} \neq \mathsf{P}}. Our idea for a proof is related to parity-based prediction in carry-lookahead adders (see this for instance).

Closure under multiplication, {A * B = \{x\cdot y: x \in A \,\wedge\, y \in B\}}, is even thornier. We wonder if the correspondence in descriptive complexity between multiplication and {\mathsf{TC}^0}, which is kind-of a scaled down analogue of {\mathsf{PP}} (unbounded error probabilistic polynomial time), carries through here:

Theorem 4 (??) If {\mathsf{PP} = \mathsf{P}}, then the universe of poly-constructive sets is closed under multiplication.

We suspect this but do not have a proof idea. Since {{\cal L}_k * {\cal L}_k} is contained in length-{2^{k+1}} strings, we can also ask concretely whether for appropriately-chosen {s(n)} it is contained in {{\cal L}_{k+1}}.

A Meta-Conjecture

What we actually want to establish is this:

Theorem 5 (???) There is a natural numerical operation {\circ} such that the universe of poly-constructive sets is closed under {\circ} (that is, on going from {A,B} to {A \circ B = \{x \circ y: x \in A \,\wedge\, y \in B\}}) if and only if {\mathsf{P}=\mathsf{NP}}.

A result like this would finally bring our Gödel-inspired idea to full force as a potentially useful re-scaling of the issues involved in {\mathsf{P=NP}}.

We can also consider using the intuitively looser condition of having a first-order formula to define members {z} of {A \circ B} in terms of members {x} of {A} and {y} of {B}, which immediately works for addition. This is close in form to Gödel’s definition itself. We suspect that this leads to involvement with the rudimentary relations and functions, which were introduced by Raymond Smullyan and studied in complexity theory by Celia Wrathall and others. Again it may yield an interesting re-scaling of the linear-time hierarchies involved.

Open Problems

Is the notion of {\cal {PC}} interesting? Can we prove the above theorems?

by Pip at July 17, 2014 01:05 AM UTC

The SoCG community had decided to leave the ACM. There is a good discussion of the topics involved on the making socg blog. The Rubicon had been crossed, the kosher sausage had been cut, etc.

I expect other conferences to leave the ACM in the near future. Of course, it is very hard to predict, especially the future…

by Sariel at July 17, 2014 12:34 AM UTC

Authors: Sarah R. Allen, Ryan O'Donnell
Download: PDF
Abstract: Let $X_1, \dots, X_n$ be joint $\{ \pm 1\}$-valued random variables. It is known that conditioning on a random subset of $O(1/\epsilon^2)$ of them reduces their average pairwise covariance to below $\epsilon$ (in expectation). We conjecture that $O(1/\epsilon^2)$ can be improved to $O(1/\epsilon)$. The motivation for the problem and our conjectured improvement comes from the theory of global correlation rounding for convex relaxation hierarchies. We suggest attempting the conjecture in the case that $X_1, \dots, X_n$ are the leaves of an information flow tree. We prove the conjecture in the case that the information flow tree is a caterpillar graph (similar to a two-state hidden Markov model).

at July 17, 2014 12:00 AM UTC

Authors: Anshumali Shrivastava, Ping Li
Download: PDF
Abstract: MinHash and SimHash are the two widely adopted Locality Sensitive Hashing (LSH) algorithms for large-scale data processing applications. Deciding which LSH to use for a particular problem at hand is an important question, which has no clear answer in the existing literature. In this study, we provide a theoretical answer (validated by experiments) that MinHash virtually always outperforms SimHash when the data are binary, as common in practice such as search.

The collision probability of MinHash is a function of resemblance similarity ($\mathcal{R}$), while the collision probability of SimHash is a function of cosine similarity ($\mathcal{S}$). To provide a common basis for comparison, we evaluate retrieval results in terms of $\mathcal{S}$ for both MinHash and SimHash. This evaluation is valid as we can prove that MinHash is a valid LSH with respect to $\mathcal{S}$, by using a general inequality $\mathcal{S}^2\leq \mathcal{R}\leq \frac{\mathcal{S}}{2-\mathcal{S}}$. Our worst case analysis can show that MinHash significantly outperforms SimHash in high similarity region.

Interestingly, our intensive experiments reveal that MinHash is also substantially better than SimHash even in datasets where most of the data points are not too similar to each other. This is partly because, in practical data, often $\mathcal{R}\geq \frac{\mathcal{S}}{z-\mathcal{S}}$ holds where $z$ is only slightly larger than 2 (e.g., $z\leq 2.1$). Our restricted worst case analysis by assuming $\frac{\mathcal{S}}{z-\mathcal{S}}\leq \mathcal{R}\leq \frac{\mathcal{S}}{2-\mathcal{S}}$ shows that MinHash indeed significantly outperforms SimHash even in low similarity region.

We believe the results in this paper will provide valuable guidelines for search in practice, especially when the data are sparse.

at July 17, 2014 12:41 AM UTC

Authors: Troy Lee, Zhaohui Wei, Ronald de Wolf
Download: PDF
Abstract: Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.

at July 17, 2014 12:40 AM UTC

Authors: Romain Hollanders, Balázs Gerencsér, Jean-Charles Delvenne, Raphaël M. Jungers
Download: PDF
Abstract: We construct a family of Order-Regular matrices of size $m \times n$ such that $m \sim \Omega\big(\sqrt[10]{33}^n\big)$. Previously Order-Regular matrices were known only for $m \sim O\big(\sqrt{2}^n\big)$.

at July 17, 2014 12:40 AM UTC

Authors: Danny Hucke, Markus Lohrey, Eric Noeth
Download: PDF
Abstract: It is shown that every tree of size n over a fixed set of s different ranked symbols can be decomposed into O(n log s / log n) many hierarchically defined pieces. Formally, such a hierarchical decomposition has the form of a straight-line linear context-free tree grammar of size O(n log s / log n), which can be used as a compressed representation of the input tree. This generalizes an analogous result for strings. Previous grammar-based tree compressors were not analyzed for the worst-case size of the computed grammar, except for the top dag of Bille et al., for which only the weaker upper bound of O(n / log^{0.19} n) for unranked and unlabelled trees has been derived. The main result is used to show that every arithmetical formula of size n, in which only m different variables occur, can be transformed (in time O(n log n)) into an arithmetical circuit of size O(n log m / log n) and depth O(log n). This refines a classical result of Brent from 1974, according to which an arithmetical formula of size n can be transformed into a logarithmic depth circuit of size O(n).

at July 17, 2014 12:00 AM UTC

Authors: Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou
Download: PDF
Abstract: We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we first show that the problem remains PSPACE-complete even for bipartite series-parallel graphs, which form a proper subclass of bipartite planar graphs. We note that our reduction indeed shows the PSPACE-completeness for graphs with pathwidth two, and it can be extended for threshold graphs. In contrast, we give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. Thus, this paper gives precise analyses of the problem with respect to pathwidth.

at July 17, 2014 12:41 AM UTC

[The following blog report on MMDS’14 was written by my student Mahdi Zamani - Ed]

Recently, I attended the MMDS workshop hosted by UC Berkeley. The workshop consisted of 40 talks distributed in four days and a poster session. It focused on algorithmic and statistical problems in large scale data analysis and brought together researchers from several areas including computer science, mathematics, statistics, and Big Data practitioners. In the third day of the workshop, I presented a poster about our recent work on multi-party sorting of large data sets. The following is a brief summary of a few talks that seemed interesting to me and my current research projects. The workshop program is available here.

Dan Suciu from University of Washington talked about running queries on very large databases. He argued that traditionally database queries were measured in terms of disk I/O but in Big Data query processing, since the database is store on distributed clusters, communication is the bottleneck. Now, the problem is to run a query on p servers via a Massive Parallel Communication (MPC) model, where the goal is to minimize the load on each server. In this model, the database records are partitioned among p servers each getting M/p, where M is the total number of records. Then, the database operations (like SQL joins) are performed on the partitions. As an example, Dan mentions a popular operation in Big Data analysis called triangle that is defined over three relations: Q(x,y,z)=R(x,y) join S(y,z) join T(z,x). Using a naive approach, this query can be computed in two communication rounds, doing two separate joins. But, surprisingly, it can be computed in a single communication round with reasonable load on each server using a simple technique described by Dan in [3].

Stanley Hall Auditorium

Bill Howe from University of Washington talked about Myria, a web-based framework written in Java for Big Data query processing. He is motivated by the fact that at least we, as scientists, spend more than 90% of our time handling data for our experiments rather than designing new techniques and algorithms  (I think by scientists he means practitioners here. I believe theoreticians spend much less time working with data :). Bill explains that although current Hadoop optimizations are more than 100 times faster than Hadoop itself, we still need faster and simpler frameworks that can be at least used by non-expert scientists. The main idea behind Myria is to blur the distinction between relational algebra and linear algebra. In other words, every query in the relational domain is translated to simple linear algebraic equations that can be computed very fast. Myria provides an imperative-declarative language that runs queries in parallel.

Yiannis Koutis from University of Puerto Rico talked about spectral algorithms for mining data from large graphs. Spectral analysis is an important tool for graph partitioning, where the set of vertices of a large graph is divided into smaller components such that the number of edges running between separated components is small. This is often an important subproblem for complexity reduction or parallelization. A cut that provides the smallest number of such edges is called the sparsest cut. Such a cut bisects the graph into the most important components. Given an adjacency matrix A of a graph G, the general idea behind spectral graph partitioning is that the eigenvector associated with the second smallest eigenvalue of the Laplacian matrix L of A is the sparsest cut of G (given a matrix A and the degree matrix of A denoted by D, the Laplacian matrix of can be computed as L=D-A). Since finding the exact eigenvalues of the Laplacian matrix is often computationally intensive, Yiannis argues that one can find a good (small) sparse cut by approximating the eigenvalues. However, it is an open problem whether one can find better cuts using another technique with similar computational costs. At the end of the talk, I asked Yiannis whether probabilistic methods (such as random walks) are slower than spectral methods. He answered that probabilistic methods are usually local, and global random walks are often much slower than global spectral analysis.

David Woodruff from IBM Almaden Research talked about an optimal CUR matrix decomposition technique. Given a matrix A, the goal is to find three matrices C, U, and R such that A=C.U.R. A solution to this problem can be used in many applications such as recommendation systems. For example, Netflix is interested in fast techniques for decomposing its huge users-by-movies matrix into a matrix of the most important users and a matrix of the most important movies. Since the exact decomposition is often very computationally expensive, an approximation is calculated instead. Although there are fast randomized algorithms for solving this problem (e.g., [2]), David proposes their asymptotically-optimal deterministic algorithm published recently in STOC 2014 [1].

Xavier Amatriain from Netflix talked about current Big Data challenges of his company. Until 2007, the company had over 100 million movie ratings and now it holds about 5 billion ratings. The company currently has 44 million users around the world and holds more than 5 billion hours of movies. The users play about 50 million movies and submit 5 million ratings per day. This contributes to about 32% of US daily downstream traffic. From this huge pile of data, Netflix needs to extract ranking and similarity information about the movies. Their main approach to this end is to employ distributed machine learning algorithms. Xavier argues that in today’s world more data sometimes beats better algorithms. He backs up his claim by a quote from Peter Norving, Director of Research at Google: “Google does not have better algorithms, only more data” (see this). Xavier continues by arguing that training algorithms can run in parallel because training data are often independent of each other. He also describe how they have scaled their algorithms by distributing at three different levels: across regions or subsets of the population, at the hyperparameter optimization stage, and at the model training level.

[A polished version of this report is available here - Ed]


[1] Christos Boutsidis, David P. Woodruff: “Optimal CUR Matrix Decompositions”, Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 353—362, 2014. URL:

[2] Michael Mahoney, Petros Drineas: “CUR Matrix Decompositions for Improved Data Analysis”, Proceedings of the National Academy of Sciences, pp. 697—702, 2009.

by Jared at July 16, 2014 09:20 PM UTC

This is my last research life-story (at least for now), possibly concluding this project (though you are all very welcomed to share more as long as this blog lives). My main hope was to give legitimacy to all of us to acknowledge and discuss our uncomfortable feelings and the “non-scientific” challenges of our careers. My experience with myself and others is that many of these neuroses are quite universal. And they are not necessarily correlated with success, which sometimes only adds internal pressure. Paraphrasing what Russell Impagliazzo told me the first time we met (years ago): we really are competing with ourselves, and this is a hopeless competition (I’m sure he said it better). As for myself, I feel that I learned how to enjoy our profession much more over the years (mainly through becoming a little less childish with time). Still, at times, I do feel inapt. Such a period is the topic of my last story.

During my last postdoc year, we had our first child. This was a wonderful event that I had been craving for years. But it was also very demanding. My son was colicky and we were inexperienced and mostly alone in the U.S. In addition we had three house moves, one of which was back to Israel (a move that was surprisingly non-smooth). I was very content with putting my young family at the center and I realized that this is a period that will not repeat itself and should be cherished (turns out that with kids, many periods are like that). I also understood that I cannot expect to do too much research at this period. There was nothing concrete I was worried about: I had just landed my dream position at Weizmann, I wasn’t worried about getting tenure, and I already had many results that I was very proud of (including one with Irit Dinur on PCPs that was quite recent). I could allow myself to take it easy, but my ego was not ready for that. With time, internal pressure accumulated. “Is this it? Did my creativity dry up? Is it downhill from now on?”

At the end of that year at Weizmann (with my son being just a bit over a year), I headed with my family to a summer trip to Berkeley (to work with Luca Trevisan and Irit Dinur) and to Cambridge (to Work with Salil Vadhan). I decided to invest all of the effort in problems related to RL vs. L and felt that this is a test for me. If I’ll fail, then I will scale down my expectation of myself. With this shaky (and so very silly) state of mind, I came to a complexity-theory workshop that started the trip. Though my talk about the work with Irit was very well received, I felt quite depressed. It felt like everyone have been doing these wonderful research and only I was idle. I especially remember one of these talks, with a speaker (who I knew to be very nice) that had an over-confident demeanor. Such individuals always put me off, but at this strangely vulnerable state of mind, it was a challenge to keep the tears inside.

The summer continued quite differently. Spending time with wonderful friends (who happen to be brilliant researchers), having a lot of time for vacationing with my family (thanks to Luca’s great life balance), and ending up with a result that exceeded all of my hopes (undirected connectivity in log-space). I remember very vividly the exact moment when two ideas that I had for many years suddenly clicked in an exciting new way. I remember pacing back and forth in our hotel room, going over the proof that then only existed in my mind. Could it be true? Surely not! But where could the bug be hiding? I remember going out to find a store that would have a notepad and pen for me to start writing the proof down and the slowly growing confidence that came from writing it down and every session of verification (Luca, Irit, Salil, …). And most of all, I remember all of the colleagues being happy with me and for me.

I am not sure if there is a lesson to be learned here. Perhaps, don’t believe everything you are feeling. Or at least – if you are neurotic, you are not the only one here.

* title inspired by Aretha .

by Omer Reingold at July 16, 2014 03:30 PM UTC

The Simons Foundation has issued a call for proposals for their new program Simons Collaborations in Mathematics and the Physical Sciences.  The aim of the program is to “stimulate progress on fundamental scientific questions of major importance in the broad area of mathematics, theoretical physics, and theoretical computer science.”  An example is the Simons Collaboration on Algorithms and Geometry.

Grant sizes are up to $2.5m/year for 4 years (which can be extended to 7 years).  Letters of intent are due by October 31.

by salilvadhan at July 16, 2014 03:00 PM UTC

Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field $\mathbb{F}$ of characteristic zero. We resolve this problem by proving a $N^{\Omega(\frac{d}{\tau})}$ lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin at most $\tau$ computing an explicit $N$-variate polynomial of degree $d$ over $\mathbb{F}$. Meanwhile, Nisan and Wigderson (FOCS 1995) had posed the problem of proving superpolynomial lower bounds for homogeneous depth five arithmetic circuits. We show a lower bound of $N^{\Omega(\sqrt{d})}$ for homogeneous depth five circuits (resp. also for depth three circuits) with bottom fanin at most $N^{\mu}$, for any fixed $\mu < 1$. This resolves the problem posed by Nisan and Wigderson only partially because of the added restriction on the bottom fanin (a general homogeneous depth five circuit has bottom fanin at most $N$).

at July 16, 2014 09:08 AM UTC

Special Quantum PCP and/or Quantum Codes: Simplicial Complexes and Locally Testable CodesDay

24 Jul 2014 - 09:30 to 17:00

room B-220, 2nd floor, Rothberg B Building

On Thursday, the 24th of July we will host a SC-LTC (simplicial complexes and classical and quantum locally testable codes) at the Hebrew university, Rothberg building B room 202 (second floor) in the Givat Ram campus. Please join us, we are hoping for a fruitful and enjoyable day, with lots of interactions. Coffee and refreshments will be provided throughout the day, as well as free “tickets” for lunch on campus
There is no registration fee, but please email preferably by next Tuesday if there is a reasonable probability that you attend -  so that we have some estimation regarding the number of people, for food planning

Program:SC-LTC day – simplicial complexes and locally testable classical and quantum codes -Rothberg building B202
9:00 gathering: coffee and refreshments

9:30 Irit Dinur: Locally testable codes, a bird’s eye view

10:15: coffee break

10:45 Tali Kaufman, High dimensional expanders and property testing

11:30 15 minutes break

11:45 Dorit Aharonov, quantum codes and local testability

12:30 lunch break

2:00 Alex Lubotzky: Ramanujan complexes

2:50 coffee break

3:15 Lior Eldar: Open questions about quantum locally testable codes and quantum entanglement

3:45 Guy Kindler: direct sum testing and relations to simplicial complexes ( Based on David, Dinur, Goldenberg, Kindler, and Shinkar, 2014)

4:15-5 free discussion, fruit and coffee


by Gil Kalai at July 16, 2014 07:56 AM UTC