# Yishay Mansour

According to our database

Collaborative distances:

^{1}, Yishay Mansour authored at least 285 papers between 1986 and 2019.Collaborative distances:

## Awards

## ACM Fellow

ACM Fellow 2014, "For contributions to machine learning, algorithmic game theory, distributed computing, and communication networks.".

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2019

Delay and Cooperation in Nonstochastic Bandits.

Journal of Machine Learning Research, 2019

Online Convex Optimization in Adversarial Markov Decision Processes.

Proceedings of the 36th International Conference on Machine Learning, 2019

Adversarial Online Learning with noise.

Proceedings of the 36th International Conference on Machine Learning, 2019

Differentially Private Learning of Geometric Concepts.

Proceedings of the 36th International Conference on Machine Learning, 2019

Learning Linear-Quadratic Regulators Efficiently with only √T Regret.

Proceedings of the 36th International Conference on Machine Learning, 2019

Optimal Algorithm for Bayesian Incentive-Compatible Exploration.

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

Competitive ratio vs regret minimization: achieving the best of both worlds.

Proceedings of the Algorithmic Learning Theory, 2019

Improved Generalization Bounds for Robust Learning.

Proceedings of the Algorithmic Learning Theory, 2019

2018

Sublinear Graph Augmentation for Fast Query Implementation.

Proceedings of the Approximation and Online Algorithms - 16th International Workshop, 2018

Are Two (Samples) Really Better Than One?

Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Fair Leader Election for Rational Agents in Asynchronous Rings and Networks.

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Competing Bandits: Learning Under Competition.

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

On Price versus Quality.

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Planning and Learning with Stochastic Action Sets.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Online Linear Quadratic Control.

Proceedings of the 35th International Conference on Machine Learning, 2018

Nonstochastic Bandits with Composite Anonymous Feedback.

Proceedings of the Conference On Learning Theory, 2018

Learning Decision Trees with Stochastic Linear Classifiers.

Proceedings of the Algorithmic Learning Theory, 2018

Robust Inference for Multiclass Classification.

Proceedings of the Algorithmic Learning Theory, 2018

Discriminative Learning of Prediction Intervals.

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

2017

Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback.

SIAM J. Comput., 2017

Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251).

Dagstuhl Reports, 2017

Predicting Counterfactuals from Large Historical Data and Small Randomized Trials.

Proceedings of the 26th International Conference on World Wide Web Companion, 2017

ERA: A Framework for Economic Resource Allocation for the Cloud.

Proceedings of the 26th International Conference on World Wide Web Companion, 2017

The Strategy of Experts for Repeated Predictions.

Proceedings of the Web and Internet Economics - 13th International Conference, 2017

Multi-Armed Bandits with Metric Movement Costs.

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues.

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

A User Re-Modeling Approach to Item Recommendation using Complex Usage Data.

Proceedings of the ACM SIGIR International Conference on Theory of Information Retrieval, 2017

Bandits with Movement Costs and Adaptive Pricing.

Proceedings of the 30th Conference on Learning Theory, 2017

Efficient Co-Training of Linear Separators under Weak Dependence.

Proceedings of the 30th Conference on Learning Theory, 2017

Efficient PAC Learning from the Crowd.

Proceedings of the 30th Conference on Learning Theory, 2017

Label Efficient Learning by Exploiting Multi-Class Output Codes.

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016

The AND-OR Game.

ACM Trans. Economics and Comput., 2016

Robust option pricing: Hannan and Blackwell meet Black and Scholes.

J. Economic Theory, 2016

Bayesian Exploration: Incentivizing Exploration in Bayesian Games.

Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

When Should an Expert Make a Prediction?

Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Dynamics of Evolving Social Groups.

Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

History-Independent Distributed Multi-agent Learning.

Proceedings of the Algorithmic Game Theory - 9th International Symposium, 2016

Online Pricing with Strategic and Patient Buyers.

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Online Learning with Low Rank Experts.

Proceedings of the 29th Conference on Learning Theory, 2016

Delay and Cooperation in Nonstochastic Bandits.

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Online Allocation and Pricing with Economies of Scale.

Proceedings of the Web and Internet Economics - 11th International Conference, 2015

Constant-Time Local Computation Algorithms.

Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

