Eli Upfal

Orcid: 0000-0002-9321-9460

Affiliations:
  • Brown University, Providence, USA


According to our database1, Eli Upfal authored at least 208 papers between 1982 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2005, "For contributions to parallel and stochastic networks.".

IEEE Fellow

IEEE Fellow 2002, "For contributions to theoretical aspects of computer science and engineering.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Bruisable Onions: Anonymous Communication in the Asynchronous Model.
IACR Cryptol. ePrint Arch., 2024

2023
An Adaptive Method for Weak Supervision with Drifting Data.
CoRR, 2023

An Adaptive Algorithm for Learning with Unknown Distribution Drift.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Nonparametric Density Estimation under Distribution Drift.
Proceedings of the International Conference on Machine Learning, 2023

2022
Balanced Allocation: Patience Is Not a Virtue.
SIAM J. Comput., 2022

Reducing polarization and increasing diverse navigability in graphs by inserting edges and swapping edge weights.
Data Min. Knowl. Discov., 2022

Tight Lower Bounds on Worst-Case Guarantees for Zero-Shot Learning with Attributes.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021
Tiered Sampling: An Efficient Method for Counting Sparse Motifs in Massive Graph Streams.
ACM Trans. Knowl. Discov. Data, 2021

Neuro-Hotnet: A Graph Theoretic Approach for Brain FC Estimation.
CoRR, 2021

RePBubLik: Reducing Polarized Bubble Radius with Link Insertions.
Proceedings of the WSDM '21, 2021

Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Adversarial Multi Class Learning under Weak Supervision with Performance Guarantees.
Proceedings of the 38th International Conference on Machine Learning, 2021

On the Complexity of Anonymous Communication Through Public Networks.
Proceedings of the 2nd Conference on Information-Theoretic Cryptography, 2021

How Inclusive Are Wikipedia's Hyperlinks in Articles Covering Polarizing Topics?
Proceedings of the 2021 IEEE International Conference on Big Data (Big Data), 2021

Semi-Supervised Aggregation of Dependent Weak Supervision Sources With Performance Guarantees.
Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020
Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE.
CoRR, 2020

Wikipedia's Network Bias on Controversial Topics.
CoRR, 2020

Distributed Graph Diameter Approximation.
Algorithms, 2020

2019
Optimizing static and adaptive probing schedules for rapid event detection.
Theor. Comput. Sci., 2019

Bandits and Experts in Metric Spaces.
J. ACM, 2019

A Rademacher Complexity Based Method fo rControlling Power and Confidence Level in Adaptive Statistical Analysis.
CoRR, 2019

Learning Equilibria of Simulation-Based Games.
CoRR, 2019

Differentially mutated subnetworks discovery.
Algorithms Mol. Biol., 2019

Democratizing Data Science through Interactive Curation of ML Pipelines.
Proceedings of the 2019 International Conference on Management of Data, 2019

A Rademacher Complexity Based Method for Controlling Power and Confidence Level in Adaptive Statistical Analysis.
Proceedings of the 2019 IEEE International Conference on Data Science and Advanced Analytics, 2019

VizCertify: A Framework for Secure Visual Data Exploration.
Proceedings of the 2019 IEEE International Conference on Data Science and Advanced Analytics, 2019

Wikipedia Polarization and Its Effects on Navigation Paths.
Proceedings of the 2019 IEEE International Conference on Big Data (IEEE BigData), 2019

Ordalia: Deep Learning Hyperparameter Search via Generalization Error Bounds Extrapolation.
Proceedings of the 2019 IEEE International Conference on Big Data (IEEE BigData), 2019

Learning Simulation-Based Games from Data.
Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019

2018
ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages.
ACM Trans. Knowl. Discov. Data, 2018

Uniform Convergence Bounds for Codec Selection.
CoRR, 2018

VizRec: A framework for secure data exploration via visual representation.
CoRR, 2018

Unknown Examples & Machine Learning Model Generalization.
CoRR, 2018

