David Witmer

According to our database, David Witmer authored at least 9 papers between 2012 and 2017.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2017

Sum of squares lower bounds for refuting any CSP.

Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Lower Bounds for CSP Refutation by SDP Hierarchies.

Ryuhei Mori, David Witmer

Proceedings of the Approximation, 2016

2015

Beating the random assignment on constraint satisfaction problems of bounded degree.

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

Electron. Colloquium Comput. Complex., 2015

Continuous analogues of the Most Informative Function problem.

Guy Kindler, Ryan O'Donnell, David Witmer

CoRR, 2015

How to Refute a Random CSP.

Sarah R. Allen, Ryan O'Donnell, David Witmer

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch.

Ryan O'Donnell, David Witmer

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Sparsest cut on bounded treewidth graphs: algorithms and hardness results.

Anupam Gupta, Kunal Talwar, David Witmer

Proceedings of the Symposium on Theory of Computing Conference, 2013

Efficiency analysis of formally verified adaptive cruise controllers.

Sarah M. Loos, David Witmer, Peter Steenkiste, André Platzer

Proceedings of the 16th International IEEE Conference on Intelligent Transportation Systems, 2013

2012

Improved small-set expansion from higher eigenvalues

Ryan O'Donnell, David Witmer

CoRR, 2012