ACAC '19

Abstract: We study the problem of finding an exact solution to the consensus halving problem. This is a problem with great encoding power (it seems). While recent work has shown that the approximate version of this problem is PPA-complete , we show that the exact version is much harder. Specifically, finding a solution with n cuts is FIXP-hard, and deciding whether there exists a solution with fewer than n cuts is ETR-complete. (Here ETR satnds for the Existential Theory of the Reals Cllass). We also give a QPTAS for the case where each agent's valuation is a polynomial. Along the way, we define a new complexity class BU, which captures all problems that can be reduced to solving an instance of the Borsuk-Ulam problem exactly. We show that FIXP is in BU which is in Total Function ETR and that LinearBU = PPA, where LinearBU is the subclass of BU in which the Borsuk-Ulam instance is specified by a linear arithmetic circuit.

This is joint work with A. Deligkas, J. Fearnley and T. Melissourgos. Based on our joint paper on the topic accepted in ICALP 2019, and being a sequel of our joint paper in WINE 2018.

Abstract: The Fourier Transform is one of the most important concepts in science and engineering. The Fast Fourier Transform (FFT) algorithm of Cooley and Tukey (1965) computes the Discrete Fourier Transform (DFT) of a length $n$ vector $x$, in time $O(n \log n )$, and has been recognized as one of the most important algorithms of all time. A line of research the last decade focuses on improving FFT in the case that the DFT of $x$ has most of its energy concentrated on a small number of coordinates. Concretely, given a parameter $k$ and an oracle access to $x$, one wants to find the best $k$-term approximation to the DFT of $x$ using as few oracle accesses (samples) and as fast as possible. In this work we give a nearly sample-optimal algorithm for Sparse FT in any dimension and with running time comparable to FFT, improving upon a work of Indyk and Kapralov which suffered from the curse of dimensionality, and upon an enormous literature on compressed sensing, which satisfied a much weaker error guarantee.

Joint work with Zhao Song and Zhengyu Wang. To appear in FOCS 2019.

Abstract: TBA