Robust Probabilistic Inference.

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Scheduling Multipacket Frames with Frame Deadlines.

Proceedings of the Structural Information and Communication Complexity, 2015

Bayesian Incentive-Compatible Bandit Exploration.

Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Learning What's Going on: Reconstructing Preferences and Priorities from Opaque Transactions.

Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Making the Most of Your Samples.

Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Robust Inference and Local Algorithms.

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Classification with Low Rank and Missing Data.

Proceedings of the 32nd International Conference on Machine Learning, 2015

Learning and inference in the presence of corrupted inputs.

Proceedings of The 28th Conference on Learning Theory, 2015

On the Complexity of Learning with Kernels.

Proceedings of The 28th Conference on Learning Theory, 2015

Learning Valuation Distributions from Partial Observation.

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014

Probe scheduling for efficient detection of silent failures.

Perform. Eval., 2014

Local computation mechanism design.

Proceedings of the ACM Conference on Economics and Computation, 2014

Thompson Sampling for Complex Online Problems.

Proceedings of the 31th International Conference on Machine Learning, 2014

2013

Electronic Markets and Auctions (Dagstuhl Seminar 13461).

Dagstuhl Reports, 2013

Regret Minimization for Reserve Prices in Second-Price Auctions.

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Implementing the "Wisdom of the Crowd".

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Differential pricing with inequity aversion in social networks.

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

From Bandits to Experts: A Tale of Domination and Independence.

Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

Exploiting Ontology Structures and Unlabeled Data for Learning.

Proceedings of the 30th International Conference on Machine Learning, 2013

Regret Minimization for Branching Experts.

Proceedings of the COLT 2013, 2013

An empirical study of trading agent robustness.

Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2013

A Local Computation Approximation Scheme to Maximum Matching.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

Scheduling Subset Tests: One-Time, Continuous, and How They Relate.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Online Set Packing.

SIAM J. Comput., 2012

The load-distance balancing problem.

Networks, 2012

Distributed Learning, Communication Complexity and Privacy.

Proceedings of the COLT 2012, 2012

The AND-OR Game: Equilibrium Characterization - (Working Paper).

Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

Beyond myopic best response (in Cournot competition).

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

Learning Multiple Tasks using Shared Hypotheses.

Proceedings of the Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012

Robust Domain Adaptation.

Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2012

Upward Max Min Fairness.

Proceedings of the IEEE INFOCOM 2012, Orlando, FL, USA, March 25-30, 2012, 2012

Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions.

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Converting Online Algorithms to Local Computation Algorithms.

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Ad Exchange - Proposal for a New Trading Agent Competition Game.

Proceedings of the Agent-Mediated Electronic Commerce. Designing Trading Strategies and Mechanisms for Electronic Markets, 2012

A Model-Free Approach for a TAC-AA Trading Agent.

Proceedings of the Agent-Mediated Electronic Commerce. Designing Trading Strategies and Mechanisms for Electronic Markets, 2012

Lower Bounds on Individual Sequence Regret.

Proceedings of the Algorithmic Learning Theory - 23rd International Conference, 2012

2011

Competitive Router Scheduling with Structured Data.

Proceedings of the Approximation and Online Algorithms - 9th International Workshop, 2011

Non-price equilibria in markets of discrete goods.

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Pricing Exotic Derivatives Using Regret Minimization.

Proceedings of the Algorithmic Game Theory, 4th International Symposium, 2011

Repeated Budgeted Second Price Ad Auction.

Proceedings of the Algorithmic Game Theory, 4th International Symposium, 2011

Overflow management with multipart packets.

Proceedings of the INFOCOM 2011. 30th IEEE International Conference on Computer Communications, 2011

Welfare and Profit Maximization with Production Costs.

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Regret Minimization Algorithms for Pricing Lookback Options.

Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011

2010

How long to equilibrium? The communication complexity of uncoupled equilibrium procedures.

Games and Economic Behavior, 2010

Approximation Schemes for Sequential Posted Pricing in Multi-unit Auctions.

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Selective Call Out and Real Time Bidding.

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Regret Minimization and Job Scheduling.

Proceedings of the SOFSEM 2010: Theory and Practice of Computer Science, 2010

