Grant Schoenebeck

theoretical computer science, linear and semidefinite programs, intersection of computer science and social networks, intersection of computer science and economics, NP-complete optimization problems, computational complexity theory

Personal:

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 recently received my PhD from UC Berkeley in computer science where I was advised by Luca Trevisan.

Papers:

Also available in reverse chronological order

NP-Complete Optimization

Linear and Semidefinite Programming Hierarchies

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

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

Non-monotone Submodular Maximization (Offline and On-line)

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

Social Networks

Link Analysis

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

Potential Networks, Contagious Communities, and Social Network Structure.
G. Schoenebeck
submitted

Models and Analysis of Network Processes

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

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

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

Economics and Computer Science

Computating Nash Equilibrium and Related Problems

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

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

Algorithmic Mechanism Design

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

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

Other

Coding Theory/Property Testing

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

Crytography/Hardness Amplification

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

Peer to Peer Networks

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