David Witmer

Publication Activity (10 Years)

Years Active: 2012-2017
Publications (10 Years): 4

Top Topics

Constraint Satisfaction Problems

Constraint Networks

Bounded Treewidth

Top Venues

Publications

Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer
Sum of squares lower bounds for refuting any CSP. CoRR (2017)
Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer
Sum of squares lower bounds for refuting any CSP. STOC (2017)
Ryuhei Mori, David Witmer
Lower Bounds for CSP Refutation by SDP Hierarchies. APPROX-RANDOM (2016)
Ryuhei Mori, David Witmer
Lower bounds for CSP refutation by SDP hierarchies. CoRR (2016)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR (2015)
Guy Kindler, Ryan O'Donnell, David Witmer
Continuous analogues of the Most Informative Function problem. CoRR (2015)
Sarah R. Allen, Ryan O'Donnell, David Witmer
How to Refute a Random CSP. FOCS (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. 22 (2015)
Sarah R. Allen, Ryan O'Donnell, David Witmer
How to refute a random CSP. CoRR (2015)
Ryan O'Donnell, David Witmer
Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch. Computational Complexity Conference (2014)
Sarah M. Loos, David Witmer, Peter Steenkiste, André Platzer
Efficiency analysis of formally verified adaptive cruise controllers. ITSC (2013)
Anupam Gupta, Kunal Talwar, David Witmer
Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results CoRR (2013)
Anupam Gupta, Kunal Talwar, David Witmer
Sparsest cut on bounded treewidth graphs: algorithms and hardness results. STOC (2013)
Ryan O'Donnell, David Witmer
Improved small-set expansion from higher eigenvalues CoRR (2012)