# Theory of Computing Blog Aggregator

### TR14-161 | Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs | Rohit Gurjar, Rahul Arora, Ashu Gupta, Raghunath Tewari

from ECCC papers

The perfect matching problem has a randomized $NC$ algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph, ensures that it has a unique minimum weight perfect matching, with a good probability. We derandomize this lemma for $K_{3,3}$-free and $K_5$-free bipartite graphs, i.e. we give a deterministic log-space construction of such a weight assignment for these graphs. Such a construction was known previously for planar bipartite graphs. Our result implies that the perfect matching problem for $K_{3,3}$-free and $K_5$-free bipartite graphs is in $SPL$. It also gives an alternate proof for an already known result -- reachability for $K_{3,3}$-free and $K_5$-free graphs is in $UL$.

### TR14-160 | Zero-Fixing Extractors for Sub-Logarithmic Entropy | Gil Cohen, Igor Shinkar

from ECCC papers

An $(n,k)$-bit-fixing source is a distribution on $n$ bit strings, that is fixed on $n-k$ of the coordinates, and jointly uniform on the remaining $k$ bits. Explicit constructions of bit-fixing extractors by Gabizon, Raz and Shaltiel [SICOMP 2006] and Rao [CCC 2009], extract $(1-o(1)) \cdot k$ bits for $k = \mathrm{polylog}(n)$, almost matching the probabilistic argument. Intriguingly, unlike other well-studied sources of randomness, a result of Kamp and Zuckerman [SICOMP 2006] shows that, for any $k$, some small portion of the entropy in an $(n,k)$-bit-fixing source can be extracted. Although the extractor does not extract all the entropy, it does extract $(1/2 - o(1)) \cdot \log(k)$ bits. In this paper we prove that when the entropy $k$ is small enough compared to $n$, this exponential entropy-loss is unavoidable. More precisely, one cannot extract more than $\log(k)/2 + O(1)$ bits from $(n,k)$-bit-fixing sources. The remaining entropy is inaccessible, information theoretically. By the Kamp-Zuckerman construction, this negative result is tight. Our impossibility result also holds for what we call zero-fixing sources. These are bit-fixing sources where the fixed bits are set to $0$. We complement our negative result, by giving an explicit construction of an $(n,k)$-zero-fixing extractor, that outputs $\Omega(k)$ bits, even for $k = \mathrm{polyloglog}(n)$. Furthermore, we give a construction of an $(n,k)$-bit-fixing extractor, that outputs $k-O(1)$ bits, for entropy $k = (1+o(1)) \cdot \log\log{n}$, with running-time $n^{O(( \log{\log{n}})^2)}$.

### TR14-159 | Magic coins are useful for small-space quantum machines | A. C. Cem Say, Abuzer Yakaryilmaz

from ECCC papers

Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use logarithmic space, it is known that such magic coins'' give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits to the model changes the picture dramatically. For every language $L$, there exists such a two-way quantum finite automaton that recognizes a language of the same Turing degree as $L$ with bounded error in polynomial time. When used as verifiers in public-coin interactive proof systems, such automata can verify membership in all languages with bounded error, outperforming their classical counterparts, which are known to fail for the palindromes language.

### TR14-158 | Deterministic Identity Testing for Sum of Read Once ABPs | Arpita Korwar, Rohit Gurjar, Nitin Saxena, Thomas Thierauf

from ECCC papers

A read once ABP is an arithmetic branching program with each variable occurring in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity, i.e. $n^{O(\log n)}$. The motivating special case of this model is sum of constantly many set-multilinear depth-$3$ circuits. The prior results for that model were only slightly better than brute-force (i.e. exponential-time). Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration.

### TR14-157 | Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas | Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk

from ECCC papers

In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models. For depth-3 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 2\delta/3}))$. This implies a lower bound of $\exp(\tilde{\Omega}(n^{1/2}))$ for depth-3 multilinear formulas, for some explicit polynomial. For depth-4 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 4\delta/3}))$. This implies a lower bound of $\exp(\tilde{\Omega}(n^{1/4}))$ for depth-4 multilinear formulas, for some explicit polynomial. A regular formula consists of alternating layers of $+,\times$ gates, where all gates at layer $i$ have the same fan-in. We give a hitting set of size (roughly) $\exp\left(n^{1- \delta} \right)$, for regular depth-$d$ multilinear formulas of size $\exp(n^\delta)$, where $\delta = O(\frac{1}{\sqrt{5}^d})$. This result implies a lower bound of roughly $\exp(\tilde{\Omega}(n^{\frac{1}{\sqrt{5}^d}}))$ for such formulas. We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known. Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas we go straight to read-once algebraic branching programs).

### Trees that represent bandwidth

from David Eppstein

