Algorithms and Theory       

links

Algorithms and Theory - Events


New York Area Theory Day

The New York Area Theory Day is a semi-annual conference coorganized by IBM Research, Columbia University, and New York University. It aims to bring together people in the New York Metropolitan area for one day of interaction and discussion.  The Theory Day features several presentations by leading theoretical computer scientists about state-of-the-art advances in various areas. Some presentations give a survey of the latest advances in some area, while others may concentrate on a particular result. The meeting is free and open to everyone; in particular, students are encouraged to attend.

Please check the webpages at Columbia and NYU for up to date information. The next Theory Day will take place on December 1, 2017 at New York University.

Watson Theory Lunch

IP/AP for Lunch is a weekly seminar organized by the Algorithms, Mathematical Programming and Stochastic Processes groups at IBM T.J. Watson Research Center. The seminars are usually every Wednesday from 12:00 to 1:00. IP = Integer Programming and AP = Applied Probability, both are liberally interpreted.

Talks (2014)

  • Jan 10: Shahar Chen, Technion, Competitive Analysis via Regularization
  • Jan 22: Amitabh Basu, JHU, Recent Progress in Gomory and Johnson's "Infinite Group'' Problem
  • Jan 28: Piotr Sankowski, University of Warsaw, Matching Algorithms
  • Feb 6: Aaron Bernstein, Columbia University, Dynamic Approximate Shortest Paths
  • Feb 12: Vahid Liaghat, University of Maryland, Online Node-weighted Steiner Forest and Extensions
  • Feb 19: Ilias Diakonikolas, University of Edinburgh, Learning Sums of Independent Integer Random Variables
  • Feb 20: Nicolas Bonifas, IBM France and LIX, A relationship between geometrical and combinatorial distance in the Cayley graph of a lattice
  • Feb 25: Krzysztof Onak, IBM, Parallel Algorithms for Geometric Graph Problems
  • Mar 11: Alberto DelPia, IBM, Integer quadratic programming in the plane
  • Apr 2: Hassan Mansour, Mitsubishi Research, Factorized Robust Matrix Completion
  • Apr 14: Debmalya Panigrahi, Duke University, Online Node-weighted Network Design
  • May 14: Haim Avron, IBM, Faster Subset Selection for Matrices and Applications
  • May 19: Michael Kapralov, MIT, Sample-Optimal Fourier Sampling in Any Constant Dimension
  • Jun 4: Janardhan Kulkarni, Duke University, Non-clairvoyant Scheduling to Minimize Weighted Flow-time
  • Jun 12: Maria Chudnovsky, Columbia University, Perfection and Beyond
  • Jun 27: Michael Katz, IBM (Israel), Symmetry Breaking in Heuristic Search Planning
  • Jul 16: Thomas Rothvoss, University of Washington, The matching polytope has exponential extension complexity
  • Jul 28: Giacomo Nannicini, Singapore University of Technology and Design, What does a good Gomory cut look like?
  • Sep 11: Sudipto Guha, University of Pennsylvania, Through the Sketching Lens: Alice (and Bob) in Combinatorial Optimization
  • Sep 17: Michael Kapralov, IBM, Approximating Matching Size from Random Streams
  • Oct 17: Ilias Diakonikolas, University of Edinburgh, Algorithmic Approaches to Statistical Estimation under Structural Constraints
  • Nov 3: Pierre-Louis Poirion, LIX Ecole Polytechnique, Flattening Inequalities for Binary Linear Programs
  • Nov 6: Sonia Toubaline, LIX Ecole Polytechnique, Optimal location problem for a complete observability of an electrical distribution network
  • Nov 19: Clément Canonne, Columbia University, Communication with Imperfectly Shared Randomness
  • Dec 3: Juan Pablo Vielma, MIT, Extended Formulations for Quadratic Mixed Integer Programming
  • Dec 10: Richard Peng, MIT, L_p Row Sampling by Lewis Weights
  • Dec 17: Diego Moran, Virginia Tech, A Strong dual for conic mixed-integer linear programs

