enter search term and/or author name
In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One...
Truthful and Near-Optimal Mechanism Design via Linear Programming
Ron Lavi, Chaitanya Swamy
Article No.: 25
We give a general technique to obtain approximation mechanisms that are truthful in expectation. We show that for packing domains, any α-approximation algorithm that also bounds the integrality gap of the LP relaxation of the problem...
Compositional Shape Analysis by Means of Bi-Abduction
Cristiano Calcagno, Dino Distefano, Peter W. O’Hearn, Hongseok Yang
Article No.: 26
The accurate and efficient treatment of mutable data structures is one of the outstanding problem areas in automatic program verification and analysis. Shape analysis is a form of program analysis that attempts to infer descriptions of the data...
Randomized Shellsort: A Simple Data-Oblivious Sorting Algorithm
Michael T. Goodrich
Article No.: 27
In this article, we describe a randomized Shellsort algorithm. This algorithm is a simple, randomized, data-oblivious version of the Shellsort algorithm that always runs in O(n log n) time and succeeds in sorting any...
New Constructive Aspects of the Lovász Local Lemma
Bernhard Haeupler, Barna Saha, Aravind Srinivasan
Article No.: 28
The Lovász Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of “bad” events, with positive probability. A series of results have provided algorithms to efficiently construct...
This work considers the quantum interactive proof system model of computation, which is the (classical) interactive proof system model’s natural quantum computational analogue. An exact characterization of the expressive power of quantum...