Bounding the Sensitivity of Polynomial Threshold Functions (2009)
Harsha, Prahladh, Klivans, Adam, Meka, Raghu
We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of polynomial threshold functions. More specifically, for a Boolean function f on n variables equal to the...
Applications of Probabilistic Analysis and Game Theory (2008)
Nedialko Boyanov Dimitrov, C. Greg Plaxton, Adam Klivans, David Morton, Peter Stone, David Zuckerman, ...
To my family, friends and mentors: Thank you. – Ned.
Amos Beimel, Yevgeniy Dodis, John Dunagan, Venkatesan Guruswami, Prahladh Harsha, Adam Klivans, ...
much more careful and clear than I was. Thanks in particular to Salil Vadhan who lectured on November 9, 1998, two hours after Roshni Malhaar was born. These notes are by no means polished....
Jesse John Kamp, David Zuckerman Supervisor, Anna Gál, Adam Klivans, Vijaya Ramachandran, Salil Vadhan, ...
Firstly, I would like to thank my advisor, David Zuckerman. I appreciate his always being able to suggest interesting research problems, while at the same time always being open to listen to and...
and Applications Publication No. (2007)
Anindya Chandra Patthak, David I. Zuckerman, Anna Gál, Charanjit S. Jutla, Adam Klivans, José Felipe Voloch, ...
This dissertation is a study of special types of error correcting codes and their applications. It consists of three parts. First, we study Generalized Reed-Muller codes (over prime fields), aka...
Anup Rao, David Zuckerman Supervisor, Boaz Barak, Anna Gal, Adam Klivans, Charles Gregory Plaxton
Many people have contributed to the work that appears in this thesis. The quality of my ideas and my productivity as a researcher were directly related to the kinds of people I have interacted with,...
Sparse Random Graphs Methods, Structure, and Heuristics Publication No. (2007)
Daniel Turrin Fernholz, Vijaya Ramachandran Supervisor, Luis Caffarelli, Adam Klivans, Greg Plaxton, David Zuckerman, ...
This dissertation is an algorithmic study of sparse random graphs which are parametrized by the distribution of vertex degrees. Our contributions include: a formula for the diameter of various sparse...
Anup Rao, David Zuckerman Supervisor, Boaz Barak, Anna Gal, Adam Klivans, Charles Gregory Plaxton
Many people have contributed to the work that appears in this thesis. The quality of my ideas and my productivity as a researcher were directly related to the kinds of people I have interacted with,...
Agnostically Learning Halfspaces (2005)
Kalai, Adam, Klivans, Adam, Mansour, Yishay, Servedio, Rocco
We give the first algorithm that (under distributional assumptions) efficiently learns halfspaces in the notoriously difficult {\em agnostic} framework of Kearns, Schapire, \& Sellie\ignore{I've been...
Agnostically Learning Halfspaces (2005)
Kalai, Adam, Klivans, Adam, Mansour, Yishay, Servedio, Rocco A.
We consider the problem of learning a halfspace in the agnostic framework of Kearns et al., where a learner is given access to a distribution on labelled examples but the labelling may be arbitrary....
Factoring Polynomials Modulo Composites, (1997)
This paper characterizes all the factorizations of a polynomial with coefficients in the ring Zn where n is a composite number. We give algorithms to compute much factorizations along with algebraic...
Factoring Polynomials Modulo Composites (1997)
This paper characterizes all the factorizations of a polynomial with coefficients in the ring Z n where n is a composite number. We give algorithms to compute such factorizations along with algebraic...