BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of California\, Berkeley//UCB Events Calendar//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
DTSTART:19701029T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:19700402T020000
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20180208T000847Z
DTSTART;TZID=America/Los_Angeles:20180226T153000
DTEND;TZID=America/Los_Angeles:20180226T170000
TRANSP:OPAQUE
SUMMARY:Barna Saha - Efficient Fine-Grained Algorithms
UID:115452-ucb-events-calendar@berkeley.edu
ORGANIZER;CN="UC Berkeley Calendar Network":
LOCATION:3108 Etcheverry Hall
DESCRIPTION:Barna Saha\, University of Massachusetts Amherst\n\nAbstract: One of the greatest successes of computational complexity theory is the classification of countless fundamental computational problems into polynomial-time and NP-hard ones\, two classes that are often referred to as tractable and intractable\, respectively. However\, this crude distinction of algorithmic efficiency is clearly insufficient when handling today's large scale of data. We need a finer-grained design and analysis of algorithms that pinpoints the exact exponent of polynomial running time\, and a better understanding of when a speed-up is not possible. Over the years\, many polynomial-time approximation algorithms were devised as an approach to bypass the NP-hardness obstacle of many discrete optimization problems. This area has developed into a rich field producing many algorithmic ideas and has lead to major advances in computational complexity. So far\, however\, a similar theory for high polynomial time problems to understand the trade-off between quality and running time is vastly lacking. \n\nIn this presentation\, I will give you an overview of the newly growing field of fine-grained algorithms and complexity\, and my contributions therein. This will include fundamental problems such as edit distance computation\, all-pairs shortest paths\, parsing and matrix multiplication. They have applications ranging from genomics to statistical natural language processing\, machine learning and optimization. I will show how as a natural byproduct of improved time complexity\, one may design algorithms that are highly parallel as well as streaming algorithms with sublinear space complexity. Finally\, motivated by core machine learning applications\, I will discuss alternative measures of efficiency that may be equally relevant as time complexity.\n\nBio: Barna Saha is currently an Assistant Professor in the College of Information & Computer Science at the University of Massachusetts Amherst. She is also a Permanent Member of Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers. Before joining UMass in 2014\, she was a Research Scientist at AT&T Shannon Laboratories\, New Jersey. She spent four wonderful years (2007-2011) at the University of Maryland College Park from where she received her Ph.D. in Computer Science. In Fall 2015\, she was at the University of California Berkeley as a Visiting Scholar and as a fellow of the Simons Institute. Her research interests include Theoretical Computer Science\, Probabilistic Method & Randomized Algorithms and Large Scale Data Analytics. She is the recipient of NSF CAREER award (2017)\, Google Faculty Award (2016)\, Yahoo Academic Career Enhancement Award (2015)\, Simons-Berkeley Research Fellowship (2015)\, NSF CRII Award (2015) and Dean's Dissertation Fellowship (2011). She received the best paper award at the Very Large Data Bases Conference (VLDB) 2009 for her work on Probabilistic Databases and was chosen as finalists for best papers at the IEEE Conference on Data Engineering (ICDE) 2012 for developing new techniques to handle low quality data.
URL:http://events.berkeley.edu/index.php/calendar/sn/pubaff.html?event_ID=115452&view=preview
SEQUENCE:0
CLASS:PUBLIC
CREATED:20180208T000847Z
LAST-MODIFIED:20180208T000847Z
X-MICROSOFT-CDO-BUSYSTATUS:BUSY
X-MICROSOFT-CDO-INSTTYPE:0
X-MICROSOFT-CDO-IMPORTANCE:1
X-MICROSOFT-CDO-OWNERAPPTID:-1
END:VEVENT
END:VCALENDAR