Machine Learning in High Energy Physics Community White Paper.
, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,
CoRR, 2018

Efficient Approximation for Restricted Biclique Cover Problems.
Algorithms, 2018

Towards Interactive Curation & Automatic Tuning of ML Pipelines.
Proceedings of the Second Workshop on Data Management for End-To-End Machine Learning, 2018

Practical and Provably Secure Onion Routing.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017
TRIÈST: Counting Local and Global Triangles in Fully Dynamic Streams with Fixed Memory Size.
ACM Trans. Knowl. Discov. Data, 2017

MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension.
Proc. VLDB Endow., 2017

Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141).
Dagstuhl Reports, 2017

Scalable and Provably Secure P2P Communication Protocols.
CoRR, 2017

Safe Visual Data Exploration.
Proceedings of the 2017 ACM International Conference on Management of Data, 2017

Controlling False Discoveries During Interactive Data Exploration.
Proceedings of the 2017 ACM International Conference on Management of Data, 2017

Minimizing operational cost for zero information leakage.
Proceedings of the IEEE International Conference on Communications, 2017

The k-Nearest Representatives Classifier: A Distance-Based Classifier with Strong Generalization Bounds.
Proceedings of the 2017 IEEE International Conference on Data Science and Advanced Analytics, 2017

Toward Sustainable Insights, or Why Polygamy is Bad for You.
Proceedings of the 8th Biennial Conference on Innovative Data Systems Research, 2017


Tiered sampling: An efficient method for approximate counting sparse motifs in massive graph streams.
Proceedings of the 2017 IEEE International Conference on Big Data (IEEE BigData 2017), 2017

Real-Time Targeted-Influence Queries over Large Graphs.
Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, Sydney, Australia, July 31, 2017

2016
On the Sample Complexity of Cancer Pathways Identification.
J. Comput. Biol., 2016

Wiggins: Detecting Valuable Information in Dynamic Networks Using Limited Resources.
Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, 2016

Scalable Betweenness Centrality Maximization via Sampling.
Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016

A Practical Parallel Algorithm for Diameter Approximation of Massive Weighted Graphs.
Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium, 2016

Reconstructing Hidden Permutations Using the Average-Precision (AP) Correlation Statistic.
Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 2016

2015
Fast distributed PageRank computation.
Theor. Comput. Sci., 2015

Accurate Computation of Survival Statistics in Genome-Wide Studies.
PLoS Comput. Biol., 2015

Distributed agreement in dynamic peer-to-peer networks.
J. Comput. Syst. Sci., 2015

The Probabilistic Hitting Set Paradigm: a General Framework for Search and Detection in Dynamic Social Networks.
CoRR, 2015

Space and Time Efficient Parallel Graph Decomposition, Clustering, and Diameter Approximation.
Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

VC-Dimension and Rademacher Averages: From Statistical Learning Theory to Sampling Algorithms.
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015

Mining Frequent Itemsets through Progressive Sampling with Rademacher Averages.
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015

Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Novel inexact memory aware algorithm co-design for energy efficient computation: algorithmic principles.
Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition, 2015

Optimizing Static and Adaptive Probing Schedules for Rapid Event Detection.
Proceedings of the Combinatorial Optimization and Applications, 2015

2014
Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees.
ACM Trans. Knowl. Discov. Data, 2014

Parallel Graph Decomposition and Diameter Approximation in o(Diameter) Time and Linear Space.
CoRR, 2014

The Melbourne Shuffle: Improving Oblivious Storage in the Cloud.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Contender: A Resource Modeling Approach for Concurrent Query Performance Prediction.
Proceedings of the 17th International Conference on Extending Database Technology, 2014

Some Practical Randomized Algorithms and Data Structures.
Proceedings of the Computing Handbook, 2014

2013
Storage and search in dynamic peer-to-peer networks.
Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Genome-Wide Survival Analysis of Somatic Mutations in Cancer.
Proceedings of the Research in Computational Molecular Biology, 2013

Identifying significant mutations in large cohorts of cancer genomes.
Proceedings of the IEEE 3rd International Conference on Computational Advances in Bio and Medical Sciences, 2013

