Santosh Vempala's papers (in ps/pdf)

Refine by topic:

1 Sampling and Integration of Logconcave Functions by Algorithmic Diffusion (Yunbum Kook)
STOC 2025
2 Does GPT Really Get It? A Hierarchical Scale to Quantify Human vs AI's Understanding of Algorithms (Mirabel Reid)
AAAI 2025 (oral) (prelim. version in NeurIPS 2024 workshop on Behavioral ML)
3 Computation with Sequences in a Model of the Brain (M. Dabagia, C. H. Papadimitriou)
Neural Computation 2025 (prelim. version in ALT 2024)
4 In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies (Y. Kook, M. Zhang)
NeurIPS 2024 (spotlight)
5 Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling (Yunbum Kook)
COLT 2024
6 Sampling with Barriers: Faster Mixing via Lewis Weights (K. Gatmiry, J. Kelner)
COLT 2024
7 Calibrated Language Models must Hallucinate (Adam Kalai)
STOC 2024
8 Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time (Xinyuan Cao)
Neurips 2023
9 Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error (He Jia, P. Kothari)
FOCS 2023
10 The Bit Complexity of Efficient Continuous Optimization (M. Ghadiri, R. Peng)
FOCS 2023
11 The k-cap Process on Geometric Random Graphs (Mirabel Reid)
COLT 2023
12 Is Planted Coloring Easier than Planted Clique? (P. Kothari, A. Wein, J. Xu)
COLT 2023
13 Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators (Y. Kook, Y.-T. Lee, R. Shen)
COLT 2023
14 Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space (Y. Kook, Y.-T. Lee, R. Shen)
Neurips 2022
15 The Manifold Joys of Sampling in High Dimension
ICALP 2022 (invited)
16 A Unified Approach to Discrepancy Minimization (N. Bansal, A. Laddha)
RANDOM 2022
17 Assemblies of Neurons Learn to Classify Well-Separated Distributions (M. Dabagia, C. Papadimitriou)
COLT 2022
18 Robustly Learning Mixtures of k Arbitrary Gaussians (A. Bakshi, H. Jia, D. Kane, P. Kothari, I. Diakonikolas)
STOC 2022
19 Approximating Sparse Graphs: The Random Overlapping Communities Model (Sam Petti)
Random Structures and Algorithms, 2022
20 Provable Lifelong Learning of Representations (Xinyan Cao, Weiyang Liu)
AISTATS 2022
21 How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization (Shivam Garg)
AISTATS 2022
22 The Mirror Langevin Algorithm Converges with Vanishing Bias (R. Li, M. Tao, A. Wibisono)
ALT 2022
23 A Unified View of Graph Regularity via Matrix Decompositions (G. Bodwin)
Random Structures and Algorithms, 2021
24 Reducing Isotropy and Volume to KLS: An O*(n3 \psi2) Volume Algorithm (He Jia, Aditi Laddha, Yin Tat Lee)
STOC 2021
25 Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast (Aditi Laddha)
SoCG 2021, special issue of Discrete and Computational Geometry (invited)
26 Socially Fair k-Means Clustering (M. Ghadiri, S. Samadi)
FAccT 2021
27 Solving Sparse Linear Systems Faster than Matrix Multiplication (Richard Peng)
SODA 2021 (Best Paper)
28 A Generalized Central Limit Conjecture for Convex Bodies (Haotian Jiang, Yin Tat Lee)
Geometric Aspects of Functional Analysis 2020
29 Brain Computation with Assemblies of Neurons (Papadimitriou, Mitropolsky, Collins, Maass)
PNAS 2020
30 The Complexity of Human Computation via a Concrete Model with an Application to Passwords (Manuel Blum)
PNAS 2020
31 Strong Self-Concordance and Sampling (Aditi Laddha, Yin Tat Lee)
STOC 2020
32 The Communication Complexity of Optimization (R. Wang, D. Woodruff)
SODA 2020 (invited to HALG 2020)
33 Redesigning a Basic Laboratory Information System for the Global South (Jung Wook Park, Aditi Shah, Rosa Arriaga)
(ITU Kaleidescope 2019) ICT for Health: Networks, Standards and Innovation. (Best Paper).
34 Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices (Andre Wibisono)
NeurIPS 2019
35 Multi-Criteria Dimensionality Reduction with Applications to Fairness (S. Samadi, M. Singh, U. Tantipongpipat)
NeurIPS 2019 (spotlight)
36 Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions (Zongchen Chen)
RANDOM 2019 (invited to special issue of Theory of Computing)
37 Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds (John Wilmes)
COLT 2019
38 Random Projection in the Brain and Computation with Assemblies of Neurons (Christos Papadimitriou)
ITCS 2019
39 The Price of Fair PCA: One Extra Dimension (S. Samadi, U. Tantipongpipat, J. Morgenstern, M. Singh)
NIPS 2018
40 Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons (N. Anari, C. Daskalakis, W. Maass, C. Papadimitriou, A. Saberi)
NIPS 2018
41 The Usability of Humanly Computable Passwords (Samira Samadi, Adam Kalai)
HCOMP 2018
42 Efficient Convex Optimization with Membership Oracles (Yin Tat Lee, Aaron Sidford)
COLT 2018
43 Stochastic Localization + Stieltjes Barrier = Tight Bound for Log-Sobolev (Yin Tat Lee)
STOC 2018
44 Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation (Yin Tat Lee)
STOC 2018
45 The KLS conjecture (Yin Tat Lee)
Survey for Current Developments in Mathematics (CDM 2017)
46 Long-term Memory and the Densest k-Subgraph Problem (R.Legenstein, W. Maass, Christos Papadimitriou)
ITCS 2018
47 On the Complexity of Learning Neural Networks (J. Wilmes, B. Xie, L. Song)
NIPS 2017
48 Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion (Yin Tat Lee)
short version, FOCS 2017
49 Randomized Algorithms in Numerical Linear Algebra (Ravi Kannan)
Acta Numerica, 2017
50 The Hidden Hubs Problem (Ravi Kannan)
COLT 2017
51 Geodesic Walks in Polytopes (Yin Tat Lee)
STOC 2017 (invited to SICOMP special issue for STOC)
52 Adaptive Matrix Vector Product (D. P. Woodruff)
SODA 2017
53 Statistical Query Algorithms for Stochastic Convex Optimization (V. Feldman, C. Guzman)
SODA 2017
54 Geometric Random Edge (F. Eisenbrand)
Math Prog. (B) 2017
55 Agnostic Estimation of Mean and Covariance (Kevin Lai, Anup B. Rao)
FOCS 2016
56 Accelerated Newton Iteration for Roots of Blackbox Polynomials (Anand Louis)
FOCS 2016
57 Cortical Computation via Iterative Constructions (Christos Papadimitriou, Samantha Petti)
COLT 2016
58 C4G BLIS: Health Care Delivery via Iterative Collaborative Design in Resource-constrained Settings (N. Chopra, A. Rajagopal, J. Nkengasong, S. Akuro)
ICTD 2016
59 A Practical Volume Algorithm (B. Cousins)
Math Prog. (C), 2016
60 Subsampled Power Iteration: A Unified Algorithm for Block Models and Planted CSP's (V. Feldman, W. Perkins)
NIPS 2015
61 Publishable Humanly Usable Secure Password Creation Schemas (Manuel Blum)
HCOMP 2015
62 Visual Categorization via Random Projection (Rosa I. Arriaga, D. Rutter, M. Cakmak)
Neural Computation, Oct 2015
63 Cortical Learning via Prediction (C. H. Papadimitriou)
COLT 2015
64 Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity (Y. Xiao)
COLT 2015
65 Efficient Representations for Lifelong Learning and Autoencoding (M. F. Balcan, A. Blum)
COLT 2015
66 Bypassing KLS: Gaussian Cooling and an O*(n3) Volume Algorithm (B. Cousins)
STOC 2015 (SICOMP special issue for STOC)
67 The Complexity of Random Satisfiability Problems with Planted Solutions (V. Feldman, W. Perkins)
STOC 2015
68 Stochastic Billiards for Sampling from the Boundary of a Convex Set (T. Dieker)
Math. of OR, 2015
69 Principal Component Analysis and Higher Correlations for Distributed Data (R. Kannan, D. Woodruff)
COLT 2014
70 Fourier PCA and Robust Tensor Decomposition (N. Goyal, Y. Xiao)
STOC 2014
71 Integer Feasibility of Random Polytopes (K. Chandrasekaran)
ITCS 2014
72 A Cubic Algorithm for Computing Gaussian Volume (B. Cousins)
SODA 2014
73 Near-optimal Deterministic Algorithms for Volume Computation via M-ellipsoids (D. Dadush)
Proc. National Academy of Sciences (PNAS)
74 The Complexity of Approximating Vertex Expansion (A. Louis and P. Raghavendra)
FOCS 2013
75 Statistical Algorithms and a lower bound for detecting planted cliques (V. Feldman, E. Grigorescu, L. Reyzin, Y. Xiao)
STOC 2013
76 The approximate rank of a matrix and its algorithmic applications. (N. Alon, T. Lee, A. Shraibman)
STOC 2013
77 Randomly oriented k-d trees adapt to intrinsic dimension.
FSTTCS 2012
78 The cutting plane method is polynomial for perfect matchings. (K. Chandrasekaran, L. Vegh)
FOCS 2012, to appear in Math of OR.
79 Many sparse cuts via higher eigenvalues (A. Louis, P. Raghavendra, P. Tetali)
STOC 2012
80 Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms. (D. Dadush)
SODA 2012
81 Modeling High-dimensional Data: Technical Perspective.
Comm. ACM 55(2): 112, 2012.
82 Enumerative Lattice Algorithms in Any Norm via M-Ellipsoid Coverings (D. Dadush, C. Peikert)
Proc. of FOCS 2011.
83 A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions(D. Stefankovic, E. Vigoda)
Proc. of FOCS 2011.
SIAM J. Comp., 41(2): 356-366, 2012
84 Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues (A. Louis, P. Raghavendra, P. Tetali)
Proc. of APPROX 2011.
85 Semantic Communication for Simple Goals is Equivalent to On-line Learning (B. Juba)
Proc. of ALT 2011.
86 On Noise-Tolerant Learning of Sparse Parities and Related Problems (E. Grigorescu, L. Reyzin)
Proc. of ALT 2011.
87 LifeNet: A Flexible Ad hoc Networking Solution for Transient Environments (H. Mehendale, A. Paranjpe)
SIGCOMM 2011, demo.
88 Algorithms for Implicit Hitting Set Problems (K. Chandrasekaran, R. Karp, E. Moreno-Centeno)
Proc. of SODA 2011.
89 Learning Convex Concepts from Gaussian Distributions with PCA
Proc. of FOCS 2010.
90 On Nash-Equilibria of Approximation-Stable Games (P. Awasthi, N. Balcan, A. Blum, O. Sheffet)
Proc. of SAGT 2010.
91 Chipping Away at Censorship with User-Generated Content (S. Burnett, N. Feamster)
Proc. of USENIX Security 2010.
92 A Random Sampling Algorithm for Learning an Intersection of Halfspaces
JACM, 2010.
93 A New Approach to Strongly Polynomial Linear Programming (M. B r sz)
Proc. of ICS 2010.
94 Thin Partitions: Isoperimetry and Sampling for Star-shaped Bodies (K. Chandrasekara, D. Dadush)
Proc. of SODA 2010.
95 MyMANET: A Customizable Mobile Ad hoc Network (A. Paranjpe)
Proc. of ACM NSDR 2009.
96 Random Tensors and Planted Cliques (S. C. Brubaker)
Proc. of RANDOM 2009.
97 Sampling s-Concave Functions: The Limit of Convexity-based Isoperimetry (K. Chandrasekaran, A. Deshpande)
Proc. of RANDOM 2009.
98 Design and Deployment of a Blood Safety Monitoring Tool (S. Thomas, A. Osuntogun, J. Pitman, B. Mulenga)
Proc. of ICTD 2009.
99 Expanders via Random Spanning Trees (N. Goyal, L. Rademacher)
Proc. of SODA 2009.
100 Algorithmic Prediction of Health-Care Costs (D. Bertsimas, M. V. Bjarnad ttir, M. A. Kane, J. C. Kryder, R. Pandey, G. Wang )
Operations Research, 2008 (special issue on Health Care).
101Isotropic PCA and Affine-Invariant Clustering (S.C. Brubaker) [conf version]
Building Bridges (Ed.s M. Gr\"{o}tchel and G.O.H.Katona), Bolyai Society Mathematical Studies, 2008. (special issue in honor of L. Lov sz).
Proc. of FOCS 2008.
102Path Splicing (M. Motiwala, M. Elmore and N. Feamster)
Proc. of SIGCOMM, 2008.
103 Logconcave Random Graphs (A. Frieze and J. Vera)
Proc. of STOC 2008.
104A Discriminative Framework for Clustering via Similarity Functions (M. F. Balcan and A. Blum)
Proc. of STOC, 2008.
105Life (and Routing) on the Wireless Manifold (V. Kanade)
Proc. of HotNets, 2007.
106Path Splicing: Reliable Connectivity with Rapid Recovery (M. Motiwala and N. Feamster)
Proc. of HotNets, 2007.
107 Filtering Spam with Behavioral Blacklisting (A. Ramachandran and N. Feamster)
Proc. ACM Computer and Communication Security, 2007.
108 Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting (D. Stefankovic and E. Vigoda)
JACM 2009
Proc. of the 48th IEEE Symposium on Foundations of Computer Science (FOCS '07), 2007. (invited to special issue)
109 An Efficient Re-scaled Perceptron Algorithm for Conic Systems (A. Belloni, R. Freund)
Proc. of 20th Conf. on Computational Learning Theory, San Diego, 2007.
110 Dispersion of Mass and the Complexity of Randomized Geometric Algorithms (L. Rademacher)
Proc. of the 47th IEEE Symposium on Foundations of Computer Science (FOCS '06), 2006.
Advances in Mathematics, 2008.
111 Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization (L. Lov sz)
Proc. of the 47th IEEE Symposium on Foundations of Computer Science (FOCS '06), 2006.
112Adaptive Sampling and Fast Low-rank Matrix Approximation (A. Deshpande)
Proc. of RANDOM, 2006.
113Symmetric Network Computation (D. Pritchard)
Proc. of ACM SPAA, 2006.
114Matrix Approximation and Projective Clustering via Volume Sampling (A. Deshpande, L. Rademacher and G. Wang)
Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms, 2006.
Theory of Computing, 2006
115Local versus Global Properties of Metric Spaces (S. Arora, L. Lov sz, I. Newman, Y. Rabani and Y. Rabinovich)
Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms, 2006.
SIAM J. Comp. 41(1): 250-271, 2012
116 Nash Equilibria in Random Games (I. Barany and A. Vetta)
Proc. of the 46th IEEE Symposium on Foundations of Computer Science (FOCS '05), 2005. (invited to special issue)
Random Structures and Algorithms, 2007.
117 The spectral method for general mixture models (R. Kannan and H. Salmasian)
Proc. of the 18th Conference on Learning Theory, 2005 (Mark Fulk award).
SIAM J. Computing, 2008.
118 A Divide-and-Merge Methodology for Clustering (D. Cheng, R. Kannan and G. Wang)
Proc. of the ACM Symposium on Principles of Database Systems, 2005.
ACM Trans. Database Systems, 2006.
119 Tensor decomposition and approximation schemes for constraint satisfaction problems.
(W. F. de la Vega, R. Kannan and M. Karpinski)
Proc. of the 37th ACM Symposium on the Theory of Computing (STOC '05), 2005.
120 Geometric Random Walks: A Survey.
MSRI volume on Combinatorial and Computational Geometry.
121 Testing geometric convexity. (Luis Rademacher)
Proc. of the 24th FST & TCS, Chennai, 2004.
122 On Kernels, Margins and Low-dimensional Mappings. (Nina Balcan, Avrim Blum)
Proc. of the 15th Conf. Algorithmic Learning Theory, Padua, 2004.
Machine Learning
123 Hit-and-run from a corner. (L. Lov sz)
Proc. of the 36th ACM Symposium on the Theory of Computing (STOC '04), Chicago, 2004.
SIAM J. Computing (STOC04 special issue).
124 A simple polynomial-time rescaling algorithm for solving linear programs.(J. Dunagan)
Proc. of the 36th ACM Symposium on the Theory of Computing (STOC '04), Chicago, 2004.
Math. Prog. A
125 Simulated annealing in convex bodies and an O*(n^4) volume algorithm. (L. Lov sz)
Proc. of the 44th IEEE Foundations of Computer Science (FOCS '03), Boston, 2003.
JCSS (FOCS03 special issue).
126Simulated annealing for convex optimization . (Adam Kalai)
Math of OR.
127 Logconcave functions: Geometry and efficient sampling algorithms. (L. Lov sz)
Proc. of the 44th IEEE Foundations of Computer Science (FOCS '03), Boston, 2003.
Random Structures and Algorithms
128 Efficient algorithms for the online decision problem. (Adam Kalai)
Proc. of 16th Conf. on Computational Learning Theory, Washington D.C., 2003.
129 A spectral algorithm for learning mixtures of distributions. (Grant Wang)
Proc. of the 43rd IEEE Foundations of Computer Science (FOCS '02), Vancouver, 2002.
JCSS (special issue for FOCS '02), 68(4), 841--860, 2004.
130 Solving convex programs by random walks. (Dimitris Bertsimas)
Journal of the ACM (JACM) 51(4), 540--556, 2004.
Proc. of the 34th ACM Symposium on the Theory of Computing (STOC '02), Montreal, 2002.
131 An approximation algorithm for the minimum-cost k-vertex connected subgraph.
(Joseph Cheriyan, Adrian Vetta)
SIAM J. Computing, 32(4) (2003), 1050-1055.
132 Network design via iterative rounding of setpair relaxations. (Joseph Cheriyan, Adrian Vetta)
Combinatorica.
A preliminary version of the previous two appeared as
Approximation algorithms for minimum-cost k-connected subgraphs.
Proc. of the 34th ACM Symposium on the Theory of Computing (STOC '02), Montreal, 2002.
133 Flow metrics. (Claudson Bornstein)
Proc. of the 5th Symposium on Latin American Theoretical Informatics, Cancun, 2002.
Theoretical Computer Science (special issue for LATIN '02), 321(1), 13--24, 2004.
134 On Euclidean embeddings and bandwidth minimization. (John Dunagan)
Proc. of the 5th Workshop on Randomization and Approximation, Berkeley, 2001.
135 Optimal outlier removal in high-dimensional spaces. (John Dunagan)
Proc. of the 33rd ACM Symposium on the Theory of Computing (STOC '01), Crete, 2001.
JCSS (special issue for STOC '01), 68(2), 335--373, 2004.
136 Edge covers of setpairs and the iterative rounding method. (Joseph Cheriyan)
Proc. of Integer Programming and Combinatorial Optimization, Utrecht, 2001.
137 Fences are futile: on relaxations for the linear ordering problem. (Alantha Newman)
Proc. of Integer Programming and Combinatorial Optimization, Utrecht, 2001.
138 On clusterings: good, bad and spectral. (Ravi Kannan and Adrian Vetta)
Journal of the ACM (JACM) 51(3), 497--515, 2004.
Proc. of the 41st Foundations of Computer Science (FOCS '00), Redondo Beach, 2000.
139 Efficient algorithms for universal portfolios. (Adam Kalai)
J. Machine Learning Research, 3, (2002), 423--440 (invited).
Proc. of the 41st Foundations of Computer Science (FOCS '00), Redondo Beach, 2000.
140 Factor 4/3 approximations for minimum 2-connected subgraphs. (Adrian Vetta)
Proc. of the 3rd Workshop on Approximation , Saarbrucken, 2000.
141 On the approximability of the traveling salesman problem. (Christos H. Papadimitriou)
Proc. of the 32nd ACM Symposium on the Theory of Computing (STOC '00), Portland, 2000.
Combinatorica.
142 Randomized meta-rounding. (Bob Carr)
Random Structures and Algorithms, 20(3), (2002), 343-352 (invited).
Proc. of the 32nd ACM Symposium on the Theory of Computing (STOC '00), Portland, 2000.
143 On the Held-Karp relaxation for the asymmetric and symmetric TSPs. (Bob Carr)
Proc. of the 11th ACM-SIAM Symposium on Discrete Algorithms , San Francisco, 2000.
Mathematical Programming, 100(3), 569--587, 2004.
144 Approximating multicast congestion. (Berthold Vocking)
Proc. of ISAAC, Chennai, 1999.
145 An algorithmic theory of learning: Robust Concepts and Random Projection. (Rosa I. Arriaga)
Proc. of the 40th Foundations of Computer Science (FOCS '99), New York, 1999.
Machine Learning, 2006.
146 A convex relaxation for the Asymmetric TSP. (Mihalis Yannakakis)[two pages only]
Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 1999.
147 Clustering large graphs via the Singular Value Decomposition. (Petros Drineas, Ravi Kannan, Alan Frieze and V. Vinay)
Machine Learning 56, 9--33, 2004.
Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 1999.
148 Random Projection: A New Approach to VLSI Layout.
Proc. of the 39th Foundations of Computer Science (FOCS '98), Palo Alto, 1998.
149 Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. (A. Frieze, R. Kannan)
Proc. of the 39th Foundations of Computer Science (FOCS '98), Palo Alto, 1998.
Journal of the ACM (JACM), 51(6), 1025-1041, 2004.
150 Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems.
(Avrim Blum, Goran Konjevod and R. Ravi)
Proc. of the 30th ACM Symposium on the Theory of Computing (STOC '98), Dallas, 1998.
Theoretical Computer Science, 235 (2000), 25-42 (special issue in honour of Manuel Blum).
151 A Random Sampling based Algorithm for learning the Intersection of Half-spaces
Proc. of the 38th Foundations of Computer Science (FOCS '97), Miami, 1997. (Machtey Prize)
152 Sampling Lattice Points. (Ravi Kannan)
Proc. 29th ACM Symposium on the Theory of Computing (STOC '97), El Paso, 1997.
Invited for publication in Journal of Comp. and System Sciences.
153 Locality-Preserving Hashing in Multidimensional Spaces.
(Piotr Indyk, Rajeev Motwani and Prabhakar Raghavan)
Proc. 29th ACM Symposium on the Theory of Computing (STOC '97), El Paso, 1997.
154 Latent Semantic Indexing: A Probabilistic Analysis.
(Christos Papadimitriou, Prabhakar Raghavan and Hisao Tamaki)
Proc. 17th ACM Symposium on the Principles of Database Systems, Seattle, 1998.
Journal of Comp. and System Sciences (special issue for PODS '01), 61, 2000 217-235.
155 Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments.
(Ravi Kannan and Prasad Tetali)
Proc. 8th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 1997.
Random Structures and Algorithms, 14(4), 1999, 293-308.
156 A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
(Avrim Blum, Alan Frieze and Ravi Kannan)
Proc. 37th IEEE Symposium on the Foundations of Computer Science (FOCS '96), Burlington, 1996.
Algorithmica, 22(1), 35-52 (invited).
157 The Colin de Verdiere Number and Sphere Representations of a Graph
(Andrew Kotlov and Laszlo Lovasz)
Combinatorica, 17(4), 1997.
158 A Constant-Factor Approximation for the k-MST Problem. (Avrim Blum, R. Ravi)
Proc. 28th ACM Symposium on the Theory of Computing (STOC '96), Philadelphia, 1996.
J. Computer and System Sciences, 58(1), 101-108 (special issue for STOC '96).
159 Improved Approximations for Minimum-Weight k-Trees and Prize-Collecting Salesmen.
(Baruch Awerbuch, Yossi Azar, Avrim Blum)
Proc. 27th ACM Symposium on the Theory of Computing (STOC '95), Las Vegas, 1995.
SIAM J. on Computing, 28(1) 1999.
160 A Constant-Factor Approximation for the k-MST Problem in the Plane. (A. Blum, P. Chalasani)
Proc. 27th ACM Symposium on the Theory of Computing (STOC '95), Las Vegas, 1995.
161 A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane
(J.S.B. Mitchell, A. Blum, P. Chalasani)
Siam J. on Computing , 28(3) 1999.
162 Improved Approximations for Finding Minimum 2-connected Subgraphs via Better Lower-Bounding Techniques
(Naveen Garg, Aman Singla)
Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, Austin, 1993.
163 A Limited-Backtrack Greedy Schema for Approximation Algorithms
Proc. 14th Conf. on the Foundations of Software Technology and Theoretical Computer Science, Madras, 1994.