Academic Work
2018;
2017;
2016;
2015;
2014;
2013;
2012;
2011;
2010;
2009;
2008;
2007;
2006;
2005;
2004;
2003;
2002;
2001;
2000;
1999 and before.
Publications:
2018:

(2018 Jrnl)
A. F. Atiya, Malik MagdonIsmail,
"The maximum drawdown of discrete time processes", Advanced Mathematical
Models and Applications, Vol. 3, No. 2, pages 95105, 2018.
(print)
(pdf).
Summary:
We derive the MDDdistribution for a discrete time process
using integral equation recursions.

(2018 Jrnl)
Petros Drineas, Ilse Ipsen, EugeniaMaria Kontopoulou, Malik MagdonIsmail,
"Structural convergence results for approximation of dominant subspaces from block Krylov spaces",
SIAM Journal on Matrix Analysis and Applications,
Vol. 39, No. 2, pp 567586, 2018.
(print)
(preprint).
Summary:
This paper is concerned with approximating the dominant left singular vector space of a real matrix A of arbitrary dimension, from block Krylov spaces generated by the matrix AAT and the block vector AX. Two classes of results are presented. First are bounds on the distance, in the two and Frobenius norms, between the Krylov space and the target space. The distance is expressed in terms of principal angles. Second are quality of approximation bounds, relative to the best approximation in the Frobenius norm. For starting guesses X of full columnrank, the bounds depend on the tangent of the principal angles between X and the dominant right singular vector space of A. The results presented here form the structural foundation for the analysis of randomized Krylov space methods. The innovative feature is a combination of traditional Lanczos convergence analysis with optimal approximations via least squares problems.

(2018 Conf) Malik MagdonIsmail, Lirong Xia
"A Mathematical Model For Optimal Decisions In A
Representative Democracy",
NIPS, Dec. 2018.
(pdf)
( ppt)

(2018 Conf) Kshiteesh Hegde, Malik MagdonIsmail,
"Separating TerroristLike Topological Signatures
Embedded in Benign Networks",
MILCOM, Oct. 2018.
(pdf)
( ppt)

(2018 Conf) Prasanna Date, Christopher Carothers, Malik MagdonIsmail, James Hendler,
"Efficient Classification of Supercomputer Failures Using Neuromorphic Computing",
IEEE Symposium Series on Computational Intelligence (SSCI), Nov 2018.
(pdf)
( ppt)

(2018 Ligntning Talk, Not In Proceedings) Prasanna Date, Christopher Carothers, Malik MagdonIsmail, James Hendler,
"Efficient Classification of Supercomputer Failures Using Neuromorphic Computing",
Int. Conf. Neuromorphic Computing (ICONS), Knoxville, Tennessee, July 2018.
(pdf)
( ppt)
2017:

(2017 Jrnl)
Abhisek Kundu, Petros Drineas, Malik MagdonIsmail,
"Recovering PCA and Sparse PCA via Hybrid(l1,l2) Sparse Sampling of Data Elements",
Journal of Machine Learning Research (JMLR): 18(75):134, 2017.
(print)
(preprint).
Summary:
We show that a sparse sampling of the elements of a matrix using
sampling probabilitis based on a hybrid of L1 and L2 elementnorms
give better spectral reconstruction that using either elementnorm
independently. We show that this allows us to reconstruct
PCA and sparsePCA from incomplete data. We also consider
extensions to the streaming setting.

(2017 Jrnl)
Malik MagdonIsmail
"NPhardness and inapproximability of sparse PCA",
Information Processing Letters, Volume 126, October 2017, Pages 3538.
(print)
(preprint).
Summary:
Using a reduction from CLIQUE we show NPhardness and inapproximability
of Sparse PCA.
2016:

(2016 WkgPap)
P. Drineas, I. Ipsen, E. Kontopoulou, Malik MagdonIsmail
" Structural Convergence Results for LowRank Approximations from Block Krylov Spaces",
(arXiv).
Summary:
This paper is concerned with approximating the dominant left singular vector space of a real matrix A of arbitrary dimension, from block Krylov spaces q(AAT,AX). Two classes of results are presented. First are bounds on the distance, in the two and Frobenius norms, between the Krylov space and the target space. The distance is expressed in terms of principal angles. Second are quality of approximation bounds, relative to the best lowrank approximation in the Frobenius norm. For starting guesses X of full columnrank, the bounds depend on the tangent of the principal angles between X and the dominant right singular vector space of A. The results presented here form the structural foundation for the analysis of randomized Krylov space methods. The innovative feature is a combination of traditional Lanczos convergence analysis with optimal lowrank approximations via least squares problems.

(2016 WkgPap)
A. Kundu, P. Drineas, Malik MagdonIsmail
"Recovering PCA from Hybrid(ℓ1,ℓ2) Sparse Sampling of Data Elements",
(arXiv).
Summary:
This paper addresses how well we can recover a data matrix when only given a few of its elements. We present a randomized algorithm that elementwise sparsifies the data, retaining only a few its elements. Our new algorithm independently samples the data using sampling probabilities that depend on both the squares (ℓ2 sampling) and absolute values (ℓ1 sampling) of the entries. We prove that the hybrid algorithm recovers a nearPCA reconstruction of the data from a sublinear samplesize: hybrid(ℓ1,ℓ2) inherits the ℓ2ability to sample the important elements as well as the regularization properties of ℓ1 sampling, and gives strictly better performance than either ℓ1 or ℓ2 on their own. We also give a onepass version of our algorithm and show experiments to corroborate the theory.

(2016 WkgPap)
K. Wu, Malik MagdonIsmail
"NodeByNode Greedy Deep Learning for Interpretable Features",
(arXiv).
Summary:
Multilayer networks have seen a resurgence under the umbrella of deep learning. Current deep learning algorithms train the layers of the network sequentially, improving algorithmic performance as well as providing some regularization. We present a new training algorithm for deep networks which trains \emph{each node in the network} sequentially. Our algorithm is orders of magnitude faster, creates more interpretable internal representations at the node level, while not sacrificing on the ultimate outofsample performance.

(2016 Jrnl)
S. Das, A. Lavoie,
Malik MagdonIsmail,
"Manipulation among the arbiters of collective intelligence: How Wikipedia administrators mold public opinion",
ACM Transactions on the Web
(pdf preprint)
Summary:
We document that a surprisingly large number of editors change their behavior and
begin focusing more on a particular controversial topic once they are promoted to administrator status. The
conscious and unconscious biases of these few, but powerful, administrators may be shaping the information
on many of the most sensitive topics on Wikipedia; some may even be explicitly infiltrating the ranks of
administrators in order to promote their own points of view. In addition, we ask whether administrators
who change their behavior in this suspicious manner can be identified in advance. Neither prior history nor
vote counts during an administrator’s election are useful in doing so, but we find that an alternative mea
sure, which gives more weight to influential voters, can successfully reject these suspicious candidates. This
second result has important implications for how we harness collective intelligence: even if wisdom exists in
a collective opinion (like a vote), that signal can be lost unless we carefully distinguish the true expert voter
from the noisy or manipulative voter.

(2016 Jrnl) R. Korolov, J. Peabody, A. Lavoie,
S. Das,
Malik MagdonIsmail, W. Wallace,
"Predicting Charitable Donations Using Social Media",
Social Network Analysis and Mining, 6:31.
(pdf preprint)
Summary:
We study the relationship between chatter on
social media and observed actions concerning charita
ble donation. One hypothesis is that a fraction of those who
act will also tweet about it, implying a linear relation.
However, if the contagion is present, we expect a super
linear scaling. We consider two scenarios: donations in
response to a natural disaster, and regular donations. We
empirically validate the model using two locationpaired
sets of social media and donation data, corresponding to
the two scenarios. Results show a quadratic relation
between chatter and action in emergency response case. In
case of regular donations, we observe a nearlinear relation.
Additionally, regular donations can be explained by
demographic factors, while for a disaster response social
media is a much better predictor of action. A contagion
model is used to predict the nearquadratic scaling for the
disaster response case. This suggests that diffusion is pre
sent in emergency response case, while regular charity does
not spread via social network.

(2016 Jrnl)
S. Paul,
Malik MagdonIsmail, P. Drineas,
"Feature selection for linear SVM with provable guarantees",
Pattern Recognition, 60, pages 205214.
(pdf preprint)
Summary:
We give two
provably
accurate featureselection techniques for the linear SVM. The algorithms run in
deterministic and randomized time respectively. Our algorithms can be used in an unsupervised or
supervised setting. The supervised approach is based on sampling features from support vectors. We
prove that the margin in the feature space is preserved to within
εrelative error of the margin in the full
feature space in the worstcase. In the unsupervised setting, we also provide worstcase guarantees of
the radius of the minimum enclosing ball, thereby ensuring comparable generalization as in the full
feature space and resolving an open problem posed in Dasgupta et al. (2007).

(2016 Jrnl)
K. Clarkson, P. Drineas,
Malik MagdonIsmail, M. Mahoney, X. Meng, D. Woodruff
"The Fast Cauchy Transform and Faster Robust Regression",
SIAM J. on Computing.
(pdf preprint)
Summary:
We provide fast algorithms for robust (L_1) and general L_p regression using
a fast projection of the design matrix with a Hardmard scaled by Cauchy
random variables (hence the name Fast Cauchy Transform, FCT). Our projection
algorithm runs in O(ndlogn) and provides O(d^(2+)) L_1 distortion obliviously
for an arbitrary subspace of dimension d. We give applications of our
fast embedding algorithm to robust regression, L_p regression and L_1 subspace
approximation.

(2016 Conf) Malik MagdonIsmail, C. Boutsidis,
"Optimal Sparse Linear Encoders and Sparse PCA",
NIPS 2016, Barcelona, Spain, Dec 2016.
(pdf)
( ppt)

(2016 Conf) K. Hegde, Malik MagdonIsmail, B. Szymanski,
K. Kuzmin
"Clustering, Prominence and Social Network Analysis on Incomplete Networks",
Complex Networks 2016, Milan, Italy, NovDec 2016.
(pdf)
( ppt)

(2016 Conf) K. Wu, P. Waters, Malik MagdonIsmail,
"Network Classification Using Adjacency Matrix Embeddings and Deep Learning",
ASONAM 2016, San Francisco, Aug 2016.
(pdf)
( ppt)
2015:

(2015 WkgPap)
Malik MagdonIsmail, Christos Boutsidis
"Optimal Sparse Linear AutoEncoders and Sparse PCA",
(arXiv).
Summary:
Principal components analysis (PCA) is the optimal linear autoencoder of data, and it is often used to construct features. Enforcing sparsity on the principal components can promote better generalization, while improving the interpretability of the features. We study the problem of constructing optimal sparse linear autoencoders. Two natural questions in such a setting are: i) Given a level of sparsity, what is the best approximation to PCA that can be achieved? ii) Are there loworder polynomialtime algorithms which can asymptotically achieve this optimal tradeoff between the sparsity and the approximation quality?
In this work, we answer both questions by giving efficient loworder polynomialtime algorithms for constructing asymptotically \emph{optimal} linear autoencoders (in particular, sparse features with nearPCA reconstruction error) and demonstrate the performance of our algorithms on real data.

(2015 WkgPap)
Malik MagdonIsmail
"NPHardness and Inapproximability of Sparse PCA",
(arXiv).
Summary:
We give a reduction from {\sc clique} to establish that sparse PCA is NPhard. The reduction has a gap which we use to exclude an FPTAS for sparse PCA (unless P=NP). Under weaker complexity assumptions, we also exclude polynomial constantfactor approximation algorithms.

(2015 WkgPap) Mark Goldberg, Mykola Hayvanovych,
Malik MagdonIsmail, William Wallace
"Extracting Hidden Groups and their Structure from Streaming Interaction Data",
(arXiv).
Summary:
When actors in a social network interact, it usually means they have some general goal towards which they are collaborating. This could be a research collaboration in a company or a foursome planning a golf game. We call such groups \emph{planning groups}. Our particular focus is hidden planning groups who have not
"declared" their membership explicitly. We formulate the problem of hidden group discovery from streaming interaction data, and we propose efficient algorithms for identifying the hidden group structures by isolating the hidden group's nonrandom, planningrelated, communications from the random background communications. We validate our algorithms on real data (the Enron email corpus and Blog communication data).

