# Theory of Computing Blog Aggregator

### Harvard Junior Faculty Job Search

Harvard Computer Science is doing a junior faculty search this year.  We pretty much have been doing one every year, but it's nice to be able to make an announcement and point people to the ad.

So here is the ad, telling you what you need so send in if you're applying.

Also as usual, we're looking in all areas, because we're always interested in great people.  However, in the interest of full disclosure, the focus this year is described as
This is a broad faculty search and we welcome outstanding applicants in all areas of computer science, including applicants whose research and interests connect to such areas as engineering, health and medicine, or the social sciences. Of particular interest are candidates with a focus on systems and data science, including operating systems, networking, software engineering, data storage and management, and computational science.
We'll look forward to your application.

by Michael Mitzenmacher (noreply@blogger.com) at October 24, 2014 06:46 PM UTC

### TR14-136 | Classical Automata on Promise Problems | Viliam Geffert, Abuzer Yakaryilmaz

from ECCC papers

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Second, despite of the existing quadratic gap between Las Vegas realtime probabilistic automata and one-way deterministic automata for language recognition, we show that, by turning to promise problems, the tight gap becomes exponential. Last, we show that the situation is different for one-way probabilistic automata with two-sided bounded-error. We present a family of unary promise problems that is very easy for these machines; solvable with only two states, but the number of states in two-way alternating or any simpler automata is not limited by a constant. Moreover, we show that one-way bounded-error probabilistic automata can solve promise problems not solvable at all by any other classical model.

### TR14-135 | Sign rank, VC dimension and spectral gaps | Shay Moran, Amir Yehudayoff, Noga Alon

from ECCC papers

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe connections to combinatorics, communication complexity and learning theory. We also provide explicit examples of matrices with low VC dimension and high sign rank. Let $A$ be the $N \times N$ point-hyperplane incidence matrix of a finite projective geometry with order $n \geq 3$ and dimension $d \geq 2$. The VC dimension of $A$ is $d$, and we prove that its sign rank is larger than $N^{\frac{1}{2}-\frac{1}{2d}}$. The large sign rank of $A$ demonstrates yet another difference between finite and real geometries. To analyse the sign rank of $A$, we introduce a connection between sign rank and spectral gaps, which may be of independent interest. Consider the $N \times N$ adjacency matrix of a $\Delta$ regular graph with a second eigenvalue in absolute value $\lambda$ and $\Delta \leq N/2$. We show that the sign rank of the signed version of this matrix is at least $\Delta/\lambda$. A similar statement holds for all regular (not necessarily symmetric) sign matrices. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem.

### TR14-134 | Parameterized Complexity of CTL: Courcelle&#39;s Theorem For Infinite Vocabularies | Martin Lück, Arne Meier, Irina Schindler

from ECCC papers

We present a complete classification of the parameterized complexity of all operator fragments of the satisfiability problem in computation tree logic CTL. The investigated parameterization is temporal depth and pathwidth. Our results show a dichotomy between W[1]-hard and fixed-parameter tractable fragments. The two real operator fragments which are in FPT are the fragments containing solely AF, or AX. Also we prove a generalization of Courcelle's theorem to infinite vocabularies which will be used to proof the FPT-membership cases.

### TR14-133 | Mutual Dimension | Adam Case, Jack H. Lutz

from ECCC papers

We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory measure of mutual algorithmic information. Our main theorem, the data processing inequality for mutual dimension, says that, if $f:\mathbb{R}^m \rightarrow \mathbb{R}^n$ is computable and Lipschitz, then the inequalities $mdim(f(x):y) \leq mdim(x:y)$ and $Mdim(f(x):y) \leq Mdim(x:y)$ hold for all $x \in \mathbb{R}^m$ and $y \in \mathbb{R}^t$. We use this inequality and related inequalities that we prove in like fashion to establish conditions under which various classes of computable functions on Euclidean space preserve or otherwise transform mutual dimensions between points.

### An Alternative to the Seddighin-Hajiaghayi Ranking Methodology

from Luca Trevisan

[Update 10/24/14: there was a bug in the code I wrote yesterday night, apologies to the colleagues at Rutgers!]

[Update 10/24/14: a reaction to the authoritative study of MIT and the University of Maryland. Also, coincidentally, today Scott Adams comes down against reputation-based rankings]

Saeed Seddighin and MohammadTaghi Hajiaghayi have proposed a ranking methodology for theory groups based on the following desiderata: (1) the ranking should be objective, and based only on quantitative information and (2) the ranking should be transparent, and the methodology openly revealed.

Inspired by their work, I propose an alternative methodology that meets both criteria, but has some additional advantages, including having an easier implementation. Based on the same Brown University dataset, I count, for each theory group, the total number of letters in the name of each faculty member.

Here are the results (apologies for the poor formatting):

1 ( 201 ) Massachusetts Institute of Technology
2 ( 179 ) Georgia Institute of Technology
3 ( 146 ) Rutgers – State University of New Jersey – New Brunswick
4 ( 142 ) University of Illinois at Urbana-Champaign
5 ( 141 ) Princeton University
6 ( 139 ) Duke University
7 ( 128 ) Carnegie Mellon University
8 ( 126 ) University of Texas – Austin
9 ( 115 ) University of Maryland – College Park
10 ( 114 ) Texas A&M University
11 ( 111 ) Northwestern University
12 ( 110 ) Stanford University
13 ( 108 ) Columbia University
14 ( 106 ) University of Wisconsin – Madison
15 ( 105 ) University of Massachusetts – Amherst
16 ( 105 ) University of California – San Diego
17 ( 98 ) University of California – Irvine
18 ( 94 ) New York University
19 ( 94 ) State University of New York – Stony Brook
20 ( 93 ) University of Chicago
21 ( 91 ) Harvard University
22 ( 91 ) Cornell University
23 ( 87 ) University of Southern California
24 ( 87 ) University of Michigan
25 ( 85 ) University of Pennsylvania
26 ( 84 ) University of California – Los Angeles
27 ( 81 ) University of California – Berkeley
28 ( 78 ) Dartmouth College
29 ( 76 ) Purdue University
30 ( 71 ) California Institute of Technology
31 ( 67 ) Ohio State University
32 ( 63 ) Brown University
33 ( 61 ) Yale University
34 ( 54 ) University of Rochester
35 ( 53 ) University of California – Santa Barbara
36 ( 53 ) Johns Hopkins University
37 ( 52 ) University of Minnesota – Twin Cities
38 ( 49 ) Virginia Polytechnic Institute and State University
39 ( 48 ) North Carolina State University
40 ( 47 ) University of Florida
41 ( 45 ) Rensselaer Polytechnic Institute
42 ( 44 ) University of Washington
43 ( 44 ) University of California – Davis
44 ( 44 ) Pennsylvania State University
45 ( 40 ) University of Colorado Boulder
46 ( 38 ) University of Utah
47 ( 36 ) University of North Carolina – Chapel Hill
48 ( 33 ) Boston University
49 ( 31 ) University of Arizona
50 ( 30 ) Rice University
51 ( 14 ) University of Virginia
52 ( 12 ) Arizona State University
53 ( 12 ) University of Pittsburgh

