Petros Drineas::Publications

Petros Drineas

Contact Info

Email: drinep@cs.rpi.edu
Physical address: Lally Hall, Room 317, 110 8th Street, Troy, NY 12180, USA
Phone: +1 (518) 276 8265
Fax: +1 (518) 276 4033

Publications

(Please e-mail me for copies of papers that are not available online.)

2013

P. Saurabh, C. Boutsidis, M. Magdon-Ismail, and P. Drineas, Random Projections for Support Vector Machines, under review.
K. Clarkson, P. Drineas, M. Magdon-Ismail, M. W. Mahoney, X. Meng, and D. P. Woodruff, Faster Robust Linear Regression, under review.
C. Boutsidis, P. Drineas, and M. Magdon-Ismail, Rich Coresets for Contstrained Linear Regression, under review.
C. Boutsidis, A. Zouzias, M. W. Mahoney, and P. Drineas, Stochastic Dimensionality Reduction for K-means Clustering, under review.
C. Boutsidis, P. Drineas, and M. Magdon-Ismail, Near-Optimal Column-Based Matrix Reconstruction, under review.
N. Nguyen, P. Drineas, and T. Tran, Tensor Sparsification via a Bound on the Spectral Norm of Random Tensors, under review.
C. Boutsidis, M.W. Mahoney, and P. Drineas, An improved approximation algorithm for the column subset selection problem, under review.
K. Clarkson, P. Drineas, M. Magdon-Ismail, M. W. Mahoney, X. Meng, and D. P. Woodruff, The Fast Cauchy Transform and Faster Robust Linear Regression, Proc. of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.

2012

P. Drineas, M. Magdon-Ismail, M. W. Mahoney, and D. Woodruff, Fast Approximation of Matrix Coherence and Statistical Leverage, Journal of Machine Learning Research, 13, pp. 3475-3506 , 2012.
V. Stathias, G. Sotiris, I. Karagiannidis, G. Bourikas, G. Martinis, D. Papazoglou, A. Tavridou, N. Papanas, E. Maltezos, M. Theodoridis, V. Vargemezis, V. Manolopoulos, W. C. Speed, J. R. Kidd, K. K. Kidd, P. Drineas, and P. Paschou, Exploring genomic structure differences and similarities between the Greek and European HapMap populations: implications for association studies, Annals of Human Genetics, 76(6), pp. 472-483, 2012.
P. Drineas, M. Magdon-Ismail, M. W. Mahoney, and D. Woodruff, Fast Approximation of Matrix Coherence and Statistical Leverage, International Conference on Machine Learning (ICML), 2012.

2011

N. Kupp, H. Huang, P. Drineas, and Y. Makris, Improving Analog and RF Device Yield through Performance Calibration, IEEE Design and Test of Computers, 28(3), pp. 64-75, 2011.
N. Kupp, H. Stratigopoulos, P. Drineas, and Y. Makris, On Proving the Efficiency of Alternative RF Tests, International Conference on Computer-Aided Design (ICCAD), pp. 762-767, 2011.
C. Boutsidis, P. Drineas, and M. Magdon-Ismail, Sparse Features for PCA-Like Linear Regression, Proc. of Neural Information Processing Systems (NIPS), 2011.
C. Boutsidis, P. Drineas, and M. Magdon-Ismail, Near-Optimal Column-Based Matrix Reconstruction, Proc. of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), 2011.
A. Javed, P. Drineas, M. W. Mahoney, P. Paschou, Efficient genome-wide selection of PCA-correlated tSNPs for genotype imputation, Annals of Human Genetics, 75(6), pp. 707-722, 2011.
J. Lewis, Z. Abas, C. Dadousis, D. Lykidis, P. Paschou, and P. Drineas, Tracing Cattle Breeds With Principal Components Analysis Ancestry Informative SNPs, PLoS ONE, 6(4): e18007, 2011.
U. Acer, P. Drineas, and A. Abouzeid, Connectivity in Time-Graphs, Pervasive and Mobile Computing, 7, pp. 160-171, 2011.
N. G. Sgourakis, M. Merced-Serrano, C. Boutsidis, P. Drineas, Z. Du, C. Wang, and A. E. Garcia, Atomic-level characterization of the ensemble of the Aβ(1-42) monomer in water using unbiased molecular dynamics simulations and spectral algorithms, Journal of Molecular Biology, 405(2), pp.570-583, 2011.
P. Drineas, M. W. Mahoney, S. Muthukrishnan, and T. Sarlos, Faster Least Squares Approximation, Numerische Mathematik, 117(2), pp. 217-249, 2011.
C. Tsourakakis, P. Drineas, E. Michelakis, I. Koutis, and C. Faloutsos, Spectral Counting of Triangles via Element-Wise Sparsification and Triangle-Based Link Recommendation, Journal of Social Network Analysis and Mining (SNAM), 1(2), pp. 75-81, 2011.
P. Drineas and A. Zouzias, A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality, Information Processing Letters, 111, pp. 385-389, 2011.