Abstract: We study the problem of estimating the parameters of a Gaussian distribution when samples are only shown if they fall in some (unknown) subset $S \subseteq \mathbb{R}^d$. This core problem in truncated statistics has long history going back to Galton, Lee, Pearson and Fisher. Recent work by Daskalakis et al. (FOCS'18), provides the first efficient algorithm that works for arbitrary sets in high dimension when the set is known, but leaves as an open problem the more challenging and relevant case of unknown truncation set. Our main result is a computationally and sample efficient algorithm for estimating the parameters of the Gaussian under arbitrary unknown truncation sets whose performance decays with a natural measure of complexity of the set, namely its Gaussian surface area. Notably, this algorithm works for large families of sets including intersections of halfspaces, polynomial threshold functions and general convex sets. We show that our algorithm accurately captures the tradeoff between the complexity of the set and the number of samples needed to learn the parameters by exhibiting a set with small Gaussian surface area for which it is information theoretically impossible to learn the true Gaussian with few samples.

Abstract: We study the multistage $K$-facility reallocation problem on the real line, where we maintain $K$ facility locations over $T$ stages, based on the stage-dependent locations of $n$ agents. Each agent is connected to the nearest facility at each stage, and the facilities may move from one stage to another, to accommodate different agent locations. The objective is to minimize the connection cost of the agents plus the total moving cost of the facilities, over all stages. $K$-facility reallocation was introduced by de Keijzer and Wojtczak, where they mostly focused on the special case of a single facility. Using an LP-based approach, we present a polynomial time algorithm that computes the optimal solution for any number of facilities. We also consider online $K$-facility reallocation, where the algorithm becomes aware of agent locations in a stage-by-stage fashion. By exploiting an interesting connection to the classical $K$-server problem, we present a constant-competitive algorithm for $K = 2$ facilities.

Abstract: Timetable information systems of multimodal public (schedule-based) transport networks can be represented by a suitable directed graph model, whose arcs are associated with travel times. The graph may change over time as delays of public transport vehicles inevitably occur. Two key routines in timetable information systems are (i) the efficient update the timetable information in case of delays, and (ii) the real-time computation of multimodal journey planning queries. In this work, we present multimodal DTM, a new model for multimodal journey planning in public (schedule-based) transport networks. Multimodal DTM constitutes an extension of the dynamic timetable model (DTM), developed originally for unimodal journey planning. Multimodal DTM exhibits a very fast query algorithm, meeting the request for real-time response to best journey queries and an extremely fast update algorithm for updating the timetable information in case of delays. In particular, an experimental study on real-world metropolitan networks demonstrates that our methods compare favorably with other state-of-the-art approaches when public transport along with unrestricted with respect to departing time traveling (walking and electric vehicles) is considered.

Abstract: We study the problem of estimating the volume of convex polytopes, focusing on zonotopes as well as V-polytopes. Although a lot of effort is devoted to practical algorithms for H-polytopes there is no such method for the latter two representations. We propose a new, practical method which undertakes volume computations that were intractable until now, as it is the first polynomial-time, practical method for V-polytopes and zonotopes that scales to high dimensions (currently 100). It relies on random walks for uniform sampling, and combines a new simulated annealing method with the Multiphase Monte Carlo (MMC) approach. We offer an open-source, optimized C++ implementation, and analyze its performance.

Joint work with Ioannis Z. Emiris, Vissarion Fisikopoulos

Abstract: We study two algorithms that exploit sampling, to solve convex optimization problems. The first is based on a randomized version of the cutting plane method and the second improves convergence using simulated annealing. Both methods are based on sampling points from convex bodies which is achieved with random walks. Starting from the popular Hit & Run algorithm, we experiment with various random walks and test heuristics which aim to assist the random walk, to better sample the body. We examine the practicality of such algorithms, especially how well they scale to large dimensions and compare them to state-of-the-art software for convex optimization.

Abstract: Patterns in Permutations and Words is a topic that can be traced in the work of Rotem, Rogers, and Knuth in the 1970s and early 1980s, on data structures design and analysis, and in particular on the stack sorting problem. Currently there is a great amount of papers on this subject. A pattern u in a word w is a sub-word v of w such that the letters in v have the same relative order as the ones in u. In the special case where v is a factor of w, the pattern is said to be consecutive. In this presentation, we focus on the notion of embeddings, that is a generalization of consecutive patterns. Super-strong Wilf equivalence is a type of Wilf equivalence on words which was originally introduced as “strong Wilf equivalence” by Kitaev et al. [Electron. J. Combin.16(2)] in 2009 and was defined using embeddings and the so called generalized factor order. We provide a necessary and sufficient condition for two permutations in n letters to be super-strongly Wilf equivalent, using distances between letters within a permutation. In this way super-strong Wilf equivalence classes in the symmetric group $S_n$ on n letters are in bijection with pyramidal sequences of consecutive differences. Furthermore, we enumerate all super-strong Wilf equivalence classes of $S_n$ by giving a recursive formula in terms of a two-dimensional analogue of the sequence of the number of non-interval permutations in $S_n$. Finally, as a by-product, we give a recursively defined set of representatives of super-strong Wilf equivalence classes and a corresponding tree representation.

Abstract: We study a fundamental question related to the feasibility of deterministic symmetry breaking in the infinite Euclidean plane for two robots that have minimal or no knowledge of the respective capabilities and ``measuring instruments'' of themselves and each other. Assume that two anonymous mobile robots are placed at different locations at unknown distance $d$ from each other on the infinite Euclidean plane. Each robot knows neither the location of itself nor of the other robot. The robots cannot communicate wirelessly, but have a certain nonzero visibility radius $r$ (with range $r$ unknown to the robots). By rendezvous we mean that they are brought at distance at most $r$ of each other by executing symmetric (identical) mobility algorithms. The robots are moving with unknown, constant but not necessarily identical speeds, their clocks and pedometers may be asymmetric, and their chirality inconsistent. We demonstrate that rendezvous for two robots is feasible under the studied model iff the robots have either: different speeds; or different clocks; or different orientations but equal chiralities. When the rendezvous is feasible, we provide a universal algorithm which always solves rendezvous despite the fact that the robots have no knowledge of which among their respective parameters may be different.

Paper presented in PODC 2019: Joint work with Jurek Czyzowicz, Leszek Gasieniec, and Ryan Killick

Abstract: We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within polylogarithmic, subpolynomial or arbitrarily small polynomial factors from the na\"{\i}ve linear space, constant query-time lower bound. These tradeoffs include: (i) an oracle with space $\mathcal{O}(n^{1+\epsilon})$ and query-time $\tilde{\mathcal{O}}(1)$ for any constant $\epsilon>0$, (ii) an oracle with space $\tilde{\mathcal{O}}(n)$ and query-time $\mathcal{O}(n^{\epsilon})$ for any constant $\epsilon>0$, and (iii) an oracle with space $n^{1+o(1)}$ and query-time $n^{o(1)}$.

Abstract: The problem to be presented is referred to and encountered in various forms in international bibliography and has many applications as far as Optical Networks, TDMA (Time Division Multiple Access) and parallel message or data transmission are concerned. For the purposes of this presentation the graph theoretic model of the problem will be used. Researchers are referring to the problem at hand as PREEMPTIVE BIPARTITE SCHEDULING (PBS). In its various forms it has been studied extensively by many researchers and scholars. It is described as follows: Given a set of transmission stations (a set of vertices V, |V|=n), a set of receivers U (a set of vertices U, |U|=m) and a set of messages to be transmitted from V to U (a set of edges E), we are required to produce an efficient schedule such that the total time duration from beginning of the first transmission to the conclusion of the last will be minimized. Each of the messages to be transmitted has some specific duration (edges weight: w). To achieve our goal we are allowed to interrupt (preempt) message packages. Unfortunately, preemption comes with a cost (delay=d) in order to reconfigure the system and/or prepare for the next transmission. Each time we decide to preempt, a reconfiguration delay add to the total transmission time. Therefor in order to produce an optimal schedule one has to take into account two different parameters simultaneously. The approximation algorithms to be presented aim in pinpointing different methodolies in order to efficiently tackle NP-Hard problems.

Abstract: We seek to understand when heterogeneity in user preferences yields improved outcomes in terms of overall cost. That this might be hoped for is based on the common belief that diversity is advantageous in many settings. We investigate this in the context of routing. Our main result is a sharp characterization of the network settings in which diversity always helps, versus those in which it is sometimes harmful. Specifically, we consider routing games, where diversity arises in the way that users trade-off two criteria (such as time and money, or, in the case of stochastic delays, expectation and variance of delay). Our main contributions—a conceptual and a technical one— are the following: 1) A participant-oriented measure of cost in the presence of user diversity, together with the identification of the natural benchmark: the same cost measure for an appropriately defined average of the diversity. 2) A full characterization of those network topologies for which diversity always helps, for all latency functions and demands. For single-commodity routings, these are series-parallel graphs, while for multi-commodity routings, they are the newly-defined “block-matching” networks. The latter comprise a suitable interweaving of multiple series-parallel graphs each connecting a distinct source-sink pair. While the result for the single-commodity case may seem intuitive in light of the well-known Braess paradox, the two problems are different: there are instances where diversity helps although the Braess paradox occurs, and vice-versa. But the main technical challenge is to establish the “only if” direction of the result for multi-commodity networks. This follows by constructing an instance where diversity hurts, and showing how to embed it in any network which is not block-matching, by carefully exploiting the way the simple source-sink paths of the commodities intersect in the “non-block-matching” portion of the network.