(2015 Conf) S. Paul, Malik MagdonIsmail,
P. Drineas
"Column Selection via Adaptive Sampling ",
NIPS 2015, Montreal, Canada, Dec 2015.
(pdf)
( ppt)

(2015 Conf) A. Kundu, P. Drineas, Malik MagdonIsmail,
"Approximatinig Sparse PCA from Incomplete Data",
NIPS 2015, Montreal, Canada, Dec 2015.
(pdf)
( ppt)

(2015 Conf) R. Korolov, J. Peabody, A. Lavoie, S. Das, Malik MagdonIsmail,
W. Wallace
"Actions Are Louder than Words in Social Media",
Proceedings of 2015 International Conference on Advences in Social Networks
Analysis and Mining (ASONAM), Paris, France, August 2015.
(pdf)
( ppt)

(2015 Conf) S. Paul, Malik MagdonIsmail,
P. Drineas
"Feature Selection for Linear SVM with Provable Guarantees",
Proceedings of the 17th International Conference on
Artificial Intelligence and Statistics (AISTATS), San Diego, CA, May 2015.
(pdf)
(supplementary material)
( ppt)

(2015 Conf) E. Gertle, E. Mackin, , Malik MagdonIsmail,
L. Xia, Y. Yi,
"Computing Manipulations of Ranking Systems",
Proceedings of the International Conference on
Autonomous Agents and Multiagent Systems (AAMAS), Istanbul, Turkey, May 2015.
(pdf)
( ppt)
2014:

(2014 Talk)
Malik MagdonIsmail,
"Machines that Learn From Data",
Rensselaer  TALKS, December 6, 2014.
(pdf)

(2014 Talk)
Malik MagdonIsmail,
"Using Social Media to Predict Material Convergence",
RPI Workshop on Disaster Response Logistics, December 4, 2014.
(pdf)

(2014 Talk)
Malik MagdonIsmail,
"Learning, Sparsity and Big Data",
Bloomberg ML Group
(pdf)
Summary:
PCA, Clustering and Regression with sparse
features: compute them efficiently and not sacrifice in insample performance
too much. Mostly show and tell. A little SVM.

(2014 Jrnl)
S. Adali, X. Lu,
Malik MagdonIsmail
"Local, community and global centrality methods for analyzing networks",
Social Network Analysis and Mining (SNAM) (Vol. 4, No 1).
(pdf preprint)
Summary:
We introduce different notions of prominence in a network based on its
community structure: a local rank, which is the prominence of an actor
within its communities (the communities are computed using a
clustering algorithm) and its community rank, which is the rank of an
actor's community within the "graph of communities". We show in a variety
of real networks that these two measures of prominence capture different
effects. On these same real networks, we show that external measures
of prominence (like an authors citation prominence, or an actors ability to
feature in bigbudget movies) can be deconstructed into a contribution from
local rank and community rank. Local and community ranks also
play differing roles depending on the nature of the network and the
type of external prominence one wishes to capture.

(2014 Jrnl)
C. Boutsidis, P. Drineas,
Malik MagdonIsmail
"NearOptimal ColumnBased Matrix Reconstruction",
SIAM Journal on Computing (Vol. 43, Issue 2).
(pdf)
Summary:
We give o(SVD) algorithms that construct
O(k/e) columns to reconstruct a matrix to within
O(1+e) AAk_F, where Ak is the best rank k reconstruction from the SVD.
The number of columns is near optimal, asymptotically
matching a known lower bound.
We introduce two new tools in our algorithm  fast approximate matrix
factorizations, and dual set sparsification results which may be of
independent interest.

(2014 Jrnl)
C. Boutsidis,
Malik MagdonIsmail
"A Note on Sparse Leastsquares Regression",
Information Processing Letters, accepted.
(arXiv version)
Summary:
We give additive error bounds on sparse regression (where the
regression vector is required to have a small number of nonzeros)
in terms of the topk PCA regression.

(2014 Jrnl)
S. Paul, C. Boutsidis,
Malik MagdonIsmail, P. Drineas
"Random Projections for Linear Support Vector Machines",
ACM Transactions on Knowledge Discovery from Data, accepted.
(arXiv version)
Summary:
We show that using random projections for dimensionality reduction
in SVM preserves (to within relative error) both the margin and the
radius of the data. Since the margin and data radius are the two
quantities parametrizing the statistical generalization error, these statistical
bounds
are preserved during the feature selection.

(2014 WkgPap) Christos Boutsidis
Malik MagdonIsmail,
"Faster SVDtruncated Regularized Leastsquares",
(arXiv).
Summary:
We develop a new algorithm that computes the SVDtruncated solution to a
least squares problem (regression onto the topk principal components)
in time faster than SVD, while guaranteeing
an additive error. The algorithm first quickly
constructs an approximation to the
topk PCA and uses that approximation in the regression.
We give a lower bound showing that our quality of approximation is
the best one can expect of such algorithms which first approximate PCA.

(2014 Conf)
C. Boutsidis,
Malik MagdonIsmail
"Faster SVDtruncated Regularized Leastsquares",
IEEE International Symposium on
Information Theory (ISIT), July 2014, Honolulu, HI, USA.
(pdf)
Summary:
We give additive error bounds on sparse regression (where the
regression vector is required to have a small number of nonzeros)
in terms of the topk PCA regression.
2013:

(2013 Talk)
Malik MagdonIsmail,
"Efficiently Implementing Sparsity in Learning",
NIPS Workshop on Large Scale Matrix Analysis and Inference
(pdf)
Summary:
This talk describes ways to do PCA, Clustering and Regression with sparse
features: compute them efficiently and not sacrifice in insample performance
too much.

(2013 Talk)
Malik MagdonIsmail,
"Learning, Sparsity and Big Data",
RPI Dean's Seminar Series
(pdf)
Summary:
This talk describes ways to do PCA, Clustering and Regression with sparse
features: compute them efficiently and not sacrifice in insample performance
too much. Mostly show and tell.

(2013 Talk)
Malik MagdonIsmail,
"Sparsity in Machine Learning",
Talk at ICML Workshop on Numerical Linear Algebra in Machine Learning
(pdf)
Summary:
This talk describes ways to do PCA, Clustering and Regression with sparse
features: compute them efficiently and not sacrifice in insample performance
too much.

(2013 Jrnl)
C. Boutsidis,
Malik MagdonIsmail,
"NearOptimal Coresets for LeastSquares Regression",
IEEE Transactions on Infomation Theory, Vol 59, No. 10, 2013.
(pdf, coming soon)
Summary:
We give linear coresets for linear regression in both the spectral and
Frobenius norms. Our algorithms are deterministic.
We also provide lower bounds on coreset size for both deterministic and
randomized algorithms.

(2013 Jrnl)
C. Boutsidis,
Malik MagdonIsmail,
"Deterministic Feature Selection for kmeans Clustering",
IEEE Transactions on Infomation Theory, Vol 59, No. 9, 2013.
(pdf, coming soon)
Summary:
We give new deterministic algorithms for selecting
O(k) features to perform clustering. The resulting features
give a relative error approximation to the optimal objective
when considering the clustering error in the full space.

(2013 Jrnl)
Matthew Newby, Nathan Cole, Heidi Jo Newberg, Travis Desell,
Malik MagdonIsmail, Boleslaw Szymanski, Carlos Varela,
Benjamin Willett, and Brian Yanny,
"A Spatial Characterization of the Sagittarius Dwarf Galaxy Tidal Tails",
The Astronomical Journal Volume 145 Number 6, 2013.
(pdf,print version)
Summary: Using a maximum likelihood algorithm, we simultaneously
estimate the dynamical parameters of the Saggitarius Dwarf galaxy stream
as well as the parameters of the Milky Way galaxy. As a byproduct,
we present the first catalog of stars having the same density
profile as the Saggitarius stream. These results were achieved by
leveraginig the MilkyWay@home
volunteer computing platform.

(2013 Jrnl)
Sibel Adali,
Malik MagdonIsmail, Xiaohui Lu,
"iHypR: Prominence Ranking in Networks of Collaborations with
Hyperedges",
ACM Transactions on Knowledge Discovery from Data (TKDD), 2013. (accepted)
(pdf, coming soon)
Summary:
We give new algorithms for ranking in collaborative networks based on
[i]clustering[/i] the collaborative artifacts into hyperedges and using
an iterative pagerank type algorithm to obtain the rankings from these
hyperedges.

(2013 WkgPap) Elliot Anshelevich, Ameya Hate,
Malik MagdonIsmail,
"Seeding Influential Nodes in NonSubmodular Models of Information Diffusion",
(arXiv).
Summary:
We develop new algorithms to seed an information diffusions for
a nonsubmodlar model. The model is built to mimic social proceeses that
are likely to occur in information diffusion. Our approach is to
project the nonsubmodular model to a class of submodular models for which
an efficient solution can be constructed. We demonstrate
significantly better performance as compared to using random or high degree
seeding strategies on real and synthetic networks.

(2013 WkgPap) Kenneth L. Clarkson, Petros Drineas,
Malik MagdonIsmail, Michael W. Mahoney, Xiangrui Meng,
David P. Woodruff,
"The Fast Cauchy Transform and Faster Robust Linear Regression",
submitted, 2013.
(arXiv).
Summary:
We develop the Fast Cauchy Transform (FCT), the L1 equivalent of the
Fast Johnson Lindenstrauss Transform, which allows us to develop a fast
algorithm
for robust (L1) regression. This can be extended to Lp regression for
p in the range [1,2]. We also give experimental simulations which show that the
practice follows the theory closely.

(2013 Conf) Sanmay Das, Allen Lavoie, Malik MagdonIsmail,
"Manipulation Among the Arbiters of Collective Intelligence:
How Wikipedia Administrators Mold Public Opinion",
ACM Conference on Information and Knowledge Management (CIKM),
2013. Pages 10971106.
(pdf)
(slides)

(2013 Conf) Sibel Adali, Xiaohui Lu, Malik MagdonIsmail,
"Deconstructing centrality: thinking locally and
ranking globally in networks",
Proceedings 5th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Niagara Falls, Canada, August 2013.
(pdf)
(slides)

(2013 Conf) S. Paul, C. Boutsidis, Malik MagdonIsmail,
P. Drineas
"Random Projections for Support Vector Machines",
Proceedings of the 16th International Conference on
Artificial Intelligence and Statistics (AISTATS)
Scottsdale, AZ, April 2013.
(pdf, coming soon)
( ppt)

(2013 Conf) Elliot Anshelevich, Ameya Hate, Malik MagdonIsmail,
"Seeding Influential Nodes in NonSubmodular Models of Information Diffusion",
Proceedings of the 12th International Conference on
Autonomous Agents and Multiagent Systems (AAMAS),
St. Paul,
Minnesota, May 2013.
(pdf)
(arXiv)
( ppt)

(2013 Conf) Kenneth Clarkson, Petros Drineas, Malik MagdonIsmail,
Michael Mahoney, Xiangrui Meng, David Woodruff,
"The Fast Cauchy Transform and Faster Robust Linear Regression",
Proceedings of ACMSIAM Symposium on Discrete Algorithms (SODA),
New Orleans, Louisiana, January 2013.
(pdf)
( ppt)
2012:

(2012 Book)
Yaser AbuMostafa,
Malik MagdonIsmail, HsuanTien Lin
"Learning from Data: A Short Course",
amlbook.com, ISBN13: 9781600490064, March 2012.
This book is Part I of our text book on Machine Learning that
is on the foundations and basic principles
of learning from data. Roughly speaking, the book addresses the
following topics: What is learning? Is learning feasible?
Can we do it efficiently (linear models)?
Can we do it well (overfitting and regularization)?
Lesons learned  what are the
take home messages?

(2012 Jrnl)
Petros Drineas,
Malik MagdonIsmail, Michael Mahoney, David Woodruff,
"Fast Approximation of Matrix Coherence and Statistical Leverage",
Journal of Machine Learning Research (JMLR), Volume 13, pages 34413472, Dec 2012.
(pdf)
Summary:
We give the first algorithms to compute statistical leverage and coherence
in subSVD time using random projections. The algorithms are accurate
to within relative error. Datapoints with high statistical leverage are
important in that they are likely to belong to good coresets that can
reproduce a linear regression to within relative error.

