Theory of Computing Blog Aggregator

GAMES/EC 2016

This week I report from Maastricht in the Netherlands from the GAMES 2016, the 5th World Congress of the Game Theory Society. By having their congress every four years, everyone who is anyone in the game theory community makes a strong effort to be here, including three Nobel laureates, Robert Aumann, Roger Myerson and Eric Maskin. The conference has about 750 participants and up to 19 parallel sessions.

This year the conference is co-located with the Economics and Computation conference that comes more from the CS community. By co-located we are sharing the same buildings and many of the events, effectively one larger conference (which means in reality 21 parallel sessions).

EC keeps growing, accepting 80 papers out of 242 submissions, all of which are freely downloadable.

My favorite EC talk was the best student paper, Deferred Acceptance with Compensation Chains by
Piotr Dworczak, a graduate student in the Stanford Business School. He gives an algorithm for finding stable matchings with the property that every stable matching can be found by changing the order that the agents get to choose. The paper Which Is the Fairest (Rent Division) of Them All? by
Kobi Gal, Moshe Mash, Ariel Procaccia and Yair Zick won best paper.

Also a shout out to the talk Cadet-Branch Matching in a Quasi-Linear Labor Market solely authored by Ravi Jagadeesan, a rising junior undergraduate at Harvard. I went to grad school with Ravi's mother Lalita, and yes that makes me feel old.

Tim Roughgarden gave the Kalai prize talk for his work on Intrinsic Robustness of the Price of Anarchy. The talk, attended by a good number of the game theorists, gave a general approach to generalizing bounds price of anarchy results to broader classes of equilibria. Tim followed Keith Chen who heads the analytic team for Uber and discussed how game theory and optimization ideas are driving a major e-commerce company. No major surprises but here's one trade secret: Uber covers its maps with hexagons while Lyft uses squares.

All is all a great week, with packed schedules and crowded activities, but great to see all these game theorists and computer scientists talking with each other.

by Lance Fortnow (noreply@blogger.com) at July 28, 2016 05:55 AM UTC

Counting matchings with k unmatched vertices in planar graphs

Abstract: We consider the problem of counting matchings in planar graphs. While perfect matchings in planar graphs can be counted by a classical polynomial-time algorithm, the problem of counting all matchings (possibly containing unmatched vertices, also known as defects) is known to be #P-complete on planar graphs. To interpolate between the hard case of counting matchings and the easy case of counting perfect matchings, we study the parameterized problem of counting matchings with exactly k unmatched vertices in a planar graph G, on input G and k. This setting has a natural interpretation in statistical physics, and it is a special case of counting perfect matchings in k-apex graphs (graphs that can be turned planar by removing at most k vertices).

Starting from a recent #W[1]-hardness proof for counting perfect matchings on k-apex graphs, we obtain that counting matchings with k unmatched vertices in planar graphs is #W[1]-hard. In contrast, given a plane graph G with s distinguished faces, there is an $O(2^s \cdot n^3)$ time algorithm for counting those matchings with k unmatched vertices such that all unmatched vertices lie on the distinguished faces. This implies an $f(k,s)\cdot n^{O(1)}$ time algorithm for counting perfect matchings in k-apex graphs whose apex neighborhood is covered by s faces.

Suffix arrays with a twist

Authors: Tomasz Kowalski, Szymon Grabowski, Kimmo Fredriksson, Marcin Raniszewski
Abstract: The suffix array is a classic full-text index, combining effectiveness with simplicity. We discuss three approaches aiming to improve its efficiency even more: changes to the navigation, data layout and adding extra data. In short, we show that $(i)$ how we search for the right interval boundary impacts significantly the overall search speed, $(ii)$ a B-tree data layout easily wins over the standard one, $(iii)$ the well-known idea of a lookup table for the prefixes of the suffixes can be refined with using compression, $(iv)$ caching prefixes of the suffixes in a helper array can pose a(nother) practical space-time tradeoff.

Computing exponentially faster: Implementing a nondeterministic universal Turing machine using DNA

Authors: Andrew Currin, Konstantin Korovin, Maria Ababi, Katherine Roper, Douglas B. Kell, Philip J. Day, Ross D. King
Abstract: The theory of computer science is based around Universal Turing Machines (UTMs): abstract machines able to execute all possible algorithms. Modern digital computers are physical embodiments of UTMs. The nondeterministic polynomial (NP) time complexity class of problems is the most significant in computer science, and an efficient (i.e. polynomial P) way to solve such problems would be of profound economic and social importance. By definition nondeterministic UTMs (NUTMs) solve NP complete problems in P time. However, NUTMs have previously been believed to be physically impossible to construct. Thue string rewriting systems are computationally equivalent to UTMs, and are naturally nondeterministic. Here we describe the physical design for a NUTM that implements a universal Thue system. The design exploits the ability of DNA to replicate to execute an exponential number of computational paths in P time. Each Thue rewriting step is embodied in a DNA edit implemented using a novel combination of polymerase chain reactions and site-directed mutagenesis. We demonstrate that this design works using both computational modelling and in vitro molecular biology experimentation. The current design has limitations, such as restricted error-correction. However, it opens up the prospect of engineering NUTM based computers able to outperform all standard computers on important practical problems.

Algorithmic statistics: forty years later

Authors: Nikolai Vereshchagin, Alexander Shen
Abstract: Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some statistical models are better than others. After this notion of a "good model" is introduced, a natural question arises: it is possible that for some piece of data there is no good model? If yes, how often these bad ("non-stochastic") data appear "in real life"?

