**Yishay Mansour - **Publications

**1986**

Y.Mansour, S.Zaks

On the bit complexity of distributed computations in a ring with a leader.

In ``Proceedings of the 5-th Annual ACM Symposium on Principles of Distributed
Computing", 151--160 (1986).

[Information and Computation 75(2), 162--177 (1987).]

**1987**

O.Goldreich, Y.Mansour, M.Sipser

Interactive proofs systems: Provers that never fail and random selection.

In 28-th Annual Symposium on Foundations of Computer Science, Los Angeles,
California, IEEE, 449--461 (1987).

[``Randomness and Computation" (Silvio Micali, ed.), 429--442. JAI press
(1989).]

I.Chlamtac, Y.Mansour

Local cycle generation in multihop radio networks.

In Proceeding of IEEE conference on Military Communications, IEEE 40.2 (1987).

H. Attiya, Y. Mansour

Language complexity on the synchronous anonymous ring.

Theoretical Computer Science 53(3), 167-185 (1987).

**1988**

N.Lynch, Y.Mansour, A.Fekete

Data link layer: Two impossibility results.

In Proceedings of the 7-th} Annual ACM Symposium on Principles of Distributed
Computing,

Toronto, Ontario, Canada ACM 149--170 (1988).

N.Linial, Y.Mansour, R.Rivest

Results on learnability and the vapnik-chervonenkis dimension.

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

White Plains, New York 120--129 (1988).

[Information and Computation 90(1), 33--49 (1991).]

Y.Mansour, B.Schieber, P.Tiwari

Lower bounds for integer greatest common divisor computations.

In 29-th Annual Symposium on Foundations of Computer Science, White Plains, New
York 54--63 (1988).

[Journal of the ACM 38:2, 453-471(1991).]

**1989**

Y.Mansour, B.Schieber, P.Tiwari

Lower bounds for computations with the floor operation.

In Proceeding of ICALP, 559-573 (1989).

SIAM Journal on Computing, 20(2), 315--327 (1991).

A.Herzberg, O.Goldreich, Y.Mansour

Source to destination communication in the presence of faults.

In Proceedings of the 8-th Annual ACM Symposium on Principles of Distributed
Computing,

Edmonton, Canada 85--102 (1989).

Y.Mansour, B.Schieber

The intractability of bounded protocols for non-FIFO channels.

In Proceedings of the 8-th Annual ACM Symposium on Principles of Distributed
Computing, Edmonton, Canada 59--72 (1989).

[Journal of the ACM, 39(4), 783--799 (1992).]

D.Bernstein, D.Goldin, M.Golumbic, H.Krawczyk, Y.Mansour, I.Nahshon,
R.Pinter

Spill code minimization techniques for optimizing compilers.

In Proceeding of SIGPLAN 89, (1989).

B.Awerbuch, Y.Mansour, N.Shavit

Polynomial end-to-end communication.

In 30-th Annual Symposium on Foundations of Computer Science,

Research Triangle Park, NC 358--363 (1989).

Y.Mansour, B.Schieber, P.Tiwari

The complexity of approximating the square root.

In 30-th Annual Symposium on Foundations of Computer Science,

Research Triangle Park, NC 325--330 (1989).

N.Linial, Y.Mansour, N.Nisan

Constant depth circuits, fourier transform, and learnability.

In 30-th Annual Symposium on Foundations of Computer Science,

Research Triangle Park, NC 574--579 (1989).

[ACM 40(3), 607--620 (1993).]

S.Ben-david, G.Benedek, Y.Mansour

A parametrization scheme for classifying models of learnability.

In Proceeding of the 2-nd annual workshop on Computational Learning Theory,

Santa Cruz, CA 285--302 (1989).

[Information and Computation 120(1):11-21 (1995).]

Y.Mansour, N.Nisan, P.Tiwari

The computational complexity of universal hash functions.

In Proceedings of the 22-nd Annual ACM Symposium on Theory of Computing,
Baltimore, Maryland 235-243 (1989).

[Theoretical Computer Science 107(1), 121--133 (1993).]

O. Gerstel, Y.Mansour, S. Zaks

