# Theory of Computing Blog Aggregator

### The benefits of Recreational Mathematics

Why study Recreational Mathematics?

Why do recreational Mathematics?

1)  The line between recreational and serious mathematics is thin. Some of the problems in so-called recreational math are harder than they look.

2) Inspiring. Both Lance and I were inspired by books by Martin Gardner, Ray Smullyan, Brian Hayes, and others.

3) Pedagogical: Understanding Godel's Inc. theorem via the Liar's paradox (Ray S has popularized that approach) is a nice way to teach the theorem to the layperson (and even to non-laypeople).

4) Rec math can be the starting point for so-called serious math. The Konigsberg bridge problem was the starting point for graph theory,  The fault diagnosis problem is a generalization of the Truth Tellers and Normals Problem. See here for a nice paper by Blecher on the recreational'' problem of given N people of which over half are truth tellers and the rest are normals, asking questions of the type is that guy a normal'' to determine whose who. See here for my writeup of  the algorithm for a slightly more general problem. See William Hurwoods Thesis: here for a review of the Fault Diagnosis Literature which includes Blecher's paper.

I am sure there are many other examples and I invite the readers to write of them in the comments.

5) Rec math can be used to inspire HS students who don't quite have enough background to do so-called serious mathematics.

This post is a bit odd since I cannot imagine a serious counter-argument; however, if you disagree, leave an intelligent thoughtful comment with a contrary point of view.

by GASARCH (noreply@blogger.com) at February 20, 2017 04:25 AM UTC

### Triangle-free penny graphs are 2-degenerate

from David Eppstein

