Research Excellence Award

Departmental Research Excellence:   Gavin Brown

Departmental Research Excellence:   Sarah Scheffler & Kostas Sotiropoulos

Ramesh Pallavoor Suresh

Ramesh’s research focuses on sublinear-time algorithms. The goal is to understand what can be computed extremely quickly (after looking only at a tiny portion of the input), but with reasonable accuracy. Ramesh has recent results on sublinear-time algorithms that compute on graph data with erasures. This work defines a new model, appropriate for situations when the input graph is corrupted or access to the input is denied, for example, because of privacy concerns. Ramesh investigated testing connectedness and approximating the average degree in this model. Ramesh is a coauthor on a SODA 2020 paper on approximating the distance of a given function to the nearest monotone function. This work has resolved an important open question in sublinear algorithms from Property Testing Review 2014 for the case of nonadaptive algorithms. These are algorithms that make all their queries in advance, before receiving any answers. The approximation algorithm in the SODA paper is based on a novel use of a directed isoperimetric inequality for the Boolean hypercube. Ramesh is also a coauthor of the best approximation algorithms and hardness results for testing whether a function is unate in different parameter regimes. A function is called unate if it is nonincreasing or nondecreasing in every variable. This work was published in ICALP 2017, and the full version has been accepted to the Theory of Computing journal. Ramesh has also done interesting work on parametrized property testing (ITCS 2017, ACM Transactions on Computation Theory 2018). Usually, the running time of sublinear-time algorithms is measured with respect to the size of the input. Ramesh showed that by measuring it with respect to other parameters, we can sometimes overcome the known hardness results. Notably, he gave an algorithm for testing whether the data is sorted which is extremely efficient for data in a bounded range and beats the long-time lower bound for general range. Ramesh also contributed significantly to the success of the Algorithms and Theory group at BU, helping run our Algorithms/Theory seminar and assisting in TCS classes. 

Xingchao Peng

Xingchao Peng is a final year PhD student with an excellent track record in both research and service. Xingchao’s PhD work has focused on designing Machine Learning algorithms that can learn from less data. He developed several algorithms that transfer learned knowledge from one application domain to another, thus reducing the need for extra data annotation. These were published in nine peer-reviewed papers in top AI conferences, including an oral paper at ICCV19 that provided both theoretical insights and practical algorithms for knowledge transfer from multiple labeled source domains to an unlabeled target domain. Xingchao has also served the AI research community extensively, acting as a conference reviewer for over 35 conferences and journals in the last five years, and collecting two large-scale datasets to facilitate transfer learning research, VisDA (28K images) and DomainNet (0.6 million images).

Jacob Harer

In the short four years that Jacob Harer has been in our department, he has not only transitioned successfully from his old field EE (in which he has his BA and MS), but has also blossomed into an indecent, original and fancifully imaginative researcher in his own right. He has made a critical contribution to a four year research program at DARPA called MUSE (Mining and Understanding of Software Enclaves), which culminated in a paper in NIPS 2018, titled “Learning to Repair Software Vulnerabilities with Generative Adversarial Networks.” He has developed novel learning algorithms to understand patterns in various signals (neural spikes and local field potentials in brains, RF and magnetic signals from integrated circuits, etc.), and in his final year of the doctoral program, he tackled a difficult challenge of Tree-to-Tree learning with potential applications for various NLP tasks. He was the first member of my group and a valuable senior PhD within the group, as he is always willing to help his follow students with I-can-do-this-for-you attitude. He is always full of great ideas and more importantly full of heart.

Oxana Poburinnaya

Omer Paneth, PhD ’16

Omer has written papers that have significantly influenced the state of the art in cryptographic research, including seminal works on the construction of program obfuscation schemes and their use within cryptography and beyond, on succinct delegation of computation, on zero knowledge proofs with low round complexity, on resettable and concurrent protocols, on functional encryption, and much more. Omer also contributed significantly to the success of the BUSEC group, mentoring younger students. and assisting in crypto and security classes.

Ye Li, PhD ’15
Ye’s research focuses on the development of operating system kernels for real-time and embedded computing. His PhD is on the design of the Quest-V separation kernel for mixed-criticality systems, which he has been co-developing with his advisor, Prof. Rich West, and other systems students. Ye’s contribution is on the use of hardware virtualization techniques to sandbox and, hence, separate components of a system into different criticality domains. The resulting Quest-V system takes a radically different system structure to normal OSes: rather than being an SMP-based system with one image running on every core, it looks like a chip-level distributed system. CPU, memory and I/O resources are partitioned amongst sandbox domains that manage resources directly without hypervisor (or virtual machine monitor) intervention. This makes the system far more efficient than with traditional hypervisor-based systems. Ye has also contributed to the design and development of secure and predictable inter-sandbox communication techniques. Application use-cases for such a system include automotive, avionics, healthcare, factory automation and robotics, where safety-critical system components must be separated so that failures and timing violations do not have global, and potentially catastrophic, consequences. Ye has led or been co-author on papers in top conferences for his area, including RTSS 2014, VEE 2014, PACT 2014, and RTAS (2013 and 2011), amongst others. His work has also been submitted to ACM TOCS and USENIX ATC, where it is currently under review.