(2012 Jrnl)
Sibel Adali, Tina Liu,
Malik MagdonIsmail,
"An Analysis of Optimal Link Bombs",
Theoretical Computer Science, volume 437, pages 120, 2012.
(preprint pdf)
(print version online).
Summary:
We consider the optimal attack pattern to spam the page rank algorithm.
It turns out to be particularly simple: all attackers point to the victim.
This optimally increases not only the pagerank of the victim but also
the rank (based on the pagerank) of the victim. We also consider
optimal 'disguised' attacks, i.e. attacks where the attackers do not want to
be directly associated to the victim. A similar result holds in that setting.

(2012 Jrnl)
Ali Civril,
Malik MagdonIsmail,
"Column subset selection via sparse approximation of SVD",
Theoretical Computer Science, Volume 421, pages 114, 2012.
(preprint pdf)
(print version).
Summary:
We give one of the first deterministic algorithms for provable
reconstruction of
a matrix using a small subset of its columns. The method is based on
a greedy approximation of the SVD. In order to greedily
approximate the SVD from a dictionary, we extend Natarajan's result
for greedy approximation of a vector from a dictionary.

(2012 WkgPap) Saurabh Paul, Christos Boutsidis,
Malik MagdonIsmail, Petros Drineas,
"Random Projections for Support Vector Machines",
submitted, 2012.
(arXiv).
Summary:
We give an oblivious
random projection algorithm which samples a number
features proportional to the rank of the data matrix such that the
margin and radius of the data in the dimensionally reduced
space are comparable to those in the original fulldimension space.
Thus the generalization properties of the SVM are preserved. We give
experimental simulations which bear out the theory.

(2012 WkgPap) Christos Boutsidis, Petros Drineas,
Malik MagdonIsmail,
"Rich Coresets For Constrained Linear Regression",
submitted, 2012.
(arXiv).
Summary:
We give the first polynomial algorithms which find a coreset of
size order the number of variables, such that the regression on
this coreset gives a relative error approximation to the
regression on the full data set.

(2012 WkgPap) P. Horn,
Malik MagdonIsmail,
"Spreading Processes and Large Components in Ordered, Directed
Random Graphs",
submitted, 2011.
(arXiv).
Summary:
We consider a spreading process that can be mapped onto a
random graph model:
order the vertices and randomply place directed edges from
lower ranked to higher ranked vertices; each such edge exists
independently
with probability \math{p}.
If the spread starts at the first vertex, the size of the infection
is the component reachable from
this vertex. We prove existence of a sharp threshold
\math{p^*=\log n/n} at which this reachable component transitions from
\math{o(n)} to \math{\Omega(n)}.

(2012 WkgPap)
Malik MagdonIsmail,
"A Note On Estimating the Spectral Norm of A Matrix Efficiently".
(arXiv).
Summary:
A random projection based power iteration for estimating spectral norms
to within
relative error.

(2012 Conf) Sibel Adali, Xiaohui Lu, Malik MagdonIsmail,
"Attentive Betweenness Centrality (ABC):
Considering Options and Bandwidth when
Measuring Criticality",
Proceedings IEEE Conference on Social Computing (SocialCom),
Amsterdam, The Netherlands, September 2012.
(pdf)
(slides)

(2012 Conf) Pranay Anchuri, Malik MagdonIsmail,
"Communities and Balance in Signed Networks: A Spectral Approach",
Proceedings of 4th International on
Advances in Social Networks Analysis and Mining
(ASONAM),
Istanbul, Turkey, August 2012.
(pdf)
( ppt)

(2012 Conf) Mark Goldberg, Malik MagdonIsmail,
James Thompson
"Identifying Long Lived Social Communities Using Structural Properties",
Proceedings of 4th International on
Advances in Social Networks Analysis and Mining
(ASONAM),
Istanbul, Turkey, August 2012.
(pdf)
( ppt)

(2012 Conf) Petros Drineas, Malik MagdonIsmail,
Michael W. Mahoney, David P. Woodruff
"Fast Approximation of Matrix Coherence and Statistical Leverage",
Proceedings of 25th International Conference on Machine Learning (ICML),
Edinburgh, Scotland, June 2012.
(pdf)
( ppt)

(2012 Wkshp) HsuanTien Lin, Malik MagdonIsmail,
Yaser S. AbuMostafa
"Teaching Machine Learning to a Diverse Audience:
the Foundationbased Approach",
Teaching Machine Learning Workshop at the
25th International Conference on Machine Learning (ICML),
Edinburgh, Scotland, June 2012.
(pdf)
( ppt)

(2012 Conf) Mark Goldberg, Malik MagdonIsmail,
William Wallace, John Schwartz and Bridget Gutting
"Graph Search Beyond Text: Relational Searches in Semantic Hyperlinked Data",
Proceedings of 10th International Conference on Intelligence and Security
Informatics (ISI), Washington DC, June 2012.
(pdf)
( ppt)

(2012 Conf) Malik MagdonIsmail, Brian Orecchio
"Guard Your Connections: Infiltration of a Trust/Reputation Based Network",
Proceedings of 4th International Conference on
Web Science (WebSci) in conjunction
with NetSci 2012,
Evanston IL, June 2012.
( pdf)
( ppt)

(2012 Wkshp) Sanmay Das, Allen Lavoie, Malik MagdonIsmail,
"Pushing Your Point of View: Behavioral Measures of
Manipulation in Wikipedia",
Workshop on Social Computing and User Generated Content at
ACM Conference on Electronic Commerce (ACMEC), Valencia, Spain, June 2012.
(pdf)
( ppt)

(2012 Conf) Aseem Brahma, Mithun Chakraborty,
Sanmay Das, Allen Lavoie, Malik MagdonIsmail,
"A Bayesian Market Maker",
Proceedings of 13th International Conference on Electronic Commerce (EC),
Valencia, Spain, June 2012.
( pdf)
( ppt)

(2012 Conf) Cindy Hui, William Wallace, Malik MagdonIsmail,
Mark Goldberg
"Information Cascades in Social Media in Response to a Crisis: a Preliminary Model and a Case Study",
Proceedings of Workshop on Social Web for Disaster Management (SWDM) at World Wide Web Conference (WWW), April 2012.
pdf.
Poster:
ppt.

(2012 Conf) Sibel Adali,
Fred Sisenda, Malik MagdonIsmail,
"Actions Speak as Loud as Words:
Predicting Relationships from Social Behavior Data",
Proceedings of World Wide Web Conference (WWW), April 2012.
pdf.
Poster:
ppt.
2011:

(2011 BkChap) S. Kelley, M. Goldberg,
Malik MagdonIsmail, K. Mertsalov, W. Wallace,
"Defining and Discovering Communities in Social Networks",
Book Chapter in
Handbook of Optimization in Complex Networks,
eds. M. Thai and P. Pardalos, Chapter 6, pages, 2011.
(pdf).
Summary:
Overlapping communities play a large role in the functioning of
social networks. We give a definition based on minimal
properties that such communities should have, and develop efficient
algorithms to find such comunities. We give some
methods for validating that the communities found are "real" and compare
this minimal axiomatic approach to several other benchmark algorithms
which take a specific view as to the structure of the communities.

(2011 BkChap) C. Busch,
Malik MagdonIsmail, J. Xi,
"Oblivious Routing for Sensor Network Topologies",
Book Chapter in
Theoretical Aspects of Distributed Computing in Sensor Networks,
eds. S. Nikoletseas and J. D. P. Rolim, Chapter 13, pages 381400,
Springer, 2011.
(pdf).
Summary:
We collect some of our previous results on
oblivious routing algorithms with
nearoptimal congestion and dilation (as compared with optimal
offline routing) for sensor network topologies which
include the ddimensional mesh and uniform geometric networks.

(2011 Jrnl)
Ali Civril,
Malik MagdonIsmail
"Exponential Inapproximability of Selecting a Maximum Volume Submatrix",
Algorithmica, pages 118
Journal Version:
pdf.
(arXiv).
Summary:
We show that selecting columns of a data matrix to have maximum "numerical
rank" (as measured by the volume of the data vectors selected) is
exponentially hard to approximate.

(2011 Jrnl) S. Das,
Malik MagdonIsmail,
"A Model for Information Growth in Collective Wisdom Processes",
ACM Transactions on Knowledge Discovery from Data (TKDD),
volume 6, issue 2, article 6, July 2011.
preprint (pdf).
(pdf).
Summary:
We give a succint model for edit dynamics in collective wisdom processes
in which users (the collective) arrive sequentially and contribute to the
wisdom on a particular topic.
The model captures the arrival of new information, together with
the saturation of information on a particular topic. As the quality of a
particular topic increases, there is a tradeoff between more uses arriving and
those users having less to contribute. We demonstrate
the model on Wiki and Blog edit behavior, in particular capturing the
main observed phenomenological dynamics within just this simple
model.

(2011 Jrnl) M. Goldberg,
Malik MagdonIsmail,
"Embedding a Forest in a Graph",
Electronic Journal of Combinatorics (EJC),
Volume 18(1), P99, Apr 29, 2011.
(pdf).
Summary:
For $p\backslash ge\; 1$, we prove that every forest with $p$ trees whose sizes are $a\_1,\; .\; .\; .\; ,\; a\_p$ can be
embedded in any graph containing at least $\backslash sum\_\{i=1\}^p\; (a\_i\; +\; 1)$ vertices and having minimum
degree at least $\backslash sum\_\{i=1\}^p\; a\_i$.

(2011 Jrnl)
Malik MagdonIsmail, Jonathan Purnell,
"Approximating the Covariance Matrix of GMMs with Lowrank Perturbations",
International Journal of Data Mining, Modelling and Management,
Special issue on the best papers of IDEAL'10
(invited), pp 300307.
preprint (pdf).
Summary:
We present a method for using Gaussian Mixture Models
(GMMs) efficiently using low rank perturbations to a diagonal
covariance matrix. The full covariance matrix has O(d^2) free parameters
and could be prone to overfitting as well as inefficient. The
diagonal covariance matrix has O(d) parameters and is efficient
but can be restrictive. The low rank perturbation to a diagonal
covariance matrix has O(d) parameters, is efficient and offers a
middle ground between full and diagonal covariance which can capture
correlations but using linear (in d) parameters.

(2011 WkgPap) C. Boutsidis
Malik MagdonIsmail,
"Deterministic Feature Selection for kmeans Clustering",
submitted, 2011.
(arXiv).
Summary:
We show that it is possible to reduce the feature
dimension and provably obtain clusterings which are comparable
to the good clusterings in the original dimension.

(2011 WkgPap) Sanmay Das, Allen Lavoie,
Malik MagdonIsmail,
"Pushing Your Point of View: Behavioral Measures of Manipulation in Wikipedia", 2011.
(arXiv).
Summary:
We develop edit behavioral indices that capture change in behavior and show
correlation between blocked (potentially manipulative) editors and
adverse changes in this index.

(2011 Conf) ,
M. Goldberg, J. Greenman, B. Gutting, Malik MagdonIsmail,
J. Schwartz, W. Wallace,
"Toward Efficient Search for a Fragment
Network in a Large Semantic Database",
Proc.6th Annual Network Science Workshop,
West Point, Oct 2324 2011.
pdf
Talk:
pdf.

(2011 Conf) T. Desel,
Malik MagdonIsmail, H. Newberg, L. Newberg, B. Szymanski, and C. Varela,
"A Robust Asynchronous Newton Method for Massive Scale Computing Systems",
In the 2011 IEEE International Conference on Computational Intelligence and Software Engineering
(CiSE 2011). Wuhan, China. December 911, 2011.
pdf
Talk:
pdf.

(2011 Conf) T. Desel,
Malik MagdonIsmail, L. Newberg, B. Szymanski,
"Finding Protein Binding Sites Using Volunteer Computing Grids",
Proc.
2nd International Congress on Computer Applications and Computational Science
(CACS 2011),
Bali, Indonesia, Nov 1517 2011.
pdf
Talk:
pdf.

(2011 Conf) C. Boutsidis, P. Drineas,
Malik MagdonIsmail,
"Sparse Features for PCAlike Regression",
Proc. 25th Conference on Neural Information Processing Systems
(NIPS 2011),
Granada, Spain, Dec 1315 2011.
pdf (coming soon)
Talk:
pdf.

(2011 Conf) C. Boutsidis, P. Drineas,
Malik MagdonIsmail,
"NearOptimal Column Based Matrix Reconstruction",
Proc. 52nd IEEE Symposium on Foundations of Computer Science (FOCS 2011),
Palm Springs, CA, Oct 2325 2011.
pdf
(full version: arXiv).
Talk:
pdf.