On the Equilibria of Alternating Move Games.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Online set packing and competitive scheduling of multi-part tasks.

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Learning Bounds for Importance Weighting.

Proceedings of the Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, 2010

Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior.

Proceedings of the Innovations in Computer Science, 2010

Learning with Global Cost in Stochastic Environments.

Proceedings of the COLT 2010, 2010

Regret Minimization With Concept Drift.

Proceedings of the COLT 2010, 2010

2009

Online Markov Decision Processes.

Math. Oper. Res., 2009

Efficient graph topologies in network routing games.

Games and Economic Behavior, 2009

Bid optimization for broad match ad auctions.

Proceedings of the 18th International Conference on World Wide Web, 2009

Multiple Source Adaptation and the Rényi Divergence.

Proceedings of the UAI 2009, 2009

On the convergence of regret minimization dynamics in concave games.

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Improved equilibria via public service advertising.

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

The price of uncertainty.

Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

Learning and Domain Adaptation.

Proceedings of the Discovery Science, 12th International Conference, 2009

Domain Adaptation: Learning Bounds and Algorithms.

Proceedings of the COLT 2009, 2009

Reliable Agnostic Learning.

Proceedings of the COLT 2009, 2009

Online Learning for Global Cost Functions.

Proceedings of the COLT 2009, 2009

Learning and Domain Adaptation.

Proceedings of the Algorithmic Learning Theory, 20th International Conference, 2009

2008

Competitive buffer management for shared-memory switches.

ACM Trans. Algorithms, 2008

Reducing mechanism design to algorithm design via machine learning.

J. Comput. Syst. Sci., 2008

Position Auctions with Bidder-Specific Minimum Prices.

Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

On agnostic boosting and parity learning.

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

Competitive queue management for latency sensitive packets.

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Item pricing for revenue maximization.

Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

Domain Adaptation with Multiple Sources.

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

2007

A Time-Optimal Self-Stabilizing Synchronizer Using A Phase Clock.

IEEE Trans. Dependable Sec. Comput., 2007

Convergence time to Nash equilibrium in load balancing.

ACM Trans. Algorithms, 2007

A Network Creation Game with Nonuniform Interests.

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Learning, regret minimization and option pricing.

Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2007), 2007

The communication complexity of uncoupled nash equilibrium procedures.

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Efficient contention resolution protocols for selfish agents.

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Strong price of anarchy.

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Strong equilibrium in cost sharing connection games.

Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

The Value of Observation for Monitoring Dynamic Systems.

Proceedings of the IJCAI 2007, 2007

Regret to the Best vs. Regret to the Average.

Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

2006

Harnessing Machine Learning to Improve the Success Rate of Stimuli Generation.

IEEE Trans. Computers, 2006

Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems.

Journal of Machine Learning Research, 2006

Online trading algorithms and robust option pricing.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Combining Multiple Heuristics.

Proceedings of the STACS 2006, 2006

On nash equilibria for a network creation game.

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

(In)Stability properties of limit order dynamics.

Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

A sufficient condition for truthfulness with single parameter agents.

Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

Active Sampling for Multiple Output Identification.

Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

2005

Combining Online Algorithms for Acceptance and Rejection.

Theory of Computing, 2005

Concentration Bounds for Unigram Language Models.

Journal of Machine Learning Research, 2005

Planning in POMDPs Using Multiplicity Automata.

Proceedings of the UAI '05, 2005

Learning with attribute costs.

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Fast convergence of selfish rerouting.

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Reinforcement Learning in POMDPs Without Resets.

Proceedings of the IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30, 2005

Optimizing TCP Retransmission Timeout.

Proceedings of the Networking, 2005

Harnessing machine learning to improve the success rate of stimuli generation.

Proceedings of the Tenth IEEE International High-Level Design Validation and Test Workshop 2005, Napa Valley, CA, USA, November 30, 2005

Agnostically Learning Halfspaces.

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Mechanism Design via Machine Learning.

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Improved Second-Order Bounds for Prediction with Expert Advice.

Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

From External to Internal Regret.

Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

2004

Optimal smoothing schedules for real-time streams.

Distributed Computing, 2004

Auctions with Budget Constraints.

Proceedings of the Algorithm Theory, 2004

Improved combination of online algorithms for acceptance and rejection.

Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004