Danna Gurari, PhD ’15
Danna Gurari’s research focuses on computer vision and human computation. Human computation is an emerging branch of computer science that concerns the design and analysis of computing systems in which humans participate as computing elements. Danna’s research contributions have solved problems at the intersection of computer vision, crowd sourcing, and biomedical user interface design. The excitement in the research community for Danna’s work is maybe best exemplified by the “Best Paper Awards” that two of her first-authored papers have received. Most recently, she was awarded an “Innovative Idea Award” for her work on bootstrapping automated image segmentation methods with crowdsourced initializations to significantly improve the performance of these methods. Danna’s human computation system produced the outlines of living cells in microscopy images with expert-level accuracy. The potential impact of this work is immense: Annotating the outline of regions of interest in images, i.e., “segmentation,” is a very common and extremely time-consuming manual task for scientists working with image or video data. Danna demonstrated, for the first time in the literature, that a well-designed human-computation system can include internet workers without domain-specific training in reliably taking on the role of experts in various biomedical segmentation tasks. In her award winning 2013 WACV paper, Danna introduced the first human computation system to address the problem of segmentation in biomedical image analysis with a collection of multiple algorithms. She showed how to obtain project-specific performance indicators in a principled way that links annotation tools, fusion methods, and evaluation algorithms into a unified system. Danna has made the source code of all her work available on the internet. She has also contributed new image libraries for benchmarking. In addition to papers in WACV 2013 and 2015, Danna has published in Collective Intelligence 2015, HCOMP 2014, MICCAI IMIC 2014, BSA 2014, MICCAI 2012, and IHCI 2011.

Dimitrios Papadopoulos, PhD ’16
Dimitrios Papadopoulos has gone from ‘strength to strength;’ last year he had FIVE papers in top conferences, and he is a leader and role model in our BUSEC group. Dimitrios participated in various research projects that resulted in five publications at top cryptography, security and data management conferences, namely, PKC’14, Usenix Security’14, ACM CCS’14, NDSS’15 and VLDB’15. His PKC, CCS and VLBD papers correspond to core works for his thesis with contributions performed mostly by him. His Usenix and NDSS papers are also related to his thesis topic, with significant pieces of the work contributed by him. The NDSS paper has high potential to have practical impact on DNS security. Dimitrios currently participates in a number of research projects that will very likely result in more high-quality publications.

Ben Fuller, PhD ’15
Ben Fuller designed techniques for authentication and key derivation from noisy secrets, significantly advancing the state of the art. When establishing a secure communication channel, each communicating party needs some method to authenticate the other, lest it unwittingly establish a channel with the adversary instead. Current techniques for authentication often rely on passwords, which have considerable drawbacks. Biometrics, visual passwords, or physical tokens provide better sources of secrets, but are noisy, and don’t give the same result each time they are accessed. The problem of using noisy sources for authentication has a rich history going back almost three decades. However, previous approaches were not usable with realistic noisy sources, because when the noise is high, then the communication needed for removing the noise may reveal too much of the secret to an adversary. Ben found approaches that tolerate the noise rather than remove it, considerably enlarging the class of secret noisy sources that can be used for key agreement. He has also demonstrated that information-theoretic analysis (i.e., analysis that does not rely on the fact that the adversary is computationally bounded) of the resulting security is inherently limited, and has developed techniques for proving security against more realistic, computationally-bounded, adversaries. His techniques have found applications to other areas of cryptography, including deterministic encryption.

Gonca Gürsun, PhD ’13
Gonca’s research focuses on identifying hidden features of the Internet. Her Ph.D. thesis applied machine learning and data mining methods to large-scale Internet measurements in order to demonstrate the feasibility of inferring important properties that are not directly measurable. In particular, she has studied the problem of inferring traffic volumes that are not directly measurable (“traffic matrix completion”) and estimating the effects of routing decisions that are not directly observable (“inferring visibility”). In a series of papers in top conferences, she showed significant progress on both problems. In papers in CoNEXT 2010 and IMC 2012, she showed that Internet traffic matrices are low rank (a necessary condition for matrix completion) and she studied which operators have the best vantage point from which to infer unmeasurable traffic. In papers in SIGCOMM 2012 and in another IMC 2012 paper, she showed how to infer the effects of distant routing decisions; in support of this goal she developed a new metric for analyzing Internet routing. This metric (RSD) has independent value as a tool for visualization and analysis of Internet routing, and was recognized with an IETF/IRTF Applied Networking Research Prize.

