| Publication | Date of Publication | Type |
|---|
Aspects of a randomly growing cluster in \(\mathbb{R}^d\), \(d \geq 2\)
Discrete Applied Mathematics | 2026-03-05 | Paper |
| Random separating hyperplane theorem and learning polytopes | 2026-01-14 | Paper |
| Fast Monte-Carlo algorithms for finding low-rank approximations | 2025-10-29 | Paper |
| Approximation of diameters: randomization doesn't help | 2025-10-29 | Paper |
| Bit complexity of Jordan normal form and polynomial spectral factorization | 2024-09-25 | Paper |
| How many clusters? -- An algorithmic answer | 2024-07-19 | Paper |
Foundations of data science
Texts and Readings in Mathematics | 2021-06-23 | Paper |
Finding a latent k–simplex in O* (k · nnz(data)) time via Subset Smoothing
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Randomized algorithms in numerical linear algebra
Acta Numerica | 2017-11-17 | Paper |
Faster mixing via average conductance
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Computing a nonnegative matrix factorization -- provably
SIAM Journal on Computing | 2016-09-02 | Paper |
Polynomial-time algorithm for the orbit problem
Journal of the ACM | 2016-01-04 | Paper |
| scientific article; zbMATH DE number 6472593 (Why is no real title available?) | 2015-08-14 | Paper |
Learning mixtures of arbitrary Gaussians
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Random walks on polytopes and an affine interior point method for linear programming
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
| Games of fixed rank: a hierarchy of bimatrix games | 2014-12-18 | Paper |
| scientific article; zbMATH DE number 6381736 (Why is no real title available?) | 2014-12-18 | Paper |
A simple randomised algorithm for convex optimisation
Mathematical Programming. Series A. Series B | 2014-10-17 | Paper |
Spectral methods for matrices and tensors
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
A New Probability Inequality Using Typical Moments and Concentration Results
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Computing a nonnegative matrix factorization -- provably
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Zero-one rounding of singular vectors
Automata, Languages, and Programming | 2013-08-12 | Paper |
| A new approach to the planted clique problem | 2012-10-19 | Paper |
Random walks on polytopes and an affine interior point method for linear programming
Mathematics of Operations Research | 2012-05-24 | Paper |
On clusterings: good, bad and spectral
Journal of the ACM | 2010-08-17 | Paper |
Tensor decomposition and approximation schemes for constraint satisfaction problems
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
The space complexity of pass-efficient algorithms for clustering
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Random sampling and approximation of MAX-CSP problems
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Pass-efficient algorithms for learning mixtures of uniform distributions
SIAM Journal on Computing | 2010-07-07 | Paper |
Finding dense subgraphs in \(G(n,1/2)\)
Approximation and Online Algorithms | 2010-05-11 | Paper |
Games of fixed rank: a hierarchy of bimatrix games
Economic Theory | 2010-02-19 | Paper |
Spectral algorithms
Foundations and Trends in Theoretical Computer Science | 2009-12-22 | Paper |
Optimization of a convex program with a polynomial perturbation
Operations Research Letters | 2009-12-07 | Paper |
Adaptive Sampling for k-Means Clustering
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2009-08-07 | Paper |
The Spectral Method for General Mixture Models
SIAM Journal on Computing | 2009-06-22 | Paper |
Decoupling and Partial Independence
Bolyai Society Mathematical Studies | 2009-02-12 | Paper |
| Two new Probability inequalities and Concentration Results | 2008-09-15 | Paper |
Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
Random Structures & Algorithms | 2008-06-05 | Paper |
Spectral Clustering by Recursive Partitioning
Lecture Notes in Computer Science | 2008-03-11 | Paper |
Fast monte-carlo algorithms for finding low-rank approximations
Journal of the ACM | 2008-01-14 | Paper |
Blocking Conductance and Mixing in Random Walks
Combinatorics, Probability and Computing | 2007-07-30 | Paper |
Learning Theory
Lecture Notes in Computer Science | 2006-06-22 | Paper |
Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
SIAM Journal on Computing | 2006-06-01 | Paper |
Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
SIAM Journal on Computing | 2006-06-01 | Paper |
Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
SIAM Journal on Computing | 2006-06-01 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
Learning mixtures of separated nonspherical Gaussians
The Annals of Applied Probability | 2005-04-29 | Paper |
Clustering large graphs via the singular value decomposition
Machine Learning | 2005-01-19 | Paper |
Random sampling and approximation of MAX-CSPs
Journal of Computer and System Sciences | 2004-11-18 | Paper |
| scientific article; zbMATH DE number 2079343 (Why is no real title available?) | 2004-07-28 | Paper |
Deterministic and randomized polynomial‐time approximation of radii
Mathematika | 2003-11-16 | Paper |
scientific article; zbMATH DE number 1789923 (Why is no real title available?)
(available as arXiv preprint) | 2003-06-16 | Paper |
A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
Theoretical Computer Science | 2003-01-21 | Paper |
| scientific article; zbMATH DE number 1559589 (Why is no real title available?) | 2001-03-01 | Paper |
Log-Sobolev inequalities and sampling from log-concave distributions
The Annals of Applied Probability | 2000-02-07 | Paper |
Quick approximation to matrices and applications
Combinatorica | 1999-12-08 | Paper |
| scientific article; zbMATH DE number 1334601 (Why is no real title available?) | 1999-11-11 | Paper |
| scientific article; zbMATH DE number 1263257 (Why is no real title available?) | 1999-10-28 | Paper |
| scientific article; zbMATH DE number 1305418 (Why is no real title available?) | 1999-06-17 | Paper |
| scientific article; zbMATH DE number 1305090 (Why is no real title available?) | 1999-06-17 | Paper |
A simple algorithm for constructing Szemerédi's regularity partition
The Electronic Journal of Combinatorics | 1999-03-31 | Paper |
A simple algorithm for constructing Szemerédi's regularity partition
The Electronic Journal of Combinatorics | 1999-03-31 | Paper |
A polynomial-time algorithm for learning noisy linear threshold functions
Algorithmica | 1998-11-11 | Paper |
| Sampling contingency tables | 1998-04-05 | Paper |
Learning an intersection of a constant number of halfspaces over a uniform distribution
Journal of Computer and System Sciences | 1997-12-08 | Paper |
On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
Mathematics of Operations Research | 1997-10-28 | Paper |
| Random walks and anO*(n5) volume algorithm for convex bodies | 1997-09-04 | Paper |
A Randomized Algorithm to Optimize Over Certain Convex Sets
Mathematics of Operations Research | 1996-09-16 | Paper |
| scientific article; zbMATH DE number 774005 (Why is no real title available?) | 1995-08-07 | Paper |
Isoperimetric problems for convex bodies and a localization lemma
Discrete & Computational Geometry | 1995-07-02 | Paper |
Sampling from log-concave distributions
The Annals of Applied Probability | 1995-05-30 | Paper |
A random polynomial-time algorithm for approximating the volume of convex bodies
Journal of the ACM | 1994-08-21 | Paper |
A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
Combinatorics, Probability and Computing | 1994-04-28 | Paper |
A circuit-based proof of Toda's theorem
Information and Computation | 1993-08-30 | Paper |
Lattice translates of a polytope and the Frobenius problem
Combinatorica | 1993-01-16 | Paper |
| scientific article; zbMATH DE number 18540 (Why is no real title available?) | 1992-06-26 | Paper |
Chvátal closures for mixed integer programming problems
Mathematical Programming. Series A. Series B | 1990-01-01 | Paper |
| scientific article; zbMATH DE number 4204116 (Why is no real title available?) | 1990-01-01 | Paper |
The Shapes of Polyhedra
Mathematics of Operations Research | 1990-01-01 | Paper |
On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines
Journal of Computer and System Sciences | 1989-01-01 | Paper |
On 3-pushdown graphs with large separators
Combinatorica | 1989-01-01 | Paper |
Succinct Certificates for Almost All Subset Sum Problems
SIAM Journal on Computing | 1989-01-01 | Paper |
Covering minima and lattice-point-free convex bodies
Annals of Mathematics. Second Series | 1988-01-01 | Paper |
| Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers | 1988-01-01 | Paper |
Reconstructing Truncated Integer Variables Satisfying Linear Congruences
SIAM Journal on Computing | 1988-01-01 | Paper |
Hermite Normal Form Computation Using Modulo Determinant Arithmetic
Mathematics of Operations Research | 1987-01-01 | Paper |
Minkowski's Convex Body Theorem and Integer Programming
Mathematics of Operations Research | 1987-01-01 | Paper |
Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers
SIAM Journal on Computing | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4036606 (Why is no real title available?) | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4006346 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3997912 (Why is no real title available?) | 1986-01-01 | Paper |
Solving systems of linear equations over polynomials
Theoretical Computer Science | 1985-01-01 | Paper |
Unraveling k-page graphs
Information and Control | 1985-01-01 | Paper |
Towards separating nondeterminism from determinism
Mathematical Systems Theory | 1984-01-01 | Paper |
Polynomial-Time Aggregation of Integer Programming Problems
Journal of the ACM | 1983-01-01 | Paper |
| scientific article; zbMATH DE number 3890617 (Why is no real title available?) | 1983-01-01 | Paper |
Circuit-size lower bounds and non-reducibility to sparse sets
Information and Control | 1982-01-01 | Paper |
Exponential Lower Bounds on a Class of Knapsack Algorithms
Mathematics of Operations Research | 1981-01-01 | Paper |
A Polynomial Algorithm for the Two-Variable Integer Programming Problem
Journal of the ACM | 1980-01-01 | Paper |
A characterization of threshold matroids
Discrete Mathematics | 1980-01-01 | Paper |
Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
SIAM Journal on Computing | 1979-01-01 | Paper |
| scientific article; zbMATH DE number 3619622 (Why is no real title available?) | 1979-01-01 | Paper |
| scientific article; zbMATH DE number 3619621 (Why is no real title available?) | 1979-01-01 | Paper |
| scientific article; zbMATH DE number 3634020 (Why is no real title available?) | 1979-01-01 | Paper |
| scientific article; zbMATH DE number 3637601 (Why is no real title available?) | 1978-01-01 | Paper |