(2011 Conf) M. Goldberg,
Malik MagdonIsmail, S. Nambirajan, J. Thompson
"Tracking and Predicting Evolution of Social Communities",
Proc. 3rd IEEE International Conference on Social Computing (SocialCom2011),
MIT, Boston, MA, Oct 911 2011.
pdf.
Talk:
pdf.

(2011 Conf)
Malik MagdonIsmail, J. Purnell
"SSDECLuster: Fast Overlapping Clustering of Networks Using Sampled
Spectral Distance Embedding and GMMs",
Proc. 3rd IEEE International Conference on Social Computing (SocialCom2011),
MIT, Boston, MA, Oct 911 2011.
pdf.
Talk:
pdf.

(2011 Conf)
C. Hui, Malik MagdonIsmail, W. Wallace, M. Goldberg
"Aborting a Message Flowing Through Social Communities",
Proc. 3rd IEEE International Conference on Social Computing (SocialCom2011),
MIT, Boston, MA, Oct 911 2011.
pdf.
Talk:
pdf.

(2011 Conf) Mithun Chakraborty, Sanmay Das, Allen Lavoie,
Malik MagdonIsmail, Yonatan Naamad,
"Instructor Rating Markets",
(abstract only appeared) at Workshop on Social Computing and User Generated Content
at the ACM Conference on Electronic Commerce, June 2011
and Proc.
2nd Conference on Auctions, Market Mechanisms, and
Their Applications (AMMA), August 2011.
pdf.
Poster:
pdf.

(2011 Conf) Mithun Chakraborty, Sanmay Das,
Malik MagdonIsmail,
"NearOptimal Target Learning With Stochastic Binary Signals",
Proc. 27th Conference on
Uncertainty in Artificial Intelligence (UAI), Barcelona, Spain, July 1417,
2011.
pdf.
Poster:
pdf.

(2011 Conf) Cindy Hui,
Malik MagdonIsmail, Mark Goldberg, William Wallace,
"Effectiveness of Information Retraction",
1st IEEE International Workshop on Network Science (NSW 2011), West Point,
NY, June 2224, 2010.
pdf.
Poster:
pdf.

(2011 Conf) Sibel Adali, Xiaohui Lu,
Malik MagdonIsmail, Jonathan Purnell,
"Prominence Ranking in Graphs with Community Structure",
Proceedings of the Fifth International AAAI Conference on Weblogs and
Social Media (ICWSM), July 2011.
pdf.
Poster:
ppt.
2010:

(2010 BkChap) Nathan Cole, Travis Desell, Daniel Lombranaa Gonzalez,
Francisco Fernandez de Vega, Malik MagdonIsmail, Heidi Newberg,
Boleslaw Szymanski and Carlos A. Varela,
"Evolutionary Algorithms on Volunteer Computing Platforms:
The MilkyWay@Home Project",
Bookchapter In F. Fernandez de Vega, E. CantuPaz (Eds.):
Parallel and Distributed Computational Intelligence, SCI 269, pp. 6390.
SpringerVerlag Berlin Heidelberg 2010.
preprint (pdf).
Available at springer.com.

(2010 Jrnl)
Malik MagdonIsmail, Konstantin Mertsalov,
"A Permutation Approach to Validation",
Statistical Analysis and Data Mining
Special issue on the best papers of SDM'10
(invited), Vol. 3, No. 6, pp 361380.
preprint (pdf).
Summary:
We present a method for "estimating" the outsample error (validation)
using a permutation estimate. For classification, one can bound the
outsample error using a permutation complexity which is related
to the permutation estimate. The permutation estimate, however,
applies to classification, regression, multiclass, ... and can be extended
to different error measures (other than squared error)  the paper primarily
focusses on classification and L2regression. Our experiments show that
the permutation estimate performs well for model selection,
outperforming a variety of
other model methods including LOOCV and 10fold CV.
The permutation estimate general,
easy to compute and efficient, relying only on being able to run the
learning algorithm on data.
Erratum: Rudiger Hewer, in his bachelor thesis
graciously pointed out to me that the bound in Lemma 8 should be corrected
by a factor of 2 which propagates to the error term in Theorem 5, which
should be
5*sqrt(8/n...) instead of 3*sqrt(8/n...).

(2010 Jrnl) Cindy Hui, Mark Goldberg,
Malik MagdonIsmail, William Wallace,
"Simulating the Diffusion of Information: An Agentbased
Modeling Approach",
Special Issue on AgentDirected Simulation,
International Journal of Agent Technologies and Systems
(invited paper, in press)
pdf.
Summary:
We develop an agent based model for information diffusion in
social networks based on information fusion, propagation and
querying. We validate the model on real data from the
San Diego wild fires evacuation in 2007.

(2010 WkgPap) Aseem Brahma, Sanmay Das
Malik MagdonIsmail,
"Comparing Prediction Market Structures, With an Application to
Market Making", 2010.
(arXiv).
Summary:
We develop a novel 2d ball mechanism for comparing prediction market
microstructures, and use it to compare two market makers LMSR and BMM.

(2010 Conf) Costas Busch,
Malik MagdonIsmail,
"Optimal Oblivious Routing in HoleFree Networks",
Proceedings of the 7th International Conference on
Heterogeneous Networking for Quality, Reliability, Security,
and Robustness (QShine), Houston, Texas, November 2010. (invited)
pdf.
Slides:
ppt.

(2010 Conf) Cindy Hui,
Malik MagdonIsmail, Mark Goldberg, William Wallace,
"Importance of Ties in Information Diffusion",
Extended Abstract,
Workshop on Information In Networks (WIN), NY, NY, Sept 2425, 2010.
pdf.
Poster:
pdf.

(2010 Conf) Cindy Hui,
Malik MagdonIsmail, Mark Goldberg, William Wallace,
"Weak Ties and the Diffusion of Information in Dynamic Networks",
NetSci 2010, poster presentation, Boston, MA.
pdf.
Poster:
pdf.

(2010 Conf)
Malik MagdonIsmail,
"Permutation Complexity Bound on OutSample Error",
Proc. 24th Annual Conference on Neural Information Processing Systems (NIPS),
pages, Dec. 69, 2010.
pdf.
Poster:
pdf.

(2010 Conf) Travis Desell, Anthony Waters,
Malik MagdonIsmail,
Boleslaw Szymanski, Carlos A. Varela, Matthew Newby, Heidi Newberg,
Andreas
Przystawik,
David Anderson,
"Accelerating the MilkyWay@Home Volunteer Computing Project with GPUs",
8th International Conference on
Parallel Processing and Applied Mathematics, Part I (PPAM), pages 276288
pdf.
Slides:
pdf.

(2010 Conf) Goldberg, M. K., Kelley, S.,
MagdonIsmail, M., Wallace, W.,
"Overlapping Communities in Social Networks",
Proc. 2nd Confernence on Social Computation (SocialCom),
pages 104113, Aug 2022, Minneapolis, Minnesota, 2010;
also appeared in
Proc. Workshop on Social Network Analysis (SNAKDD) at KDD,
pages 4352, July 2528, Washington, DC, 2010
pdf.
Slides:
pdf.

(2010 Conf) Jonathan Purnell, Malik MagdonIsmail,
"Approximating the Covariance Matrix with Low Rank Perturbations",
Proc. 11th Int. Conf. on Intelligent Data Engineering and Automated
Learning (IDEAL), 13 Sept., Paisley, Scotland, 2010.
pdf.
Slides:
pdf.

(2010 Conf) Goldberg, M. K., Hayvanovych, M.,
MagdonIsmail, M.,
"Measuring Similarity between Sets of Overlapping Clusters",
Proc. Workshop on Social Network Analysis (SNAKDD) at KDD, pages 6268,
July 2528, Washington, DC, 2010 ;
also appeared in
Proc. Workshop on Social Intelligence (SIN) at SocialCom,
pages 303308, Aug 2022, Minneapolis, Minnesota, 2010
pdf.
Slides:
pdf.

(2010 Conf) Travis Desell, David P. Anderson,
Malik MagdonIsmail, Heidi Newberg, Boleslaw Szymanski, Carlos A. Varela,
"An Analysis of Massively Distributed Evolutionary Algorithms",
Proc. 2010 IEEE Congress on Evolutionary Computation (CEC),
pages (to appear), Barcelona, Spain, July 1823 2010.
pdf.
Slides:
ppt.

(2010 Conf) Travis Desell, Malik MagdonIsmail, Bolek Szymanski,
Carlos Varela, Heidi Newberg, David P. Anderson,
"Validating Evolutionary Algorithms on Volunteer Computing Grids",
Proc.
10th IFIP International Conference on Distributed Applications
and Interoperable Systems (DAIS 2010),
pages 2941, Amsterdam, Netherlands, June 710 2010.
pdf.
Slides:
ppt.

(2010 Conf) Adali, S., Escriva, R., Goldberg, M. K., Hayvanovych, M.,
MagdonIsmail, M., Szymanski, B. K., Wallace, W. A., Williams, G.M,
"Measuring Behavioral Trust in Social Networks",
Proc. International Conference on Intelligence and Security Informatics (ISI),
pages 150152,
Vancouver, BC, May 2326, 2010.
pdf.
Technical Report:
pdf.
Slides:
pdf.

(2010 Conf) Sanmay Das,
Malik MagdonIsmail,
"Collective Wisdom: Information Growth in Wikis and Blogs",
ACM Conference on ECommerce (EC 2010),
pages 231240, June 78 , Cambridge Massachusetts, 2010.
pdf.
Slides:
pdf.

(2010 Conf) Cindy Hui, Mark Goldberg,
Malik MagdonIsmail, William Wallace,
"Agent Based Simulation of Diffusion Warnings",
Proc. AgentDirected Simulation Symposium (ADS),
Orlando FL, April 12May 14, 2010.
pdf.
Slides:
pdf.
[Best Paper]

(2010 Conf) Malik MagdonIsmail, Konstantin Mertsalov,
"A Permutation Approach to Validation",
Proc. 10th SIAM International Conference on Data Mining (SDM),
pages 882983, Columbus Ohio, April 29May 1, 2010.
pdf.
Slides:
pdf.
[Best paper, top 3]
2009:

(2009 Jrnl)
Ali Civril,
Malik MagdonIsmail
"On Selecting a Maximum Volume SubMatrix of a Matrix and Related
Problems",
Theoretical Computer Science,
Journal Version:
postscript,
pdf.
Summary:
We study the problem of selecting a set of columns of a matrix with maximum
volume. This is useful in trying to construct representative columns of
high "numerical rank", which may be of use in matrix reconstruction.
We study the algorithmic problem, showing that it is NPhard and
inapproximable.
We then study a natural greedy algorithm for this problem, giving a worst
case approximation guarantee, also demonstrating a problem which almost
achieves this worst case. The performance of greedy is considerably
worse than the inapproximability result we prove, suggesting avenues for
further work in strengthening the inapproximability result or
finding better algorithms.

(2009 Jrnl)
Costas Busch,
Malik MagdonIsmail
"Atomic Routing Games on Maximum Congestion",
Theoretical Computer Science, Volume 410, Issue 36, Pages 33373347, 2009.
Journal Version:
postscript,
pdf.
(link to journal web version)
Conference Version: AAIM 2006,
ps,
pdf.
Summary:
We study atomic routing games on networks in which players choose
a path with the objective of minimizing the maximum congestion along
the edges of their path. The social cost is the global maximum
congestion over all edges in the network. We show that the price of
stability is 1. The price of anarchy, PoA, is determined by topological
properties of the network. In particular, PoA=O(L+logn),
where L is the length of the longest path in the player strategy
sets, and n is the size of the network. Further,
K1<=PoA<=c(K^2+log^2 n), where
K is the length of the longest cycle in the network,
and c is a constant.

(2009 Conf) Travis Desell, Malik MagdonIsmail, Bolek Szymanski,
Carlos Varela, Heidi Newberg, Nathan Cole
"Robust Asynchronous Optimization for Volunteer
Computing Grids",
Proc. 5th International Conference eScience,
pages 263270, Oxford UK, Dec 79, 2009.
pdf.
Slides:
ppt.

(2009 Conf) Jonathan Purnell, Malik MagdonIsmail
"Learning American English Accents Using Ensemble Learning with GMMs",
Proc. 8th International Conference on Machine Learning and
Applications (ICMLA),
pages 4752, 2009.
pdf.
Slides:
pdf.