Vatche Ishakian, PhD ’13
Vatche’s research encompasses a large number of collaborators and spans a broad set of disciplines across networking, including application-level scheduling, network economics, data placement, and network architecture. His dissertation research focused on improving performance of the cloud, as perceived by networked applications. In his work on MORPHOSYS, Vatche developed new packing and scheduling methods to map workloads with complex quality-of-service constraints into regions of the cloud, work published at the IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Continuing on this line, his first-authored work at the ACM/IFIP/USENIX Middleware Conference received the Best Paper award. Here he demonstrated new methods for workload placement in the cloud using pricing mechanisms based on the Shapley value to map flexible workloads onto the more resource-elastic regions of the cloud. In a different domain, he devised new optimization techniques for content and filter placement problems published in VLDB 2012 and the ACM SIGKDD Conference in 2013, respectively.

Zheng Wu, PhD ’12
Zheng’s PhD dissertation significantly advances the state of knowledge on video-based multi-object tracking.  His dissertation is based on several first-authored research publications in the top conferences of the field of computer vision: CVPR 2011, ICCV 2009, WMVC 2009, and ECCV 2008. He was also co-author of papers published in ICPR 2010, PRIS 2010, MMBIA 2009, and NASB 2008.  With his steady stream of publications, he has established himself as an expert in designing single and multi-camera methods for tracking large numbers of tightly-spaced objects that rapidly move in two or three dimensions.  He has worked on developing algorithms for detection, segmentation, registration, and tracking of objects in visible-light, infrared, and phase-contrast microscopy.  His across-time and across-space multidimensional assignment algorithms employ iterative techniques from nonlinear optimization theory in creative ways.  His algorithmic contributions to computer vision range from designing greedy approximation algorithms, contour matching methods, network-flow techniques and set-cover techniques to handle challenging issues like occlusions, detection ambiguities, explosion of track hypotheses, and tracklet stitching. Zheng carefully tested the practicality of each of his algorithmic contributions in numerous experiments.  He validated that his methods can accurately reconstruct the 3D trajectories of flying bats and birds or walking pedestrians, the 2D tracks of living fibroblast cells, or the outlines of the fingers of a gesturing hand.  As part of his multi-disciplinary research, Zheng has participated in imaging field work in Texas, Massachusetts, and Rhode Island.  He implemented a comprehensive video analysis system, an impressive piece of software engineering, that enables the data analysis of collaborating biologists.  Zheng has served as an invaluable research mentor to more junior students in the IVC group.

Michalis Potamias, PhD’11
Michalis’s research has been on analyzing and querying large and complex graph structures with applications in biological and social networks. He
proposed new distance functions between nodes in probabilistic graphs and
he designed and implemented efficient algorithms to answer nearest
neighbor queries on very large probabilistic graphs. In addition, he
proposed and implemented a scalable and effective algorithm to cluster
massive probabilistic graphs using graph edit distance. Furthermore, he
proposed a model to quantify and explain information propagation in social
networks based on both endogenous and exogenous criteria. Finally, he has
worked on a number of other diverse areas including query optimization on
the cloud, indexing deterministic graphs, and indexing multimedia data.
His work has been published in top database venues including VLDB, ACM
SIGMOD, IEEE ICDE, and ACM CIKM. His work on shortest path distance estimation in large networks received the Best Student Paper Award in ACM CIKM 2009.

Georgios Zervas, PhD’11
Georgios’s research agenda is broad, and spans a wide spectrum of
technologies in the online economy, from sponsored search advertising and
second-price auctions, to modeling incentives in the link economy and the
blogosphere, to quantifying tradeoffs between the value of private
information and the ability to audit an untrusted third party. In his
research he combines mathematical modeling with data analysis of large and
original sources of data. An indicative example of Georgios’s work is his
recent paper published in the ACM Symposium on Electronic Commerce (EC’10). The paper presents a large-scale study of the leading pay-per-bid
auctioneer, Swoopo. This paper is the first to model information
asymmetries across players and capture the large margins made by Swoopo
and other sites. The mathematical models that capture such asymmetries are
combined with a large-scale data-analysis study on traces of tens of
thousands of auctions. The experiments validate findings from the models
and also study the effectiveness of behavioral strategies by participants,
such as the impact of aggressive bidding.

