Our research
Content type
+
Downloads (435)
+
Events (391)
 
Groups (149)
+
News (2563)
 
People (823)
 
Projects (1051)
+
Publications (11870)
+
Videos (5116)
Labs
Research areas
Algorithms and theory47205 (247)
Communication and collaboration47188 (182)
Computational linguistics47189 (173)
Computational sciences47190 (180)
Computer systems and networking47191 (659)
Computer vision208594 (29)
Data mining and data management208595 (51)
Economics and computation47192 (93)
Education47193 (78)
Gaming47194 (67)
Graphics and multimedia47195 (191)
Hardware and devices47196 (187)
Health and well-being47197 (70)
Human-computer interaction47198 (762)
Machine learning and intelligence47200 (696)
Mobile computing208596 (24)
Quantum computing208597 (8)
Search, information retrieval, and knowledge management47199 (604)
Security and privacy47202 (256)
Social media208598 (13)
Social sciences47203 (228)
Software development, programming principles, tools, and languages47204 (529)
Speech recognition, synthesis, and dialog systems208599 (44)
Technology for emerging markets208600 (24)
1–25 of 247
Sort
Show 25 | 50 | 100
1234567Next 
Edith Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Danny Raz, and Yoav Tzur

Most discovery systems for silent failures work in two phases: a continuous monitoring phase that detects presence of failures through probe packets and a localization phase that pinpoints the faultyelement(s). We focus on the monitoring phase, where the goal is to balance the probing overhead with the cost associated with longer failure detection times.

We formulate a general model for the underlying fundamental subset-test scheduling problem. We unify the treatment of schedulers and cost...

Publication details
Date: 1 October 2014
Type: Technical report
Publisher: Elsevier
Number: MSR-TR-2014-113
Abhimanyu Das, Sreenivas Gollapudi, Arindam Khan, and Renato Paes Leme

Social networks serve as important platforms for users to express, exchange and form opinions on various topics. Several opinion dynamics models have been proposed to characterize how a user iteratively updates her expressed opinion based on her innate opinion and the opinion of her neighbors. The extent to how much a user is influenced by her neighboring opinions, as opposed to her own innate opinion, is governed by a measure of her “conformity’ parameter. Characterizing this degree of conformity for...

Publication details
Date: 1 October 2014
Type: Inproceeding
Publisher: Proc. Intl. Conference on Social Networks (COSN)
Publication details
Date: 1 October 2014
Type: Inproceeding
Publisher: European Association for Theoretical Computer Science
Kshipra Bhawalkar, Sreenivas Gollapudi, and Debmalya Panigrahi

We consider a generic online allocation problem that generalizes the classical online set cover framework by considering requests comprising a set of elements rather than a single element. This problem has multiple applications in cloud computing, crowd sourcing, facility planning, etc. Formally, it is an online covering problem where each online step comprises an offline covering problem. In addition, the covering sets are capacitated, leading to packing constraints. We give a randomized algorithm for...

Publication details
Date: 4 September 2014
Type: Inproceeding
Publisher: Leibniz International Proceedings in Informatics
Yoram Bachrach, Vasilis Syrgkanis, Eva Tardos, and Milan Vojnovic

We introduce a framework for studying the effect of cooperation on the quality of outcomes in utility games. Our framework is a coalitional analog of the smoothness framework of non-cooperative games. Coalitional smoothness implies bounds on the strong price of anarchy, the loss of quality of coalitionally stable outcomes. Our coalitional smoothness framework captures existing results bounding the strong price of anarchy of network design games. Moreover, we give novel strong price of anarchy results...

Publication details
Date: 1 September 2014
Type: Inproceeding
Publisher: Springer
Markus N. Rabe, Christoph M. Wintersteiger, Hillel Kugler, Boyan Yordanov, and Youssef Hamadi

We present a novel technique to analyze the bounded reachability probability problem for large Markov chains. The essential idea is to incrementally search for sets of paths that lead to the goal region and to choose the sets in a way that allows us to easily determine the probability mass they represent. To effectively analyze the system dynamics using an SMT solver, we employ a finite-precision abstraction on the Markov chain and a custom quantifier elimination strategy. Through experimental...

Publication details
Date: 1 September 2014
Type: Inproceeding
Publisher: Springer
Dan Alistarh, James Aspnes, Valerie King, and Jared Saia

We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary.

We describe a new randomized consensus protocol for this model with expected message...

Publication details
Date: 1 September 2014
Type: Technical report
Publisher: Choose...
Number: MSR-TR-2014-15
Joppe W. Bos, Craig Costello, Michael Naehrig, and Douglas Stebila

Lattice-based cryptographic primitives are believed to offer resilience against attacks by quantum computers. We demonstrate the practicality of post-quantum key exchange by constructing ciphersuites for the Transport Layer Security (TLS) protocol that provide key exchange based on the ring learning with errors (R-LWE) problem; we accompany these ciphersuites with a rigorous proof of security. Our approach ties lattice-based key exchange together with traditional authentication using...

Publication details
Date: 5 August 2014
Type: Technical report
Publisher: Choose...
Number: MSR-TR-2014-107
Edith Cohen

Distance queries are a basic tool in data analysis. They are used for detection and localization of change for the purpose of anomaly detection, monitoring, or planning. Distance queries are particularly useful when data sets such as measurements, snapshots of a system, content, traffic matrices, and activity logs are collected repeatedly.

Random sampling, which can be efficiently performed over streamed or distributed data, is an important tool for scalable data analysis. The sample...

Publication details
Date: 1 August 2014
Type: Technical report
Publisher: ACM – Association for Computing Machinery
Number: MSR-TR-2014-111
Dan Alistarh, Rati Gelashvili, and Adrian Vladu

We give message-optimal randomized algorithms for two fundamental
distributed assignment tasks, leader election and renaming.
In leader election, all n participants compete for a single item, whereas in renaming the n participants
each compete for one of n distinct items, or names.
The setting is the classic asynchronous message-passing model, where the n
processors communicate over unreliable channels, while timing and t < n / 2 processor crashes are controlled
by a...

Publication details
Date: 1 August 2014
Type: Technical report
Publisher: Choose...
Number: MSR-TR-2014-18
Konstantin Korovin and Margus Veanes

Combining classical automated theorem proving techniques with theory based reasoning, such as satisfiability modulo theories, is a new approach to first-order reasoning modulo theories. Skolemization is a classical technique used to transform first-order formulas into equisatisfiable form. We show how Skolemization can benefit from a new satisfiability modulo theories based simplification technique of formulas called monadic decomposition. The technique can be used to transform a theory dependent...

Publication details
Date: 1 August 2014
Type: Inproceeding
Publisher: Springer
Edith Cohen, Daniel Delling, Thomas Pajor, and Renato Werneck

Propagation of contagion through networks is a fundamental process. It is used to model the spread of information, influence, or a viral infection. Diffusion patterns can be specified by a probabilistic model, such as Independent Cascade (IC), or captured by a set of representative traces.

Basic computational problems in the study of diffusion are influence queries (determining the potency of a specified seed set of nodes) and Influence Maximization (identifying the...

Publication details
Date: 1 August 2014
Type: Technical report
Publisher: Microsoft Research
Number: MSR-TR-2014-110
Florian Bourse, Marc Lelarge, and Milan Vojnovic

Balanced edge partition has emerged as a new approach to partition an input graph data for the purpose of scaling out parallel computations, which is of interest for several modern data analytics computation platforms, including platforms for iterative computations, machine learning problems, and graph databases. This new approach stands in a stark contrast to the traditional approach of balanced vertex partition, where for given number of partitions, the problem is to minimize the number of edges cut...

Publication details
Date: 1 August 2014
Type: Inproceeding
Publisher: ACM – Association for Computing Machinery
Fisher J., Piterman N., and Rastislav Bodik
Publication details
Date: 1 August 2014
Type: Article
Publisher: .
Wilkinson A., Kawata V.K.S., Schütte J., Gao X., Antoniou S., Baumann C., Woodhouse S., Hannah R., Tanaka Y., Swiers G., Moignard V., Fisher J., Hidetoshi S., Tijssen M.R., de Bruijn M.F.T.R., Liu P., and Göttgens B.
Publication details
Date: 1 August 2014
Type: Article
Publisher: The Company of Biologists
Karthick Jayaraman, Nikolaj Bjrner, Geoff Outhred, and Charlie Kaufman

Network connectivity policies are crucial for assuring the security and availability of large-scale datacenter. Managing these policies is fraught with complexity and operator errors. The difficulties are exacerbated when deploying large scale offerings of public cloud services where multiple tenants are hosted within customized isolation boundaries. In these large-scale settings it is impractical to depend on human effort or trial and error to maintain the correctness and consistency of...

Publication details
Date: 26 July 2014
Type: Technical report
Publisher: Microsoft Research
Number: MSR-TR-2014-102
Edith Cohen

Random samples are lossy summaries which allow queries posed over the data to be approximated by applying an appropriate estimator to the sample. The effectiveness of sampling, however, hinges on estimator selection. The choice of estimators is subjected to global requirements, such as unbiasedness and range restrictions on the estimate value, and ideally, we seek estimators that are both efficient to derive and apply and admissible (not dominated, in terms of variance, by other estimators). ...

Publication details
Date: 1 July 2014
Type: Proceedings
Publisher: ACM
Long Tran-Thanh, Lampros Stavrogiannis, Victor Naroditskiy, Valentin Robu, Nicholas R Jennings, and Peter Key

We study the problem of an advertising agent who needs to intelligently distribute her budget across a sequence of online keyword bidding auctions. We assume the closing price of each auction is governed by the same unknown distribution, and study the problem of making provably optimal bidding decisions. Learning the distribution is done under censored observations, i.e. the closing price of an auction is revealed only if the bid we place is above it. We consider three algorithms, namely...

Publication details
Date: 1 July 2014
Type: Inproceeding
Publisher: AUAI
Margus Veanes, Nikolaj Bjorner, Lev Nachmanson, and Sergey Bereg

Monadic predicates play a prominent role in many decidable cases, including decision procedures for symbolic automata. We are here interested in discovering whether a formula can be rewritten into a Boolean combination of monadic predicates. Our setting is quantifier-free formulas over a decidable background theory, such as arithmetic and we here develop a semi-decision procedure for extracting a monadic decomposition of a formula when it exists.

Publication details
Date: 1 July 2014
Type: Inproceeding
Publisher: Springer
Tomáš Kocák, Michal Valko, Rémi Munos, and Shipra Agrawal
Publication details
Date: 1 July 2014
Type: Article
Publisher: AAAI - Association for the Advancement of Artificial Intelligence
Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck

We present a versatile and scalable algorithm for computing exact distances on real-world networks with tens of millions of arcs in real time. Unlike existing approaches, preprocessing and queries are practical on a wide variety of inputs, such as social, communication, sensor, and road networks. We achieve this by providing a unified approach based on the concept of 2-hop labels, improving upon existing methods. In particular, we introduce a fast sampling-based algorithm to order vertices by...

Publication details
Date: 1 July 2014
Type: Technical report
Publisher: Microsoft Technical Report
Number: MSR-TR-2014-12
Qihang Lin, Zhaosong Lu, and Lin Xiao

We consider the problem of minimizing the sum of two convex functions: one is smooth and given by a gradient oracle, and the other is separable over blocks of coordinates and has a simple known structure over each block. We develop an accelerated randomized proximal coordinate gradient (APCG) method for minimizing such convex composite functions. For strongly convex functions, our method achieves faster linear convergence rates than existing randomized proximal coordinate gradient methods. Without...

Publication details
Date: 1 July 2014
Type: Technical report
Publisher: Microsoft Research
Number: MSR-TR-2014-94
Aleksandar Zeljic, Christoph M. Wintersteiger, and Philipp Rummer

We consider the problem of efficiently computing models for satisfiable constraints, in the presence of complex background theories such as oating-point arithmetic. Model construction has various applications, for instance the automatic generation of test inputs. It is well-known that naive encoding of constraints into simpler theories (for instance, bit-vectors or propositional logic) can lead to a drastic increase in size, and be unsatisfactory in terms of memory and runtime needed for model...

Publication details
Date: 1 July 2014
Type: Inproceeding
Publisher: Springer
Shaolei Ren, Yuxiong He, and Kathryn McKinley

To improve performance and meet power constraints, vendors are introducing heterogeneous multicores that combine high performance and low power cores. However, choosing which cores and scheduling applications on them remain open problems. This paper presents a scheduling algorithm that provably minimizes energy on heterogeneous multicores and meets latency constraints for interactive applications, such as search, recommendations, advertisements, and games. Because interactive applications must...

Publication details
Date: 1 July 2014
Type: Technical report
Publisher: Choose...
Number: MSR-TR-2014-101
Davd Poulin, M.B. Hastings, Dave Wecker, Nathan Wiebe, Andrew C. Doherty, and Matthias Troyer

The simulation of molecules is a widely anticipated application of quantum computers. However, recent studies have cast a shadow on this hope by revealing that the complexity in gate count of such simulations increases with the number of spin orbitals N as N^8, which becomes prohibitive even for molecules of modest size N~100 . This study was partly based on a scaling analysis of the Trotter step required for an ensemble of random artificial molecules. Here, we revisit this analysis and find instead...

Publication details
Date: 19 June 2014
Type: Article
Publisher: arXiv
1–25 of 247
Sort
Show 25 | 50 | 100
1234567Next 
> Our research