Table of Contents

• Refereed Journal Papers
• Refereed Conference Papers
• Miscellaneous

On the absolute approximation ratio for First Fit and related results

J. Boyar, G. Dósa, L. Epstein
Discrete Applied Mathematics, accepted 2012.
Abstract.

Logic minimization techniques with applications to cryptology

J. Boyar, R. Peralta
Journal of Cryptology, accepted 2012.
Abstract.

A new variable-sized bin packing problem

J. Boyar, L.M. Favrholdt
Journal of Scheduling, 15:273-287, 2012.
Abstract.

A theoretical comparison of LRU and LRU-2

J. Boyar, M.R. Ehmsen, J.S. Kohrt, K.S. Larsen
Acta Informatica, 47: 359-374, 2010.
Abstract.

Tight results for Next Fit and Worst Fit with resource augmentation

J. Boyar, L. Epstein, A. Levin
Theoretical Computer Science, 411: 2572-2580, 2010.
DOI: 10.1016/j.tcs.2010.03.019
Abstract.

Scheduling jobs on Grid processors

J. Boyar, L.M. Favrholdt
Algorithmica, 57(4), 819-847, 2010.
DOI: 10.1007/s00453-008-9257-0
Abstract.

Priority algorithms for graph optimization problems

A. Borodin, J. Boyar, K.S. Larsen, N. Mirmohammadi
Theoretical Computer Science, 411: 239-258, 2010.
Older abstract.

The relative worst order ratio applied to seat reservation

J. Boyar, P. Medvedev
ACM Transactions on Algorithms, 4(4), article 48, 22 pages, 2008.
Abstract.

Tight bounds for the multiplicative complexity of symmetric functions

J. Boyar, R. Peralta
Theoretical Computer Science, 396: 223-246, 2008.
Abstract.

The relative worst order ratio applied to paging

J. Boyar, L.M. Favrholdt, K.S. Larsen
Journal of Computer and System Sciences, 73: 818-843, 2007.
Abstract.

The relative worst order ratio for on-line algorithms

J. Boyar, L.M. Favrholdt
ACM Transactions on Algorithms, 3(2), article 22, 24 pages, 2007.
Abstract.

The maximum resource bin packing problem

J. Boyar, L. Epstein, L.M. Favrholdt, J.S. Kohrt, K.S. Larsen, M.M. Pedersen, S. Wøhlk
Theoretical Computer Science, 362: 127-139, 2006.
Abstract

Seat reservation allowing seat changes

J. Boyar, S. Krarup, M.N. Nielsen
Journal of Algorithms, 52: 169-192, 2004.
Abstract.

Extending the accommodating function

J. Boyar, L.M. Favrholdt, K.S. Larsen, M.N. Nielsen
Acta Informatica, 40: 3-35, 2003.
Abstract.

Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem

E. Bach, J. Boyar, L. Epstein, L.M. Favrholdt, T. Jiang, K.S. Larsen, G.-H. Lin, R. van Stee
Journal of Scheduling, 6(2): 131-147, 2003.
Abstract.

Fair versus unrestricted bin packing

Y. Azar, J. Boyar, L. Epstein, L.M. Favrholdt, K.S. Larsen, M.N. Nielsen
Algorithmica, 34(2): 181-196, 2002.
Abstract.

The competitive ratio for on-line dual bin packing with restricted input sequences

J. Boyar, L.M. Favrholdt, K.S. Larsen, M.N. Nielsen
Nordic Journal of Computing, 8(4): 463-472, 2001.
Abstract.

The accommodating function: a generalization of the competitive ratio

J. Boyar, K.S. Larsen, M.N. Nielsen
SIAM Journal on Computing, 31(1): 233-258, 2001.
Abstract.

Short non-interactive cryptographic proofs

J. Boyar, I. Damgård, R. Peralta
Journal of Cryptology 13(4): 449-472, 2000.
Paper.

On the multiplicative complexity of boolean functions over the basis (AND, XOR, 1)

J. Boyar, R. Peralta, D. Pochuev
Theoretical Computer Science 235(1):43-57, 2000.
Abstract.

The seat reservation problem

Joan Boyar, K.S. Larsen
Algorithmica 25(4): 403-417, 1999.
Abstract.

Amortization results for chromatic search trees, with an application to priority queues

J. Boyar, R. Fagerberg, K.S. Larsen
Journal of Computer and System Sciences 55(3):504-521, 1997.
Abstract.

Subquadratic zero-knowledge

J. Boyar, G. Brassard, R. Peralta
Journal of the Association for Computing Machinery 42: 1169-1193, 1995.

Efficient rebalancing of chromatic search trees

J. Boyar, K.S. Larsen
Journal of Computer and System Sciences, 49(3):667-682, 1994.
Abstract.

Bounds on certain multiplications of affine combinations

J. Boyar, F. Fich, K.S. Larsen
Discrete Applied Mathematics, 52(2):155-167, 1994.
Abstract.

On the communication complexity of zero-knowledge proofs

J. Boyar, C. Lund, R. Peralta
Journal of Cryptology 6: 65-85, 1993.

An arithmetic model of computation equivalent to threshold circuits

J. Boyar, G. Frandsen, C. Sturtivant
Theoretical Computer Science 93: 303-319, 1992.

Practical zero-knowledge proofs: giving hints and using deficiencies

J. Boyar, K. Friedl, C. Lund
Journal of Cryptology 4: 185-206, 1991.

A discrete logarithm implementation of perfect zero-knowledge blobs

J. Boyar, M. Krentel, S. Kurtz
Journal of Cryptology 2: 63-76, 1990.

Inferring sequences produced by a linear congruential generator missing low order bits

J. Boyar
Journal of Cryptology 1: 177-184, 1989.

Inferring sequences produced by pseudo-random number generators

J. Boyar
Journal of the ACM 36: 129-141, 1989.

Coloring planar graphs in parallel

J. Boyar, H. Karloff
Journal of Algorithms 8: 470-479, 1987.

Bounds for cube coloring

B.R Plumstead, J.B. Plustead
SIAM Journal on Algebraic and Discrete Methods 6: 73-78, 1985.

Access graphs results for LRU versus FIFO under relative worst order analysis

J. Boyar, S. Gupta and K.S. Larsen
To appear in Proceedings of SWAT 2012.
Abstract

A small depth-16 circuit for the AES S-Box

J. Boyar, R. Peralta
to appear in Proceedings of IFIP SECURITY 2012.
Abstract

A comparison of performance measures via online search

J. Boyar, K.S. Larsen, A. Maiti
SIAM Joint FAW-AAIM Conference, Lecture Notes in Computer Science 7285: 303-314. Springer, 2012.
Abstract

A new combinational logic minimization technique with applications to cryptology

J. Boyar, R. Peralta
9th International Symposium on Experimental Algorithms (SEA 2010), Lecture Notes in Computer Science 6049: 178-189. Springer 2010.
Abstract

A comparison of performance measures for online algorithms

J. Boyar, S. Irani, K.S. Larsen
11th International Algorithms and Data Structures Symposium (WADS 2009), Lecture Notes in Computer Science 5664: 119-130. Springer, 2009.
Abstract

On the shortest linear straight-line program for computing linear forms

J. Boyar, P. Matthews, R. Peralta
33nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Lecture Notes in Computer Science 5162: 168-179, Springer, 2008.
Abstract

Theoretical evidence for the superiority of LRU-2 over LRU for the paging problem

J. Boyar, M.R. Ehmsen, K.S. Larsen
Approximation and Online Algorithms (WAOA 2006), Lecture Notes in Computer Science 4368: 95-107, Springer, 2007.
Abstract

Concrete multiplicative complexity of symmetric functions

J. Boyar, R. Peralta
Mathematical Foundations of Computer Science 2006 (MFCS 2006), Lecture Notes in Computer Science 4162:179-189, Springer, 2006.
Abstract

Scheduling jobs on Grid processors

J. Boyar, L.M. Favrholdt
Algorithm Theory: SWAT 2006, Lecture Notes in Computer Science 4059: 17-28, Springer-Verlag, 2006.
Abstract

The maximum resource bin packing problem

J. Boyar, L. Epstein, L.M. Favrholdt, J.S. Kohrt, K.S. Larsen, M.M. Pedersen, S. Wøhlk
Fundamentals of Computation Theory: 15th International Symposium, (FCT 2005), Lecture Notes in Computer Science 3623: 397-408, Springer-Verlag, 2005.
Abstract

The relative worst order ratio applied to paging

J. Boyar, L.M. Favrholdt, K.S. Larsen
Proceedings of the Sixteenth ACM-SIAM Symposium on Discrete Algorithms, (SODA 2005), 718-727, 2005.
Abstract.

Priority algorithms for graph optimization problems

A. Borodin, J. Boyar, K.S. Larsen
Second Workshop on Approximation and Online Algorithms, (WAOA 2004), Lecture Notes in Computer Science 3351: 126-139, Springer-Verlag, 2005.
Abstract.

