Krzysztof Choromanski

Adjunct Professor

Krzysztof Choromanski works on several fields of machine learning & Robotics stretching from Monte Carlo methods for kernels through deep neural networks to reinforcement learning (RL), quadruped locomotion and vision-based Robotics. He has developed several Monte Carlo algorithms (e.g. the so-called Orthogonal Monte Carlo algorithms) for scaling up kernel methods, compact neural network architectures encoding RL policies and more recently - first classes of Transformers architectures (Performers) with linear space and time complexity that are fully compatible with regular softmax-attention Transformers. Krzysztof is also an expert in structural and random graph theory and applies in his research several techniques from combinatorics and discrete mathematics.

Krzysztof is interested in particular in integrating new Quasi Monte Carlo methods based on geometrically coupled samples (e.g. orthogonal ensembles) to several machine learning algorithms (such as random feature map techniques, Evolutionary Search (ES) optimization and attention-based architectures) for: accuracy gains (variance reduction and sharper concentration results), sample-complexity reduction, training/inference speedups and memory footprint compactification of the learned models. He also focuses on the role of memory in deep neural network models (lifelong learning in Robotics), designing new attention-based architectures, with attention applied in both: temporal and spatial dimensions (in the latter setting for efficient vision processing in RL producing interpretable compact representations and reducing the overall number of trainable parameters). Krzysztof developed a large class of  ES optimization techniques to train reinforcement learning agents leveraging such tools as: the aforementioned quasi Monte Carlo algorithms, guided ES techniques (e.g. the emerging theory of active subspaces), Determinantal Point Processes (for enhanced exploration in ES optimization and population-based optimization techniques), the theory of low displacement rank matrices (to propose expressive compact neural network based policy-models), LP decoding (for efficient gradients’ retrieval in the adversarial noise framework) and more.

Krzysztof’s research style is characterized by developing deeply theory-grounded algorithms, often admitting rigorous theoretical analysis (even for the fields that are of traditionally empirical flavor such as deep neural networks).

Krzysztof obtained his Ph.D in Operations Research in 2013 from the IEOR Department at Columbia University. Prior to joining Columbia, he got his double master degree in mathematics and computer science from the University of Warsaw in Poland. His Ph.D dissertation concerns structural properties of graphs with forbidden patterns and the celebrated Erdos-Hajnal Conjecture (open since 1977). Krzysztof’s impact in this field involves most results for the directed version of the Conjecture (in particular first infinite families of prime tournaments satisfying the Conjecture). After graduating from Columbia in 2013, Krzysztof joined Google Research. Then, in 2016 he became a member of Google Brain Robotics New York. Krzysztof plays piano since the age of seven. His Erdos number is 2 and his Chopin number (the shortest directed path to Chopin with edges encoding student-teacher relationship) is 5. Krzysztof holds an adjunct assistant professorship position at the IEOR Department of Columbia University for several years now, teaching classes on both: basic machine learning/data mining techniques as well as advanced Ph.D topics. He is co-authoring with his students from Columbia University several papers published in top-tier machine learning conferences (such as: NeurIPS, ICML and AISTATS).


  • research internship at Google in Mountain View on distributed optimization algorithms for graphs (2012)
  • several invited talks on machine learning and graph theory (e.g. CVPR 2019: "The Unreasonable Effectiveness of ES: A Tale of Hadamard-Minitaurs, Toeplitz-Walkers and Wasserstein-Explorers", Columbia University 2019, University Paris-Dauphine 2017, City University of New York 2014, Brown University 2014, Charles University in Prague 2013, McGill University 2013, Yale University 2012, Rutgers University 2012, Princeton University 2012, Alfred Renyi Institute in Budapest 2011, Emory University 2011)
  • two invited Google Tech talks, in particular: “New classes of tournaments satisfying the Erdos-Hajnal conjecture” (2012)


  • research scientist at Google Brain Robotics (2016 - present)
  • adjunct assistant professor at Columbia University, IEOR Department (2016 - present)
  • research scientist at Google Research (2013 - 2016)


  • In Reviewing Boards of: Journal of Combinatorial Theory Series B, Journal of Graph Theory, Journal of Discrete Mathematics, Conference on Neural Information Processing Systems (NIPS/NeurIPS), International Conference on Machine Learning (ICML), Conference on Artificial Intelligence and Statistics (AISTATS), Symposium on Foundations of Computer Science (FOCS), ACM-SIAM Symposium on Discrete Algorithms (SODA) and more


  • second prize for the best student paper ("Analysis of the random graph evolution with complex vertex structure on the example of Complex Preferential Attachment Scheme Model") from the theory of probability and applications of mathematics organized by Polish Mathematical Society, 2008
  • Polish Minister of Science Scholarship for Achievements in Science, 2006-2006
  • bronze medal at the 35th International Physics Olympiad in Pohang, South Korea, 2004
  • gold medal at Polish Physics Olympiad, 2004
  • silver medal at Polish Mathematical Olympiad, 2004
  • winner of Physics Competition organized by Warsaw University of Technology, 2004
  • gold medal at AUSTROPOL Mathematical Competition, Graz, Austria, 2003
  • bronze medal at Polish Mathematical Olympiad, 2003
  • Polish Prime Minister Scholarship for Achievements in Science, 2002-2004