Papers.

A theory of serial entrepreneurship

Algorithms on ensemble quantum computers

In ensemble (or bulk) quantum computation, all computations are performed on an ensemble of computers rather than on a single computer. Measurements of qubits in an individual computer cannot be performed; instead, only expectation values (over the complete ensemble of computers) can be measured. As a result of this limitation on the model of computation, many algorithms cannot be processed directly on such computers, and must be modified, as the common strategy of delaying the measurements usually does not resolve this ensemble-measurement problem. Here we present several new strategies for resolving this problem. Based on these strategies we provide new versions of some of the most important quantum algorithms, versions that are suitable for implementing on ensemble quantum computers, e.g., on liquid NMR quantum computers. These algorithms are Shor’s factorization algorithm, Grover’s search algorithm (with several marked items), and an algorithm for quantum fault-tolerant computation. The first two algorithms are simply modified using a randomizing and a sorting strategies. For the last algorithm, we develop a classical-quantum hybrid strategy for removing measurements. We use it to present a novel quantum fault-tolerant scheme. More explicitly, we present schemes for fault-tolerant measurement-free implementation of Toffoli and $$\sigma_{z}^{1/4},$$ as these operations cannot be implemented “bitwise”, and their standard fault-tolerant implementations require measurement.

Fault Table Computation on GPUs

Special issue of The Journal of Information Retrieval on web mining for search

Bigger, Better, Faster, More at the LHC

The Cosmology of Composite Inelastic Dark Matter

Gravity-Based Robotic Cloth Folding

LQG-Based Planning, Sensing, and Control of Steerable Needles

Taking Learning Out of Real-Time Heuristic Search for Video-Game Pathfinding.

Middleware for a Re-configurable Distributed Archival Store Based on Secret Sharing

Modern storage systems are often faced with complex trade-offs between the confidentiality, availability, and performance they offer their users. Secret sharing is a data encoding technique that provides information-theoretically provable guarantees on confidentiality unlike conventional encryption. Additionally, secret sharing provides quantifiable guarantees on the availability of the encoded data. We argue that these properties make secret sharing-based encoding of data particularly suitable for the design of increasingly popular and important distributed archival data stores. These guarantees, however, come at the cost of increased resource consumption during reads/writes. Consequently, it is desirable that such a storage system employ techniques that could dynamically transform data representation to operate the store within required confidentiality, availability, and performance regimes (or budgets) despite changes to the operating environment. Since state-of-the-art transformation techniques suffer from prohibitive data transfer overheads, we develop a middleware for dynamic data transformation. Using this, we propose the design and operation of a secure, available, and tunable distributed archival store called FlexArchive. Using a combination of analysis and empirical evaluation, we demonstrate the feasibility of our archival store. In particular, we demonstrate that FlexArchive can achieve dynamic data re-configurations in significantly lower times (factor of 50 or more) without any sacrifice in confidentiality and with a negligible loss in availability (less than 1%).

A Model for Automatic Generation of Multi-partite Graphs from Arbitrary Data

Temporal Analysis of Document Collections: Framework and Applications

Mining Large Query Induced Graphs towards a Hierarchical Query Folksonomy

Digitale Produktion via Enterprise Application Integration

Searching the Web of Objects

Retrieval Evaluation in Practice

Coniunge et Impera: Multiple-Graph Mining for Query-Log Analysis

Visualizing Threaded Conversation Networks: Mining Message Boards and Email Lists for Actionable Insights

Positional Communication and Private Information in Honeybee Foraging Models

An Empirical Study of Optimization for Maximizing Diffusion in Networks

Sampling Bias in BitTorrent Measurements

Web Advertising

Advances in Social Network Mining and Analysis

Web Structure Mining

Adding Dynamic Types to C#

gradienTv: Market-Based P2P Live Media Streaming on the Gradient Overlay

Conclusions and Further Research

Applications

User-Centric Evaluation

Network-Centric Evaluation

Evaluation Metrics

The Long Tail in Recommender Systems

Music Recommendation

The Recommendation Problem

Introduction

Music Recommendation and Discovery

Towards a Distributed Search Engine

Fast Intersection Algorithms for Sorted Sequences

Chapter 2: Next Generation Web Search

Crowdsourcing Assessments for XML Ranked Retrieval

A Language Modeling Approach for Temporal Information Needs

This work addresses information needs that have a temporal dimension conveyed by a temporal expression in the user’s query. Temporal expressions such as “in the 1990s” are frequent, easily extractable, but not leveraged by existing retrieval models. One challenge when dealing with them is their inherent uncertainty. It is often unclear which exact time interval a temporal expression refers to. We integrate temporal expressions into a language modeling approach, thus making them first-class citizens of the retrieval model and considering their inherent uncertainty. Experiments on the New York Times Annotated Corpus using Amazon Mechanical Turk to collect queries and obtain relevance assessments demonstrate that our approach yields substantial improvements in retrieval effectiveness.

A Social Network Analysis Approach to Detecting Suspicious Online Financial Activities

Effect of Humans on Belief Propagation in Large Heterogeneous Teams

Self-Organized Criticality of Belief Propagation in Large Heterogeneous Teams

Are posttraumatic stress disorder mental health terms found in SNOMED‐CT medical terminology

Capacity Planning for Vertical Search Engines

GraphLab: A New Framework For Parallel Machine Learning

Designing and implementing efficient, provably correct parallel machine learning (ML) algorithms is challenging. Existing high-level parallel abstractions like MapReduce are insufficiently expressive while low-level tools like MPI and Pthreads leave ML experts repeatedly solving the same design challenges. By targeting common patterns in ML, we developed GraphLab, which improves upon abstractions like MapReduce by compactly expressing asynchronous iterative algorithms with sparse computational dependencies while ensuring data consistency and achieving a high degree of parallel performance. We demonstrate the expressiveness of the GraphLab framework by designing and implementing parallel versions of belief propagation, Gibbs sampling, Co-EM, Lasso and Compressed Sensing. We show that using GraphLab we can achieve excellent parallel performance on large scale real-world problems.

New Physics at the LHC. A Les Houches Report: Physics at TeV Colliders 2009 - New Physics Working Group

Addressing the P2P Bootstrap Problem for Small Networks

Peer-to-Peer (P2P) overlays provide a framework for building distributed applications consisting of few to many resources with features including self-configuration, scalability, and resilience to node failures. Such systems have been successfully adopted in large-scale Internet services for content delivery networks, file sharing, and data storage. In small-scale systems, they can be useful to address privacy concerns as well as support for network applications that lack dedicated servers. The bootstrap problem, finding an existing peer in the overlay, remains a challenge to enabling these services for small-scale P2P systems. In large networks, the solution to the bootstrap problem has been the use of dedicated services, though creating and maintaining these systems requires expertise and resources, which constrain their usefulness and make them unappealing for small-scale systems. This paper surveys and summarizes requirements that allow peers potentially constrained by network connectivity to bootstrap small-scale overlays through the use of existing public overlays. In order to support bootstrapping, a public overlay must support the following requirements: a method for reflection in order to obtain publicly reachable addresses, so peers behind network address translators and firewalls can receive incoming connection requests; communication relaying to share public addresses and communicate when direct communication is not feasible; and rendezvous for discovering remote peers, when the overlay lacks stable membership. After presenting a survey of various public overlays, we identify two overlays that match the requirements: XMPP overlays, such as Google Talk and Live Journal Talk, and Brunet, a structured overlay based upon Symphony. We present qualitative experiences with prototypes that demonstrate the ability to bootstrap small-scale private structured overlays from public Brunet or XMPP infrastructures.

Observability of the total inflationary expansion

I consider the question of possible observability of the total number of e-folds accumulated during the epoch of inflation. The total number of observable e-folds has been previously constrained by the de Sitter entropy after inflation, assuming that the null energy condition (NEC) holds. The NEC is violated by upward fluctuations of the local Hubble rate, which occur with high probability in the fluctuation-dominated regime of inflation. These fluctuations lead at late times to the formation of black holes and thus limit the observability of inflationary evolution. I compute the maximum number <Delta N> of e-folds that can be observed in principle through measurements of the CMB at arbitrarily late times (if the dark energy disappears). The calculation also provides a reasonably precise definition of the boundary of the fluctuation-dominated regime, with an uncertainty of a few percent. In simple models of single-field inflation compatible with current CMB observations, I find <Delta N> of order 10^5. This upper bound on the observable e-folds, although model-dependent, is much smaller than the de Sitter entropy after inflation. The method of calculation can be used in other models of single-field inflation.