Talks in 2013

  • Jan 30: Leo Liberti, IBM, Distance constraints in Euclidean geometry
  • Feb 6: Samim Ghamami, UC Berkeley, Efficient Monte Carlo Counterparty Credit Risk Pricing and Measurement
  • Feb 7: Raphael Jungers, University of Louvain, Joint spectral characteristics: a tale of three disciplines
  • Feb 11: Stephan Held, University of Bonn, Shallow-Light Steiner Arborescences with Vertex Delays
  • Feb 13: Aleksandar Nikolov, Rutgers University, The Geometry of Differential Privacy: the Approximate and Sparse Cases
  • Feb 20: Joline Uichanco, MIT, Business analytics for flexible resource allocation under random emergencies
  • Feb 27: Kanat Tangwongsan, IBM, Achieving Parallelism By Being Approximately Greedy
  • Mar 6: Jelani Nelson, Princeton University, OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
  • Mar 13: Manish Jain, University of Southern California, Game-Theoretic Allocation of Limited Resources: Applications to Security Domains
  • Mar 14: Sim Segal, SimErgy Consulting, Value-Based Enterprise Risk Management
  • Mar 20: Wenqiang Xiao, NYU, Global Sourcing Decisions for a Multinational Firm With Foreign Tax Credit Planning
  • Mar 29: Jose Blanchet, Columbia University, A Markov Chain Substitution Scheme for Approximation of Choice Models
  • Apr 1: Mohsen Golalikhani, Quintiq Inc., Sales Force Optimization in Industrial Gas Industry
  • Apr 2: Jun Chi Yan, IBM Research-China, From pair graph matching to multiple ones: formulation and algorithm
  • Apr 3: Shuangchi He, National University of Singapore, A one-dimensional diffusion model for overloaded queues with customer abandonment
  • Apr 8: Brendon Juba, Harvard University, Efficient reasoning in PAC Semantics
  • Apr 10: Shi Li, Princeton University, Approximating k-Median via Pseudo-Approximation
  • Apr 12: Christian Gromoll, University of Virginia, Compactness in the M_1-topology on measure-valued Skorokhod space
  • Apr 18: Joline Uichanco, MIT, Business analytics for flexible resource allocation under random emergencies
  • Apr 22: Carlile Lavor, University of Campinas, A discrete distance geometry approach for calculating protein structure by using nuclear magnetic resonance (NMR) data
  • Apr 24: Mor Armony, NYU Stern, Sizing of Step-Down and Intensive-Care Units in Hospitals
  • May 2: Howard Karloff, AT&T Research, Maximum Entropy Summary Trees
  • May 8: Arnab Bhattacharyya, Rutgers University, An Algebraic Characterization of Testable Boolean CSPs
  • May 14: Eugene Feinberg, Stony Brook University, Partially Observable Markov Decision Processes with General State and Action Spaces
  • May 15: Yared Nigussie, Columbia University, Algorithmic aspects of finite dualities
  • May 21: Mohammad Ghavamzadeh, INRIA, Two Adaptive Resource Allocation Problems
  • May 29: Thomas Rothvoss, MIT, Approximating Bin Packing within O(log OPT * log log OPT) bins
  • June 7: Anthony Wirth, University of Melbourne, Resolving Rooted Triplet Inconsistency by Dissolving Multigraphs
  • June 12: Junyi Zhang, Columbia University, A New Multiple Testing Method for Regression Models
  • June 13: Dmitry Malioutov, IBM Research, Exact Rule Learning via Boolean Compressed Sensing
  • June 21: K Subramani, West Virginia University, A new mathematical programming tool for modeling reactive systems
  • June 28: Linwei Xin, Georgia Tech, Distributionally robust multistage inventory models with moment constraints
  • July 2: Fei Fang, University of Southern California, Dealing With Spatio-Temporal Continuity in Stackelberg Games
  • July 12: Andrew Mc Gregor, U Mass Amherst, Homomorphic Sketches: Shrinking Big Data without Sacrificing Structure
  • July 17: Xiaorui Sun, Columbia University, Multi-Stage Design for Quasipolynomial-Time Isomorphism Testing of Steiner 2-Systems
  • July 19: Giacomo Nannicini, Singapore University of Technology and Design, A practically efficient FPTAS for convex stochastic dynamic programs
  • July 23: Aswin Sankaranarayanan, Carnegie Mellon University, Learning near-isometric linear embeddings
  • July 24: Devendra Desai, Rutgers University, Approximation algorithms for modularity clustering
  • Aug 13: Ravishankar Krishnaswamy, Princeton University, Energy Efficient Multicommodity Routing and Capacitated Network Design
  • Aug 21: Anshul Gandhi, IBM, Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward
  • Sep 17: Parikshit Shah, Philips Research, Convex Optimization for Estimation and Identification: An Atomic Norm Approach
  • Sep 18: Rishi Saket, IBM, Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover
  • Sep 20: Jamol Pender, Columbia University, Stabilizing the Abandonment Probabilities of Jackson Networks
  • Sep 25: Alberto Del pia, IBM, On the diameter of lattice polytopes
  • Sep 27: Patrick Combettes, Marie Curie University, Proximal Splitting Algorithms for Structured Nonsmooth Convex Optimization Problems
  • Oct 1: Rajmohan Rajaraman, Northeastern University, Universal Steiner Trees
  • Oct 2: Will Millhiser, CUNY, Designing Appointment System Templates with Operational Performance Targets
  • Oct 14: Atri Rudra, University of Buffalo, A Tale of Two Join Algorithms
  • Oct 15: Srikanth Jagabathula, NYU Stern, A Two-Stage Model of Consideration Set and Choice: Learning, Revenue Prediction, and Applications
  • Oct 16: Claudia D'Ambrosio, LIX, Ecole Polytechnique, A branch-and-bound method for box constrained integer polynomial optimization
  • Oct 23: Ankit Sharma, CMU, Multiway Cut
  • Oct 30: Joel Wolf, IBM, FlowFlex: Theory and Practice of a Scheduler for Flows of MapReduce Jobs
  • Nov 7: Amirali Ahmadi, IBM, DSOS and SDSOS: More Tractable Alternatives to Sum of Squares (SOS) Programming
  • Nov 8: Manoj Gupta, IIT Delhi, Fully dynamic (1+epsilon) approximate matchings
  • Nov 12: Yao Zhao, Rutgers, Why 787 slips were inevitable?
  • Nov 14: Mahdi Cheraghchi, MIT, Capacity and Constructions of Non-Malleable Codes
  • Nov 14: Chaitanya Bandi, Northwestern University, Robust Optimal Auctions
  • Dec 4: Sebastian Pokutta, Georgia Tech, Common information and Unique Disjointness
  • Dec 18: MohammadTaghi Hajiaghayi, UMD, Contraction and Minor Graph Decomposition and Their Algorithmic Applications