2010

P. Drineas and M. W. Mahoney, Effective Resistances, Statistical Leverage, and Applications to Linear Equation Solving, arXiv1005:3097, 2010.
P. Paschou, J. Lewis, A. Javed, and P. Drineas, Ancestry Informative Markers for Fine-Scale Individual Assignment to Worldwide Populations, Journal of Medical Genetics, doi:10.1136/jmg.2010.078212, 2010.
P. Drineas, J. Lewis, and P. Paschou, Inferring Geographic Coordinates of Origin for Europeans using Small Panels of Ancestry Informative Markers, PLoS ONE, 5(8):e11892, 2010.
H-G. D. Stratigopoulos, P. Drineas, M. Slamani, and Y. Makris, RF specification test compaction using learning machines, IEEE Transactions on VLSI Systems, 18(6), pp. 1002-1006, 2010.
U. Acer, P. Drineas, and A. Abouzeid, Random walks in time-graphs, Proceedings of the Second International Workshop on Mobile Opportunistic Networking (MobiOpp), pp. 93-100, 2010.
C. Boutsidis, A. Zouzias, and P. Drineas, Random Projections for k-means Clustering, Proc. of Neural Information Processing Systems (NIPS), 2010.
N. Kupp, H. Huang, P. Drineas, and Y. Makris, Post-Production Performance Calibration in Analog/RF Devices, IEEE International Test Conference (ITC), 8.3.1-8.3.10, 2010.

2009

C. Boutsidis, M.W. Mahoney, and P. Drineas, Unsupervised Feature Selection for the k-means Clustering Problem, Proc. of Neural Information Processing Systems (NIPS), 2009.
C. Boutsidis and P. Drineas, Random projections for the nonnegative least-squares problem, Linear Algebra and its Applications, 431, pp. 760-771, 2009.
A. Dasgupta, P. Drineas, B. Harb, R. Kumar, and M. W. Mahoney, Sampling algorithms and coresets for lp regression, SIAM Journal on Computing, 38(5), pp. 2060-2078, 2009.
M. W. Mahoney and P. Drineas, CUR matrix decompositions for improved data analysis, Proceedings of the National Academy of Sciences, 106(3), pp. 697-702, 2009.
C. Tsourakakis, P. Drineas, E. Michelakis, I. Koutis, and C. Faloutsos, Spectral counting of triangles in power-law networks via element-wise sparsification, International Conference on Advances in Social Network Analysis and Mining (ASONAM), 2009.
C. Boutsidis, M.W. Mahoney, and P. Drineas, An improved approximation algorithm for the column subset selection problem, Proc. of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 968-977, 2009.

2008

M. W. Mahoney, M. Maggioni, and P. Drineas, Tensor-CUR decompositions for tensor-based data, SIAM Journal on Matrix Analysis and Applications, 30(2), pp. 957-987, 2008.
P. Drineas, M.W. Mahoney, and S. Muthukrishnan, Relative-error CUR matrix decompositions, SIAM Journal on Matrix Analysis and Applications, 30(2), pp. 844-881, 2008.
P. Paschou, P. Drineas, J. Lewis, C. Nievergelt, D. Nickerson, J. Smith, P. Ridker, D. Chasman, R. Krauss, and E. Ziv, Tracing sub-structure in the European American population with PCA-informative markers, PLoS Genetics, 4(7), pp. 1-13, 2008.
C. Boutsidis, M.W. Mahoney, and P. Drineas, Unsupervised feature selection for Principal Components Analysis, Proc. of the 14th Annual ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 61-69, 2008.
N. Kupp, P. Drineas, M. Slamani, and Y. Makris, Confidence estimation in non-RF to RF correlation-based specification test compaction, Proc. of the 13th European Test Symposium (ETS), pp. 35-40, 2008.
A. Dasgupta, P. Drineas, B. Harb, R. Kumar, and M. W. Mahoney, Sampling algorithms and coresets for lp regression, Proc. of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 932-941, 2008.

2007

