Publications

2022

 

2021

  

    2020

     

    2019

     

    2018

    2017

    2016

    • Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams:
      Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. STOC 2016: 375-388
      Summary: We prove that Edit Distance and LCS are even harder than what recent works have discovered: They can solve SAT not only on CNF formulas (as in SETH lower bounds), but also SAT on very large circuits, branching programs, and turing machines. One striking consequence of our work is that even shaving a few log factors over the n^2 bound for these problems would imply major advances in circuit complexity.

    • A. Abboud, Keren Censor-Hillel, Seri Khoury . DISC 2016 (best student paper).
      Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks.
      Summary: Consider a communication model where in every round, each node gets to send a message of length O(log n) to each one of its neighbors. How many rounds are needed in order to compute a basic property of the network, such as the diameter? We show a tight near-linear lower bound on the number of rounds. This is the first lower bound higher than sqrt(n) that applies to sparse graphs.

    • A. Abboud, Søren Dahlgaard. FOCS 2016.
      Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms.
      Summary: We prove the first "Hardness in P" results for problems on planar graphs. For example, we show that dynamic planar APSP requires polynomial update or query times, under the (standard) APSP conjecture.

    • A. Abboud, Greg Bodwin.
      Error Amplification for Pairwise Spanner Lower Bounds. SODA 2016.
      Summary: We prove new lower bounds for "Pairwise Spanners" by presenting (denser-than-before) constructions of graphs in which the removal of a constant number of edges will necessarily increase a pairwise distance between a pair of nodes from a small set of pairs. Our constructions use an "error amplification" trick which uses a special kind of graph product.

    • A. Abboud, Virginia Vassilevska Williams, Joshua Wang.
      Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. SODA 2016.
      Summary: This paper contains many things: (1) we introduce the "Hitting Set Conjecture" and show its consequences for quadratic time problems, (2) we introduce the new concept of searching for "fixed parameter subquadratic" algorithms for problems with natural parameters that cannot be solved in subquadratic time in general, (3) we devise new approximation and F.P.Subquadratic algorithms for radius and diameter. A cool result is that Diameter can be solved in 2^O(k log k)*n^{1.1} time, where k is the treewidth of the input graph, but cannot be solved in 2^o(k)*n^1.9 under SETH.

    2015

    2014

    • Daniel Keren, Guy Sagy, Amir Abboud, David Ben-David, Assaf Schuster, Izchak Sharfman, Antonios Deligiannakis:
      Geometric Monitoring of Heterogeneous Streams. IEEE Trans. Knowl. Data Eng. 26(8): 1890-1903 (2014)
    • A. Abboud, Virginia Vassilevska Williams.
      Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. FOCS 2014: 434-443. [slides]  
      Summary: The trivial algorithms for many fundamental dynamic data-structures problems are essentially optimal, unless certain popular conjectures about classic static problems, like SETH, are false. The (long) list of problems includes reachability, strongly connected components and matching.
    • A. Abboud, Kevin Lewi, Ryan Williams.
      Losing Weight by Gaining Edges. ESA 2014, Wroclaw, Poland. [slides] [pdf]
      Summary: k-SUM on n numbers can be reduced to k-Clique on roughly n nodes. Moreover, node-weighted versions of Clique and Dominating-Set are not (polynomially) harder than the unweighted versions! One interesting consequence is that k-SUM is (essentially) W[1]-complete. 
    • A. Abboud, Virginia Vassilevska Williams, Oren Weimann.
      Consequences of Faster Alignment of Sequences.  ICALP (1) 2014: 39-51. [slides] [pdf]
      Summary: We provide strong theoretical evidence that Local Alignment cannot be solved in truly subquadratic time: such algorithm would refute SETH (a breakthrough in satisfiability algorithm), the 3-SUM conjecture (from computational geometry), and give a very surprising algorithm for Min-4-Clique. 
    • Hardness for Easy Problems. YR-ICALP 2014, Copenhagen, Denmark. [slides] (A 20-minute survey on the recent attempts to classify the poly-time problems)

    2013

    • A. Abboud, Kevin Lewi.
      Exact Weight Subgraphs and the k-SUM Conjecture. ICALP 2013, Riga, Latvia. [slides] [pdf]
      Summary: A set of generic reductions relating k-SUM and weighted graph problems are given. One interesting consequence is that finding a path on four nodes of weight zero (an innocent looking problem), truly faster than the trivial cubic time, implies breakthrough algorithms for APSP, 3SUM, and 5SUM.