ACAC '18

Abstract: Assume that the members of a society of individuals are given the chance to express an opinion on a multiplicity of issues. The opinion of an individual on an issue can take one of several values, however only certain combinations of an individual’s opinions on the issues are considered to be rational. Given the set of rational combinations, can we efficiently decide whether any collection of such combinations by the individuals can be aggregated into a single rational combination in a way that avoids proclaiming one particular individual as a dictator and always following their opinion?

Joint work with Phokion Kolaitis and John Livieratos

Abstract: Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: owners (operators) of the network and users of the network. Owners of the network post a price for usage of the link they own so as to attract users and maximize profit; users of the network select routes based on price and level of use by other users. We point out that an equilibrium in these games may not exist, may not be unique and may induce an arbitrarily inefficient network performance. Our main result is to observe that a simple regulation on the network owners market solves all three issues above. Specifically, if an authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge, then: the game among the link operators has a unique and strong Nash equilibrium and the users' game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls. As a secondary objective, we want to compute great tolls that minimize total users' payments and we provide a linear program that does this. We obtain multiplicative approximation results compared to the optimal total users' payments for arbitrary networks with polynomial latencies of bounded degree, while in the single-commodity case we obtain a bound that only depends on the topology of the network. Lastly, we show how the same mechanism of setting appropriate caps on the allowable prices extends to the model of elastic demands.

Abstract: We study a beyond worst-case analysis framework known as stability and perturbation resilience, introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A combinatorial optimization problem is $\gamma$-stable or $\gamma$-perturbation-resilient if the optimal solution does not change when we perturb all parameters of the problem by a factor of at most $\gamma$. In this talk, we start with a brief survey of known results in the area, and then present exact polynomial-time algorithms for stable instances of Edge/Node Multiway Cut and Independent Set. We then proceed to explore the power of convex relaxations for solving stable instances of combinatorial optimization problems. We conclude with several hardness results for stable instances of covering problems.

Based on joint works with Konstantin Makarychev and Yury Makarychev, and Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis and Chen Dan.

Abstract: Prefetching constitutes a valuable tool toward efficient Web surfing. As a result, estimating the amount of resources that need to be preloaded during a surfer's browsing becomes an important task. In this regard, prefetching can be modeled as a two-player combinatorial game [Fomin et al., Theoretical Computer Science 2014], where a surfer and a marker alternately play on a given graph (representing the Web graph). During its turn, the marker chooses a set of $k$ nodes to mark (prefetch), whereas the surfer, represented as a token resting on graph nodes, moves to a neighboring node (Web resource). The surfer's objective is to reach an unmarked node before all nodes become marked and the marker wins. Intuitively, since the surfer is step-by-step traversing a subset of nodes in the Web graph, a satisfactory prefetching procedure would load in cache all resources lying in the neighborhood of this growing subset. Motivated by the above, we consider the following problem to which we refer to as the Maximum Rooted Connected Expansion (MRCE) problem. Given a graph $G$ and a root node $v_0$, we wish to find a subset of vertices $S$ such that $S$ is connected, $S$ contains $v_0$ and the ratio $|N[S]|/|S|$ is maximized, where $N[S]$ denotes the closed neighborhood of $S$, that is, $N[S]$ contains all nodes in $S$ and all nodes with at least one neighbor in $S$. We prove that the problem is NP-hard even when the input graph $G$ is restricted to be a split graph. On the positive side, we demonstrate a polynomial time approximation scheme for split graphs. Furthermore, we present a $\frac{1}{6}(1-\frac{1}{e})$-approximation algorithm for general graphs based on techniques for the Budgeted Connected Domination problem [Khuller et al., SODA 2014]. Finally, we provide a polynomial-time algorithm for the special case of interval graphs.

Joint work with R. Martin, S. Schewe, I. Sigalas, V. Zissimopoulos

Abstract:The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called links. The task is to find a set of links, of minimum size, whose addition to the tree leads to a 2-edge-connected graph. A long line of results on TAP culminated in the previously best known approximation guarantee of 1.5. We show that an approximation factor below 1.5 can be achieved, by presenting a 1.458-approximation that is based on several new techniques.

Abstract:When a company undergoes a merger or transfer of its ownership, the existing governing body has an opinion on which buyer should take over as the new owner. Similar situations occur while assigning the host of big sports tournaments, e.g., the World Cup or the Olympics. In all these settings, the values of the external bidders are as important as the internal experts' opinions. Motivated by such questions, we consider a social welfare maximizing approach to design and analyze truthful mechanisms in these settings. We consider the problem with one expert and two bidders and provide tight approximation guarantees of the optimal social welfare. Since this problem is a combination of mechanism design with and without monetary transfers (payments can be imposed to the bidders but not to the expert), classical solutions like VCG cannot be applied, making this a novel mechanism design problem. We distinguish between mechanisms that use ordinal and cardinal information, as well as between mechanisms that base their decisions on one of the two sides (either the bidders or the expert) or both. Our analysis shows that the cardinal setting is quite rich and admits several non-trivial randomized truthful mechanisms, and also allows for closer-to-optimal-welfare guarantees.