2012
An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets.
J. ACM, 2012

Algorithms and Genome Sequencing: Identifying Driver Pathways in Cancer.
Computer, 2012

Finding Driver Pathways in Cancer: Models and Algorithms.
Algorithms Mol. Biol., 2012

Towards robust and efficient computation in dynamic peer-to-peer networks.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Discovery of Mutated Subnetworks Associated with Clinical Data in Cancer.
Proceedings of the Biocomputing 2012: Proceedings of the Pacific Symposium, 2012

PageRank on an evolving graph.
Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012

Algorithms on evolving graphs.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Space-round tradeoffs for MapReduce computations.
Proceedings of the International Conference on Supercomputing, 2012

Learning-based Query Performance Modeling and Prediction.
Proceedings of the IEEE 28th International Conference on Data Engineering (ICDE 2012), 2012

Workshop: Algorithms for discovery of mutated pathways in cancer.
Proceedings of the IEEE 2nd International Conference on Computational Advances in Bio and Medical Sciences, 2012

PARMA: a parallel randomized algorithm for approximate association rules mining in MapReduce.
Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2012

2011
Sorting and selection on dynamic data.
Theor. Comput. Sci., 2011

Algorithms for Detecting Significantly Mutated Pathways in Cancer.
J. Comput. Biol., 2011

MADMX: A Strategy for Maximal Dense Motif Extraction.
J. Comput. Biol., 2011

The VC-Dimension of Queries and Selectivity Estimation Through Sampling
CoRR, 2011

Performance prediction for concurrent database workloads.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2011

<i>De Novo</i> Discovery of Mutated Driver Pathways in Cancer.
Proceedings of the Research in Computational Molecular Biology, 2011

Tight bounds on information dissemination in sparse mobile networks.
Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

The VC-Dimension of SQL Queries and Selectivity Estimation through Sampling.
Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2011

The Case for Predictive Database Systems: Opportunities and Challenges.
Proceedings of the Fifth Biennial Conference on Innovative Data Systems Research, 2011

2010
Database-support for Continuous Prediction Queries over Streaming Data.
Proc. VLDB Endow., 2010

Mining top-<i>K</i> frequent itemsets through progressive sampling.
Data Min. Knowl. Discov., 2010

Infectious Random Walks
CoRR, 2010

Mining Top-K Frequent Itemsets Through Progressive Sampling
CoRR, 2010

Online stochastic optimization under time constraints.
Ann. Oper. Res., 2010

2009
The Hiring Problem and Lake Wobegon Strategies.
SIAM J. Comput., 2009

MADMX: A Novel Strategy for Maximal Dense Motif Extraction.
Proceedings of the Algorithms in Bioinformatics, 9th International Workshop, 2009

Sort Me If You Can: How to Sort Dynamic Data.
Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

2008
Commitment under uncertainty: Two-stage stochastic matching problems.
Theor. Comput. Sci., 2008

Multi-armed bandits in metric spaces.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Mortal Multi-Armed Bandits.
Proceedings of the Advances in Neural Information Processing Systems 21, 2008

Adapting to a Changing Environment: the Brownian Restless Bandits.
Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007
Entropy-based bounds for online algorithms.
ACM Trans. Algorithms, 2007

Finding near neighbors through cluster pruning.
Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007

07391 Abstracts Collection - Probabilistic Methods in the Design and Analysis of Algorithms.
Proceedings of the Probabilistic Methods in the Design and Analysis of Algorithms, 23.09., 2007

Propagating Knapsack Constraints in Sublinear Time.
Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, 2007

2006
Using PageRank to Characterize Web Structure.
Internet Math., 2006

2005
Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input.
SIAM J. Comput., 2005

Steady state analysis of balanced-allocation routing.
Random Struct. Algorithms, 2005

A Learned Comparative Expression Measure for Affymetrix GeneChip DNA Microarrays.
Proceedings of the Fourth International IEEE Computer Society Computational Systems Bioinformatics Conference, 2005