Abstract: We study black-box reductions from mechanism design to algorithm design for welfare maximization in settings of incomplete information. Given oracle access to an algorithm for an underlying optimization problem, the goal is to simulate an incentive compatible mechanism. The mechanism will be evaluated on its expected welfare, relative to the algorithm provided, and its complexity is measured by the time (and queries) needed to simulate the mechanism on any input. While it is known that black-box reductions are not possible in many prior-free settings, settings with priors appear more promising: there are known reductions for Bayesian incentive compatible (BIC) mechanism design for general classes of welfare maximization problems. This dichotomy begs the question: which mechanism design problems admit black-box reductions, and which do not? Our main result is that black-box mechanism design is impossible under two of the simplest settings not captured by known positive results. First, for the problem of allocating n goods to a single buyer whose valuation is additive and independent across the goods, subject to a downward-closed constraint on feasible allocations, we show that there is no polytime (in n) BIC black-box reduction for expected welfare maximization. Second, for the setting of multiple single-parameter agents—where polytime BIC reductions are known—we show that no polytime reductions exist when the incentive requirement is tightened to Max-In-Distributional- Range. In each case, we show that achieving a sub-polynomial approximation to the expected welfare requires exponentially many queries, even when the set of feasible allocations is known to be downward-closed.

Abstract: For a graph G, let f(G) denotes the size of the maximum cut in G. The problem of estimating f(G) as a function of the number of vertices and edges of G has a long history and was extensively studied in the last fty years. In this paper we propose an approach, based on semidenite programming (SDP), to prove lower bounds on f(G). We use this approach to nd large cuts in graphs with few triangles and in Kr-free graphs.
Joint work with Charles Carlson, Ray Li, Nitya Mani, Benny Sudakov, Luca Trevisan

