College of Computing (CoC)
http://hdl.handle.net/1853/5977
The College of Computing houses one of the largest computer science programs in the countrySat, 10 Dec 2016 16:44:14 GMT2016-12-10T16:44:14ZExplicit Two-Source Extractors and Resilient Functions
http://hdl.handle.net/1853/56062
Explicit Two-Source Extractors and Resilient Functions
Zuckerman, David
We explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\Omega(1)}. The best previous extractor, by Bourgain, required each source to have min-entropy .499n.
A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta>0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylog(n)-wise independently, and the remaining q=n^{1-\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q=n^{1/2 - \delta}.
Our explicit two-source extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.
Joint work with Eshan Chattopadhyay.
Presented on November 14, 2016 at 11:00 a.m. in the Klaus Advanced Computing Building, room 1116E.; David Zuckerman holds an Endowed Professorship in the Computer Science Department at the University of Texas at Austin. His research focuses primarily on pseudorandomness and the role of randomness in computing. He is best known for his work on randomness extractors and their applications. His other research interests include coding theory, distributed computing, cryptography, inapproximability, and other areas of complexity theory.; Runtime: 60:51 minutes
Mon, 14 Nov 2016 00:00:00 GMThttp://hdl.handle.net/1853/560622016-11-14T00:00:00ZZuckerman, DavidWe explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\Omega(1)}. The best previous extractor, by Bourgain, required each source to have min-entropy .499n.
A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta>0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylog(n)-wise independently, and the remaining q=n^{1-\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q=n^{1/2 - \delta}.
Our explicit two-source extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.
Joint work with Eshan Chattopadhyay.Why Brains Need Computers: How Computer Science and Engineering Can Improve Neurology
http://hdl.handle.net/1853/56044
Why Brains Need Computers: How Computer Science and Engineering Can Improve Neurology
Westover, Brandon
Expert level GO and chess are here, while self-driving
cars and human-level
computer vision and speech recognition are
rapidly becoming realities. Meanwhile, despite hype about
"precision medicine" and "big medical data", the day-to-day
practice of neurology continues to rely almost entirely on
human expertise. In this talk I will introduce a range of real-world
clinical problems for which computing, data science,
machine learning, engineering, and other technical
approaches can improve neurology, and why previous
attempts at solving some of these problems have failed.
These problems include: predicting which patients with brain
injuries will have seizures; detecting seizures and seizure-like
patterns in streaming brain monitoring
(electroencephalography, EEG) data streams; diagnosing
epilepsy in patients who have it, and avoiding misdiagnosing
it in patients who don't; predicting which epilepsy patients will
benefit from existing therapies; predicting whether a
comatose patient will eventually recover consciousness;
detecting impending cerebral infarction (stroke) in patients
with brain aneurysms; automating the delivery of anesthesia
to patients with acute brain swelling or life-threatening
seizures; computing a patient's level of consciousness from
the EEG and EKG signals; diagnosing delirium; and tracking
sleep stages. For each of these problems, we will point out
pitfalls, progress to date, and remaining challenges.
Presented on November 10, 2016 at 3:00 p.m. in the Klaus Advanced Computer Building, room 1116.; Dr. M. Brandon Westover, MD, PhD, completed medical
training and a PhD degree in physics at Washington
University School of Medicine in St. Louis. He is currently an and a neurologist specializing in epilepsy and clinical
neurophysiology at the Massachusetts General Hospital
(MGH) where he directs the MGH Critical Care EEG
Monitoring Service. Clinically, he is interested in applying
electroencephalography (EEG) to help care for patients with
acute neurological conditions such as delirium, anoxic brain
injury, status epilepticus, and delayed cerebral ischemia
following subarachnoid hemorrhage. His research interests
include automated methods for interpreting clinical EEG
data, closed-loop
control of sedation and analgesia,
biomedical informatics, probabilistic analysis of medical
decisions, and the neurophsyiology of pain, sedation, and
delirium in critically ill patients. Dr. Westover’s overarching
research goal is to improve neurology and particularly
neurocritical care through the application of engineering
principles, applied mathematics, and computational
approaches.; Runtime: 62:17 minutes
Thu, 10 Nov 2016 00:00:00 GMThttp://hdl.handle.net/1853/560442016-11-10T00:00:00ZWestover, BrandonExpert level GO and chess are here, while self-driving
cars and human-level
computer vision and speech recognition are
rapidly becoming realities. Meanwhile, despite hype about
"precision medicine" and "big medical data", the day-to-day
practice of neurology continues to rely almost entirely on
human expertise. In this talk I will introduce a range of real-world
clinical problems for which computing, data science,
machine learning, engineering, and other technical
approaches can improve neurology, and why previous
attempts at solving some of these problems have failed.
These problems include: predicting which patients with brain
injuries will have seizures; detecting seizures and seizure-like
patterns in streaming brain monitoring
(electroencephalography, EEG) data streams; diagnosing
epilepsy in patients who have it, and avoiding misdiagnosing
it in patients who don't; predicting which epilepsy patients will
benefit from existing therapies; predicting whether a
comatose patient will eventually recover consciousness;
detecting impending cerebral infarction (stroke) in patients
with brain aneurysms; automating the delivery of anesthesia
to patients with acute brain swelling or life-threatening
seizures; computing a patient's level of consciousness from
the EEG and EKG signals; diagnosing delirium; and tracking
sleep stages. For each of these problems, we will point out
pitfalls, progress to date, and remaining challenges.Differentially Private Analysis of Graphs
http://hdl.handle.net/1853/56017
Differentially Private Analysis of Graphs
Raskhodnikova, Sofya
Many types of data can be represented as graphs, where nodes correspond to individuals and edges capture relationships between them. Examples include datasets capturing “friendships” in an online social network, financial transactions, email communication, doctor-patient relationships, and romantic ties. On one hand, such datasets contain sensitive information about individuals. On the other hand, global information that can be gleaned from their analysis can provide significant benefits to society. Several naive attempts at anonymizing sensitive data by stripping obvious identifying information resulted in spectacular failures. In this talk, we discuss algorithms for analyzing network data that satisfy a rigorous notion of privacy called node differential privacy. We present several techniques for designing node differentially private algorithms, based on combinatorial analysis, network flow, and linear and convex programming.
Based on joint work with A. Smith (FOCS 2016) and with S. Kasiwisvanathan, K. Nissim, A. Smith (TCC 2013)
Presented on November 7, 2016 at 11:00 a.m. in the Klaus Advanced Computing Building, Room 1116E; Sofya Raskhodnikova is an associate professor of Computer Science and Engineering at Penn State. Her research interests include sublinear-time algorithms, private data analysis, approximation algorithms, and randomized algorithms.; Runtime: 55:16 minutes
Mon, 07 Nov 2016 00:00:00 GMThttp://hdl.handle.net/1853/560172016-11-07T00:00:00ZRaskhodnikova, SofyaMany types of data can be represented as graphs, where nodes correspond to individuals and edges capture relationships between them. Examples include datasets capturing “friendships” in an online social network, financial transactions, email communication, doctor-patient relationships, and romantic ties. On one hand, such datasets contain sensitive information about individuals. On the other hand, global information that can be gleaned from their analysis can provide significant benefits to society. Several naive attempts at anonymizing sensitive data by stripping obvious identifying information resulted in spectacular failures. In this talk, we discuss algorithms for analyzing network data that satisfy a rigorous notion of privacy called node differential privacy. We present several techniques for designing node differentially private algorithms, based on combinatorial analysis, network flow, and linear and convex programming.
Based on joint work with A. Smith (FOCS 2016) and with S. Kasiwisvanathan, K. Nissim, A. Smith (TCC 2013)Robust Statistics, Revisited
http://hdl.handle.net/1853/56016
Robust Statistics, Revisited
Moitra, Ankur
Starting from the seminal works of Tukey (1960) and Huber (1962), the field of robust statistics asks: Are there estimators that provable work in the presence of noise? The trouble is that all known provably robust estimators are also hard to compute in high-dimensions.
Here, we study a basic problem in robust statistics, posed in various forms in the above works. Given corrupted samples from a high-dimensional Gaussian, are there efficient algorithms to accurately estimate its parameters? We give the first algorithms that are able to tolerate a constant fraction of corruptions that is independent of the dimension. Additionally, we give several more applications of our techniques to product distributions and various mixture models.
This is based on joint work with Ilias Diakonikolas, Jerry Li, Gautam Kamath, Daniel Kane and Alistair Stewart.
Presented on October 31, 2016 at 11:00 a.m. in the Klaus Advanced Computing Building, Room 1116E; Ankur Moitra is the Rockwell International Assistant Professor in the Department of Mathematics at MIT and a Principal Investigator in the Computer Science and Artificial Intelligence Lab (CSAIL). The aim of his work is to bridge the gap between theoretical computer science and machine learning by developing algorithms with provable guarantees and foundations for reasoning about their behavior.; Runtime: 58:19 minutes
Mon, 31 Oct 2016 00:00:00 GMThttp://hdl.handle.net/1853/560162016-10-31T00:00:00ZMoitra, AnkurStarting from the seminal works of Tukey (1960) and Huber (1962), the field of robust statistics asks: Are there estimators that provable work in the presence of noise? The trouble is that all known provably robust estimators are also hard to compute in high-dimensions.
Here, we study a basic problem in robust statistics, posed in various forms in the above works. Given corrupted samples from a high-dimensional Gaussian, are there efficient algorithms to accurately estimate its parameters? We give the first algorithms that are able to tolerate a constant fraction of corruptions that is independent of the dimension. Additionally, we give several more applications of our techniques to product distributions and various mixture models.
This is based on joint work with Ilias Diakonikolas, Jerry Li, Gautam Kamath, Daniel Kane and Alistair Stewart.