I should acknowledge a couple of limitations of this methodology: (1) the Brown dataset is not current, but I believe that the results would not be substantially different even with current data, (2) it might be reasonable to only count the letters in the last name, or to weigh the letters in the last name by 1 and the letters in the first name by 1/2. If there is sufficient interest, I will post rankings according to these other methodologies.

### Btrim: A fast, lightweight adapter and quality trimming program for next-generation sequencing technologies

Authors: Yong Kong
Abstract: Btrim is a fast and lightweight software to trim adapters and low quality regions in reads from ultra high-throughput next-generation sequencing machines. It also can reliably identify barcodes and assign the reads to the original samples. Based on a modified Myers's bit-vector dynamic programming algorithm, Btrim can handle indels in adapters and barcodes. It removes low quality regions and trims off adapters at both or either end of the reads. A typical trimming of 30M reads with two sets of adapter pairs can be done in about a minute with a small memory footprint. Btrim is a versatile stand-alone tool that can be used as the first step in virtually all next-generation sequence analysis pipelines. The program is available at \url{this http URL}.

### Tight tradeoffs for approximating palindromes in streams

Authors: Pawel Gawrychowski, Przemyslaw Uznanski
Abstract: We consider the question of finding the longest palindrome in a text of length $n$ in the streaming model, where the characters arrive one-by-one, and we cannot go back and retrieve a previously seen character. While computing the answer exactly using sublinear memory is not possible in such a setting, one can still hope for a good approximation guarantee. We focus on the two most natural variants, where we aim for either an additive or a multiplicative approximation of the length of the longest palindrome. We first show, that there is no point in considering either deterministic or Las Vegas algorithms in such a setting, as they cannot achieve sublinear space complexity. For Monte Carlo algorithms, we provide a lowerbound of $\Omega(\frac{n}{E})$ bits for approximating the answer with an additive error $E$, and $\Omega(\frac{\log n}{\varepsilon})$ bits for approximating the answer within a multiplicative factor of $(1+\varepsilon)$. Then we construct a generic Monte Carlo algorithm, which by choosing the parameters appropriately achieves space complexity matching up to a logarithmic factor for both variants. This substantially improves the previous results [Berenbrink et al., STACS 2014] and essentially settles the space complexity of the problem.

### On the Average-case Complexity of Parameterized Clique

Authors: Nikolaos Fountoulakis, Tobias Friedrich, Danny Hermelin
Abstract: The k-Clique problem is a fundamental combinatorial problem that plays a prominent role in classical as well as in parameterized complexity theory. It is among the most well-known NP-complete and W[1]-complete problems. Moreover, its average-case complexity analysis has created a long thread of research already since the 1970s. Here, we continue this line of research by studying the dependence of the average-case complexity of the k-Clique problem on the parameter k. To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that k-Clique admits both analogues for Erd\H{o}s-R\'{e}nyi random graphs of arbitrary density. We also show that k-Clique is unlikely to admit neither of these analogs for some specific computable input distribution.

### Permutation Reconstruction from Differences

Authors: Marzio De Biasi
Abstract: We prove that the problem of reconstructing a permutation $\pi_1,\dotsc,\pi_n$ of the integers $[1\dotso n]$ given the absolute differences $|\pi_{i+1}-\pi_i|$, $i = 1,\dotsc,n-1$ is NP-complete. As an intermediate step we first prove the NP-completeness of the decision version of a new puzzle game that we call Crazy Frog Puzzle. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.

### A type assignment for lambda-calculus complete both for FPTIME and strong normalization

Authors: Erika De Benedetti, Simona Ronchi Della Rocca
Abstract: One of the aims of Implicit Computational Complexity is the design of programming languages with bounded computational complexity; indeed, guaranteeing and certifying a limited resources usage is of central importance for various aspects of computer science. One of the more promising approaches to this aim is based on the use of lambda-calculus as paradigmatic programming language and the design of type assignment systems for lambda-terms, where types guarantee both the functional correctness and the complexity bound. Here we propose a system of stratified types, inspired by intersection types, where intersection is a non-associative operator. The system, called STR, is correct and complete for polynomial time computations; moreover, all the strongly normalizing terms are typed in it, thus increasing the typing power with respect to the previous proposals. Moreover, STR enjoys a stronger expressivity with respect to the previous system STA, since it allows to type a restricted version of iteration.

### Quantum algorithms for shortest paths problems in structured instances

Authors: Aran Nayebi, Virginia Vassilevska Williams
Abstract: We consider the quantum time complexity of the all pairs shortest paths (APSP) problem and some of its variants. The trivial classical algorithm for APSP and most all pairs path problems runs in $O(n^3)$ time, while the trivial algorithm in the quantum setting runs in $\tilde{O}(n^{2.5})$ time, using Grover search. A major open problem in classical algorithms is to obtain a truly subcubic time algorithm for APSP, i.e. an algorithm running in $O(n^{3-\varepsilon})$ time for constant $\varepsilon>0$. To approach this problem, many truly subcubic time classical algorithms have been devised for APSP and its variants for structured inputs. Some examples of such problems are APSP in geometrically weighted graphs, graphs with small integer edge weights or a small number of weights incident to each vertex, and the all pairs earliest arrivals problem. In this paper we revisit these problems in the quantum setting and obtain the first nontrivial (i.e. $O(n^{2.5-\varepsilon})$ time) quantum algorithms for the problems.

### Guest Post by Dr. Hajiaghayi: A new way to rank departments

(This is a guest post by MohammadTaghi Hajiaghayi. His name is not a typo- the first name really is MohammadTaghi.)

Due to our belief in the lack of transparency and well-defined measures in methods used by U.S News to rank CS departments in theoretical computer science (and in general), my PhD. student Saeed Seddighin and I have worked for several months to provide a ranking based on a real and measurable method of the number of papers in TCS for the top 50 US Universities. To make this possible, we gathered the information about universities from various resources. You may see the ranking and our exact methodology here.

Indeed  we have some initial rankings based on similar measures for computer science in general as well which we plan to release soon (we are still in  the process of double-checking or even triple-checking our data and our analysis due to several factors). CS theory ranking is our initial ranking release to get feedback at this point.

Please feel free to give us feedback (hajiagha@cs.umd.edu).

by GASARCH (noreply@blogger.com) at October 23, 2014 03:11 PM UTC

### TR14-132 | Information Complexity for Multiparty Communication | Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

from ECCC papers

In this paper, we have studied the information complexity for the communication model involving more than two parties. A lot of work has already been done on the information complexity in two party communication model and the question of extending the definition of information complexity to the multiparty communication model was posed in \cite{Braverman12}. In this paper, we first give a definition of internal information cost for a protocol involving more than two parties and our definition matches the definition known for two party model. Our definition is valid for both in NIH model and NOF model. We also extend several results known for information complexity of two party model to multiparty communication setting. One of them is the additivity property, which eventually gives us the direct sum theorem for both information cost and distributional information cost. We give a lower bound for the information complexity of a function involving more that two parties in terms of communication complexity and this lower bound matches with the bound known for the function evaluated by only two parties. We also show that the amortized communication complexity of a function computed by $k$ parties is lower bounded by the information complexity and upper bounded by $(k-1)$ times the information complexity and this relation is true for both distributional and non-distributional case.

### A New Twist on Flexagons?

from Richard Lipton

For Martin Gardner’s 100th birthday

 Global Science source

Martin Gardner introduced many including myself to the joys of Discrete Mathematics. His glorious monthly column “Mathematical Games” for Scientific American included some continuous mathematics too, of course; one could say it was on “Concrete Mathematics.” However, I conjecture—based on a quick flip of the several books I own of his columns—that the symbols ${\epsilon,\delta}$ in a calculus context never appeared in them.

Yesterday was the 100${{}^{th}}$ anniversary of Gardner’s birth. Dick and I wish to join the many others marking this centennial and thanking him for all he did to make math fun for so many.

His feature kicked off in 1956 with the famous column on hexaflexagons, which I will talk about in a moment. Gardner related in his autobiography, which was assembled three years after his death in 2010, how important this column was as his “break.” However, the column that made the most lasting impression on me began with the words:

The calculus of finite differences, a branch of mathematics that is not too well known but is at times highly useful, occupies a halfway house on the road from algebra to calculus.

This discrete “calculus” enables one to calculate a formula for any polynomial sequence ${p(n)}$ given enough values for ${n = 0,1,2,...}$ It also led to my favorite “visual proof” that ${0^0 = 1}$: For any integer ${k > 0}$, if you write out the powers ${k^n}$ going across and take differences of adjacent values repeatedly to make an infinite equilateral triangle pointing down, the left side has the powers of ${(k-1)}$. Iterating this gives you the powers of ${0}$, but the entry for ${k^0}$ as ${k}$ counts down to ${0}$ steadfastly remains ${1}$.

## Tributes and Contributions

Tributes have been gathered all during this centennial year. Scientific American observed yesterday by posting a review of ten of Gardner’s most appreciated columns. Bill Gasarch’s post yesterday links to some of his and Lance Fortnow’s previous items on Gardner, and further to a site where anyone can contribute a testimonial.

Frederic Friedel, who co-founded the chess-database company ChessBase three decades ago, knew Gardner personally from 1979 as a fellow original member of the Committee for Scientific Investigation of Claims of the Paranormal (CSICOP, now CSI). The committee remains housed in my town of Amherst near Buffalo, now at the Center for Inquiry (CFI Western NY) which is across Sweet Home Road from my university campus. Friedel has described to me cold days in Buffalo and round tables with Carl Sagan and other luminaries. All this was before my own arrival in 1989.

Friedel was also among the column readers with whom Gardner interacted from the beginning in the 1950s. His awesome tribute yesterday includes appreciation of Gardner’s book Fads and Fallacies in the Name of Science, which also made a strong impression on me, and other links. Dick recalls the great chapter of that book that starts with Gardner saying that this next crazy claim cannot be disproved. It was that the universe was created recently with a full fossil record that makes it look much older. Indeed, it could be a so-called “Boltzmann Brain”—and a point made in this NY Times article is that it’s crazy that this is not crazy.

I never had any contact with Gardner, despite making a few visits to CFI; it ranks among numerous lost opportunities. I could mention many other influences from his columns, and looking through his book Mathematical Circus just now reminded me that his chapter on “Mascheroni Constructions” was my first knowledge of what I called the “class ${\mathsf{NC}}$” in my “STOC 1500″ post with Dick. I had a similar experience to what Douglas Hofstadter told in his own tribute in May 2010: I started off interested in Math+Physics, intending to take the latter as far as quantum mechanics and particles at Princeton. But I found advanced mechanics and electrodynamics tough going, and am ever grateful for being allowed to parachute out of the latter at midterm into Steve Maurer’s Discrete Mathematics course, in which I knew I’d found my métier. As I could have realized from my love of Gardner all along.

## The Twist

I’ve wanted to make a post on my hexaflexagon twist when I had time to create nice pictures, but now I will have to make do by referring to the fine illustrations in Gardner’s original column, which is freely available from the M.A.A. here. It requires making the standard “hexa-hexa” as shown in Gardner’s Figure 2. For best effect, in addition to numbering the faces 1–6 as shown there (and using a solid color for each face), label the six components of each face A–F in the left-to-right order given there.

The “Twist” is always applicable from one of the three inner faces (1, 2, or 3); finding when it applies from one of the outer faces and from the configurations that follow is more of a challenge. Instead of flexing as shown in Figure 3, follow these directions:

• Put your right thumb and forefinger on the two rightmost triangles (which will be ‘2A’ and ‘2B’ in the bottom part D of Figure 2 after the final flap with ‘1A’ is folded to complete the flexagon), and put your left thumb and forefinger over the opposite two (‘2E’ and ‘2D’).

• Fold the flexagon in half away from you, keeping the horizontal diameter toward you.

• Then tease the bottom-left triangle and the bottom triangle (‘2D’ and ‘2C’) toward you to open a bowl of four triangles, with your right thumb and forefinger now pinched together to make a flap that stands over the bowl.

• Fold the flap over into the bowl (‘2B’ onto ‘3B’), and then fold the bowl flat with the top point meeting the bottom point. You now have a lozenge of two triangles (‘2E’ and ‘2F’ uppermost).

• Flip the lozenge over so you can grab at the opposite point from the two that met.

• You should be able to open from that point into another bowl of four triangles.

• Then you can lift the thickest flap at right (with ‘1C’) out of the bowl. (If a twist move fails, this is where it fails, in which case backtrack and try again elsewhere.)

• Then close the bowl inversely to how you opened the other bowl, so that you again have a flexagon folded in half away from you, and grab at the opposite end to open it.

What you will get is a flexagon with the colors on its faces jumbled up—if you’ve used the lettering, you will have ‘1C’, ‘5B’, and ‘2F’-‘2E’-‘2D’-‘2C’ clockwise from upper right. You will still be able to flex it the standard way, but only exposing one other face—that is, you will have something isomorphic to a tri-hexaflexagon.

Now the real fun is that you can iterate this process. For one thing, you can invert it to restore your original hexa-hexaflexagon (teasing ‘2E’ and ‘2F’ forward and folding in ‘1C’). But you can also find other places from which to initiate another “Twist,” and these will lead to more tri-hexa configurations. One is to flip it over, rotate once counterclockwise so you fold backwards with ‘6B’ and ‘3C’ at right, tease forward ‘3E’-‘3D’, tuck ‘3C’ into the bowl atop ‘1D’, collapse and grab at the other end of ‘2A’-‘6A’, lift flap ‘2D’ out of the bowl, and unfold to see ‘2D’-‘4D’-‘6A’-‘2A’-‘3E’-‘3D’. Then you can flip over, rotate once more counterclockwise, and iterate—but there are other twists too.

Some will lump up thick wads of paper on three triangles of each face, so be ginger about it. Finally, after much exploration, you may come upon the “Dual Hexa.” This has six faces, in which the inner three alternate colors. It is, in fact, the configuration you would build if you first rotated the top part A of Gardner’s Figure 3 by 180 degrees. Then you may find a way to go from the primal to the dual and back by a long regular pattern of repeated twists.

As a high-school student in 1976, I attempted to map out the entire space of reachable configurations by hand, but made some bookkeeping errors and gave up. I wanted to write a computer program to simulate my twists, but did not make the time.