Abstract: We consider the budgeted version of the classical connected dominating set problem (BCDS). Given a graph G and an integer budget k, we seek to find a connected subset of at most k vertices which maximizes the number of dominated vertices in G. We answer an open question in S. Khuller, M. Purohit, and K.K. Sarpatwar (Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems, SODA 2014) and thus we improve over the previous (1-1/e)/13 approximation. Our algorithm provides a (1-1/e)/7 approximation guarantee by employing an improved method for enforcing connectivity and performing tree decompositions. We also consider the edge-vertex domination variant, where an edge dominates its endpoints and all vertices neighboring them. In budgeted edge-vertex domination (BEVD), we are given a graph G, and a budget k, and we seek to find a, not necessarily connected, subset of edges such that the number of dominated vertices in G is maximized. We prove there exists a (1-1/e)-approximation algorithm. Also, for any ε > 0, we present a (1-1/e+ε)-inapproximability result by a gap-preserving reduction from the maximum coverage problem. We notice that, in the connected case, BEVD becomes equivalent to BCDS. Moreover, we examine the "dual" partial edge-vertex domination(PEVD) problem, where a graph G and a quota n' are given. The goal is to select a minimum-size set of edges to dominate at least n' vertices in G. In this case, we present a H(n')-approximation algorithm by a reduction to the partial cover problem.

Abstract: We consider the classical broadcast problem in ad-hoc (that is, unknown topology) directed radio networks with no collision detection, under the additional assumption that at most $h$ transmissions (shots) are available per node. We focus on adaptive deterministic protocols for small values of h. We provide asymptotically matching lower and upper bounds for the cases $h=2$ and $h=3$. While for $h=2$ our bound is quadratic, similar to the bound obtained for oblivious protocols, for $h=3$ we prove a sub-quadratic bound of $\Theta(n^2 \log \log n / \log n)$, where $n$ is the number of nodes in the network. The latter is the first result showing an adaptive algorithm which is asymptotically faster than oblivious $h$-shot broadcast protocols, for which a tight quadratic bound is known for every constant $h$. Our upper bound for $h=3$ is constructive, making use of constructions of graphs with large girth. We also show an improved upper bound of $O(n^{(1+\alpha/\sqrt{h})})$ for $h \ge 4$, where $\alpha$ is an absolute constant independent of $h$. Our upper bound for $h \ge 4$ is non-constructive.

(Joint work with Tomasz Radzik)