{"id":28,"date":"2021-08-01T10:02:04","date_gmt":"2021-08-01T10:02:04","guid":{"rendered":"http:\/\/www.eng.biu.ac.il\/sheffeo1\/?page_id=28"},"modified":"2021-08-01T13:25:17","modified_gmt":"2021-08-01T13:25:17","slug":"research","status":"publish","type":"page","link":"https:\/\/www.eng.biu.ac.il\/sheffeo1\/research\/","title":{"rendered":"Research"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\"><strong>Students<\/strong><\/h2>\n\n\n\n<p>List of past and current advisees<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Bar Mahpud (MEng, 2020-)<\/li><li>Refael Kohen (MEng, 2019-)<\/li><li>Yue (Anna) Gao (MSc, 2018-21)<\/li><li>Touqir Sajed (MSc, 2017-9)<\/li><\/ul>\n\n\n\n<p>If you think you might be interested in working with me, please read my<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>(rather long) <a href=\"http:\/\/www.eng.biu.ac.il\/sheffeo1\/files\/2021\/07\/If-you-are-considering-grad-school.pdf\">advice for a General CS\/Eng Students<\/a>, about applications, expectations, the life of a grad student and the importance of choosing the best advisor for you. (Written while at University of Alberta)<\/li><li>(shorter) <a href=\"http:\/\/www.eng.biu.ac.il\/sheffeo1\/files\/2021\/07\/What-Am-I-Looking-For-in-a-Prospective-Student.pdf\">advice for anyone considering me as an advisor<\/a>, regarding my field of research, my expectations from students, and how to contact me.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Publications<\/h2>\n\n\n\n<ul>\n<li>Private Approximations of a Convex Hull in Low Dimensions, Yue Gao and Or Sheffet, ITC 2021.<br><a href=\"http:\/\/arxiv.org\/abs\/2007.08110\">Paper<\/a>.<br><br><\/li>\n<li>Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme, <a href=\"http:\/\/knikolakakis.org\/\">Konstantinos Nikolakakis<\/a>, <a href=\"http:\/\/www.dkalogerias.org\/\">Dionysios Kalogerias<\/a>, Or Sheffet and <a href=\"http:\/\/www.ece.rutgers.edu\/~asarwate\/\">Anand Sarwate<\/a>, IEEE Journal on Selected Areas in Information Theory, Vol. 2 No. 2. 2021.<br><a href=\"http:\/\/arxiv.org\/abs\/2006.06792\">Paper<\/a>.<br><br><\/li>\n<li>The Power of Synergy in Differential Privacy: Combining a Small Curator with Local Randomizers, <a href=\"http:\/\/www.cs.bgu.ac.il\/~beimel\/\">Amos Beimel<\/a>, <a href=\"http:\/\/www.korolova.com\/\">Aleksandra Korolova<\/a>, <a href=\"http:\/\/people.cs.georgetown.edu\/~kobbi\/\">Kobbi Nissim<\/a>, Or Sheffet and <a href=\"http:\/\/www.uri.co.il\">Uri Stemmer<\/a>, ITC 2020. <br><a href=\"http:\/\/arxiv.org\/abs\/1912.08951\">Paper<\/a>.<br><br><\/li>\n<li>Private k-Means Clustering with Stability Assumptions, Moshe Shechner, Or Sheffet, <a href=\"http:\/\/www.uri.co.il\">Uri Stemmer<\/a>, AISTATS 2020. <br><a href=\"http:\/\/proceedings.mlr.press\/v108\/shechner20a\/shechner20a.pdf\">Paper<\/a>.<br><br><\/li>\n<li>Differentially Private Algorithms for Learning Mixtures of Separated Gaussians, <a href=\"http:\/\/www.gautamkamath.com\/\">Gautam Kamath<\/a>, Or Sheffet, <a href=\"http:\/\/www.ccs.neu.edu\/home\/vikrantsinghal\/\">Vikrant Singhal<\/a> and <a href=\"http:\/\/www.ccs.neu.edu\/home\/jullman\/\">Jonathan Ullman<\/a>, NeurIPS 2019.<br><a href=\"http:\/\/arxiv.org\/abs\/1909.03951\">Paper<\/a>.<br><br><\/li>\n<li>Locally Private Confidence Intervals: Z-test and Tight Confidence Intervals, <a href=\"http:\/\/www.acsu.buffalo.edu\/~gaboardi\/\">Marco Gaboardi<\/a>, <a href=\"https:\/\/www.math.upenn.edu\/~ryrogers\/\">Ryan Rogers<\/a> and Or Sheffet, AISTATS 2019.<br><a href=\"http:\/\/arxiv.org\/pdf\/1810.08054.pdf\">Paper<\/a>.<br><br><\/li>\n<li>Old Techniques In Private Linear Regression, Or Sheffet, ALT 2019.<br>(Based on \u201cPrivate Approximations of the 2nd-Moment Matrix Using Existing Techniques in Linear Regression\u201d in NIPS 2015 Workshop on Learning and Privacy.)<br><a href=\"http:\/\/arxiv.org\/pdf\/1507.00056\">Paper<\/a>.<br><br><\/li>\n<li>Differentially Private Contextual Linear Bandits, <a href=\"http:\/\/sites.ualberta.ca\/~rshariff\/\">Roshan Shariff<\/a> and Or Sheffet, NIPS 2018.<br><a href=\"http:\/\/arxiv.org\/abs\/1810.00068\">Paper<\/a>.<br><br><\/li>\n<li>Locally Private Hypothesis Testing, Or Sheffet, ICML 2018.<br><a href=\"http:\/\/arxiv.org\/abs\/1802.03441\">Paper<\/a>.<br><br><\/li>\n<li>Differentially Private Ordinary Least Squares, Or Sheffet, ICML 2017.<br>(Based on \u201cDifferentially Private Ordinary Least Squares: <em>t<\/em>-Values, Confidence Intervals and Rejecting Null-Hypotheses\u201d in TPDP 2016.)<br><a href=\"\/Users\/orshe\/Google%20Drive\/Documents(CMU)\/www\/OLS.html\">Paper<\/a>.<br><br><\/li>\n<li>Privacy Games, <a href=\"http:\/\/yiling.seas.harvard.edu\/\">Yiling Chen<\/a>, Or Sheffet and <a href=\"http:\/\/people.seas.harvard.edu\/~salil\">Salil Vadhan<\/a>, WINE 2014 &amp; ACM Transaction on Economics and Computation (TEAC), Vol. 8 No.2,<br><a href=\"\/Users\/orshe\/Google%20Drive\/Documents(CMU)\/www\/privacygames.html\">Paper<\/a>.<br><br><\/li>\n<li>Learning Mixture of Ranking Models, <a href=\"http:\/\/www.cs.princeton.edu\/~pawashti\/\">Pranjal Awasthi<\/a>, <a href=\"http:\/\/www.cs.cmu.edu\/~avrim\">Avrim Blum<\/a>, Or Sheffet and <a href=\"http:\/\/www.cs.princeton.edu\/~aravindv\/\">Aravindan Vijayaraghavan<\/a>, NIPS 2014.<br><a href=\"http:\/\/www.eng.biu.ac.il\/sheffeo1\/files\/2021\/07\/Mallows.pdf\">Paper<\/a>.<br>Based on \u201cLearning Mixture of Mallows Models\u201d, in Workship on Spectral Learning, NIPS 2013.<br><br><\/li>\n<li>Optimizing Password Composition Policies, <a href=\"http:\/\/www.andrew.cmu.edu\/user\/jblocki\/\">Jeremiah Blocki<\/a>, <a href=\"http:\/\/www.salsite.com\/cv\/\">Saranga Komanduri<\/a>, <a href=\"http:\/\/www.cs.cmu.edu\/~arielpro\/\">Ariel Procaccia<\/a> and Or Sheffet, EC 2013.<br><a href=\"http:\/\/www.eng.biu.ac.il\/sheffeo1\/files\/2021\/07\/ec-passwords.pdf\">Paper<\/a>.<br><br><\/li>\n<li>Differentially Private Analysis of Social Networks via Restricted Sensitivity, <a href=\"http:\/\/www.andrew.cmu.edu\/user\/jblocki\/\">Jeremiah Blocki<\/a>, <a href=\"http:\/\/www.cs.cmu.edu\/~avrim\">Avrim Blum<\/a>, <a href=\"http:\/\/www.andrew.cmu.edu\/user\/danupam\/\">Anupam Datta<\/a> and Or Sheffet, ITCS 2013.<br><a href=\"http:\/\/www.eng.biu.ac.il\/sheffeo1\/files\/2021\/07\/itcs_main.pdf\">Paper<\/a>.<br><br><\/li>\n<li>The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy, <a href=\"http:\/\/www.andrew.cmu.edu\/user\/jblocki\/\">Jeremiah Blocki<\/a>, <a href=\"http:\/\/www.cs.cmu.edu\/~avrim\">Avrim Blum<\/a>, <a href=\"http:\/\/www.andrew.cmu.edu\/user\/danupam\/\">Anupam Datta<\/a> and Or Sheffet, FOCS 2012.<br><a href=\"\/Users\/orshe\/Google%20Drive\/Documents(CMU)\/www\/jlprivacy.html\">Paper<\/a>.<br><br><\/li>\n<li>Additive Approximation for Near-Perfect Phylogeny Construction, <a href=\"http:\/\/www.cs.princeton.edu\/~pawasthi\">Pranjal Awasthi<\/a>, <a href=\"http:\/\/www.cs.cmu.edu\/~avrim\">Avrim Blum<\/a>, <a href=\"http:\/\/www.cs.cmu.edu\/~jamiemmt\/\">Jamie Morgenstern<\/a> and Or Sheffet, APPROX-RANDOM 2012.<br><a href=\"http:\/\/arxiv.org\/abs\/1206.3334\">Paper<\/a>.<br><br><\/li>\n<li>Improved Spectral Norm Bounds for Clustering, <a href=\"http:\/\/www.cs.princeton.edu\/~pawasthi\">Pranjal Awasthi<\/a> and Or Sheffet, APPROX-RANDOM 2012.<br><a href=\"http:\/\/arxiv.org\/abs\/1206.3204\">Paper<\/a>.<br><br><\/li>\n<li>Predicting Preference Flips in Commerce Search, <a href=\"http:\/\/research.microsoft.com\/en-us\/people\/saieong\/\">Samuel Ieong<\/a>, <a href=\"http:\/\/research.microsoft.com\/en-us\/people\/ninam\/\">Nina Mishra<\/a> and Or Sheffet, ICML 2012.<br><a href=\"http:\/\/www.eng.biu.ac.il\/sheffeo1\/files\/2021\/07\/RSM.pdf\">Paper<\/a>.<br><br><\/li>\n<li>Optimal Choice Functions: A Utilitarian View, <a href=\"http:\/\/www.cs.toronto.edu\/~cebly\/\">Craig Boutilier<\/a>, <a href=\"http:\/\/www.ceid.upatras.gr\/caragian\/\">Ioannis Caragiannis<\/a>, Simi Haber, <a href=\"http:\/\/www.cs.toronto.edu\/~tl\/Tylers_Homepage\/About_Me.html\">Tyler Lu<\/a><a>, <\/a><a href=\"http:\/\/www.cs.cmu.edu\/~arielpro\/\">Ariel Procaccia<\/a> and Or Sheffet, EC 2012.<br><a href=\"\/Users\/orshe\/Google%20Drive\/Documents(CMU)\/www\/Optimal_choice_function.html\">Paper<\/a>.<br><br><\/li>\n<li>Send Mixed Signals \u2012 Earn More, Work Less, <a href=\"http:\/\/www.daimi.au.dk\/~bromille\/\">Peter Bro Miltersen<\/a> and Or Sheffet, EC 2012.<br><a href=\"http:\/\/www.eng.biu.ac.il\/sheffeo1\/files\/2021\/07\/mixed-signals-auction.pdf\">Paper<\/a>.<br><br><\/li>\n<li>Center-based Clustering under Perturbation Stability, <a href=\"http:\/\/www.cs.princeton.edu\/~pawasthi\">Pranjal Awasthi<\/a>, <a href=\"http:\/\/www.cs.cmu.edu\/~avrim\">Avrim Blum<\/a> and Or Sheffet, Information Processing Letters, 112(1-2).<br><a href=\"http:\/\/www.eng.biu.ac.il\/sheffeo1\/files\/2021\/08\/clustering-IPL.pdf\">Paper<\/a>.<br><br><\/li>\n<li>Stability Yields a PTAS for <em>k<\/em>-Median and <em>k<\/em>-Means, <a href=\"http:\/\/www.cs.princeton.edu\/~pawasthi\">Pranjal Awasthi<\/a>, <a href=\"http:\/\/www.cs.cmu.edu\/~avrim\">Avrim Blum<\/a> and Or Sheffet, FOCS 2010.<br><a href=\"http:\/\/www.eng.biu.ac.il\/sheffeo1\/files\/2021\/07\/PTAS-08-06-10-FOCS-long.pdf\">Paper<\/a>.<br><br><\/li>\n<li>On Nash-Eqilibria of Approximation-Stable Games, <a href=\"http:\/\/www.cs.princeton.edu\/~pawasthi\">Pranjal Awasthi<\/a>, <a href=\"http:\/\/www.cc.gatech.edu\/~ninamf\/\">Nina Balcan<\/a>, <a href=\"http:\/\/www.cs.cmu.edu\/~avrim\">Avrim Blum<\/a>, Or Sheffet and <a href=\"http:\/\/www.cc.gatech.edu\/~vempala\/\">Santosh Vempala<\/a>. SAGT 2010.<br><a href=\"http:\/\/www.cs.cmu.edu\/~avrim\/Papers\/EpsNash.pdf\">Paper<\/a>. <a href=\"http:\/\/www.eng.biu.ac.il\/sheffeo1\/files\/2021\/07\/nash-journal-3.pdf\">Journal Version<\/a> (for general audience).<br><br><\/li>\n<li>Improved Guarantees for Agnostic Learning of Disjunctions, <a href=\"http:\/\/www.cs.princeton.edu\/~pawasthi\">Pranjal Awasthi<\/a>, <a href=\"http:\/\/www.cs.cmu.edu\/~avrim\">Avrim Blum<\/a> and Or Sheffet, COLT 2010.<br><a href=\"http:\/\/www.cs.cmu.edu\/~avrim\/Papers\/noisyOr.pdf\">Paper<\/a>.<br><br><\/li>\n<li>On the Randomness Complexity of Property Testing, <a href=\"http:\/\/www.wisdom.weizmann.ac.il\/~oded\/\">Oded Goldreich<\/a> and Or Sheffet, Journal of Computational Complexity 19 (2), 2010. Originally appeared in Approx\/Random 2007.<br><a href=\"http:\/\/www.wisdom.weizmann.ac.il\/~oded\/p_ors.html\">Oded's page<\/a>.<br>(Based on my M.Sc. thesis: \u201cReducing the Randomness Complexity of Property Testing, with an Emphasis on Testing Bipartiteness\u201d.)<br><br><\/li>\n<li>Graph Coloring with No Large Monochromatic Components, <a href=\"http:\/\/www.cs.huji.ac.il\/~nati\/\">Nathan Linial<\/a>, <a href=\"http:\/\/kam.mff.cuni.cz\/~matousek\/\">Jiri Matousek<\/a>, Or Sheffet and <a href=\"http:\/\/www.cs.sfu.ca\/~tardos\/\">Gabor Tardos<\/a>, Journal of Combinatorial Theory Series B 17 (4), 2008. Originally appeared in Eurocomb 2007.<br><a href=\"http:\/\/www.cs.huji.ac.il\/~nati\/PAPERS\/or_sheffet.pdf\">Paper<\/a>.<br>(Based on my \u201cAmirim\u201d Honors program final project: \u201cOn Ramsey Type Problems in Graphs, and the Largest Monochromatic Connected Component in a 2-Edge-Coloring of a Graph.\u201d)<br><br><\/li>\n<\/ul>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Students List of past and current advisees Bar Mahpud (MEng, 2020-) Refael Kohen (MEng, 2019-) Yue (Anna) Gao (MSc, 2018-21) Touqir Sajed (MSc, 2017-9) If you think you might be interested in working with me, please read my (rather long) advice for a General CS\/Eng Students, about applications, expectations, the life of a grad student &hellip; <a href=\"https:\/\/www.eng.biu.ac.il\/sheffeo1\/research\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Research<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":81,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-28","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.eng.biu.ac.il\/sheffeo1\/wp-json\/wp\/v2\/pages\/28"}],"collection":[{"href":"https:\/\/www.eng.biu.ac.il\/sheffeo1\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.eng.biu.ac.il\/sheffeo1\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.eng.biu.ac.il\/sheffeo1\/wp-json\/wp\/v2\/users\/81"}],"replies":[{"embeddable":true,"href":"https:\/\/www.eng.biu.ac.il\/sheffeo1\/wp-json\/wp\/v2\/comments?post=28"}],"version-history":[{"count":17,"href":"https:\/\/www.eng.biu.ac.il\/sheffeo1\/wp-json\/wp\/v2\/pages\/28\/revisions"}],"predecessor-version":[{"id":77,"href":"https:\/\/www.eng.biu.ac.il\/sheffeo1\/wp-json\/wp\/v2\/pages\/28\/revisions\/77"}],"wp:attachment":[{"href":"https:\/\/www.eng.biu.ac.il\/sheffeo1\/wp-json\/wp\/v2\/media?parent=28"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}