Self-Improving Algorithms (2009)
Ailon, Nir, Chazelle, Bernard, Clarkson, Kenneth L., Liu, Ding, Mulzer, Wolfgang, Seshadhri, C.
We investigate ways in which an algorithm can improve its expected performance by fine-tuning itself automatically with respect to an arbitrary, unknown input distribution. We give such...
Testing cycle-freeness: Finding a certificate (2009)
We deal with the problem of designing one-sided error property testers for cycle-freeness in bounded degree graphs. Such a property tester always accepts forests. Furthermore, when it rejects an...
We investigate the problem of monotonicity reconstruction, as defined in [3], in a distributed setting. We have oracle access to a nonnegative real-valued function f defined on domain [n] d =...
We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions....
Abstract Parallel Monotonicity Reconstruction (2008)
We investigate the problem of monotonicity reconstruction, as defined in [3], in a parallel setting. We have oracle access to a nonnegative real-valued function f defined on domain [n] d = {1,..., n}...
An Almost Optimal Rank Bound for Depth-3 Identities (2008)
We show that the rank of a depth-3 circuit (over any field) that is simple, minimal and zero is at most k^3\log d. The previous best rank bound known was 2^{O(k^2)}(\log d)^{k-2} by Dvir and Shpilka...
We consider the problem of testing graph expansion (either vertex or edge) in the bounded degree model [2]. We give a property tester that given a graph with degree bound d, an expansion bound α,...
Self-improving Algorithms for Delaunay Triangulations (2008)
Kenneth L. Clarkson, C. Seshadhri
We study the problem of two-dimensional Delaunay triangulation in the self-improving algorithms model [1]. We assume that the n points of the input each come from an independent, unknown, and...