Another, more technical motivation comes from algorithmic information theory. In this theory a notion of complexity of a finite object (=amount of information in this object) is introduced; it assigns to every object some number, called its algorithmic complexity (or Kolmogorov complexity). Algorithmic statistic provides a more fine-grained classification: for each finite object some curve is defined that characterizes its behavior. It turns out that several different definitions give (approximately) the same curve.

In this survey we try to provide an exposition of the main results in the field (including full proofs for the most important ones), as well as some historical comments. We assume that the reader is familiar with the main notions of algorithmic information (Kolmogorov complexity) theory.

Minmax Tree Facility Location and Sink Evacuation with Dynamic Confluent Flows

Authors: Di Chen, Mordecai Golin
Abstract: Let $G=(V,E)$ be a graph modelling a building or road network in which edges have-both travel times (lengths) and capacities associated with them. An edge's capacity is the number of people that can enter that edge in a unit of time.

In emergencies, people evacuate towards the exits. If too many people try to evacuate through the same edge, congestion builds up and slows down the evacuation.

Graphs with both lengths and capacities are known as Dynamic Flow networks. An evacuation plan for $G$ consists of a choice of exit locations and a partition of the people at the vertices into groups, with each group evacuating to the same exit. The evacuation time of a plan is the time it takes until the last person evacuates. The $k$-sink evacuation problem is to provide an evacuation plan with $k$ exit locations that minimizes the evacuation time. It is known that this problem is NP-Hard for general graphs but no polynomial time algorithm was previously known even for the case of $G$ a tree. This paper presents an $O(n k^2 \log^5 n)$ algorithm for the $k$-sink evacuation problem on trees. Our algorithms also apply to a more general class of problems, which we call minmax tree facility location.

On maximizing a monotone k-submodular function subject to a matroid constraint

Authors: Shinsaku Sakaue
Abstract: A $k$-submodular function is an extension of a submodular function in that its input is given by $k$ disjoint subsets instead of a single subset. For unconstrained nonnegative $k$-submodular maximization, Ward and \v{Z}ivn\'y proposed a constant-factor approximation algorithm, which was improved by the recent work of Iwata, Tanigawa and Yoshida presenting a $1/2$-approximation algorithm. Iwata et al. also provided a $k/(2k-1)$-approximation algorithm for monotone $k$-submodular maximization and proved that its approximation ratio is asymptotically tight. More recently, Ohsaka and Yoshida proposed constant-factor algorithms for monotone $k$-submodular maximization with several size constraints. However, while submodular maximization with various constraints has been extensively studied, no approximation algorithm has been developed for constrained $k$-submodular maximization, except for the case of size constraints. In this paper, we prove that a greedy algorithm outputs a $1/2$-approximate solution for monotone $k$-submodular maximization with a matroid constraint. The algorithm runs in $O(M|E|(\text{MO} + k\text{EO}))$ time, where $M$ is the size of an optimal solution, $|E|$ is the size of the ground set, and $\text{MO}, \text{EO}$ represent the time for the membership oracle of the matroid and the evaluation oracle of the $k$-submodular function, respectively.

A note on "Approximation schemes for a subclass of subset selection problems", and a faster FPTAS for the Minimum Knapsack Problem

Authors: Cédric Bentz, Pierre Le Bodic
Abstract: Pruhs and Woeginger prove the existence of FPTAS's for a general class of minimization and maximization subset selection problems. Without losing generality from the original framework, we prove how better asymptotic worst-case running times can be achieved if a $\rho$-approximation algorithm is available, and in particular we obtain matching running times between maximization and minimization subset selection problems. We directly apply this result to the Minimum Knapsack Problem, for which the original framework yields an FPTAS with running time $O(n^5/\epsilon)$, where $\epsilon$ is the required accuracy and $n$ is the number of items, and obtain an FPTAS with running time $O(n^3/\epsilon)$, thus improving the running time by a quadratic factor in the worst case.

Approximation and Parameterized Complexity of Minimax Approval Voting

Authors: Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat
Abstract: We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance $d$ from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in time $\mathcal{O}^\star(2^{o(d\log d)})$, unless the Exponential Time Hypothesis (ETH) fails. This means that the $\mathcal{O}^\star(d^{2d})$ algorithm of Misra et al. [AAMAS 2015] is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time $\mathcal{O}^\star(\left({3}/{\epsilon}\right)^{2d})$, which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for Minimax Approval Voting, which runs in time $n^{\mathcal{O}(1/\epsilon^2 \cdot \log(1/\epsilon))} \cdot \mathrm{poly}(m)$, almost matching the running time of the fastest known PTAS for Closest String due to Ma and Sun [SIAM J. Comp. 2009].

Fast Global Convergence of Online PCA

Authors: Zeyuan Allen-Zhu, Yuanzhi Li
Abstract: We study online principle component analysis (PCA), that is to find the top $k$ eigenvectors of a $d\times d$ hidden matrix $\bf \Sigma$ with online data samples drawn from covariance matrix $\bf \Sigma$. We provide $global$ convergence for the low-rank generalization of Oja's algorithm, which is popularly used in practice but lacks theoretical understanding.

Our convergence rate matches the lower bound in terms of the dependency on error, on eigengap and on dimension $d$; in addition, our convergence rate can be made gap-free, that is proportional to the approximation error and independent of the eigengap.

In contrast, for general rank $k$, before our work (1) it was open to design any algorithm with efficient global convergence rate; and (2) it was open to design any algorithm with (even local) gap-free convergence rate.

Computing the k Nearest-Neighbors for all Vertices via Dijkstra

Authors: Sariel Har-Peled
Abstract: We are given a directed graph $G = (V,E)$ with $n$ vertices and $m$ edges, with positive weights on the edges, and a parameter $k >0$. We show how to compute, for every vertex $v \in V$, its $k$ nearest-neighbors. The algorithm runs in $O( k ( n \log n + m ) )$ time, and follows by a somewhat careful modification of Dijkstra's shortest path algorithm.

