Alex Fabrikant

alexf * at *
Cell 510-725-9182
(N.B.: this is my permanent forwarding address)

This academic homepage is for those interested in my research work. I do not speak for my employer here.

- Bio - Papers - Teaching - Personal page -


I am a research scientist at Google, in the Social Research & Analytics group, working primarily on algorithms and link mining on social (hyper)graphs.

Before joining Google, I was a postdoc at Princeton University, in Jennifer Rexford's networking group and the Princeton CS theory group. I received my Ph.D. from UC Berkeley in 2008, with Christos H. Papadimitriou as my thesis advisor. My taste in research problems can be broadly described as "applied CS theory". My ongoing work and long-term research interests span the Cartesian product of {algorithmic game theory, combinatorial algorithms, and lower bounds} firmly grounded in applications to de-centralized systems and models in various applied domains: {social networks, computer networks, distributed systems}.


  1. James Cook, Atish Das Sarma, Alex Fabrikant, and Andrew Tomkins. Your Two Weeks of Fame and Your Grandmother's. Earlier version appears in Proc. of WWW 2012.
  2. Lujun Fang, Alex Fabrikant, Kristen LeFevre. "Look Who I Found: Understanding the Effects of Sharing Curated Friend Groups". To appear in WebSci 2012.
  3. Roee Engelberg, Alex Fabrikant, Michael Schapira, David Wajc. "Best-Response Dynamics Out of Sync: Complexity and Characterization". In submission.
  4. Alex Fabrikant, Umar Syed, and Jennifer Rexford, There's something about MRAI: Timing diversity exponentially worsens BGP convergence. In Proc. of INFOCOM 2011.
  5. Martin Suchara, Alex Fabrikant, and Jennifer Rexford, BGP Safety with Spurious Updates. In Proc. of INFOCOM 2011.
  6. Alex Fabrikant, Aaron Jaggard, and Michael Schapira, On the Structure of Weakly Acyclic Games. In Proc. of SAGT 2010.
  7. Minlan Yu, Alex Fabrikant, and Jennifer Rexford, BUFFALO: Bloom filter forwarding architecture for large organizations, In Proc. of CoNEXT 2009, pages 313-324.
  8. Alex Fabrikant, The Complexity of Game Dynamics, Ph.D. Dissertation, UC Berkeley, 2008.
  9. Alex Fabrikant and Christos Papadimitriou, The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond, In Proc. of SODA 2008, pages 844-853.
  10. Constantinos Daskalakis, Alex Fabrikant, and Christos Papadimitriou, The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games, In Proc. of ICALP 2006, pages 513-524.
  11. Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar, "The Complexity of Pure Nash Equilibria". In Proc. of STOC 2004, pages 604-612.
  12. Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou, and Scott Shenker, "On a Network Creation Game.". In Proc. of 2003 PODC, pages 347-351.
  13. Alex Fabrikant, Elias Koutsoupias, and Christos H. Papadimitriou, "Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet". In Proc. of 2002 ICALP, pages 110-122. Springer-Verlag LNCS, 2002.
  14. Alex Fabrikant, Tad Hogg, "Graph Coloring with Quantum Heuristics". In Proc. of 2002 AAAI, pages 22-27. AAAI, 2002.


I have recently: