Carsten Lund

SODA Conference 2009 Conference Paper

Stream sampling for variance-optimal estimation of subset sums

• Edith Cohen
• Nick G. Duffield
• Haim Kaplan
• Carsten Lund
• Mikkel Thorup

STOC Conference 1994 Conference Paper

Efficient probabilistic checkable proofs and applications to approximation

• Mihir Bellare
• Shafi Goldwasser
• Carsten Lund
• Alexander Russell

FOCS Conference 1994 Conference Paper

IP over connection-oriented networks and distributional paging

• Carsten Lund
• Steven J. Phillips
• Nick Reingold

Next generation wide area network are very likely to use connection-oriented protocols such as Asynchronous Transfer Mode (ATM). For the huge existing investment in current IP networks such as the Internet to remain useful, me must devise mechanisms to carry IP traffic over connection-oriented networks. A basic issue is to devise holding policies for virtual circuits carrying datagrams. In this paper we consider two variants of the paging problem that arise in the design of such holding policies. In the IP-paging problem the page inter-request times are chosen according to independent distributions. For this model we construct a very simple deterministic algorithm whose page fault rate is at most 5 times that of the best online algorithm (that knows the inter-request time distributions). We also show that some natural algorithms for this problem do not have constant competitive ratio. In distributional paging the inter-request time distributions may be dependent, and hence any probabilistic model of page request sequences can be represented. We construct a simple randomized algorithm whose page fault rate is at most 4 times that of the best online algorithm. >

SODA Conference 1994 Conference Paper

Linear Programs for Randomized On-Line Algorithms

• Carsten Lund
• Nick Reingold

STOC Conference 1993 Conference Paper

Efficient probabilistically checkable proofs and applications to approximations

• Mihir Bellare
• Shafi Goldwasser
• Carsten Lund
• Alexander Russell

TCS Journal 1993 Journal Article

Interactive proof systems and alternating time—space complexity

• Lance Fortnow
• Carsten Lund

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 include the following: • All of NC has interactive proofs, with a log-space polynomial-time public-coin verifier vastly improving the best previous lower bound of LOGCFL for this model (Fortnow and Sipser, 1988). • All languages in P have interactive proofs with a polynomial-time public-coin verifier using o(log2 n) space. • All exponential-time languages have interactive proof systems with public-coin polynomial-space exponential-time verifiers. To achieve better bounds, we show how to reduce a k-tape alternating Turing machine to a 1-tape alternating Turing machine with only a constant factor increase in time and space.

STOC Conference 1993 Conference Paper

On the hardness of approximating minimization problems

• Carsten Lund
• Mihalis Yannakakis

STOC Conference 1993 Conference Paper

Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions

• Anne Condon
• Joan Feigenbaum
• Carsten Lund
• Peter W. Shor

STOC Conference 1992 Conference Paper

On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract)

• Uriel Feige
• Carsten Lund

FOCS Conference 1992 Conference Paper

Proof Verification and Hardness of Approximation Problems

• Sanjeev Arora
• Carsten Lund
• Rajeev Motwani 0001
• Madhu Sudan 0001
• 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 used O(f(n)) random bits, queries O(g(n)) bits of its oracle and behaves as follows: If x in L then there exists an oracle y such that the machine accepts for all random choices but if x not in L then for every oracle y the machine rejects with high probability. Arora and Safra (1992) characterized NP as PCP(log n, (loglogn)/sup O(1)/). The authors improve on their result by showing that NP=PCP(logn, 1). The result has the following consequences: (1) MAXSNP-hard problems (e. g. metric TSP, MAX-SAT, MAX-CUT) do not have polynomial time approximation schemes unless P=NP; and (2) for some epsilon >0 the size of the maximal clique in a graph cannot be approximated within a factor of n/sup epsilon / unless P=NP. >

FOCS Conference 1990 Conference Paper

Algebraic Methods for Interactive Proof Systems

• Carsten Lund
• Lance Fortnow
• Howard J. Karloff
• Noam Nisan

An algebraic technique for the construction of interactive proof systems is proposed. The technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. For the proof, a method is developed for reducing the problem of verifying the value of a low-degree polynomial at two points to verifying the value at one new point. The results have implications for program checking, verification, and self-correction. >

FOCS Conference 1990 Conference Paper

Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols

• László Babai
• Lance Fortnow
• Carsten Lund

The exact power of two-prover interactive proof systems (MIP) introduced by M. Ben-Or et al. (Proc. 20th Symp. on Theory of Computing, 1988, p. 113-31) is determined. In this system, two all-powerful noncommunicating provers convince a randomizing polynomial-time verifier in polynomial time that the input x belongs to the language L. It was previously suspected (and proved in a relativized sense) that coNP-complete languages do not admit such proof systems. In sharp contrast, it is shown that the class of languages having two-prover interactive proof systems is computable in nondeterministic exponential time (NEXP). This represents a further step demonstrating the unexpectedly immense power for randomization and interaction in efficient provability. >