EDBT 2026 Demo / reviewers in the wild / expert
John Rompel
dblp:02/6786
· DBLP profile ↗
8ranked-venue papers
1as first author
0since 2021 · last 1994
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 7 · 1 first-authorApplied, interdisciplinary, general and emerging computing · 1
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
4 papers |
Computational complexity · 47% Algorithms and data structures · 29% Combinatorics and discrete mathematics · 10% | |
| Network and information security
1 paper |
Cryptographic primitives and cryptanalysis · 100% |
Topics — the 14 heaviest of 15, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity
derandomization |
0.0 | 3 | 1994 | Randomness-Efficient Oblivious Sampling · FOCS 1994 Simulating (log c n)-Wise Independence in NC · J. ACM 1991 Simulating (log ^c n)-wise Independence in NC · FOCS 1989 |
Algorithms and data structures › parallel algorithms
NC algorithms |
0.0 | 3 | 1991 | Simulating (log c n)-Wise Independence in NC · J. ACM 1991 Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry · FOCS 1989 Simulating (log ^c n)-wise Independence in NC · FOCS 1989 |
Algorithms and data structures
parallel algorithms |
0.0 | 3 | 1991 | Simulating (log c n)-Wise Independence in NC · J. ACM 1991 Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry · FOCS 1989 Simulating (log ^c n)-wise Independence in NC · FOCS 1989 |
Graph algorithms and graph theory › graph coloring
edge coloring |
0.0 | 1 | 1991 | Simulating (log c n)-Wise Independence in NC · J. ACM 1991 |
Combinatorics and discrete mathematics › hypergraph
hypergraph coloring |
0.0 | 1 | 1991 | Simulating (log c n)-Wise Independence in NC · J. ACM 1991 |
Computational complexity › pseudorandomness
limited independence |
0.0 | 1 | 1991 | Simulating (log c n)-Wise Independence in NC · J. ACM 1991 |
Computational complexity
pseudorandomness |
0.0 | 1 | 1991 | Simulating (log c n)-Wise Independence in NC · J. ACM 1991 |
Cryptographic primitives and cryptanalysis › public-key cryptography
digital signatures |
0.0 | 1 | 1990 | One-Way Functions are Necessary and Sufficient for Secure Signatures · STOC 1990 |
Cryptographic primitives and cryptanalysis
one-way functions |
0.0 | 1 | 1990 | One-Way Functions are Necessary and Sufficient for Secure Signatures · STOC 1990 |
Approximation and online algorithms
approximation algorithms |
0.0 | 1 | 1989 | Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry · FOCS 1989 |
Combinatorics and discrete mathematics › discrepancy theory
discrepancy |
0.0 | 1 | 1989 | Simulating (log ^c n)-wise Independence in NC · FOCS 1989 |
Computational complexity
learning theory |
0.0 | 1 | 1989 | Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry · FOCS 1989 |
Approximation and online algorithms › approximation algorithms › combinatorial approximation algorithms
set cover approximation |
0.0 | 1 | 1989 | Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry · FOCS 1989 |
Computational complexity › learning theory
VC dimension |
0.0 | 1 | 1989 | Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry · FOCS 1989 |
Methods — techniques the papers use, named apart from their topics
sampling · 0.0pseudorandomness · 0.0pairwise independence · 0.0discrepancy method · 0.0reduction · 0.0probabilistic method · 0.0linear-processor parallel algorithm · 0.0limited independence · 0.0approximation algorithm · 0.0
| Year | Publication | Venue | Position |
|---|---|---|---|
| 1994 | Randomness-Efficient Oblivious SamplingabstractWe 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]|> Mihir Bellare, John Rompel |
FOCS | 2 |
| 1994 | Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry
Bonnie Berger, John Rompel, Peter W. Shor |
J. Comput. Syst. Sci. | 2 |
| 1994 | On the Power of Multi-Prover Interactive Protocols
Lance Fortnow, John Rompel, Michael Sipser |
Theor. Comput. Sci. | 2 |
| 1991 | Simulating (log c n)-Wise Independence in NCabstractA general framework for removing randomness from randomized NC algorithms whose analysls uses only pol ylogarlthmic independence is developed.Previously, no techniques were known to remove the randomness from those randomized NC algorithms depending on more than constant independence.One application of our techniques is an NC algorithm for the set discrepancy y problem.which can be used to obtain many other NC algorithms, mcludmg a better NC edge coloring algorithm.As another application of the techniques in this paper.an NC algorlthm for the h ypergraph coloring problem M provided. Bonnie Berger, John Rompel |
J. ACM | 2 |
| 1990 | One-Way Functions are Necessary and Sufficient for Secure SignaturesabstractMuch research in theoretical cryptography has been centered around finding the weakest possible cryptographic assumptions required to implement major primitives. Ever since Diffie and Hellman first suggested that modern John Rompel |
STOC | 1 |
| 1990 | A Better Performance Guarantee for Approximate Graph Coloring
Bonnie Berger, John Rompel |
Algorithmica | 2 |
| 1989 | Simulating (log ^c n)-wise Independence in NCabstractA 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.> Bonnie Berger, John Rompel |
FOCS | 2 |
| 1989 | Efficient NC Algorithms for Set Cover with Applications to Learning and GeometryabstractNC 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.> Bonnie Berger, John Rompel, Peter W. Shor |
FOCS | 2 |