(2009 Conf) Christopher Wynnyk, Malik MagdonIsmail
"Pricing the American Option using Reconfigurable Hardware",
Proc. 7th IEEE/IFIP Conference on Embedded and Ubiquituous Computing (EUC2009)
pages 532536, 2009.
pdf.
Slides:
pdf.

(2009 Conf) Mark Goldberg,
Malik MagdonIsmail, Konstantin Mertsalov,
"Models of Communication Dynamics for Simulation of Information Diffusion",
Proceedings of Advances in Social Networks Analysis and Mining (ASONAM 2009),
pages 4449, 2009.
pdf.
Slides:
ppt.

(2009 Conf)
Stephen Kelley, Mark Goldberg, Malik MagdonIsmail, Konstantin Mertsalov,William Wallace, Mohammed Zaki
"graphOnt: An Ontology Based Library for Conversion from Semantic Graphs to JUNG",
Proceedings 2009 IEEE International Conference on Intelligence and Security Informatics, pages 170172, 2009.
pdf.
Slides:
pdf.

(2009 Conf)
Stephen Kelley, Mark Goldberg, Malik MagdonIsmail, Konstantin Mertsalov
"Stability of Individual and Group Behavior in a Blog Network",
Proceedings 2009 IEEE International Conference on Intelligence and Security Informatics, pages 712, 2009.
pdf.
Slides:
pdf.

(2009 Conf) C. Hui,
Malik MagdonIsmail, Mark Goldberg, William A. Wallace
"The Impact of Changes in Network Structure on
Diffusion of Warnings",
Proc. Workshop on Analysis of
Dynamic Networks (SIAM International Conference on Data Mining),
pages, 2009.
pdf.
Slides:
pdf.
2008:

(2008 Jrnl)
HungChing (Justin) Chen, Mark Goldberg,
Malik MagdonIsmail, William Wallace
"Reverse Engineering an AgentBased Hidden Markov Model for
Complex Social Systems",
International Journal of Neural Systems,
pdf.
Summary:
We give heuristics for learning the parameters of a HMM describing
dynamics of social groups in social networks. The input data are
communications for the social network. The HMM is an agent based microlaw
model which is highly interdependent. We apply our methodology
to real data from blogs, newsgroups.

(2008 Jrnl)
Jeffery Baumes, HungChing (Justin) Chen, Matthew Francisco, Mark Goldberg,
Malik MagdonIsmail, William Wallace
"ViSAGE:
A Virtual Laboratory for Simulation and Analysis of Social Group Evolution",
ACM Transactions on Autonomous and Adaptive Systems (TAAS),
postscript,
pdf.
Summary:
We give a parameterised
generative HMM model for social group evolution based on social
capital theory,
and demonstrate its potential for modeling of social groups in social
networks. In particular, one may
observe certain abrupt changes in the behavior of macroscopic properties
such as the group size distribution as one continuously changes some of
the parameters. Within this model we can reproduce many observed phenemona
within the social science literature.

(2008 Jrnl)
Nathan Cole, Heidi Joe Newberg,
Malik MagdonIsmail, Travis Desell, Kristopher Dawsey, Warren
Hayashi, Xinyang (Fred) Liu, Jonathan Purnell, Boleslaw Szymanski,
Carlos Varela, James Wisniewski,
"Maximum Likelihood Fitting of Tidal Streams with application to the
Sagittarius Dwarf Tidal Tails",
the Astrophysical Journal, Vol 683, pages 750766 (2008).
Journal Version:
postscript,
pdf.
Conference Versions:
eScience 2007 (pdf) .
ISMIS 2005 (pdf).
Summary:
We give a maximum likelihood algorithm to identify streams in from
SDSS like data. In particular, we use a cylindrical profile
for the stream over small length scales and a Hernquist profile for the
Milky Way halo. The algorithm finds the stream and separates it from the
background halo, thus producing more accurate parameters of the
stream and giving the first catalogue of stars extracted from the
data to have the stream density profile. In general, we are studying the
problem of separating geometric objects in spatial data bases.

(2008 Conf) Nathan Cole, Heidi Joe Newberg,
Malik MagdonIsmail, Travis Desell, Boleslaw Szymanski,
Carlos Varela,
"Tracing the Sagittarius Tidal Stream with Maximum Likelihood",
Proc. AIP Conference, Volume 1082, pages 216220, December 5th,
2008.
pdf.
Slides:
pdf.

(2008 Conf) Ali Civril,
Malik MagdonIsmail
"Deterministic Sparse Column Based
Matrix Reconstruction via Greedy Approximation of SVD",
Proc. 19th International Symposium on Algorithms and
Computation (ISAAC), pages, December
2008.
pdf.
Slides:
pdf.

(2008 Conf) Sanmay Das,
Malik MagdonIsmail
"Collective Wisdom: Information growth in Wikis and Blogs",
NIPS Workshop
"Beyond Search: Computational Intelligence for the Web", December
2008.
ps,
pdf.
Poster:
pdf.

(2008 Conf) Sanmay Das,
Malik MagdonIsmail
"Adapting to a Market Shock: Optimal Sequential MarketMaking",
Proc. Advances in Neural Information Processing Systems (NIPS), pages, December
2008.
pdf (paper).
pdf (supplementary material).
Poster:
pdf.

(2008 Conf) Mark Goldberg, Stephen Kelley,
Malik MagdonIsmail, Konstantin Mertsalov, William Wallace
"Communication Dynamics of Blog Networks",
Proc. SIGKDD Workshop on Social Network Mining and Analysis,
pages
August, 2008.
pdf.
Slides:
pdf.

(2008 Conf) Mark Goldberg, Stephen Kelley,
Malik MagdonIsmail, Konstantin Mertsalov,
"Stable Statistics of the Blogograph",
Proc.Interdisciplinary Studies in
Information Privacy and Security (ISIPS),
pages, 2008.
pdf.
Slides:
pdf.

(2008 Conf) C. Hui,
Malik MagdonIsmail, Mark Goldberg, William A. Wallace
"MicroSimulation of Diffusion on Warnings",
Proc. 5th Int. Conf. on Information Systems
for Crisis Response and Management
ISCRAM, pages 424430, 2008.
pdf.
Slides:
pdf.

(2008 Conf) M. Hayvanovych, A. Hoonlor, M. Goldberg,
S. Kelley,
Malik MagdonIsmail, K. Mertsalov, B. Szymanski, W. Wallace,
"Discovery, analysis and monitoring
of hidden social networks and their evolution",
Proc. IEEE Conference on Technologies for Homeland Security,
pages 16
May, Boston, 2008.
pdf.
Slides:
pdf.

(2008 Conf) Yingjie Zhou,
Malik MagdonIsmail, William A. Wallace, Mark Goldberg,
"A Generative Model for Statistical Determination of Information Content
from Conversation Threads",
Proc. International Conference on Intelligencs and Security Informatics
(ISI), pages 331342
June 1720, Taipei, Taiwan, 2008.
pdf.
Slides:
pdf.

(2008 Conf) Mark Goldberg, Stephen Kelley,
Malik MagdonIsmail, Konstantin Mertsalov,
"A Locality Model of the Evolution of Blog Networks",
Proc. International Conference on Intelligencs and Security Informatics
(ISI), pages 191193
June 1720, Taipei, Taiwan, 2008.
pdf.
Slides:
ppt.

(2008 Conf) Baumes, Jeffery, Goldberg, Mark K.,
Malik MagdonIsmail, Wallace, William
"Discovering Hidden Groups in Communication Networks",
Invited Book Chapter, in "Security Informatics and Terrorism: Patrolling the Web",NATO
Science for Peace and Security Series, Subseries D: Information and
Communication Security, eds.Cecilia S. Gal and Paul B. Kantor and Bracha Shapira, NATO, pages 82108.
ps (preprint)
, pdf (preprint).
2007:

(2007 Jrnl)
Costas Busch,
Malik MagdonIsmail,
Marios Mavronicolas,
"Efficient Bufferless Packet Switching on Trees and Leveled Networks",
Journal of Parallel and Distributed Computing, Volume 67 (2007), pages
11681186.
Journal Version:
postscript,
pdf.
Conference Versions: EUROPAR 2005 (Leveled), EUROPAR 2004 (Trees),
ps,
pdf.
(Leveled)
ps,
pdf.
(Trees)
Summary:
We give bufferless hotpotato style scheduling algorithms for
trees and leveled networks.
For leveled networks, we give centralized and distributed
algorithms. The centralized algorithm
has routing time within a logarithmic factor of optimal,
and the distributed algorithm is a logarithmic factor worse
than the centralized. For trees, we give deterministic and
randomized algorithms. The deterministic algorithm applies to bounded
degree networks and has routing time within a logaritmic factor
of optimal. The randomized algorithm applies to arbitrary networks,
and has routing time within a logsquared factor from optimal.

(2007 Jrnl)
Costas Busch,
Malik MagdonIsmail,
Jing Xi,
"Optimal Oblivious Path Selection on the Mesh",
IEEE Transactions on Computers, Vol. 57, No. 5, pages 660671
Journal Version:
postscript,
pdf.
Conference Version:
International Parallel and Distributed Processing Symposium (IPDPS), 2005,
postscript,
pdf.
Summary:
We give an oblivious algorithm for the ddimensional mesh in
which packets select their paths
independently of each other. The stretch and congestion are both
within O(d^2) from the
optimal stretch and congestion attainable by oblivious algorithms,
and for oblivious algorithms, the congestion
is within a logarithmic factor
from the optimal congestion attainable by nonoblivious algorithms.
Our algorithm is randomized, and we show that
significant randomization is required for any algorithm which attains
near optimal congestion. In particular, we show
that our algorithm uses at most a factor O(d) more bits per
packet than any algorithm which attains a comparable congestion.

(2007 Jrnl)
Costas Busch,
Malik MagdonIsmail
Fikret Sivrikaya, Bulent Yener
"Contentionfree MAC protocols for asynchronous wireless sensor networks",
Distributed Computing, Vol. 21, No. 1, pages 2342, 2008
Journal Version:
ps,
pdf.
Conference Version:
18th Annual Conference on Distributed Computing (DISC),
2004,
postscript,
pdf.
Summary:
We study TDMAbased MAC protocols for
asynchronous wireless sensor networks in very harsh environments.
Specifically, the protocols are contentionfree
(avoid collisions),
distributed
and selfstabilize to
topological changes in the network;
any
topological changes
are contained, namely,
affect only the nodes in the vicinity of the change;
our protocols do not assume that nodes have a global time reference,
that is, nodes may not be timesynchronized, and nodes may wake up
in an arbitrary order.
We also discuss how to accomodate clock skew, slot misalignment and inability
for collision detection at a node.

(2007 Jrnl)
Volkan Isler,
Malik MagdonIsmail
"Sensor Selection in Arbitrary Dimension",
IEEE Transactions on Automation Science and Engineering (TASE),
Vol. 5, No. 4, pages 651660, 2008
ps,
pdf.
Summary:
We address the problem of localizing an object in many dimensions
by selecting a small number of sensors from which to obtain a measurement.
We abstract a sensor measurement as a convex set in R^n and a localization
as the intersection of all measurments available to the object.
We show that a constant number of sensors is all that is required
to obtain a constant factor approximation to the localization error
obtained from using all the sensors. Instrumental in our
proof is a new construction of an enclosing simplex
of a convex polygon with bounded volume.

(2007 Jrnl)
Costas Busch,
Malik MagdonIsmail,
Marios Mavronicolas,
"Universal Bufferless Packet Switching",
Siam Journal on Computing, Volume 37, Issue 4, pages 11391162, 2007.
Journal Version:
ps,
pdf.
Conference Version:
Workshop in Approximate and Online Algorithms (WAOA),
2004,
postscript,
pdf.
Summary:
We give universal packet switching algorithms for bufferless networks,
settling an open question regarding the possibility of
optimal (to within polylog factors) bufferless packet switching algorithms.
Our argument is constructive and the algorithm is polynomial time.
The main idea is to convert a bufferless scheduling problem with
prespecified paths in a graph G to a
new routing problem in a related graph G'.
The problem in G' is solved using buffers, and the
solution in G'
is emulated in a deterministic bufferless manner in G
to give the final bufferless schedule. Buffering in G' is emulated by
packet circulation in regions of G.

(2007 Jrnl) Malik MagdonIsmail,
and Joseph Sill
"A Linear Fit Gets the Correct Monotonicity Directions",
Machine Learning,
Volume 70, Number 1 / January, 2008, pages 2143.
Journal Version:
postscript
, pdf.
Conference Version: Conference on Learning Theory (COLT), 2003,
postscript,
pdf.
Summary:
It is often the case that learning with a monotonicity constraint is
appropriate, however the directions of the monotonicity constraints
may not be available in a general ddimensional setting. One approach is
to use a simple learning model to learn the monotonicity constraints, which can
then be applied to constrain a more complex learning model. We show that
the optimal linear fit can extract the correct monotonicity directions in one
dimension, which remains true in multidimensions provided that the
input distribution is of a Mahalanobis type. The same results remain true
asymptotically when the the OLS estimator is used instead of the
optimal linear fit.

(2007 Jrnl)
Sibel Adali,
Brandeis Hill,
Malik MagdonIsmail,
"Information vs. Robustness in Rank Aggregation:
Models, Algorithms and a Statistical Framework for
Evaluation",
(accepted to appear in)
Journal of Digital Information Management (JDIM), special issue on
Web Information Retrieval
pdf.
Summary:
We develop a statistical framework for studying ranker aggregation
and a new algorithm for ranker aggregation based on a KerniganLin
style iterative best flip approach. We give experimental results
for varying amounts of noise in the rankers as well as dissimilarity in the
rankers (misinformation). In this space the optimal ranker can
vary significantly, illustrating an information vs. robustness tradeoff for
ranker aggregation.

(2007 Conf) HungChing (Justin) Chen,
Mark Goldberg,
Malik MagdonIsmail and Al Wallace,
"Reverse Engineering an AgentBased
Hidden Markov Model for Complex Social Systems",
Proc. International Conference on Intelligent
Data Engineering and Automated Learning (IDEAL), pages 940949,
December 1619, Birmingham, UK, 2007.
postscript,
pdf.
Slides:
postscript,
pdf.

(2007 Conf) HungChing (Justin) Chen,
Mark Goldberg,
Malik MagdonIsmail and Al Wallace,
"Discover The Power of Social and Hidden Curriculum
to Decision Making: Experiments with Enron Email and Movie Newsgroups",
Proc. International Conference on Machine
Learning and Applications (ICMLA), pages 154159,
December 1315, 2007, Cincinnati, Ohio, 2007.
postscript,
pdf.
Slides:
postscript,
pdf.

(2007 Conf)
Travis Desell, Nathan Cole, Malik MagdonIsmail, Heidi Newberg,
Bolek Szymanski, Carlos Varela
"Distributed and Generic Maximum Likelihood Evaluation",
[Best paper Award, 2nd place]
Proc. 3rd International Conference on eScience and Grid
Computing, pp ,
Bangalore, India, Dec 1013, 2007.
pdf.
Slides:
pdf.

(2007 Conf) HungChing (Justin) Chen,
Mark Goldberg,
Malik MagdonIsmail and Al Wallace,
"Learning What Makes a Society Tick",
Proc. Worksop on
Optimizationbased Data Mining Techniques with Applications
at the Seventh IEEE International Conference on Data Mining (ICDM),
pages 195200,
October 2831, Omaha, Nebraska, 2007.
pdf.
Slides:
postscript,
pdf.

(2007 Conf)
Fikret Sivrikaya,
Costas Busch,
Malik MagdonIsmail,
Bulent Yener
"ASAND: Asynchronous Slot Assignment and Neighbor Discovery
Protocol for Wireless Networks",
OPNETWORK 2007,
August 2731,Washington DC.
postscript,
pdf.
Slides:
powerpoint,

(2007 Conf) HungChing (Justin) Chen,
Mark Goldberg,
Malik MagdonIsmail and Al Wallace,
"Inferring Agent Dynamics from Social Communication Network",
Proc. Joint 9th Web Mining (WebKDD) and
1st Social Network Analysis (SNAKDD) Workshop and KDD 2007,
August 1215, San Jose, CA, 2007.
postscript,
pdf.
Slides:
ppt,

(2007 Conf) HungChing (Justin) Chen,
Mark Goldberg,
Malik MagdonIsmail and Al Wallace,
"Extracting Agent Based Models from a Social Communication Network",
Conference of Agentbased Modelers and Agentbased Modeling
Platform Users (SwarmFest 2007), July 1214, Chicago, IL USA, 2007.
abstract(pdf),
Slides:
ppt,

(2007 Conf) Yingjie Zhou,
Mark Goldberg, Malik MagdonIsmail and Al Wallace,
"Strategies for Cleaning Organizational Emails with an Application to Enron
Email Dataset",
5th Conf. of North American Association for Computational Social
and Organizational Science (NAACSOS 07), Emory  Atlanta, Georgia , USA.
June 79, 2007.
postscript,
pdf.
Slides:
ppt,

(2007 Conf) Jeffery Baumes,
Mark Goldberg, Mykola Hayvanovych, Stephen Kelley,
Malik MagdonIsmail Konstantin Mertsalov and Al Wallace,
"SIGHTS: A Software System for Finding Coalitions and Leaders in a
Social Network",
Proc. 5th Conference on Intelligence and Security Informatics
(ISI), May 2324, Rutgers, NJ, 2007.
postscript,
pdf.
Slides:
postscript,
pdf.

(2008 Conf) Baumes, Jeffery, Goldberg, Mark K.,
Malik MagdonIsmail, Wallace, William
"Identification of Hidden Groups in Communications",
Invited Book Chapter, in "Handbooks in Information
Systems 2 (National Security)", Elsevier,
eds. , pages 209242.
ps (preprint)
, pdf (preprint).
Technical Report
2006:

(2006 Jrnl)
Victor Boyarshinov,
Malik MagdonIsmail,
"Efficient Optimal Linear Boosting of a Pair of Classifiers",
IEEE Transactions on Neural Networks, Vol. 18, No. 2, pages 317328, 2007.
postscript,
pdf.
Summary:
We relate the problem of boosting a pair of classifiers to an
optimal weighted linear separation problem in
two dimensions. We give efficient algorithms to perform this
separation and compute the leave one out error.
The main idea is to carefully enumerate the possible separators
to finally obtain an O(n^2logn) algorithm, where
n is the number of data points.

(2006 Jrnl)
Costas Busch,
Malik MagdonIsmail, Marios Mavronicolas, Paul Spirakis
"Direct Routing: Algorithms and Complexity",
Algorithmica, Volume 45, Number 1, Pages 4568, June 2006.
(Invited submission from ESA 2004).
Journal Version:
postscript
, pdf.
Conference Version: European Symposium on Algorithms (ESA), 2004,
postscript
, pdf.
Summary:
We consider the direct routing problem, in which packets must follow
prespecified paths in a bufferless network.
In this routing model, the only parameter to be determined for a
packet is the injection time. We give a general
greedy algorithm which has routing time O(C D), and we show
that there are routing problems where this is the best
achievable by a direct algorithm. We show that optimal direct
routing is NPhard to approximate by gap preserving
reduction from graph coloring. We give versions of the greedy
algorithm which have optimal or near optimal routing time
for trees, multidimensional meshes, hypercubes and the butterfly.
Finally, we use hard direct routing problems to obtain lower
bounds on the buffering requirements of any algorithm that requires
packets to follow prespecified paths. If such algorithms
obtain near optimal routing time, then packets must be
buffered Omega(N^{1/3}) times (on average),
where N is the number of packets.

(2006 Conf) HungChing (Justin) Chen, Malik MagdonIsmail,
"Learning Martingale Measures From High Frequency Finiancial Data
to Help Option Pricing",
5th International Conference on Computational
Intelligence in Economics and Finance (CIEF 2006)
in conjunction with
9th Joint Conference on Information Sciences
(JCIS 2006)
October 8  11, Kaohsiung, Taiwan.
postscript,
pdf.
Slides:
postscript,
pdf.

(2006 Conf) HungChing (Justin) Chen, Malik MagdonIsmail,
"NNOPT: Neural Networks for Option Pricing Using Multinomial Trees",
The 13th International Conference on Neural Information Processing
(ICONIP2006),
October 36, Hong Kong.
postscript,
pdf.
Slides:
postscript,
pdf.

(2006 Conf) Matthew Francisco, Jeffery Baumes, HungChing Chen,
Mark Goldberg, Malik MagdonIsmail and Al Wallace,
"Using AgentBased Modeling to Traverse Frameworks in Theories of the Social",
International Conference on Complex Systems (ICCS06),
Boston, MA, June 2530, 2006.
postscript,
pdf.
Slides:
postscript,
pdf.

(2006 Conf) Jeffery Baumes, HungChing Chen, Matthew Francisco,
Mark Goldberg, Malik MagdonIsmail and Al Wallace,
"Modeling the Cultural Subjectivity: Towards Computational Critique",
4th Conf. of North American Association for Computational Social and Organizational Science (NAACSOS 06), NotreDame, Indiana, June 2223, 2006.
postscript,
pdf.
Slides:
postscript,
pdf.

(2006 Conf)
Petros Drineas, Asif Javed, Malik MagdonIsmail, Gopal Pandurangan,
Reino Virrankoski,
Andreas Savvides
"Distance Matrix Reconstruction from Incomplete Distance Information
for Sensor Network Localization",
Third Annual IEEE Communications Society Conference on Sensor,
Mesh and Ad Hoc Communications and Networks (IEEE SECON06),
Sep. 2528, Reston, VA, USA.
postscript,
pdf.

(2006 Conf)
Ali Civril, Malik MagdonIsmail and Eli BocekRivele,
"SSDE: Fast Graph Drawing Using Sampled Spectral Distance Embedding",
14th International Symposium on Graph Drawing
(GD2006),
Karlsruhe, Germany, Sept 1820, 2006.
postscript,
pdf.
Slides:
powerpoint.

(2006 Conf)
Jeffery Baumes, HungChing Chen,
Matthew Francisco,
Mark Goldberg,
Malik MagdonIsmail,
and
Al Wallace
"Social Capital Experiments",
4th Conf. of North American Association for Computational
Social and Organizational Science (NAACSOS 06),
NotreDame, Indiana, June 2223, 2006.
postscript,
pdf.
Slides:
ps,
pdf,
powerpoint,

(2006 Conf)
Jeffery Baumes,
Mark Goldberg, Mykola Hayvonovych,
Malik MagdonIsmail,
William Wallace, Mohammed Zaki,
"Finding Hidden Group Structure in a Stream of Communications",
[Top 3 Paper Award]
Proceedings of the 4th
Symposium on Intelligence and Security Informatics (ISI 06),
San Diego, CA, May 2324 2006.
postscript,
pdf.
Slides:
ps,
pdf,

(2006 Conf)
Costas Busch, Malik MagdonIsmail,
"Atomic Routing Games on Maximum Congestion",
Proceedings of the
2nd International Conference on Algorithmic
Aspects in Information and Management (AAIM), Hong Kong, June 2223, 2006.
postscript,
pdf.
Slides:
postscript,
pdf.

(2006 Conf)
Sibel Adali, Brandeis Hill and
Malik MagdonIsmail,
"The Impact of Ranker Quality on Ranker Aggregation Algorithms: Information
vs. Robustness",
Proc. ICDE Workshop on Challenges in Web Information
Retrieval and Integration (WIRI), pp 1019,
Atlanta, Georgia, April 3, 2006.
postscript,
pdf.
Slides:
postscript,
pdf.
2005:

(2005 Jrnl)
Malik MagdonIsmail, Fikret Sivrikaya, Bulent Yener
"Joint Problem of Power Optimal Connectivity and Coverage in Wireless
Sensor Networks",
Wireless Networks, Vol. 13, No. 4, pages 537550, 2006.
postscript
, pdf.
Summary:
We model a node using a Markovian automaton which transitions between
various modes which offer different capabilities and use power at
different states. We develop a
mean field theoretic analysis for the behavior of the system,
which we optimize with respect to
power consumption using connectivity and coverage as constraints.
We apply the methodology to a
3 state automaton with off, listen and transmit states.
We give results comparing the mean field theory
analysis with a simulation, and we compare our approach
with existing power saving approaches, which do not
necessarily offer connectivity and coverage.