Bit complexity of order statistics on a distributed star network.

Information Processing Letters 30(3), 127-132 (1989)

Y. Mamsour, B. Schiber

Finding the edge connectivity of directed graphs.

Journal of Algorithms,10(1), 76-85 (1989)

M.Fuerer, O.Goldreich, Y. Mansour, M.Sipser, S.Zachos

On the completeness and soundness in interactive proof system.

In ``Randomness and Computation" (Silvio Micali, ed.), 429--442. JAI press
(1989).

**1990**

I.Cidon, S.Kutten, Y.Mansour, D.Peleg

Greedy packet scheduling.

In Proceedings of the 4-th Annual Workshop on Distributed Algorithms, Bari,
Italy (1990).

[SIAM Journal on Computing 24:1, 148-157 (1995).]

Y. Mansour, L Schulman

Sorting on a ring of processors.

Journal of Algorithms 11(4), 622-630 (1990)

**1991**

E.Kushilevitz, Y.Mansour

Learning decision trees using the fourier spectrum.

In Proceedings of the 23-rd Annual ACM Symposium on Theory of Computing, New
Orleans, LA 455--464 (1991).

[SIAM Journal on Computing 22(6), 1331-1348 (1993).]

Y.Mansour, B.Patt-Shamir

Greedy packet scheduling on shortest paths.

In Proceedings of the 10-th Annual ACM Symposium on Principles of Distributed
Computing, Montreal, Canada (1991).

[Journal of Algorithms, 14, 449-465 (1993).]

B.Awerbuch, I.Cidon, S.Kutten, Y.Mansour, D.Peleg

Broadcast with partial knowledge.

In Proceedings of the 10-th Annual ACM Symposium on Principles of Distributed
Computing, Montreal, Canada (1991).

[Siam J. on Computing, 28(2), 511-524 (1998).]

T.Hancock, Y.Mansour

Learning monotone k-mu DNF fomulas on product distributions.

In Proceeding of the 2-nd annual workshop on Computational Learning Theory,
Santa Cruz, CA 179--183 (1991).

S.Even, Y.Mansour

A construction of a pseudorandom cipher from single pseudorandom permutation.

In Aisa-CRYPT 1991, 210-224 (1991). [J. of Cryptology (1):151-161, 1997. ]

**1992**

Y.Mansour, J.Park, S.San, B.Schieber

Improved selection in totally monotone arrays.

In FST & TCS 11, India (1992).

[International Journal of Computational Geometry and Applications 3(2),
115--132 (1993).]

Y.Mansour, J.Park, S.San, B.Schieber

B.Awerbuch, Y.Mansour

An efficient topology update protocol for dynamic networks

``$6^{th}$ Workshop on Distributed Algorithms" 185--202 (1992).

Y. Mansour

Randomized approxmation and interpolation of sparse polynomials.

In "ICALP" 261--272 (1992).

[SIAM Journal on Computing 24:2 (1995).]

Y.Mansour

An $O(n^{\log\log n})$ learning algorithm for DNF under the uniform
distribution

In Proceeding of ``COLT" 53--61 (1992).

[Journal of Computer and Systems Sciences 50(3):543-550 (1995).]

N.H. Bshouty, Y. Mansour, B. Schiber. P. Tiwari

Fast exponentiation using the truncation operation

Computational Complexity 2, 244-255 (1992).

**1993**

B.Awerbuch, S.Kutten, Y.Mansour, B.Patt-Shamir, G.Varghese

Time optimal self-stabilizing synchronization.

In ``Proceedings of the 25^{th} Annual ACM Symposium on Theory of
Computing", San Diego, CA 652--661 (1993).

E.Kushilevitz, Y.Mansour, M.Rabin, D.Zuckerman

Lower bounds for randomized mutual exclusion.

In ``Proceedings of the $25^{th}$ Annual ACM Symposium on Theory of
Computing", San Diego, CA 154--163 (1993).

[Siam J. on Computing, 27(6):1550-1563 (1998).]

D. Coppersmith, H. Krawzcyk, Y.Mansour

The shrinking generator.

