Kletenik, Devorah

Assistant Professor, Computer and Information Science, Brooklyn College (CUNY)

Academic Appointments:

Associate Professor, Department of Computer and Information Science, Brooklyn College, The City University of New York
Faculty, Computer Science PhD Program, The Graduate Center, The City University of New York


Ph.D. (Computer Science) NYU School of Engineering, USA
M.S. (Computer Science), Polytechnic Institute of NYU, USA

Research Focus:

One of my areas of research focuses on reducing the prediction costs of machine learning classifiers. Our work focuses on application areas where there is a preference for simple and interpretable classifiers, and where it is important to be able to evaluate those classifiers cheaply. A prime example is medical diagnosis, where doctors seek diagnosis rules that are easily interpretable, and whose predictions can be explained to patients. Since diagnoses typically are based on the results of medical tests, which are expensive, reducing prediction cost is important. Our work focuses on a number of simple classification classes (for example, symmetric functions, monotone DNF and CNF, linear threshold functions), in adaptive and non-adaptive settings. Our goal is to give algorithms that output an ordering of the tests to be performed that is within a tight factor of the optimal ordering in terms of the cost of diagnosis.

Selected Publications

Gkenosis, Dimitrios, Nathaniel Grammel, Lisa Hellerstein, and Devorah Kletenik. “The stochastic score classification problem.” In 26th European Symposium on Algorithms, ESA 2018. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018.

Bach, Eric, Jérémie Dusart, Lisa Hellerstein, and Devorah Kletenik. “Submodular goal value of boolean functions.” Discrete Applied Mathematics 238 (2018): 1-13.

Allen, Sarah R., Lisa Hellerstein, Devorah Kletenik, and Tonguç Ünlüyurt. “Evaluation of monotone DNF formulas.” Algorithmica 77, no. 3 (2017): 661-685.

Deshpande, Amol, Lisa Hellerstein, and Devorah Kletenik. “Approximation algorithms for stochastic submodular set cover with applications to boolean function evaluation and min-knapsack.” ACM Transactions on Algorithms (TALG) 12, no. 3 (2016): 1-28.

Grammel, N., Hellerstein, L., Kletenik, D., & Lin, P. (2016, August). Scenario submodular cover. In International Workshop on Approximation and Online Algorithms (pp. 116-128). Springer, Cham.


D. Kletenik, co-PI.
Public Interest Technology University Network
Curricula Design in Public Interest Tech Using OER
09/01/2019 – 08/31/2020

D. Kletenik, PI
Cornell Tech WiTNY
Girls who Play: Developing a Women-Focused Serious Game to Reinforce Programming Concepts
08/01/2019 – 07/31/2020