Matthias Poloczek
School of Operations Research and Information Engineering
Department of Computer Science

• About me
• Publications
• Teaching
• Poloczek Home
• ORIE Home
• CS Home

About me

I am a postdoctoral researcher with Professor Peter I. Frazier. My research is on algorithms in combinatorial optimization and decision-making under uncertainty. Specifically, I focus on algorithms that are fast in practice and provide provable performance guarantees.

I received my PhD from the Goethe-University Frankfurt in 2013, advised by Georg Schnitger. Then I joined Cornell University to work with Professor David P. Williamson, funded by a Feodor Lynen Research Fellowship of the Alexander von Humboldt Foundation in 2014 and 2015.

My work in optimal learning aims to optimally trade-off exploration vs. exploitation for sequential decision making under uncertainty. In particular, I develop Bayesian optimization algorithms for simulation optimization and the design of experiments with applications in aerospace engineering, biochemistry, chemical engineering, materials science, and medicine.
My research also deals with approximation algorithms for combinatorial problems that allow very fast implementations and thus scale to large data. Often these are randomized greedy algorithms. Moreover, I investigate the inherent limitations of the greedy paradigm, i.e. the price of making decisions myopically.

At SIAM CSE17 I will be a guide in the Sustainable Horizons program for underrepresented groups. Please feel free to contact me if you want to join my group.

Publications

• Multi-Information Source Optimization with General Model Discrepancies
   with Jialei Wang and Peter I. Frazier.
   Preliminary version on arXiv
  
• Bayesian Optimization with Gradients
   with Jian Wu, Andrew G. Wilson, and Peter I. Frazier.
   Preliminary version on arXiv
  
• Comparing the Finite-Time Performance of Simulation-Optimization Algorithms
   with Naijia Dong, David J. Eckman, Xueqi Zhao, and Shane G. Henderson.
   To Appear in the In Proc. of the 2017 Winter Simulation Conference (WSC).
   Preliminary version on arXiv -- Source code
  
• Greedy Algorithms for MAX SAT: Simple Algorithms and Inapproximability Bounds
   with Georg Schnitger, David P. Williamson, and Anke van Zuylen.
   In SIAM Journal on Computing (SICOMP), Vol. 46, Issue 3.
    DOI - PDF
  
• Warm Starting Bayesian Optimization
   with Jialei Wang and Peter I. Frazier.
   In Proc. of the 2016 Winter Simulation Conference (WSC).
   Bibtex - DOI - Extended version on arXiv
  
• An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
   with David P. Williamson.
   Accepted for publication in ACM Journal on Experimental Algorithmics (JEA).
   A preliminary version appeared in Proc. of 15th International Symposium on Experimental Algorithms (SEA), 2016.
   BibTex - DOI - Please contact me if you are interested in the full version of the paper.
  
• Simple Approximation Algorithms for Balanced MAX 2SAT
   with Alice Paul and David P. Williamson.
   In Algorithmica (special issue on LATIN'16), 2017.
   BibTeX - DOI
  
   A Preliminary version appeared in the Proc. of 12th Latin American Theoretical INformatics (LATIN), 2016.
   BibTeX - DOI
  
• Greedy Matching: Guarantees and Limitations
   with Bert Besser.
   In Algorithmica, 2017.
   BibTeX - DOI - Erratum for Theorem 5 - Preliminary version on arXiv
  
• Contagious Sets in Dense Graphs
   with Daniel Freund and Daniel Reichman.
   Accepted for publication in the European Journal of Combinatorics (Special issue on IWOCA'15 and IWOCA'14).
   Preliminary version on arXiv
   A preliminary version appeared in the Proc. of 26th International Workshop on Combinatorial Algorithms (IWOCA), 2015.
   BibTeX - DOI
  
• On Some Recent MAX SAT Approximation Algorithms
   with David P. Williamson and Anke van Zuylen.
   In Proc. of 11th Latin American Theoretical INformatics (LATIN), 2014.
   BibTeX - DOI - Preliminary version on arXiv
• Greedy Algorithms for Max Sat and Maximum Matching: Their Power and Limitations
   Ph.D. thesis, Goethe-University, Frankfurt am Main, Germany, 2012.
   Please contact me if you are interested in my thesis.
  
• Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis
   with Mario Szegedy.
   In Proc. of 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012.
   BibTeX - DOI
• Bounds on Greedy Algorithms for MAX SAT
   In Proc. of 19th Annual European Symposium on Algorithms (ESA), 2011.
   BibTeX - DOI - Full version
• Randomized Variants of Johnson's Algorithm for MAX SAT
   with Georg Schnitger.
   In Proc. of 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
   BibTeX - DOI