A penny graph (the topic of today's new Wikipedia article) is what you get from pennies by shoving them together on a tabletop, keeping them only one layer thick, and looking at which pairs of pennies are touching each other. In a 2009 paper, Konrad Swanepoel suggested that, when there are no three mutually-touching pennies, the number of adjacencies should be at most 2n − 2√n. I don't know how to prove that, and as far as I know the problem remains open. But here's an argument for why the number of edges should be strictly less than 2n − 4, the upper bound given by Swanepoel.

The basic idea is that, in any set of triangle-free pennies, some penny is touched at most twice. Or, in graph theoretic terms, a triangle-free penny graph must be 2-degenerate. For, suppose to the contrary that all pennies had at least three neighbors, and consider the outer face of the planar graph formed by the pennies (marked by the blue polyline below). For each penny on the outer face, draw a line through its center and the center of a neighboring penny that is not one of its two outer-face neighbors (the red lines in the figure).

As you walk around the outer face (clockwise, say) these red lines would always have to point consistently inwards and outwards, so they would have to turn with you, eventually making a complete circuit in the clockwise direction. But they can only turn counterclockwise! If you follow an outer face edge whose adjacent inner face is a quadrilateral, the red lines stay parallel (as they do in most of the picture) and otherwise they turn the wrong way. The impossibility of the red lines making a complete clockwise turn while only turning counterclockwise at each step shows that our assumption, that all pennies have three neighbors, cannot be correct. Therefore, there is a penny on the outer face with at most two neighbors.

Five-vertex triangle-free penny graphs have at most five edges, so by induction n-vertex triangle-free penny graphs have at most 2n − 5 edges, very slightly edging out an upper bound of 2n − 4 given by Swanepoel based on Euler's formula.

The fact that penny graphs are 3-degenerate is a standard exercise, part of an easy proof of the four-color theorem for these graphs. Similarly, the 2-degeneracy of triangle-free penny graphs leads to an easy proof of Grötzsch's theorem for them. So I would be surprised if the 2-degeneracy of the triangle-free penny graphs is new, but I didn't see it when I was researching the Wikipedia article. Does anyone know of a reference?

### LCL problems on grids

Authors: Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R. J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, Przemysław Uznański
Abstract: LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of $O(1)$, $\Theta(\log^* n)$, or $\Theta(n)$, and the design of optimal algorithms can be fully automated.

This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: $O(1)$, $\Theta(\log^* n)$, and $\Theta(n)$. However, given an LCL problem it is undecidable whether its complexity is $\Theta(\log^* n)$ or $\Theta(n)$ in 2-dimensional grids.

Nevertheless, if we correctly guess that the complexity of a problem is $\Theta(\log^* n)$, we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form $A' \circ S_k$, where $A'$ is a finite function, $S_k$ is an algorithm for finding a maximal independent set in $k$th power of the grid, and $k$ is a constant.

With the help of this technique, we study several concrete \lcl{} problems, also in more general settings. For example, for all $d \ge 2$, we prove that:

- $d$-dimensional grids can be $k$-vertex coloured in time $O(\log^* n)$ iff $k \ge 4$,

- $d$-dimensional grids can be $k$-edge coloured in time $O(\log^* n)$ iff $k \ge 2d+1$.

The proof that $3$-colouring of $2$-dimensional grids requires $\Theta(n)$ time introduces a new topological proof technique, which can also be applied to e.g. orientation problems.

### Counting edge-injective homomorphisms and matchings on restricted graph classes

Authors: Radu Curticapean, Holger Dell, Marc Roth
Abstract: We consider the parameterized problem of counting all matchings with exactly $k$ edges in a given input graph $G$. This problem is #W[1]-hard (Curticapean, ICALP 2013), so it is unlikely to admit $f(k)\cdot n^{O(1)}$ time algorithms. We show that #W[1]-hardness persists even when the input graph $G$ comes from restricted graph classes, such as line graphs and bipartite graphs of arbitrary constant girth and maximum degree two on one side. To prove the result for line graphs, we observe that $k$-matchings in line graphs can be equivalently viewed as edge-injective homomorphisms from the disjoint union of $k$ paths of length two into (arbitrary) host graphs. Here, a homomorphism from $H$ to $G$ is edge-injective if it maps any two distinct edges of $H$ to distinct edges in $G$. We show that edge-injective homomorphisms from a pattern graph $H$ can be counted in polynomial time if $H$ has bounded vertex-cover number after removing isolated edges. For hereditary classes $\mathcal{H}$ of pattern graphs, we obtain a full complexity dichotomy theorem by proving that counting edge-injective homomorphisms, restricted to patterns from $\mathcal{H}$, is #W[1]-hard if no such bound exists. Our proofs rely on an edge-colored variant of Holant problems and a delicate interpolation argument; both may be of independent interest.

### Network Flow Based Post Processing for Sales Diversity

Authors: Arda Antikacioglu, R Ravi
Abstract: Collaborative filtering is a broad and powerful framework for building recommendation systems that has seen widespread adoption. Over the past decade, the propensity of such systems for favoring popular products and thus creating echo chambers have been observed. This has given rise to an active area of research that seeks to diversify recommendations generated by such algorithms.

We address the problem of increasing diversity in recommendation systems that are based on collaborative filtering that use past ratings to predicting a rating quality for potential recommendations. Following our earlier work, we formulate recommendation system design as a subgraph selection problem from a candidate super-graph of potential recommendations where both diversity and rating quality are explicitly optimized: (1) On the modeling side, we define a new flexible notion of diversity that allows a system designer to prescribe the number of recommendations each item should receive, and smoothly penalizes deviations from this distribution. (2) On the algorithmic side, we show that minimum-cost network flow methods yield fast algorithms in theory and practice for designing recommendation subgraphs that optimize this notion of diversity. (3) On the empirical side, we show the effectiveness of our new model and method to increase diversity while maintaining high rating quality in standard rating data sets from Netflix and MovieLens.

### Exact clustering in linear time

Authors: Jonathan A. Marshall, Lawrence C. Rafsky
Abstract: The time complexity of data clustering has been viewed as fundamentally quadratic, slowing with the number of data items, as each item is compared for similarity to preceding items. Clustering of large data sets has been infeasible without resorting to probabilistic methods or to capping the number of clusters. Here we introduce MIMOSA, a novel class of algorithms which achieve linear time computational complexity on clustering tasks. MIMOSA algorithms mark and match partial-signature keys in a hash table to obtain exact, error-free cluster retrieval. Benchmark measurements, on clustering a data set of 10,000,000 news articles by news topic, found that a MIMOSA implementation finished more than four orders of magnitude faster than a standard centroid implementation.

### 3D Cell Nuclei Segmentation with Balanced Graph Partitioning

Authors: Julian Arz, Peter Sanders, Johannes Stegmaier, Ralf Mikut
Abstract: Cell nuclei segmentation is one of the most important tasks in the analysis of biomedical images. With ever-growing sizes and amounts of three-dimensional images to be processed, there is a need for better and faster segmentation methods. Graph-based image segmentation has seen a rise in popularity in recent years, but is seen as very costly with regard to computational demand. We propose a new segmentation algorithm which overcomes these limitations. Our method uses recursive balanced graph partitioning to segment foreground components of a fast and efficient binarization. We construct a model for the cell nuclei to guide the partitioning process. Our algorithm is compared to other state-of-the-art segmentation algorithms in an experimental evaluation on two sets of realistically simulated inputs. Our method is faster, has similar or better quality and an acceptable memory overhead.

### Computational topology of graphs on surfaces

Authors: Éric Colin de Verdière
Abstract: Computational topology is an area that revisits topological problems from an algorithmic point of view, and develops topological tools for improved algorithms. We survey results in computational topology that are concerned with graphs drawn on surfaces. Typical questions include representing surfaces and graphs embedded on them computationally, deciding whether a graph embeds on a surface, solving computational problems related to homotopy, optimizing curves and graphs on surfaces, and solving standard graph algorithm problems more efficiently in the case of surface-embedded graphs.

### On algebraic branching programs of small width

Authors: Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam
Abstract: In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds.

Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar.

As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.

Authors: Elisabetta Bergamini, Pierluigi Crescenzi, Gianlorenzo D'Angelo, Henning Meyerhenke, Lorenzo Severini, Yllka Velaj
Abstract: Betweenness is a well-known centrality measure that ranks the nodes according to their participation in the shortest paths of a network. In several scenarios, having a high betweenness can have a positive impact on the node itself. Hence, in this paper we consider the problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it. In particular, we study the problem of maximizing the betweenness score of a given node -- Maximum Betweenness Improvement (MBI) -- and that of maximizing the ranking of a given node -- Maximum Ranking Improvement (MRI). We show that MBI cannot be approximated in polynomial-time within a factor $(1-\frac{1}{2e})$ and that MRI does not admit any polynomial-time constant factor approximation algorithm, both unless $P=NP$. We then propose a simple greedy approximation algorithm for MBI with an almost tight approximation ratio and we test its performance on several real-world networks. We experimentally show that our algorithm highly increases both the betweenness score and the ranking of a given node ant that it outperforms several competitive baselines. To speed up the computation of our greedy algorithm, we also propose a new dynamic algorithm for updating the betweenness of one node after an edge insertion, which might be of independent interest. Using the dynamic algorithm, we are now able to compute an approximation of MBI on networks with up to $10^5$ edges in most cases in a matter of seconds or a few minutes.

### T-Shape Visibility Representations of 1-Planar Graphs

Authors: Franz J. Brandenburg
Abstract: A shape visibility representation displays a graph so that each vertex is represented by an orthogonal polygon of a particular shape and for each edge there is a horizontal or vertical line of sight between the polygons assigned to its endvertices. Special shapes are rectangles, L, T, E and H-shapes, and caterpillars. A flat rectangle is a horizontal bar of height $\epsilon>0$. A graph is 1-planar if there is a drawing in the plane such that each edge is crossed at most once and is IC-planar if in addition no two crossing edges share a vertex.

We show that every IC-planar graph has a flat rectangle visibility representation and that every 1-planar graph has a T-shape visibility representation. The representations use quadratic area and can be computed in linear time from a given embedding.

### Complete Submodularity Characterization in the Comparative Independent Cascade Model

Authors: Wei Chen, Hanrui Zhang
Abstract: We study the propagation of comparative ideas in social network. A full characterization for submodularity in the comparative independent cascade (Com-IC) model of two-idea cascade is given, for competing ideas and complementary ideas respectively. We further introduce One-Shot model where agents show less patience toward ideas, and show that in One-Shot model, only the stronger idea spreads with submodularity.

### A Fully Polynomial Time Approximation Scheme for Packing While Traveling

Authors: Frank Neumann, Sergey Polyakovskiy, Martin Skutella, Leen Stougie, Junhua Wu
Abstract: Understanding the interactions between different combinatorial optimisation problems in real-world applications is a challenging task. Recently, the traveling thief problem (TTP), as a combination of the classical traveling salesperson problem and the knapsack problem, has been introduced to study these interactions in a systematic way. We investigate the underlying non-linear packing while traveling (PWT) problem of the TTP where items have to be selected along a fixed route. We give an exact dynamic programming approach for this problem and a fully polynomial time approximation scheme (FPTAS) when maximising the benefit that can be gained over the baseline travel cost. Our experimental investigations show that our new approaches outperform current state-of-the-art approaches on a wide range of benchmark instances.

Authors: Patricia Bouyer-Decitre, Vincent Jugé, Nicolas Markey
Abstract: Dynamic complexity is concerned with updating the output of a problem when the input is slightly changed. We study the dynamic complexity of model checking a fixed monadic second-order formula over evolving subgraphs of a fixed maximal graph having bounded tree-width; here the subgraph evolves by losing or gaining edges (from the maximal graph). We show that this problem is in DynFO (with LOGSPACE precomputation), via a reduction to a Dyck reachability problem on an acyclic automaton.

### On the Bit Complexity of Sum-of-Squares Proofs

Abstract: It has often been claimed in recent papers that one can find a degree d Sum-of-Squares proof if one exists via the Ellipsoid algorithm. In [O17], Ryan O'Donnell notes this widely quoted claim is not necessarily true. He presents an example of a polynomial system with bounded coeffcients that admits low-degree proofs of non-negativity, but these proofs necessarily involve numbers with an exponential number of bits, causing the Ellipsoid algorithm to take exponential time. In this paper we obtain both positive and negative results on the bit complexity of SoS proofs. First, we propose a suffcient condition on a polynomial system that implies a bound on the coefficients in an SoS proof. We demonstrate that this sufficient condition is applicable for common use-cases of the SoS algorithm, such as Max-CSP, Balanced Separator, Max- Clique, Max-Bisection, and Unit-Vector constraints. On the negative side, O'Donnell asked whether every polynomial system containing Boolean constraints admits proofs of polynomial bit complexity. We answer this question in the negative, giving a counterexample system and non-negative polynomial which has degree two SoS proofs, but no SoS proof with small coefficients until degree Omega(sqrt(n))

### TR17-033 | Labeling the complete bipartite graph with no zero cycles | Daniel Kane, Shachar Lovett, Sankeerth Rao

from ECCC papers

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size needed for maximally recoverable codes in grid topologies. We show that the answer is that $d$ is linear in $n$. The upper bound is an explicit construction which improves upon the random construction. The lower bound is more technical, and relies on the study of independent sets in certain Cayley graphs of the permutation group.

### Exciting new book

My long term collaborator, thinker, and a theory researcher Ramesh Hariharan has put together a book that sounds fascinating: Genomic Quirks: The Search for Spelling Errors.

"This is a book of real stories about the search for genomic spelling errors that have stark consequences -- infants who pass away mysteriously, siblings with misplaced organs, a family with several instances of vision loss, sisters whose hearts fail in the prime of their youth, a boy whose blood can’t carry enough oxygen, a baby with cancer in the eye, a middle-aged patient battling cancer, and the author’s own color blindness. The search in each case proves to be a detective quest that connects the world of medical practice with that of molecular biology, traversing the world of computer algorithms along the way."

by metoo (noreply@blogger.com) at February 19, 2017 02:16 PM UTC

### Proof By Lice!

from Gil Kalai

From camels to lice. (A proof promised here.)

Theorem (Hopf and Pannwitz, 1934): Let $X$ be a set of $n$ points in the plane  in general position (no three points on a line) and consider $n+1$ line segments whose endpoints are in $X$.  Then there are two disjoint line segments.

Micha Perles’s proof by Lice:

Useful properties of lice: A louse lives on a head and wishes to lay an egg on a hair.

Think about the points in the plane as little heads, and think about each line segments between two points as a hair.

The proof goes as follows:

Step one: You take $n$ lice from your own head and put them on the $n$ points of $X$.

Step two: each louse examines the hairs coming from the head and lay eggs (on the hair near the head)

Step three (not strictly needed): You take back the $n$ lice and put them back on your head.

To make it work we need a special type of lice: spoiled-left-wing-louse.

A spoiled-left-wing louse lays an egg on a hair if and only if the area near the head,  180 degrees to the right of this hair is free from other hairs.

Lemma: Every louse lays at most one egg.

Proof of lemma: As you see from the picture, if the louse lays an egg on one hair, this hair disturbs every other hair.

Proof of theorem continued: since there are $n+1$ line segments and only at most $n$ eggs there is a hair X between heads A and B with no eggs.

We look at this hair and ask:

Why don’t we have an egg near head A: because there is a hair Y in the angle 180° to the right.

Why don’t we have an egg near head B: because there is a hair Z in the angle 180° to the right.

Y and Z must be disjoint. Q. E. D.

Remarks: We actually get a ZIG formed by Y, X, and Z

If we use right-wing-spoiled lice we will get a ZAG.

We can allow the points not to be in general position as long as one hair from a head does not contain another hair from the same head.

The topological version of this problem is the infamous Conway’s thrackle conjecture. See also Stephan Wehner page about it.

by Gil Kalai at February 19, 2017 10:58 AM UTC

### TR17-032 | Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds | Joshua Blinkhorn, Olaf Beyersdorff

from ECCC papers

We devise a new technique to prove lower bounds for the proof size in resolution-type calculi for quantified Boolean formulas (QBF). The new technique applies to the strong expansion system IR-calc and thereby also to the most studied QBF system Q-Resolution. Our technique exploits a clear semantic paradigm, showing the hardness of a QBF family by demonstrating that (1) the formulas require large witnessing functions for the universal variables, and (2) in the game semantics of QBF, the universal player is forced to make many responses on a set of variables that we identify as critical. Based on these two conditions, our technique yields a weight for a QBF formula, which provides an absolute lower bound for the size of its IR-calc proofs (and hence also its Q-Resolution proofs). We exemplify our technique on a couple of known and new instances, among them the prominent formulas of Kleine Büning et al. (Inform. Comput. 1995), for which our method provides a hardness proof that is considerably simpler than previous approaches. Our technique also provides the first separations for QBF dependency calculi. In particular, we construct a simple class of formulas that are hard for Q-Resolution, but easy in Q-Resolution parameterized by the reflexive resolution path dependency scheme, thus answering a question posed by Slivovsky and Szeider (SAT 2014).

### TR17-031 | Quadratic Simulations of Merlin-Arthur Games | Thomas Watson

from ECCC papers

The known proofs of $\text{MA}\subseteq\text{PP}$ incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which $\text{MA-TIME}(t)\not\subseteq\text{P-TIME}(o(t^2))$. We also show that 2-sided-error Merlin--Arthur games can be simulated by 1-sided-error Arthur--Merlin games with quadratic overhead. We also present a simple, query complexity based proof (provided by Mika G\"o\"os) that there is an oracle relative to which $\text{MA}\not\subseteq\text{NP}^{\text{BPP}}$ (which was previously known to hold by a proof using generics).

### TR17-030 | An Improved Dictatorship Test with Perfect Completeness | Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

from ECCC papers

A Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is called a dictator if it depends on exactly one variable i.e $f(x_1, x_2, \ldots, x_n) = x_i$ for some $i\in [n]$. In this work, we study a $k$-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems. The dictatorship test is said to have {\em perfect completeness} if it accepts any dictator function. The {\em soundness} of a test is the maximum probability with which it accepts any function far from a dictator. Our main result is a $k$-query dictatorship test with perfect completeness and soundness $\frac{2k + 1}{2^k}$, where $k$ is of the form $2^t -1$ for any integer $t > 2$. This improves upon the result of \cite{TY15} which gave a dictatorship test with soundness $\frac{2k + 3}{2^k}$.

### TR17-029 | An Adaptivity Hierarchy Theorem for Property Testing | Tom Gur, Clement Canonne

from ECCC papers

Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their \emph{non-adaptive} counterparts, in which all queries are independent of answers obtained from previous queries. In this work, we investigate the role of adaptivity in property testing at a finer level. We first quantify the degree of adaptivity of a testing algorithm by considering the number of rounds of adaptivity'' it uses. More accurately, we say that a tester is $k$-(round) adaptive if it makes queries in $k+1$ rounds, where the queries in the $i$'th round may depend on the answers obtained in the previous $i-1$ rounds. Then, we ask the following question: Does the power of testing algorithms smoothly grow with the number of rounds of adaptivity? We provide a positive answer to the foregoing question by proving an adaptivity hierarchy theorem for property testing. Specifically, our main result shows that for every $n\in \N$ and $0 \le k \le n^{0.99}$ there exists a property $\mathcal{P}_{n,k}$ of functions for which (1) there exists a $k$-adaptive tester for $\mathcal{P}_{n,k}$ with query complexity $\tildeO{k}$, yet (2) any $(k-1)$-adaptive tester for $\mathcal{P}_{n,k}$ must make $\Omega(n)$ queries. In addition, we show that such a qualitative adaptivity hierarchy can be witnessed for testing natural properties of graphs.

### Coincidence?

from Luca Trevisan

“Art imitates life, but life imitates bad TV” (Woody Allen)

The mention for a major alumni award given by U.C. Berkeley is for excellence in achievement.

Meanwhile, in the episode “Brother, can you spare two dimes?”, Mr. Burns has to come up on the spot with the name for a fake awards, and he comes up with an award for outstanding achievement in the field of excellence.

(You’ll note that the dancers in the video are wearing gold and blue)

### TR17-028 | A quadratic lower bound for homogeneous algebraic branching programs | Mrinal Kumar

from ECCC papers

An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex $s$, and end vertex $t$ and each edge having a weight which is an affine form in $\F[x_1, x_2, \ldots, x_n]$. An ABP computes a polynomial in a natural way, as the sum of weights of all paths from $s$ to $t$, where the weight of a path is the product of the weights of the edges in the path. An ABP is said to be homogeneous if the polynomial computed at every vertex is homogeneous. In this paper, we show that any homogeneous algebraic branching which computes the polynomial $x_1^n + x_2^n + \ldots + x_n^n$ has at least $\Omega(n^2)$ vertices (and hence edges). To the best of our knowledge, this seems to be the first non-trivial super-linear lower bound on the number of vertices for a general \emph{homogeneous} ABP and slightly improves the known lower bound of $\Omega(n\log n)$ on the number of edges of in a general (possibly \emph{non-homogeneous}) ABP, which follows from the classical results of Strassen~\cite{Strassen73} and Baur \& Strassen~\cite{BS83}. On the way, we also get an alternate and essentially unified proof of an $\Omega(n\log n)$ lower bound on the size of a \emph{homogeneous} arithmetic circuit (follows from~\cite{Strassen73, BS83}), and an $n/2$ lower bound ($n$ over $\mathbb{R}$) on the determinantal complexity of an explicit polynomial~\cite{mr04, CCL10, Yabe15}. These are currently the best lower bounds known for these problems for any explicit polynomial, and were originally proved nearly two decades apart using seemingly different proof techniques.

### TR17-027 | A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate | Dean Doron, Avraham Ben-Aroya, Amnon Ta-Shma, Eshan Chattopadhyay, Xin Li

from ECCC papers

We show a reduction from the existence of explicit t-non-malleable extractors with a small seed length, to the construction of explicit two-source extractors with small error for sources with arbitrarily small constant rate. Previously, such a reduction was known either when one source had entropy rate above half [Raz05] or for general entropy rates but only for large error [CZ16]. As in previous reductions we start with the Chattopadhyay and Zuckerman approach [CZ16], where an extractor is applied on one source to create a table, and the second source is used to sample a sub-table. In previous work, a resilient function was applied on the sub-table and the use of resilient functions immediately implied large error. In this work we replace the resilient function with the parity function (that is not resilient). We prove correctness by showing that doing the sampling properly, the sample size can be made so small that it is smaller then the non-malleability parameter t of the first extractor, which is enough for the correctness. The parameters we require from the non-malleable construction hold (quite comfortably) in a non-explicit construction, but currently it is not known how to explicitly construct such graphs. As a result we do not give an unconditional construction of an explicit low-error two-source extractor. However, the reduction shows a new connection between non-malleable and two-source extractors, and also shows resilient functions do not play a crucial role in the two-source construction framework suggested in [CZ16]. Furthermore, the reduction highlights a barrier in constructing non-malleable extractors, and reveals its importance. We hope this work would lead to further developments in explicit constructions of both non-malleable and two-source extractors.

### An unsuccessful attempt to use CairoSVG to generate small vector-graphics PDF files

from David Eppstein

The following image shows the onion layers of a 6 × 6 grid (see Sariel's post for context). It consists of 42 circles, 36 with a fill and a stroke and 6 with only a stroke.

My usual workflow is to draw this sort of thing in Adobe Illustrator, but one drawback of doing things this way is huge files: as a PDF file suitable for inclusion in LaTeX, these 42 circles take up 155k bytes. I've recently started cutting my file size by opening the Illustrator PDF in the Apple Preview application, and then using Preview's "export" command with the "reduce file size" filter. This cuts it down to 41k, still nothing impressive but a lot better. It does have the drawback that going between Illustrator and Preview multiple times has sometimes messed up my fonts, so I think it's best viewed as a one-way filter: if I want to re-edit the same file, I need to keep the original.

But if I save as an SVG file from Illustrator (like the one above) it's only 3.3K, a reasonable size for such a simple image. Reading the SVG back into Illustrator and saving as PDF blows it back up to 88k, which is still way too big. So I thought: maybe there's a good command line tool for converting SVG to PDF? I could have a workflow where I use Illustrator only to read and edit SVG files (keeping them around so that I can re-edit them if I want, without as much confusion as keeping two different PDF versions of the same file) and use a different program to convert them to small PDFs.

After some searching, I found CairoSVG, which (after a lot of hassle installing, see below) seemed to work well: it produces a 3.5k byte PDF file from the same image.

The installation process was a bit of a mess. Very different from typical OS X download-and-run installation processes:
1. Install pip from https://pip.pypa.io/en/stable/installing/
2. Use pip to install CairoSvg per http://cairosvg.org/
3. Try running cairosvg from the command line, but it doesn't work because it is unable to load the cairo library. After much searching, discover what the CairoSVG web site never tells you: that cairo is a separate piece of software that you also need to install.
4. Install MacPorts from https://www.macports.org/install.php
5. Try using MacPorts to install cairo, but discover that it requires the App version of Xcode and not just the command-line developer tools I already had installed.
6. Install Xcode from the Apple App store
7. Try MacPorts again, but discover that the App store install is not the real install.
8. Run Xcode to install it for real.
9. Use MacPorts to install cairo per https://www.cairographics.org/
10. Try running cairosvg from the command line, but it still can't find the library.
11. Searching the net for the error message eventually leads to https://github.com/Kozea/WeasyPrint/issues/79 which advises setting the environment variable DYLD_FALLBACK_LIBRARY_PATH to /opt/local/lib
12. It used to be the case that setting environment variables globally was done by editing the file ~/.MacOSX/environment.plist but that no longer works — see http://stackoverflow.com/questions/603785/environment-variables-in-mac-os-x/ — so instead I've been putting them in my .login file.
13. After editing .login to set the environment variable I need to make a new terminal window because the old ones won't have it set yet.
After all this, the command-line cairosvg runs, and the command line "cairosvg grid-onion.svg -o grid-onion.pdf" produces the small PDF file reported above.

But we're not done...

It turns out that the resulting PDF has a different image size than the original file. After some more groveling on the net I discovered that it's using a default value of 96 dots per inch rather than respecting the 72dpi value used by Illustrator. So when I view the resulting pdf files in Illustrator, Preview, or TeX, they don't have the same scale as when I drew them. This is a problem, because I've been using relative image sizes (the scale= parameter of graphicx) when including images in some of my LaTeX documents.

The cairosvg command line program has two options for changing the scale. We can either set the program to use 72 dpi, or we can tell it to scale the image by a factor of 1.33. Both generate images that have the correct size. But now the bounding box of the image has been destroyed, and it's instead using a bounding box that's way too big. This turns out to be true for svg to png conversion as well: if I try to use cairosvg to make a png from my svg file, it also loses the bounding box. There are no options for telling cairosvg to avoid destroying the bounding box, and no suggestion on the cairosvg issue tracking site that anyone knows or cares about this problem.

After all this, I'm ready to give up on cairosvg as being worth what I've paid for it (nothing). Does anyone know of an svg-to-pdf conversion pipeline that produces small pdf files but actually works?

### TR17-026 | A Polynomial Restriction Lemma with Applications | Valentine Kabanets, Daniel Kane, Zhenjian Lu

from ECCC papers

A polynomial threshold function (PTF) of degree $d$ is a boolean function of the form $f=\mathrm{sgn}(p)$, where $p$ is a degree-$d$ polynomial, and $\mathrm{sgn}$ is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is not close to a constant function, where a boolean function $g$ is called $\delta$-close to constant if, for some $v\in\{1,-1\}$, we have $g(x)=v$ for all but at most $\delta$ fraction of inputs. We show for every PTF $f$ of degree $d\geq 1$, and parameters $0<\delta, r\leq 1/16$, that $\mathbf{Pr}_{\rho\sim R_r} [f_{\rho} \text{ is not } \delta \text{-close to constant}] \leq (\sqrt{r} + \delta)\cdot (\log (1/r) \cdot \log (1/\delta))^{O(d^2)},$ where $\rho\sim R_r$ is a random restriction leaving each variable, independently, free with probability $r$, and otherwise assigning it $1$ or $-1$ uniformly at random. In fact, we show a more general result for random block restrictions: given an arbitrary partitioning of input variables into $m$ blocks, a random block restriction picks a uniformly random block $\ell\in [m]$ and assigns $1$ or $-1$, uniformly at random, to all variable outside the chosen block $\ell$. We prove the Block Restriction Lemma saying that a PTF $f$ of degree $d$ becomes $\delta$-close to constant when hit with a random block restriction, except with probability at most $(m^{-1/2}+\delta)\cdot (\log m\cdot \log (1/\delta))^{O(d^2)}$. As an application of our Restriction Lemma, we prove lower bounds against constant-depth circuits with PTF gates of any degree $1\leq d\ll \sqrt{\log n/\log\log n}$, generalizing the recent bounds against constant-depth circuits with linear threshold gates (LTF gates) proved by Kane and Williams (STOC, 2016) and Chen, Santhanam, and Srinivasan (CCC, 2016). In particular, we show that there is an $n$-variate boolean function $F_n \in \mathrm{P}$ such that every depth-2 circuit with PTF gates of degree $d\geq 1$ that computes $F_n$ must have at least $\left(n^{\frac{3}{2}+\frac{1}{d}}\right)\cdot (\log n)^{-O(d^2)}$ wires. For constant depths greater than $2$, we also show average-case lower bounds for such circuits with super-linear number of wires. These are the first super-linear bounds on the number of wires for circuits with PTF gates. We also give short proofs of the optimal-exponent average sensitivity bound for degree-$d$ PTFs due to Kane (Computational Complexity, 2014), and the Littlewood-Offord type anticoncentration bound for degree-$d$ multilinear polynomials due to Meka, Nguyen, and Vu (Theory of Computing, 2016). Finally, we give derandomized versions of our Block Restriction Lemma and Littlewood-Offord type anticoncentration bounds, using a pseudorandom generator for PTFs due to Meka and Zuckerman (SICOMP, 2013).

### Succinct progress measures for solving parity games

Authors: Marcin Jurdziński, Ranko Lazić
Abstract: Calude et al. have given the first algorithm for solving parity games in quasi-polynomial time, where previously the best algorithms were mildly subexponential. We combine the succinct counting technique of Calude et al.\ with the small progress measure technique of Jurdzi\'nski. Our contribution is two-fold: we provide an alternative exposition of the ideas behind the groundbreaking quasi-polynomial algorithm of Calude et al., and we use it to reduce the space required from quasi-polynomial to nearly linear.

### Online Constrained Forest and Prize-Collecting Network Design

Authors: Jiawei Qian, Seeun William Umboh, David P. Williamson
Abstract: In this paper, we study a very general type of online network design problem, and generalize two different previous algorithms, one for an online network design problem due to Berman and Coulston [4] and one for (offline) general network design problems due to Goemans and Williamson [9]; we give an O(log k)-competitive algorithm, where k is the number of nodes that must be connected. We also consider a further generalization of the problem that allows us to pay penalties in exchange for violating connectivity constraints; we give an online O(log k)-competitive algorithm for this case as well.

### Proust: A Design Space for Highly-Concurrent Transactional Data Structures

Authors: Thomas D. Dickerson, Paul Gazzillo, Eric Koskinen, Maurice Herlihy
Abstract: Most STM systems are poorly equipped to support libraries of concurrent data structures. One reason is that they typically detect conflicts by tracking transactions' read sets and write sets, an approach that often leads to false conflicts. A second is that existing data structures and libraries often need to be rewritten from scratch to support transactional conflict detection and rollback. This paper introduces Proust, a framework for the design and implementation of transactional data structures. Proust is designed to maximize re-use of existing well-engineered by providing transactional "wrappers" to make existing thread-safe concurrent data structures transactional. Proustian objects are also integrated with an underling STM system, allowing them to take advantage of well-engineered STM conflict detection mechanisms. Proust generalizes and unifies prior approaches such as boosting and predication.

### Finding All Useless Arcs in Directed Planar Graphs

Authors: Jittat Fakcharoenphol, Bundit Laekhanukit, Pattara Sukprasert
Abstract: Maximum flow is a fundamental problem in Combinatorial Optimization that has numerous applications in both theory and practice. In this paper, we study the flow network simplification problem, which asks to remove all the useless arcs from the graph. To be precise, an arc is useless if it does not participate in any simple s,t-path. Weihe [FOCS'94, JCSS'97] showed if there exists an $O(n \log n)$-time algorithm for simplifying a flow network, then a maximum s,t-flow in directed planar graphs can be computed in $O(n \log n)$-time. However, there was no known algorithm that could determine all the useless arcs in $O(n \log n)$-time. Although an $O(n \log n)$-time algorithm for computing maximum flow on directed planar graphs without simplifying a flow network has been later discovered Borradaile and Klein [SODA'06, J.ACM'09], it remains open whether a directed planar flow network can be simplified in $O(n \log n)$-time.

Here we present an algorithm that determines all the useless arcs in $O(n \log n)$-time, thus completing the framework of Weihe. Our algorithm improves upon the previous best running time of $O(n^2)$ for removing all the useless by Misiolek and Chen [COCOON'05, IPL'06] and by Biedl, Brejova and Vinar [MFCS'00].

### Compression Complexity

Authors: Stephen Fenner, Lance Fortnow
Abstract: The Kolmogorov complexity of x, denoted C(x), is the length of the shortest program that generates x. For such a simple definition, Kolmogorov complexity has a rich and deep theory, as well as applications to a wide variety of topics including learning theory, complexity lower bounds and SAT algorithms.

Kolmogorov complexity typically focuses on decompression, going from the compressed program to the original string. This paper develops a dual notion of compression, the mapping from a string to its compressed version. Typical lossless compression algorithms such as Lempel-Ziv or Huffman Encoding always produce a string that will decompress to the original. We define a general compression concept based on this observation.

For every m, we exhibit a single compression algorithm q of length about m which for n and strings x of length n >= m, the output of q will have length within n-m+O(1) bits of C(x). We also show this bound is tight in a strong way, for every n >= m there is an x of length n with C(x) about m such that no compression program of size slightly less than m can compress x at all.

We also consider a polynomial time-bounded version of compression complexity and show that similar results for this version would rule out cryptographic one-way functions.

### An Improved Dictatorship Test with Perfect Completeness

Authors: Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari
Abstract: A Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is called a dictator if it depends on exactly one variable i.e $f(x_1, x_2, \ldots, x_n) = x_i$ for some $i\in [n]$. In this work, we study a $k$-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems.

The dictatorship test is said to have {\em perfect completeness} if it accepts any dictator function. The {\em soundness} of a test is the maximum probability with which it accepts any function far from a dictator. Our main result is a $k$-query dictatorship test with perfect completeness and soundness $\frac{2k + 1}{2^k}$, where $k$ is of the form $2^t -1$ for any integer $t > 2$. This improves upon the result of \cite{TY15} which gave a dictatorship test with soundness $\frac{2k + 3}{2^k}$.

### The seventeen camels riddle, and Noga Alon’s camel proof and algorithms

from Gil Kalai

Three children inherited 17 camels. The will gave one half to one child, one third to a second child and one ninth to the third. The children did not know what to do and  a neighbor offered to lend them a camel. Now there were 18 camels. One child got $\frac{18}{2}=9$ camels the second got $\frac{18}{3}=6$ camels, and the third got $\frac{18}{9}=2$ camels. Altogether they got 17 camels so they could give back the extra camel to the kind neighbor.

In the very short 2003 paper A simple algorithm for edge-coloring bipartite multigraphs, Information Processing Letters 85 (2003), 301-302, Noga Alon used a similar idea for algorithmic purposes. (He also observed the connection to the camel riddle). Here is how the extra camel idea is used for:

Theorem:  A bipartite cubic graph $G$ has a perfect matching.

(A cubic graph is a  3-regular graph.)

Proof: Suppose that $G$ has $n$ vertices. Multiply each edge $r$ times ($r$ large) so that the degree of each vertex $3r$ is of the form $2^m-1$. Now ask your neighbor to give you an additional perfect matching and add it to the graph which now is regular of degree $2^{m}$ . The new graph has an Eulerian cycle. (If not connected, every connected component has an Eulerian cycle.) When we walk on the Eulerian cycle and take either the even edges or the odd edges we get two subraphs of degree $2^{m-1}$.  At least one of them does not use all the edges of the neighbor. We move to this subgraph and give the unused edge back to the neighbor.  We repeat, and in each step we move to a regular subgraph of degree  a smaller power of two, and give back at least one edge to the kind neighbor. If $r$ is large enough to start with we will end with a perfect matching that uses only the original edges of our graph.

(Remark: We can take $m=n/2$ or $m=n/2+1$. If we are a little more careful and in each step try to give many edges back to the kind neighbor we can use $m=\log n$ or so.)

by Gil Kalai at February 16, 2017 07:01 PM UTC

### TR17-025 | Pseudorandom Generators for Low-Sensitivity Functions | Pooya Hatami, Avishay Tal

from ECCC papers

A Boolean function is said to have maximal sensitivity $s$ if $s$ is the largest number of Hamming neighbors of a point which differ from it in function value. We construct a pseudorandom generator with seed-length $2^{O(\sqrt{s})} \cdot \log(n)$ that fools Boolean functions on $n$ variables with maximal sensitivity at most $s$. Prior to our work, the best pseudorandom generators for this class of functions required seed-length $2^{O(s)} \cdot \log(n)$.

### Liberatus Wins at Poker

 Tuomas Sandholm (center) and Ph.D. student Noam Brown (via CMU)
Congratulations to Liberatus the new poker champ. Liberatus, an AI program, beat several top-ranked players in heads-up (two player) no-limit Texas hold 'em.

For those unfamiliar with Texas hold 'em
Two cards, known as the hole cards or hold cards, are dealt face down to each player, and then five community cards are dealt face up in three stages. The stages consist of a series of three cards ("the flop"), later an additional single card ("the turn") and a final card ("the river"). Each player seeks the best five card poker hand from the combination of the community cards and their own hole cards. Players have betting options to check, call, raise or fold. Rounds of betting take place before the flop is dealt, and after each subsequent deal.
Unlike the computers that defeated the best humans in chess, Jeopardy and go, Liberatus comes directly from academia, from Tuomas Sandholm and his student Noam Brown at Carnegie-Mellon.

Unlike chess and go, poker is a game of incomplete information in many forms.
• Information both players have: the community cards already played.
• Information only one player has: the hole card
• Information neither player has: the community cards yet to be played.
Betting in poker plays the primary role of raising the stakes but betting can also signal what hole cards you have. Players can bluff (betting large amounts without a corresponding strong hand), trying to cause other players to misread the signal. There is no perfect play in poker, just a mixed equilibrium though we still don't know how to compute the equilibrium and even if we could we might deviate from the equilibrium to gain an advantage. Deviating also make you vulnerable.

All of this makes poker a far more complicated game for computers to tackle. But through persistence and new tools in machine learning, Sandholm and Brown have found success.

If history holds up, it won't be long before we have champion-caliber poker apps on our phones. Will we see cheating like has been happening in chess? Will online poker sites just disappear?

What is the next great game to fall to computers? I'm guessing NASCAR.

by Lance Fortnow (noreply@blogger.com) at February 16, 2017 12:51 PM UTC

### TR17-024 | Query-to-Communication Lifting for P^NP | Thomas Watson, Mika Göös, Pritish Kamath, Toniann Pitassi

from ECCC papers

We prove that the $\text{P}^{\small\text{NP}}$-type query complexity (alternatively, decision list width) of any boolean function $f$ is quadratically related to the $\text{P}^{\small\text{NP}}$-type communication complexity of a lifted version of $f$. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to capture $\text{P}^{\small\text{NP}}$ communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).

### A parallel implementation of the Synchronised Louvain method

Authors: Benjamin Chiêm, Andine Havelange, Paul Van Dooren