The Perceptron Strikes Back (2007)
Richard Beigel, Nick Reingold, Daniel Spielman
We show that every AC 0 predicate is computed by a low-degree probabilistic polynomial over the reals. We show that circuits composed of a symmetric gate at the root with AND-OR subcircuits of...
Richard Beigel, Nick Reingold, Daniel Spielman, Order O
We show that every AC 0 predicate is computed by a low-degree probabilistic polynomial over the reals. We show that circuits composed of a symmetric gate at the root with AND-OR subcircuits of...
OPT versus LOAD in Dynamic Storage Allocation (2003)
Adam L. Buchsbaum, Howard Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup
Dynamic Storage Allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L = LOAD...
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...
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...
Off-line Algorithms for The List Update Problem (1996)
Nick Reingold, Jeffery Westbrook
Optimum off-line algorithms for the list update problem are investigated. The list update problem involves implementing a dictionary of items as a linear list. Several characterizations of optimum...
PP is closed under intersection (1995)
Richard Beigel, Nick Reingold, Daniel Spielman
In his seminal paper on probabilistic Turing machines, Gill [13] asked whether the class PP is closed under intersection and union. We give a positive answer to this question. We also show that PP is...
PP is closed under intersection (1995)
Richard Beigel, Nick Reingold, Daniel Spielman
In his seminal paper on probabilistic Turing machines, Gill [13] asked whether the class PP is closed under intersection and union. We give a positive answer to this question. We also show that PP is...
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...
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...
Off-line Algorithms for The List Update Problem (1995)
Nick Reingold, Jeffery Westbrook
Optimum off-line algorithms for the list update problem are investigated. The list update problem involves implementing a dictionary of items as a linear list. Several characterizations of optimum...
Page Migration Algorithms Using Work Functions (1994)
Marek Chrobak, Lawrence L. Larmore, Nick Reingold, Jeffery Westbrook
The page migration problem occurs in managing a globally addressed shared memory in a multiprocessor system. Each physical page of memory is located at a given processor, and memory references to...
Randomized competitive algorithms for the list update problem (1994)
Nick Reingold, Daniel D. Sleator
Abstract. We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is...
Universal Traversal Sequences (1993)
Joan Feigenbaum, Nick Reingold
this article we discuss a purely combinatorial problem, the construction of short universal traversal sequences, and its relationship to questions about logspace computation. We state the problem...
Randomized Competitive Algorithms for the List Update Problem (1992)
Nick Reingold, Jeffery Westbrook, Daniel D. Sleator
We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more...
PP is Closed Under Truth-Table Reductions (1991)
Beigel, Reingold and Spielman [2] showed that PP is closed under intersection and a variety of special cases of polynomial-time truth-table closure. We extend the techniques in [2] to show PP is...
PP is Closed Under Truth-Table Reductions (1991)
Beigel, Reingold and Spielman [BRS] showed that PP is closed under intersection and a variety of special cases of truth-table closure. We extend the techniques in [BRS] to show PP is closed under...