## Open Problems

Can you do the “Twist”? The space of configurations you can explore is much larger than the “Tuckerman Traverse” of the standard hexa-hexa shown in Gardner’s Figure 4. Can you map it all out? Has anyone previously known about this?

[some format and word changes, updated to include letters of facets.]

by KWRegan at October 23, 2014 04:59 AM UTC

### Computing the Skorokhod Distance between Polygonal Traces (Full Paper)

Authors: Rupak Majumdar, Vinayak S. Prabhu
Abstract: The \emph{Skorokhod distance} is a natural metric on traces of continuous and hybrid systems. For two traces, from $[0,T]$ to values in a metric space $O$, it measures the best match between the traces when allowed continuous bijective timing distortions. Formally, it computes the infimum, over all timing distortions, of the maximum of two components: the first component quantifies the {\em timing discrepancy} of the timing distortion, and the second quantifies the mismatch (in the metric space $O$) of the values under the timing distortion. Skorokhod distances appear in various fundamental hybrid systems analysis concerns: from definitions of hybrid systems semantics and notions of equivalence, to practical problems such as checking the closeness of models or the quality of simulations. Despite its popularity and extensive theoretical use, the \emph{computation} problem for the Skorokhod distance between two finite sampled-time hybrid traces has remained open.

We address in this work the problem of computing the Skorokhod distance between two polygonal traces (these traces arise when sampled-time traces are completed by linear interpolation between sample points). We provide the first algorithm to compute the exact Skorokhod distance when trace values are in $\reals^n$ for the $L_1$, $L_2$, and $L_{\infty}$ norms. Our algorithm, based on a reduction to Frechet distances, is fully polynomial-time, and incorporates novel polynomial-time procedures for a set of geometric primitives in $\reals^n$ over the three norms.

### Computational Complexity of Tensor Nuclear Norm

Authors: Shmuel Friedland, Lek-Heng Lim
Abstract: The main result of this paper shows that the weak membership problem in the unit ball of a given norm is NP-hard if and only if the weak membership problem in the unit ball of the dual norm is NP-hard. Equivalently, the approximation of a given norm is polynomial time if and only if the approximation of the dual norm is polynomial time. Using the NP-hardness of the approximation of the spectral norm of tensors we show that the approximation of the nuclear norm is NP-hard. We relate our results to bipartite separable states in quantum mechanics.

### Posimodular Function Optimization

Authors: Toshimasa Ishii, Kazuhisa Makino
Abstract: Given a posimodular function $f: 2^V \to \mathbb{R}$ on a finite set $V$, we consider the problem of finding a nonempty subset $X$ of $V$ that minimizes $f(X)$. Posimodular functions often arise in combinatorial optimization such as undirected cut functions. In this paper, we show that any algorithm for the problem requires $\Omega(2^{\frac{n}{7.54}})$ oracle calls to $f$, where $n=|V|$. It contrasts to the fact that the submodular function minimization, which is another generalization of cut functions, is polynomially solvable.

When the range of a given posimodular function is restricted to be $D=\{0,1,...,d\}$ for some nonnegative integer $d$, we show that $\Omega(2^{\frac{d}{15.08}})$ oracle calls are necessary, while we propose an $O(n^dT_f+n^{2d+1})$-time algorithm for the problem. Here, $T_f$ denotes the time needed to evaluate the function value $f(X)$ for a given $X \subseteq V$.

We also consider the problem of maximizing a given posimodular function. We show that $\Omega(2^{n-1})$ oracle calls are necessary for solving the problem, and that the problem has time complexity $\Theta(n^{d-1}T_f)$ when $D=\{0,1,..., d\}$ is the range of $f$ for some constant $d$.

### A unified approach to linear probing hashing with buckets

Authors: Svante Janson, Alfredo Viola
Abstract: We give a unified analysis of linear probing hashing with a general bucket size. We use both a combinatorial approach, giving exact formulas for generating functions, and a probabilistic approach, giving simple derivations of asymptotic results. Both approaches complement nicely, and give a good insight in the relation between linear probing and random walks. A key methodological contribution, at the core of Analytic Combinatorics, is the use of the symbolic method (based on q-calculus) to directly derive the generating functions to analyze.

### Algorithms for Art Gallery Illumination

Authors: Maximilian Ernestus, Stephan Friedrichs, Michael Hemmer, Jan Kokemüller, Alexander Kröller, Mahdi Moeini, Christiane Schmidt
Abstract: We consider a variant of the Art Gallery Problem, where a polygonal region is to be covered with light sources, with light fading over distance. We describe two practical algorithms, one based on a discrete approximation, and another based on nonlinear programming by means of simplex partitioning strategies. For the case where the light positions are given, we describe a fully polynomial-time approximation scheme. For both algorithms we present an experimental evaluation.

### A Fast Hybrid Primal Heuristic for Multiband Robust Capacitated Network Design with Multiple Time Periods

