“the main point
of the new algorithm
is that it is guaranteed
to work and
to work quickly,”
says Gary L. miller.

tee was only theoretical and for what he
calls “impractically huge” system ma-
trices. The new CMU solver, says Spiel-
man, fixes this problem. “The resulting
algorithm is theoretically sound, prov-
ably correct, and reasonable in prac-
tice,” he says. “Now, they just need to
optimize their implementations.”
Spielman says he expects it will be
another decade before understanding
of the CMU algorithm fully matures,
and that it remains to be seen whether
the algorithm will be put to use by de-
velopers in the near term. “There are
still many reasonable ways of varying
their algorithm,” Spielman says. “I ex-
pect particular applications will benefit
from different optimizations.”
For the algorithm to be useful in
practice, these optimizations must be
done so the new algorithm can accom-
modate the massive sets of data that are
the norm for machine-learning prob-
lems, materials modeling, image pro-
cessing, and other applications whose
computational results often benefit
from better input-data quality. One
way to accommodate large amounts of
input data while still achieving accept-
able computation speed is, of course, to
parallelize, but parallelization remains
an ongoing challenge in itself for algo-
rithm designers.

“People want better answers, but
the algorithms cannot practically
handle the larger data sets unless they
are fast,” says Spielman. “The best we
can hope for is algorithms whose run-
ning time scales linearly with their in-
put size.”
Koutis, Miller, and Peng are work-
ing on such optimizations, including
parallelization, and are testing their
ideas in several practical implementa-
tions, such as a new approach to medi-
cal imaging developed with David Toll-
iver, also at CMU, and researchers at
the University of Pittsburgh Medical
Center. The idea is to use a technique
called spectral rounding, driven by SDD
systems, to improve the quality of reti-
nal image segmentation. Koutis says
that, so far, he and his colleagues have
achieved imaging results whose qual-
ity, in many cases, has far exceeded that
of previous methods.

Further Reading

Koutis, I., Miller, G.L., and Peng, R. Approaching optimality for solving SDD linear systems, Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, Las Vegas, nV, Oct. 23–26, 2010. Spielman, D.A. and Teng, S-H. nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, June 13–16, 2004.

Koutis, I., Miller, G.L., and Tolliver, D. Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing, Proceedings of the 5th International Symposium on Advances in Visual Computing: Part I, Las Vegas, nV, nov. 30–Dec. 2, 2009.

Blelloch, G.E., Koutis, I., Miller, G.L., and Tangwongsan, K. hierarchical diagonal blocking and precision reduction applied to combinatorial multigrid, Proceedings of the 2010 ACM/ IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, new Orleans, LA, nov. 13–19, 2010.

Teng, S.-H.

The Laplacian paradigm: Emerging algorithms for massive graphs. Lecture Notes in Computer Science 6108, Kratochvíl, J., Li, A., Fiala, J., and Kolman, P. (Eds.), Springer-Verlag, Berlin, Germany, 2010.

based in los angeles, Kirk L. Kroeker is a freelance editor and writer specializing in science and technology.

© 2011 aCM 0001-0782/11/09 $10.00

Security
Small
Companies
Targeted

Cybercriminals have expanded their reach beyond large corporations and are increasingly attacking small businesses, according to The Wall Street Journal.

While break-ins at sony and
other well-known corporations
have recently attracted
widespread media attention, the
boom in small business hacking
has gone largely unnoticed.
last year, the U.s. secret
service and Verizon responded
to a combined total of 761 data
breaches, with 63% of them
involving small businesses. in
2009, they responded to 141
data breaches, of which only
27% involved small businesses.
as small companies have
grown increasingly reliant on
computers in recent years,
they have started to store more
business-critical information
online, including credit card
information and other financial
data. While large organizations
usually employ rigorous security
measures to safeguard sensitive
data, small businesses’ relative
lack of it sophistication has
made them easy prey. the wide
array of small business systems
now in place has created
ample opportunities for
hackers to develop new
techniques for compromising
those systems.
in one common ploy,
hackers pilfer money by gaining
access to companies’ online
bank account login information.
the Journal reports that lease
duckwall of abilene, Ks, saw
$63,000 disappear from his
company’s bank account when
a hacker added nine fictitious
employees to the company’s
payroll. By the time duckwall
spotted the discrepancy and
notified his bank to freeze
the accounts, the hackers had
already withdrawn $22,000. to
this day, duckwall has no idea
how the hackers gained access
to his account information.
small business hacking is
becoming a “prolific problem,”
dean Kinsman, a special
agent in the federal Bureau of
investigation’s cyberdivision,
told the Journal. “it’s going to get
much worse before it gets better.”
—Alex Wright