Michael Brautbar

Contact info:
Computer and Information Science
University of Pennsylvania
561 Levine Hall (GRW Wing), 3330 Walnut Street,
Philadelphia, PA 19104.
Email: brautbar AT cis DOT upenn DOT edu
Mobile: 215-779-7935

Welcome! I'm a PhD student in the Computer and Information Science department at the University of Pennsylvania.
I am fortunate to have Michael Kearns as my academic advisor.
Before coming to Penn, I completed my undergraduate and master of science studies in Computer Science from the Hebrew University.

My Research interests lie in algorithm design and theoretical computer science.
In particular, I work in social networks theory, economics and computation, and applied probability.


Publications
  1. The Power of Local Information in Social Networks [arXiv]
    with Christian Borgs, Jennifer Chayes, Sanjeev Khanna, and Brendan Lucier
    In submission.
  2. A Sublinear Time Algorithm for PageRank Computations and Related Applications [arXiv]
    with Christian Borgs, Jennifer Chayes, and Shang-Hua Teng
    Workshop on Algorithms and Models for the Web Graph (WAW), 2012, to appear.
  3. A Clustering Coefficient Network Formation Game [PDF]
    with Michael Kearns
    Symposium on Algorithmic Game Theory (SAGT), 2011, Amalfi, Italy.
    A preliminary workshop version appeared in the second Workshop on Information in Networks.
  4. Private and Third Party Randomization in Risk-Sensitive Equilibrium Concepts [PDF]
    with Michael Kearns and Umar Syed
    Twenty-Forth AAAI Conference on Artificial Intelligence (AAAI), 2010, Atlanta, Georgia.
  5. Local Algorithms for Finding Interesting Individuals in Large Networks [PDF]
    with Michael Kearns
    Innovations in Computer Science (ICS), 2010, Beijing, China.
    A preliminary workshop version appeared in the first Workshop on Information in Networks
    and also in New York Computer Science and Economics Day, 2009.
  6. Online Learning a Binary Labeling of a Graph [PDF]
    Mining and Learning with Graphs (MLG), 2009, Leuven, Belgium.
  7. On Efficient Entropy Approximation via Lempel-Ziv Compression [PDF]
    with Alex Samorodnitsky
  8. Approximating the Entropy from Sublinear Samples [PDF]
    with Alex Samorodnitsky
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, New Orleans, USA.
  9. Approximating the Entropy of Large Alphabets
    Master thesis, Hebrew University of Jerusalem.