Petros Drineas::Publications

Contact Info

Email: d r i n e p AT c s . r p i . e d u
Physical address: Lally Hall, Room 317, 110 8th Street, Troy, NY 12180, USA
Phone: +1 (518) 276 8265
Fax: +1 (518) 276 4033

Publications

Manuscripts

P. Drineas, M. W. Mahoney, S. Muthukrishnan, and T. Sarlos, Faster least squares approximation, Oct 2007 (revised May 2009).
C. Boutsidis, M.W. Mahoney, and P. Drineas, An improved approximation algorithm for the column subset selection problem, Dec 2008.

2009

C. Boutsidis and P. Drineas, Random projections for the nonnegative least-squares problem, Dec 2008 (revised Mar 2009), to appear in Linear Algebra and its Applications.
H-G. D. Stratigopoulos, P. Drineas, M. Slamani, and Y. Makris, RF specification test compaction using learning machines, IEEE Transactions on VLSI, to appear, 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, to appear
in the 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 Symposiumon 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 TechnicalReport 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 DiscreteAlgorithms (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. Drineas and 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 forNP-Hard Problems, Oberwolfach, Germany, 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), Maastricht, Netherlands, 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.