David Witmer

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