The Uniform Hardcore Lemma via Approximate Bregman Pro jections* (2009)
Boaz Barak, Moritz Hardt, Satyen Kale
Abstract We give a simple, more efficient and uniform proof of thehard-core lemma, a fundamental result in complexity theory with applications in machine learning and cryp-tography. Our result...
The Uniform Hardcore Lemma via Approximate Bregman Projections ∗ (2009)
Boaz Barak, Moritz Hardt, Satyen Kale, Sloan Fellowships
We give a simple, more efficient and uniform proof of the hard-core lemma, a fundamental result in complexity theory with applications in machine learning and cryptography. Our result follows from...
Better Algorithms for Benign Bandits (2009)
The online bandit problem is a repeated decision making problem, where the goal is to select one of several possible decisions in every round, and incur a cost associated with the decision, in such a...
Noise Tolerance of Expanders and Sublinear Expander Reconstruction (2009)
Abstract We consider the problem of online sublinear expanderreconstruction and its relation to random walks in "noisy " expanders. Given access to an adjacency list representationof a...
Noise Tolerance of Expanders and Sublinear Expander Reconstruction (2009)
We consider the problem of online sublinear expander reconstruction and its relation to random walks in “noisy” expanders. Given access to an adjacency list representation of a bounded-degree...
Sanjeev Arora, Elad Hazan, Satyen Kale
Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analyses are usually very...
The contingency table is a work horse of official statistics, the format of reported data for the US Census, Bureau of Labor Statistics, and the Internal Revenue Service. In many settings such as...
We study the relation between notions of game-theoretic equilibria which are based on stability under a set of deviations, and empirical equilibria which are reached by rational players. Rational...
Approximating Quadratic Programs with Positive Semidefinite Constraints (2008)
We describe a polynomial time approximation algorithm to the problem of maximizing a quadratic form subject to quadratic constraints specified by PSD matrices. A special case, that has applications...
Approximating Quadratic Programs with Positive Semidefinite Constraints (2008)
We describe a polynomial time approximation algorithm to the problem of maximizing a quadratic form subject to quadratic constraints specified by PSD matrices. A special case, that has applications...
The contingency table is a work horse of official statistics, the format of reported data for the US Census, Bureau of Labor Statistics, and the Internal Revenue Service. In many settings such as...
T. S. Jayram, Satyen Kale, Erik Vee
We study the problem of computing aggregation operators
We revisit the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio. We present a boosting algorithm with a certain smoothness property that is...
We study the relation between notions of game-theoretic equilibria which are based on stability under a set of deviations, and empirical equilibria which are reached by rational players. Rational...
T. S. Jayram, Satyen Kale, Erik Vee
We study the problem of computing aggregation operators
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 α,...
We study the relation between notions of game-theoretic equilibria which are based on stability under a set of deviations, and empirical equilibria which are reached by rational players. Rational...
Efficient Algorithms Using The Multiplicative Weights Update Method (2007)
Abstract Algorithms based on convex optimization, especially linear and semidefinite programming, are ubiquitous in Computer Science. While there are polynomial time algorithms known to solve such...
Satyen Kale, Advisor Prof, Sanjeev Arora, Advisor Prof, Abhiram Ranade
Completed equivalent of a Master’s course in mathematics.
O(plog n) Approximation to Sparsest Cut in ~O(n2) Time (2007)
Sanjeev Arora, Elad Hazan, Satyen Kale
Abstract We show how to compute O(plog n)-approximations to Sparsest Cut and Balanced Separator problems in ~O(n2) time, thus improving upon the recent algorithm of Arora, Rao and Vazirani (2004)....
A combinatorial, primal-dual approach to semidefinite programs (2007)
Semidefinite programs (SDP) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative...
Logarithmic regret algorithms for online convex optimization (2007)
Elad Hazan, Amit Agarwal, Satyen Kale
In an online convex optimization problem a decision-maker makes a sequence of decisions, i.e., chooses a sequence of points in Euclidean space, from a fixed feasible set. After each point is chosen,...
Logarithmic regret algorithms for online convex optimization (2006)
Elad Hazan, Adam Kalai, Satyen Kale, Amit Agarwal
Abstract. In an online convex optimization problem a decision-maker makes a sequence of decisions, i.e., choose a sequence of points in Euclidean space, from a fixed feasible set. After each point is...
Logarithmic regret algorithms for online convex optimization (2006)
Elad Hazan, Amit Agarwal, Satyen Kale
In an online convex optimization problem a decision-maker makes a sequence of decisions, i.e., chooses a sequence of points in Euclidean space, from a fixed feasible set. After each point is chosen,...
A Fast Random Sampling Algorithm for Sparsifying Matrices (2006)
Sanjeev Arora, Elad Hazan, Satyen Kale
We describe a simple random-sampling based procedure for producing sparse matrix approximations. Our procedure and analysis are extremely simple: the analysis uses nothing more than the...
Logarithmic regret algorithms for online convex optimization (2006)
Elad Hazan, Adam Kalai, Satyen Kale, Amit Agarwal
Abstract. In an online convex optimization problem a decision-maker makes a sequence of decisions, i.e., chooses a sequence of points in Euclidean space, from a fixed feasible set. After each point...
Efficient Algorithms Using The Multiplicative Weights Update Method (2006)
Algorithms based on convex optimization, especially linear and semidefinite programming, are ubiquitous in Computer Science. While there are polynomial time algorithms known to solve such problems,...
The multiplicative weights update method: a meta algorithm and applications (2005)
Sanjeev Arora, Elad Hazan, Satyen Kale
Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analysis are usually very...
The multiplicative weights update method: a meta algorithm and applications (2005)
Sanjeev Arora, Elad Hazan, Satyen Kale
Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analysis are usually very...
Analysis and algorithms for content-based event matching (2005)
Satyen Kale, Elad Hazan, Fengyun Cao, Jaswinder Pal Singh
Content-based event matching is an important problem in large-scale event-based publish/subscribe systems. However, open questions remain in analysis of its difficulty and evaluation of its...
Sanjeev Arora, Elad Hazan, Satyen Kale
Semidefinite programming (SDP) relaxations appear in many recent approximation algorithms but the only general technique for solving such SDP relaxations is via interior point methods. We use a...
The multiplicative weights update method: a meta algorithm and applications (2005)
Sanjeev Arora, Elad Hazan, Satyen Kale
Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analysis are usually very...
O(plog n) approximation to SPARSEST CUT in ~O(n2) time (2004)
Sanjeev Arora, Elad Hazan, Satyen Kale
We show how to compute O ( √ log n)-approximations to Sparsest Cut and Balanced Separator problems in Õ(n2) time, thus improving upon the recent algorithm of Arora, Rao and Vazirani (2004). Their...
O ( √ log n) approximation to SPARSEST CUT can be found in Õ(n 2) time FOCS 2004 Submission (2004)
Sanjeev Arora, Elad Hazan, Satyen Kale
We show that the recent results for obtaining O ( √ log n)-approximation to sparsest cut and balanced separator problems due to Arora, Rao, and Vazirani (2004) can be used to derive an Õ(n2) time...
Algorithms for Portfolio Management based on the Newton Method (1999)
Amit Agarwal, Elad Hazan, Satyen Kale, Robert E. Schapire
We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio...
Algorithms for Portfolio Management based on the Newton Method (1999)
Amit Agarwal, Elad Hazan, Satyen Kale, Robert E. Schapire
We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio...
Algorithms for Portfolio Management based on the Newton Method (1999)
Amit Agarwal, Elad Hazan, Satyen Kale, Robert E. Schapire
We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio...
Algorithms for Portfolio Management based on the Newton Method (1999)
Amit Agarwal, Elad Hazan, Satyen Kale, Robert E. Schapire
We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio...