SODA

In this paper we study the fine-grained complexity of finding exact and approximate solutions to problems in P. Our main contribution is showing reductions from an exact to an approximate solution for a host of such problems.

As one (notable) example, ...

The Orthogonal Vectors problem (OV) asks: given n vectors in {0,1}O(log n), are two of them orthogonal? OV is easily solved in O(n2 log n) time, and it is a central problem in finegrained complexity: dozens of conditional lower bounds are based on the ...

SUBSET SUM and k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. An important open problem in this area is to base the hardness of one ...

Given n positive integers, the Modular Subset Sum problem asks if a subset adds up to a given target t modulo a given integer m. This is a natural generalization of the Subset Sum problem (where m = +∞) with ties to additive combinatorics and ...

The subject of this paper is the time complexity of approximating KNAPSACK, SUBSET SUM, PARTITION, and some other related problems. The main result is an Õ(n + 1/ε^5/3) time randomized FPTAS for PARTITION, which is derived from a certain relaxed form of ...

We consider metrical task systems on tree metrics, and present an O(depthxlog n)-competitive randomized algorithm based on the mirror descent framework introduced in our prior work on the k-server problem. For the special case of hierarchically ...

We consider the k-server problem on trees and HSTs. We give an algorithm based on Bregman projections. This algorithm has a competitive ratios that match some of the recent results given by Bubeck et al. (STOC 2018), whose algorithm was based on mirror-...

Friedman and Linial [8] introduced the convex body chasing problem to explore the interplay between geometry and competitive ratio in metrical task systems. In convex body chasing, at each time step t ∈ N, the online algorithm receives a request in the ...

In the online packet scheduling problem with deadlines (PacketScheduling, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing ...

Motivated by applications in cloud computing, we study the classical online caching problem for a cache of variable size, where the algorithm pays a maintenance cost that monotonically increases with cache size. This captures not only the classical ...

We study the problem of designing dynamic double auctions for two-sided markets in which a platform intermediates the trade between one seller offering independent items to multiple buyers, repeatedly over a finite horizon, when agents have private ...

We design multi-unit auctions for budget-constrained bidders in the Bayesian setting. Our auctions are supply-monotone, which allows the auction to be run online without knowing the number of items in advance, and achieve asymptotic revenue optimality. ...

We investigate the problem of revenue maximization in single-item auction within the new correlation-robust framework proposed by Carroll [2017] and further developed by Gravin and Lu [2018]. In this framework the auctioneer is assumed to have only ...

We consider a fundamental problem in microeconomics: Selling a single item among a number of buyers whose values are drawn from known independent and regular distributions. There are four widely-used and widely-studied mechanisms in this literature: ...

We study the assignment problem of objects to agents with heterogeneous preferences under distributional constraints. Each agent is associated with a publicly known type and has a private ordinal ranking over objects. We are interested in assigning as ...

We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (1/2 + ε)-approximation for the problem. This algorithm is the first deterministic algorithm known to ...

Submodular optimization generalizes many classic problems in combinatorial optimization and has recently found a wide range of applications in machine learning (e.g., feature engineering and active learning). For many large-scale optimization problems, ...

In this paper, we study the tradeoff between the approximation guarantee and adaptivity for the problem of maximizing a monotone submodular function subject to a cardinality constraint. The adaptivity of an algorithm is the number of sequential rounds ...

In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel. Adaptivity is a fundamental concept that is heavily ...

Balkanski and Singer [4] recently initiated the study of adaptivity (or parallelism) for constrained submodular function maximization, and studied the setting of a cardinality constraint. Subsequent improvements for this problem by Balkanski, Rubinstein,...

In the submodular cover problem, we are given a non-negative monotone submodular function f over a ground set E of items, and the goal is to choose a smallest subset S ⊆ E such that f (S) = Q where Q = f (E). In the stochastic version of the problem, we ...

This paper considers stochastic optimization problems whose objective functions involve powers of random variables. For a concrete example, consider the classic Stochastic ℓ_p Load Balancing Problem (StochLoadBal_p): There are m machines and n jobs, and ...

We present a new approach to ε-approximate nearest-neighbor queries in fixed dimension under a variety of non-Euclidean distances. We consider two families of distance functions: (a) convex scaling distance functions including the Mahalanobis distance, ...

The range closest-pair (RCP) problem is the range-search version of the classical closest-pair problem, which aims to store a given dataset of points in some data structure such that when a query range X is specified, the closest pair of points ...

Given a set of m point sites in a simple polygon, the geodesic nearest-point Voronoi diagram of the sites partitions the polygon into m Voronoi cells, one cell per site, such that every point in a cell has the same nearest site under the geodesic ...

Arrangements of lines and pseudolines are fundamental objects in discrete and computational geometry. They also appear in other areas of computer science, such as the study of sorting networks. Let B_n be the number of nonisomorphic arrangements of n ...

A configuration is a finite set of points in the plane. Two configurations A and B have the same order type if there exists a bijection between them preserving the orientation of every ordered triple. We investigate extremal and probabilistic problems ...

Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph ...

Given an ideal I and a polynomial f the Ideal Membership Problem is to test if f ∈ I. This problem is a fundamental algorithmic problem with important applications and notoriously intractable.

We study the complexity of the Ideal Membership Problem for ...

We develop a theory of graph algebras over general fields. This is modeled after the theory developed by Freedman, Lovász and Schrijver in [22] for connection matrices, in the study of graph homomorphism functions over real edge weight and positive ...