In my algorithms class today, I covered minimum spanning trees, one property of which is that they (or rather maximum spanning trees) can be used to find the bottleneck in communications bandwidth between any two vertices in a network. Suppose the network edges are labeled by bandwidth, and we compute the maximum spanning tree using these labels. Then between any two vertices the path in this tree has the maximum bandwidth possible, among all paths in the network that connect the same two vertices. (There may also be other equally good paths that aren't part of the tree.) So if you want to send all of your data on a single route in the network, and you're not worried about other people using the same links at the same time, and bandwidth is your main quality issue (a lot of ifs) then that's the best path to take. The bandwidth of the path is controlled by its weakest link, the edge on the path with the smallest bandwidth. If you want to quickly look up the bandwidth between pairs of vertices, you can do it in constant time using the nearest common ancestor in a Cartesian tree derived from the maximum spanning tree.

Ok, but if you're so concerned about bandwidth then maybe you should use a more clever routing scheme that spreads your messages across multiple paths to get even more bandwidth. This can be modeled as a network flow, and the bottleneck to getting the most bandwidth is no longer a single edge. Instead, the max-flow min-cut theorem tells you that the bottleneck takes the form of a cut: a partition of the graphs into two disjoint subsets, whose bandwidth is the sum of the bandwidths of the edges crossing the cut.

Despite all this added complexity, it turns out that the bandwidth in this sort of multi-path routing scheme can still be described by a single tree. That is, there's a tree whose vertices are the vertices of your graph (but whose edges and edge weights are no longer those of the graph) such that the bandwidth you can get from one vertex to another by routing data along multiple paths in the graph is the same as the bandwidth of the single path between the same two vertices in the tree. More, the edges of the tree can be labeled by cuts in the graph such that the weakest link in the tree path between any two vertices is labeled by the minimum cut that separates those vertices in the original graph. This tree is called the Gomory–Hu tree of the given (undirected and edge-weighted) graph. Using the same Cartesian tree ancestor technique, you can look up the bandwidth between any pair of vertices, in constant time per query.

My latest arXiv preprint, All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs (arXiv:1411.7055, with Cora Borradaile and new co-authors Amir Nayyeri and Christian Wulff-Nilsen) is on exactly these trees. For arbitrary graphs they can be found in polynomial time, but slowly, because the computation involves multiple flow computations. For planar graphs it was known how to find the Gomory–Hu tree much more quickly, in O(n log3 n) time; we shave a log off this time bound. Then, we extend this result to a larger class of graphs, the graphs of bounded genus, by showing how to slice the bounded-genus surface up (in a number of ways that's exponential in the genus) into planar pieces such that, for every pair of vertices, one of the pieces contains the minimum cut. That gives us exponentially many Gomory-Hu trees, one for each piece, but it turns out that these can all be combined into a single tree for the whole graph.

One curious difference between the planar and higher-genus graphs is that, for planar graphs, the set of cuts given by the Gomory–Hu tree also solves a different problem: it's the minimum-weight cycle basis of the dual graph. In higher-genus graphs, we don't quite have enough cuts to generate the dual cycle space (we're off by the genus) but more importantly some of the optimal cycle basis members might not be cuts. So although the new preprint also improves the time for finding cycle bases in planar graphs, making a similar improvement in the higher genus case remains open.

### Algorithms in the Ultra-Wide Word Model

Authors: Arash Farzan, Alejandro López-Ortiz, Patrick K. Nicholson, Alejandro Salinger
Abstract: The effective use of parallel computing resources to speed up algorithms in current multi-core parallel architectures remains a difficult challenge, with ease of programming playing a key role in the eventual success of various parallel architectures. In this paper we consider an alternative view of parallelism in the form of an ultra-wide word processor. We introduce the Ultra-Wide Word architecture and model, an extension of the word-RAM model that allows for constant time operations on thousands of bits in parallel. Word parallelism as exploited by the word-RAM model does not suffer from the more difficult aspects of parallel programming, namely synchronization and concurrency. For the standard word-RAM algorithms, the speedups obtained are moderate, as they are limited by the word size. We argue that a large class of word-RAM algorithms can be implemented in the Ultra-Wide Word model, obtaining speedups comparable to multi-threaded computations while keeping the simplicity of programming of the sequential RAM model. We show that this is the case by describing implementations of Ultra-Wide Word algorithms for dynamic programming and string searching. In addition, we show that the Ultra-Wide Word model can be used to implement a nonstandard memory architecture, which enables the sidestepping of lower bounds of important data structure problems such as priority queues and dynamic prefix sums. While similar ideas about operating on large words have been mentioned before in the context of multimedia processors [Thorup 2003], it is only recently that an architecture like the one we propose has become feasible and that details can be worked out.

### A Chasm Between Identity and Equivalence Testing with Conditional Queries

Authors: Jayadev Acharya, Clément L. Canonne, Gautam Kamath
Abstract: A recent model for property testing of probability distributions enables tremendous savings in the sample complexity of testing algorithms, by allowing them to condition the sampling on subsets of the domain.

In particular, Canonne et al. showed that, in this setting, testing identity of an unknown distribution $D$ (i.e., whether $D=D^\ast$ for an explicitly known $D^\ast$) can be done with a constant number of samples, independent of the support size $n$ -- in contrast to the required $\sqrt{n}$ in the standard sampling model. However, it was unclear whether the same held for the case of testing equivalence, where both distributions are unknown. Indeed, while the best known upper bound for equivalence testing is ${\rm polylog}(n)$, whether a dependence on the domain size $n$ is necessary was still open, and explicitly posed at the Bertinoro Workshop on Sublinear Algorithms. In this work, we answer the question in the positive, showing that any testing algorithm for equivalence must make $\Omega(\sqrt{\log\log n})$ queries in the conditional sampling model. Interestingly, this demonstrates an intrinsic qualitative gap between identity and equivalence testing, absent in the standard sampling model (where both problems have sampling complexity $n^{\Theta(1)}$).

Turning to another question, we strengthen a result of Ron and Tsur on support size estimation in the conditional sampling model, with an algorithm to approximate the support size of an arbitrary distribution. This result matches the previously known upper bound in the restricted case where the distribution is guaranteed to be uniform over a subset. Furthermore, we settle a related open problem of theirs, proving tight lower bounds on support size estimation with non-adaptive queries.

### Deterministic Identity Testing for Sum of Read Once ABPs

Authors: Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
Abstract: A read once ABP is an arithmetic branching program with each variable occurring in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity, i.e. $n^{O(\log n)}$. The motivating special case of this model is sum of constantly many set-multilinear depth-$3$ circuits. The prior results for that model were only slightly better than brute-force (i.e. exponential-time).

Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration.

### Bounds on the Expected Size of the Maximum Agreement Subtree

Authors: Daniel Irving Bernstein, Lam Si Tung Ho, Colby Long, Mike Steel, Katherine St. John, Seth Sullivant
Abstract: We prove polynomial upper and lower bounds on the expected size of the maximum agreement subtree of two random binary phylogenetic trees under both the uniform distribution and Yule-Harding distribution. This positively answers a question posed in earlier work. Determining tight upper and lower bounds remains an open problem.

### Coordinate-Free Quantification of Coverage in Dynamic Sensor Networks

Authors: Jennifer Gamble, Harish Chintakunta, Hamid Krim
Abstract: We present a novel set of methods for analyzing coverage properties in dynamic sensor networks. The dynamic sensor network under consideration is studied through a series of snapshots, and is represented by a sequence of simplicial complexes, built from the communication graph at each time point. A method from computational topology called zigzag persistent homology takes this sequence of simplicial complexes as input, and returns a barcode' containing the birth and death times of homological features in this sequence. We derive useful statistics from this output for analyzing time-varying coverage properties. Further, we propose a method which returns specific representative cycles for these homological features, at each point along the birth-death intervals. These representative cycles are then used to track coverage holes in the network, and obtain size estimates for individual holes at each time point. A weighted barcode, incorporating the size information, is then used as a visual and quantitative descriptor of the dynamic network coverage.

### Faster Language Edit Distance, Connection to All-pairs Shortest Paths and Related Problems

Authors: Barna Saha
Abstract: Given a context free language $L(G)$ over alphabet $\Sigma$ and a string $s \in \Sigma^*$, the language edit distance (Lan-ED) problem seeks the minimum number of edits (insertions, deletions and substitutions) required to convert $s$ into a valid member of $L(G)$. The well-known dynamic programming algorithm solves this problem in $O(n^3)$ time (ignoring grammar size) where $n$ is the string length [Aho, Peterson 1972, Myers 1985]. Despite its vast number of applications, there is no algorithm known till date that computes or approximates Lan-ED in true sub-cubic time.

In this paper we give the first such algorithm that computes Lan-ED almost optimally. For any arbitrary $\epsilon > 0$, our algorithm runs in $\tilde{O}(\frac{n^{\omega}}{poly(\epsilon)})$ time and returns an estimate within a multiplicative approximation factor of $(1+\epsilon)$, where $\omega$ is the exponent of ordinary matrix multiplication of $n$ dimensional square matrices. It also computes the edit script. Further, for all substrings of $s$, we can estimate their Lan-ED within $(1\pm \epsilon)$ factor in $\tilde{O}(\frac{n^{\omega}}{poly(\epsilon)})$ time with high probability. We also design the very first sub-cubic ($\tilde{O}(n^\omega)$) algorithm to handle arbitrary stochastic context free grammar (SCFG) parsing. SCFGs lie the foundation of statistical natural language processing, they generalize hidden Markov models, and have found widespread applications.

To complement our upper bound result, we show that exact computation of Lan-ED in true sub-cubic time will imply a truly sub-cubic algorithm for all-pairs shortest paths. This will result in a breakthrough for a large range of problems in graphs and matrices due to sub-cubic equivalence. By a known lower bound result [Lee 2002], improving upon our time bound of $O(n^\omega)$ for any nontrivial multiplicative approximation is (almost) not possible.

### Query complexity in expectation

Authors: Jedrzej Kaniewski, Troy Lee, Ronald de Wolf
Abstract: We study the query complexity of computing a function f:{0,1}^n-->R_+ in expectation. This requires the algorithm on input x to output a nonnegative random variable whose expectation equals f(x), using as few queries to the input x as possible. We exactly characterize both the randomized and the quantum query complexity by two polynomial degrees, the nonnegative literal degree and the sum-of-squares degree, respectively. We observe that the quantum complexity can be unboundedly smaller than the classical complexity for some functions, but can be at most polynomially smaller for functions with range {0,1}.

These query complexities relate to (and are motivated by) the extension complexity of polytopes. The linear extension complexity of a polytope is characterized by the randomized communication complexity of computing its slack matrix in expectation, and the semidefinite (psd) extension complexity is characterized by the analogous quantum model. Since query complexity can be used to upper bound communication complexity of related functions, we can derive some upper bounds on psd extension complexity by constructing efficient quantum query algorithms. As an example we give an exponentially-close entrywise approximation of the slack matrix of the perfect matching polytope with psd-rank only 2^{n^{1/2+epsilon}}. Finally, we show there is a precise sense in which randomized/quantum query complexity in expectation corresponds to the Sherali-Adams and Lasserre hierarchies, respectively.

### $1$-String $B_2$-VPG Representation of Planar Graphs

Authors: Therese Biedl, Martin Derka
Abstract: In this paper, we prove that every planar graph has a 1-string $B_2$-VPG representation---a string representation using paths in a rectangular grid that contain at most two bends. Furthermore, two paths representing vertices $u,v$ intersect precisely once whenever there is an edge between $u$ and $v$.

### Partial-Matching and Hausdorff RMS Distance Under Translation: Combinatorics and Algorithms

Authors: Rinat Ben-Avraham, Matthias Henze, Rafel Jaume, Balázs Keszegh, Orit E. Raz, Micha Sharir, Igor Tubis
Abstract: We consider the RMS distance (sum of squared distances between pairs of points) under translation between two point sets in the plane, in two different setups. In the partial-matching setup, each point in the smaller set is matched to a distinct point in the bigger set. Although the problem is not known to be polynomial, we establish several structural properties of the underlying subdivision of the plane and derive improved bounds on its complexity. These results lead to the best known algorithm for finding a translation for which the partial-matching RMS distance between the point sets is minimized. In addition, we show how to compute a local minimum of the partial-matching RMS distance under translation, in polynomial time. In the Hausdorff setup, each point is paired to its nearest neighbor in the other set. We develop algorithms for finding a local minimum of the Hausdorff RMS distance in nearly linear time on the line, and in nearly quadratic time in the plane. These improve substantially the worst-case behavior of the popular ICP heuristics for solving this problem.

### Efficient SimRank Computation via Linearization

Authors: Takanori Maehara, Mitsuru Kusumoto, Ken-ichi Kawarabayashi
Abstract: SimRank, proposed by Jeh and Widom, provides a good similarity measure that has been successfully used in numerous applications. While there are many algorithms proposed for computing SimRank, their computational costs are very high. In this paper, we propose a new computational technique, "SimRank linearization," for computing SimRank, which converts the SimRank problem to a linear equation problem. By using this technique, we can solve many SimRank problems, such as single-pair compuation, single-source computation, all-pairs computation, top k searching, and similarity join problems, efficiently.

### Hashing for statistics over k-partitions

Authors: Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup
Abstract: In this paper we propose a hash function for $k$-partitioning a set into bins so that we get good concentration bounds when combining statistics from different bins.

To understand this point, suppose we have a fully random hash function applied to a set $X$ of red and blue balls. We want to estimate the fraction $f$ of red balls. The idea of MinHash is to sample the ball with the smallest hash value. This sample is uniformly random and is red with probability $f$. The standard method is to repeat the experiment $k$ times with independent hash functions to reduce variance.

Consider the alternative experiment using a single hash function, where we use some bits of the hash value to partition $X$ into $k$ bins, and then use the remaining bits as a local hash value. We pick the ball with the smallest hash value in each bin.

The big difference between the two schemes is that the second one runs $\Omega(k)$ times faster. In the first experiment, each ball participated in $k$ independent experiments, but in the second one with $k$-partitions, each ball picks its bin, and then only participates in the local experiment for that bin. Thus, essentially, we get $k$ experiments for the price of one. However, no realistic hash function is known to give the desired concentration bounds because the contents of different bins may be too correlated even if the marginal distribution for a single bin is random.

Here, we present and analyze a hash function showing that it does yields statistics similar to that of a fully random hash function when $k$-partitioning a set into bins. In this process we also give more insight into simple tabulation and show new results regarding the power of choice and moment estimation.

### The robust single machine scheduling problem with uncertain release and processing times

Authors: Nitish Umang, Alan L. Erera, Michel Bierlaire
Abstract: In this work, we study the single machine scheduling problem with uncertain release times and processing times of jobs. We adopt a robust scheduling approach, in which the measure of robustness to be minimized for a given sequence of jobs is the worst-case objective function value from the set of all possible realizations of release and processing times. The objective function value is the total flow time of all jobs. We discuss some important properties of robust schedules for zero and non-zero release times, and illustrate the added complexity in robust scheduling given non-zero release times. We propose heuristics based on variable neighborhood search and iterated local search to solve the problem and generate robust schedules. The algorithms are tested and their solution performance is compared with optimal solutions or lower bounds through numerical experiments based on synthetic data.

### All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

Authors: Glencora Borradaile, David Eppstein, Amir Nayyeri, Christian Wulff-Nilsen
Abstract: For an undirected $n$-vertex graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a minimum $st$-cut in $G$? We solve this problem in preprocessing time $O(n\log^3 n)$ for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space $O(n)$ that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is $2^{O(g^2)}$.

### An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets

Authors: Venkatesan Guruswami, Ameya Velingker
Abstract: We prove a lower estimate on the increase in entropy when two copies of a conditional random variable $X | Y$, with $X$ supported on $\mathbb{Z}_q=\{0,1,\dots,q-1\}$ for prime $q$, are summed modulo $q$. Specifically, given two i.i.d copies $(X_1,Y_1)$ and $(X_2,Y_2)$ of a pair of random variables $(X,Y)$, with $X$ taking values in $\mathbb{Z}_q$, we show $H(X_1 + X_2 \mid Y_1, Y_2) - H(X|Y) \ge \alpha(q) \cdot H(X|Y) (1-H(X|Y))$ for some $\alpha(q) > 0$, where $H(\cdot)$ is the normalized (by factor $\log_2 q$) entropy. Our motivation is an effective analysis of the finite-length behavior of polar codes, and the assumption of $q$ being prime is necessary. For $X$ supported on infinite groups without a finite subgroup and no conditioning, a sumset inequality for the absolute increase in (unnormalized) entropy was shown by Tao (2010).

We use our sumset inequality to analyze Ar{\i}kan's construction of polar codes and prove that for any $q$-ary source $X$, where $q$ is any fixed prime, and any $\epsilon > 0$, polar codes allow {\em efficient} data compression of $N$ i.i.d. copies of $X$ into $(H(X)+\epsilon)N$ $q$-ary symbols, as soon as $N$ is polynomially large in $1/\epsilon$. We can get capacity-achieving source codes with similar guarantees for composite alphabets, by factoring $q$ into primes and combining different polar codes for each prime in factorization.

A consequence of our result for noisy channel coding is that for {\em all} discrete memoryless channels, there are explicit codes enabling reliable communication within $\epsilon > 0$ of the symmetric Shannon capacity for a block length and decoding complexity bounded by a polynomial in $1/\epsilon$. The result was previously shown for the special case of binary input channels (Guruswami-Xia '13 and Hassani-Alishahi-Urbanke '13), and this work extends the result to channels over any alphabet.

### Cornell CS at 50

from Richard Lipton

Plus a long-promised discussion on diagonalization

 TRUST security source

Dexter Kozen has been on the faculty of computer science at Cornell for almost 30 of the department’s 50 years. He first came to Cornell 40 years ago as a graduate student and finished a PhD under Juris Hartmanis in just over 2 years. He was named to the Joseph Newton Pew, Jr., professorship 20 years ago, and celebrated his 60th birthday in 2012. Besides many research achievements he co-authored an award-winning book on Dynamic Logic.

Today we salute the 50th anniversary of Cornell’s department and keep a promise we made 5 years ago to talk about a diagonalization theorem by Dexter. It yields what may be an interesting finite puzzle.

The 50th anniversary symposium earlier this fall was a great occasion; I wish I’d been able to drive over for it. There were two days of talks by Cornell faculty and alumni. It coincided with the department moving into a new building, Gates Hall, named for—who else?—Bill and Melinda Gates as principal donors. Bill Gates came for the dedication and engaged Cornell president David Skorton in a one-hour conversation on how to serve students best.

I have fond memories of my time at Cornell in 1986–7 and 1988–9 split with time at Oxford. I was given a home in the department though my postdoc came from Cornell’s Mathematical Sciences Institute, and I was treated incredibly well. It was a great personal as well as professional time for me. When I last visited two years ago, Gates Hall was just going up across the street, beyond the left-field fence of the baseball field I viewed from my office window in the 1980s. Dick and I wish them the best for the next 50 years.

 “Innovative Departments” source

## 1982

Dexter is on sabbatical in the Netherlands and Denmark this academic year. I first met him in Denmark, at ICALP 1982 in Aarhus. We took part in a local tradition of performing musical numbers at the conference banquet. He had a band called the “Steamin’ Weenies” when I was at Cornell. He has kept his music up with bands of various names through the “Katatonics,” which performed in a Superstorm Sandy benefit two years ago at Ithaca’s club “The Gates” (not named for—who else?—Bill and Melinda Gates).

It is hard to believe, but summer 1982 is three-fourths of the way back to Steve Cook’s 1971 paper which put the ${\mathsf{P}}$ versus ${\mathsf{NP}}$ question on everyone’s map. Back then we knew it was hard but there was more optimism. I have told the story of sharing a train car with Mike Sipser on the way to that conference and hearing Mike’s confidence in being able to solve the question.

The aspect that captivated me that summer was formal logic issues involved in separating complexity classes. They can be approached in two ways: as sets of languages and as subsets of machines. The former I tried to conceptualize as a topological space. As with the Zariski topology of algebraic sets employed by Alexander Grothendieck, it satisfies only the ${T_1}$ axiom and so is not a Hausdorff space. The latter view was developed by Dexter’s 1979 paper, “Indexings of Subrecursive Classes.”

Dexter’s paper cut to the chase away from logic or topology by treating the problem as one about programming systems, i.e., recursive enumerations of machines that have nice properties like efficient substitution and composition. He showed a tradeoff between power and niceness of what one can do with them. The niftiest theorem, in section 7 of his paper, shows that if you insist on representing ${\mathsf{P}}$ by machines that mark ${n^k}$ cells on a tape as a polynomial time clock, and insist on a composition operator giving only a constant-factor overhead in program size, then both universal simulation and diagonalization need more than polynomial space. Thus such representations of ${\mathsf{P}}$ will not support a proof of ${\mathsf{P}}$ different from ${\mathsf{PSPACE}}$, let alone ${\mathsf{NP}}$. But in the previous section he gave a theorem showing that if you give up all efficient closure properties, then you can in principle achieve any diagonalization you like.

## Kozen’s Theorem

The only property of the class ${\mathsf{P}}$ that is used by the theorem is that it is closed under finite differences: if ${L}$ is different from a language ${B \in \mathsf{P}}$ by a finite set, meaning that the symmetric difference ${L \;\Delta\; B = (L \setminus B) \cup (B \setminus L)}$ is finite, then ${L}$ is in ${\mathsf{P}}$. And of course it uses that ${\mathsf{P}}$ has an effective programming system, which is what distinguished bounded closed sets in my topological view.

Theorem 1 Let ${[P_u]_{u=1}^{\infty}}$ be any enumeration of ${\mathsf{P}}$ by machines, and let ${A}$ be any language outside of ${\mathsf{P}}$. Then we can define a function ${g : \mathbb{N} \longrightarrow \mathbb{N}}$ such that

1. ${\mathsf{P} = \{L(P_{g(u)}) : u \in \mathbb{N}\}}$, and

2. ${A = D_g}$ where we define ${D_g = \{u : u \notin L(P_{g(u)})\}}$.

Moreover, any reasonable formal system that can prove ${A \notin \mathsf{P}}$ can prove statements 1 and 2. Indeed, we can make ${g}$ a permutation, so that the new indexing involves the same machines as the original, only scrambled. In the case ${A = \mathsf{SAT}}$, this yields his prose conclusion:

If ${\mathsf{P \neq NP}}$ is provable at all, then it is provable by diagonalization.

As he was quick to add, this doesn’t say that the mere fact of ${\mathsf{P \neq NP}}$ enables diagonalization, only that working by diagonalization does not impose any additional burden on a reasonable formal system.

Proof: We define ${g(u)}$ in stages. At each stage we have “marked” the values ${g(t)}$ for ${t < u}$. At stage ${u}$, take ${v}$ to be the least unmarked value such that

$\displaystyle u \in (L(P_v) \;\Delta\; A)$

and define ${g(u) = v}$. This also marks ${v}$. A suitable ${v}$ always exists since infinitely many languages in ${\mathsf{P}}$ include ${u}$, which handles the case ${u \notin A}$, and infinitely many exclude ${u}$, so there’s always a ${v}$ when ${u \in A}$ too. Also clearly ${g}$ is one-to-one since we mark each value. To see that ${g}$ is onto, let ${v}$ be the least unmarked value at any stage ${u}$. Since ${A}$ and ${L(P_v)}$ differ by an infinite set, there will always be a ${u' \geq u}$ in the symmetric difference, and the algorithm will set ${g(u') = v}$ for the least such ${u'}$. $\Box$

## Interpretations

The proof works even if ${A}$ is undecidable—we just get that ${g = g_A}$ is uncomputable—and there are uncountably many ${g}$‘s to go with uncountably many ${A}$‘s. When ${A}$ is computable the ${g_A}$ in the algorithm is computable, and if the indexing includes many copies of machines accepting ${\emptyset}$ or ${\Sigma^*}$ then we can get ${g(u) < 3u}$ or lower.

The inverse of ${g_A}$, that is, the mapping ${e_A(v) = u}$, however, may have explosive growth for infinitely many ${v}$, depending on how sparse the symmetric difference of ${A}$ with some languages in ${\mathsf{P}}$ is. Still, if the statement ${A \notin \mathsf{P}}$ is provable in a given formal system, then the inverse is provably total, so the diagonalization can be verified. Another way of putting this is that the formal system is able to verify that every language in ${\mathsf{P}}$—that is, every ${L(P_v)}$, is eventually enumerated, so the formal system can tell that the class being diagonalized against is all of ${\mathsf{P}}$.

The ease of the proof and its relation to oracle results contributed to controversy over how to interpret it. I’ve mostly felt that the logical “horse” was being put behind or at best alongside the “cart” of combinatorial proof methods. Recently I’ve appreciated how the proof focuses the question on how large your idea of “${\mathsf{P}}$” is rather than how hard ${\mathsf{SAT}}$ is, which was a key issue in the attempted ${\mathsf{P \neq NP}}$ proof by Vinay Deolalikar. The oracle result showing ${\mathsf{P}^B = \mathsf{NP}^B}$ for some computable languages ${B}$ (any ${\mathsf{PSPACE}}$-complete language will do) was supposed to argue that diagonalization against the class ${\mathsf{P}}$ had no special power as a tool for ${\mathsf{P \neq NP}}$.

The proof relativizes by taking ${[P_u]}$ to be an ensemble of polynomial-time oracle Turing machines giving ${\mathsf{P}^B = \{L(P_u^B)\}}$ for each oracle set ${B}$, and by taking a fixed oracle TM ${N}$ such that ${L(N^B)}$ is ${\mathsf{NP}^B}$-complete for each ${B}$. We get a fixed oracle transducer ${T}$ such that ${T^B}$ executes the algorithm for ${A^B = L(N^B)}$. Whenever ${\mathsf{P}^B \neq \mathsf{NP}^B}$ it computes a total function ${g_A^B}$ whose diagonal is ${A^B}$. If you think of “${g_A^B}$” as “${g_A}$ relativized to ${B}$” then this seems like a recipe for contradiction if the unrelativized ${g_A}$ is total and ${\mathsf{P}^B = \mathsf{NP}^B}$. But what happens when ${\mathsf{P}^B = \mathsf{NP}^B}$ is just that ${T^B}$ computes an undefined function—indeed it doesn’t halt. To make an algebraic analogy, ${g_A^B}$ should be parsed as ${(g^B)_A}$ not ${(g_A)^B}$, so “the diagram does not commute” and there is no problem.

## Variations

I came back to Dexter’s theorem this fall term while re-thinking how best to introduce diagonalization in an undergrad or grad theory course. The classical way is

$\displaystyle D = \{e : e \notin L(M_e)\},$

where ${e}$ is the “Gödel Number” of the machine ${M_e}$. My own usual style is to identify a machine or program with its code as a string, thus writing

$\displaystyle D = \{M : M \notin L(M)\}.$

This removes any need to talk about the correspondence between strings and numbers, Gödel or any kind of numbers. However, styling this via programming raises questions such as whether “${M}$” means the source or compiled code, and does it matter how they differ?

Recently I’ve preferred to think of ${M}$ as an object, indeed analogizing components ${(Q,\Sigma,\delta,\dots)}$ to fields of a class. Then “${e}$” re-appears as an encoding of the object by a (number or) string. We define:

$\displaystyle D^e = \{e(M): e(M) \notin L(M)\}.$

Now it doesn’t matter if we say ${e(M)}$ is the source code or the compiled executable, and it can be anything—we can downplay the “self-reference” aspect if we wish. The encoding function need not be 1-to-1, provided it is “extensional” in the sense that

$\displaystyle e(M) = e(M') \implies L(M) = L(M').$

We still get the diagonal contradiction: if ${D^e = L(M)}$, then ${e(M) \notin L(M) \implies e(M) \in D^e}$ contradicting ${D^e = L(M)}$. And ${e(M) \in L(M) \implies e(M) \in D^e}$, which implies that there is some ${M'}$ such that ${e(M') = e(M) \wedge e(M') \notin L(M')}$, but by extensionality we have ${L(M') = L(M)}$ and again that is a contradiction. (Well, you don’t have to tell students this more-complicated proof—just say that ${e}$ is 1-to-1 and it’s just as quick as the usual diagonal proof.)

Returning to Dexter’s diagonal set ${D_g = \{u: u \notin L(M_{g(u)})}$, we see it is the same as ${D^e}$ with ${e = g^{-1}}$. Looking at ${D_g}$ by itself, much as we can relax ${e}$ being 1-to-1, we can relax ${g}$ being onto, so long as ${g}$ is “functionally onto” the languages, in keeping with statement 1 of Theorem 1. Indeed, when the programming system ${[P_u]}$ repeats each language infinitely often, we could redo the proof to make ${g}$ an increasing function.

We can abstract this by considering any function ${F}$ from a set ${S}$ into its power set ${P(S)}$ and functions ${e,g}$ on ${S}$. It is interesting to try to formalize exactly when ${D^e = D_g}$, that is,

$\displaystyle \{e(x) : e(x) \notin F(x)\} = \{u: u \notin F(g(u))\},$

with ${e}$ being extensional with respect to ${F}$ and ${F\circ g}$ being onto the image of ${F}$. One interesting requirement is that when ${e}$ is not onto ${S}$, ${Ran(F)}$ must cover ${S \setminus Ran(e)}$, that is:

$\displaystyle (\forall z \in S)(\exists x \in S)[z = e(x) \vee z \in F(x)].$

Again I wonder if there is a useful analogy in abstract algebra or category theory for this situation. Given the function ${e}$ and ${y \in Ran(e)}$, we can define ${g(y) = x}$ for some choice of ${x}$ such that ${e(x) = y}$. For other ${y}$ we can put ${g(y) = z}$ for any ${z}$ such that ${y \in F(z)}$. Given the function ${g}$, we can define ${e(x)}$ for any ${x}$ by taking ${y}$ such that ${F(x) = F(g(y))}$, since ${g}$ is functionally onto ${Ran(F)}$, and define ${e(x) = y}$.

## A Finite Puzzle

The abstraction nicely gives a concrete puzzle when ${S}$ is a finite set. Then we don’t have Dexter’s property of ${Ran(F)}$ being closed under finite differences, but we can still ask:

Is every unindexed subset a diagonal? That is, for all ${A \subseteq S}$ with ${A \notin Ran(F)}$, does there exist ${g: S \longrightarrow S}$ such that ${A = D_g(F)}$?

Equivalently, does there exist ${e: S \longrightarrow S}$ such that ${A = D^e(F)}$? If ${F}$ is 1-to-1, then ${g}$ must be onto, which means ${g}$ must be a permutation since ${S}$ is finite, and likewise ${e}$ must be its inverse. There are interesting cases where ${F}$ is not 1-to-1, in which the extra latitude for ${g}$ and ${e}$ becomes important.

For example, let ${S = \{a,b,c\}}$ and let ${F(a) = \{a,b\}}$, ${F(b) = \{a\}}$, and ${F(c) = \{b,c\}}$. Then ${F}$ is 1-to-1, so we have six permutations ${g}$ to consider. They become the six columns after the first in the following table:

$\displaystyle \begin{array}{c|cccccc} \hline a & a,b & a,b & a & a & b,c & b,c\\ b & a & b,c & a,b & b,c & a & a,b\\ c & b,c & a & b,c & a,b & a,b & a\\ \hline D_g & \{b\} & \{c\} & \emptyset & \{c\} & \{a,b,c\} & \{a,c\} \end{array}$

Every subset not in the range appears; curiously ${\{c\}}$ appears twice. If instead we define ${F(a) = \{a\}}$ only, then only three permutations are relevant, but having ${F(a) = F(b)}$ gives us three other functions ${g}$ to consider:

$\displaystyle \begin{array}{c|cccccc} \hline a & a & a & b,c & a & b,c & b,c\\ b & a & b,c & a & b,c & a & b,c\\ c & b,c & a & a & b,c & b,c & a\\ \hline D_g & \{b\} & \{c\} & \{a,b,c\} & \emptyset & \{a,b\} & \{a,c\} \end{array}$

Once again we have all eight subsets between the range and the diagonals, this time with no repetition.

Which functions ${F}$ have this “pan-diagonal” property? If some element ${a \in S}$ belongs to every set ${F(x)}$ then we can never get ${a}$ into any diagonal, so except for some small-${S}$ cases the answer is ‘no’ for such ${F}$. Note that the complementary function ${F'(x) = S \setminus F(x)}$ gives equivalent results by duality. Hence the answer is also generally ‘no’ when some element is excluded from all subsets ${F(x)}$. This extends to say that if some ${k}$ elements are collectively included in ${k-1}$ or fewer subsets, and ${F}$ is one-to-one, then it is impossible to get ${\emptyset}$ as a diagonal, so the answer is ‘no’ unless ${\emptyset}$ is already part of the range. Note, however, that our second example shows that success is still possible if ${F}$ is not 1-to-1.

Is there an easily-stated criterion for ${F}$ to be pan-diagonal? Or is ${\mathsf{NP}}$-hardness lurking about? That is the puzzle. One can also pose it for infinite ${S}$, when the range of ${F}$ is not closed under finite differences.

## Open Problems

How powerful is diagonalization? Does the puzzle have a simple answer?

We also wish everyone a Happy Thanksgiving.

by KWRegan at November 26, 2014 11:00 PM UTC

### TR14-156 | A Chasm Between Identity and Equivalence Testing with Conditional Queries | Jayadev Acharya, Clement Canonne, Gautam Kamath

from ECCC papers

A recent model for property testing of probability distributions enables tremendous savings in the sample complexity of testing algorithms, by allowing them to condition the sampling on subsets of the domain. In particular, Canonne et al. showed that, in this setting, testing identity of an unknown distribution $D$ (i.e., whether $D=D^\ast$ for an explicitly known $D^\ast$) can be done with a constant number of samples, independent of the support size $n$ -- in contrast to the required $\sqrt{n}$ in the standard sampling model. However, it was unclear whether the same held for the case of testing equivalence, where both distributions are unknown. Indeed, while the best known upper bound for equivalence testing is ${\rm polylog}(n)$, whether a dependence on the domain size $n$ is necessary was still open, and explicitly posed at the Bertinoro Workshop on Sublinear Algorithms. In this work, we answer the question in the positive, showing that any testing algorithm for equivalence must make $\Omega(\sqrt{\log\log n})$ queries in the conditional sampling model. Interestingly, this demonstrates an intrinsic qualitative gap between identity and equivalence testing, absent in the standard sampling model (where both problems have sampling complexity $n^{\Theta(1)}$). Turning to another question, we strengthen a result of Ron and Tsur on support size estimation in the conditional sampling model, with an algorithm to approximate the support size of an arbitrary distribution. This result matches the previously known upper bound in the restricted case where the distribution is guaranteed to be uniform over a subset. Furthermore, we settle a related open problem of theirs, proving tight lower bounds on support size estimation with non-adaptive queries.

### Kernelization Algorithms for Packing Problems Allowing Overlaps

Authors: Henning Fernau, Alejandro López-Ortiz, Jazmín Romero
Abstract: We consider the problem of discovering overlapping communities in networks which we model as generalizations of the Set and Graph Packing problems with overlap.

As usual for Set Packing problems we seek a collection $\mathcal{S}$ consisting of at least $k$ sets subject to certain disjointness restrictions. In a Set Packing with $t$-Membership, each element of $\mathcal{U}$ belongs to at most $t$ sets while in a Set Packing with $t$-Overlap each pair of sets overlaps in at most $t$ elements. For both problems, each set of $\mathcal{S}$ has at most $r$ elements, and $t$ and $r$ are constants.

Similarly, both of our graph packing problems seek a collection of at least $k$ subgraphs in a graph $G$ each isomorphic to a graph $H \in \mathcal{H}$. In an $\mathcal{H}$-Packing with $t$-Membership, each vertex of $G$ belongs to at most $t$ subgraphs while in an $\mathcal{H}$-Packing with $t$-Overlap each pair of subgraphs overlaps in at most $t$ vertices. For both problems, each member of $\mathcal{H}$ has at most $r$ vertices, and $t$ and $r$ are constants.

We provide NP-Completeness results for all of our packing problems. Given that, we reduce the Set Packing with $t$-Overlap to an $O(r^r k^{r-t-1})$ problem kernel while we achieve an $O(r^r k^{r-1})$ problem kernel for the Set Packing with $t$-Membership. In addition, we reduce the $\mathcal{H}$-Packing with $t$-Membership and its induced version to an $O(r^r k^{r-1})$ kernel. Moreover, we give an $O(r^{2r^2} k^{{r^2}-1})$ kernel for its edge version. On the other hand, we achieve an $O(r^r k^{r-t-1})$ kernel for the $\mathcal{H}$-Packing with $t$-Overlap and its induced version while we provide an $O(r^{2r^2} k^{r^2-t-1})$ kernel for its edge version. Our kernel results match the best kernel for Set and Graph Packing.

### Efficiently listing bounded length st-paths

Authors: Romeo Rizzi, Gustavo Sacomoto, Marie-France Sagot
Abstract: The problem of listing the $K$ shortest simple (loopless) $st$-paths in a graph has been studied since the early 1960s. For a non-negatively weighted graph with $n$ vertices and $m$ edges, the most efficient solution is an $O(K(mn + n^2 \log n))$ algorithm for directed graphs by Yen and Lawler [Management Science, 1971 and 1972], and an $O(K(m+n \log n))$ algorithm for the undirected version by Katoh et al. [Networks, 1982], both using $O(Kn + m)$ space. In this work, we consider a different parameterization for this problem: instead of bounding the number of $st$-paths output, we bound their length. For the bounded length parameterization, we propose new non-trivial algorithms matching the time complexity of the classic algorithms but using only $O(m+n)$ space. Moreover, we provide a unified framework such that the solutions to both parameterizations -- the classic $K$-shortest and the new length-bounded paths -- can be seen as two different traversals of a same tree, a Dijkstra-like and a DFS-like traversal, respectively.

### Approximately counting locally-optimal structures

Authors: Leslie Ann Goldberg, Rob Gysel, John Lapinskas
Abstract: A locally-optimal structure is a combinatorial structure such as a maximal independent set that cannot be improved by certain (greedy) local moves, even though it may not be globally optimal. It is trivial to construct an independent set in a graph. It is easy to (greedily) construct a maximal independent set. However, it is NP-hard to construct a globally-optimal (maximum) independent set. In general, constructing a locally-optimal structure is somewhat more difficult than constructing an arbitrary structure, and constructing a globally-optimal structure is more difficult than constructing a locally-optimal structure. The same situation arises with listing. The differences between the problems become obscured when we move from listing to counting because nearly everything is #P-complete. However, we highlight an interesting phenomenon that arises in approximate counting, where the situation is apparently reversed. Specifically, we show that counting maximal independent sets is complete for #P with respect to approximation-preserving reductions, whereas counting all independent sets, or counting maximum independent sets is complete for an apparently smaller class, $\mathrm{\#RH}\Pi_1$ which has a prominent role in the complexity of approximate counting. Motivated by the difficulty of approximately counting maximal independent sets in bipartite graphs, we also study the problem of approximately counting other locally-optimal structures that arise in algorithmic applications, particularly problems involving minimal separators and minimal edge separators. Minimal separators have applications via fixed-parameter-tractable algorithms for constructing triangulations and phylogenetic trees. Although exact (exponential-time) algorithms exist for listing these structures, we show that the counting problems are #P-complete with respect to both exact and approximation-preserving reductions.

### Improved Algorithmic Results for Unsplittable Stable Allocation Problems

Authors: Ágnes Cseh, Brian C. Dean
Abstract: The stable allocation problem is a many-to-many generalization of the well-known stable marriage problem, where we seek a bipartite assignment between, say, jobs (of varying sizes) and machines (of varying capacities) that is "stable" based on a set of underlying preference lists submitted by the jobs and machines. We study a natural "unsplittable" variant of this problem, where each assigned job must be fully assigned to a single machine. Such unsplittable bipartite assignment problems generally tend to be NP-hard, including previously-proposed variants of the unsplittable stable allocation problem. Our main result is to show that under an alternative model of stability, the unsplittable stable allocation problem becomes solvable in polynomial time; although this model is less likely to admit feasible solutions than the model proposed iby McDermid and Manlove, we show that in the event there is no feasible solution, our approach computes a solution of minimal total congestion (overfilling of all machines collectively beyond their capacities). We also describe a technique for rounding the solution of a stable allocation problem to produce "relaxed" unsplit solutions that are only mildly infeasible, where each machine is overcongested by at most a single job.

### Discretization of Planar Geometric Cover Problems

Authors: Dae-Sung Jang, Han-Lim Choi
Abstract: We consider discretization of the 'geometric cover problem' in the plane: Given a set $P$ of $n$ points in the plane and a compact planar object $T_0$, find a minimum cardinality collection of planar translates of $T_0$ such that the union of the translates in the collection contains all the points in $P$. We show that the geometric cover problem can be converted to a form of the geometric set cover, which has a given finite-size collection of translates rather than the infinite continuous solution space of the former. We propose a reduced finite solution space that consists of distinct canonical translates and present polynomial algorithms to find the reduce solution space for disks, convex/non-convex polygons (including holes), and planar objects consisting of finite Jordan curves.

### Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets

Authors: Katharina Huber, Leo van Iersel, Vincent Moulton, Celine Scornavacca, Taoyang Wu
Abstract: Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set $\mathcal{T}$ of binary binets or trinets over a set $X$ of taxa, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an $O(3^{|X|} poly(|X|))$ time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.

### The square root rank of the correlation polytope is exponential

Authors: Troy Lee, Zhaohui Wei
Abstract: The square root rank of a nonnegative matrix $A$ is the minimum rank of a matrix $B$ such that $A=B \circ B$, where $\circ$ denotes entrywise product. We show that the square root rank of the slack matrix of the correlation polytope is exponential. Our main technique is a way to lower bound the rank of certain matrices under arbitrary sign changes of the entries using properties of the roots of polynomials in number fields. The square root rank is an upper bound on the positive semidefinite rank of a matrix, and corresponds the special case where all matrices in the factorization are rank-one.

### Counting cliques and clique covers in random graphs

Authors: Kashyap Dixit, Martin Fürer
Abstract: We study the problem of counting the number of \emph{isomorphic} copies of a given {\em template} graph, say $H$, in the input {\em base} graph, say $G$. In general, this is (provably) very hard to solve efficiently. So, a lot of work has gone into designing efficient {\em approximation schemes}, especially, when $H$ is a perfect matching.

In this work, we present schemes to count $k$-cliques and $k$-clique covers. Our embedding problems are \emph{almost} always approximable. The decision versions of these problems are fundamental and are well studied. Both of these problems are NP-hard. In particular, the {\em $k$-Clique Cover} problem is NP-hard for every $k\ge 3$.

Here, we present {\em fully polynomial time randomized approximation schemes} (fpras) to count $k$-cliques when $k=O(\sqrt{\log n})$ and $k$-clique covers when $k$ is a constant. Our work partially resolves an open problem in [Frieze and McDiarmid (1997)], where they ask whether there exists a fpras for counting $k$-cliques in random graphs. As an aside, we also obtain an alternate derivation of the closed form expression for the $k$-th moment of a binomial random variable. Here, we use the equalities that we derive from binomial theorem. The previous derivation [Knoblauch (2008)] was based on the moment generating function of a binomial random variable.

### Pattern overlap implies runaway growth in hierarchical tile systems

Authors: Ho-Lin Chen, David Doty, Ján Maňuch, Arash Rafiey, Ladislav Stacho
Abstract: We show that in the hierarchical tile assembly model, if there is a producible assembly that overlaps a nontrivial translation of itself consistently (i.e., the pattern of tile types in the overlap region is identical in both translations), then arbitrarily large assemblies are producible. The significance of this result is that tile systems intended to controllably produce finite structures must avoid pattern repetition in their producible assemblies that would lead to such overlap. This answers an open question of Chen and Doty (SODA 2012), who showed that so-called "partial-order" systems producing a unique finite assembly *and" avoiding such overlaps must require time linear in the assembly diameter. An application of our main result is that any system producing a unique finite assembly is automatically guaranteed to avoid such overlaps, simplifying the hypothesis of Chen and Doty's main theorem.

### Deletion codes in the high-noise and high-rate regimes

Authors: Venkatesan Guruswami, Carol Wang
Abstract: The noise model of deletions poses significant challenges in coding theory, with basic questions like the capacity of the binary deletion channel still being open. In this paper, we study the harder model of worst-case deletions, with a focus on constructing efficiently decodable codes for the two extreme regimes of high-noise and high-rate. Specifically, we construct polynomial-time decodable codes with the following trade-offs (for any eps > 0):

(1) Codes that can correct a fraction 1-eps of deletions with rate poly(eps) over an alphabet of size poly(1/eps);

(2) Binary codes of rate 1-O~(sqrt(eps)) that can correct a fraction eps of deletions; and

(3) Binary codes that can be list decoded from a fraction (1/2-eps) of deletions with rate poly(eps)

Our work is the first to achieve the qualitative goals of correcting a deletion fraction approaching 1 over bounded alphabets, and correcting a constant fraction of bit deletions with rate aproaching 1. The above results bring our understanding of deletion code constructions in these regimes to a similar level as worst-case errors.

### Lens of Computation on the Sciences

from Scott Aaronson

This weekend, the Institute for Advanced Study in Princeton hosted a workshop on the “Lens of Computation in the Sciences,” which was organized by Avi Wigderson, and was meant to showcase theoretical computer science’s imperialistic ambitions to transform every other field.  I was proud to speak at the workshop, representing CS theory’s designs on physics.  But videos of all four of the talks are now available, and all are worth checking out:

Unfortunately, the videos were slow to buffer when I last tried it.  While you’re waiting, you could also check my PowerPoint slides, though they overlap considerably with my previous talks.  (As always, if you can’t read PowerPoint, then go ask another reader of this blog to convert the file into a format you like.)

Thanks so much to Avi, and everyone else at IAS, for organizing an awesome workshop!

### Differential Privacy Workshop in London

from Aaron Roth

There will be a differential privacy workshop in London in April, accepting submissions soon. If you have something you are working on, consider submitting here. Some highlights:

-- Although the workshop will not have proceedings (so you can as usual submit a talk and still submit it to a conference of your choosing), exceptional submissions will be invited to a special issue of the Journal of Privacy and Confidentiality.

-- The PC is pretty inter-disciplinary. This is certainly not just a Theory-A workshop. Work on privacy in all areas is on topic.

-- You get to hear Jon Ullman give a (presumably excellent) talk.

CALL FOR PAPERSTPDP 2015First workshop on the Theory and Practice of Differential Privacy18th April 2015, London, UKAffiliated to ETAPShttp://tpdp.computing.dundee.ac.ukDifferential privacy is a promising approach to the privacy-preservingrelease of data: it offers a strong guaranteed bound on the increasein harm that a user incurs as a result of participating in adifferentially private data analysis.Researchers in differential privacy come from several area of computerscience as algorithms, programming languages, security, databases,machine learning, as well as from several areas of statistics and dataanalysis. The workshop is intended to be an occasion for researchersfrom these different research areas to discuss the recent developmentsin the theory and practice of differential privacy.**Submissions**The overall goal of TPDP is to stimulate the discussion on therelevance of differentially private data analyses in practice. Forthis reason, we seek contributions from different research areas ofcomputer science and statistics.Authors are invited to submit a short abstract (4-5 pages maximum) oftheir work by January 23, 2015. Abstracts must be written in Englishand be submitted as a single PDF file at the EasyChair page for TPDP:https://easychair.org/conferences/?conf=3Dtpdp2015Submissions will be judged on originality, relevance, interest andclarity. Submission should describe novel works or works that havealready appeared elsewhere but that can stimulate the discussionbetween the different communities. Accepted abstracts willbe presented at the workshop.The workshop will not have formal proceedings, but we plan to have aspecial issue of the Journal of Privacy and Confidentiality devoted toTPDP. Authors presenting valuable contributions at the workshop willbe invited to submit a journal version of their work right after theworkshop.**Important Dates**-January 23, 2015 - Abstract Submission-February 10, 2015 - Notification-February 14, 2015 - Deadline early registration ETAPS-April 18, 2015 - Workshop-May 15, 2015 Deadline for journal special issue**Topics**Specific topics of interest for the workshop include (but are not limited t=o):theory of differential privacy,verification techniques for differential privacy,programming languages for differential privacy,models for differential privacy,trade-offs between privacy protection and analytic utility,differential privacy and surveys,relaxations of the differential privacy definition,differential privacy vs other privacy notions and methods,differential privacy and accuracy,practical differential privacy,implementations for differential privacy,differential privacy and security,applications of differential privacy.**Invited Speakers**Jonathan Ullman - Simons Fellow at Columbia University,Another invited speaker joint with HotSpot'15 to be confirmed.**Program Committee**Gilles Barthe - IMDEA SoftwareKonstantinos Chatzikokolakis - CNRS and LIX, Ecole PolytechniqueKamalika Chaudhuri - UC San DiegoGraham Cormode - University of WarwickGeorge Danezis - University College LondonMarco Gaboardi - University of DundeeMatteo Maffei - CISPA, Saarland UniversityCatuscia Palamidessi - INRIA and LIX, Ecole PolytechniqueBenjamin C. Pierce - University of PennsylvaniaAaron Roth - University of PennsylvaniaDavid Sands - Chalmers University of TechnologyChris Skinner - London School of EconomicsAdam Smith - Pennsylvania State UniversityCarmela Troncoso - GradiantSalil Vadhan - Harvard University

by Aaron Roth (noreply@blogger.com) at November 25, 2014 06:49 PM UTC

### LIPIcs formatting tricks

from David Eppstein

If, like me, you're working on a SoCG submission, and this is the first time you've tried using the LIPIcs format that SoCG is now using, you may run into some minor formatting issues (no worse than the issues with the LNCS or ACM formats, but new and different). Here are the ones I've encountered, with workarounds where I have them:
• The LIPIcs format automatically includes several standard LaTeX packages including babel, amsmath, amsthm, amssymb, and hyperref. So there's no point in including them yourself and (if you specify incompatible options) it may cause an error to include them yourself. I haven't needed to change the hyperref options, but if you do, see here.

• You may like to use the lineno package so that, when reviewers give you comments on your submission, they can tell you more accurately which line they're referring to. If you try this with the LIPIcs format, you will notice that you don't get line numbers in the last paragraph of a proof, nor in a paragraph that contains a displayed equation (even if you correctly delimit the equation with $...$ instead of using the obsolete $$...$$, which can also cause problems with lineno). The solution to the proof problem is to change the proof termination symbol (a triangle instead of the usual Halmos box) to use an explicit $...$ instead of \ensuremath):

\renewcommand\qedsymbol{\textcolor{darkgray}{$\blacktriangleleft$}}

The solution to the displayed equation problem is more complicated, but is given in this blog post from 2007 (the update near the start of that post). Why this incompatibility hasn't been fixed in the last seven years is a different question.

• If you use the numberwithinsect document class option (pronounced "number with insect"), then the LIPIcs format numbers theorems, lemmas, etc by what section they are in: Lemma 2.1 for the first lemma in Section 2, etc. But if you also run past the page limit and use appendices, you may notice that the lemmas are being given numbers that re-use previously used numbers, because although the appendices have letters rather than numbers the lemmas use numbers: the first lemma in Appendix B is also called Lemma 2.1. The problem is that the LIPIcs style expands the \thesection macro (the one that gives the number or letter of the current section) at the time it defines \thetheorem (the one that gives the name of the current theorem or lemma). So when you use \appendix (or \begin{appendix} if you like to pretend that non-environment commands are really environments), \thesection gets changed but it's too late to make a difference to \thetheorem. The fix is to add the following lines after \appendix:

\makeatletter
\edef\thetheorem{\expandafter\noexpand\thesection\@thmcountersep\@thmcounter{theorem}}
\makeatother

• I've already written about the problems with using the \autoref command of the hyperref package: because LIPIcs wants to use a shared numeric sequence for theorems, lemmas, etc., \autoref thinks they are all theorems. Someone else also recently asked about this problem. This is a more general incompatibilty between amsthm and hyperref, but LIPIcs also includes some of its own code for theorem formatting, which seems to be causing the fixes one can find for amsthm not to work. The solution is to fall back to the non-hyperref way of doing things: Lemma~\ref{lem:my-lemma-name} etc.

• Speaking of theorems: if you use \newtheorem, you probably want to have a previous line \theoremstyle{definition} so that whatever you're defining looks like the other theorems and lemmas.

• On the first page of a LIPIcs paper, the last line of text may be uncomfortably close to the Creative Commons licencing icon. I haven't found a direct workaround for this (although probably it's possible) but you can obtain better spacing by having a footnote (for instance one listing your grant acknowledgements) or a bottom figure on that page.

• If you're used to trying to fit things into a page limit with LNCS format, you may have learned to use \paragraph as a trick to save space over subsections. That doesn't work very well in LIPIcs, for two reasons. First, because it will give you an ugly paragraph number like 6.0.0.1 (the first numbered paragraph in an un-numbered subsubsection of an un-numbered subsection of section 6). You can work around this by using \paragraph*. But second, because unlike in LNCS the paragraph heading won't be folded into the paragraph that follows it, so you save a lot less space. I don't want to try to work around this one. And fortunately I haven't yet seen my coauthors adding code like \noindent{\bfseries Paragraph heading.} Paragraph text... (or worse \bf ...). Solution: find different tricks for your space-saving efforts. Like maybe write more tersely.

Anyone else have any timely tips?

### Thin folding

from David Eppstein

I have another new preprint on arXiv this evening: Folding a Paper Strip to Minimize Thickness, arXiv:1411.6371, with six other authors (Demaine, Hesterberg, Ito, Lubiw, Uehara, and Uno); it's been accepted at WALCOM.

The basic goal of this is to try to understand how to measure the thickness of a piece of paper that has been folded into a shape that lies flat in the plane. For instance, in designing origami pieces, it's undesirable to have too much thickness, both because it wastes paper causing your piece to be smaller than it needs to and because it may be an obstacle to forming features of your piece that are supposed to be thin.

The obvious thing to do is to just count the number of layers of paper that cover any point of the plane, but can be problematic. For instance, if you have two offset accordion folds (drawn sideways below)
/\/\/\/\/\
\/\/\/\/\/`
then it's not really accurate to say that the thickness is the same as if you just had one of the two sets of folds: one of the two folds is raised up by the thickness of the other one so the whole folded piece of paper is more like the sum of the thicknesses of its two halves.

In the preprint, we model the thickness by assuming that the flat parts of the paper are completely horizontal, at integer heights, that two overlapping parts of paper have to be at different heights, and that a fold can connect parts of paper that are at any two different heights. But then, it turns out that finding an assignment of heights to the parts of paper that minimizes the maximum height is hard, even for one-dimensional problems where we are given a crease pattern of mountain and valley folds as input, without being told exactly how to arrange those folds. The reason is that there can be ambiguities about how the folded shape can fit into pockets formed by other parts of the fold, and choosing the right pockets is difficult.

### Optimal Encodings for Range Min-Max and Top-k

Authors: Pawel Gawrychowski, Patrick K. Nicholson
Abstract: In this paper we consider various encoding problems for range queries on arrays. In these problems, the goal is that the encoding occupies the information theoretic minimum space required to answer a particular set of range queries. Given an array $A[1..n]$ a range top-$k$ query on an arbitrary range $[i,j] \subseteq [1,n]$ asks us to return the ordered set of indices $\{l_1 ,...,l_k \}$ such that $A[l_m]$ is the $m$-th largest element in $A[i..j]$. We present optimal encodings for range top-$k$ queries, as well as for a new problem which we call range min-max, in which the goal is to return the indices of both the minimum and maximum element in a range.

### Complexity of Secure Sets

Authors: Bernhard Bliem, Stefan Woltran
Abstract: A secure set $S$ in a graph is defined as a set of vertices such that for any $X \subseteq S$ the majority of vertices in the neighborhood of $X$ belongs to $S$. It is known that deciding whether a set $S$ is secure in a graph is co-NP-complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph $G$ and integer $k$, a non-empty secure set for $G$ of size at most $k$ exists. While membership in the class $\Sigma^P_2$ is rather easy to see for this existence problem, showing $\Sigma^P_2$-hardness is quite involved. In this paper, we provide such a hardness result, hence classifying the secure set existence problem as $\Sigma^P_2$-complete. We do so by first showing hardness for a variant of the problem, which we then reduce step-by-step to secure set existence. In total, we obtain eight new completeness results for different variants of the secure set existence problem.
Abstract: Biobjective mixed integer linear programs (BOMILP) are optimization problems where two linear objectives are optimized over a polyhedron while restricting some of the variables to be integer. Since many of the techniques for solving BOMILP (or approximating its solution set) are iterative processes which utilize data discovered during early iterations to aid in the discovery of improved data during later iterations, it is highly desirable to efficiently store the nondominated subset of a given set of data. This problem has not received considerable attention in the context of BOMILP; only naive methods have been implemented. We seek to bridge this gap by presenting a new data structure in the form of a modified binary tree that stores, updates, searches and returns nondominated solutions. This structure takes points and line segments in $\mathbb{R}^2$ as input and stores the nondominated subset of this input. We note that when used alongside an exact solution procedure, such as branch-and-bound (BB), at termination the data stored by this structure is precisely the set of Pareto optimal solutions. We perform two experiments. The first is designed to compare the utility of our structure for storing nondominated data to that of a dynamic list which updates via pairwise comparison. In the second we use our data structure alongside the biobjective BB techniques available in the literature and solve specific instances of BOMILP. The results of our first experiment suggest that the data structure performs reasonably well in handling input of up to $10^7$ points or segments and does so much more efficiently than a dynamic list. The results of the second experiment show that when our structure is utilized alongside BB fathoming is enhanced and running times improve slightly.