ABSTRACT Sketching Unaggregated Data Streams for Subpopulation-Size Queries (2009)
IP packet streams consist of multiple interleaving IP flows. Statistical summaries of these streams, collected for different measurement periods, are used for characterization of traffic, billing,...
Non-Deterministic Exponential Time has Two-Prover Interactive Protocols (2008)
Laszlo Babai, Lance Fortnow, Carsten Lund
We determine the exact power of two-prover inter-active proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful non-communicating provers...
Carsten Lund, Mihalis Yannakakis
Abstract. We prove results indicating that it is hard to compute efficiently good approximate solutions to the Graph Coloring, Set Covering and other related minimization problems. Specifi-cally,...
Noga Alon, Nick Duffield, Carsten Lund, Mikkel Thorup
Suppose we have a large table T of items i, each with a weight wi, e.g., people and their salary. In a general preprocessing step for estimating arbitrary subset sums, we assign each item a random...
Abstract Optimal Combination of Sampled Network Measurements (2008)
Nick Duffield, Carsten Lund, Mikkel Thorup
IP network traffic is commonly measured at multiple points in order that all traffic passes at least one observation point. The resulting measurements are subsequently joined for network analysis....
ABSTRACT Sketching Unaggregated Data Streams for Subpopulation-Size Queries (2008)
IP packet streams consist of multiple interleaving IP flows. Statistical summaries of these streams, collected for different measurement periods, are used for characterization of traffic, billing,...
Variance optimal sampling based estimation of subset sums (2008)
Cohen, Edith, Duffield, Nick, Kaplan, Haim, Lund, Carsten, Thorup, Mikkel
From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size $k$ that we can later use to estimate the total weight of arbitrary subsets. This is the...
Online Identification of Hierarchical Heavy Hitters: Algorithms, Evaluation, and Applications (2008)
Yin Zhang, Sumeet Singh, Subhabrata Sen, Nick Duffield, Carsten Lund
In traffic monitoring, accounting, and network anomaly detection, it is often important to be able to detect high-volume traffic clusters in near real-time. Such heavy-hitter traffic clusters are...
Nick Duffield, Carsten Lund, Mikkel Thorup
Abstract---IP flows have heavy-tailed packet and byte size distributions. This make them poor candidates for uniform sampling---i.e. selecting
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Mario Szegedy
We show that every language in NP has a probablistic verier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If a...
Learn More, Sample Less: Control of Volume and Variance in Network Measurement (2007)
Nick Duffield, Carsten Lund, Mikkel Thorup
objects 289-43596 . We wish to estimate the sums !#" %$ &('*)+& , of the sizes of objects of a given color , from a sampled subset of objects. How should the sampling distribution...
Algorithms and estimators for accurate summarization of Internet traffic (2007)
Statistical summaries of traffic in IP networks are at the heart of network operation and are used to recover information on arbitrary subpopulations of flows. It is therefore of great importance to...
Algorithms and estimators for accurate summarization of Internet traffic (2007)
Statistical summaries of traffic in IP networks are at the heart of network operation and are used to recover information on arbitrary subpopulations of flows. It is therefore of great importance to...
Richard Chang, Carsten Lund, William I. Gasarch
This paper investigates the computational complexity of approximating several NPoptimization problems using the number of queries to an NP oracle as a complexity measure. The results show a trade-off...
Algorithms and estimators for accurate summarization of Internet traffic (2007)
Statistical summaries of traffic in IP networks are at the heart of network operation and are used to recover information on arbitrary subpopulations of flows. It is therefore of great importance to...
Sampling to estimate arbitrary subset sums (2005)
Duffield, Nick, Lund, Carsten, Thorup, Mikkel
Starting with a set of weighted items, we want to create a generic sample of a certain size that we can later use to estimate the total weight of arbitrary subsets. For this purpose, we propose...
Estimating arbitrary subset sums with few probes (2005)
Noga Alon, Nick Duffield, Carsten Lund, Mikkel Thorup
Suppose we have a large table T of items i, each with a weight wi, e.g., people and their salary. In a general preprocessing step for estimating arbitrary subset sums, we assign each item a random...
Optimal Combination of Sampled Network Measurements (2005)
Nick Duffield, Carsten Lund, Mikkel Thorup
IP network traffic is commonly measured at multiple points in order that all traffic passes at least one observation point. The resulting measurements are subsequently joined for network analysis....
Yin Zhang, Matthew Roughan, Carsten Lund, David Donoho
Traffic matrices are required inputs for many IP network management tasks, such as capacity planning, traffic engineering and network reliability analysis. However, it is difficult to measure these...
Learn more, sample less: Control of volume and variance in network measurement (2005)
Nick Duffield, Carsten Lund, Mikkel Thorup
Abstract — This paper deals with sampling objects from a large stream. Each object possesses a size, and the aim is to be able to estimate the total size of an arbitrary subset of objects whose...
Yin Zhang, Matthew Roughan, Carsten Lund, David Donoho
Abstract — Traffic matrices are required inputs for many IP network management tasks, such as capacity planning, traffic engineering and network reliability analysis. However, it is difficult to...
An Information-Theoretic Approach to Traffic Matrix Estimation (2003)
Yin Zhang, Matthew Roughan, Carsten Lund, David Donoho
Traffic matrices are required inputs for many IP network management
An Information-Theoretic Approach to Traffic Matrix Estimation (2003)
Yin Zhang, Matthew Roughan, Carsten Lund, David Donoho
Traffic matrices are required inputs for many IP network management tasks: for instance, capacity planning, traffic engineering and network reliability analysis. However, it is difficult to measure...
An Information-Theoretic Approach to Traffic Matrix (2003)
Estimation Yin Zhang, Yin Zhang, Matthew Roughan, Carsten Lund, David Donoho
Traffic matrices are required inputs for many IP network management tasks: for instance, capacity planning, traffic engineering and network reliability analysis. However, it is difficult to measure...
An Information-Theoretic Approach to Traffic Matrix Estimation (2003)
Yin Zhang, Matthew Roughan, Carsten Lund, David Donoho
Traffic matrices are required inputs for many IP network management
This paper describes a measurement infrastructure used to collect detailed IP traffic measurements from an IP backbone. Usage, i.e, bytes transmitted, is determined from raw NetFlow records generated...
An Information-Theoretic Approach to Traffic Matrix Estimation (2003)
Yin Zhang, Matthew Roughan, Carsten Lund, David Donoho
Traffic matrices are required inputs for many IP network management
Properties and prediction of flow statistics from sampled packet streams (2002)
Nick Duffield, Carsten Lund, Mikkel Thorup
Abstract--- Many routers can generate and export statistics on flows of packets that traverse them. Increasingly, high end routers form flow statistics from only a sampled packet stream in order to...
Properties and Prediction of Flow Statistics from Sampled Packet Streams (2002)
Nick Duffield, Carsten Lund, Mikkel Thorup
Many routers can generate and export statistics on flows of packets that traverse them. Increasingly, high end routers form flow statistics from only a sampled packet stream in order to manage...
Deriving Traffic Demands for Operational IP networks: Methodology and Experience (2001)
Anja Feldmann, Albert Greenberg, Carsten Lund, Nick Reingold, Jennifer Rexford, Fred True
1. INTRODUCTION The engineering of large, IP backbone networks faces a number of difficult challenges. Owing to the astonishing success of Internet applications and the continuing rollout of faster...
Deriving Traffic Demands for Operational IP networks: Methodology and Experience (2001)
Anja Feldmann, Albert Greenberg, Carsten Lund, Nick Reingold, Jennifer Rexford, Fred True
Engineering a large IP backbone network without an accurate, network-wide view of the tra c demands is challenging. Shifts in user behavior, changes in routing policies, and failures of network...
Deriving Traffic Demands for Operational IP networks: Methodology and Experience (2001)
Anja Feldmann, Albert Greenberg, Carsten Lund, Nick Reingold, Jennifer Rexford, Fred True
Abstract--- Engineering a large IP backbone network without an accurate, network-wide view of the traffic demands is challenging. Shifts in user behavior, changes in routing policies, and failures of...
Deriving Traffic Demands for Operational IP networks: Methodology and Experience (2001)
Anja Feldmann, Albert Greenberg, Carsten Lund, Nick Reingold, Jennifer Rexford, Fred True
anja,albert,lund,reingold,jrex,ft¢
NetScope: Tra c Engineering for IP Networks (2000)
Anja Feldmann, Albert Greenberg, Carsten Lund, Nick Reingold, Jennifer Rexford
Managing large IP networks requires an understanding of the current tra c ows, routing policies, and network con guration. Yet, the state-of-the-art for managing IP networks involves manual con...
Deriving Traffic Demands for Operational IP Networks: Methodology and Experience (2000)
Anja Feldmann, Albert Greenberg, Carsten Lund, Nick Reingold, Jennifer Rexford, Fred True
Engineering a large IP backbone network without an accurate, network-wide view of the traffic demands is challenging. Shifts in user behavior, changes in routing policies, and failures of network...
NetScope: Traffic Engineering for IP Networks (1999)
Anja Feldmann, Albert Greenberg, Carsten Lund, Nick Reingold, Jennifer Rexford
Managing large IP networks requires an understanding of the current traffic flows, routing policies, and network configuration. Yet, the state-of-the-art for managing IP networks involves manual...
Competitive On-Line Algorithms for Distributed Data Management (1999)
Carsten Lund, Nick Reingold, Jeffery Westbrook, Dicky Yan
. Competitive on-line algorithms for data management in a network of processors are studied in this paper. A data object such as a file or a page of virtual memory is to be read and updated by...
Competitive On-Line Algorithms For Distributed Data Management (1999)
Carsten Lund, Nick Reingold, Jeffery Westbrook, Dicky Yan
.<F3.887e+05> Competitive on-line algorithms for data management in a network of processors are studied in this paper. A data object such as a file or a page of virtual memory is to be read and...
Paging Against a Distribution and IP Networking (1999)
Carsten Lund, Steven Phillips, Nick Reingold
In this paper we consider the paging problem when the page request sequence is drawn from a distribution, and give an application to computer networking. In the IP-paging problem the page...
On bounded queries and approximation (1997)
Richard Chang, William I. Gasarch, Carsten Lund
Abstract. This paper investigates the computational complexity of approximating several NPoptimization problems using the number of queries to an NP oracle as a complexity measure. The results show a...
On Bounded Queries and Approximation (1997)
Richard Chang, William I. Gasarch, Carsten Lund
This paper investigates the computational complexity of approximating several NPoptimization problems using the number of queries to an NP oracle as a complexity measure. The results show a trade-off...
Random Debaters and the Hardness of Approximating Stochastic Functions (1997)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
. A probabilistically checkable debate system (PCDS) for a language L consists of a probabilistic polynomial-time verifier V and a debate between Player 1, who claims that the input x is in L, and...
On Bounded Queries and Approximation (1997)
Richard Chang, William I. Gasarch, Carsten Lund
This paper investigates the computational complexity of approximating several NPoptimization problems using the number of queries to an NP oracle as a complexity measure. The results show a trade-off...
A Better Lower Bound on the Competitive Ratio of the Randomized 2-Server Problem (1997)
Marek Chrobak, Lawrence L. Larmore, Carsten Lund, Nick Reingold
We present a lower bound of 1+e \Gamma1=2 ß 1:6065 on the competitive ratio of randomized algorithms for the weighted 2-cache problem, which is a special case of the 2-server problem. This improves...
Hardness Of Approximations (1996)
Sanjeev Arora Carsten, Carsten Lund
This chapter is a self-contained survey of recent results about the hardness of approximating NP-hard optimization problems. 1 This chapter surveys recent results on the hardness of approximating NP-...
Hardness Of Approximations (1996)
This chapter is a self-contained survey of recent results about the hardness of approximating NP-hard optimization problems.
An Empirical Evaluation of Virtual Circuit Holding Time Policies in IP-over-ATM Networks (1995)
Keshav Carsten, S. Keshav, Carsten Lund, Steven Phillips, Nick Reingold, Huzur Saran
When carrying Internet Protocol (IP) traffic over an Asynchronous Transfer Mode (ATM) network, the ATM adaptation layer must determine how long to hold a virtual circuit opened to carry an IP...
Random Debaters and the Hardness of Approximating Stochastic Functions (1995)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
A probabilistically checkable debate system (PCDS) for a language L consists of a probabilistic polynomial-time verifier V and a debate between Player 1, who claims that the input x is in L, and...
Balanced Allocations for Tree-Like Inputs (1995)
Andrei Z. Broder, Alan Frieze, Carsten Lund, Steven Phillips, Nick Reingold
We consider the following procedure for constructing a directed tree on n vertices: The underlying undirected tree is fixed in advance but the edges of the tree are presented in a random order (all...
An Empirical Evaluation of Virtual Circuit Holding Time Policies in IP-Over-ATM Networks (1995)
Srinivasan Keshav, Carsten Lund, Steven Phillips, Nick Reingold, Huzur Saran
When carrying Internet Protocol (IP) traffic over an Asynchronous Transfer Mode (ATM) network, the ATM adaptation layer must determine how long to hold a virtual circuit opened to carry an IP...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1995)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
We initiate an investigation of probabilistically checkable debate systems (PCDS's), a natural generalization of probabilistically checkable proof systems. A PCDS for a language L consists of a...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1995)
Pankaj Agarwal, Joan Feigenbaum, Carsten Lund, Andrew Goldberg, Ketan Mulmuley, ...
We initiate an investigation of probabilistically checkable debate systems (PCDS), a natural generalization of probabilistically checkable proof systems (PCPS). A PCDS for a language L consists of a...
Richard Chang, Carsten Lund, William I. Gasarch
This paper investigates the computational complexity of approximating several NPoptimization problems using the number of queries to an NP oracle as a complexity measure. The results show a trade-off...
The power of adaptiveness and additional queries in random-self-reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
1 We look at relationships between adaptive and nonadaptive random-self-reductions. We also look at what happens to random-self-reductions if we restrict the number of queries they are allowed to...
Random Debaters and the Hardness of Approximating Stochastic Functions (1994)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
. A probabilistically checkable debate system (PCDS) for a language L consists of a probabilistic polynomial-time verifier V and a debate between Player 1, who claims that the input x is in L, and...
The Power Of Adaptiveness And Additional Queries In Random-Self-Reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
. We study random-self-reductions from a structural complexity -theoretic point of view. Specifically, we look at relationships between adaptive and nonadaptive random-self-reductions. We also look...
Alternation in Interaction (1994)
Marcos Kiwi, Carsten Lund, Alexander Russell, C. Lund, Ravi Sundaram, A. Russell, ...
We study competing-prover one-round interactive proof systems. We show that one-round proof systems in which the first prover is trying to convince a verifier to accept and the second prover is...
Practical Zero-Knowledge Proofs: Giving Hints and Using Deficiencies (1994)
Joan Boyar, Katalin Friedl, Carsten Lund
New zero-knowledge proofs are given for some number-theoretic problems. All of the problems are in NP, but the proofs given here are much more efficient than the previously known proofs. In addition,...
The Power Of Adaptiveness And Additional Queries In Random-Self-Reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
. We study random-self-reductions from a structural complexity -theoretic point of view. Specifically, we look at relationships between adaptive and nonadaptive random-self-reductions. We also look...
The Power of Adaptiveness and Additional Queries in Random-Self-Reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
. We study random-self-reductions from a structural complexity -theoretic point of view. Specifically, we look at relationships between adaptive and nonadaptive random-self-reductions. We also look...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1993)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
We initiate an investigation of probabilistically checkable debate systems (PCDS's), a natural generalization of probabilistically checkable proof systems. A PCDS for a language L consists of a...
Random Debaters and the Hardness of Approximating Stochastic Functions (1993)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
A probabilistically checkable debate system (PCDS) for a language L consists of a probabilistic polynomial-time verifier V and a debate between Player 1, who claims that the input x is in L, and...
On the Hardness of Computing the Permanent of Random Matrices (1992)
Abstract. Extending a line of research initiated by Lipton, we study the complexity of computing the permanent of random n by n matrices with integer values between 0 and p \Gamma 1, for any suitably...
Proof verification and hardness of approximation problems (1992)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Mario Szegedy
The class PCP(f(n); g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that uses O(f(n)) random bits, queries O(g(n)) bits of its oracle and...
Proof verification and hardness of approximation problems (1992)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If...
Algebraic Methods for Interactive Proof Systems (1992)
Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan
We present a new algebraic technique for the construction of interactive proof systems. We use our technique to prove that every language in the polynomial-time hierarchy has an interactive proof...
Proof Verification and Hardness of Approximation Problems (1992)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
The class PCP(f(n); g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that uses O(f(n)) random bits, queries O(g(n)) bits of its oracle and...
Proof verification and hardness of approximation problems (1992)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If...
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols (1991)
László Babai, Lance Fortnow, Carsten Lund
. We determine the exact power of two-prover interactive proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers...
Interactive Proof Systems And Alternating Time-Space Complexity (1991)
. We show a rough equivalence between alternating time-space complexity and a public-coin interactive proof system with the verifier having a polynomial related time-space complexity. Special cases...
The Power Of Interaction (1991)
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : vii Chapter 1. INTRODUCTION : : : : : : : : : : : : : : : : : : : : : : : : : 1 2. PRELIMINARIES : : : : : : : : : : : : : : : : : : :...
Algebraic Methods for Interactive Proof Systems (1990)
Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan
We present a new algebraic technique for the construc-tion of interactive proof systems. We use our technique to prove that every language in the polynomial-time hierarchy has an interactive proof...