Bhavana Kanukurthi, PhD’11
Bhavana’s research has been on cryptographic key agreement protocols that do not rely on any computational assumptions but instead utilize minimal amounts of shared knowledge that the communicating parties possess. She has constructed the first such protocol to run in polynomial time (Eurocrypt 2009). She then further improved it, using techniques from error-correcting codes, to develop the first protocol in which the amount of initial shared knowledge required is only linear in the desired security (STOC 2010). With the help of undergraduates under her supervision, she developed an implementation of the protocol that demonstrated its applicability in practice. She has given several excellent talks on her work at top computer science departments around the world.

Kyle Burke, PhD’09
Kyle Burke’s research has been on games built upon mathematical theorems that are fundamental to Economics. Specifically, he designed two games, Atropos and Dictator. Atropos is based on Sperner’s lemma, one of the most important Fixed Point Theorems. The Dictator is based on Arrow’s theorem. The design of both games show great creativity. These games can be valuable for computer science and mathematics education. Kyle also obtained solid complexity results for both games.

Jorge Londono, PhD’10
Jorge Londono’s research focuses on optimization and game-theoretic approaches for embedding multiple overlay (virtual) networks into a single shared (physical) host network. This “network embedding” problem is central to emerging cloud computing and virtualization paradigms. From a system-centric perspective, Jorge devised solutions that aim to maximize the efficiency of the hosting network. From a user-centric perspective, Jorge devised solutions that recognize the selfish nature of the users and host. In both settings, Jorge’s contributions, which appeared in a number of papers, include theoretical results and empirical evaluation.

Gabe Parmer, PhD’09
Gabe Parmer’s research has focused on both mechanisms and policies that are central to the design of dependable and predictable software systems. In 2006, he co-authored a best-paper at IEEE RTAS, on the design of kernel- and user-level solutions for sandboxing application-specific real-time services. This was followed by the development of the “Hijack” infrastructure for Linux, that supported interposition of user-defined services on system calls and interrupts. In effect, this allowed users to define application-specific services to over-ride those of the underlying kernel, where appropriate, while ensuring the integrity of the core OS was not compromised. More recently, the work on Hijack has been used to implement a component-based system, called “Composite”, that features the notion of “mutable protection domains” (MPDs). MPDs essentially form adaptable isolation boundaries around software components, thereby influencing the communication cost between one component and another. This enables a system to adapt itself to the highest degree of isolation between components, thereby maximizing dependability, while ensuring timely execution. In 2007, Gabe had several notable first-author publications and presentations including at RTAS, RTSS, PDPTA and VMworld.

Jingbin Wang, PhD’07
Jingbin has shown excellent taste in selecting or defining the tough problems that are central in his field. His algorithms are not only theoretically interesting, but also solve important practical tasks. For example, his results on tracking and recognizing non-rigid hand motions are so far among the best in the world. His work in the area of image segmentation and object recognition appears in the proceedings of some highly competitive conferences and a journal. Some problems he worked on: 1. Recognizing objects with varying shape in images. Parts of such objects can appear in many different ways in an image and can even be occluded altogether. With his co-authors, he developed a probabilistic tool, “Hidden State Shape Models”, then (by himself) applied it to localize hands, fingers and other objects in heavily cluttered test images. 2. Combination of grouping image regions with shape-based object recognition; the resulting first-authored paper became very visible. 3. For the problem of locating the major lung fissures on CT (computer tomography), he discovered an elegant, probabilistic method to combine prior shape information with data. 4. He designed and independently wrote the code for an extensively used human-computer interaction system for visualization and processing of chest CT images.

Anukool Lakhina, PhD’06
Anukool has shown that analyzing traffic measurements from many points in the network simultaneously yields enormous leverage on a number of practical problems in networking. He has been the first to develop methods to do this. The work attracted attention at a series of top conferences, and results in an outstanding publication record that would be the envy of any junior faculty member (and a good start on a strong tenure case at a top-ranked school). While being theoretically grounded, it has immense practical value, since it is useful for identifying unusual operating conditions in networks, for predicting future traffic patterns, for estimating unavailable traffic measurements, and for diagnosing network intrusion and network abuse. The methods that Anukool has developed are quickly being adopted by other researchers; papers are already appearing that are applying his methods to other problems.

2003/04 Research Excellence Award Winners

• Vassilis Athitsos, PhD’06
  As a senior graduate student in the Image and Video Computing group at Boston University, Vassilis has been productive in a wide range of areas — computer vision, machine learning, pattern recognition, databases, and human-computer interfaces. He proposed a method for constructing embeddings for similarity indexing and nearest-neighbor classification.