P. Paschou, E. Ziv, E. Burchard, S. Choudhry, W. Rodriguez-Cintron, M. W. Mahoney, and P. Drineas, PCA-correlated SNPs for structure identification in worldwide human populations, PLOS Genetics, 3(9), pp. 1672-1686, 2007.
P. Paschou, M. W. Mahoney, A. Javed, J. Kidd, A. Pakstis, S. Gu, K. Kidd, and P. Drineas, Intra- and inter-population genotype reconstruction from tagging SNPs, Genome Research, 17(1), pp. 96-107, 2007.
P. Drineas and M. W. Mahoney, A randomized algorithm for a tensor-based generalization of the SVD, Linear Algebra and its Applications, 420, pp. 553-571, 2007.
P. Drineas, M. W. Mahoney, and R. Kannan, Sampling sub-problems of heterogeneous max-cut problems and approximation algorithms, Random Structures and Algorithms,32(3), pp. 307-333, 2007.
A. Dasgupta, P. Drineas, B. Harb, V. Josifovski, and M. Mahoney, Feature selection methods for text classification, Proc. of the 13th Annual ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 230-239, 2007.
H-G. D. Stratigopoulos, P. Drineas, M. Slamani, and Y. Makris, Non-RF to RF test correlation using learning machines: a case study, Proc. of the 25th IEEE VLSITest Symposium (VTS), pp. 9-14, 2007.

2006

G.H. Golub, M.W. Mahoney, P. Drineas, and L.-H. Lim, MMDS 2006: bridging the gap between numerical linear algebra, theoretical computer science, and data applications, SIAM News, Oct 2006.
P. Drineas, R. Kannan, and M. W. Mahoney, Fast monte carlo algorithms for matrices I: approximating matrix multiplication, SIAM Journal on Computing, 36(1), pp. 132-157, 2006.
P. Drineas, R. Kannan, and M. W. Mahoney, Fast monte carlo algorithms for matrices II: computing a low rank approximation to a matrix, SIAM Journal on Computing, 36(1), pp. 158-183, 2006.
P. Drineas, R. Kannan, and M. W. Mahoney, Fast monte carlo algorithms for matrices III: computing a compressed approximate matrix decomposition, SIAM Journal on Computing, 36(1), pp. 184-206, 2006.
S. Almukhaizim, P. Drineas, and Y. Makris, Entropy-driven parity tree selection for low-overhead concurrent error detection in finite state machines, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(8), pp. 1547-1554, 2006.
P. Drineas, M. W. Mahoney, and S. Muthukrishnan, Subspace sampling and relative error matrix approximation: column-based methods, Proc. of APPROX-RANDOM, pp. 316-326, 2006.
P. Drineas, M. W. Mahoney, and S. Muthukrishnan, Subspace sampling and relative error matrix approximation: column-row-based methods, Proc. of the 14th Annual European Symposium on Algorithms (ESA), pp. 304-314, 2006.
P. Drineas, M. W. Mahoney, and S. Muthukrishnan, Polynomial time algorithm for column-row based relative error low-rank matrix approximation, DIMACS Technical Report 2006-04, 2006.
P. Drineas, A. Javed, M. Magdon-Ismail, G. Pandurangan, R. Virrankoski, and A. Savvides, Distance matrix reconstruction from incomplete distance information for sensor network localization, Proc. of the 3rd Annual IEEE Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), pp. 536-544, 2006.
P. Drineas and M. W. Mahoney, Randomized algorithms for matrices and massive data sets, Proc. of the 32nd Annual Conference on Very Large Data Bases (VLDB), p. 1269, 2006.
M. W. Mahoney, M. Maggioni, and P. Drineas, Tensor-CUR decompositions for tensor-based data, Proc. of the 12th Annual ACM Conference on Knowledge Discovery andData Mining (KDD), pp. 327-336, 2006.
P. Drineas, M. W. Mahoney, and S. Muthukrishnan, Sampling algorithms for l2 regression and applications, Proc. of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1127-1136, 2006.

2005

P. Drineas and M. W. Mahoney, On the Nystrom method for approximating a Gram matrix for improved kernel-based learning, Journal of Machine Learning Research 6, pp. 2153-2175, 2005.
S. Almukhaizim, P. Drineas, and Y. Makris, Compaction-based concurrent error detection for digital circuits, Microelectronics Journal, 36(9), pp. 856-862, Elsevier, 2005.
D. Freedman and P. Drineas, Energy minimization via graph cuts: settling what is possible, Proc. of the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), pp. 939-946, 2005.
P. Drineasand M. W. Mahoney, Approximating a Gram matrix for improved kernel-based learning, Proc. of the 18th Annual Symposium on Computational Learning Theory (COLT), pp. 323-337, 2005.
P. Drineas, R. Kannan, and M. W. Mahoney, Sampling sub-problems of heterogeneous max-cut problems and approximation algorithms, Proc. of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in ComputerScience 3404, pp. 57-68, 2005.

