{"493111":{"#nid":"493111","#data":{"type":"event","title":"ARC Theory Day","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EARC Theory Day\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, April 11\u003C\/strong\u003E\u003Cstrong\u003E, 2016\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 - 9:00 am - 4:00 pm\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EObjective:\u003C\/strong\u003E \u0026nbsp;\u003Cbr \/\u003EAlgorithms and Randomness Center (ARC) Theory Day is an annual event to showcase lectures on exciting new developments in theoretical computer science. This year\u0027s event features four young speakers who are dedicated to investigating some of the most complex questions in theoretical computer science. These guests will discuss a wide range of topics from interior point methods to circuit lower bounds by random projections. The lectures promise to be engaging and discuss techniques to help solve these emerging problems and understand related phenomena.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EOrganizers:\u003C\/strong\u003E Santosh Vempala, Richard Peng and Dana Randall\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ESchedule:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EMonday, April 11, 2016: \u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E9:30 am \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Breakfast\u003Cbr \/\u003E9:50 am \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Opening Remarks\u003Cbr \/\u003E10:00 am \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003Cstrong\u003EVirginia Vassilevska-Williams\u003C\/strong\u003E (Stanford): \u003Cstrong\u003EFine-Grained Algorithms and Complexity\u003Cbr \/\u003E\u003C\/strong\u003E11:00 am \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Break\u003Cbr \/\u003E11:15 am\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003Cstrong\u003ERocco Servedio\u003C\/strong\u003E (Columbia): \u003Cstrong\u003ECircuit Lower Bounds via Random Projections\u003Cbr \/\u003E\u003C\/strong\u003E12:15 pm\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Lunch Break\u003Cbr \/\u003E1:30 pm\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003Cstrong\u003EAaron Sidford \u003C\/strong\u003E(Microsoft Research): \u003Cstrong\u003ERecent Advances in the Theory of Interior Point Methods\u003Cbr \/\u003E\u003C\/strong\u003E2:30 pm \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Break\u003Cbr \/\u003E2:45 pm\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003Cstrong\u003ELuca Trevisan\u003C\/strong\u003E (UC Berkeley): \u003Cstrong\u003ERamanujan Graphs\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstracts:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EVirginia Vassilevska-Williams (Stanford): \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E \u003Cbr \/\u003E Fine-Grained Algorithms and Complexity\u003Cbr \/\u003E \u003Cstrong\u003EAbstract:\u003Cbr \/\u003E \u003C\/strong\u003EA central goal of algorithmic research is to determine how fast computational problems can be solved in the worst case. Theorems from complexity theory state that there are problems that, on inputs of size n, can be solved in t(n) time but not in t(n)^{1-eps} time for eps\u0026gt;0. The main challenge is to determine where in this hierarchy various natural and important problems lie. Throughout the years, many ingenious algorithmic techniques have been developed and applied to obtain blazingly fast algorithms for many problems. Nevertheless, for many other central problems, the best known running times are essentially those of the classical algorithms devised for them in the 1950s and 1960s.\u003Cbr \/\u003E \u003Cbr \/\u003E Unconditional lower bounds seem very difficult to obtain, and so practically all known time lower bounds are conditional. For years, the main tool for proving hardness of computational problems have been NP-hardness reductions, basing hardness on P\\neq NP. However, when we care about the exact running time (as opposed to merely polynomial vs non-polynomial), NP-hardness is not applicable, especially if the running time is already polynomial. In recent years, a new theory has been developed, based on \u201cfine-grained reductions\u201d that focus on exact running times. The goal of these reductions is as follows. Suppose problem A is solvable in a(n) time and problem B in b(n) time, and no a(n)^{1-eps} and b(n)^{1-eps} algorithms are known for A and B respectively. Then, if A is fine-grained reducible to problem B (for a(n) and b(n)), a b(n)^{1-eps} time algorithm for B (for any eps\u0026gt;0) implies an a(n)^{1-eps\u0027} algorithm for A (for some eps\u0027\u0026gt;0). Now, mimicking NP-hardness, the approach is to (1) select a key problem X that is conjectured to require t(n)^{1-o(1)} time for some t, and (2) reduce X in a fine-grained way to many important problems. This approach has led to the discovery of many meaningful relationships between problems, and even sometimes to equivalence classes.\u003Cbr \/\u003E \u003Cbr \/\u003E In this talk I will give an overview or the current progress in this area of study, and will highlight some new exciting developments.\u003Cbr \/\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E Virginia V. Williams is an assistant professor of computer science at Stanford University. She obtained her Ph.D. in 2008 from Carnegie Mellon where she was advised by Guy Blelloch. Before joining Stanford, she spent time at the Institute for Advanced Study and UC Berkeley. Her main area of interest is broadly in computational complexity, the design and analysis of algorithms, and more specifically in graph and matrix algorithms.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ERocco Servedio (Columbia University)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E \u0026nbsp;\u003Cbr \/\u003E Circuit Lower Bounds via Random Projections\u003Cbr \/\u003E \u003Cstrong\u003EAbstract:\u003C\/strong\u003E \u003Cbr \/\u003E Random restrictions are a classical and\u0026nbsp;important technique for proving circuit lower bounds.\u0026nbsp; This talk will discuss\u0026nbsp;\u003Cem\u003Erandom\u0026nbsp;projections,\u0026nbsp;\u003C\/em\u003Ea generalization of random restrictions.\u0026nbsp; While conceptually simple, random projections have led to recent advances on several well-studied lower bound problems involving small-depth circuits.\u0026nbsp; We will see how random projections play a key role in the following results:\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003EAn average-case depth hierarchy theorem for Boolean circuits.\u0026nbsp;This gives an average-case extension of the classical (worst-case) depth hierarchy theorem of\u0026nbsp;Sipser, Yao, and\u0026nbsp;Hastad, and resolves a main open problem in\u0026nbsp;Hastad\u2019s\u0026nbsp;1986 PhD thesis.\u0026nbsp; Via a classical connection between Boolean circuits and structural complexity, this hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, resolving a longstanding conjecture of\u0026nbsp;Hastad,\u0026nbsp;Cai\u0026nbsp;and\u0026nbsp;Babai\u0026nbsp;from the 1980s.\u0026nbsp; (Joint work with Ben\u0026nbsp;Rossman\u0026nbsp;and Li-Yang Tan.)\u003C\/li\u003E\u003Cli\u003EThe first super-polynomial lower bounds against the \u201cdepth d\u0026nbsp;Frege\u201d proof system for some polylogarithmic depth d.\u0026nbsp; Previous super-polynomial lower bounds (Pitassi\u0026nbsp;et al. 1993,\u0026nbsp;Krajicek\u0026nbsp;et al. 1995) were only known against depth-d\u0026nbsp;Frege\u0026nbsp;for d=Theta(log log n).\u0026nbsp; (Joint work with Toni\u0026nbsp;Pitassi, Ben\u0026nbsp;Rossman, and Li-Yang Tan.)\u003C\/li\u003E\u003Cli\u003EA nearly optimal size lower bound on small-depth circuits that determine whether a graph has a short s-to-t path.\u0026nbsp; We show that depth-d circuits for distance-k connectivity on n-node graphs must have size n^{\\Omega(k^{1\/d}\/d)}; the previous best size lower bounds for this problem were n^{k^{\\exp(-O(d))}} (due to\u0026nbsp;Beame\u0026nbsp;et al. 1998) and n^{\\Omega((\\log k)\/d)} (due to\u0026nbsp;Rossman\u0026nbsp;2014).\u0026nbsp; (Joint work with Xi Chen, Igor Oliveira and Li-Yang Tan.)\u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E \u0026nbsp;\u003Cbr \/\u003E Rocco Servedio is an Associate Professor of Computer Science at Columbia University. His research interests center around computational learning theory, property testing, and computational complexity.\u0026nbsp; Rocco is the recipient of an NSF Career Award and a Sloan Foundation Fellowship; his research has received Best Paper \/ Best Student Paper awards from the CCC, COLT, FOCS, and STOC conferences.\u0026nbsp; His teaching at Columbia has been recognized with the Department of Computer Science Distinguished Teaching Award, the Columbia Engineering Alumni Association Distinguished Faculty Teaching Award, and the Columbia Presidential Teaching Award.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAaron Sidford (Microsoft Research)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle\u003C\/strong\u003E: \u003Cbr \/\u003E Recent Advances in the Theory of Interior Point Methods\u0026nbsp;\u003Cbr \/\u003E \u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u0026nbsp;\u003Cbr \/\u003E In this talk I will survey recent results on\u0026nbsp;using interior point techniques\u0026nbsp;to design provably efficient algorithms. I will give a brief overview of this powerful convex optimization technique and discuss how it has been used to improve the running time of fundamental optimization problems such as maximum flow, linear programming, and most recently the geometric median problem. In particular, I will highlight recent joint work with Michael Cohen, Yin Tat Lee, Jakub Pachocki, and Gary Miller building on these techniques to obtain the first nearly linear time algorithm for computing the geometric median. No previous experience with interior point methods required.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EBio\u003C\/strong\u003E:\u0026nbsp;\u003Cbr \/\u003E Aaron Sidford is a postdoctoral researcher at Microsoft Research New England and will be joining the department of Management Science and Engineering at Stanford University in Fall 2016. Aaron received his PhD from the EECS department at MIT where he was advised by Professor Jonathan Kelner.\u0026nbsp;\u003Cbr \/\u003E \u003Cbr \/\u003EAaron\u2019s research interests lie broadly in the theory of computation and the design and analysis of algorithms. He is particularly interested in work at the intersection of continuous optimization, graph theory, numerical linear algebra, and data structures.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ELuca Trevisan (UC Berkeley)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E \u003Cbr \/\u003E Ramanujan Graphs\u003Cbr \/\u003E \u003Cstrong\u003EAbstract:\u003C\/strong\u003E \u003Cbr \/\u003E We will review what is known about existence and constructions of Ramanujan graphs, which are the best possible expander graphs from the point of view of spectral expansion.\u003Cbr \/\u003E We will talk about Friedman\u0027s result that random graphs are nearly Ramanujan, and recent simplifications of his proof, about a characterization of Ramanujan graphs in terms of the Ihara zeta function, about number-theoretic efficient constructions, and about the recent non-constructive existence results of Marcus, Spielman, and Srivastava.\u003Cbr \/\u003E \u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E Luca Trevisan is a professor of Electrical Engineering and Computer Sciences and of Mathematics at U.C. Berkeley, and a senior scientist at the Simons Institute for the Theory of Computing. In the past, he has also taught at Columbia University and at Stanford. He is interested in several aspects of computational complexity theory and, in the last few years, he has been working on spectral graph theory.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 East \u0026 West - Invited Speakers: Rocco Servedio (Columbia), Aaron Sidford (Microsoft Research), Luca Trevisan (UC Berkeley) and Virginia Vassilevska-Williams (Stanford)"}],"uid":"27466","created_gmt":"2016-01-31 16:15:32","changed_gmt":"2017-04-13 21:16:50","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-04-11T10:30:00-04:00","event_time_end":"2016-04-11T17:00:00-04:00","event_time_end_last":"2016-04-11T17:00:00-04:00","gmt_time_start":"2016-04-11 14:30:00","gmt_time_end":"2016-04-11 21:00:00","gmt_time_end_last":"2016-04-11 21:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"},{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}