John Rompel

TCS Journal 1994 Journal Article

On the power of multi-prover interactive protocols

• Lance Fortnow
• John Rompel
• Michael Sipser

We look at complexity issues of interactive proof systems with multiple provers separated from each other. This model, developed by Ben-Or et al. (1988) allows the verifier to play the provers off each other. We show this model equivalent to an alternative interactive proof system model using oracles as provers. We also show that every language accepted by these models lies in nondeterministic exponential time. We exhibit a relativized world where a co-NP language does not have multiple prover interactive proofs. Finally, we show a simple example that one cannot parallelize multiple prover protocols as easily as the single prover model.

FOCS Conference 1994 Conference Paper

Randomness-Efficient Oblivious Sampling

• Mihir Bellare
• John Rompel

We introduce a natural notion of obliviousness of a sampling procedure, and construct a randomness-efficient oblivious sampler. Our sampler uses O(l+log /spl delta//sup -1//spl middot/log l) coins to output m=poly(/spl epsiv//sup -1/, log /spl delta//sup -1/, log l) sample points x/sub 1/, .. ., x/sub m/, /spl isin/ {0, 1}/sup 1/ such that Pr[|1/m/spl Sigma//sub i=1//sup m/f(x/sub i/)-E[f]|>

STOC Conference 1990 Conference Paper

One-Way Functions are Necessary and Sufficient for Secure Signatures

• John Rompel

FOCS Conference 1989 Conference Paper

Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry

• Bonnie Berger
• John Rompel
• Peter W. Shor

NC approximation algorithms are given for the unweighted and weighted set cover problems. The algorithms use a linear number of processors and give a cover that has at most log n times the optimal size/weight, thus matching the performance of the best sequential algorithms. The set cover algorithm is applied to learning theory, providing an NC algorithm for learning the concept class obtained by taking the closure under finite union or finite intersection of any concept class of finite VC dimension which has an NC hypothesis finder. In addition, a linear-processor NC algorithm is given for a variant of the set cover problem and used to obtain NC algorithms for several problems in computational geometry. >

FOCS Conference 1989 Conference Paper

Simulating (log ^c n)-wise Independence in NC

• Bonnie Berger
• John Rompel

A general framework is developed for removing randomness from randomized NC algorithms whose analysis uses only polylogarithmic independence. Previously, no techniques were known to determinize those RNC algorithms depending on more than constant independence. One application of the techniques is an NC algorithm for the set discrepancy problem, which can be used to obtain many other NC algorithms, including a better NC edge-coloring algorithm. As another application an NC algorithm for the hypergraph coloring problem is provided. >