(2005 Jrnl)
Victor Boyarshinov,
Malik MagdonIsmail
"Linear Time Isotonic and Unimodal Regression in the L1 and Linfinity
Norms",
Journal of Discrete Algorithms, Vol. 4, No. 4, pages 676691, 2006.
postscript
, pdf.
Summary:
We give linear time algorithms for (unweighted)
isotonic and unimodal regression in the Linfinity norm.
For the L1 norm, we give linear time algorithms when the output values
are in a bounded, finite set, and an approximation algorithm
when the output values are in a bounded range.
An open question that remains is to construct linear time
isotonic regression in the L1 norm for the arbitrary case.

(2005 Jrnl) Costas Busch,
Malik MagdonIsmail
and Mukkai Krishnamoorthy
"Hardness Results for CakeCutting",
Bulletin of the
European
Association for Theoretical Computer Science,
Number 86, pp. 85106, June 2005.
Journal Version:
postscript
, pdf.
Conference Version: Symposium on the Theoretical Aspects of Computing
(STACS), 2003,
postscript,
pdf.
Summary:
We consider the algorithm aspects of fair division of a resource,
in which limited input from the users may be obtained regarding
how much they value a certain part of the resource. If there
are n users, it is known that a fair division of the resource
(one in which no user thinks they have a less than 1/n
of the resource) can be obtained using n logn cuts of the
resource (which is modeled as the unit interval). No
matching lower bound is available. We take a first step in this direction
by showing (through reduction from sorting) that Omega(n logn)
comparisons are made by any fair division algorithm.
We also consider strong envyfree division (in which no user thinks
she has a lesser share than any other user), and give lower bounds
of Omega(n^2) on the number of cuts that must be made.

(2005 Conf)
HungChing (Justin) Chen, Malik MagdonIsmail,
"Learning Martingale Measures to Price Options",
1st Workshop on Machine Learning in Finance at NIPS 2005
Vancouver/Whistler, Dec 9, 2005.
postscript,
pdf.
Slides:
postscript,
pdf.

(2005 Conf)
Ali Civril, Malik MagdonIsmail and Eli BocekRivele,
"SDE: Graph Drawing Using Spectral Distance Embedding",
13th International Symposium on Graph Drawing (GD05),
Limerick, Ireland, Sept 1214, 2005.
postscript,
pdf.
Slides:
postscript,
pdf.
powerpoint.
Technical Report:
postscript,
pdf.

(2005 Conf)
Sibel Adali, Tina Liu and
Malik MagdonIsmail,
"Optimal Link Bombs are Uncoordinated",
First International Workshop on Adversarial Information Retrieval on the Web
(AIRWeb 05) at the
14th International World Wide Web Conference (WWW2005),
Chiba, Japan, 1014 May, 2005.
postscript,
pdf.
Slides:
ps,
pdf,
powerpoint,

(2005 Conf)
Jeffery Baumes, HungChing Chen,
Matthew Francisco,
Mark Goldberg,
Malik MagdonIsmail,
and
Al Wallace
"Dynamics of Bridging and Bonding in Social Groups, a MultiAgent
Model",
3rd Conf. of North American Association for Computational
Social and Organizational Science (NAACSOS 05),
NotreDame, Indiana, June 2628, 2005.
postscript,
pdf.
Slides:
ps,
pdf,
powerpoint,

(2005 Conf)
Jeffery Baumes,
Mark Goldberg,
Malik MagdonIsmail,
"Efficient Identification of Overlapping Communities",
IEEE International Conference
on Intelligence and Security Informatics (ISI 05),
Atlanta, Georgia, May 1920 2005.
postscript,
pdf.
Slides:
ps,
pdf,
powerpoint,

(2005 Conf)
Costas Busch,
Malik MagdonIsmail,
Jing Xi
"Oblivious Routing
on Geometric Networks",
17th ACM Symp. on Parallelism in Alg. and Arch. (SPAA) 2005,
July 1720, Las Vegas, Nevada, USA.
postscript,
pdf.
Slides:
ps,
pdf.

(2005 Conf)
Costas Busch, Shailesh Kelkar,
Malik MagdonIsmail
"Efficient Bufferless Routing on Leveled Networks",
EUROPAR 2005,
Aug 30Sep 2, Lisboa, Portugal.
postscript,
pdf.
Slides:
postscript,
pdf.

(2005 Conf)
Jonathan Purnell,
Malik MagdonIsmail, Heidi Newberg
"A Probabilistic Approach to Finding Geometric
Objects in Spatial Datasets of the Milky Way",
15th International Symposium on Methodoligies for
Intelligent Systems (ISMIS 2005),
May 2528, Saratoga Springs, NY, USA.
postscript,
pdf.
Slides:
ps,
pdf,
powerpoint,

(2005 Conf)
Mark Goldberg, David Hollinger,
Malik MagdonIsmail
"Experimental Evaluation of the Greedy and Random Algorithms for Finding
Independent Sets in Random Graphs",
4th International Workshop on Efficient and Experimental
Algorithms (WEA 2005),
May 1013, Santorini, Greece.
postscript,
pdf.
Slides:
postscript,
pdf.

(2005 Conf)
Costas Busch,
Malik MagdonIsmail,
Jing Xi
"Optimal Oblivious Path Selection on the Mesh",
International Parallel and Distributed Processing Symposium (IPDPS 2005),
Apr 38, Denver, Colorado, USA.
postscript,
pdf.
Slides:
postscript,
pdf.

(2005 Conf)
Jeffrey Baumes, Mark Goldberg, Mukkai Krishnamoorthy,
Malik MagdonIsmail, Nathan Preston
"Finding Communities by Clustering a Graph into Overlapping Subgraphs",
International Conference on Applied Computing (IADIS 2005),
Feb 2225, Algarve, Portugal.
postscript,
pdf,
doc.
Slides:
ps,
pdf,
powerpoint,

(2005 Conf)
Seyit Ahmet Camtepe, Mark Goldberg,
Malik MagdonIsmail, Mukkai Krishnamoorthy
"Detecting Conversing Groups of Chatters: A Model, Algorithms and Tests",
International Conference on Applied Computing (IADIS 2005),
Feb 2225, Algarve, Portugal.
postscript,
pdf,
doc.
Slides:
ps,
pdf,
powerpoint,
2004:

(2004 Jrnl) Malik MagdonIsmail,
Amir F. Atiya,
"Maximum Drawdown",
Risk Magazine, Volume 17, Number 10, pages 99102, October, 2004.
postscript (preprint)
, pdf (preprint).
Print Version.
Summary:
We use some recent results on the behavior of the Maximum Drawdown of
a Brownian motion to develop a scaling law for the Maximum Drawdown which
allows one to compare the Sterling/Calmar ratios of trading strategies
when the historical data available for the different trading strategies
extends over different lengths of time.

(2004 Jrnl) Malik MagdonIsmail,
Amir F. Atiya,
Amrit Pratap,
and
Yaser S. AbuMostafa
"On the Maximum Drawdown of a Brownian Motion",
Journal of Applied Probability, Volume 41, Number 1, pages 147161,
March, 2004.
Journal Version:
postscript (preprint)
, pdf (preprint).
Print Version.
Conference Version: Conference on Computational Intelligence
for Financial Engineering (CIFEr), 2003,
postscript,
pdf.
Summary:
We develop the distribution for the Maximum Drawdown (largest drop from a
peak to a bottom) of a Brownian motion. We compute the expected value
as an infinite integral series.
We reduce this function to a single "universal" function, which
can be computed numerically once, and used to compute the expected drawdown
for any Brownian motion.
We compute the asymptotic behavior of this
infinite series to reveal three regimes for the behavior of the
MDD  logarithmic, squareroot and linear, depending on the
sign of the drift parameter in the Brownian motion.

(2004 Conf)
Costas Busch,
Malik MagdonIsmail,
Fikret Sivrikaya,
Bulent Yener
"ContentionFree MAC Protocols for Wireless Sensor Networks",
18th Annual Conference on Distributed Computing (DISC 2004),
Oct 47, Amsterdam, the Netherlands.
postscript,
pdf.
Slides:
ps,
pdf,
powerpoint,

(2004 Conf)
Costas Busch,
Malik MagdonIsmail,
Marios Mavronicolas,
"Universal Bufferless Routing",
Workshop in Online Algorithms (with
ESA 2004 in conjunction with ALGO 2004),
Sept 1417, Bergen, Norway.
postscript,
pdf.
Slides:
ps,
pdf,
powerpoint,

(2004 Conf)
Costas Busch,
Malik MagdonIsmail,
Marios Mavronicolas,
Paul Spirakis
"Direct Routing: Algorithms and Complexity",
12th European Symposium on Algorithms
(ESA 2004 in conjunction with ALGO 2004),
Sept 1417, Bergen, Norway.
postscript,
pdf.
Slides:
postscript,
pdf.

(2004 Conf)
Costas Busch,
Malik MagdonIsmail,
Marios Mavronicolas,
Roger Wattenhofer
"NearOptimal Hot Potato Routing on Trees",
EUROPAR 2004,
31 Aug3 Sept, Pisa, Italy.
postscript,
pdf.
Slides:
ps,
pdf,
powerpoint,

(2004 Conf)
HungChing Chen,
Mark Goldberg,
Malik MagdonIsmail,
"Identifying MultiID users in Open Forums",
2nd NSF/NIJ Symposium on Intelligence and Security Informatics (ISI 04),
Tucson, AZ, June 1112 2004.
postscript,
pdf.
Slides:
ps ,
pdf ,
powerpoint ,

(2004 Conf)
Jeffery Baumes,
Mark Goldberg,
Malik MagdonIsmail,
William Wallace
"Discovering Hidden Groups in Communication Networks",
2nd NSF/NIJ Symposium on Intelligence and Security Informatics (ISI 04),
Tucson, AZ, June 1112 2004.
postscript,
pdf.
Slides:
ps,
pdf,
powerpoint,
2003:

(2003 Jrnl) Malik MagdonIsmail and Amir F. Atiya
"A Maximum Likelihood Approach to Variance Estimation of a Brownian
Motion Using the High, Low and Close",
Quantitative Finance, volume 3, issue 5, pages 376  384, August 2003.
Preprint versions: postscript
, pdf.
Print version
Summary:
Since joint distribution of the high, low and close (conditioned on the
open, drift and variance parameters) can be computed, we use this
distribution to develop a likelihood for observing the
high, low and close conditioned on the drift and variance parameters.
By maximizing this likelihood, we construct an estimate of the variance
parameter,
which we compare to other well known estimators of variance parameter.
Maximizing the likelihood yields a systematic gain in performance.

(2003 Conf) Malik MagdonIsmail and Joseph Sill
"Using a Linear Fit to Determine Monotonicity Directions",
The 16th Annual Conference on Learning Theory (COLT 2003),
Washington, DC, USA, August 2427 2003.
ps
pdf
Slides:
postscript,
pdf.

(2003 Conf)
Mark Goldberg,
Paul Horn,
Malik MagdonIsmail,
Jessie Riposo,
David Siebecker
and
William Wallace
Bulent Yener
"Statistical Modeling of Social Groups on Communication Networks",
First conference of the North American Association for Computational
Social and Organizational Science (CASOS 03),
Pittsburgh PA, June 2225, 2003.
postscript,
pdf.
Slides:
postscript,
pdf.

(2003 Conf)
Malik MagdonIsmail,
Mark Goldberg,
David Siebecker
and
William Wallace
"Locating Hidden Groups in Communication Networks Using Hidden Markov Models ",
NSF/NIJ Symposium on Intelligence and Security Informatics (ISI 03),
Tucson, AZ, June 23 2003.
postscript,
pdf.
Slides:
postscript,
pdf.

(2003 Conf)
Malik MagdonIsmail,
Amir Atiya,
Amrit Pratap,
and
Yaser S. AbuMostafa
"The Maximum Drawdown of the Brownian Motion",
International Conference on Computational Intelligence
for Financial Engineering (CIFEr 03), Hong Kong, March 2003.
postscript,
pdf.
Slides:
postscript,
pdf.

(2003 Conf)
Malik MagdonIsmail
"Pricing the American Put Using a New Class of Tight Lower Bounds",
International Conference on Computational Intelligence
for Financial Engineering
(CIFEr 03), Hong Kong, March 2003.
postscript,
pdf.
Slides:
postscript,
pdf.

(2003 Conf)
Malik MagdonIsmail, Costas Busch
and Mukkai Krishnamoorthy
"CakeCutting is Not A Piece of Cake",
Symposium on the Theoretical Aspects of Computer Science (STACS 03),
Berlin,
February 27  March 1, 2003.
postscript,
pdf.
Slides:
ps,
pdf,
powerpoint,
2002:

