BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Beyond P vs. NP: Quadratic-Time Hardness For Big Data Problems –
  Piotr Indyk
DTSTART:20170614T093000
DTEND:20170614T101500
DTSTAMP:20260510T084012Z
UID:73eaec34b2a684f7da3ba702104b25a5214cdd9096f947558bb40721
CATEGORIES:Conferences - Seminars
DESCRIPTION:Piotr Indyk\, MIT\nThe theory of NP-hardness has been very suc
 cessful in identifying problems that are unlikely to be solvable in polyno
 mial time. However\, many other important problems do have polynomial time
  algorithms\, but large exponents in their time bounds can make them run f
 or days\, weeks or more. For example\, quadratic time algorithms\, althoug
 h practical on moderately sized inputs\, can become inefficient on big dat
 a problems that involve gigabytes or more of data. Although for many probl
 ems no sub-quadratic time algorithms are known\, any evidence of quadratic
 -time hardness has remained elusive. In this talk I will give an overview 
 of recent research that aims to remedy this situation. In particular\, I w
 ill describe hardness results for problems in string processing (e.g.\, ed
 it distance computation or regular expression matching) and machine learni
 ng (e.g.\, Support Vector Machines or gradient computation in neural netwo
 rks). All of them have polynomial time algorithms\, but despite extensive 
 amount of research\, no near-linear time algorithms have been found for ma
 ny variants of these problems. I will show that\, under a natural complexi
 ty-theoretic conjecture\, such algorithms do not exist. I will also descri
 be how this framework has led to the development of new algorithms.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR