David Witmer

I am a Ph.D. student in the Computer Science Department at CMU. My advisors are Anupam Gupta and Ryan O'Donnell. 

my email address


Spring 2017:  15-750: Graduate Algorithms


Sum of squares lower bounds for refuting any CSP (arXiv)
P. K. Kothari, R. Mori, R. O'Donnell, D. Witmer.

Lower bounds for CSP refutation by SDP hierarchies (arXiv)
R. Mori, D. Witmer.
      RANDOM 2016

Remarks on the Most Informative Function Conjecture at fixed mean (arXiv)
G. Kindler, R. O'Donnell, D. Witmer.

Beating the random assignment on constraint satisfaction problems of bounded degree (arXiv)
B. Barak, A. Moitra, R. O'Donnell, P. Raghavendra, O. Regev, D. Steurer, L. Trevisan, A. Vijayaraghavan, D. Witmer, J. Wright.
      APPROX 2015

How to refute a random CSP (arXiv)
S. R. Allen, R. O'Donnell, D. Witmer.
      FOCS 2015

Goldreich's PRG: Evidence for near-optimal polynomial stretch (pdf)
R. O'Donnell, D. Witmer.
      CCC 2014

Efficiency Analysis of Formally Verified Adaptive Cruise Controllers (pdf)
S. M. Loos, D. Witmer, P. Steenkiste, A. Platzer.
      IEEE Conference on Intelligent Transportation Systems 2013

Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results (arXiv)
A. Gupta, K. Talwar, D. Witmer.
      STOC 2013

Markov chain methods for small-set expansion (arXiv)
R. O'Donnell, D. Witmer.

Sloppy models, parameter uncertainty, and the role of experimental design (url)
J. F. Apgar, D. Witmer, F. M. White, B. Tidor.
      Molecular BioSystems 6 (10), pp. 1890-1900 (2010).

Effects of atherogenic diet on hepatic gene expression across mouse strains (url)
K. R. Shockley, D. Witmer, S. L. Burgess-Herbert, B. Paigen, G. A. Churchill.
      Physiological Genomics 39 (3), pp. 172-182 (2009).