The relative worst order ratio applied to seat reservation

J. Boyar, P. Medvedev
Proceedings of the Ninth Scandinavian Workshop on Algorithm Theory, (SWAT 2004), Lecture Notes in Computer Science 3111: 90-101, Springer-Verlag, 2004.
Abstract.

The relative worst order ratio for on-line algorithms

J. Boyar, L.M. Favrholdt
5th Italian Conference on Algorithms and Complexity (CIAC 2003), Lecture Notes in Computer Science 2653: 58-69, Springer-Verlag, 2003.
Abstract.

Extending the accommodating function

J. Boyar, L.M. Favrholdt, K.S. Larsen, M.N. Nielsen
Eighth Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science 2387: 87-96, Springer-Verlag, 2002.
Abstract.

Seat reservation allowing seat changes

J. Boyar, S. Krarup, M.N. Nielsen
Workshop on Algorithmic Methods and Models for Optimization of Railways, ATMOS 2001,
Proc. of the Satellite Workshops of the 28th International Colloquium on Automata, Languages, and Programming,
Electronic Notes in Theoretical Computer Science 50: 24--38, Elsevier Science B.V., 2001.
Abstract.

Better bounds on the accommodating ratio for the seat reservation problem

E. Bach, J. Boyar, T. Jiang, K.S. Larsen, G.-H. Lin
Proceedings of the Sixth Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science 1858: 221-231, Springer-Verlag, 2000.
Abstract.

Fair versus unrestricted bin packing

Y. Azar, J. Boyar, L.M. Favrholdt, K.S. Larsen, Morten N. Nielsen
Proceedings of the Seventh Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 1851: 200-213, Springer-Verlag, 2000.
Abstract.

The accommodating function - a generalization of the competitive ratio

J. Boyar, K.S. Larsen, M.N. Nielsen
Sixth International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 1663: 74-79, Springer-Verlag, 1999.
Abstract.

Short discreet proofs

J. Boyar, R. Peralta
Advances in Cryptology - Proceedings of Eurocrypt '96, Lecture Notes in Computer Science 1070: 131-142, Springer-Verlag, 1996.

Amortization results for chromatic search trees, with an application to priority queues

J. Boyar, R. Fagerberg, K.S. Larsen
Fourth International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 955: 270-281, Springer-Verlag, 1995.
Abstract.

Efficient rebalancing of chromatic search trees

J. Boyar, K.S. Larsen
Proceedings of the Third Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 621: 151-164, Springer-Verlag, 1992.
Abstract.

Subquadratic zero-knowledge

J. Boyar, G. Brassard, R. Peralta
Proc. 32nd IEEE Symp. on Foundations of Computer Science, 69-78, 1991.

Convertible undeniable signatures

J. Boyar, D. Chaum, I. Damgård, T. Pedersen
Advances in Cryptology - CRYPTO '90 Proceedings, Lecture Notes in Computer Science 537: 189-205, Springer-Verlag, 1991.

On the concrete complexity of zero-knowledge proofs

J. Boyar, R. Peralta
Advances in Cryptology - CRYPTO '89 Proceedings, Lecture Notes in Computer Science 435: 507-525, Springer-Verlag, 1990.

Practical zero-knowledge proofs: giving hints and using deficiencies

J. Boyar, K. Friedl, C. Lund
Advances in Cryptology - EUROCRYPT '89, Lecture Notes in Computer Science 434: 155-172, Springer-Verlag, 1990.

Inferring a sequence generated by a linear congruence

J.B. Plumstead
Proc. 23rd IEEE Symp. on Foundations of Computer Science, 153-159, 1982.
An abstract of this paper also appears in "Advances in Cryptography: Proceedings of CRYPTO 82, Plenum Press, 1983."

Some preprints

Better bounds on the accommodating ration for the seat reservation problem

E. Bach, J. Boyar, T. Jiang, K.S. Larsen, G.-H. Lin
IMADA preprint PP-2000-08, University of Southern Denmark, Odense, April 6, 2000.
Abstract and paper.

Fair versus unrestricted bin packing

Y. Azar, J. Boyar, L.M. Favrholdt, K.S. Larsen, M.N. Nielsen
IMADA preprint PP-2000-04, University of Southern Denmark, Odense, March 10, 2000.
Abstract and paper.

Slides for a talk

The accommodating ratio: A performance measure for on-line algorithms

J. Boyar, M.N. Nielsen, K.S. Larsen. Presented at Dagstuhl Seminar: Competitive Algorithms, June 1999.
Slides.