{"id":249560,"date":"2016-07-07T09:12:49","date_gmt":"2016-07-07T16:12:49","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-event&p=249560"},"modified":"2016-08-18T17:50:16","modified_gmt":"2016-08-19T00:50:16","slug":"theory-colloquium","status":"publish","type":"msr-event","link":"https:\/\/www.microsoft.com\/en-us\/research\/event\/theory-colloquium\/","title":{"rendered":"Theory Colloquium"},"content":{"rendered":"

Microsoft Research New England <\/a>
\nFirst Floor Conference Center
\nOne Memorial Drive, Cambridge, MA<\/p>\n","protected":false},"excerpt":{"rendered":"

The Microsoft Research New England Theory Colloquium focuses on research in the foundational aspects of computing, communication, networks and society.<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_startdate":"","msr_enddate":"","msr_location":"","msr_expirationdate":"","msr_event_recording_link":"","msr_event_link":"","msr_event_link_redirect":false,"msr_event_time":"","msr_hide_region":false,"msr_private_event":true,"footnotes":""},"research-area":[],"msr-region":[197900],"msr-event-type":[197944],"msr-video-type":[],"msr-locale":[268875],"msr-program-audience":[],"msr-post-option":[],"msr-impact-theme":[],"class_list":["post-249560","msr-event","type-msr-event","status-publish","hentry","msr-region-north-america","msr-event-type-hosted-by-microsoft","msr-locale-en_us"],"msr_about":"Microsoft Research New England <\/a>\r\nFirst Floor Conference Center\r\nOne Memorial Drive, Cambridge, MA","tab-content":[{"id":0,"name":"About","content":"The Microsoft Research New England Theory Colloquium focuses on research in the foundational aspects of computing, communication, networks and society. While a wide variety of perspectives have been utilized successfully to improve our understanding of these fields, this colloquium series focuses on research with a mathematical flavor, and aims to bring speakers from a variety of fields to describe their work. The talks are intended to be accessible to young researchers in diverse fields.\r\n\r\nThe Theory Colloquium is now part of the Microsoft Research Colloquium<\/a>."},{"id":1,"name":"Past Speakers","content":"[accordion]\r\n\r\n[panel header=\"Costs and Benefits of Dynamic Trading in a Lemons\u00a0\u00a0A Model of Focusing in Economic Choice\"]\r\n\r\nAdam Szeidl<\/a>, Berkeley Wednesday, June 27 4:00 PM \u2013 5:30 PM | Video<\/a>\r\n\r\nDescription<\/strong>\r\n\r\nWe present a generally applicable theory of focusing based on the hypothesis that a person focuses more on, and hence overweights, attributes in which her options differ more. Our model predicts that the decisionmaker is too prone to choose options with concentrated advantages relative to alternatives, but maximizes utility when the advantages and disadvantages of alternatives are equally concentrated. In intertemporal choice, the decisionmaker exhibits present bias and time inconsistency when---such as in lifestyle choices and other widely invoked applications of hyperbolic discounting---the future costs of current misbehavior are distributed over many dates, and the effects of multiple decisions accumulate. But unlike in previous models, (1) present bias is lower when the costs of current misbehavior are less dispersed, helping to explain why individuals respond more to monetary incentives than to health concerns in harmful consumption; and (2) time inconsistency is lower when the ex-ante choice integrates fewer decisions with accumulating effects. In addition, the agent does not fully maximize welfare even when making decisions ex ante: (3) she commits to too much of an activity---e.g., exercise or work---that is beneficial overall; and (4) makes ``future-biased'' commitments when---such as in preparing for a big event---the benefit of many periods' effort is concentrated in a single goal. URL: http:\/\/www.personal.ceu.hu\/staff\/Adam_Szeidl\/papers\/focusing.pdf<\/a>\r\n\r\nBiography <\/strong>\r\n\r\nAdam Szeidl is professor of economics at Central European University. His research has focused on the economics of social networks, household consumption, and international trade. Szeidl received his PhD from Harvard University in 2004. The same year he joined the faculty of the Economics Department at UC-Berkeley, where he stayed until 2012, most recently as tenured associate professor. Adam has published in leading economics journals such as the Quarterly Journal of Economics and the Journal of Economic Theory. He received a European Research Council Starter Grant in 2011, an Alfred P. Sloan Research Fellowship in 2010 and has been supported by the National Science Foundation since 2005. Szeidl is a member of the NBER and the CEPR.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Costs and Benefits of Dynamic Trading in a Lemons\"]\r\n\r\nAndrzej Skrzypacz<\/a>, Stanford Wednesday, June 20 4:00 PM \u2013 5:30 PM\r\n\r\nDescription<\/strong>\r\n\r\nWe study a dynamic market with asymmetric information that induces the lemons problem. We compare efficiency of the market under different assumption about the timing of trade. We show that there generally exist conditions under which efficiency can be improved by temporarily closing the market as compared to continuous trading opportunities. Full paper and most current abstract available here: http:\/\/www.stanford.edu\/~skrz\/Dynamic_Lemons.pdf<\/a>\r\n\r\nBiography <\/strong>\r\n\r\nAndrzej (Andy) Skrzypacz is the Theodore J. Kreps Professor of Economics at the Stanford Graduate School of Business and a Professor, by courtesy at the Department of Economics. His research is in microeconomic theory, specializing in market design, economic dynamics and collusion. He is currently a co-editor of the American Economic Review and an associate editor at the Rand Journal of Economics. He has received a Stanford GSB PhD Distinguished Service Award in 2005 and has advised over a dozen of Ph.D. dissertations.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Quantum Hamiltonian Complexity\"]\r\n\r\nUmesh Vazirani<\/a>, Berkeley Wednesday, June 13 4:00 PM \u2013 5:30 PM | Video<\/a>\r\n\r\nDescription<\/strong>\r\n\r\nWe consider three basic questions about quantum mechanics:\r\n

    \r\n \t
  1. Do `typical' quantum states that occur in Nature have succinct (polynomial) description?<\/li>\r\n \t
  2. Can quantum systems at room temperature exhibit exponential complexity?<\/li>\r\n \t
  3. Is the scientific method sufficiently powerful to comprehend general quantum systems?<\/li>\r\n<\/ol>\r\nEach of these questions is best studied through a computational lens as a question about computation. The resulting questions lie at the core of theory. The first asks\u00a0 about the structure of solutions to the quantum analog of SAT. The second asks whether there is a quantum analog of the PCP theorem. And the third can be\u00a0formulated as a question about interactive proof systems with BQP provers. In this talk I will describe recent progress on these issues.\r\n\r\nBiography <\/strong>\r\n\r\nUmesh Vazirani received his B.Tech. in computer science from MIT in 1981 and his Ph.D. in computer science from U.C. Berkeley in 1986. He is currently professor of computer science at U.C. Berkeley and director of BQIC -the Berkeley center for Quantum Information and Computation. Prof. Vazirani is a theoretician with broad interests in novel models of computation. He has done seminal work in quantum computation and on the computational foundations of randomness. He is the author of two books \"An introduction to computational learning theory\" with Michael Kearns and \"Algorithms\" with Sanjoy Dasgupta and Christos Papadimitriou.\u00a0 <\/strong>\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Lattice-Based Cryptography\"]\r\n\r\nOded Regev<\/a>, Tel Aviv University and CNRS, ENS, Paris Wednesday, June 6 4:00 PM \u2013 5:30 PM | Video<\/a>\r\n\r\nDescription<\/strong>\r\n\r\nWe will give a survey of recent work on lattice-based cryptography, mainly focusing on the so-called Learning with Errors (LWE) problem. This problem has turned out to be an amazingly versatile basis for cryptographic constructions, with tens of applications, including the recent celebrated work on fully homomorphic encryption. In addition to applications, we will also mention very recent work providing a better understanding of the security of the problem. The talk does not require any prior knowledge in cryptography or in lattices.\r\n\r\nBiography <\/strong>\r\n\r\nOded Regev is a professor in Tel Aviv University and a directeur de recherche in the \u00c9cole Normale Sup\u00e9rieure, Paris under the CNRS. He received his Ph.D. in Computer Science from Tel Aviv University in 2001. He is the recipient of the Krill Prize for Excellence, awarded by the Wolf foundation in 2005, as well as best paper awards in STOC'03 and Eurocrypt'06. He was awarded a European Research Council (ERC) Starting Grant in 2008. His main research areas include theoretical computer science, cryptography, quantum computation, and complexity theory. A main focus of his research is in the area of lattice-based cryptography, where he introduced several key concepts, including the \"learning with error\" problem and the use of Gaussian measures.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Calibrated Incentive Contracts\"]\r\n\r\nSylvain Chassang<\/a>, Princeton Wednesday, May 30 4:00 PM \u2013 5:30 PM\r\n\r\nDescription<\/strong>\r\n\r\nThis paper studies a dynamic agency problem which includes limited liability, moral hazard and adverse selection. The paper develops a robust approach to dynamic contracting based on calibrating the payoffs that would have been delivered by simple benchmark contracts that are attractive but infeasible, due to limited liability constraints. The resulting dynamic contracts are detail-free and satisfy robust performance bounds independently of the underlying process for returns, which need not be i.i.d. or even ergodic.\r\n\r\nBiography <\/strong>\r\n\r\nSylvain Chassang is a Professor of Economics at Princeton University. He received his Ph.D. from MIT and is the recipient of a Sloan Fellowship. His interests include Game Theory and Development Economics.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Low-distortion Inference of Latent Similarities from a Multiplex Social Network\"]\r\n\r\nDavid Kempe<\/a>, USC Wednesday, May 23 4:00 PM \u2013 5:30 PM | Video<\/a>\r\n\r\nDescription<\/strong>\r\n\r\nWhat can a social network tell us about the underlying latent \"social structure,\" the way in which individuals are similar or dissimilar? Much of social network analysis is, implicitly or explicitly, predicated on the assumption that individuals tend to be more similar to their friends than to strangers. Having explicit access to similarity information instead of merely the noisy signal provided by the presence or absence of edges could improve analysis significantly. We study the following natural question: Given a social network - reflecting the underlying social distances between its nodes - how accurately can we reconstruct the social structure?\r\n\r\nIt is tempting to model similarities and dissimilarities as distances, so that the social structure is a metric space.However, observed social networks are usually multiplex, in the sense that different edges originate from similarity in one or more among a number of different categories, such as geographical proximity, professional interactions, kinship, or hobbies. Since close proximity in even one category makes the presence of edges much more likely, an observed social network is more accurately modeled as a union of separate networks. In general, it is a priori not known which network a given edge comes from. While generative models based on a single metric space have been analyzed previously, a union of several networks individually generated from metrics is structurally very different from (and more complex than) networks generated from just one metric.\r\n\r\nWe begin to address this reconstruction problem formally. The latent \"social structure\" consists of several metric spaces. Each metric space gives rise to a \"distance-based random graph,\" in which edges are created according to a distribution that depends on the underlying metric space and makes long-range edges less likely than short ones. For a concrete model, we consider Kleinberg's small-world model and some variations thereof. The observed social network is the union of these graphs. All edges are unlabeled, in the sense that the existence of an edge does not reveal which random graph it comes from. Our main result is a near-linear time algorithm which reconstructs from this unlabeled union each of the individual metrics with provably low distortion.\r\n\r\n(Joint work with Ittai Abraham Shiri Chechik, and Aleksandrs Slivkins.)\r\n\r\nBiography <\/strong>\r\n\r\nDavid Kempe received his Ph.D. from Cornell University in 2003, and has been on the faculty in the computer science department at USC since the Fall of 2004, where he is currently an Associate Professor. During the Spring of 2012, he is visiting Microsoft Research, New England.His primary research interests are in computer science theory and the design and analysis of algorithms, with a particular emphasis on social networks, algorithms for feature selection, and game-theoretic and pricing questions. He is a recipient of the NSF CAREER award, the VSoE Junior Research Award, the ONR Young Investigator Award, and a Sloan Fellowship, in addition to several USC Mentoring awards.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"How to Compute Blindfolded: New Developments in Fully Homomorphic Encryption\"]\r\n\r\nVinod Vaikuntanathan<\/a>, Toronto Wednesday, April 25, 2012 4:00 PM \u2013 5:30 PM\r\n\r\nDescription<\/strong>\r\n\r\nA fully homomorphic encryption scheme enables computation of arbitrary functions on encrypted data. Long regarded as cryptography\u2019s prized \u201choly grail\", a concrete construction of such an encryption scheme remained elusive for over three decades. The last three years has witnessed a number of constructions of fully homomorphic encryption involving novel mathematical techniques based on integer lattices, as well as a number of exciting applications. I will give an overview of these developments and provide a glimpse of the research directions that lie ahead.\r\n\r\nBiography <\/strong>\r\n\r\nVinod Vaikuntanathan is an assistant professor of Computer Science at the University of Toronto. In previous avatars, he was a Researcher at Microsoft Redmond and a Josef Raviv postdoctoral fellow at IBM T.J. Watson. He received his Ph.D. from MIT, where he was a recipient of a George M. Sprowls doctoral dissertation award.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Identity-Based Encryption: Past, Present, and Future\"]\r\n\r\nDan Boneh<\/a>, Stanford Wednesday, May 2 4:00 PM \u2013 5:30 PM\r\n\r\nDescription<\/strong>\r\n\r\nIdentity Based encryption (IBE) is a public-key encryption system where any string can function as a public key. IBE systems imply chosen ciphertext secure encryption, searching on encrypted data, secure signatures, and many other cryptographic primitives. Over the past decade three families of IBE constructions were developed: one family uses pairing-friendly elliptic curve, another uses arithmetic modulo composites, and a third uses integer lattices. This talk will survey some recent IBE constructions and highlight a few central open problems in this area.\r\n\r\nBiography <\/strong>\r\n\r\nDan Boneh is a Professor of Computer Science and Electrical Engineering at Stanford University<\/a>. He is a well-known researcher in the areas of applied cryptography<\/a> and computer security<\/a>.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Expressible Inspections\"]\r\n\r\nEran Shmaya<\/a>, Northwestern Wednesday, April 18, 2012 4:00 PM \u2013 5:30 PM | Video<\/a>\r\n\r\nDescription<\/strong>\r\n\r\nA decision maker needs predictions about the realization of a repeated experi- ment in each period. An expert provides a theory that, conditional on each finite history of outcomes, supplies a probabilistic prediction about the next outcome. However, there may be false experts without any knowledge of the data-generating process who deliver theories strategically. Hence, empirical tests for predictions are necessary. A test is manipulable if a false expert can pass the test with a high probability. Like contracts, tests have to be com- putable to be implemented. Considering only computable tests, we show that there is a test which passes true experts with a high probability yet is not manipulable by any computable strategy. In particular, the constructed test is both prequential and future-independent. On the other hand, any computable test is manipulable by a strategy that is computable relative to the halting problem. Our conclusion overturns earlier results that prequential or future independent tests are manipulable, and shows that computability considerations have significant effects in these problems.\r\n\r\nBiography <\/strong>\r\n\r\nEran Shmaya joined the Managerial Economics and Decision Sciences department at the Kellogg School of Management in 2008. Professor Shmaya graduated from Tel Aviv University in 2007. Professor Shmaya's research areas are game theory, probability and information theory. He is currently working on infinite games. He is also interested in applications of game theory in the natural sciences.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Illegitimi non carborundum\"]\r\n\r\nRon Rivest<\/a>, MIT Wednesday, April 11, 2012 4:00 PM \u2013 5:30 PM\r\n\r\nDescription <\/strong>\r\n\r\nMotivated by the increasing sophistication of recent Advanced Persistent Threats (APTs), we introduce the game of \"stealthy takeovers'' (aka \"FlipIt''). FlipIt is a two-player game (between an attacker and a defender) where either player can move at any given time, but cannot determine the state of the game until he moves himself. This stealthy game models various security situations in which a resource can be \"silently corrupted'' by an adversary, but then \"disinfected'' later by the defender. Interesting features of this game include:\r\n