2004

P. Drineas, R. Kannan, A. Frieze, S. Vempala, and V. Vinay, Clustering of large graphs via the singular value decomposition, Machine Learning (56), pp. 9-33, 2004.
K. Akcoglu, P. Drineas, and M. Kao, Fast universalization of investment strategies, SIAM Journal on Computing 34(1), pp. 1-22, 2004.
P. Drineas, M. Krishnamoorthy, D. Sofka, and B. Yener, Studying E-mail graphs for intelligence monitoring and analysis in the absence of semantic information, Proc. of the Symposium on Intelligence and Security Informatics, Lecture Notes in Computer Science 3073, pp. 297-306, 2004.
P. Drineas, Pass efficient algorithms for approximating large matrices, Mathematisches Forschungsinstitut Oberwolfach (MFO) Workshop on Approximation Algorithms for NP-Hard Problems, Oberwolfach, 2004.
S. Almukhaizim, P. Drineas, and Y. Makris, Cost-driven selection of parity trees, Proc. of the IEEE VLSI Test Symposium (VTS), pp. 319-324, 2004.
S. Almukhaizim, P. Drineas, and Y. Makris, Concurrent error detection for combinational and sequential logic via output compaction, Proc. of the IEEE International Symposium on Quality Electronic Design (ISQED), pp. 459-464, 2004.
S. Almukhaizim, P. Drineas, and Y. Makris, On concurrent error detection with bounded latency in FSMs, Proc. of the IEEE Design Automation and Test in Europe Conference(DATE), pp. 596-601, 2004.

2003

P. Drineas and Y. Makris, SPaRe: selective partial replication for concurrent fault detection in FSMs, IEEE Transactions on Instrumentation and Measurement, 52(6), pp. 1729-1737, 2003.
P. Drineas, E. Drinea, and P. Huggins, An experimental evaluation of a monte carlo algorithm for singular value decomposition, Y. Manolopoulos et. al. (Eds.): Revised Selected Papers from the 8th Panhellenic Conference on Informatics, Lecture Notes in Computer Science 2563, pp. 279-296, 2003.
P. Drineas and R. Kannan, Pass efficient algorithms for approximating large matrices, Proc. of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 223-232, 2003.
S. Almukhaizim, P. Drineas, and Y. Makris, On Compaction-based concurrent error detection, Proc. of the IEEE On-Line Test Symposium, pp. 157, 2003.
P. Drineas and Y. Makris, Independent test sequence compaction through integer programming, Proc. of the IEEE International Conference on Computer Design (ICCD), pp. 380-386, 2003.
P. Drineas and Y. Makris, Non-intrusive concurrent error detection in FSMs through State/Output compaction and monitoring via parity trees, Proc. of the Design Automation and Test in Europe Conference (DATE), pp. 1164-1165, 2003.
P. Drineas and Y. Makris, SPaRe: selective partial replication for concurrent fault detection in FSMs, Proc. of the IEEE International Conference on VLSI Design, pp. 84-91, 2003.
P. Drineas and Y. Makris, On the Compaction of Independent Test Sequences for Sequential Circuits, IEEE European Test Workshop (ETW), 2003.
P. Drineas and Y. Makris, Concurrent fault detection in random combinational logic, Proc. of the IEEE International Symposium on Quality Electronic Design (ISQED), pp. 425-430, 2003.

2002

P. Drineas, I. Kerenidis, and P. Raghavan, Competitive recommendation systems, Proc. of the 34th ACM Symposium on Theory of Computing (STOC), pp. 82-90, 2002.
K. Akcoglu, P. Drineas, and M. Kao, Fast universalization of investment strategies with provably good relative returns, Proc. of the 29th International Colloquium on Automata, Languages and Programming (ICALP), pp. 888-900, 2002.
P. Drineas and Y. Makris, Non-intrusive design of concurrently self-testable FSMs, Proc. of the IEEE Asian Test Symposium (ATS), pp. 33-38, 2002.
P. Drineas and Y. Makris, Non-intrusive design of concurrently self-testable FSMs, IEEE North Atlantic Test Workshop (NATW), Montauk NY, USA, 2002.

2001

E. Drinea, P. Drineas, and P. Huggins, A randomized singular value decomposition algorithm for image processing applications, Proc. of the 8th Panhellenic Conference on Informatics, pp. 278-288, 2001.
P. Drineas and R. Kannan, Fast monte carlo algorithms for approximate matrix multiplication, Proc. of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 452-459, 2001.

1999

P. Drineas, R. Kannan, A. Frieze, S. Vempala, and V. Vinay, Clustering in large graphs and matrices, Proc. of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 291-299, 1999.