Shai Vardi

AAAI Conference 2018 Conference Paper

A Parallelizable Acceleration Framework for Packing Linear Programs

• Palma London
• Shai Vardi
• Adam Wierman
• Hanling Yi

This paper presents an acceleration framework for packing linear programming problems where the amount of data available is limited, i. e. , where the number of constraints m is small compared to the variable dimension n. The framework can be used as a black box to speed up linear programming solvers dramatically, by two orders of magnitude in our experiments. We present worst-case guarantees on the quality of the solution and the speedup provided by the algorithm, showing that the framework provides an approximately optimal solution while running the original solver on a much smaller problem. The framework can be used to accelerate exact solvers, approximate solvers, and parallel/distributed solvers. Further, it can be used for both linear programs and integer linear programs.

AAAI Conference 2018 Conference Paper

Non-Exploitable Protocols for Repeated Cake Cutting

• Omer Tamuz
• Shai Vardi
• Juba Ziani

We introduce the notion of exploitability in cut-and-choose protocols for repeated cake cutting. If a cut-and-choose protocol is repeated, the cutter can possibly gain information about the chooser from her previous actions, and exploit this information for her own gain, at the expense of the chooser. We de- fine a generalization of cut-and-choose protocols—forced-cut protocols—in which some cuts are made exogenously while others are made by the cutter, and show that there exist nonexploitable forced-cut protocols that use a small number of cuts per day: When the cake has at least as many dimensions as days, we show a protocol that uses a single cut per day. When the cake is 1-dimensional, we show an adaptive non-exploitable protocol that uses 3 cuts per day, and a nonadaptive protocol that uses n cuts per day (where n is the number of days). In contrast, we show that no non-adaptive non-exploitable forced-cut protocol can use a constant number of cuts per day. Finally, we show that if the cake is at least 2-dimensional, there is a non-adaptive non-exploitable protocol that uses 3 cuts per day.

SODA Conference 2017 Conference Paper

Sorting from Noisier Samples

• Aviad Rubinstein
• Shai Vardi

We study the problem of constructing an order over a set of elements given noisy samples. We consider two models for generating the noisy samples; in both, the distribution of samples is induced by an unknown state of nature: a permutation ρ. In Mallow's model, r permutations n i are generated independently from p, each with probability proportional to e −ßd K (ρ, πί), where d K (p, π i ) is the Kemeny distance between ρ and n i - the number of pairs they order differently. In the noisy comparisons model, we are given a tournament, generated from ρ as follows: if i is before j in p, then with probability 1/2 + γ, the edge between them is oriented from i to j. Both of these problems were studied by Braverman and Mossel [7]; they showed how to construct a maximum-likelihood permutation when the noise parameter (ß or γ, respectively) is constant. In this work, we obtain algorithms that work in the presence of stronger noise or respectively). In Mallow's model, our algorithm works for a relaxed solution concept: likelier than nature. That is, rather than requiring that our output maximizes the likelihood over the entire domain, we guarantee that the likelihood of our output is, w. h. p. , greater than or equal to that of the true state of nature (p). An interesting feature of our algorithm is that it handles noise by adding more noise.

SODA Conference 2012 Conference Paper

Space-efficient local computation algorithms

• Noga Alon
• Ronitt Rubinfeld
• Shai Vardi
• Ning Xie 0002