Communications of the ACM

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.

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.