In CRYPTO 22-39 (1993).

J.A. Garay, I.S. Gopal, S.Kutten, Y.Mansour, M.Yung

Efficient on--line call control mechanism.

In ``The 2nd Israel Symposium on Theory and Computing Systems" 285--293
(1993).

[Journal of Algorithms , 23:180-194, 1997]

E.Kushilevitz, Y.Mansour

An $\Omega(d\log n)$ lower bound for broadcast in radio networks.

In ``Proceedings of the $12^{th}$ Annual ACM Symposium on Principles of
Distributed Computing", Ithaca, NY 65--73 (1993).

[Siam J. on Computing, 27(3):702-712
(1998).]

A.Fekete, N.Lynch, Y.Mansour, J.Spinelli

The impossibility of implementing reliable communication in face of crashes.

Journal of the ACM 40:5, 1087-1107 (1993).

**1994**

Y.Afek, H.Attiya, A.Fekete, M.Fischer, N.Lynch, Y.Mansour, D.Wang, L.Zuck.

Reliable communication over unreliable channels.

Journal of the ACM 41:6, 1267-1297 (1994).

Y. Mansour, N. Nisan, U. Vishkin

Trade-offs between communication throughput
and parallel time.

In ``The 26th Annual ACM Symposium on Theory of Computing" 372--381
(1994).

[J. of Complexity 15(1):148-166 (1999).]

A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, S. Rudich

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

In ``The 26th Annual ACM Symposium on Theory of Computing" 253--262
(1994).

H. Karloff, Y. Mansour

On construction of $k$-wise independent
random variables.

In ``The 26th Annual ACM Symposium on Theory of Computing" 564--573
(1994).

[Combinatorica, 17(1) 91-107, 1997]

M. Kearns, Y. Mansour, D. Ron, R. Rubinfel, R.E. Schapire, L. Sellie

On the learnability of discrete
distributions.

In ``The 26th Annual ACM Symposium on Theory of Computing" 273--282
(1994).

Y. Mansour.

Learning Boolean Functions via the
Fourier Transform.

In ``Theoretical Advances in Neural Computation and Learning",

(V.P. Roychodhury and K-Y. Siu and A. Orlitsky, ed.), 391--424 (1994).

**1995**

I.Gaber and Y.Mansour.

Broadcast in radio networks.

In ``The 6th ACM-Siam Symposium on Discrete Algorithms" 577--585 (1995).

[Journal of Algorithms, 46(1): 1-20, (2003)]

Shai Ben-David, Eyal Kushilevitz, and Yishay Mansour.

Online learning versus offline learning.

In Euro-Colt (1995).

[Machine Learning, 29:45-63, 1997]

Y.Mansour and Boaz Patt-Shamir.

Many-to-one packet routing on grids.

In ``The 26th Annual ACM Symposium on Theory of Computing", 1995.

Amotz Bar-Noy, Ran Canetti, Shay Kutten, Y.Mansour, and Baruch Schieber.

Bandwidth allocation with preemption.

In ``The 26th Annual ACM Symposium on Theory of Computing", 1995.

[Siam J. on Computing 28(5):1806-1828 (1999).]

Michael Kearns, Yishay Mansour, AndrewY. Ng, and Dana Ron.

An experimental and theoretical comparison of
model selection methods.

In ``Proceeding of the $8^{th}$ annual workshop on Computational Learning
Theory" 21--30 (1995).

[Special issue of Machine Learning Journal, 7:7-50, 1997]

Meir Feder, Yoav Freund, and Yishay Mansour.

Optimal on-line prediction of conditional distributions.

In ``International Symposium on Information Theory" (1995).

Amos Fiat, Y.Mansour, Adi Ros\'en, and Orli Waarts.

Competitive access time via dynamic storage
rearrangement.

In ``$36^{th}$ Annual Symposium on Foundations of Computer Science",
392--401 (1995).

NaderH. Bshouty and Yishay Mansour.

Simple learning algorithms for decision
trees and multivariate polynomials.

In ``$36^{th}$ Annual Symposium on Foundations of Computer Science",
304--311 (1995).

