Daniel Reichman

Hi and welcome to my homepage! I am a Postdoctoral fellow in the

computer science department at Princeton University. My host is

Tom Griffiths. I am also working with Jon Cohen at the Princeton

Neuroscience Institute.

I received my PhD in computer science at the Weizmann

Institute. My adviser was Uri Feige.

Contact: daniel.reichman@gmail.com

Research Interests:

  • Algorithms: Algorithms for pattern recognition. Design and analysis of algorithms with uncertainty/randomness in their data
  • Machine learning
  • Cognitive science

Selected Publications:


  • The computational complexity of training ReLU(s) [PDF]

Pasin Manurangsi and Daniel Reichman

Manuscript.

  • Cognitive model priors for predicting human decisions [PDF]

David Bourgin, Joshua Peterson, Daniel Reichman, Tom Griffiths and Stuart Russell

ICML, 2019.

  • Predicting human decisions with behavioral theories and machine learning [PDF]

Ori Plonsky, Reut Apel, Eyal Ert, Moshe Tennenholtz, David Bourgin,

Joshua C. Peterson, Daniel Reichman, Thomas L. Griffiths, Stuart J. Russell,

Evan C. Carter, James F. Cavanagh, Ido Erev

Submitted.

  • Multitasking capacity: Hardness results and improved constructions [PDF]

Noga Alon, Jonathan Cohen, Tom Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner and Alexander Yu

Submitted.

  • String Matching: Communication, Circuits, and Learning [PDF]

Alexander Golovnev, Mika Göös, Daniel Reichman and Igor Shinkar

Submitted.

  • A graph-theoretic approach to multitasking [PDF]

Noga Alon, Daniel Reichman, Igor Shinkar, Tal Wagner, Sebastian Musslick, Jonathan Cohen, Tom Griffiths, Biswadip Dey

and Kayhan Ozcimder

NIPS, 2017 (oral presentation).

  • The computational challenges of pursuing multiple goals: Network structure of goal systems predicts human

performance [PDF]

David Bourgin, Falk Lieder, Daniel Reichman, Nimrod Talmon and Tom Griffiths

[PDF] Preliminary version: The structure of goal systems predicts human performance CogSci, 2017.

  • Inference in sparse graphs with pairwise measurements and side information [PDF]

Dylan Foster, Daniel Reichman and Karthik Sridharan

AISTATS, 2018.

  • On the non-existence of Nash equilibrium in games with resource-bounded players [PDF]

Joe Halpern, Rafael Pass and Daniel Reichman

Submitted.

  • Deleting and testing forbidden patterns in multi-dimensional arrays [PDF]

Omri Ben Eliezer, Simon Korman and Daniel Reichman

ICALP, 2017 (Track A).

  • Robust algorithms for noisy minor-free and bounded treewidth graphs [PDF]

Nikhil Bansal, Daniel Reichman and Seeun William Umboh

SODA, 2017.

  • On percolation and NP-hardness [PDF]

Huck Bennet, Daniel Reichman and Igor Shinkar

Random Structures and Algorithms, 2018. Preliminary version: ICALP, 2016 (Track A).

  • Contagious sets in dense graphs [PDF]

Daniel Freund, Matthias Poloczek and Daniel Reichman

European Journal of Combinatorics, 2018.

  • On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian

tensors [PDF]

Andrea Montanari, Daniel Reichman and Ofer Zeitouni.

IEEE Transactions of information theory, 2017. Preliminary version: NIPS, 2015.

  • Contagious sets in random graphs [PDF]

Uriel Feige, Michael Krivelevich and Daniel Reichman

Annals of Applied Probability, 2017. Video

  • Contagious sets in expanders [PDF]

Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich and Daniel Reichman

SODA, 2015.

  • On giant components and treewidth in the layers model [PDF]

Uriel Feige, Jonathan Hermon and Daniel Reichman

Random Structures and Algorithms, 2015.

  • Smoothed analysis in connected graphs [PDF]

Michael Krivelevich, Daniel Reichman and Wojciech Samotij

SIAM Journal of Discrete Mathematics, 2015. Preliminary version: RANDOM, 2014.

  • FAsT-Match: Fast Affine Template Matching [PDF]

Simon Korman, Daniel Reichman, Gilad Tsur and Shai Avidan

International Journal of Computer Vision, 2017. Preliminary version: CVPR, 2013.

  • Recoverable values for independent sets [PDF]

Uriel Feige and Daniel Reichman

Random Structures and Algorithms, 2013. Preliminary version: ICALP, 2011.

  • New bounds for contagious sets

Daniel Reichman

Discrete Mathematics, 2012

  • Approximating maximum satisfiable subsystems of linear equations of bounded width [PDF]

Zeev Nutov and Daniel Reichman

Information Processing Letters, 2008.

  • On the hardness of approximating Max-Satisfy

Uriel Feige and Daniel Reichman

Information Processing Letters, 2006.

  • On systems of linear equations with two variables per equation

Uriel Feige and Daniel Reichman

APPROX, 2004.

Selected Talks:

  • Princeton Discrete math seminar, Contagious sets: known results and open questions. April 2019.
  • Columbia CS theory seminar, Non-Uniform and Learning Algorithms for String Matching Problems. December 2018.
  • Princeton CS theory seminar, A Graph Theoretic Approach for Multitasking. October, 2017.
  • Redwood Center for Theoretical Neuroscience, Redwood-Griffiths Summit, A Graph Theoretic Approach for Multitasking. April, 2017.
  • UCSD, CS theory seminar, On Percolation and NP-hardness. September, 2016.
  • Random Instances and Phase Transitions, Contagious Sets in Random Graphs. May, 2016.
  • Sublinear Algorithms Workshop, Testing pattern freeness. January, 2016.
  • University of Chicago, CS theory seminar, The layers model, with applications. November, 2013.
  • Gerogia Tech, Combinatorics seminar, Smoothed analysis on connected graphs. November, 2013.
  • Microsoft Research, SVC, theory seminar, Smoothed analysis on connected graphs. November, 2013.
  • Princeton University, Theory lunch, The layers model, with applications. November, 2013.
  • Weizmann Institute, CS theory seminar, Smoothed analysis on connected graphs. October 2013
  • Cornell University, CS theory seminar, Contagious sets in expanders. May, 2013.
  • Harvard University, Theory of computation seminar, Contagious sets in expanders. May, 2013.
  • Freie University, Berlin, Combinatorics seminar, Random permutations and random subgraphs. April 2012.
  • Max Planck Institute for Human Development, Berlin, Adaptive Behavior and Cognition, Group seminar, Complexity: A theoretical analysis with applications to self regulation and goal pursuit. April 2012.

Events: