Eli Upfal

IACR Cryptol. ePrint Arch., 2024

2023

An Adaptive Method for Weak Supervision with Drifting Data.

[BibT_eX]

[DOI]

CoRR, 2023

An Adaptive Algorithm for Learning with Unknown Distribution Drift.

[BibT_eX]

[DOI]

Alessio Mazzetto

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.

[BibT_eX]

[DOI]

Alessio Mazzetto

Proceedings of the International Conference on Machine Learning, 2023

2022

Balanced Allocation: Patience Is Not a Virtue.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Reducing polarization and increasing diverse navigability in graphs by inserting edges and swapping edge weights.

[BibT_eX]

[DOI]

Data Min. Knowl. Discov., 2022

Tight Lower Bounds on Worst-Case Guarantees for Zero-Shot Learning with Attributes.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Erisa Terolli

ACM Trans. Knowl. Discov. Data, 2021

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

[BibT_eX]

[DOI]

CoRR, 2021

RePBubLik: Reducing Polarized Bubble Radius with Link Insertions.

[BibT_eX]

[DOI]

Proceedings of the WSDM '21, 2021

Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

On the Complexity of Anonymous Communication Through Public Networks.

[BibT_eX]

[DOI]

Proceedings of the 2nd Conference on Information-Theoretic Cryptography, 2021

How Inclusive Are Wikipedia's Hyperlinks in Articles Covering Polarizing Topics?

[BibT_eX]

[DOI]

Cristina Menghini

Proceedings of the 2021 IEEE International Conference on Big Data (Big Data), 2021

Semi-Supervised Aggregation of Dependent Weak Supervision Sources With Performance Guarantees.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Shahrzad Haddadan

CoRR, 2020

Wikipedia's Network Bias on Controversial Topics.

[BibT_eX]

[DOI]

Cristina Menghini

CoRR, 2020

Distributed Graph Diameter Approximation.

[BibT_eX]

[DOI]

Algorithms, 2020

2019

Optimizing static and adaptive probing schedules for rapid event detection.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

Bandits and Experts in Metric Spaces.

[BibT_eX]

[DOI]

Robert Kleinberg

Aleksandrs Slivkins

J. ACM, 2019

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

[BibT_eX]

[DOI]

CoRR, 2019

Learning Equilibria of Simulation-Based Games.

[BibT_eX]

[DOI]

Enrique Areyan Viqueira

Amy Greenwald

CoRR, 2019

Differentially mutated subnetworks discovery.

[BibT_eX]

[DOI]

Morteza Chalabi Hajkarim

Algorithms Mol. Biol., 2019

Democratizing Data Science through Interactive Curation of ML Pipelines.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 2019 IEEE International Conference on Data Science and Advanced Analytics, 2019

VizCertify: A Framework for Secure Visual Data Exploration.

[BibT_eX]

[DOI]

Leonhard F. Spiegelberg

Tim Kraska

Proceedings of the 2019 IEEE International Conference on Data Science and Advanced Analytics, 2019

Wikipedia Polarization and Its Effects on Navigation Paths.

[BibT_eX]

[DOI]

Cristina Menghini

Proceedings of the 2019 IEEE International Conference on Big Data (IEEE BigData), 2019

Ordalia: Deep Learning Hyperparameter Search via Generalization Error Bounds Extrapolation.

[BibT_eX]

[DOI]

Benedetto Buratti

Proceedings of the 2019 IEEE International Conference on Big Data (IEEE BigData), 2019

Learning Simulation-Based Games from Data.

[BibT_eX]

[DOI]

Enrique Areyan Viqueira

Amy Greenwald

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.

[BibT_eX]

[DOI]

ACM Trans. Knowl. Discov. Data, 2018

Uniform Convergence Bounds for Codec Selection.

[BibT_eX]

[DOI]

Clayton Sanford

CoRR, 2018

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

[BibT_eX]

[DOI]

Leonhard F. Spiegelberg

Tim Kraska

Juan Pedro Araque Espinosa

CoRR, 2018

Unknown Examples & Machine Learning Model Generalization.

[BibT_eX]

[DOI]

CoRR, 2018

Machine Learning in High Energy Physics Community White Paper.

[BibT_eX]

[DOI]

Konstantin Kanishchev

Graeme Andrew Stewart

Xavier Vilasís-Cardona

CoRR, 2018

Efficient Approximation for Restricted Biclique Cover Problems.

[BibT_eX]

[DOI]

Alessandro Epasto

Algorithms, 2018

Towards Interactive Curation & Automatic Tuning of ML Pipelines.

[BibT_eX]

[DOI]

Proceedings of the Second Workshop on Data Management for End-To-End Machine Learning, 2018

Practical and Provably Secure Onion Routing.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

ACM Trans. Knowl. Discov. Data, 2017

MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2017

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

[BibT_eX]

[DOI]

Dagstuhl Reports, 2017

Scalable and Provably Secure P2P Communication Protocols.

[BibT_eX]

[DOI]

CoRR, 2017

Safe Visual Data Exploration.

[BibT_eX]

[DOI]

Proceedings of the 2017 ACM International Conference on Management of Data, 2017

Controlling False Discoveries During Interactive Data Exploration.

[BibT_eX]

[DOI]

Proceedings of the 2017 ACM International Conference on Management of Data, 2017

Minimizing operational cost for zero information leakage.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Conference on Communications, 2017

The k-Nearest Representatives Classifier: A Distance-Based Classifier with Strong Generalization Bounds.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE International Conference on Data Science and Advanced Analytics, 2017

Toward Sustainable Insights, or Why Polygamy is Bad for You.

[BibT_eX]

[DOI]

Proceedings of the 8th Biennial Conference on Innovative Data Systems Research, 2017

Towards Interactive Data Exploration.

[BibT_eX]

[DOI]

Proceedings of the Real-Time Business Intelligence and Analytics, 2017

Tiered sampling: An efficient method for approximate counting sparse motifs in massive graph streams.

[BibT_eX]

[DOI]

Erisa Terolli

Proceedings of the 2017 IEEE International Conference on Big Data (IEEE BigData 2017), 2017

Real-Time Targeted-Influence Queries over Large Graphs.

[BibT_eX]

[DOI]

Alessandro Epasto

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.

[BibT_eX]

[DOI]

J. Comput. Biol., 2016

Wiggins: Detecting Valuable Information in Dynamic Networks Using Limited Resources.

[BibT_eX]

[DOI]

Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, 2016

Scalable Betweenness Centrality Maximization via Sampling.

[BibT_eX]

[DOI]

Charalampos E. Tsourakakis

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.

[BibT_eX]

[DOI]

Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium, 2016

Reconstructing Hidden Permutations Using the Average-Precision (AP) Correlation Statistic.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 2016

2015

Fast distributed PageRank computation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Accurate Computation of Survival Statistics in Genome-Wide Studies.

[BibT_eX]

[DOI]

PLoS Comput. Biol., 2015

Distributed agreement in dynamic peer-to-peer networks.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2015

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

[BibT_eX]

[DOI]

CoRR, 2015

Space and Time Efficient Parallel Graph Decomposition, Clustering, and Diameter Approximation.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015

Mining Frequent Itemsets through Progressive Sampling with Rademacher Averages.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Guru Prakash Arumugam

Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition, 2015

Optimizing Static and Adaptive Probing Schedules for Rapid Event Detection.

[BibT_eX]

[DOI]

Evgenios M. Kornaropoulos

Proceedings of the Combinatorial Optimization and Applications, 2015

2014

Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees.

[BibT_eX]

[DOI]

ACM Trans. Knowl. Discov. Data, 2014

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

[BibT_eX]

[DOI]

CoRR, 2014