Talks in 2012

  • April 4: Yada Zhu, IBM, Infrastructure Failure Analysis and Condition-based Maintenance Planning
  • April 11: Jian Tan, IBM Research, Delay Tails in MapReduce Scheduling
  • April 25: Lena Granovsky, IBM, Statistical Analysis of DNA Microarrays
  • May 16: Rishi Saket, IBM, Stochastic Vehicle Routing with Recourse
  • May 24: Jugal Garg, IIT Bombay, A Complementary Pivot Algorithm for Markets under Separable, Piecewise-Linear Concave Utilities
  • May 30: Alina Ene, UIUC, Approximation Algorithms for Submodular Multiway Partition
  • June 1: Anastasios Zouzias, University of Toronto, A Matrix Hyperbolic Cosine Algorithm and Applications
  • June 5: Jenn Fohring, University of British Columbia, Optimal experimental design for Magnetotelluric monitoring of CO2 emplacement within depleted reservoirs
  • June 6: Chinmoy Dutta, Northeastern University, Information Spreading in Dynamic Networks
  • June 13: Varun Gupta, Google Research, Optimal Online Stochastic Bin Packing
  • June 14: Richard Peng, CMU, Algorithm Design using Spectral Graph Theory
  • June 21: Aravindan Vijayaraghavan, Princeton University, Approximation Algorithms for Semi-random Graph Partitioning problems
  • June 28: Alex Gittens, CalTech, Several randomized matrix approximation problems
  • July 2: Alina Ene, UIUC, Node-weighted Network Design in Planar Graphs
  • July 11: Lavanya Marla, CMU, Robust Resource Allocation under Uncertainty for Transportation Systems
  • July 12: Xuefeng Gao, Georgia Tech, A Short Survey on Limit Order Book
  • July 13: Mourad Baiou, ISIMA - University of Clermont-Ferrand (France), The Dominating Set Problem
  • July 17: Raghu Pasupathy, Virginia Tech, Simulation Optimization and Optimal Sampling
  • July 18: Shiva Kasiviswanathan, The Power of Linear Reconstruction Attacks
  • July 24: Diego Moran, Georgia Tech, Some Properties of Convex Hulls of Mixed Integer Points contained in General Convex Sets
  • July 26: Maxime Cohen, MIT, Designing Consumer Subsidies for Green Technology Adoption
  • August 1: Jon Lenchner, The Card Game Zero sumZ and its Mathematical Cousins
  • August 6: Ali Koc, Scenario Reduction and Decomposition in Stochastic Programming
  • August 8: Ankur Moitra, Institute for Advanced Study, Provable Algorithms for Nonnegative Matrix Factorization and Learning Topic Models
  • Aug 15: Henry Lam, Boston University, Robust Sensitivity Analysis for Stochastic Systems
  • Aug 30: Josh Reed, NYU, A Fair Policy for the Servers in the G/GI/N Queue with Multiple Server Pools
  • Sept 5: Minghong Lin, Caltech, Energy Efficient Algorithms in Data Centers
  • Sept 20: Rishi Saket, IBM, New and Improved Bounds for the Minimum Set Cover Problem
  • Oct 2: Swastik Kopparty, Rutgers University, The complexity of powering in finite fields
  • Oct 3: Tolga Tezcan, University of Rochester, Staffing and dynamic control of customer service web chat systems with impatient customers
  • Oct 4: Jake Abernethy, University of Pennsylvania, Minimax Option Pricing Meets Black-Scholes in the Limit
  • Oct 10: Nan Liu, Columbia University, Appointment Scheduling under Patient Preference and No-show Behavior
  • Oct 11: Amirali Ahmadi, IBM, Semidefinite Optimization in Analysis of Nonlinear and Uncertain Dynamical Systems
  • Oct 17: Aaron Roth, University of Pennsylvania, Mechanism Design in Large Games: Incentives and Privacy
  • Oct 19: Johannn Kunze von Bischoffshausen, Karlsruhe Institute of Technology, Personal relationship-based assignment of accounts to client reps
  • Oct 19: Tsvi Kopelowitz, Weizmann Institute, Predecessor Queries on Dynamic Subsets of an Ordered List
  • Oct 24: Ravishankar Krishnaswamy, Princeton University, Approximation Algorithms for Stochastic Knapsack and Multi-Armed Bandits
  • Nov 1: Pablo Parrilo, MIT, Representations of convex sets and conic matrix factorizations
  • Nov 2: Eilyan Bitar, Cornell University, Smart Grid Data Integrity Attacks: Characterizations and Countermeasures
  • Nov 6: Ilias Diakonikolos, University of Edinburgh, Learning Poisson Binomial Distributions
  • Nov 7: Georgia Perakis, MIT, Markdown Optimization for a Fashion e-tailer: The Impact of Returning Customers
  • Nov 8: Johannes Schneider, IBM Zurich Research Lab, Hierarchical Clustering: Preservation on Right-Protected Data and Efficient Computation
  • Nov 12: Xi Chen, Columbia University, The Complexity of Non-Monotone Markets
  • Nov 14: Grigory Yaroslavtsev, Pennsylvania State University, Learning and Testing Submodular Functions
  • Nov 16: Raghu Pasupathy, Virginia Tech,On Sampling Rates in Sampling -Controlled Stochastic Approximation
  • Nov 19: Yifan Xu, Binghamton University, First Crossing Times of Compound Poisson Processes with Upper and Lower Boundaries --- M/G/1 Queues with Workload Restriction
  • Nov 21: Levent Kocaga, Yeshiva University, Staffing and Admission Control in an M/M/N+M Queue with an Uncertain Arrival Rate
  • Nov 28: Neil Olver, MIT, Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations
  • Nov 30: Yiwei Chen, MIT, What's On The Table: Revenue Management And The Welfare Gap In The US Airline Industry
  • Dec 4: Baruch Schieber, IBM, The Euclidean k-Supplier Problem
  • Dec 12: Xiaoxuan Zhang, IBM, Incentive Pricing for Lowest Cost Energy Demand Reduction
  • Dec 13: Anupam Gupta, CMU, Sparsest Cut on Bounded Treewidth Graphs
  • Dec 14: Roger Lederman, IBM, Event-Driven Latent Segment Models for Product Portfolio Management
  • Dec 19: Krzysztof Onak, IBM, Superlinear lower bounds for multipass graph processing
  • Dec 20: Leo Liberti, IBM, Symmetry in Mathematical Programming