# About

Institute for Operations Research

Department of Mathematics

ETH Zurich

stephenc@ethz.ch

I study algorithms for combinatorial optimization and streaming computation. My present projects relate to efficient computation on massive data sets, optimization tasks for machine learning problems, and approximation algorithms for interdiction.

Department of Mathematics

ETH Zurich

stephenc@ethz.ch

I study algorithms for combinatorial optimization and streaming computation. My present projects relate to efficient computation on massive data sets, optimization tasks for machine learning problems, and approximation algorithms for interdiction.

### Papers

- with V. Braverman, R. Krauthgamer, and L. F. Yang. Sketches for Matrix Norms: Faster, Smaller and More General. 2016
- with M. Nägele and R. Zenklusen. Refuting a Conjecture of Goemans on Bounded Degree Spanning Trees. Operations Research Letters. 2016
- with V. Braverman, N. Ivkin, J. Nelson, Z. Wang, and D. P. Woodruff. BPTree: an l2 Heavy Hitters Algorithm Using Constant Memory. in PODS. 2017
- with R. Hildebrand and R. Zenklusen. Sublinear Bounds for a Quantitative Doignon-Bell-Scarf Theorem. 2015
- with R. Zenklusen. Hardness and Approximation for Network Flow Interdiction. Networks. 2017. older arXiv version
- with J. Błasiok, V. Braverman, R. Krauthgamer, and L. F. Yang. Streaming Symmetric Norms via Measure Concentration. in STOC. 2017
- with V. Braverman, N. Ivkin, and D. P. Woodruff. Beating CountSketch for Heavy Hitters in Insertion Streams. in STOC. 2016
- with R. Zenklusen. Interdicting structured combinatorial optimization problems with {0,1}-objectives. Mathematics of Operations Research. 2016
- with V. Braverman, D. P. Woodruff, and L. F. Yang. Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors. in PODS. 2016
- Stream Sketches, Sampling, and Sabotage. PhD Thesis. 2015
- with V. Braverman. Universal sketches for the frequency negative moments and other decreasing streaming sums. in RANDOM. 2015
- with M. Lladser. Approximation of sojourn-times via maximal couplings: motif frequency distributions. Journal of Mathematical Biology. 2013
- with D. Fishkind. Counting spanning trees of threshold graphs. 2012
- with M. Lladser. Occupancy distributions in Markov chains via Doeblin's ergodicity coefficient. DMTCS Proceedings, AofA'10. 2010: 79-92
- Before entering grad school I worked on specialized navigation problems. I have two papers and patent to that effect.

### Talks

- "Concentration Inequalities." IFOR Seminar. ETH Zurich. October 2016.
- "Hardness and approximation for Network Flow Interdiction." Swiss OR Days. Università della Svizzera Italiana. September 2016. slides
- "Approximation algorithms for interdiction problems." OR 2016. Helmut-Schmidt University. August 2016. slides
- "Finding heavy hitters by chaining with few random bits." Chaining Methods and their Applications to Computer Science. Harvard University. June 2016. slides. video
- "Beating CountSketch for heavy hitters." Symposium on the Theory of Computing. Cambridge, MA. June 2016. slides
- "L2 heavy hitters in optimal space and time." Theory Reading Group. EPFL. June 2016. notes
- "Beating CountSketch for heavy hitters." Mittagsseminar. ETH Zurich. June 2016. slides
- "Beating CountSketch for heavy hitters." Foundations of Computer Science Seminar. Weizmann Institute. May 2016. slides
- "Streaming sums and symmetric norms." NICT Inference Workshop. Institut Henri Poincaré. March 2016. slides. video
- "Streaming symmetric norms via measure concentration." NICT Central Workshop. Institut Henri Poincaré. February 2016. slides. video
- "The space complexity of streaming sums". Sublinear Algorithms Workshop. Johns Hopkins University. January 2016. slides
- "Universal sketches for the frequency negative moments". RANDOM. Princeton University. August 2015. slides
- "b-stable set interdiction on bipartite graphs". International Symposium on Mathematical Programming. Pittsburgh, PA. July 2015. slides
- "Stable and b-stable set interdiction on bipartite graphs". Swiss OR Days. IBM Research Ruschlikon. May 2015. slides
- "Streaming space complexity of nearly all functions of one variable". Mittagsseminar. ETH Zurich. April 2015. slides
- "Sampling bipartite graphs". IFOR Seminar. ETH Zurich. January 2014. slides
- "Sampling bipartite graphs". CUSO Spring Seminar. Zinal, Switzerland. January 2014. slides