optimization, machine learning, and network analysis.
Theorem 8 has already been applied many times within pure
mathematics (see, e.g., Naor28). We hope this body of work
will encourage more exchange of ideas between numerical
analysis, pure mathematics and theoretical computer science, and inspire and enable the development of faster algorithms and novel analyses of network phenomena.
References
1. abraham, I., neiman, o. using petal-decompositions to build a low stretch
spanning tree. In (2012).
2. achlioptas, D., mcsherry, f. fast
computation of low-rank matrix
approximations. , 2 (2007), 9.
3. alon, n., milman, V. D. λ1, isoperimetric
inequalities for graphs, and
superconcentrators. , 1 (1985), 73–88.
4. althöfer, I., Das, g., Dobkin, D., Joseph,
D., Soares, J. on sparse spanners
of weighted graphs. (1993), 81–100,
10.1007/bf02189308.
5. andersen, r., chung, f., lang, k. local
graph partitioning using pagerank
vectors. In (2006), 475–486.
6. andersen, r., yuval, P. finding sparse
cuts locally using evolving sets. In
(2009), acm, 235–244.
7. batson, J.D., Spielman, D.a., Srivastava, n.
twice-ramanujan sparsifiers. 6 (2012),
1704 –1721.
8. benczúr, a.a., karger, D.r.
approximating s-t minimum cuts in
o(n2) time. In (1996), 47–55.
9. bollobás, b. the isoperimetric number
of random regular graphs. , 3 (may
1988), 241–244.
10. chandra, a.k., raghavan, P., ruzzo, W.l.,
Smolensky, r., tiwari, P. the electrical
resistance of a graph captures its
commute and cover times. In (1989),
acm, new york, ny, uSa, 574–586.
11. cheeger, J. a lower bound for smallest
eigenvalue of laplacian. In (1970),
Princeton university Press, 195–199.
12. chierichetti, f., lattanzi, S., Panconesi, a.
rumour spreading and graph
conductance. In (2010), 1657–1663.
13. christiano, P., kelner, J.a., madry, a.,
Spielman, D.a., teng, S.h. electrical
flows, laplacian systems, and faster
approximation of maximum flow in
undirected graphs. In (2011), 273–282.
14. chung, f.r.k. Spectral graph theory.
cbmS regional conference Series in
mathematics, american mathematical
Society, 1997.
15. de carli Silva, m.k., harvey, n.J.a., Sato, c.m.
Sparse sums of positive semidefinite
matrices. (2011), abs/1107.0088.
16. Ding, J., lee, J.r., Peres, y. cover times,
blanket times, and majorizing measures.
In (2011), 61–70.
17. friedman, J. a Proof of alon’s Second
eigenvalue conjecture and related
Problems. number 910 in memoirs
of the american mathematical Society.
american mathematical Society, 2008.
Joshua Batson, mathematics, mIt.
Daniel A. Spielman, computer Science &
applied mathematics, yale university.
nikhil Srivastava, microsoft research,
bangalore.
Shang-hua Teng, computer Science,
uSc.
© 2013 acm 0001-0782/13/08
You’ve come a long way.
Share what you’ve learned.
ACM has partnered with MentorNet, the award-winning nonprofit e-mentoring network in engineering,
science and mathematics. MentorNet’s award-winning One-on-One Mentoring Programs pair ACM
student members with mentors from industry, government, higher education, and other sectors.
• Communicate by email about career goals, course work, and many other topics.
• Spend just 20 minutes a week - and make a huge difference in a student’s life.
• Take part in a lively online community of professionals and students all over the world.
Make a difference to a student in your field.
Sign up today at: www.mentornet.net
Find out more at: www.acm.org/mentornet
MentorNet’s sponsors include 3M Foundation, ACM, Alcoa Foundation, Agilent Technologies, Amylin Pharmaceuticals, Bechtel Group Foundation, Cisco
Systems, Hewlett-Packard Company, IBM Corporation, Intel Foundation, Lockheed Martin Space Systems, National Science Foundation, Naval Research
Laboratory, NVIDIA, Sandia National Laboratories, Schlumberger, S.D. Bechtel, Jr. Foundation, Texas Instruments, and The Henry Luce Foundation.