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:
- Canadam, 2015. Speaker at the minisymposium "probabilistic combinatorics".
- Probability on graphs, Eurandom, Mathematics and Computer Science Department, TU Eindhoven.
- The 16th International Conference on Random Structures and Algorithms, Adam Mickiewicz University, Poznan, 2013.
- Weizmann-Warwick Meeting, Eilat, 2012.
- Weizmann-Warwick Workshop, Warwick, 2011.
- Summer Institute on Bounded Rationality, Adaptive Behavior and Cognition group, Max Planck Institute for Human Development, Berlin, 2009.