The Melbourne Shuffle: Improving Oblivious Storage in the Cloud.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Contender: A Resource Modeling Approach for Concurrent Query Performance Prediction.

[BibT_eX]

[DOI]

Proceedings of the 17th International Conference on Extending Database Technology, 2014

Some Practical Randomized Algorithms and Data Structures.

[BibT_eX]

Michael Mitzenmacher

Proceedings of the Computing Handbook, 2014

2013

Storage and search in dynamic peer-to-peer networks.

[BibT_eX]

[DOI]

Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Genome-Wide Survival Analysis of Somatic Mutations in Cancer.

[BibT_eX]

[DOI]

Proceedings of the Research in Computational Molecular Biology, 2013

Identifying significant mutations in large cohorts of cancer genomes.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

J. ACM, 2012

Algorithms and Genome Sequencing: Identifying Driver Pathways in Cancer.

[BibT_eX]

[DOI]

Computer, 2012

Finding Driver Pathways in Cancer: Models and Algorithms.

[BibT_eX]

[DOI]

Algorithms Mol. Biol., 2012

Towards robust and efficient computation in dynamic peer-to-peer networks.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Discovery of Mutated Subnetworks Associated with Clinical Data in Cancer.

[BibT_eX]

[DOI]

Proceedings of the Biocomputing 2012: Proceedings of the Pacific Symposium, 2012

PageRank on an evolving graph.

[BibT_eX]

[DOI]

Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012

Algorithms on evolving graphs.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Space-round tradeoffs for MapReduce computations.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Supercomputing, 2012

Learning-based Query Performance Modeling and Prediction.

[BibT_eX]

[DOI]

Proceedings of the IEEE 28th International Conference on Data Engineering (ICDE 2012), 2012

Workshop: Algorithms for discovery of mutated pathways in cancer.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2012

2011

Sorting and selection on dynamic data.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Algorithms for Detecting Significantly Mutated Pathways in Cancer.

[BibT_eX]

[DOI]

J. Comput. Biol., 2011

MADMX: A Strategy for Maximal Dense Motif Extraction.

[BibT_eX]

[DOI]

J. Comput. Biol., 2011

The VC-Dimension of Queries and Selectivity Estimation Through Sampling

[BibT_eX]

[DOI]

CoRR, 2011

Performance prediction for concurrent database workloads.

[BibT_eX]

[DOI]

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2011

De Novo Discovery of Mutated Driver Pathways in Cancer.

[BibT_eX]

[DOI]

Proceedings of the Research in Computational Molecular Biology, 2011

Tight bounds on information dissemination in sparse mobile networks.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

The VC-Dimension of SQL Queries and Selectivity Estimation through Sampling.

[BibT_eX]

[DOI]

Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2011

The Case for Predictive Database Systems: Opportunities and Challenges.

[BibT_eX]

[DOI]

Proceedings of the Fifth Biennial Conference on Innovative Data Systems Research, 2011

2010

Database-support for Continuous Prediction Queries over Streaming Data.

[BibT_eX]

[DOI]

Mert Akdere

Ugur Çetintemel

Proc. VLDB Endow., 2010

Mining top-K frequent itemsets through progressive sampling.

[BibT_eX]

[DOI]

Data Min. Knowl. Discov., 2010

Infectious Random Walks

[BibT_eX]

[DOI]

CoRR, 2010

Mining Top-K Frequent Itemsets Through Progressive Sampling

[BibT_eX]

[DOI]

CoRR, 2010

Online stochastic optimization under time constraints.

[BibT_eX]

[DOI]

Pascal Van Hentenryck

Russell Bent

Ann. Oper. Res., 2010

2009

The Hiring Problem and Lake Wobegon Strategies.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

MADMX: A Novel Strategy for Maximal Dense Motif Extraction.

[BibT_eX]

[DOI]

Proceedings of the Algorithms in Bioinformatics, 9th International Workshop, 2009