Probability and Computing: Randomized Algorithms and Probabilistic Analysis.
Cambridge University Press, ISBN: 9780511813603, 2005

2004
Efficient communication in an ad-hoc network.
J. Algorithms, 2004

A simple and deterministic competitive algorithm for online facility location.
Inf. Comput., 2004

2003
Building low-diameter peer-to-peer networks.
IEEE J. Sel. Areas Commun., 2003

Performance Analysis of Dynamic Network Processes.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Stability and Efficiency of a Random Local Load Balancing Protocol.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2001
A general approach to dynamic packet routing with bounded buffers.
J. ACM, 2001

Efficient Methods for Computing Investment Strategies for Multi-Market Commodity Trading.
Appl. Artif. Intell., 2001

A Clustering Approach to Solving Large Stochastic Matching Problems.
Proceedings of the UAI '01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, 2001

Can entropy characterize performance of online algorithms?.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Building Low-Diameter P2P Networks.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
Static and Dynamic Evaluation of QoS Properties.
J. Interconnect. Networks, 2000

Sequencing-by-Hybridization at the Information-Theory Bound: An Optimal Algorithm.
J. Comput. Biol., 2000

The Web as a Graph.
Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

Random graph models for the web graph.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Computing Global Strategies for Multi-Market Commodity Trading.
Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems, 2000

1999
Balanced Allocations.
SIAM J. Comput., 1999

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach.
Random Struct. Algorithms, 1999

Real-Time Communication Scheduling in a Multicomputer Video Server.
J. Parallel Distributed Comput., 1999

Optimal Reconstruction of a Sequence from its Probes.
J. Comput. Biol., 1999

On the power of universal bases in sequencing by hybridization.
Proceedings of the Third Annual International Conference on Research in Computational Molecular Biology, 1999

Computing Near Optimal Strategies for Stochastic Investment Planning Problems.
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, 1999

Reducing Network Congestion and Blocking Probability Through Balanced Allocation.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Stochastic Contention Resolution With Short Delays.
SIAM J. Comput., 1998

Optimal Construction of Edge-Disjoint Paths in Random Graphs.
SIAM J. Comput., 1998

A Steady State Analysis of Diffracting Trees.
Theory Comput. Syst., 1998

Reliable Fault Diagnosis with Few Tests.
Comb. Probab. Comput., 1998


On Balls and Bins with Deletions.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

Dynamic Packet Routing on Arrays with Bounded Buffers.
Proceedings of the LATIN '98: Theoretical Informatics, 1998

Design and Analysis of Dynamic Processes: A Stochastic Approach.
Proceedings of the Algorithms, 1998

1997
Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems.
IEEE Trans. Parallel Distributed Syst., 1997

How much can hardware help routing?
J. ACM, 1997

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

A Wait-Free Sorting Algorithm.
Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, 1997

Stochastic Analysis of Dynamic Processes.
Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

1996
Randomized Routing with Shorter Paths.
IEEE Trans. Parallel Distributed Syst., 1996

A Theory of Wormhole Routing in Parallel Computers.
IEEE Trans. Computers, 1996

Safe and Efficient Traffic Laws for Mobile Robots.
Proceedings of the Algorithm Theory, 1996

Dynamic Deflection Routing on Arrays (Preliminary Version).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

A Steady State Analysis of Diffracting Trees (Extended Abstract).
Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996

An Efficient Algorithm for the Vertex-Disjoint Paths Problem in Random Graphs.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Efficient Traffic Laws for Mobile Robots - Work in Progress (Avstract).
Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

A General Approach to Dynamic Packet Routing with Bounded Buffers (extended abstract).
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height.
Inf. Process. Lett., 1995

1994
Tolerating a Linear Number of Faults in Networks of Bounded Degree
Inf. Comput., December, 1994

Computing with Noisy Information.
SIAM J. Comput., 1994

Trading Space for Time in Undirected s-t Connectivity.
SIAM J. Comput., 1994

Existence and Construction of Edge-Disjoint Paths on Expander Graphs.
SIAM J. Comput., 1994

Near-perfect Token Distribution.
Random Struct. Algorithms, 1994

Efficient routing in all-optical networks.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Balanced allocations (extended abstract).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

On the Theory of Interconnection Networks for Parallel Computers.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

1993
On the Satisfiability and Maximum Satisfiability of Random 3-CNF Formulas.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

1992
An O(log(N)) Deterministic Packet-Routing Scheme.
J. ACM, 1992

An Experimental Study of Wormhole Routing in Parallel Computers.
Proceedings of the Parallel Architectures and Their Efficient Use, 1992

A Theory of Wormhole Routing in Parallel Computers (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
Fault Tolerant Sorting Networks.
SIAM J. Discret. Math., 1991

A Simple Load Balancing Scheme for Task Allocation in Parallel Machines.
Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991

On the Parallel Complexity of Evaluating Game Trees.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

1990
A Time-Randomness Trade-Off for Oblivious Routing.
SIAM J. Comput., 1990

Randomized Broadcast in Networks.
Random Struct. Algorithms, 1990

Computing with Unreliable Information (Preliminary Version)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Fault Tolerant Sorting Network
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
The Token Distribution Problem.
SIAM J. Comput., 1989

A trade-off between space and efficiency for routing tables.
J. ACM, 1989

Constructng disjoint paths on expander graphs.
Comb., 1989

An O(log N) Deterministic Packet Routing Scheme (Preliminary Version)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
Theor. Comput. Sci., 1988

Fault Tolerance in Networks of Bounded Degree.
SIAM J. Comput., 1988

The Complexity of Parallel Search.
J. Comput. Syst. Sci., 1988

Parallel hashing: an efficient implementation of shared memory.
J. ACM, 1988

A Tradeoff between Space and Efficiency for Routing Tables (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

A Time-Randomness Tradeoff for Oblivious Routing (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1987
The Generalized Packet Routing Problem.
Theor. Comput. Sci., 1987

A Time-Space Tradeoff for Element Distinctness.
SIAM J. Comput., 1987

A Probabilistic Approach to the Load-Sharing Problem in Distributed Systems.
J. Parallel Distributed Comput., 1987

How to share memory in a distributed system.
J. ACM, 1987

Constructing Disjoint Paths on Expander Graphs (Extended Abstract)
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986
The Parallel Complexity of Scheduling with Precedence Constraints.
J. Parallel Distributed Comput., 1986

Constructing a perfect matching is in random NC.
Comb., 1986

Parallel Hashing-An Efficient Implementation of Shared Memory (Preliminary Version)
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Fault Tolerance in Networks of Bounded Degree (Preliminary Version)
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

The Token Distribution Problem (Preliminary Version)
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
Random hypergraph coloring algorithms and the weak chromatic number.
J. Graph Theory, 1985

Are Search and Decision Problems Computationally Equivalent?
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

The Complexity of Parallel Computation on Matroids
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
Sequential and Distributed Graph Coloring Algorithms with Performance Analysis in Random Graph Spaces.
J. Algorithms, 1984

Efficient Schemes for Parallel Communication.
J. ACM, 1984

A Probabilistic Relation between Desirable and Feasible Models of Parallel Computation (A Preliminary Version)
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

How to Share Memory in a Distributed System (A Preliminary Version)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
אלגוריתמים הסתברותיים מבזרים לבעיות בתורת הגרפים, תקשורת תאום ותזמון (Distributed probabilistic algorithms for problems in graph theory.).
PhD thesis, 1983

A Fast Construction oF Disjoint Paths in Communication Networks.
Proceedings of the Fundamentals of Computation Theory, 1983

1982
Formal Correctness Proofs of a Nondeterministic Program.
Inf. Process. Lett., 1982

One-factor in random graphs based on vertex choice.
Discret. Math., 1982

N-Processors Graph Distributively Achieve Perfect Matchings in O(log<sup>2</sup>N) Beats.
Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 1982


  Loading...