There is an unknown n-bit string x. A "trace" is a random substring of x formed by deleting each bit with probability (say) 1/2. Suppose an algorithm has access to independent traces of x. How many does it need to reconstruct x? The previous best method needed about exp(n^{1/2}) traces. We give a simple "mean-based" algorithm that uses about exp(n^{1/3}) traces (and time). We also show that any algorithm working in the restricted "mean-based" framework requires exp(n^{1/3}) traces. The main tool in our work is elementary complex analysis.

For More Information, Contact:

Tree data structures play an important role in almost every area if computer science. Nowadays the explosion of data puts forward a higher demand for the performance of the trees, which requires efficient parallel algorithms for processing large-scale data, as well as a full-featured interface for achieving more functionalities. Traditional algorithm designing on balanced binary trees based on insertions and deletions are plagued with challenges such as being hard to parallelize, single-operand oriented, and varying among different balancing schemes.

For More Information, Contact:

Approximation Algorithms, and its sister field Online Algorithms have had a pro- found impact in theoretical computer science. Questions in this field have created a host of new algorithmic tools and techniques that have had impact in the other fields such as operations research, machine learning and complexity theory. In this thesis, we study several problems and propose new variations on them. We achieve new results on classical problems such as finding indpendent sets in degree-d graphs and fraction- ally sub-additive network design problem.

For More Information, Contact:

DNA read mapping is one of the fundamental problem in bioinformatics. The general goal is to map billions of short pieces of DNA (reads) to a high quality reference genome, while tolerating errors including genomic variations between individuals and the sequencer imprecision.

For More Information, Contact:

Formal verification methods are making headway into required safety verification policies for transportation. However, they often fail to account for the fact that controllers, whether digital or human, have imperfect knowledge of the world. Without addressing this shortcoming, we risk never bridging the gap between theoretical and practical safety.

In this talk, we discuss the sometimes fatal consequences of these shortcomings, and describe a new logic with belief as a first-class citizen, allowing us to model, think and verify belief-aware cyber physical systems.

For More Information, Contact:

Wearable cognitive assistance applications can provide guidance for many facets of a user's daily life. In this presentation, I will talk about my recent work that enables a new genre of such applications that require both heavy computation and very low response time on inputs from mobile devices. The core of this work is the design, implementation, and evaluation of Gabriel, an application platform that simplifies the creation of and experimentation with this new genre of applications.

For More Information, Contact:

Monday, November 13, 2017 - by

The School of Computer Science's Ph.D. women are hard at work bringing new and exciting opportunities to Carnegie Mellon's Women @ SCS program. Directed by Carol Frieze, Women @ SCS creates and supports academic, social and professional opportunities for women in computer science. The program includes a wide range of women including undergraduate, master's and Ph.D. students — as well as faculty.

For More Information, Contact:

Monday, November 13, 2017 - by

Carnegie Mellon University's Libratus artificial intelligence, which scored an historic victory over four human poker pros earlier this year, has won the HPCwire Reader's Choice Award for Best Use of AI. The award from the supercomputing trade publication was announced at the 2017 International Conference for High Performance Computing, Networking, Storage and Analysis (SC17) in Denver, Colo.

For More Information, Contact:

Friday, November 10, 2017 - by

Priya Donti, a doctoral candidate co-advised by Zico Kolter and Inês Azevedo at Carnegie Mellon University, has been awarded a Department of Energy Computational Science Graduate Fellowship (DOE CSGF) to support her Computer Science and Energy Policy research.

For More Information, Contact:

My dissertation will demonstrate some of the limitations of existing approaches to automated curriculum design and propose a new approach that leverages learner-generated resources to create new educational content.

For More Information, Contact:

Pages

Subscribe to Carnegie Mellon University - Computer Science Department RSS