Our research
Content type
+
Downloads (434)
+
Events (385)
 
Groups (149)
+
News (2544)
 
People (820)
 
Projects (1052)
+
Publications (11795)
+
Videos (5029)
Labs
Research areas
Algorithms and theory47205 (235)
Communication and collaboration47188 (182)
Computational linguistics47189 (168)
Computational sciences47190 (176)
Computer systems and networking47191 (642)
Computer vision208594 (24)
Data mining and data management208595 (31)
Economics and computation47192 (89)
Education47193 (77)
Gaming47194 (65)
Graphics and multimedia47195 (190)
Hardware and devices47196 (186)
Health and well-being47197 (68)
Human-computer interaction47198 (750)
Machine learning and intelligence47200 (670)
Mobile computing208596 (19)
Quantum computing208597 (6)
Search, information retrieval, and knowledge management47199 (590)
Security and privacy47202 (239)
Social media208598 (13)
Social sciences47203 (227)
Software development, programming principles, tools, and languages47204 (521)
Speech recognition, synthesis, and dialog systems208599 (34)
Technology for emerging markets208600 (24)
1–25 of 235
Sort
Show 25 | 50 | 100
1234567Next 
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Yoram Bachrach, Sofia Ceppi, Ian A. Kash, Peter Key, and David Kurokawa

We examine trade-offs among stakeholders in ad auctions. Our metrics are the revenue for the utility of the auctioneer, the number of clicks for the utility of the users and the welfare for the utility of the advertisers. We show how to optimize linear combinations of the stakeholder utilities, showing that these can be tackled through a GSP auction with a per-click reserve price. We then examine constrained optimization of stakeholder utilities.

We use simulations and analysis of real-world...

Publication details
Date: 1 June 2014
Type: Proceedings
Publisher: ACM
David B. Wilson and Uri Zwick

We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the outgoing and incoming adjacency lists of the vertices appear in non-decreasing order of weight. (Spira's algorithm makes the same assumption about the outgoing adjacency lists, but does not use incoming adjacency lists.) The running...

Publication details
Date: 1 June 2014
Type: Technical report
Publisher: Choose...
Number: MSR-TR-2014-77
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
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
Rakesh Agrawal, Maria Christoforaki, Sreenivas Gollapudi, Anitha Kannan, Krishnaram Kenthapadi, and Adith Swaminathan

We propose a system for mining videos from the web for supplementing the content of electronic textbooks in order to enhance their utility. Textbooks are generally organized into sections such that each section explains very few concepts and every concept is primarily explained in one section. Building upon these principles from the education literature and drawing upon the theory of Formal Concept Analysis, we define the focus of a section in terms of a few indicia, which themselves are combinations of...

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

Closeness centrality, first considered by Bavelas (1948), is an importance measure of nodes in social and massive graphs, which is based on the distances from the node to all other nodes. The classic definition, proposed by Bavelas (1950), Beauchamp (1965), and Sabidussi (1966), is (the inverse of) the average distance to all other nodes.

We propose the first highly scalable (near linear-time processing and linear space overhead) algorithm for estimating, within a small relative error, the...

Publication details
Date: 21 May 2014
Type: Technical report
Number: MSR-TR-2014-71
1–25 of 235
Sort
Show 25 | 50 | 100
1234567Next 
> Our research