Authors: Fabio D'Andreagiovanni, Jonatan Krolikowski, Jonad Pulaj
Abstract: We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (B\"using and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim that uses a system of multiple deviation bands. Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization, which exploits information coming from linear relaxations of the problem, and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps.

Authors: Aaron Adcock, Erik D. Demaine, Martin L. Demaine, Michael P. O'Brien, Felix Reidl, Fernando Sánchez Villaamil, Blair D. Sullivan
Abstract: When can $t$ terminal pairs in an $m \times n$ grid be connected by $t$ vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the cover all vertices'' constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class. The latter restriction is a common form of the famous Nikoli puzzle \emph{Numberlink}; our problem is another common form of Numberlink, sometimes called \emph{Zig-Zag Numberlink} and popularized by the smartphone app \emph{Flow Free}.

### BDA 2014

from Jared Saia

[The following report on BDA’14 was written by my student Mahdi Zamani]

[A more polished version of this report is available HERE]

Recently, Mahnush and I attended a workshop on Biological Distributed Algorithms co-located with DISC 2014. The workshop consisted of 20 talks distributed in two days and focused on the relationships between distributed computing and distributed biological systems and in particular, on analysis and case studies that combine the two. The following is a summary of some of the talks we found interesting.

### Insect Colonies and Distributed Algorithms; Insect Colony Researcher Viewpoint, Anna Dornhaus, University of Arizona

Anna talked about several open questions in modeling the behavior of different insect colonies. Insect colonies go through many changes over time in response to their changing needs and environment.

Most changes happen via complex collective behaviors such as task allocation, foraging (food finding), nest building, load transport, etc. One interesting aspect of insect colonies is that unreliable individual behaviors result in complex group behaviors that are reliable. Individuals use various methods of communication such as pheromone trails, versatile signals, visual cues, substrate vibration, and waggle dance. Waggle dance is a sophisticated method of communication among honeybees to indicate resource locations by showing the angle from sun. Biologists are generally interested in computer models to know how individual behaviors impact group behaviors. In particular, they are interested to understand how positive feedbacks (a process A produces more of another process B which in turn produces more of A and so on) lead to significant consequences such as symmetry breaking. For example, ants tend to choose from one food source even if there are multiple similar sources around them. Also, larger colonies result in more symmetry breaking behavior. This motivates the following questions: How does the size of a colony affect collective behavior? Why is the workload distribution so uneven in some biological systems?

### Distributed Algorithms and Biological Systems, Nancy Lynch, MIT

Nancy started by describing similarities between biological and distributed systems. Both systems often have components that perform local communications using message passing and local broadcasting. In bio systems, there are components with simple states that follow simple rules. To model a bio system using a distributed algorithm, the first step is to define the problem, the platform (physical capabilities of the system such as memory), and the strategies (rules).
Nancy then talked about two important distributed problems: leader election and maximal independent sets (MIS). In leader election, there is a ring of processes that can communicate with their neighbors and the goal is to pick a leader process. If the processes are all identical and their behaviors are deterministic, then solving this problem is impossible due to symmetry (all processes are similar). On the other hand, if the processes are not identical (i.e., each has a unique ID), then finding a leader is possible. Interestingly, in a setting with identical processes that are allowed to make random choices, this problem can be solved using a biased coin: each party flips a coin with probability to announce itself as the leader.
In MIS, the goal is to find the largest subset of the vertices of a graph such that no two neighbors (i.e., vertices connected directly via an edge) are both in the subset. There is a Las Vegas algorithm [B]  for solving this problem: in each of several rounds, each party flips a biased coin and informs its neighbors that it is in the MIS if it has not received a similar message from its neighbors. Each party stops if either it is in MIS or one of its neighbors in the MIS. Nancy finally talked about three ant colony problems that her research group has recently been working on: Ants foraging, house hunting, and task allocation.

### Modeling Slime Mold Networks, Saket Navlakha, CMU

Saket started his talk by explaining an experiment related to slime mold, where the mold food was put in different locations similar to the station of the Tokyo rail system. They observed that the mold grew in a similar network as the rail system. This is very interesting because Japanese engineers could have asked a slime mold to design the rail system instead of spending several hours on the design.

Saket then continued by describing their model of the slime mold behavior for finding food sources. For simplicity, they assume there is a complete graph at first and then by calculating flow over the edges (tubes) some of the edges are disconnected. Then, they measured and compared the cost, efficiency, and fault tolerance of the network generated by their model and the Tokyo rail system: their model is as efficient as the rail system! The brain development has a similar behavior: it generates a complete neural network at first and then prunes over time. This is called the synaptic pruning algorithm.

The human brain starts with a very dense network of neurons and each edge keeps track of the number of times it is used to route information based on some pre-determined distribution. Then, the network is pruned based on the flow information. Saket finally talked about a similar distributed model for bacterial foraging (E. coli) in complicated terrains.

### Collective Load Transport in Ants, Ofer Feinerman, Weizmann Institute

Ever seen a group of ants carrying a large foot item together? Ofer talked about collective load retrieval, the process in which a large number of ants cooperate to carry a large food item to the nest. Ofer’s research team tracked a group of ants and the load over distances of about 1000 ant lengths and used image analysis to obtain highly detailed information. They showed that the collective motion is highly cooperative and guided by temporary leaders that are knowledgeable regarding the correct direction home. Ofer finally presented a theoretical model suggesting that the ant-load system is poised at a critical point between random and ballistic motions which renders it highly susceptible to a knowledgeable leader. He played a video showing a group of ants carrying their load in a wrong direction. Then, one ant joined the group as the leader and corrected the direction.

### Distributed Information Processing by Insect Societies, Stephen Pratt, Arizona State University

Stephen talked about a collective model of optimal house-hunting in rock ant Temnothorax albipennis. Each colony of T. albipennis has a single queen and hundreds of scouts (workers). In the process of house-hunting, scouts first discover new nests and assess them according to some criteria such as size and darkness. Then, they recruit other ants to the new nest using tandem running, where an informed ant leads a second ant to her destination to get a second opinion about the nest (see Figure 3↓).

Figure 3. Ants tandem run (courtesy of Stephen Pratt)

When the number of ants in the new nest reaches a threshold, scouts begin rapid transport of the rest of the colony by carrying nest-mates. In each time step, each ant is in one of these three states: explore, tandem, and transport. The transition between these states happens based on the ant’s evaluation of the quality of the nest sites and the population of the ants in this sites. Stephen defines optimality with regards to the speed and accuracy of the decision-making process. He asked: Does a colony have a greater cognitive capacity than an individual? For the house-hunting process, recent lab experiments show that when the number of nests (choices) increases, colony performs much better in choosing the good choices while lone ants visit more nests. He then asked: Do colonies make more precise discriminations than individuals? To answer this, Stephen’s team ran experiments to measure how individuals and colonies can correctly compare a dark nest with nests with various brightness levels. Interestingly, they observed that colonies can correctly choose darker nests with significantly more accuracy than individuals. They also show that even two ants perform significantly better than one.

### Cells, Termites, and Robot Collectives, Radhika Nagpal, Harvard University

Radhika talked about biological systems from an engineering viewpoint. Collective behaviors often result in self-repairing and self-organizing properties which are crucial for building robust systems. In bio systems, these properties are achieved from cooperation of vast numbers of unreliable agents.

Figure 4. Termite-inspired robots
(courtesy of Harvard University)

Radhika described a bio-inspired distributed robot system that can perform group tasks such as collective construction, collective transport, and pattern/shape formation. The robots achieve a desired global goal in a completely decentralized fashion by performing local interactions with other robots. In particular, they model a large population of termites for building complex structures (see Figure 4↑).

### Confidence Sharing: An Economic Strategy for Efficient Information Flows in Animal Groups, Amos Korman, CNRS and University of Paris Diderot

Amos started his talk by defining two methods of communication that exist in biological systems: passive (indirect) and active (direct) communication. Passive communication is done by transferring information with no direct intention of signaling, i.e., cues from the behavior of one animal are indirectly perceived by others. For example, it is shown that animals align their movements to those performed by their neighbors. In active communication, an animal communicates directly with others by sending parts of its internal state via, for example, pheromone trails, cell signaling, etc. Amos then continued his talk by arguing that confidence exists among animals: they are shown to become more responsive as their certainty drops. For example, crickets increase their speed when they are more confident about their intention. This confidency is propagated from one cricket to others via passive and active communication. By sharing their confidence, agents improve their unreliable individual estimates. Amos described an algorithm in which each agent compresses all information it has gathered into a single parameter that represents its confidence in its behavior. This gives a very simple and near optimal algorithm. The algorithm continuously updates agents confidence level based on the interaction it has with other agents. Unfortunately, if there are bandwidth and computational restrictions to agents, then the performance of this algorithm decreases significantly. Also, the algorithm assumes two agents who exchange confidence information must have disjoint set of exchange history.

### Task Allocation in Ant Colonies, Alex Cornejo, Harvard University

Alex presented a general mathematical model for task allocation in ant colonies that can be used to achieve optimal division of labor. Based on this model, Alex described a distributed randomized efficient algorithm for task allocation that imposes minimal assumptions on the capabilities of the individual ants. The proposed algorithm requires constant amount of memory. Moreover, it assumes the ants have a primitive binary feedback function to sense the current labor allocation and to determine whether a particular task requires more workers or not. The algorithm also assumes individual workers do not differ in their ability to perform tasks. The proposed algorithm for ants converges to a near-optimal task allocation with high probability in time which is logarithmic in the size of the colony.
Compared to the previous work on task allocation, the proposed algorithm is different in the following aspects: it uses constant memory per ant, works only when the number of tasks to allocate is a small constant, and the allocation is for proportions of workers (and not for individual workers), and all workers are similar. Once workers are variant in ability to perform tasks, the task allocation problem becomes NP-hard. One drawback that was pointed out by one of the participants is that their model does not strictly adhere to the real ants’ behaviors.

by Jared at October 22, 2014 10:31 PM UTC

### Cuckoo Filters

An upcoming paper appearing at CoNext will be of interest to any Bloom Filter user or aficionado:

Cuckoo Filter:  Practically Better than Bloom
(Bin Fan, David Andersen, Michael Kaminsky, Michael Mitzenmacher)

Let me describe a cuckoo filter and some of what's in the paper for you.  If you want to avoid a technical discussion, all you need to know is that for reasonably large sized sets, for the same false positive rate as a corresponding Bloom filter, cuckoo filters use less space than Bloom filters, are faster on lookups (but slower on insertions/to construct), and amazingly also allow deletions of keys (which Bloom filters cannot do).  If you want to look at code, there's even a github repository for you with code for cuckoo filters.

Note:  I'll assume you probably know what a Bloom filter is in the discussion that follows.  As a reminder, it's a hash-based data structure for set membership that can give false positives;  by allowing false positives, you can save space in your representation of the set.  I'll assume you probably know what cuckoo hashing is.  As a reminder, in cuckoo hashing, you have buckets that can contain a fixed number of keys, and each key gets some number d of buckets (obtained by getting d values from hashing the key) where it can be placed.  When you insert a new key, if all of its buckets are full, you can move keys out of that bucket to one of its other buckets to make room.  Since apparently there are drinking games that exist based on taking a drink whenever I use the word "Bloom filter" or "cuckoo hashing" in a talk, I imagine most readers of the blog know about these things.  (Or, always, Wikipedia.)

The framework used in the paper comes from the following idea.  One way of implementing Bloom filter functionality when given a static set of items is to use a perfect hash function;  that is, as hash function that maps the n elements of your set into an array of size n in a 1-1 fashion.  Then, you use another hash function to store a fingerprint of the element instead of the element itself in the array location.  To do a set membership test on an element z, you hash z once to find its location in the array, and hash z again to find its fingerprint, and check against the fingerprint in the array location.  For elements not in the set, you get a false positive rate of 2^{# of fingerprint bits}.

The problem is that the perfect hashing framework doesn't allow you to insert new items naturally.  Or do deletions (but standard Bloom filters don't allow deletions also -- you need a counting Bloom filter for that).  So a natural thing to do is to think of using some other sort of hash table, besides a perfect hash table, and see what happens.  This idea was explored way back in for instance some papers I worked on in 2006 (here and here) using "d-left" hash tables, which are based on a multiple choice hashing scheme.

If you're going to use multiple choice hashing schemes, though, you should think about using cuckoo hashing.  The ability to move keys around means you should get better space utilization;  for example, even with 2 choices, if your buckets can hold 4 items, cuckoo hashing can get you about 95% space utilization.  The problem with cuckoo hashing in this setting is that, for a Bloom filter, you want to just keep fingerprints of keys, not the keys themselves.  So, when you want to move the key, how do you figure out where to move it to -- you no longer have the key to hash?

The approach used in the paper is a trick called partial-key cuckoo hashing.  To get two buckets for our key, we do a hash to get the first bucket (idealized to be uniformly at random), but to get the second bucket, we do not hash the key, but just the fingerprint of the key;  we XOR that value with the value for the first bucket to get the second.  The upside of this approach is given a bucket and a fingerprint in the bucket we can find the other bucket corresponding to the fingerprint.  (XORing the hash of the fingerprint works if the fingerprint is in the first bucket or the second, as is easily checked.)  The downside is if our fingerprint has F bits, that means our second bucket is really only chosen from 2^F possibilities;  it is not uniform conditioned on the first.

Because of this limitation, one interesting aspect of the paper is that we show, in theory, this approach just will not work.  Specifically, there is an Omega(log n) lower bound on the size of the fingerprint that must be stored; this means the cuckoo filter is super-linear in space, unlike standard Bloom filters which are linear in space.  This lower bound is easy to derive.  Suppose that you have buckets that can hold b keys.  If 2b+1 keys have the same pair of buckets, then there is trouble;  you can't fit 2b+1 keys into 2b bucket slots.  So the question is whether there are collections of 2b+1 keys that have the same pair of buckets.  With standard cuckoo hashing, this would be a low probability event.  With partial-key cuckoo hashing, the probability depends on the size of the fingerprint, since this determines how many possible second choices of a bucket there are for each key (given their first random choice of a bucket).  If you have too few choices, you will get too many collisions, or too many keys in a pair of buckets.  Some straightforward calculations yield the Omega(log n) lower bound on the size of the fingerprint.

So now that we've proven theoretically that this won't work, how could it work in practice?  If you go back to those calculations, you find that the lower bound has some nice constant factors.  The bounds you get on the fingerprint size are actually (roughly speaking) log n/(2b).  That constant factor in the denominator, even when b=4, covers a large range of n.  In practice, fingerprints can be quite a reasonable size, and still avoid the potential bottleneck of too large a group of keys all hashing to the same small number of buckets.

In any case, this may be the first paper I've written that contains a proof that the described data structure fails in theory but works in practice.  (The other way around I generally find much easier.)

Big open theoretical question:  try to analyze why partial-key cuckoo hashing gets roughly the same load threshold as regular cuckoo hashing.  (Anyone want to work on that?  Let me know...)

This post is long enough;  there's a lot more in the paper, including comparisons with other schemes, bit-saving tricks, and lots of performance results.  Have a look.

Postscript/Tangent:  In a recent review (for a different paper, with a different theme) one reviewer made the following comment/criticism:  "Despite years of research, no one has found a variant of cuckoo hashing that can outperform simpler methods in realistic situations."  To which I say, hunh?  Yes, I understand linear probing is wonderful in practice due to cache effects and block sizes and in many and perhaps even most situations can yield better performance than cuckoo hash tables.  But certainly not everywhere.  Cuckoo hash tables certainly seem at least potentially better for many hardware settings, and for at least some important applications -- such as this one -- cuckoo hashing seems to be a clear win.  (The issue here is the number of fingerprints you have to deal with on a lookup affects the false positive probability -- so even if linear probing lookups are "faster" due to cache effects and block sizes, if you try to get this sort of space utilization you get larger contiguous blocks which increase your false positives.)

My co-author David Andersen also violently disagrees with this review comment, and points to these recent papers at NSDI and Eurosys.

Perhaps I'm missing something, but my thought was this was a sign of a bad review (both in content, and in its overall rudeness).  I felt obliged to try to correct the record (and I can only hope the reviewer sees this post).

by Michael Mitzenmacher (noreply@blogger.com) at October 22, 2014 06:17 PM UTC

### MSR SVC Letters

The Committee for the Advancement of Theoretical Computer Science put together an open letter to several research leaders at Microsoft.
We feel that there should have been a better way to close down this lab, one that would have allowed them to have continuous employment until academic jobs are available again in September 2015. Given that this lab was continuing to produce exceptional — indeed revolutionary — research, we fail to understand why closing it had to be done so suddenly.
I recommend reading the whole letter. Many in the theory community and beyond, including myself, signed the original letter or added their support in the comments.

Yesterday Harry Shum, Microsoft Executive VP for Technology and Research sent a reply.
No one at Microsoft feels good about the fact that a significant number of our friends and colleagues were laid off.  These people contributed to the success of Microsoft over many years.  As one can readily imagine, the decisions made about how the cuts were implemented within MSR were extremely complicated and personally painful.  We feel with you the sense of loss that has been evoked by the closing of our Silicon Valley lab.
Theory Matters has a cover email. More on the CRA Policy Blog.

I'd like to thank the CATCS leadership in putting together the letter which expressed well the thoughts and concerns of the community. The tone of the letter hit the right notes and really made Microsoft research leadership think about the important role the company plays in the larger computer science academic world.

by Lance Fortnow (noreply@blogger.com) at October 22, 2014 04:34 PM UTC

### Microsoft Research Response to Open Letter

from Theory Matters

—–Original Message—–
From: Peter Lee (MSR) [mailto:petelee@microsoft.com]
Sent: Tuesday, October 21, 2014 6:24 PM
Cc: Harry Shum; Jeannette Wing

Dear Salil, SIGACT Community, and Colleagues:

Thank you for your letter. We are grateful for the obvious thought and care you have put into expressing the concerns of the research community. It helps all of us in MSR and Microsoft to know that people care deeply about what we do and the health of our organization.

We welcome the invitation to respond. Toward this end, we have posted a note on the MSR Connections Blog at http://blogs.msdn.com/b/msr_er/archive/2014/10/21/harry-shum-open-letter-to-academic-research-community.aspx. We thank you for giving us the opportunity to explain that we share your concerns, and also to state clearly that Microsoft and MSR remain committed to fundamental research, now and into the future. We look forward to continuing the deep partnership between the research community and MSR.

Sincerely,

Harry Shum, Peter Lee, and Jeannette Wing

by salilvadhan at October 22, 2014 11:20 AM UTC

### Most memorable CS paper titles

Following a fruitful question in MO, I thought it would be worthwhile to discuss some notable paper names in CS.

It is quite clear that most of us might be attracted to read (or at least glance at) a paper with an interesting title (every time I go over a list of papers in a conference), or avoid reading poorly named articles.

Which papers do you remember because of their titles (and, not-necessarily, the contents)?

My favorite, while not a proper TCS paper is "The relational model is dead, SQL is dead, and I don’t feel so good myself." .

### Generalized Compression Dictionary Distance as Universal Similarity Measure

Authors: Andrey Bogomolov, Bruno Lepri, Fabio Pianesi
Abstract: We present a new similarity measure based on information theoretic measures which is superior than Normalized Compression Distance for clustering problems and inherits the useful properties of conditional Kolmogorov complexity. We show that Normalized Compression Dictionary Size and Normalized Compression Dictionary Entropy are computationally more efficient, as the need to perform the compression itself is eliminated. Also they scale linearly with exponential vector size growth and are content independent. We show that normalized compression dictionary distance is compressor independent, if limited to lossless compressors, which gives space for optimizations and implementation speed improvement for real-time and big data applications. The introduced measure is applicable for machine learning tasks of parameter-free unsupervised clustering, supervised learning such as classification and regression, feature selection, and is applicable for big data problems with order of magnitude speed increase.

### Simple PTAS's for families of graphs excluding a minor

Authors: Sergio Cabello, David Gajser
Abstract: We show that very simple algorithms based on local search are polynomial-time approximation schemes for Maximum Independent Set, Minimum Vertex Cover and Minimum Dominating Set, when the input graphs have a fixed forbidden minor.

### Stochastic billiards for sampling from the boundary of a convex set

Authors: A. B. Dieker, Santosh Vempala
Abstract: Stochastic billiards can be used for approximate sampling from the boundary of a bounded convex set through the Markov Chain Monte Carlo (MCMC) paradigm. This paper studies how many steps of the underlying Markov chain are required to get samples (approximately) from the uniform distribution on the boundary of the set, for sets with an upper bound on the curvature of the boundary. Our main theorem implies a polynomial-time algorithm for sampling from the boundary of such sets.

### Polynomials: a new tool for length reduction in binary discrete convolutions

Authors: Amihood Amir, Oren Kapah, Ely Porat, Amir Rothschild
Abstract: Efficient handling of sparse data is a key challenge in Computer Science. Binary convolutions, such as polynomial multiplication or the Walsh Transform are a useful tool in many applications and are efficiently solved.

In the last decade, several problems required efficient solution of sparse binary convolutions. both randomized and deterministic algorithms were developed for efficiently computing the sparse polynomial multiplication. The key operation in all these algorithms was length reduction. The sparse data is mapped into small vectors that preserve the convolution result. The reduction method used to-date was the modulo function since it preserves location (of the "1" bits) up to cyclic shift.

To date there is no known efficient algorithm for computing the sparse Walsh transform. Since the modulo function does not preserve the Walsh transform a new method for length reduction is needed. In this paper we present such a new method - polynomials. This method enables the development of an efficient algorithm for computing the binary sparse Walsh transform. To our knowledge, this is the first such algorithm. We also show that this method allows a faster deterministic computation of sparse polynomial multiplication than currently known in the literature.

### Optimal randomized incremental construction for guaranteed logarithmic planar point location

Authors: Michael Hemmer, Michal Kleinbort, Dan Halperin
Abstract: Given a planar map of $n$ segments in which we wish to efficiently locate points, we present the first randomized incremental construction of the well-known trapezoidal-map search-structure that only requires expected $O(n \log n)$ preprocessing time while deterministically guaranteeing worst-case linear storage space and worst-case logarithmic query time. This settles a long standing open problem; the best previously known construction time of such a structure, which is based on a directed acyclic graph, so-called the history DAG, and with the above worst-case space and query-time guarantees, was expected $O(n \log^2 n)$. The result is based on a deeper understanding of the structure of the history DAG, its depth in relation to the length of its longest search path, as well as its correspondence to the trapezoidal search tree. Our results immediately extend to planar maps induced by finite collections of pairwise interior disjoint well-behaved curves.

### On computational complexity of length embeddability of graphs

Authors: Mikhail Tikhomirov
Abstract: A graph $G$ is embeddable in $\mathbb{R}^d$ if vertices of $G$ can be assigned with points of $\mathbb{R}^d$ in such a way that all pairs of adjacent vertices are at the distance 1. We show that verifying embeddability of a given graph in $\mathbb{R}^d$ is NP-hard in the case $d > 2$ for all reasonable notions of embeddability.

### A simpler and better LSH for Maximum Inner Product Search (MIPS)

Authors: Behnam Neyshabur, Nathan Srebro
Abstract: In a recent manuscript ("Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)", available on arXiv and to be presented in the upcoming NIPS), Shrivastava and Li argue that there is no symmetric LSH for the problem of Maximum Inner Product Search and propose an asymmetric LSH based on different mappings for query and database points. We show a simple LSH for the problem, using a simple symmetric mapping, with better performance, both theoretically and empirically.

### Rearrangement Problems with Duplicated Genomic Markers

Authors: Antoine Thomas
Abstract: Understanding the dynamics of genome rearrangements is a major issue of phylogenetics. Phylogenetics is the study of species evolution. A major goal of the field is to establish evolutionary relationships within groups of species, in order to infer the topology of an evolutionary tree formed by this group and common ancestors to some of these species. In this context, having means to evaluate relative evolutionary distances between species, or to infer common ancestor genomes to a group of species would be of great help. This work, in the vein of other studies from the past, aims at designing such means, here in the particular case where genomes present multiple occurrencies of genes, which makes things more complex. Several hypotheses accounting for the presence of duplications were considered. Distances formulae as well as scenario computing algorithms were established, along with their complexity proofs.

### Martin Gardner Centennial

Martin Gardner was born on October 21, 1914, so today is his Centennial (he died on May 22, 2010, at the age of 95). We've mentioned him in the blog before:

1.  The Life of Martin Gardner
2.  Contribute to the Gardner Centennial
3.  Another Post on Martin Gardner
4. I used the anagram Tim Andrer Gran in both my review of the Lipton-Regan book (see here) and my Applications of Ramsey Theory to History paper (see here)

So what can I add on his centennial?

1. He was not the first person to write on recreational mathematics, but he was certainly early and did it for a long time.
2. I suspect he influenced everyone reading this who is over 50. For every y, y is under 50 and reading this column, there exists x such that MG influenced x and x influenced y.
3. The line between recreational'' and serious'' math is sometimes blurry or hard to see. An obvious case of this was Euler and the Bridges problem leading to graph theory. At one time solving equations was done for competition, which seems recreational. Galois theory is not recreational.
4. Donald Knuth's book Selected Papers in Discrete Math (reviewed by me here) states I've never been able to see the boundary between scientific research and game playing.
5. I am reading a book  Martin Gardner in the 21st century which is papers by people who were inspired by him. The papers really do blur the distinction between recreational and serious. Some are rather difficult but all start out with a fun problem.
6. Aside from recreational math he did other things- magic, and debunking bad science.  (Fads and Fallacies in the name of science was excellent.) He was a well rounded person which is rare now.
7. Brian Hayes and Ian Stewart and others do what he did, but given the times we live in now, its hard capture the attention of a large segment of the public. (analogous to that when I was a kid there were only a handful of TV stations, now there are... too many?)
8. When I was in high school I went to the library looking for math books I could read (naive?). I found one of his books (collection of his columns) and began reading it. I learned about casting out nines and I learned what was to be the first theorem I ever learned a proof of outside of class (given that I was probably 12 it may be the first proof I learned ever). It was that (in todays lang) a graph is Eulerian iff every vertex is even degree.

by GASARCH (noreply@blogger.com) at October 21, 2014 03:09 PM UTC

### Algorithms that never get coded up

(There was a passing ref to this topic in the comments to one of Scott's blogs, so I thought I would pick up the theme.)

When I teach Formal Lang Theory I end up teaching them many algorithms that I don't think are ever coded up. Or if they are, I doubt they are used. A common refrain in my class is

Could you code this up?

Would you want to?

If the answers are YES and NO then they are enlightened.

Here are some examples of algorithms that are commonly taught but are never really used. They are still good to know

1. The algorithm that takes a DFA and makes a Regular Expression out of it. (I use the R(i,j,k) algorithm- R(i,j,k) is the set of all strings that take you from state i to state j using a subset of  {1,...,k} as intermediaries. One computes a reg exp for R(i,j,k) via dynamic programming. The actual reg expressions may get very long so I do not know if its poly time. But its not coded up since there is never a reason to go from a DFA to a Reg Exp. (There IS a reason to go from a Reg Exp to a DFA). Note that it IS good to know that REG EXP = DFA= NDFA so this IS worth teaching and knowing, AND its a nice example of Dyn Programming.
2. The algorithm that takes any CFG and puts it in Chomsky Normal form. The only grammars really used now (for compliers) are of a much more specialized type.
3. The algorithm that shows that and CFL is in P (O(n^3), though you can do better) that uses Chomsky Normal Form. Again, Nobody uses general grammars. Still good to know that CFL's are in P, and again a nice Dyn Programming algorithm.
4. Converting a PDA to a CFG. I doubt this is ever done. The converse is of course a key to compliers. But the converse is done for very specialized grammars, not general ones. Again though, good to know that CFG's and PDA's are equivalent. The PDA to CFG conversion is NOT nice.
5. Converting a Blah-tape Blah-head Turing Machine to a Blah'-tape, Blah'-head Turing Machine.  Important to know you can do it, not important to know the details, not worth coding up unless you are trying to win that contest where you want to get really small Univ TM's
6. All of the reductions in NP-completeness. I doubt any are actually done. Since we have very good SAT solvers there may be algorithms to convert problems TO SAT problems.
If I am wrong on any of these and something on the above list IS worth coding up and HAS been code up and IS being used, then I will be delighted to hear about it.

by GASARCH (noreply@blogger.com) at October 21, 2014 02:34 PM UTC

### An Improved Scheme for Asymmetric LSH

Authors: Anshumali Shrivastava, Ping Li
Abstract: A recent technical report developed a provably sublinear time algorithm for approximate \emph{Maximum Inner Product Search} (MIPS), by observing that inner products, after independent asymmetric transformations, can be converted into the problem of approximate near neighbor search in terms of the $L_2$ distance. We name the particular ALSH scheme in\cite{Report:ALSH_arXiv14} as {\em L2-ALSH}. In this study, we present another asymmetric transformation scheme which converts the problem of maximum inner products into the problem of maximum correlation search. The latter can be solved efficiently by "sign random projections". We name this new scheme as {\em Sign-ALSH}. Theoretical analysis shows that {\em Sign-ALSH} can be noticeably more advantageous than {\em L2-ALSH}. Our experimental study confirms the theoretical finding.
Abstract: Motivated by a sampling problem basic to computational statistical inference, we develop a nearly optimal algorithm for a fundamental problem in spectral graph theory and numerical analysis. Given an $n\times n$ SDDM matrix ${\bf \mathbf{M}}$, and a constant $-1 \leq p \leq 1$, our algorithm gives efficient access to a sparse $n\times n$ linear operator $\tilde{\mathbf{C}}$ such that $${\mathbf{M}}^{p} \approx \tilde{\mathbf{C}} \tilde{\mathbf{C}}^\top.$$ The solution is based on factoring ${\bf \mathbf{M}}$ into a product of simple and sparse matrices using squaring and spectral sparsification. For ${\mathbf{M}}$ with $m$ non-zero entries, our algorithm takes work nearly-linear in $m$, and polylogarithmic depth on a parallel machine with $m$ processors. This gives the first sampling algorithm that only requires nearly linear work and $n$ i.i.d. random univariate Gaussian samples to generate i.i.d. random samples for $n$-dimensional Gaussian random fields with SDDM precision matrices. For sampling this natural subclass of Gaussian random fields, it is optimal in the randomness and nearly optimal in the work and parallel complexity. In addition, our sampling algorithm can be directly extended to Gaussian random fields with SDD precision matrices.