This result is probably folklore, but we were unable to find a reference to it -- thus, this note.

Finding Detours is Fixed-parameter Tractable

Authors: Ivona Bezáková, Radu Curticapean, Holger Dell, Fedor V. Fomin
Abstract: We consider the following natural "above guarantee" parameterization of the classical Longest Path problem: For given vertices s and t of a graph G, and an integer k, the problem Longest Detour asks for an (s,t)-path in G that is at least k longer than a shortest (s,t)-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parameter tractable (FPT) on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time exp(O(k)) poly(n). This matches (up to the base of the exponential) the best algorithms for finding a path of length at least k.

Furthermore, we study the related problem Exact Detour that asks whether a graph G contains an (s,t)-path that is exactly k longer than a shortest (s,t)-path. For this problem, we obtain a randomized algorithm with running time about 2.746^k, and a deterministic algorithm with running time about 6.745^k, showing that this problem is FPT as well. Our algorithms for Exact Detour apply to both undirected and directed graphs.

Complexity of Token Swapping and its Variants

Authors: Édouard Bonnet, Tillmann Miltzow, Paweł Rzążewski
Abstract: In the Token Swapping problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is $W[1]$-hard parameterized by the length $k$ of a shortest sequence of swaps. In fact, we prove that, for any computable function $f$, it cannot be solved in time $f(k)n^{o(k / \log k)}$ where $n$ is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial $n^{O(k)}$-time algorithm.

We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have different colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes.

Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases.

A Selectable Sloppy Heap

Abstract: We study the selection problem, namely that of computing the $i$th order statistic of $n$ given elements. Here we offer a data structure handling a dynamic version in which upon request: (i)~a new element is inserted or (ii)~an element of a prescribed quantile group is deleted from the data structure. Each operation is executed in (ideal!) constant time---and is thus independent of $n$ (the number of elements stored in the data structure). The design demonstrates how slowing down a certain computation can reduce the response time of the data structure.

A Scalable Algorithm for Tracking an Unknown Number of Targets Using Multiple Sensors

Authors: Florian Meyer, Paolo Braca, Peter Willett, Franz Hlawatsch
Abstract: We propose a method for tracking an unknown number of targets based on measurements provided by multiple sensors. Our method achieves low computational complexity and excellent scalability by running belief propagation on a suitably devised factor graph. A redundant formulation of data association uncertainty and the use of "augmented target states" including binary target indicators make it possible to exploit statistical independencies for a drastic reduction of complexity. An increase in the number of targets, sensors, or measurements leads to additional variable nodes in the factor graph but not to higher dimensions of the messages. As a consequence, the complexity of our method scales only quadratically in the number of targets, linearly in the number of sensors, and linearly in the number of measurements per sensors. The performance of the method compares well with that of previously proposed methods, including methods with a less favorable scaling behavior. In particular, our method can outperform multisensor versions of the probability hypothesis density (PHD) filter, the cardinalized PHD filter, and the multi-Bernoulli filter.

Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios

Authors: Christos Kalaitzis, Ola Svensson, Jakub Tarnawski
Abstract: We consider the classic problem of scheduling jobs on unrelated machines so as to minimize the weighted sum of completion times. Recently, for a small constant $\varepsilon >0$, Bansal et al. gave a $(3/2-\varepsilon)$-approximation algorithm improving upon the natural barrier of $3/2$ which follows from independent randomized rounding. In simplified terms, their result is obtained by an enhancement of independent randomized rounding via strong negative correlation properties.

In this work, we take a different approach and propose to use the same elegant rounding scheme for the weighted completion time objective as devised by Shmoys and Tardos for optimizing a linear function subject to makespan constraints. Our main result is a $1.21$-approximation algorithm for the natural special case where the weight of a job is proportional to its processing time (specifically, all jobs have the same Smith ratio), which expresses the notion that each unit of work has the same weight. In addition, as a direct consequence of the rounding, our algorithm also achieves a bi-criteria $2$-approximation for the makespan objective. Our technical contribution is a tight analysis of the expected cost of the solution compared to the one given by the Configuration-LP relaxation - we reduce this task to that of understanding certain worst-case instances which are simple to analyze.

Low-Congestion Shortcuts without Embedding