Competitive algorithms for VWAP and limit order trading.

Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

Competitive on-line paging strategies for mobile users under delay constraints.

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Experts in a Markov Decision Process.

Proceedings of the Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, 2004

Concentration Bounds for Unigrams Language Model.

Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

2003

Diffusion without false rumors: on propagating updates in a Byzantine environment.

Theor. Comput. Sci., 2003

Centralized broadcast in multihop radio networks.

J. Algorithms, 2003

Almost k-wise independence versus k-wise independence.

Inf. Process. Lett., 2003

Competitive Management of Non-preemptive Queues with Multiple Values.

Proceedings of the Distributed Computing, 17th International Conference, 2003

Buffer overflows of merging streams.

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Combining online algorithms for rejection and acceptance.

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Competitive queueing policies for QoS switches.

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Adaptive AIMD congestion control.

Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, 2003

Adapting to a reliable network path.

Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, 2003

Action Elimination and Stopping Conditions for Reinforcement Learning.

Proceedings of the Machine Learning, 2003

Convergence Time to Nash Equilibria.

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

AdaVegas: adaptive control for TCP Vegas.

Proceedings of the Global Telecommunications Conference, 2003

Improved Competitive Guarantees for QoS Buffering.

Proceedings of the Algorithms, 2003

Buffer Overflows of Merging Streams.

Proceedings of the Algorithms, 2003

Approximate Equivalence of Markov Decision Processes.

Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2002

Almost k-wise independence versus k-wise independence.

Electronic Colloquium on Computational Complexity (ECCC), 2002

Efficient Nash Computation in Large Population Games with Bounded Influence.

Proceedings of the UAI '02, 2002

Harmonic Buffer Management Policy for Shared Memory Switches.

Proceedings of the Proceedings IEEE INFOCOM 2002, 2002

Predicting and bypassing end-to-end internet service degradations.

Proceedings of the 2nd ACM SIGCOMM Internet Measurement Workshop, 2002

PAC Bounds for Multi-armed Bandit and Markov Decision Processes.

Proceedings of the Computational Learning Theory, 2002

2001

Buffer overflow management in QoS switches.

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Competitve buffer management for shared-memory switches.

Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

Loss-bounded analysis for differentiated services.

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

QoS-Competitive Video Buffering.

Proceedings of the SIROCCO 8, 2001

Convergence of Optimistic and Incremental Q-Learning.

Proceedings of the Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, 2001

Learning Rates for Q-Learning.

Proceedings of the Computational Learning Theory, 2001

Agnostic Boosting.

Proceedings of the Computational Learning Theory, 2001

Why averaging classifiers can protect against overfitting.

Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, 2001

2000

Nash Convergence of Gradient Dynamics in General-Sum Games.

Proceedings of the UAI '00: Proceedings of the 16th Conference in Uncertainty in Artificial Intelligence, Stanford University, Stanford, California, USA, June 30, 2000

Fast Planning in Stochastic Games.

Proceedings of the UAI '00: Proceedings of the 16th Conference in Uncertainty in Artificial Intelligence, Stanford University, Stanford, California, USA, June 30, 2000

Optimal smoothing schedules for real-time streams (extended abstract).

Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

Competitive Queue Policies for Differentiated Services.

Proceedings of the Proceedings IEEE INFOCOM 2000, 2000

Boosting Using Branching Programs.

Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28, 2000

Generalization Bounds for Decision Trees.

Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28, 2000

1999

Convergence Complexity of Optimistic Rate-Based Flow-Control Algorithms.

J. Algorithms, 1999

On the Complexity of Policy Iteration.

Proceedings of the UAI '99: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, Stockholm, Sweden, July 30, 1999

On Diffusing Updates in a Byzantine Environment.

Proceedings of the Eighteenth Symposium on Reliable Distributed Systems, 1999

Policy Gradient Methods for Reinforcement Learning with Function Approximation.