Sort Me If You Can: How to Sort Dynamic Data.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

2008

Commitment under uncertainty: Two-stage stochastic matching problems.

[BibT_eX]

[DOI]

Irit Katriel

Claire Kenyon-Mathieu

Theor. Comput. Sci., 2008

Multi-armed bandits in metric spaces.

[BibT_eX]

[DOI]

Robert Kleinberg

Aleksandrs Slivkins

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Mortal Multi-Armed Bandits.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 21, 2008

Adapting to a Changing Environment: the Brownian Restless Bandits.

[BibT_eX]

[DOI]

Aleksandrs Slivkins

Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007

Entropy-based bounds for online algorithms.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

Finding near neighbors through cluster pruning.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Martin Dietzfelbinger

Shang-Hua Teng

Berthold Vöcking

Proceedings of the Probabilistic Methods in the Design and Analysis of Algorithms, 23.09., 2007

Propagating Knapsack Constraints in Sublinear Time.

[BibT_eX]

[DOI]

Irit Katriel

Meinolf Sellmann

Pascal Van Hentenryck

Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, 2007

2006

Using PageRank to Characterize Web Structure.

[BibT_eX]

[DOI]

Internet Math., 2006

2005

Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input.

[BibT_eX]

[DOI]

Adam Kirsch

SIAM J. Comput., 2005

Steady state analysis of balanced-allocation routing.

[BibT_eX]

[DOI]

Ioannis Kontoyiannis

Random Struct. Algorithms, 2005

A Learned Comparative Expression Measure for Affymetrix GeneChip DNA Microarrays.

[BibT_eX]

[DOI]

Will Sheffler

John Sedivy

William Stafford Noble

Proceedings of the Fourth International IEEE Computer Society Computational Systems Bioinformatics Conference, 2005

Probability and Computing: Randomized Algorithms and Probabilistic Analysis.

[BibT_eX]

[DOI]

Michael Mitzenmacher

Cambridge University Press, ISBN: 9780511813603, 2005

2004

Efficient communication in an ad-hoc network.

[BibT_eX]

[DOI]

Abraham Flaxman

J. Algorithms, 2004

A simple and deterministic competitive algorithm for online facility location.

[BibT_eX]

[DOI]

Russell Bent

Pascal Van Hentenryck

Inf. Comput., 2004

2003

Building low-diameter peer-to-peer networks.

[BibT_eX]

[DOI]

IEEE J. Sel. Areas Commun., 2003

Performance Analysis of Dynamic Network Processes.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Stability and Efficiency of a Random Local Load Balancing Protocol.

[BibT_eX]

[DOI]

Adam Kirsch

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2001

A general approach to dynamic packet routing with bounded buffers.

[BibT_eX]

[DOI]

J. ACM, 2001

Efficient Methods for Computing Investment Strategies for Multi-Market Commodity Trading.

[BibT_eX]

[DOI]

Luis E. Ortiz

Ioannis Tsochantaridis

Appl. Artif. Intell., 2001

A Clustering Approach to Solving Large Stochastic Matching Problems.

[BibT_eX]

[DOI]

Proceedings of the UAI '01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, 2001

Can entropy characterize performance of online algorithms?.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Building Low-Diameter P2P Networks.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Static and Dynamic Evaluation of QoS Properties.

[BibT_eX]

[DOI]

J. Interconnect. Networks, 2000

Sequencing-by-Hybridization at the Information-Theory Bound: An Optimal Algorithm.

[BibT_eX]

[DOI]

Franco P. Preparata

J. Comput. Biol., 2000

The Web as a Graph.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

Random graph models for the web graph.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Computing Global Strategies for Multi-Market Commodity Trading.

[BibT_eX]

[DOI]

Luis E. Ortiz

Ioannis Tsochantaridis

Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems, 2000

1999

Balanced Allocations.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1999

Real-Time Communication Scheduling in a Multicomputer Video Server.

[BibT_eX]

[DOI]

A. L. Narasimha Reddy

J. Parallel Distributed Comput., 1999

Optimal Reconstruction of a Sequence from its Probes.

[BibT_eX]

[DOI]

Franco P. Preparata

J. Comput. Biol., 1999

On the power of universal bases in sequencing by hybridization.

[BibT_eX]

[DOI]

Franco P. Preparata

Proceedings of the Third Annual International Conference on Research in Computational Molecular Biology, 1999

Computing Near Optimal Strategies for Stochastic Investment Planning Problems.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, 1999

Reducing Network Congestion and Blocking Probability Through Balanced Allocation.

[BibT_eX]

[DOI]

Malwina J. Luczak

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Stochastic Contention Resolution With Short Delays.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Optimal Construction of Edge-Disjoint Paths in Random Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

A Steady State Analysis of Diffracting Trees.

[BibT_eX]

[DOI]

Nir Shavit

Asaph Zemach

Theory Comput. Syst., 1998

Reliable Fault Diagnosis with Few Tests.

[BibT_eX]

[DOI]

Andrzej Pelc

Comb. Probab. Comput., 1998

Updates to the QBIC System.

[BibT_eX]

[DOI]

Proceedings of the Storage and Retrieval for Image and Video Databases VI, 1998

On Balls and Bins with Deletions.

[BibT_eX]

[DOI]

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

Dynamic Packet Routing on Arrays with Bounded Buffers.

[BibT_eX]

[DOI]

Proceedings of the LATIN '98: Theoretical Informatics, 1998

Design and Analysis of Dynamic Processes: A Stochastic Approach.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1998

1997

Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 1997

How much can hardware help routing?

[BibT_eX]

[DOI]

J. ACM, 1997

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

A Wait-Free Sorting Algorithm.

[BibT_eX]

[DOI]

Nir Shavit

Asaph Zemach

Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, 1997

Stochastic Analysis of Dynamic Processes.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

1996

Randomized Routing with Shorter Paths.

[BibT_eX]

[DOI]

Marc Snir

IEEE Trans. Parallel Distributed Syst., 1996

A Theory of Wormhole Routing in Parallel Computers.

[BibT_eX]

[DOI]

IEEE Trans. Computers, 1996

Safe and Efficient Traffic Laws for Mobile Robots.

[BibT_eX]

[DOI]

Sonne Preminger

Proceedings of the Algorithm Theory, 1996

Dynamic Deflection Routing on Arrays (Preliminary Version).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

A Steady State Analysis of Diffracting Trees (Extended Abstract).

[BibT_eX]

[DOI]

Nir Shavit

Asaph Zemach

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.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Efficient Traffic Laws for Mobile Robots - Work in Progress (Avstract).

[BibT_eX]

[DOI]

Sonne Preminger

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).

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1995

1994

Tolerating a Linear Number of Faults in Networks of Bounded Degree

[BibT_eX]

[DOI]

Inf. Comput., December, 1994

Computing with Noisy Information.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

Trading Space for Time in Undirected s-t Connectivity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

Existence and Construction of Edge-Disjoint Paths on Expander Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

Near-perfect Token Distribution.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1994

Efficient routing in all-optical networks.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Balanced allocations (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

On the Theory of Interconnection Networks for Parallel Computers.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

1993

On the Satisfiability and Maximum Satisfiability of Random 3-CNF Formulas.

[BibT_eX]

[DOI]

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

1992

An O(log(N)) Deterministic Packet-Routing Scheme.

[BibT_eX]

[DOI]

J. ACM, 1992

An Experimental Study of Wormhole Routing in Parallel Computers.

[BibT_eX]

[DOI]

Proceedings of the Parallel Architectures and Their Efficient Use, 1992

A Theory of Wormhole Routing in Parallel Computers (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Fault Tolerant Sorting Networks.

[BibT_eX]

[DOI]

Shay Assaf

SIAM J. Discret. Math., 1991

A Simple Load Balancing Scheme for Task Allocation in Parallel Machines.

[BibT_eX]

[DOI]

Larry Rudolph

Miriam Slivkin-Allalouf

Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991

On the Parallel Complexity of Evaluating Game Trees.

[BibT_eX]

[DOI]

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

1990

A Time-Randomness Trade-Off for Oblivious Routing.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

Randomized Broadcast in Networks.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1990

Computing with Unreliable Information (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Fault Tolerant Sorting Network

[BibT_eX]

[DOI]

Shay Assaf

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

The Token Distribution Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

A trade-off between space and efficiency for routing tables.

[BibT_eX]

[DOI]

J. ACM, 1989

Constructng disjoint paths on expander graphs.

[BibT_eX]

[DOI]

Comb., 1989

An O(log N) Deterministic Packet Routing Scheme (Preliminary Version)

[BibT_eX]

[DOI]

Friedhelm Meyer auf der Heide

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.

[BibT_eX]

[DOI]

Allan Borodin

Faith E. Fich

Theor. Comput. Sci., 1988

Fault Tolerance in Networks of Bounded Degree.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

The Complexity of Parallel Search.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1988

Parallel hashing: an efficient implementation of shared memory.

[BibT_eX]

[DOI]

Anna R. Karlin

J. ACM, 1988

A Tradeoff between Space and Efficiency for Routing Tables (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

A Time-Randomness Tradeoff for Oblivious Routing (Extended Abstract)

[BibT_eX]

[DOI]

Danny Krizanc

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1987

The Generalized Packet Routing Problem.

[BibT_eX]

[DOI]

Friedhelm Meyer auf der Heide

Theor. Comput. Sci., 1987

A Time-Space Tradeoff for Element Distinctness.

[BibT_eX]

[DOI]

Allan Borodin

Faith E. Fich

SIAM J. Comput., 1987

A Probabilistic Approach to the Load-Sharing Problem in Distributed Systems.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 1987

How to share memory in a distributed system.

[BibT_eX]

[DOI]

J. ACM, 1987

Constructing Disjoint Paths on Expander Graphs (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986

The Parallel Complexity of Scheduling with Precedence Constraints.

[BibT_eX]

[DOI]

Danny Dolev

Manfred K. Warmuth

J. Parallel Distributed Comput., 1986

Constructing a perfect matching is in random NC.

[BibT_eX]

[DOI]

Comb., 1986

Parallel Hashing-An Efficient Implementation of Shared Memory (Preliminary Version)

[BibT_eX]

[DOI]

Anna R. Karlin

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Fault Tolerance in Networks of Bounded Degree (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

The Token Distribution Problem (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985

Random hypergraph coloring algorithms and the weak chromatic number.

[BibT_eX]

[DOI]

Jeanette Schmidt-Pruzan

J. Graph Theory, 1985

Are Search and Decision Problems Computationally Equivalent?

[BibT_eX]

[DOI]

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

The Complexity of Parallel Computation on Matroids

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

J. Algorithms, 1984

Efficient Schemes for Parallel Communication.

[BibT_eX]

[DOI]

J. ACM, 1984

A Probabilistic Relation between Desirable and Feasible Models of Parallel Computation (A Preliminary Version)

[BibT_eX]

[DOI]

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)

[BibT_eX]

[DOI]

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

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

[BibT_eX]

[DOI]

PhD thesis, 1983

A Fast Construction oF Disjoint Paths in Communication Networks.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 1983

1982

Formal Correctness Proofs of a Nondeterministic Program.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1982

One-factor in random graphs based on vertex choice.

[BibT_eX]

[DOI]

Discret. Math., 1982

N-Processors Graph Distributively Achieve Perfect Matchings in O(log2N) Beats.

[BibT_eX]

[DOI]