[Siam J. on Computing, 31(6), 1909-1925 (2003).]

Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld and
Robert E. Schapire.

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

In ``$36^{th}$ Annual Symposium on Foundations of Computer Science",
332--341 (1995).

Baruch Awerbuch, Shay Kutten, Yishay Mansour, and David Peleg.

Optimal broadcast with partial knowledge.

In ``Proceedings of the $9^{th}$ Annual Workshop on Distributed
Algorithms", 116-130(1995).

[Siam J. on Computing, 28(2), 511-524 (1998).]

Yishay Mansour and Sigal Sahar.

Implementation issues in the fourier transform
algorithm.

In ``Nerual Information Processing Systems'', 260-265,(1995).

[Machine Learning Journal 40(1):5-33 (2000).]

E. Kushilevits, Y. Mansour, M. Rabin

On lotteries with unique winners.

Siam J. on Discrete Math 8(1):93-98 (1995)

N. Alon, Y. Mansour

epsilon discrepancy sets and their applications
for interpolation and of sparse polynomials.

Information Processing Letters, 54:337-342 (1995).

**1996**

Yehuda Afek, Menashe Cohen, Eyal Hallmann, and Yishay Mansour.

Dynamic bandwidth allocation.

In InfoComm, 880-887,(1996).

Yehuda Afek, Yishay Mansour, and Zvi Ostfeld.

On the convergence of rate based flow control.

In STOC, 89-108,1996.

[J. of Algorithms 30(1):106-143(1999)]

Yehuda Afek, Yishay Mansour, and Zvi Ostfeld.

Phantom: A simple and effective flow control
scheme.

In SIGCOMM, 1996.

[Computer networks, 32(2000) 277-305, (2000).]

Michael Kearns and Yishay Mansour.

On the boosting ability of top-down decision tree
learning algorithms.

In STOC, 459-468,1996

[JCSS, 58(1):109-128 (1999)]

Tom Dietterich, Michael Kearns and Yishay Mansour

Applying the Weak Learning Framework to understand
and improve C4.5

In Proc. of Machine Learning, 1996

Eyal Kushilevitz and Yishay Mansour.

Randomness in private computations.

In PODC, 181-190,1996.

[Siam J. on Discrete Math, 10(4): 647-661 (1997).]

Yishay Mansour and Michal Parnas.

On learning conjunctions with malicious noise.

In Proceedings of ISTCS, 1996.

[Information Processing Letters 68:189-196 (1998).]

**1997**

Yoav Freund and Yishay Mansour.

Learning under persistent drift.

In Proceedings of EuroColt, 109-118,1997.

Michael Kearns, Yishay Mansour, and AndrewY. Ng.

An information theoretic analysis of hard and soft clustering.

In Proceedings of Uncertainty in AI, 1997

[``Learning in Graphical Models'' (Michael Jordon, ed.), 495-520 (1999).]

Yishay Mansour.

Pessimistic decision tree pruning.

In Proceedings of Machine Learning, 195-201, 1997.

Yishay Mansour and Mariano Schain.

Learning with maximum-entropy distributions.

In Colt, 201-210,1997.

[Machine Learning 45(2):123-145 (2001)]

Y. Afek, B. Awerbuch,E. Gafni, Y. Mansour, A. Rosen, N. Shavit

Slide - the key to polynomial end-to-end
communication.

J. of Algorithms 22(1): 158-186 (1997)

Nader H. Bshouty, Yishay Mansour, Baruch Schieber, Prasoon Tiwari:

A Tight Bound for Approximating the Square Root.

Inf. Process. Lett. 63(4): 211-213 (1997)

**1998**

Eyal Kushilevitz and Yishay Mansour

Computation in Noisy Radio Networks

In ACM-SIAM symposium on discrete algorithms (SODA), 236-243, 1998

[Siam J. on Discrete Math 19(1), 96-108, 2005]

M. Kearns, Y. Mansour

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

In ``Proceeding of Uncertainty in Artificial Intelligence", 304-310
(1998).

M. Kearns, Y. Mansour

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

In `` Proceeding of the International Conference on Machine Learning",
269-277 (1998).

Amotz Bar-Noy, Yishay Mansour and Baruch Schieber

Competitive Dynamic Bandwidth Allocation

In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed
Computing 1998

Yishay Mansour and Boaz Patt-Shamir

Jitter Control in QoS Networks

In 39th Annual Symposium on Foundations of Computer Science 1998

[IEEE/ACM Trans. On Networking 4(9):492-502 (2001)

Yishay Mansour and David Peleg

An Approximation Algorithm for Minimum-Cost
Network Design

DIMACS Workshop on Robust Communication Networks, 1998

**1999**

M. Kearns and Y. Mansour and A. Ng

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

IJCAI, 1999

[Machine Learning 49(2-3): 193-208 (2002)]

Y. Mansour and S. Singh

On the Complexity of Policy Iteration

UAI, 1999

Y. Mansour

Reinforcement Learning and Mistake Bounded
Algorithms

COLT, 1999

Y. Freund and Y. Mansour

Estimating a mixture of two product distributions

COLT, 1999

Y. Mansour and D. MaAllester

Boosting with Multi-Way Branching in Decision
Trees

NIPS 1999.

R. Sutton and D. McAllester and S. Singh and Y. Mansour

Policy Gradient Methods for Reinforcement
Learning with Function Approximation

NIPS 1999.

M. Kearns, Y. Mansour and A. Ng

Approximate Planning in Large POMDPs via Reusable
Trajectories

NIPS, 1999

D. Malkhi, Y. Mansour and M. K. Reiter,

On Diffusing Updates in a Byzantine Environment,

Symposium on Reliable Distributed Systems (SRDS), 134-143, 1999

[Theoretical Computer Science, 1-3(299):289-306 (2003).]

Y. Afek, Y. Mansour, Z. Ostfeld,

Virtual-Credit: Efficient End-to-End Credit Based Flow Control,

Special issue on Networks in Distributed Computing

published by the American Mathematical Society in the DIMACS

Series. 45:1-21 (1999).

**2000**

William Aiello, Yishay Mansour, S. Rajagpopalan and Adi Rosen

Competitive queue policies for diffrentiated
services

INFOCOM 2000.

[J. Algorithms 55(2): 113-141 (2005)]

Yishay Mansour, Boaz Patt-Shamir and Ofer Lapid

Optimal Smoothing Schedules for Real-time Streams

PODC 2000

[To appear in Distribute Computing]

Yishay Mansour and David McAllester

Boosting using Branching Programs

COLT 2000

[JCSS 64(1): 103-112 (2002). (Special issue for COLT 2000)]

Yishay Mansour and David McAllester

Generalization Bounds for Decision Trees

COLT 2000

Singh S, Kearns M, Mansour Y.

Nash Convergence of Gradient Dynamics in
General-Sum Games.

In UAI 2000.

Kearns M, Mansour Y, Singh S.

Fast Planning in Stochastic Games.

In UAI 2000.

**2001**

Alexander Kesselman and Yishay Mansour

Loss bounded analysis for differentiated services

In (SODA) 2001, 591-600

[Journal of Algorithms, 46(1): 79-95, (2003)]

Yoav Freund Yishay Mansour and Robert E. Schapire,

Why averaging classifiers can protect against
overfitting

In Proceeding of the Eighth International Workshop on Artificial Intelligence
and

Statistics, 2001

[To appear in The Annals of Statistics]

Alexander Kesselman and Yishay Mansour

QoS-Competitive Video Buffering,

SIROCCO, 2001

[Also in Computing and Informatics]

Ellen L. Hahne, Alexander Kesselman and Yishay Mansour

Competitive Buffer Management for Shared-Memory Switches

SPAA, 2001

Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch
Schieber, Maxim Sviridenko

Buffer Overflow Management in QoS Switches,

STOC, 2001

[SIAM J. Comput. 33(3): 563-583 (2004)]

Eyal Even-Dar Yishay Mansour,

Learning Rates for Q-Learning

The Fourteenth Annual Conference on Computational Learning Theory, 589-604
(2001)

[Journal of Machine Learning Research 5 (Dec):1-25, 2003]

Shai Ben-David, Phil Long and Yishay Mansour,

Agnostic Boosting

The Fourteenth Annual Conference on Computational Learning Theory 2001

E. Even-Dar and Y. Mansour.

Convergence of Optimistic and Incremental Q-Learning

Advances in Neural Information Processing Systems 14 (NIPS), 2001, pp.
1499-1506.

**2002**

Alexander Kesselman and Yishay Mansour,

Harmonic Buffer Management Policy for Shared Memory Switches,

InfoCom, 2002.

[Theor. Comput. Sci. 324(2-3): 161-182 (2004)]

Eyal Even-Dar, Shie Mannor, and Yishay Mansour,

PAC Bounds for Multi-Armed Bandit and Markov Decision Processes,

The Fifthteenth Annual Conference on Computational Learning Theory 2002

Michael Kearns and Yishay Mansour,

Efficient Nash Computation in Large Population Games with Bounded Influence,

18th Conference on Uncertainty in Artificial Intelligence, 2002

Anat Bremler-Barr, Idit Cohen, Haim Kaplan , and Yishay Mansour.

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

Internet Meassurement Workshop (IMW) 2002

[IEEE Journal on Selected Areas in
Communications (JSAC), 21(6):961-978 (2003)]

Noga Alon, Oded Goldreich, and Yishay Mansour

Almost k-wise independence versus k-wise
independence

ECCC TR02-048

[Inf. Process. Lett. 88(3): 107-110 (2003)]

**2003**

Nir Andelman, Yishay Mansour , and An Zhu .

Competitive Queueing Policies for QoS Switches.

14th ACM-SIAM Symposium on Discrete Algorithms (SODA), (Jan. 2003).

Alexander Kesselman,Yishay Mansour and Rob van Stee,

"Improved Competitive Guarantees for QoS Buffering,"

In ESA 2003.

[Special Issue of Algorithmica on
Network Design. Editor: Lisa Zhang:
Algorithmica 43(1-2): 63-80 (2005)]

Alexander Kesselman, Zvi Lotker, Yishay Mansour and Boaz Patt-Shamir,

"Buffer Overflows of Merging Streams,"

In ESA 2003

Alexander Kesselman and Yishay Mansour,

"Adaptive AIMD Congestion Control,"

In PODC 2003.

[Special Issue of Algorithmica on Network
Design. Editor: Lisa Zhang Algorithmica 43(1-2): 97-111 (2005)]

Baruch Awerbuch, Yishay Mansour

Adapting to a Reliable Network Path

In PODC 2003.

Eyal Even-Dar, Alexander Kesselman and Yishay Mansour,

"Convergence Time to Nash Equilibria,"

In ICALP 2003. [Also: ACM Transactions on Algorithms,
Vol. 3, No. 3, August 2007]

Yossi Azar, Avrim Blum, and Yishay Mansour

Combining Online Algorithms for Rejection and Acceptance

In SPAA 2003

[Theory of Computating, 1(2005), pp. 105-117]

Amir Maor, Yishay Mansour

'AdaVegas: Adaptive Control for TCP Vegas'

Globecom 2003

Eyal Even-Dar and Yishay Mansour

Approximate Equivalence of Markov Decision Processes

COLT 2003

Eyal
Even-Dar Shie Mannor and Yishay Mansour

Action Elimination and Stopping Conditions for Reinforcement Learning

ICML 2003

[Journal of Machine Learning Research 7: 1079-1105 (2006)]

Nir Andelman and Yishay Mansour.

Competitive Management of Non-Preemptive Queues with Multiple Values.

17th International Symposium on Distributed Computing (DISC) 2003.

**2004**

Sham Kakade, Michael Kearns, Yishay Mansour, and Luis Ortiz.

Competitive Algorithms for VWAP and Limit Order
Trading.

ACM Electronic Commerce Conference 2004.

Nir Andelman and Yishay Mansour

Randomized Queue Management for DiffServ

OLAP 2004

Nir Andelman and Yishay Mansour

Auctions with Budget Constraints

SWAT 2004

David P. Bunde and Yishay Mansour

Improved Combination of Online Algorithms for
Acceptance and Rejection

SPAA 2004

[Theory of Computating, 1(2005), pp. 105-117]

Evgeny Drukh and Yishay Mansour

Concentration Bounds for Unigrams Language Model

COLT 2004

[JMLR
6(Aug):1231--1264, 2005]

Amotz Bar-Noy and Yishay Mansour

Competitive On-Line Paging Strategies for Mobile
Users Under Delay Constraints

PODC 2004

E. Even-Dar, Sham Kakade and Y. Mansour.

Experts in a Markov Decision Process.

Advances in Neural Information Processing Systems 17 (NIPS), 2004.

**2005**

E. Even-Dar and Y. Mansour.

Fast Convergence of Selfish Rerouting.

Sixteenth ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005.

Alexander Kesselman and Yishay Mansour,

Optimizing TCP Retransmission Timeout

ICN'2005

Haim Kaplan, Eyal Kushilevtiz and Yishay Mansour

Learning with Attribute Costs

STOC 2005

Eyal Even-Dar, Sham Kakade
and Yishay Mansour.

Reinforcement Learning in POMDPs without Resets.

Nineteenth International Joint Conference on Artificial Intelligence (IJCAI)
2005.

Nicoḷ
Cesa-Bianchi, Yishay Mansour and Gilles Stoltz

Improved Second-Order Bounds for Prediction with
Expert Advice

COLT 2005

[Machine Learning , 66(2/3):321-352, 2007.]

Avrim Blum and Yishay Mansour

From External to Internal Regret

COLT 2005

Eyal Even-Dar and Sham M. Kakade and Yishay Mansour

Planning in POMDPS using Multiplicity Automata

UAI 2005

Maria-Florina balcan, Avrim Blum, Jason Hartline and Yishay Mansour

Mechanism Design via Machine Learning

FOCS, 2005

A.
Kalai and A. Klivans and Y. Mansour and R. Servedio.

Agnostically Learning Halfspaces.

FOCS, 2005

[Accepted to special issue of Siam J. on Computing.]* *

Shai Fine, Arie Freund, Itai Jaeger, Yishay Mansour, Yehuda Naveh, and Ave Ziv,

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

Proc. High Level Design Validation and Test Workshop (HLDVT) 2005.

[Journal version: IEEE Transactions on Computers 55(11): 1344-1355 (2006)]

**2006**

S. Albers, S. Eilts, E. Even-Dar, Y. Mansour and L. Roditty.

On Nash Equilibria for a Network Creation Game.

Seventeenth ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006

Tzur Sayag, Shai Fine and Yishay Mansour

Combining Multiple Heuristics

STACS 2006

Peter DeMarzo and Ilan Kremer and Yishay Mansour

Online Trading Algorithms and Robust Option
Pricing

STOC 2006

Nir Andelman, Yishay Mansour

**A
Sufficient Condition for Truthfulness with Single Parameter Agents**

ACM EC 2006

Eyal Even-Dar, Sham Kakade, Michael Kearns, and Yishay Mansour

**(In)Stability
Properties of Limit Order Dynamics**

ACM EC 2006

Shai Fine and YishayMansour

Active Sampling for Multiple Output Identification

COLT 2006

Eyal
Even-Dar, Sham M. Kakade, Yishay Mansour:

The Value of Observation for Monitoring Dynamic
Systems.

IJCAI 2007: 2474-2479

Nir Andelman, Michal Feldman and Yishay Mansour

Strong Price of Anarchy

Seventeenth ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007

Amir Epstein, Michal Feldman and Yishay Mansour

Strong Equilibrium in Cost-Sharing Connection Game

In Proceedings of the 8th ACM Conference on Electronic Commerce (EC'07)

Sergiu Hart and Yishay Mansour

The Communication Complexity of Uncoupled Nash
Equilibrium Procedures

STOC 2007

Eyal Even-Dar, Michael Kearns, Yishay Mansour and Jenn Wortman

Regret to the Best vs. Regret to the average.

COLT 2007

Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, and George
Varghese

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

IEEE Transactions on Dependable and Secure Computing (to appear)