Marco Molinaro

I am an Assistant Professor in the Computer Science Department at PUC-RIo. I was previously an Assistant Professor at TU Delft's EWI and at Georgia Tech's ISyE and ACO, and before that a PhD student in the ACO program at Carnegie Mellon University.

Email: molinaro[dot]marco[AT]gmail[DOT]com

Current teaching

• 2021.1 - Estruturas Discretas
  
• 2021.1 - Analise de Algoritmos
  

Previous teaching (PUC)

• 2020.2 - Algoritmos e Incerteza (pos)
  
• 2020.2 - Estruturas Discretas
  
• 2020.1 - Projeto e Analise de Algoritmos (pos)
  
• 2020.1 - Estruturas Discretas
  
• 2019.2 - Projeto e Analise de Algoritmos (pos)
  
• 2019.2 - Estruturas Discretas
  
• 2019.1 - Analise de Algoritmos
  
• 2019.1 - Algoritmos e Incerteza (pos)
  
• 2018.2 - Analise de Algoritmos
  
• 2018.2 - Algoritmos e Incerteza (pos)
  
• 2018.1 - Analise de Algoritmos
  
• 2018.1 - Projeto e Analise de Algoritmos (pos)
  
• 2017.2 - Estruturas Discretas
  
• 2017.2 - Projeto e Analise de Algoritmos (pos)
  
• 2017.1 - Analise de Algoritmos
  
• 2017.1 - Algoritmos e Incerteza (pos)
  
• 2016.1 - Analise de Algoritmos
  
• 2016.1 - Projeto e Analise de Algoritmos (pos)
  

Publications

• Lipschitz Selectors may not Yield Competitive Algorithms for Convex Body Chasing
  With C.J. Argue and Anupam Gupta
  
  
• Lower Bounds on the Size of General Branch-and-Bound Trees
  With Santanu Dey and Yatharth Dubey
  
  
• Solving row-sparse principal component analysis via convex integer programs
  With Santanu Dey and Guanyi Wang
  
  
• Online Advertiser-Centric Budget Allocation
  With Eduardo Cesar Coutinho
  
  
• Curvature of Feasible Sets in Offline and Online Optimization
  
  
• Sparse PSD approximation of the PSD cone
  Accepted to Math Programming
  With Grigoriy Blekherman, Santanu Dey, and Shengding Sun
  
  
• Branch-and-Bound Solves Random Binary IPs in Polytime
  SODA 2021
  With Santanu Dey and Yatharth Dubey
  
  
• Robust Algorithms for Online Convex Problems via Primal-Dual
  SODA 2021
  
  
• Teaching with Limited Information on the Learner's Behaviour
  ICML 2020
  With Ferdinando Cicalese, Sergio Freitas, and Eduardo Laber
  
  
• Knapsack Secretary with Bursty Adversary
  ICALP 2020
  With Thomas Kesselheim
  
  
• Lower bounds on the lattice-free rank for packing and covering integer programs
  SIAM Journal on Optimization, 29 (1), 2019
  With Merve Bodur, Alberto del Pia, and Santanu Dey
  
  
• k-Servers with a Smile: Online Algorithms via Projections / presentation
  SODA 2019
  With Niv Buchbinder, Anupam Gupta, and Seffi Naor
  
  
• Stochastic lp Load Balancing and Moment Problems via the L-Function Method / presentation
  SODA 2019.
  
  
• Binary Partitions with Approximate Minimum Impurity
  ICML 2018.
  With Eduardo Laber and Felipe Pereira.
  
  
• Maximizing Profit with Convex Costs in the Random-order Model / presentation
  ICALP 2018.
  With Anupam Gupta and Ruta Mehta
  
  
• Minimal Cut-generating Functions are Nearly Extreme
  Math Programming, 172 (1-2), 2018. Preliminary version in IPCO 2016.
  With Amitabh Basu and Robert Hildebrand.
  
  
• Theoretical challenges towards cutting-plane selection
  Math Programming, 170 (1), 2018.
  With Santanu Dey.
  
  
• Aggregation-based cutting-planes for packing and covering integer programs
  Math Programming, 171 (1-2), 2018.
  With Merve Bodur, Alberto del Pia, Santanu Dey, and Sebastian Pokutta.
  
  
• Improving the Randomization Step in Feasibility Pump / instances and results
  SIAM Journal on Optimization, 28 (1), 2018.
  With Santanu Dey, Andres Iroume, and Domenico Salvagnin.
  
  
• Analysis of Sparse Cutting-planes for Sparse MILPs with Applications to Stochastic MILPs
  Math of Operations Research, 43 (1), 2018.
  With Santanu Dey and Qianyi Wang.
  
  
• Online and Random-order Load Balancing Simultaneously / presentation
  SODA 2017.
  
  
• Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
  Math Programming, 162 (1), 2017.
  With Natashia Boland, Santanu Dey, Thomas Kalinowski, and Fabian Rigterink.
  
  
• Mixed-integer Quadratic Programming is in NP / presentation
  Math Programming, 162 (1), 2017.
  With Alberto del Pia and Santanu Dey.
  
  
• How the Experts Algorithm Can Solve LPs Online / presentation
  Math of Operations Research, 41(4), 2016. Preliminary version in ESA 2014.
  With Anupam Gupta.
  
  
• Capacitated Vehicle Routing with Non-Uniform Speeds / presentation
  Math of Operations Research, 41 (1), 2016. Preliminary version in IPCO 2011.
  With Inge Li Gortz, Viswanath Nagarajan and R. Ravi.
  
  
• Testing Lipschitz Functions on Hypergrid Domain
  Algorithmica, 74, 2016. Preliminary version in RANDOM 2012.
  With Pranjal Awasthi, Madhav Jha, and Sofya Raskhodnikova.
  
  
• Amplification of One-Way Information Complexity via Codes and Noise Sensitivity / presentation
  ICALP 2015.
  With David Woodruff and Grigory Yaroslavtsev.
  
  
• Limitations of Local Filters of Lipschitz and Monotone Functions / presentation
  Transactions on Computation Theory, 7, 2015. Preliminary version in RANDOM 2012.
  With Pranjal Awasthi, Madhav Jha, and Sofya Raskhodnikova.
  
  
• Approximating Polyhedra with Sparse Inequalities / presentation
  Math Programming, 154, 2015. Preliminary version in IPCO 2014.
  With Santanu Dey and Qianyi Wang.
  
  
• Some Lower Bounds on Sparse Outer Approximations of Polytopes / presentation
  Operations Research Letters, 43 (3), 2015.
  With Santanu Dey and Andres Iroume.
  
  
• Characterization of the Split Closure by Cut Generating functions via Geometric Lifting
  European Journal of Operations Research, 243 (3), 2015.
  With Amitabh Basu.
  
  
• On the Relative Strength of Different Generalizations of Split Cuts / presentation
  Discrete Optimization, 16, 2015.
  With Sanjeeb Dash and Oktay Gunluk.
  
  
• The Geometry of Online Packing Linear Programs / presentation
  Math of Operations Research, 39, 2014. Preliminary version in ICALP 2012.
  With R. Ravi.
  
  
• Improved Approximation Algorithms for the Average-Case Tree Searching Problem
  Algorithmica, 68, 2014. Preliminary version in ICALP 2010 (merged with "On the Complexity of Searching..." below).
  With Ferdinando Cicalese, Tobias Jacobs and Eduardo Laber.
  
  
• Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching / presentation
  SODA 2013.
  With David Woodruff and Grigory Yaroslavtsev.
  
  
• A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation
  SIAM Journal on Optimization, 23, 2013.
  With Amitabh Basu, Robert Hildebrand and Matthias Koeppe.
  
  
• A 3-Slope Theorem for the 2-d Infinite Relaxation / presentation
  Math Programming, 142, 2013.
  With Gerard Cornuejols.
  
  
• Cutting Planes from Two-Term Disjunctions
  Operations Research Letters, 41, 2013.
  With Pierre Bonami, Michelle Conforti, Gerard Cornuejols and Giacomo Zambelli.
  
  
• Lifting Gomory Cuts with Bounded Variables
  Operations Research Letters, 41, 2013.
  With Gerard Cornuejols and Tamas Kis.
  
  
• Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
  FOCS 2011.
  With Anupam Gupta, Ravishankar Krishnaswamy and R. Ravi.
  
  
• A Probabilistic Analysis of the Strength of the Split and Triangle Closures / presentation
  IPCO 2011.
  With Amitabh Basu and Gerard Cornuejols.
  
  
• On the Complexity of Searching in Trees and Partially Ordered Structures
  Theoretical Computer Science, 412, 2011. Preliminary version in ICALP 2010.
  With Ferdinando Cicalese, Tobias Jacobs and Eduardo Laber.
  
  
• Improved Approximations for the Hotlink Assignment Problem
  ACM Transactions on Algorithms, 7(3), 2011.
  With Eduardo Laber.
  
  
• An Approximation Algorithm for Binary Searching in Trees / presentation
  Algorithmica, 59, 2011. Preliminary version in ICALP 2008
  With Eduardo Laber.
  
  
• On Greedy Algorithms for Decision Trees
  ISAAC 2010.
  With Ferdinando Cicalese, Tobias Jacobs and Eduardo Laber.
  
  

Copyright notice: The copyrights of the published papers have been transferred to the respective publishers.