# Yishay Mansour

According to our database1, Yishay Mansour authored at least 336 papers between 1987 and 2021.

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

## ACM Fellow

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

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2021
Differentially Private Multi-Armed Bandits in the Shuffle Model.
CoRR, 2021

Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions.
CoRR, 2021

Minimax Regret for Stochastic Shortest Path.
CoRR, 2021

Competitive Equilibria with Unequal Budgets: Supporting Arbitrary Pareto Optimal Allocations.
CoRR, 2021

Online Markov Decision Processes with Aggregate Bandit Feedback.
CoRR, 2021

Separating Adaptive Streaming from Oblivious Streaming.
CoRR, 2021

A Theory of Multiple-Source Adaptation with Limited Target Labeled Data.
Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020
Bayesian Incentive-Compatible Bandit Exploration.
Oper. Res., 2020

Learning Adversarial Markov Decision Processes with Delayed Feedback.
CoRR, 2020

CoRR, 2020

Kidney exchange and endless paths: On the optimal use of an altruistic donor.
CoRR, 2020

The Sparse Vector Technique, Revisited.
CoRR, 2020

Oracle-Efficient Reinforcement Learning in Factored MDPs with Unknown Structure.
CoRR, 2020

Beyond Individual and Group Fairness.
CoRR, 2020

Detecting malicious PDF using CNN.
CoRR, 2020

Competing Bandits: The Perils of Exploration Under Competition.
CoRR, 2020

A Theory of Multiple-Source Adaptation with Limited Target Labeled Data.
CoRR, 2020

CoRR, 2020

Three Approaches for Personalization with Applications to Federated Learning.
CoRR, 2020

Unknown mixing times in apprenticeship and reinforcement learning.
Proceedings of the Thirty-Sixth Conference on Uncertainty in Artificial Intelligence, 2020

Sample Complexity of Uniform Convergence for Multicalibration.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Adversarially Robust Streaming Algorithms via Differential Privacy.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Reinforcement Learning with Feedback Graphs.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Online Revenue Maximization for Server Pricing.
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020

Near-optimal Regret Bounds for Stochastic Shortest Path.
Proceedings of the 37th International Conference on Machine Learning, 2020

Efficient Candidate Screening Under Multiple Tests and Implications for Fairness.
Proceedings of the 1st Symposium on Foundations of Responsible Computing, 2020

Privately Learning Thresholds: Closing the Exponential Gap.
Proceedings of the Conference on Learning Theory, 2020

Planning in Hierarchical Reinforcement Learning: Guarantees for Using Local Policies.
Proceedings of the Algorithmic Learning Theory, 2020

Top-$k$ Combinatorial Bandits with Full-Bandit Feedback.
Proceedings of the Algorithmic Learning Theory, 2020

Thompson Sampling for Adversarial Bit Prediction.
Proceedings of the Algorithmic Learning Theory, 2020

Apprenticeship Learning via Frank-Wolfe.
Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

Designing Committees for Mitigating Biases.
Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019
Dynamics of Evolving Social Groups.
ACM Trans. Economics and Comput., 2019

Delay and Cooperation in Nonstochastic Bandits.
J. Mach. Learn. Res., 2019

Beyond myopic best response (in Cournot competition).
Games Econ. Behav., 2019

The Role of A-priori Information in Networks of Rational Agents.
CoRR, 2019

Combinatorial Bandits with Full-Bandit Feedback: Sample Complexity and Regret Minimization.
CoRR, 2019

Repeated A/B Testing.
CoRR, 2019

Average reward reinforcement learning with unknown mixing times.
CoRR, 2019

Competitive ratio versus regret minimization: achieving the best of both worlds.
CoRR, 2019

Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret.
CoRR, 2019

Learning and Generalization for Matching Problems.
CoRR, 2019

Graph-based Discriminators: Sample Complexity and Expressiveness.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Learning to Screen.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Online Stochastic Shortest Path with Bandit Feedback and Unknown Transition Function.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Online Convex Optimization in Adversarial Markov Decision Processes.
Proceedings of the 36th International Conference on Machine Learning, 2019

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
Learning What's Going on: Reconstructing Preferences and Priorities from Opaque Transactions.
ACM Trans. Economics and Comput., 2018

Making the Most of Your Samples.
SIAM J. Comput., 2018

