Our research
Content type
+
Downloads (434)
+
Events (385)
 
Groups (149)
+
News (2551)
 
People (821)
 
Projects (1052)
+
Publications (11811)
+
Videos (5060)
Labs
Research areas
Algorithms and theory47205 (238)
Communication and collaboration47188 (182)
Computational linguistics47189 (169)
Computational sciences47190 (180)
Computer systems and networking47191 (646)
Computer vision208594 (24)
Data mining and data management208595 (38)
Economics and computation47192 (89)
Education47193 (77)
Gaming47194 (65)
Graphics and multimedia47195 (190)
Hardware and devices47196 (186)
Health and well-being47197 (68)
Human-computer interaction47198 (752)
Machine learning and intelligence47200 (672)
Mobile computing208596 (20)
Quantum computing208597 (7)
Search, information retrieval, and knowledge management47199 (590)
Security and privacy47202 (251)
Social media208598 (13)
Social sciences47203 (228)
Software development, programming principles, tools, and languages47204 (523)
Speech recognition, synthesis, and dialog systems208599 (36)
Technology for emerging markets208600 (24)
1–25 of 238
Sort
Show 25 | 50 | 100
1234567Next 
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Shipra Agrawal and Nikhil R. Devanur

In this paper, we consider a very general model for exploration-exploitation tradeoff which allows arbitrary concave rewards and convex constraints on the decisions across time, in addition to the customary limitation on the time horizon. This model subsumes the classic multi-armed bandit (MAB) model, and the Bandits with Knapsacks (BwK) model of Badanidiyuru et al.[2013]. We also consider an extension of this model to allow linear contexts, similar to the linear contextual extension of the MAB model....

Publication details
Date: 1 June 2014
Type: Inproceeding
Publisher: ACM conference on Economics and Computation
Loris D'Antoni, Margus Veanes, Benjamin Livshits, and David Molnar

Tree automata and tree transducers are used in a wide range of applications in software engineering, from XML processing to language type-checking. While these formalisms are of immense practical use, they can only model finite alphabets, and since many real-world applications operate over infinite domains such as integers, this is often a limitation. To overcome this problem we augment tree automata and transducers with symbolic alphabets represented as parametric theories. Admitting infinite alphabets...

Publication details
Date: 1 June 2014
Type: Inproceeding
Publisher: ACM
Daniel Delling, Andrew V. Goldberg, Ruslan Savchenko, and Renato F.Werneck

The Hub Labeling algorithm (HL) is an exact shortest path algorithm with excellent query performance on some classes of problems. It precomputes some auxiliary information (stored as a label) for each vertex, and its query performance depends only on the label size. While there are polynomial-time approximation algorithms to find labels of approximately optimal size, practical solutions use hierarchical hub labels (HHL), which are faster to compute but offer no guarantee on the label...

Publication details
Date: 1 June 2014
Type: Inproceeding
Publisher: Springer
Margus Veanes

Implementing string transformation routines, such as encoders, decoders, and sanitizers, correctly and efficiently is a difficult and error prone task. Such routines are often used in security critical settings, process large amounts of data, and must work efficiently and correctly. We introduce a new declarative language called Bex that builds on elements of regular expressions, symbolic automata and transducers, and enables a compilation scheme into C, C# or JavaScript that avoids many of the...

Publication details
Date: 1 June 2014
Type: Inproceeding
Publisher: Springer Verlag
Frank Kelly, Peter Key, and Neil Walton

We consider a large-scale Ad-auction where adverts are assigned over a potentially infinite number of searches. We capture the intrinsic asymmetries in information between advertisers, the advert platform and the space of searches: advertisers know and can optimize the average performance of their advertisement campaign; the platform knows and can optimize on each search instance; and, neither party knows the distribution of the infinite number of searches that can occur. We look at maximizing the...

Publication details
Date: 1 June 2014
Type: Inproceeding
Publisher: ACM Electronic Commerce
Qihang Lin and Lin Xiao

We consider optimization problems with an objective function that is the sum of two convex terms: one is smooth and given by a black-box oracle, and the other is general but with a simple, known structure. We first present an accelerated proximal gradient (APG) method for problems where the smooth part of the objective function is also strongly convex. This method incorporates an efficient line-search procedure, and achieves the optimal iteration complexity for such composite optimization problems. In...

Publication details
Date: 1 June 2014
Type: Inproceeding
Edith Cohen

Graph datasets with billions of edges, such as social and Web graphs, are prevalent. To be feasible, computation on such large graphs should scale linearly with graph size. All-distances sketches (ADSs) are emerging as a powerful tool for scalable computation of some basic properties of individual nodes or the whole graph.

ADSs were first proposed two decades ago (Cohen 1994) and more recent algorithms include ANF (Palmer, Gibbons, and Faloutsos 2002) and hyperANF (Boldi, Rosa, and Vigna...

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