Authors: Bernhard Haeupler, Taisuke Izumi, Goran Zuzic
Abstract: Distributed optimization algorithms are frequently faced with solving sub-problems on disjoint connected parts of a network. Unfortunately, the diameter of these parts can be significantly larger than the diameter of the underlying network, leading to slow running times. Recent work by [Ghaffari and Hauepler; SODA'16] showed that this phenomenon can be seen as the broad underlying reason for the pervasive $\Omega(\sqrt{n} + D)$ lower bounds that apply to most optimization problems in the CONGEST model. On the positive side, this work also introduced low-congestion shortcuts as an elegant solution to circumvent this problem in certain topologies of interest. Particularly, they showed that there exist good shortcuts for any planar network and more generally any bounded genus network. This directly leads to fast $O(D \log^{O(1)} n)$ distributed algorithms for MST and Min-Cut approximation, given that one can efficiently construct these shortcuts in a distributed manner.

Unfortunately, the shortcut construction of [Ghaffari and Hauepler; SODA'16] relies heavily on having access to a genus embedding of the network. Computing such an embedding distributedly, however, is a hard problem - even for planar networks. No distributed embedding algorithm for bounded genus graphs is in sight.

In this work, we side-step this problem by defining a restricted and more structured form of shortcuts and giving a novel construction algorithm which efficiently finds a shortcut which is, up to a logarithmic factor, as good as the best shortcut that exists for a given network. This new construction algorithm directly leads to an $O(D \log^{O(1)} n)$-round algorithm for solving optimization problems like MST for any topology for which good restricted shortcuts exist - without the need to compute any embedding. This includes the first efficient algorithm for bounded genus graphs.

Quantum Advantage on Information Leakage for Equality

Authors: Juan Miguel Arrazola, Dave Touchette
Abstract: We prove a lower bound on the information leakage of any classical protocol computing the equality function in the simultaneous message passing (SMP) model. Our bound is valid in the finite length regime and is strong enough to demonstrate a quantum advantage in terms of information leakage for practical quantum protocols. We prove our bound by obtaining an improved finite size version of the communication bound due to Babai and Kimmel, relating randomized communication to deterministic communication in the SMP model. We then relate information leakage to randomized communication through a series of reductions. We first provide alternative characterizations for information leakage, allowing us to link it to average length communication while allowing for shared randomness (pairwise, with the referee). A Markov inequality links this with bounded length communication, and a Newman type argument allows us to go from shared to private randomness. The only reduction in which we incur more than a logarithmic additive factor is in the Markov inequality; in particular, our compression method is essentially tight for the SMP model with average length communication.

A Hierarchy of Lower Bounds for Sublinear Additive Spanners

Authors: Amir Abboud, Greg Bodwin, Seth Pettie
Abstract: Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say $\tilde{O}(n^{1+\delta})$ bits. There is an inherent tradeoff between the sparsity parameter $\delta$ and the stretch function $f$ of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem.

In this paper we show that the recent additive spanner lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that fully characterize the asymptotic behavior of the optimal stretch function $f$ as a function of $\delta \in (0,1/3)$. Specifically, for any integer $k\ge 2$, any compression scheme with size $O(n^{1+\frac{1}{2^k-1} - \epsilon})$ has a sublinear additive stretch function $f$: $$f(d) = d + \Omega(d^{1-\frac{1}{k}}).$$ This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's $(1+\epsilon,\beta)$-spanners have an essentially optimal tradeoff between $\delta,\epsilon,$ and $\beta$, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal.

To complement these lower bounds we present a new construction of $(1+\epsilon, O(k/\epsilon)^{k-1})$-spanners with size $O((k/\epsilon)^{h_k} kn^{1+\frac{1}{2^{k+1}-1}})$, where $h_k < 3/4$. This size bound improves on the spanners of Elkin and Peleg (2004), Thorup and Zwick (2006), and Pettie (2009). According to our lower bounds neither the size nor stretch function can be substantially improved.

postdoc at Ulm University (apply by September 2016)

from CCI: jobs

A postdoc position for up to 2 years is available with Thomas Thierauf at Ulm University, Germany. The starting date is ideally in October 2016, but can be slightly shifted to a later point.
Topic is complexity theory, with a focus on Polynomial Identity Testing (PIT) and related subjects.

Email: thomas.thierauf@uni-ulm.de

by theorycsjobs at July 26, 2016 03:06 PM UTC

Polynomial Time Algorithm for $2$-Stable Clustering Instances

Abstract: Clustering with most objective functions is NP-Hard, even to approximate well in the worst case. Recently, there has been work on exploring different notions of stability which lend structure to the problem. The notion of stability, $\alpha$-perturbation resilience, that we study in this paper was originally introduced by Bilu et al.~\cite{Bilu10}. The works of Awasthi et al~\cite{Awasthi12} and Balcan et al.~\cite{Balcan12} provide a polynomial time algorithm for $3$-stable and $(1+\sqrt{2})$-stable instances respectively. This paper provides a polynomial time algorithm for $2$-stable instances, improving on and answering an open question in ~\cite{Balcan12}.

Unfolding Convex Polyhedra via Radially Monotone Cut Trees

Authors: Joseph O'Rourke
Abstract: A notion of "radially monotone" cut paths is introduced as an effective choice for finding a non-overlapping edge-unfolding of a convex polyhedron. These paths have the property that the two sides of the cut avoid overlap locally as the cut is infinitesimally opened by the curvature at the vertices along the path. It is shown that a class of planar, triangulated convex domains always have a radially monotone spanning forest, a forest that can be found by an essentially greedy algorithm. This algorithm can be mimicked in 3D and applied to polyhedra inscribed in a sphere. Although the algorithm does not provably find a radially monotone cut tree, it in fact does find such a tree with high frequency, and after cutting unfolds without overlap. This performance of a greedy algorithm leads to the conjecture that spherical polyhedra always have a radially monotone cut tree and unfold without overlap.

Unique Set Cover on Unit Disks and Unit Squares

Authors: Saeed Mehrabi
Abstract: We study the Unique Set Cover problem on unit disks and unit squares. For a given set $P$ of $n$ points and a set $D$ of $m$ geometric objects both in the plane, the objective of the Unique Set Cover problem is to select a subset $D'\subseteq D$ of objects such that every point in $P$ is covered by at least one object in $D'$ and the number of points covered uniquely is maximized, where a point is covered uniquely if the point is covered by exactly one object in $D'$. In this paper, (i) we show that the Unique Set Cover is NP-hard on both unit disks and unit squares, and (ii) we give a PTAS for this problem on unit squares by applying the mod-one approach of Chan and Hu (Comput. Geom. 48(5), 2015).

Sliding k-Transmitters: Hardness and Approximation

Authors: Therese Biedl, Saeed Mehrabi, Ziting Yu
Abstract: A sliding k-transmitter in an orthogonal polygon P is a mobile guard that travels back and forth along an orthogonal line segment s inside P. It can see a point p in P if the perpendicular from p onto s intersects the boundary of P at most k times. We show that guarding an orthogonal polygon P with the minimum number of k-transmitters is NP-hard, for any fixed k>0, even if P is simple and monotone. Moreover, we give an O(1)-approximation algorithm for this problem.

The Costs and Benefits of Ridesharing: Sequential Individual Rationality and Sequential Fairness

Authors: Ragavendran Gopalakrishnan, Koyel Mukherjee, Theja Tulabandhula
Abstract: We introduce a cost sharing framework for ridesharing that explicitly takes into account the "inconvenience costs" of passengers due to detours. We introduce the notion of "sequential" individual rationality (SIR) that requires that the "disutility" of existing passengers is non-increasing as additional passengers are picked up, and show that these constraints induce a natural limit on the incremental detours permissible as the ride progresses. We provide an exact characterization of all routes for which there exists some cost sharing scheme that is SIR on that route, and under these constraints, for realistic scenarios, we also show a $\Theta(\sqrt{n})$ upper bound and a $\Theta(\log n)$ lower bound on the total detour experienced by the passengers as a fraction of the direct distance to their destination. Next, we observe that under any budget-balanced cost sharing scheme that is SIR on a route, the total amount by which the passengers' disutilities decrease (which can be viewed as the total incremental benefit due to ridesharing) is a constant. This observation inspires a "dual" notion of viewing cost sharing schemes as benefit sharing schemes, under which we introduce a natural definition of "sequential" fairness-the total incremental benefit due to the addition of a new passenger is (partly) shared among the existing passengers in proportion to the incremental inconvenience costs they suffer. We then provide an exact characterization of sequentially fair cost sharing schemes, which brings out several useful structural properties, including a strong requirement that passengers must compensate each other for the detour inconveniences that they cause. Finally, we conclude with an extended discussion of new algorithmic problems related to and motivated by SIR, and important future work.

Covering segments with axis-parallel unit squares

Authors: Ankush Acharyya, Subhas C. Nandy, Supantha Pandit, Sasanka Roy
Abstract: We study various kinds of line segments covering problems with axis-parallel unit squares in two dimensions. A set $S$ of $n$ line segments is given. The objective is to find the minimum number of axis-parallel unit squares which cover at least one end-point of each segment. We may have different variations of this problem depending on the orientation and length of the input segments. We prove some of these problems to be NP-hard, and give constant factor approximation algorithms for those problems. For some variations, we have polynomial time exact algorithms. Further, we show that our problems have connections with the problems studied by Arkin et al. (2015) on conflict-free covering problem. We also improve approximation factors of some of their problems.

Low growth equational complexity

Authors: Marcel Jackson
Abstract: The equational complexity function $\beta_\mathscr{V}:\mathbb{N}\to\mathbb{N}$ of an equational class of algebras $\mathscr{V}$ bounds the size of equation required to determine membership of $n$-element algebras in $\mathscr{V}$. Known examples of finitely generated varieties $\mathscr{V}$ with unbounded equational complexity have growth in $\Omega(n^c)$, usually for $c\geq \frac{1}{2}$. We show that much slower growth is possible, exhibiting $O(\log_2^3(n))$ growth amongst varieties of semilattice ordered inverse semigroups and additive idempotent semirings. We also examine a quasivariety analogue of equational complexity, and show that a finite group has polylogarithmic quasi-equational complexity function, bounded if and only if all Sylow subgroups are abelian.

A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian

Authors: Dana Moshkovitz, Govind Ramnarayan, Henry Yuen
Abstract: In this work we show a barrier towards proving a randomness-efficient parallel repetition, a promising avenue for achieving many tight inapproximability results. Feige and Kilian (STOC'95) proved an impossibility result for randomness-efficient parallel repetition for two prover games with small degree, i.e., when each prover has only few possibilities for the question of the other prover. In recent years, there have been indications that randomness-efficient parallel repetition (also called derandomized parallel repetition) might be possible for games with large degree, circumventing the impossibility result of Feige and Kilian. In particular, Dinur and Meir (CCC'11) construct games with large degree whose repetition can be derandomized using a theorem of Impagliazzo, Kabanets and Wigderson (SICOMP'12). However, obtaining derandomized parallel repetition theorems that would yield optimal inapproximability results has remained elusive.

This paper presents an explanation for the current impasse in progress, by proving a limitation on derandomized parallel repetition. We formalize two properties which we call "fortification-friendliness" and "yields robust embeddings." We show that any proof of derandomized parallel repetition achieving almost-linear blow-up cannot both (a) be fortification-friendly and (b) yield robust embeddings. Unlike Feige and Kilian, we do not require the small degree assumption.

Given that virtually all existing proofs of parallel repetition, including the derandomized parallel repetition result of Dinur and Meir, share these two properties, our no-go theorem highlights a major barrier to achieving almost-linear derandomized parallel repetition.

Exploiting Symmetry and/or Manhattan Properties for 3D Object Structure Estimation from Single and Multiple Images

Authors: Yuan Gao, Alan L. Yuille
Abstract: Many man-made objects have intrinsic symmetries and Manhattan structure. By assuming an orthographic projection model, this paper addresses the estimation of 3D structures and camera projection using symmetry and/or Manhattan structure cues, for the two cases when the input is a single image or multiple images from the same category, e.g. multiple different cars. Specifically, analysis on single image case implies that Manhattan alone is sufficient to recover the camera projection, then the 3D structure can be reconstructed uniquely exploiting symmetry. But Manhattan structure can be hard to observe from single image due to occlusion. Hence, we extend to the multiple image case which can also exploit symmetry but does not require Manhattan axes. We propose a new rigid structure from motion method, exploiting symmetry, using multiple images from the same category as input. Our results on Pascal3D+ dataset show that our methods can significantly outperform baseline methods.

Incremental $2$-Edge-Connectivity in Directed Graphs

Authors: Loukas Georgiadis, Giuseppe F. Italiano, Nikos Parotsidis
Abstract: In this paper, we initiate the study of the dynamic maintenance of $2$-edge-connectivity relationships in directed graphs. We present an algorithm that can update the $2$-edge-connected blocks of a directed graph with $n$ vertices through a sequence of $m$ edge insertions in a total of $O(mn)$ time. After each insertion, we can answer the following queries in asymptotically optimal time: (i) Test in constant time if two query vertices $v$ and $w$ are $2$-edge-connected. Moreover, if $v$ and $w$ are not $2$-edge-connected, we can produce in constant time a "witness" of this property, by exhibiting an edge that is contained in all paths from $v$ to $w$ or in all paths from $w$ to $v$. (ii) Report in $O(n)$ time all the $2$-edge-connected blocks of $G$. To the best of our knowledge, this is the first dynamic algorithm for $2$-connectivity problems on directed graphs, and it matches the best known bounds for simpler problems, such as incremental transitive closure.

Authors: Yara Elias, Pierre McKenzie
Abstract: Given integers d >= 1, and g >= 2, a g-addition chain for d is a sequence of integers a_0=1, a_1, a_2,..., a_{r-1}, a_r=d where a_i=a_{j_1}+a_{j_2}+...+a_{j_k}, with 2 =< k =< g, and 0 =< j_1 =< j_2 =< ... =< j_k =< i-1. The length of a g-addition chain is r, the number of terms following 1 in the sequence. We denote by l_g(d) the length of a shortest addition chain for d. Many results have been established in the case g=2. Our aim is to establish the same sort of results for arbitrary fixed g. In particular, we adapt methods for constructing g-addition chains when g=2 to the case g>2 and we study the asymptotic behavior of l_g.

A Search Algorithm for Simplicial Complexes

Authors: Subhrajit Bhattacharya
Abstract: We present the `Basic S*' algorithm for computing shortest path through a metric simplicial complex. In particular, we consider the Rips complex constructed out of a given metric graph, $G$. Such a complex, and hence shortest paths in it, represent the underlying metric space (whose discrete representation is the graph) more closely than what a graph would do. While discrete graph representations of continuous spaces is convenient for motion planning in configuration spaces of robotic systems, the metric induced in them by the ambient configuration space is different from the metric of the configuration space itself. We remedy this problem using a simplicial complex instead. Our algorithm is local in nature, requiring only an abstract graph, $G=(V,E)$, and a cost/length function, $d:E\rightarrow \mathbb{R}_+$, and no other global information such as an embedding is required. The complexity of our algorithm is comparable to that of Dijkstra's search algorithm, but, as the results presented in this paper demonstrate, the shortest paths obtained using the proposed algorithm represent/approximate the geodesic paths in the original metric space much more closely.

A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees

Authors: Gopal Pandurangan, Peter Robinson, Michele Scquizzato
Abstract: This paper presents a randomized Las Vegas distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in $\tilde{O}(D + \sqrt{n})$ time and exchanges $\tilde{O}(m)$ messages (both with high probability), where $n$ is the number of nodes of the network, $D$ is the diameter, and $m$ is the number of edges. This is the first distributed MST algorithm that matches \emph{simultaneously} the time lower bound of $\tilde{\Omega}(D + \sqrt{n})$ [Elkin, SIAM J. Comput. 2006] and the message lower bound of $\Omega(m)$ [Kutten et al., J.ACM 2015] (which both apply to randomized algorithms).

The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower bound construction that shows one lower bound {\em does not} work for the other. To complement our algorithm, we present a new lower bound graph construction for which any distributed MST algorithm requires \emph{both} $\tilde{\Omega}(D + \sqrt{n})$ rounds and $\Omega(m)$ messages.

Connectivity Oracles for Graphs Subject to Vertex Failures

Authors: Ran Duan, Seth Pettie
Abstract: We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. Our deterministic structure processes a batch of $d\leq d_{\star}$ failed vertices in $\tilde{O}(d^3)$ time and thereafter answers connectivity queries in $O(d)$ time. It occupies space $O(d_{\star} m\log n)$. We develop a randomized Monte Carlo version of our data structure with update time $\tilde{O}(d^2)$, query time $O(d)$, and space $\tilde{O}(m)$ for any $d_{\star}$. This is the first connectivity oracle for general graphs that can efficiently deal with an unbounded number of vertex failures.

Our data structures are based on a new decomposition theorem for an undirected graph $G=(V,E)$, which is of independent interest. It states that for any terminal set $U\subseteq V$ we can remove a set $B$ of $|U|/(s-2)$ vertices such that the remaining graph contains a Steiner forest for $U-B$ with maximum degree $s$.

Pokégyms at Dagstuhl

from The Geomblog

Yes, you read that correctly. The whole of Dagstuhl is now a Pokégym and there are Pokémon wandering the streets of Wadern (conveniently close to the ice cream shop that has excellent ice cream!)

Given this latest advancement, I was reminded of Lance Fortnow's post about Dagstuhl from back in 2008 where he wistfully mourned the fact that Wifi now meant that people don't hang out together.

Times change. I am happy to note that everything else about Dagstuhl hasn't changed that much: we still have the book of handwritten abstracts for one thing.

by Suresh Venkatasubramanian (noreply@blogger.com) at July 25, 2016 11:26 PM UTC

Carl Zimmer's series on exploring his genome

from The Geomblog

If you haven't yet read Carl Zimmer's series of articles (one, two, three), you should go out and read it now!

Because after all, it's Carl Zimmer, one of the best science writers around, especially when it comes to biology.

But even more so because when you read the story of his personal quest to understand his genetic story in all its multifaceted glory, you understand the terrifying opportunities and dangers in the use of genetic information for predictive and diagnostic medicine. You also realize the intricate way that computation is woven into this discovery, and how sequences of seemingly arbitrary choices lead to actual conclusions about your genome that you now have to evaluate for risk and likelihood.

In a sense, this is the tale of the use of all computational approaches right now, whether it be in science, engineering, the social sciences, or yes, even algorithmic fairness. Zimmer uses the analogy with telescopes to describe his attempts to look at his genome, and this explanation is right on the money:
Early telescopes weren’t terribly accurate, either, and yet they still allowed astronomers to discover new planets, galaxies, and even the expansion of the universe. But if your life depended on your telescope — if, for example, you wanted to spot every asteroid heading straight for Earth — that kind of fuzziness wouldn’t be acceptable.
And this quote from Robert Green, one of the geneticists who was helping Zimmer map out his genome:
Ultimately, the more you know, the more frustrating an exercise it is. What seemed to be so technologically clear and deterministic, you realize is going through a variety of filters — some of which are judgments, some of which are flawed databases, some of which are assumptions about frequencies, to get to a best guess.
In this is a message for all of us doing any kind of data mining.

by Suresh Venkatasubramanian (noreply@blogger.com) at July 25, 2016 05:54 PM UTC

Jirka

from Gil Kalai

The Mathematics of Jiří Matoušek is a conference taking place this week at Prague in memory of Jirka Matoušek.  Here are the slides of my planned talk on Maestro Jirka Matoušek. This post presents the opening slides for the conference by Imre Barany.  Unfortunately, at the last minute I had to cancel my own participation. My planned talk is similar to the one devoted to Jirka  that I gave last summer in Budapest. I also wanted to  mention a lovely new theorem related to Tverberg’s theorem by Moshe White.

“The Mathematics of Jiří Matoušek,” Imre Barany’s opening presentation

by Gil Kalai at July 25, 2016 07:50 AM UTC

The Mathematics Of Dan’s Inferno

from Richard Lipton

A possible error with mathematical ramifications

 Non-technical fact-check source

Dan Brown is the bestselling author of the novel The Da Vinci Code. His most recent bestseller, published in 2013, is Inferno. Like two of his earlier blockbusters it has been made into a movie. It stars Tom Hanks and Felicity Jones and is slated for release on October 28.

Today I want to talk about a curious aspect of the book Inferno, since it raises an interesting mathematical question.

Brown’s books are famous for their themes: cryptography, keys, symbols, codes, and conspiracy theories. The first four of these have a distinctive flavor of our field. Although we avoid the last in our work, it is easy to think of possible conspiracies that involve computational theory. How about these: certain groups already can factor large numbers, certain groups have real quantum computers, certain groups have trapdoors in cryptocurrencies, or …

The book has been out for awhile, but I only tried to read it the other day. It was tough to finish so I jumped to the end where the “secret” was exposed. Brown’s works have sold countless copies and yet have been attacked as being poorly written. He must be doing something very right. His prose may not be magical—whose is?—but his plots and the use of his themes usually makes for a terrific “cannot put down” book.

Well I put it down. But I must be the exception. If you haven’t read the book and wish to do so without “spoilers” then you can put down this column.

In The Inferno

The Inferno is about the release of a powerful virus that changes the world. Before I go into the mathematical issues this virus raises I must point out that Brown’s work has often been criticized for making scientific errors and overstepping the bounds of “plausible suspension of disbelief.” I think it is a great honor—really—that so many posts and discussions are around mistakes that he has made. Clearly there is huge interest in his books.

Examples of such criticism of The Inferno have addressed the DNA science involved, the kind of virus used, the hows of genetic engineering and virus detection, and the population projections, some of which we get into below. There is also an entire book about Brown’s novel, Secrets of Inferno

However, none of these seems to address a simple point that we hadn’t found anywhere, until Ken noticed it raised here on the often-helpful FourmiLab site maintained by the popular science writer John Walker. It appears when you click “Show Spoilers” on that page, so again you may stop reading if you don’t wish to know.

How The Virus Works—or Doesn’t?

How does the virus work? The goal of the virus is to stop population explosion.

The book hints that it is airborne, so we may assume that everyone in the world is infected by it—all women in particular. Brown says that 1/3 are made infertile. There are two ways to think about this statement. It depends on the exact definition of the mechanism causing infertility.

The first way is that when you get infected by the virus a coin is flipped and with probability 1/3 you are unable to have children. That is, when the virus attacks your original DNA there is a 1/3 chance the altered genes render you infertile. In the 2/3-case that the virus embeds in a way that does not cause infertility, that gets passed on to children and there is no further effect. In the 1/3-case that the alteration causes infertility, that property too gets passed on. Except, that is, for the issue in this famous quote:

Having Children Is Hereditary: If Your Parents Didn’t Have Any, Then You Probably Won’t Either.

Thus the effect “dies out” almost immediately; it would necessarily be just one-shot on the current generation.

The second way is that the virus allows the initial receiver to be fertile but has its effect when (female) children are born. In one third of cases the woman becomes infertile, and otherwise is able to have children when she grows up.

In this case the effect seems to work as claimed in the book. Children all get the virus and it keeps flipping coins forever. Walker still isn’t sure—we won’t reveal here the words he hides but you can find them. In any event, the point remains that this would become a much more complex virus. And Brown does not explain this point in his book—at least I am unsure if he even sees the necessary distinctions.

The other discussions focus on issues like how society would react to this reduction in fertility. Except for part of one we noted above, however, none seems to address the novel’s mathematical presumptions.

The Math and Aftermath

The purpose of the virus is to reduce the growth rate in the world’s population. By how much is not clear in the book. The over-arching issue is that it is hard to find conditions under which the projection of the effect is stable.

For example, suppose we can divide time into discrete units of generations so that the world population of women after ${t}$ generations follows the exponential growth curve ${N = N_0 r^t}$. Ignoring the natural rate of infertility and male-female imbalance and other factors for simplicity, this envisions ${N}$ women having ${r}$ female children on average. The intent seems to be to replace this with ${2N/3}$ women having ${r}$ female children each, for ${N' = 2rN/3}$ in the next generation. This means multiplying ${N}$ by ${\frac{2}{3}r}$, so

$\displaystyle N'_t = N_0 \left(\frac{2}{3}r\right)^t$

becomes the new curve. The problem is that this tends to zero unless ${r \geq 3/2}$, whereas the estimates of ${r}$ that you can get from tables such as this are uniformly lower at least since 2000.

The point is that the blunt “1/3” factor of the virus is thinking only in such simplistic terms about “exponential growth”—yet in the same terms there is no region of stability. Either growth remains exponential or humanity crashes. Maybe the latter possibility is implicit in the dark allusions to Dante Alighieri’s Inferno that permeate the plot.

In reality, as our source points out, it would not take much for humanity to compensate. If a generation is 30 years and we are missing 33% of women, then what’s needed is for just over 3% of the remaining women to change their minds about not having a child in any given year. We don’t want to trivialize the effect of infertility, but there is much more to adaptability than the book’s tenet presumes.

Open Problems

Have you read the book? What do you think about the math?

The College Issues that are talked about/College issues that are important

The following college issues get lots of attention:

Admissions-  high school students PLAN to do things JUST to get them into an elite college. For example nobody takes the SATs just for the fun of it anymore.

Sports- too much money spend on it?

Sports- the players treated unfairly?

Are other out-of-class activites also an issue? See here.

Jock Culture.

Free speech- Speech codes, triggers. (I've heard this talked about for about 30 years now.)

A  common core. How to make it not just dead white males.

A common core. How to get this to work when profs are overly specialized.

Professors are rewarded for research more than teaching- how to induce them to be better teachers.(I've heard about this one for about 40 years.)

Renaming buildings that are named after racists. ( Byrd Stadium at UMCP is now Maryland Stadium  see here) (If we find out that Fields or Abel was a racist will we rename the awards? Why bother naming things after Justice Scalia or Bobby Kennedy when they will be renamed at some point because of their views on gay people?)

Renaming buildings that are named after the things racists do (see here)

White privilege  (If I was black then whenever my blog had   bad spelling or grammar it would be connected to my race and assumed upbringing.)

The crushing debts of $100,000 or so that some students face after college. (Which is why some students Feel the Bern!, though others Feel the Bern! for different reasons.) Hookup culture on campus Lack of diversity in some majors (I've heard this talked about for about 30 years now.) (Examples: Across the country CS is at around 15% female. Art History is around 80% female. Why does the CS one generate much discussion and some outrage but the art history one... not so much? I would guess jobs. But the point of this list is just that these are the issues people ARE talking about.) Should college be vocational vs intellectual? Are these two disjoint? MOOCS: How will they affect education? These are important issues. But they affect few people. 65% (and dropping) high school seniors goto college. Over 1/2 of all college students go to community college. Many of those students are part timers who also work. Speech codes are not at the top of the things they have to worry about. These people face other problems that do not get attention. See the following excellent articles Shut up abour Harvard by Ben Cassleman and The other 75% by Paul Attewell and David Lavin To give one example: The number of students going to community college who need to take part time jobs to finish and end up with a crushing (to them) debt of$10,000 is a far more common problem then any of the ones above. Why so little coverage?

The articles give other examples of problems that are NOT being talked about.

The other 75% is from the excellent book What is college for edited by Lagemann and Lewis, and reviewed by me, for SIGACT News, here.   Most of the other chapters are about the issues above. We need a book, or at least  a conversation, about issues of education affecting many more people.

The Morrill Land-Grant Acts established many colleges. It was passed in a time when it was realized that its important to have an educated public. It must have been passed in a time where there were not the pressing issues we have today (like bathrooms for transgender people) so they could think about these issues clearly. It was passed in 1862 in the middle of the Civil War.

A meta-thought--- Every comment on this blog about the issues I list above as NOT affecting that many people will prove my point that those issues are discussed far more than issues that affect far more people. Even so, feel free to comment on whatever issues you want.

by GASARCH (noreply@blogger.com) at July 25, 2016 03:34 AM UTC

Colouring on Hereditary Graph Classes Closed under Complementation

Authors: Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma
Abstract: The Colouring problem is that of deciding whether a given graph $G$ admits a (proper) $k$-colouring for a given integer $k$. A graph is $(H_1,H_2)$-free for a pair of graphs $H_1,H_2$ if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. We continue a study into the complexity of Colouring for $(H_1,H_2)$-free graphs. The complement $\bar{H}$ of a graph $H$ has the same vertices as $H$ and an edge between two distinct vertices if and only if these vertices are not adjacent in $H$. By combining new and known results we classify the computational complexity of Colouring for $(H,\bar{H})$-free graphs except when $H=sP_1+P_3$ or $H=sP_1+P_4$ for $s\geq 2$. We also show that these are the only open cases when considering all bigenic graph classes closed under complementation.