(2002 Jrnl) Malik MagdonIsmail and Amir F. Atiya
"Density Estimation and Random Variate Generation
Using MultiLayer Networks",
IEEE Transactions on Neural Networks, Volume 13, Number 3, pp 497520,
May 2002.
Journal Version:
postscript
, pdf.
Conference Versions:
Advances in Neural Information Processing Systems (NIPS),
1998,
postscript,
pdf. (Density Estimation)
Neural Networks for Signal Processing (NNSP99), 1999
postscript,
pdf.
(Control Theory Formulation of Random Variate Generation)
Summary:
We consider density estimation and random variate generation using
neural networks. For density estimation, we give two methods, both
based on learning the sample cumulative distribution function,
one is randomized (SLC) and one is a deterministic interpolation
using a smoothness constraint.
We prove that the randomized algorithm converges to the
deterministic version, asymptotically, however practically, randomization
offers an additional smoothness property. We prove convergence
of the deterministic algorithm to the true density given bounded derivative
constraints on the true density.

(2002 Conf) Malik MagdonIsmail, HungChing (Justin) Chen
and Yaser S. AbuMostafa
"The Multilevel Classification Problem and a Monotonicity Hint",
Intelligent Data Engineering and Learning, Third International Conference,
Manchester, UK, August, 2002. Springer.
postscript,
pdf.
Slides:
postscript,
pdf.

(2002 Conf) Malik MagdonIsmail, Yu Shao,
Daniel Freedman and Chris Bystroff
"Compressing Protein Conformational Space",
ISMB02: Tenth International Conference on Intelligent Systems for
Molecular Biology, August 2002.
postscript,
pdf.
(submitted, rejected)

(2002 Conf) Yu Shao, Malik MagdonIsmail,
Daniel Freedman, Srinivas Akella, Mohammed Zaki and Chris Bystroff
"Compressing Protein Conformational Space",
RECOMB02: Sixth International Conference on Research in Computational
Molecular Biology, April 2002 (poster).
postscript,
pdf.
(abstract)

(2002 BkChap) Malik MagdonIsmail
"Maximum Likelihood Estimation (MLE)",
Book Chapter, to appear in
"Encyclopedia of Financial Engineering and Risk Management",
commissioning editor Gillian Lindsey, Fitzroy Dearborn Publishers, 2002.
postscript
, pdf.

(2002 BkChap) Malik MagdonIsmail
"Ordinary Least Squares (OLS)",
Book Chapter, to appear in
"Encyclopedia of Financial Engineering and Risk Management",
commissioning editor Gillian Lindsey, Fitzroy Dearborn Publishers, 2002.
postscript
, pdf.

(2002 BkChap) Malik MagdonIsmail
"Expected Value / Mathematical Expectation",
Book Chapter, to appear in
"Encyclopedia of Financial Engineering and Risk Management",
commissioning editor Gillian Lindsey, Fitzroy Dearborn Publishers, 2002.
postscript
, pdf.
2001:

(2001 Jrnl) Malik MagdonIsmail
"The Equivalent Martingale Measure:
An Introduction to Pricing Using Expectations",
IEEE Transactions on Neural Networks, Volume 12, Number 4, pp 684693,
July 2001.
postscript
, pdf.
Summary:
We give an introduction to the Martingale measure, a tool for
pricing options, which forml a link between pricing of financial derivatives
and Monte Carlo simulation.
We use this approach together with a limiting argument to give an elementary
derivation of the price of the European call option, and discuss American
options.

(2001 Jrnl) Eric Breimer, Mark K. Goldberg, Brian Kolstad and
Malik MagdonIsmail
"On the Height of a Random Set of Points in a dDimensional Unit Cube",
Journal of Experimental Mathematics, Volume 10, Number 4, pp 583597, 2001.
Journal Version:
postscript
, pdf,
source code.
Conference Version: Workshop on Algorithm Engineering and Experiments (ALENEX),
2001,
postscript,
pdf.
Summary:
We give give efficient algorithms for estimating the height (maximum
antichain) of a set of
random points in a ddimensional unit cube. The algorithms are
based on a result we show which states that it suffices to consider
only points near the diagonal of the cube. We develop efficient algorithms
for generating these points directly, together with an efficient
algorithm for constructing the height of this set. We use the coconvergence
of estimates from different
sized regions around the diagonal to the same value too develop an improved
estimate. As a result, we give the first accurate estimates of
c_d, the coefficients governing the convergence rate.

(2001 Conf) Mark K. Goldberg, Darren T. Lim and
Malik MagdonIsmail
"A Learning Algorithm for String Assembly",
BIOKDD01: Workshop on Data Mining in Bioinformatics
(with SIGKDD01 Conference), August 2001.
postscript,
pdf.
Slides:
postscript,
pdf.

(2001 Conf) Eric Breimer, Mark K. Goldberg, Brian Kolstad and Malik MagdonIsmail
"Experimental Evaluation of the Height of a Random Set of Points in a dDimensional Cube",
3rd Workshop on Algorithm Engineering and Experiments (ALENEX), January 2001.
postscript,
pdf.
Slides:
postscript,
pdf.
2000:

(2000 Jrnl) Malik MagdonIsmail and Amir F. Atiya
"The Early Restart Algorithm",
Neural Computation, Volume 12, Number 6, pp 13031313, June 2000.
postscript
, pdf.
Summary:
We give an analysis of the early restart phenomenon which can be used to
speed up an algorithm whose running time is a function of the
initial conditions. For some initial conditions, the runtime may be excessively
long or unbounded (for example local minima in an optimization).
Given some probability distribution over which the initial conditions
are sampled, there is some distribution for the stopping time of
the process. We give a analysis of how using restart can improve the
expected runtime, and develop a condition for selecting the optimal
restart time. Essentially, if the algorithm has run for long enough, it
may be favorable to restart the algorithm.

(2000 Jrnl) Malik MagdonIsmail
"No Free Lunch for Noise Prediction",
Neural Computation, Volume 12, Number 3, pp547565, March 2000.
postscript
, pdf.
Summary:
We show that if the noise is additive, then the prior and posterior
distributions of the noise are equal when the prior over target functions
is uniform. There is no free lunch in the sense that if no useful
assumptions can be made about the target function, then it is not possible
gain any extra information regarding the nature of the noise.

(2000 Conf) Malik MagdonIsmail and Amir F. Atiya
"Volatility Estimation Using High, Low and Close Data  A Maximum Likelihood Approach",
Computational Finance (CF2000), Proceedings, June 2000.
postscript,
pdf.

(2000 Conf) Malik MagdonIsmail Amir F. Atiya, Yaser AbuMostafa
"Pricing the quality option for the bond futures contract in a
multifactor Vasicek framework",
Proceedings of the 16th IMACS World Congress, Lausanne, Switzerland,
August 2000.
postscript,
pdf.
1999 and before:

(1998 Jrnl) Malik MagdonIsmail,
Alexander Nicholson and Yaser AbuMostafa,
"Financial Markets, Very Noisy Information Processing",
Proceedings of the IEEE, Special Issue on Intelligent
Signal Processing, Volume 86, Number 11, pp 21842195, November 1998.
postscript
, pdf.
addendum to definition A.1, postcript
, pdf.
Summary:
We give a general characterization of the performance
of a general class
of learning systems. Specifically, when the learning system is stable
(satisfies certain regularity conditions) and the noise is
additive with bounded variance and the input distribution has
compact support, the test performance
approaches the optimal test performance at a universal rate of
O(1/N), where N is the number of data points.

(1999 Jrnl) Zehra Cataltepe, Yaser AbuMostafa and
Malik MagdonIsmail
"No Free Lunch for Early Stopping",
Neural Computation, Volume 11, Number 4, pp 9951010, May 1998.
postscript
, pdf.
Summary:
We show that the success of early stopping is an artifact of training
dynamics which tends to initialize the weights at smaller values and so
the resulting function tends to have smaller magnitude weights, and
hence tends to be smoother, which corresponds to having a smoothness
prior on the target functions. When no such hidden
prior assumption is made, i.e.,
when early stopping chooses uniformily among all hypotheses with the same
(higher than optimal) error, we show that the resulting classifier
has performance which is monotonically decreasing in the value of the
early stopping error. Thus there is No Free Lunch for early stopping, in that
it can only be succesfull if some bias is given toward the target function
prior  which means that some prior on the target function is necessary.

(1998 Jrnl) Malik MagdonIsmail and Yaser AbuMostafa,
"Validation of Volatility Models",
Journal of Forecasting, Volume 17, pp 349368, 1998.
Journal Version:
postscript
, pdf.
Conference Version: Conference on Neural Networks in the
Capital Markets (NNCM), 1996.
postscript,
pdf.
Summary:
We analyse some systematic errors in the prediction of
volatility using Maximum Likelihood methods. In particular, there is a
systematic underprediction even when the mean is predicted well.
Further, Maximum Likelihood methods can systematically select the wrong
model over the correct model, when faced with a choice of two models.
We develop an expression for a correction factor for systematically
correcting for this systematic underprediction.

(1999 Conf) Malik MagdonIsmail and Amir F. Atiya
"A Control Formulation for Random Variate Generation",
Neural Networks for Signal Processing (NNSP99) IX, Proceedings of the 1999
IEEE Workshop, eds. YuHen Hu, Jan Larsen, Elizabeth Wilson,
Scott Douglas, August 1999.
postscript,
pdf.

(1999 Conf) Malik MagdonIsmail and Amir Atiya,
"A Bayesian Approach to Estimating Mutual Fund Returns",
Computational Finance (CF99), eds Yaser S. AbuMostafa, Blake LeBaron, Andrew W. Lo and Andreas S. Weigend, MIT Press, 1999.
postscript,
pdf.

(1998 Conf) Malik MagdonIsmail and Amir Atiya,
"Neural Networks for Density Estimation",
Advances in Neural Information Processing Systems (NIPS) 11,
Proceedings of the 1998 Conference, pp522528, eds.
Michael S. Kearns, Sara A. Solla and David A. Cohen, MIT Press, 1998.
postscript,
pdf.

(1998 Conf) Malik MagdonIsmail and Amir Atiya
"Neural Networks for Density Estimation in Financial Markets",
Intelligent Data Engineering and Learning, First International Symposium,
pp 171178,
eds. L. Xu, L. W. Chan, I. King and A. Fu, Springer, October, 1998.
postscript,
pdf.

(1998 Conf) Malik MagdonIsmail, Alexander Nicholson and Yaser AbuMostafa,
"Estimating Model Limitation in Financial Markets",
Intelligent Data Engineering and Learning (IDEAL), First International Symposium, pp 1926, eds. L. Xu, L. W. Chan, I. King and A. Fu, Springer, October, 1998.
postscript,
pdf.

(1997 Conf) Zehra Cataltepe and Malik MagdonIsmail
"Incorporating Test Inputs into Learning",
Advances in Neural Information Processing Systems (NIPS) 10, Proceedings of the 1997 Conference, pp 437443, eds. Michael I. Jordan, Michael J. Kearns and
Sara A. Solla, MIT Press, 1997.
postscript,
pdf.

(1996 Conf) Malik MagdonIsmail and Yaser AbuMostafa,
"Systematic Underprediction of Volatility in Maximum Likelihood Methods",
Decision Technologies for Financial Engineering, Proceedings of the Fourth International Conference on Neural Networks in the Capital Markets, NNCM 96 (currently Computational Finance), pp 125137, eds. Andreas S. Weigend, Yaser S. AbuMostafa and A.Paul N. Refenes, World Scientific, 1996.
postscript,
pdf.

(1998 BkChap) Malik MagdonIsmail, Alexander Nicholson and Yaser AbuMostafa,
"Learning in the Presence of Noise",
Book Chapter, in "Intelligent Signal Processing", eds. Simon Haykin and
Bart Kosko, IEEE Press, 2001.
postscript
, pdf.
The
IEEE
provisional copyright policies require the following message be posted:

This material is presented to ensure timely dissemination of
scholarly and technical work. Copyright and all rights
therein are retained by authors or by other copyright holders.
All persons copying this information are expected to adhere
to the terms and constraints invoked by each author's
copyright. In most cases, these works may not be reposted
without the explicit permission of the copyright holder.
