Grant Schoenebeck


I am excited to announce that starting Fall 2019, I will be an assistant professor in the School of Information at the University of Michigan School. I am currently in the Computer Science and Engineering Division at the University of Michigan.

I am looking for new PhD students! Please apply to UMSI and include my name in your application. I am interested in a wide range of students including those interested in computer science theory topics, those interested in applications of these topics (e.g. in social networks, political divisiveness and polarization, information elicitation mechanism, etc.), and those looking to combine theoretical and applied approaches.


NSF CAREER Award Recipient
Google Faculty Award Recipient
Facebook Faculty Award Recipient
NSF Algorithms in the Field Grant Recipient
NSF CCF Small Recipient


Curriculum Vitae

Research Interests:

theoretical computer science; the intersection of computer science and economics - especially social networks and mechanisms for information elicitation and aggregation

Students and Postdocs:

Yuqing Kong (current PhD Student, starts TT at Peking University Fall 2018)

Fang-Yi Yu (current PhD Student)

Biaoshuai Tao (current PhD Student)

Bo Li (former Post-Doc, starts TT at UIUC, Fall 2018)


Water from Two Rocks: Maximizing the Mutual Information
Y. Kong, G. Schoenebeck
EC '18, arXiv '18

Eliciting Expertise without Verification
Y. Kong, G. Schoenebeck
EC '18, arXiv '18

Characterizing Adversarial Subspaces Using Local Intrinsic Dimensionality
X. Ma, B. Li, Y. Wang, S. M. Erfani, S. Wijewickrema, M. E. Houle, G. Schoenebeck, D. Song, J. Bailey
ICLR '18 to appear, arXiv '18

Consensus of Interacting Particle Systems on Erdos-Renyi Graphs
G. Schoenebeck, F. Yu
SODA '18, pdf

Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case
Y. Kong, G. Schoenebeck.
ITCS '18

Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity
Y. Kong, G. Schoenebeck..
ITCS' 18, Arxiv '16

Contention-Aware Lock Scheduling for Transactional Databases
B. Tian, J. Huang, B. Mozafari, G. Schoenebeck

Don't Be Greedy: Leveraging Community Structure to Find High Quality Seed Sets for Influence Maximization
R. Angell, G. Schoenebeck
WINE'17, arXiv '16

Cascades and Myopic Routing in Nonhomogeneous Kleinbergs Small World Model
J. Gao, G. Schoenebeck, F. Yu
WINE '17

Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization
G. Schoenebeck, B. Tao
WINE '17, arXiv '17

A Top-Down Approach to Achieving Performance Predictability in Database Systems
J. Huang, B. Mozafari, G. Schoenebeck, T. Wenisch

Engineering Agreement:The Naming Game with Asymmetric and Heterogeneous Agents
J. Gao, B. Li, G. Schoenebeck, F. Yu
AAAI '17

How Complex Contagions Spread Quickly in Preferential Attachment Models and Other Time-Evolving Networks
R.Ebrahimi, J. Gao, G. Ghasemiesfeh, G. Schoenebeck
IEEE Transactions on Network Science and Engineering '17, arXiv '14

Sybil Detection Using Latent Network Structure
A. Snook, G. Schoenebeck, F. Yu.
EC '16

General Threshold Model for Social Cascades: Analysis and Simulations
J. Gao, G. Ghasemiesfeh, G. Schoenebeck, F. Yu
EC '16

Complex Contagions on Configuration Model Graphs with a Power-Law Degree Distribution
G. Schoenebeck, F. Yu
WINE '16

Putting Peer Prediction Under the Micro(economic)scope and Making Truth-telling Focal
Y. Kong, K. Ligett, G. Schoenebeck.
WINE '16, Arxiv '15

Identifying the Major Sources of Variance in Transaction Latencies: Towards More Predictable Databases
J. Huang, B. Mozafari, G. Schoenebeck, T. Wenisch

A Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling
Y. Kong, G. Schoenebeck..
Arxiv '15

Complex Contagions in Kleinberg's Small World Model
R. Ebrahimi, J. Gao, G. Ghasemiesfeh, G. Schoenebeck
ITCS '15