Abstract: Suppose that $X=(X_1,...,X_n)$ follows a multivariate normal distribution with precision matrix Q and G(V,E) is the underlying graph of Q, i.e., an edge ij belongs in E if and only if $q_{ij}$ is not zero. We give randomised algorithms that recover efficiently the graph G, under some graph theoretic assumptions. Moreover, we give lower bounds on the number of pairwise correlations needed to recover G. We pursue to extend our results to more general classes of graphs.

This is joint (and ongoing) work with Gábor Lugosi, Jakub Truszkowski, and Piotr Zwiernik.

Abstract:Local Differential Privacy has recently attracted much attention as a privacy metric in the local model, in which each user adds noise to his own personal data by himself and the data aggregator estimates the statistics of the personal data such as a distribution underlying the data. Local Differential Privacy provides a privacy guarantee against adversaries with arbitrary background knowledge, and does not suffer from a possibility of data leakage. It is very useful in practice because users don't need to trust the data aggregator to be willing to give their data.

Abstract: We consider a discriminative learning problem in which the regression function is a convex combination of k linear classifiers of dimension d. This is motivated both by a classifier mixture setting as well as by the identifiability of a 2-layer neural network. We study two problems related by this setting: (a) learning the subspace spanned by the k classifiers, which can be used for dimensionality reduction, and (b) learning the classifier parameters themselves, i.e., solving the full regression problem. For the first problem, we develop a simple algorithm based on the principal Hessian directions method and a "mirroring" trick; under a probabilistic assumption on the feature vector distribution, we prove that this approach has nearly optimal $(O(d))$ statistical efficiency. For the second problem, we provide an algorithm that retrieves the classifier parameter vectors by clustering estimates of the regression function's gradient. Combining the two algorithms yields an algorithm learning classifier parameters with $O(d)+e^{\Theta(poly(k))}$ sample complexity.

This is joint work with Yuekai Sun and Andrea Montanari.

Abstract: We consider the problem of scheduling a set of malleable jobs on uniform/unrelated machines, minimizing the makespan of the produced schedule. Unlike the classical parallel scheduling where every job is assigned to a specific machine, in the malleable setting, every job is assigned to a subset of machines where it is executed non-preemptively and in unison, i.e., the starting and ending time of a job is the same on every machine it is executed on. We propose LP-based O(1)-approximation algorithms for: (a) the case of uniform machines, where every machine is associated with some speed, and (b) the case of unrelated machines, where the speed of each machine is job-dependent.

Joint work with Evdokia Nikolova, Dimitris Fotakis and Jannik Matuschke.

Abstract:Given a rooted point set P , the rooted y−Monotone Minimum Spanning Tree (rooted y−MMST) of P is the spanning geometric graph of P in which all the vertices are connected to the root by some y−monotone path and the sum of the Euclidean lengths of its edges is the minimum. We show that the maximum degree of a rooted y−MMST is not bounded by a constant number. We give a linear time algorithm that draws any rooted tree as a rooted y−MMST and also show that there exist rooted trees that can be drawn as rooted y−MMSTs only in a grid of exponential area.

Abstract:We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents, so that every agent finds her piece at least as valuable as every other agent's piece. The problem has had an interesting history so far. Although the case of three agents is solvable with less than 15 queries, for four agents no bounded procedure was known until the recent breakthroughs of Aziz and Mackenzie (STOC 2016, FOCS 2016). The main drawback of these new algorithms, however, is that they are quite complicated and with a very high query complexity. With four agents, the number of queries required is close to 600. In this work we provide an improved algorithm for four agents, which reduces the current complexity by a factor of 3.4. Our algorithm builds on the approach of Aziz and Mackenzie (STOC 2016) by incorporating new insights and simplifying several steps. Overall, this yields an easier to grasp procedure with lower complexity.

Abstract:Consider the following Stochastic Score Classification Problem. A doctor is assessing a patient's risk of developing a certain disease, and can perform $n$ tests on the patient. Each test has a binary outcome, positive or negative. A positive test result is an indication of risk, and a patient's score is the total number of positive test results. The doctor needs to classify the patient into one of $B$ risk classes, depending on the score (e.g., LOW, MEDIUM, and HIGH risk). Each of these classes corresponds to a contiguous range of scores. Test $i$ has probability $p_i$ of being positive, and it costs $c_i$ to perform the test. To reduce costs, instead of performing all tests, the doctor will perform them sequentially and stop testing when it is possible to determine the risk category for the patient. The problem is to determine the order in which the doctor should perform the tests, so as to minimize the expected testing cost. We provide approximation algorithms for adaptive and non-adaptive versions of this problem, and pose a number of open questions.

Abstract:The area of boolean satisfiability and SAT solvers has seen dramatic advances in the past two decades. A recent trend in SAT solving is an attempt to combine the stengths of symbolic computation tools with the power of SAT solvers, in order to improve their effectiveness and to build custom-tailored SAT solvers for hard combinatorial problems. We will describe our work in this context, with a focus on some particularly hard combinatorial problems, described via autocorrelation of finite sequences.

Based on joint work with Vijay Ganesh (University of Waterloo) and Curtis Bright (University of Waterloo) in the context of the Horizon 2020 EU project "Satisfiability Checking and Symbolic Computation" (SC^2).

Abstract:Banach’s fixed point theorem has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach’s theorem limited. Our first result is a strong converse of Banach’s theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to. We next consider the computational complexity of Banach’s fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach’s fixed point theorem is CLS-complete. We thus provide the first natural complete problem for the class CLS, which was defined in [DP11].