Constant-Time Local Computation Algorithms.
Theory Comput. Syst., 2018

Optimal Algorithm for Bayesian Incentive-Compatible.
CoRR, 2018

Are All Experts Equally Good? A Study of Analyst Earnings Estimates.
CoRR, 2018

Planning and Learning with Stochastic Action Sets.
CoRR, 2018

Flow Equilibria via Online Surge Pricing.
CoRR, 2018

Hierarchical Reinforcement Learning: Approximating Optimal Discounted TSP Using Local Policies.
CoRR, 2018

Are Two (Samples) Really Better Than One? On the Non-Asymptotic Performance of Empirical Revenue Maximization.
CoRR, 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

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

Scheduling multipacket frames with frame deadlines.
J. Sched., 2017

Upward Max-Min Fairness.
J. ACM, 2017

Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251).
Dagstuhl Reports, 2017

Automatic Representation for Lifetime Value Recommender Systems.
CoRR, 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
Local Computation Mechanism Design.
ACM Trans. Economics and Comput., 2016

The AND-OR Game.
ACM Trans. Economics and Comput., 2016

Lower bounds on individual sequence regret.
Mach. Learn., 2016

Robust option pricing: Hannan and Blackwell meet Black and Scholes.
J. Econ. 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

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
Regret Minimization for Reserve Prices in Second-Price Auctions.
IEEE Trans. Inf. Theory, 2015

Optimistic-Conservative Bidding in Sequential Auctions.
CoRR, 2015

On the geometry of output-code multi-class learning.
CoRR, 2015

Online Allocation and Pricing with Economies of Scale.
Proceedings of the Web and Internet Economics - 11th International Conference, 2015

Robust Probabilistic Inference.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 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
On Nash Equilibria for a Network Creation Game.
ACM Trans. Economics and Comput., 2014

Competitive router scheduling with structured data.
Theor. Comput. Sci., 2014

Probe scheduling for efficient detection of silent failures.
Perform. Evaluation, 2014

Repeated Budgeted Second Price Ad Auction.
Theory Comput. Syst., 2014

Ann. Math. Artif. Intell., 2014

Thompson Sampling for Complex Online Problems.
Proceedings of the 31th International Conference on Machine Learning, 2014

2013
The Price of Uncertainty.
ACM Trans. Economics and Comput., 2013

Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior.
SIAM J. Comput., 2013

Electronic Markets and Auctions (Dagstuhl Seminar 13461).
Dagstuhl Reports, 2013

Nash Convergence of Gradient Dynamics in Iterated General-Sum Games
CoRR, 2013

Thompson Sampling for Complex Bandit Problems.
CoRR, 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

Networks, 2012

Distributed Learning, Communication Complexity and Privacy.
Proceedings of the COLT 2012, 2012

Reliable agnostic learning.
J. Comput. Syst. Sci., 2012

CoRR, 2012

Overflow management with multipart packets.
Comput. Networks, 2012

The AND-OR Game: Equilibrium Characterization - (Working Paper).
Proceedings of the Internet and Network Economics - 8th International Workshop, 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

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

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

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

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 Econ. Behav., 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

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 Econ. Behav., 2009

Strong equilibrium in cost sharing connection games.
Games Econ. Behav., 2009

Strong price of anarchy.
Games Econ. Behav., 2009

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

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

Domain Adaptation: Learning Bounds and Algorithms.
Proceedings of the COLT 2009, 2009

Online Learning for Global Cost Functions.
Proceedings of the COLT 2009, 2009

2008
Competitive buffer management for shared-memory switches.
ACM Trans. Algorithms, 2008

Item pricing for revenue maximization.
SIGecom Exch., 2008

Agnostically Learning Halfspaces.
SIAM J. Comput., 2008

Regret to the best vs. regret to the average.
Mach. Learn., 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

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 Secur. Comput., 2007

Convergence time to Nash equilibrium in load balancing.
ACM Trans. Algorithms, 2007

Active sampling for multiple output identification.
Mach. Learn., 2007

Improved second-order bounds for prediction with expert advice.
Mach. Learn., 2007

From External to Internal Regret.
J. Mach. Learn. Res., 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

The Value of Observation for Monitoring Dynamic Systems.
Proceedings of the IJCAI 2007, 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.
J. Mach. Learn. Res., 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