Buying Private Data without Verification
A. Ghosh, K. Ligett, A. Roth, G. Schoenebeck.
EC '14

Characterizing Strategic Cascades on Networks
T. Martin, G. Schoenebeck, M. Wellman
EC '14

Graph Isomorphism and the Lasserre Hierarchy
P. Codenotti, G. Schoenebeck, A. Snook
arXiv '14

Better Approximation Algorithms for the Graph Diameter.
S. Chechik, D. H. Larkin, L. Roditty, G. Schoenebeck, R. E. Tarjan, V. V. Williams
SODA '14

Potential Networks, Contagious Communities, and Social Network Structure.
G. Schoenebeck
WWW '13

Conducting Truthful Surveys, Cheaply
A. Roth, G. Schoenebeck.
EC '12

Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach
S. Arora, R. Ge, S. Sachdeva, G. Schoenebeck
EC '12

Social Learning in a Changing World
R. Frongillo, G. Schoenebeck, O. Tamuz
Wine '11

General Hardness Amplification of Predicates and Puzzles
T. Hollenstein, G. Schoenebeck
TCC '11

Constrained Non-monotone Submodular Maximization: Offline and Secretary Algoritms.
A. Gupta, A. Roth. G. Schoenebeck, K. Talwar.
WINE '10

The Limitations of Linear and Semidefinite Programs
G. Schoenebeck
PhD Thesis, 2010

Optimal Testing of Reed-Muller Codes
A. Bhattacharyya, S. Kopparty, G. Schoenebeck, M. Sudan, D. Zuckerman
FOCS '10.

Detecting Spam in a Twitter Network.
S. Yardi, D. Romero, G. Schoenebeck. d. boyd.
First Monday '10

Reaching Consensus on Social Networks
E. Mossel, G. Schoenebeck
ICS '10.

On the Complexity of Nash Equilibria of Action-Graph Games
C. Daskalakis, G. Schoenebeck, G. Valiant, P. Valiant
Soda '09.

Linear Level Lasserre Lower Bounds for Certain k-CSPs
G. Schoenebeck.
FOCS '08

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut
G. Schoenebeck, L. Trevisan, M. Tulsiani.
STOC '07

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover
G. Schoenebeck, L. Trevisan, M. Tulsiani.
CCC '07

Chora: Expert-based Peer-to-peer web search
H. Gylfason, O. Khan, G. Schoenebeck
AP2PC workshop at AAMAS '06.

The computational Complexity of Concisely Represented Games
G. Schoenebeck, S. Vadhan.
EC '06. ACM Transactions on Computation Theory 2012.

GrowRange: Anytime VCG-Based Mechanisms
D. Parkes, G. Schoenebeck.
AAAI '04.


Fall 2017

EECS 547 / SI: 652: Electronic Commerce (about algorithmic game theory) .

Winter 2017

EECS 376 Foundations of Computing

Fall 2015

EECS 598-06 Randomness and Computation

Winter 2015

EECS 376 Foundations of Computing

Fall 2014

EECS 574 Computational Complexity Theory

Fall 2013

EECS 574 Computational Complexity Theory

Winter 2013

EECS 203 Discrete Math

Fall 2012

EECS 598-06 Social Networks: Reasoning about Structure and Processes This class looked at social networks research and how a theoretical computer science prospective both brings new questions and gains additional insights into this growing body of research. Schedule and readings on the website.

New Jersey Governor's School: The Math Behind the Maching, Summer 2012

New Jersey Governor's School: The Math Behind the Maching, Summer 2011

Contact Information:

3636 Bob and Betty Beyster Building
2260 Hayward
University of Michigan
Ann Arbor, MI 48109-2121
Phone: (734)647-4712


I was born in Green Bay, WI and moved to Wichita, KS when I was nine. I attended Harvard University, graduating with highest honors in mathematics. Afterwards, I attended Oxford University as the von Clemm fellow and studied theology. I received my PhD from UC Berkeley in computer science where I was advised by Luca Trevisan. Subsequently I was the Simons Foundation Postdoctoral Research Fellow in Theoretical Computer Science at Princeton University.