Proceedings of the Advances in Neural Information Processing Systems 12, [NIPS Conference, Denver, Colorado, USA, November 29, 1999

Boosting with Multi-Way Branching in Decision Trees.

Proceedings of the Advances in Neural Information Processing Systems 12, [NIPS Conference, Denver, Colorado, USA, November 29, 1999

Approximate Planning in Large POMDPs via Reusable Trajectories.

Proceedings of the Advances in Neural Information Processing Systems 12, [NIPS Conference, Denver, Colorado, USA, November 29, 1999

A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes.

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

Empirical evaluation of interest-level criteria.

Proceedings of the Data Mining and Knowledge Discovery: Theory, 1999

Reinforcement Learning and Mistake Bounded Algorithms.

Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

Estimating a Mixture of Two Product Distributions.

Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

1998

SIAM J. Comput., 1998

Optimal Broadcast with Partial Knowledge.

SIAM J. Comput., 1998

Learning Conjunctions with Noise under Product Distributions.

Inf. Process. Lett., 1998

Exact Inference of Hidden Structure from Sample Data in noisy-OR Networks.

Proceedings of the UAI '98: Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, 1998

Computation in Noisy Radio Networks.

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Competitive Dynamic Bandwidth Allocation.

Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, 1998

A Fast, Bottom-Up Decision Tree Pruning Algorithm with Near-Optimal Generalization.

Proceedings of the Fifteenth International Conference on Machine Learning (ICML 1998), 1998

Jitter Control in QoS Networks.

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

An approximation algorithm for minimum-cost network design.

Proceedings of the Robust Communication Networks: Interconnection and Survivability, 1998

1997

A Construction of a Cipher from a Single Pseudorandom Permutation.

J. Cryptology, 1997

Slide-The Key to Polynomial End-to-End Communication.

J. Algorithms, 1997

A Tight Bound for Approximating the Square Root.

Inf. Process. Lett., 1997

On Construction of

*k*-Wise Independent Random Variables.
Combinatorica, 1997

An Information-Theoretic Analysis of Hard and Soft Assignment Methods for Clustering.

Proceedings of the UAI '97: Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, 1997

Pessimistic decision tree pruning based Continuous-time.

Proceedings of the Fourteenth International Conference on Machine Learning (ICML 1997), 1997

Learning Under Persistent Drift.

Proceedings of the Computational Learning Theory, Third European Conference, 1997

Virtual-credit: Efficient end-to-end credit based flow control.

Proceedings of the Networks in Distributed Computing, 1997

Learning with Maximum-Entropy Distributions.

Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

1996

On the Boosting Ability of Top-Down Decision Tree Learning Algorithms.

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

Convergence Complexity of Optimistic Rate Based Flow Control Algorithms (Extended Abstract).

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

Phantom: A Simple and Effective Flow Control Scheme.

Proceedings of the ACM SIGCOMM 1996 Conference on Applications, 1996

Randomness in Private Computations.

Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

On the Convergence Complexity of Optimistic Rate Based Flow Control Algorithms (Brief Announcement).

Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

On Learning Conjunctions with Malicious Noise.

Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

Dynamic Bandwidth Allocation Policies.

Proceedings of the Proceedings IEEE INFOCOM '96, 1996

Applying the Waek Learning Framework to Understand and Improve C4.5.

Proceedings of the Machine Learning, 1996

1995

A Parametrization Scheme for Classifying Models of PAC Learnability

Inf. Comput., July, 1995

On Lotteries with Unique Winners.

SIAM J. Discrete Math., 1995

An O(n^(log log n)) Learning Algorithm for DNT under the Uniform Distribution.

J. Comput. Syst. Sci., 1995

epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials.

Inf. Process. Lett., 1995

Optimal Broadcast with Partial Knowledge (Extended Abstract).

Proceedings of the Distributed Algorithms, 9th International Workshop, 1995

Many-to-one packet routing on grids (Extended Abstract).

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Bandwidth allocation with preemption.

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Broadcast in Radio Networks.

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Implementation Issues in the Fourier Transform Algorithm.

Proceedings of the Advances in Neural Information Processing Systems 8, 1995

Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries.

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Competitive Access Time via Dynamic Storage Rearrangement (Preliminary Version).

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Simple Learning Algorithms for Decision Trees and Multivariate Polynomials.

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Online learning versus offline learning.

Proceedings of the Computational Learning Theory, Second European Conference, 1995

An Experimental and Theoretical Comparison of Model Selection Methods.

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994

Reliable Communication Over Unreliable Channels.

J. ACM, 1994

Trade-offs between communication throughput and parallel time.

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

On the learnability of discrete distributions.

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

Weakly learning DNF and characterizing statistical query learning using Fourier analysis.

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

1993

Learning Decision Trees Using the Fourier Spectrum.

SIAM J. Comput., 1993

Greedy Packet Scheduling on Shortest Paths.

J. Algorithms, 1993

Constant Depth Circuits, Fourier Transform, and Learnability.

J. ACM, 1993

The Impossibility of Implementing Reliable Communication in the Face of Crashes.

J. ACM, 1993

Improved selection in totally monotone arrays.

Int. J. Comput. Geometry Appl., 1993

Lower bounds for randomized mutual exclusion.

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Time optimal self-stabilizing synchronization.

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

An Omega(D log(N/D)) Lower Bound for Broadcast in Radio Networks.

Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, 1993

Efficient On-Line Call Control Algorithms.

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

The Shrinking Generator.

Proceedings of the Advances in Cryptology, 1993

1992

The Intractability of Bounded Protocols for On-Line Sequence Transmission over Non-FIFO Channels.

J. ACM, 1992

Fast Exponentiation Using the Truncation Operation.

Computational Complexity, 1992

An Efficient Topology Update Protocol for Dynamic Networks.

Proceedings of the Distributed Algorithms, 6th International Workshop, 1992

Randomized Interpolation and Approximation of Sparse Polynomials.

Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

An O(n

*) Learning Algorithm for DNF Under the Uniform Distribution.*^{log log n}
Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992

1991

Results on Learnability and the Vapnik-Chervonenkis Dimension

Inf. Comput., January, 1991

A Lower Bound for Integer Greatest Common Divisor Computations.

J. ACM, 1991

Learning Decision Trees Using the Fourier Sprectrum (Extended Abstract)

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Greedy Packet Scheduling on Shortest Paths (Preliminary Version).

Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

Broadcast with Partial Knowledge (Preliminary Version).

Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

Improved Selection on Totally Monotone Arrays.

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991

Learning Monotone

*kµ*DNF Formulas on Product Distributions.
Proceedings of the Fourth Annual Workshop on Computational Learning Theory, 1991

A Construction of a Cioher From a Single Pseudorandom Permutation.

Proceedings of the Advances in Cryptology, 1991

1990

Sorting on a Ring of Processors.

J. Algorithms, 1990

Greedy Packet Scheduling.

Proceedings of the Distributed Algorithms, 4th International Workshop, 1990

The Computational Complexity of Universal Hashing

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

The Computational Complexity of Universal Hashing.

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

Finding the Edge Connectivity of Directed Graphs.

J. Algorithms, 1989

Bit Complexity of Order Statistics on a Distributed Star Network.

Inf. Process. Lett., 1989

On Completeness and Soundness in Interactive Proof Systems.

Advances in Computing Research, 1989

The Intractability of Bounded Protocols for Non-FIFO Channels.

Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, 1989

Source to Destination Communication in the Presence of Faults.

Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, 1989

Spill Code Minimization Techniques for Optimizing Compilers.

Proceedings of the ACM SIGPLAN'89 Conference on Programming Language Design and Implementation (PLDI), 1989

Lower Bounds for Computations with the Floor Operation.

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

The Complexity of Approximating the Square Root (Extended Summary)

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Constant Depth Circuits, Fourier Transform, and Learnability

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Polynomial End-To-End Communication (Extended Abstract)

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

A Parametrization Scheme for Classifying Models of Learnability.

Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989

1988

Data Link Layer: Two Impossibility Results.

Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, 1988

Lower Bounds for Integer Greatest Common Divisor Computations (Extended Summary)

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Results on learnability and the Vapnik-Chervonenkis dimension (Extended Abstract)

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Results on Learnability and the Vapnick-Chervonenkis Dimension.

Proceedings of the First Annual Workshop on Computational Learning Theory, 1988

1987

On the Bit Complexity of Distributed Computations in a Ring with a Leader

Inf. Comput., November, 1987

Language Complexity on the Synchronous Anonymous Ring.

Theor. Comput. Sci., 1987

Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract)

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986

On the Bit Complexity of Distributed Computations in a Ring with a Leader.

Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, 1986