(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

2005
Combining Online Algorithms for Acceptance and Rejection.
Theory Comput., 2005

SIAM J. Discret. Math., 2005

Concentration Bounds for Unigram Language Models.
J. Mach. Learn. Res., 2005

Competitive queue policies for differentiated services.
J. Algorithms, 2005

Improved Competitive Guarantees for QoS Buffering.
Algorithmica, 2005

Algorithmica, 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

Mechanism Design via Machine Learning.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
Harmonic buffer management policy for shared memory switches.
Theor. Comput. Sci., 2004

Buffer Overflow Management in QoS Switches.
SIAM J. Comput., 2004

Optimal smoothing schedules for real-time streams.
Distributed Comput., 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

Predicting and bypassing end-to-end Internet service degradations.
IEEE J. Sel. Areas Commun., 2003

Learning Rates for Q-learning.
J. Mach. Learn. Res., 2003

Loss-bounded analysis for differentiated services.
J. Algorithms, 2003

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

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

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

Proceedings of the Global Telecommunications Conference, 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
Simple Learning Algorithms for Decision Trees and Multivariate Polynomials.
SIAM J. Comput., 2002

A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes.
Mach. Learn., 2002

Boosting Using Branching Programs.
J. Comput. Syst. Sci., 2002

QoS-Competitive Video Buffering.
Comput. Artif. Intell., 2002

Efficient Nash Computation in Large Population Games with Bounded Influence.
Proceedings of the UAI '02, 2002

PAC Bounds for Multi-armed Bandit and Markov Decision Processes.
Proceedings of the Computational Learning Theory, 2002

2001
Jitter control in QoS networks.
IEEE/ACM Trans. Netw., 2001

Learning with Maximum-Entropy Distributions.
Mach. Learn., 2001

Competitve buffer management for shared-memory switches.
Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 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

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
Implementation Issues in the Fourier Transform Algorithm.
Mach. Learn., 2000

Phantom: a simple and effective flow control scheme.
Comput. Networks, 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

Generalization Bounds for Decision Trees.
Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28, 2000

1999
Bandwidth Allocation with Preemption.
SIAM J. Comput., 1999

On the Boosting Ability of Top-Down Decision Tree Learning Algorithms.
J. Comput. Syst. Sci., 1999

Trade-offs between Communication Throughput and Parallel Time.
J. Complex., 1999

Convergence Complexity of Optimistic Rate-Based Flow-Control Algorithms.
J. Algorithms, 1999

On Propagating Updates in a Byzantine Environment
CoRR, 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

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
Lower Bounds for Randomized Mutual Exclusion.
SIAM J. Comput., 1998

SIAM J. Comput., 1998

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

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

An approximation algorithm for minimum-cost network design.
Proceedings of the Robust Communication Networks: Interconnection and Survivability, 1998

An Information-Theoretic Analysis of Hard and Soft Assignment Methods for Clustering.
Proceedings of the Learning in Graphical Models, 1998

1997
Randomness in Private Computations.
SIAM J. Discret. Math., 1997

An Experimental and Theoretical Comparison of Model Selection Methods.
Mach. Learn., 1997

Online Learning versus Offline Learning.
Mach. Learn., 1997

A Construction of a Cipher from a Single Pseudorandom Permutation.
J. Cryptol., 1997

Efficient On-Line Call Control Algorithms.
J. Algorithms, 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 <i>k</i>-Wise Independent Random Variables.
Comb., 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

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

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. Discret. Math., 1995

Randomized Interpolation and Approximation of Sparse Polynomials.
SIAM J. Comput., 1995

Greedy Packet Scheduling.
SIAM J. Comput., 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

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

1994
Reliable Communication Over Unreliable Channels.
J. ACM, 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
The Computational Complexity of Universal Hashing.
Theor. Comput. Sci., 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. Geom. Appl., 1993

Time optimal self-stabilizing synchronization.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, 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.
Comput. Complex., 1992

An Efficient Topology Update Protocol for Dynamic Networks.
Proceedings of the Distributed Algorithms, 6th International Workshop, 1992

An O(n<i><sup>log log n</sup></i>) Learning Algorithm for DNF Under the Uniform Distribution.
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

Lower Bounds for Computations with the Floor Operation.
SIAM J. Comput., 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 <i>kµ</i> 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

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.

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

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

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