Table of Contents

Refereed Journal Papers

Online-bounded analysis
J. Boyar, L. Epstein, L.M. Favrholdt, K.S. Larsen, A. Levin
To appear in Journal of Scheduling, DOI 10.1007/s10951-017-0536-y.
Abstract

Weighted online problems with advice
J. Boyar, L.M. Favrholdt, C. Kudahl, J.W. Mikkelsen
To appear in Theory of Computing Systems.
Abstract

Online algorithms with advice: A survey
J. Boyar, L.M. Favrholdt, C. Kudahl, K.S. Larsen, J.W. Mikkelsen
ACM Computing Surveys, 50(2), Article No. 19, 2017.
Open access.
Earlier version, invited contribution, in SIGACT News, 47: 93-129, 2016.

Adding isolated vertices makes some greedy online algorithms optimal
J. Boyar, C. Kudahl
To appear in Discrete Applied Mathematics, DOI 10.1016/j.dam.2017.02.025.
Abstract

The advice complexity of a class of hard online problems
J. Boyar, L.M. Favrholdt, C. Kudahl, J.W. Mikkelsen
To appear in Theory of Computing Systems, DOI 10.1007/s00224-016-9688-y.
Abstract

On the list update problem with advice
J. Boyar, S. Kamali, K.S. Larsen, A. López-Ortiz
Information and Computation, 253: 411-423, 2017.
Abstract

Online bin packing with advice
J. Boyar, S. Kamali, K.S. Larsen, A. López-Ortiz
Algorithmica, 74: 507-527, 2016.
Abstract and paper

On various nonlinearity measures for Boolean functions
J. Boyar, M.G. Find, R. Peralta.
Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences, 8: 313-330, 2016.
Abstract and almost final version of paper.

The frequent items problem in online streaming under various performance measures
J. Boyar, K.S. Larsen, A. Maiti.
International Journal of Foundations of Computer Science, 26: 413-439, 2015.
Abstract

Relative interval analysis of paging algorithms on access graphs
J. Boyar, S. Gupta, K.S. Larsen
Theoretical Computer Science, 568: 28-48, 2015.
DOI: 10.1016/j.tcs2013.07.022.
Abstract

Cancellation-free circuits in unbounded and bounded depth
J. Boyar, M. Find
Theoretical Computer Science, 590: 17-26, 2015.
DOI: 10.1016/j.tcs.2014.10.014.
Abstract

A comparison of performance measures for online algorithms
J. Boyar, S. Irani, K.S. Larsen
Algorithmica, 72: 969-994, 2015.
DOI: 10.1007/s00453-014-9884-6.
Abstract

A comparison of performance measures via online search
J. Boyar, K.S. Larsen, A. Maiti
Theoretical Computer Science, 532: 2-13, 2014.
DOI: 10.1016/j.tcs2013.07.022.
Abstract

Logic minimization techniques with applications to cryptology
J. Boyar, P. Matthews, R. Peralta
Journal of Cryptology, 26: 280-312, 2013.
DOI: 10.1007/s00145-012-9124-7.
Abstract.

On the absolute approximation ratio for First Fit and related results
J. Boyar, G. Dósa, L. Epstein
Discrete Applied Mathematics, 160: 1914-1923, 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.
Abstract and open access.

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. Plumstead
SIAM Journal on Algebraic and Discrete Methods 6: 73-78, 1985.

Refereed Conference Papers

Relaxing the irrevocability requirement for online graph algorithms
J. Boyar, L.M. Favrholdt, M. Kotrbčik, K.S. Larsen
Algorithms and Data Structures Symposium (WADS 2017). Lecture Notes in Computer Science 10389: 217-228, Springer 2017.
Abstract

Batch coloring of graphs
J. Boyar, L. Epstein, L.M. Favrholdt, K.S. Larsen, A. Levin
14th Workshop on Approximation and Online Algorithms (WAOA 2016). Lecture Notes in Computer Science 10138: 52-64, Springer 2017.
Abstract

Weighted online problems with advice
J. Boyar, L.M. Favrholdt, C. Kudahl, J.W. Mikkelsen
27th International Workshop on Combinatorial Algorithms (IWOCA 2016). Lecture Notes in Computer Science 9843: 179-190, Springer 2016.
Abstract

Online dominating set
J. Boyar, S.J. Eidenbenz, L.M. Favrholdt, M. Kotrbčik, K.S. Larsen
15th Scandinavian Symposium and Workshops on Algorithmic Theory (SWAT 2016). Leibniz International Proceedings in Informatics 53: 21:1-21:15, 2016.
Article

Online bounded analysis
J. Boyar, L. Epstein, L.M. Favrholdt, K.S. Larsen, A. Levin
11th International Computer Science Symposium in Russia (CSR 2016). Lecture Notes in Computer Science 9691: 131-145, Springer 2016.
Abstract

Adding isolated vertices makes some online algorithms optimal
J. Boyar, C. Kudahl
26th International Workshop on Combinatorial Algorithms (IWOCA 2015). Lecture Notes in Computer Science 9538: 65-76, Springer 2016.
Abstract

Constructive relationships between algebraic thickness and normality
J. Boyar, M.G. Find
Fundamentals of Computation Theory - 20th International Symposium (FCT 2015). Lecture Notes in Computer Science 9210: 106-117, Springer, 2015.
Abstract

Advice complexity for a class of online problems
J. Boyar, L.M. Favrholdt, C. Kudahl, J.W. Mikkelsen
31st Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics 30: 116-129, 2015.
Article

The relationship between multiplicative complexity and nonlinearity
J. Boyar, M.G. Find
Mathematical Foundations of Computer Science 2014 (MFCS 2014). Lecture Notes in Computer Science 8635: 130-140, Springer, 2014.
Abstract

On the list update problem with advice
J. Boyar, S. Kamali, K.S. Larsen, A. López-Ortiz
8th International Conference on Language and Automata Theory and Applications (LATA 2014). Lecture Notes in Computer Science 8370: 210-221, Springer, 2014.
Abstract

Online bin packing with advice
J. Boyar, S. Kamali, K.S. Larsen, A. López-Ortiz
31st Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics 25: 174-186, 2014.
Article

Cancellation-free circuits in unbounded and bounded depth
J. Boyar, M. Find
Fundamentals of Computation Theory - 19th International Symposium (FCT 2013), Lecture Notes in Computer Science 8070: 159-170, Springer, 2013.
Abstract

Performance measures for frequent items in online streaming
J. Boyar, K.S. Larsen, A. Maiti
Fundamentals of Computation Theory - 19th International Symposium (FCT 2013), Lecture Notes in Computer Science 8070: 60-71, Springer, 2013.
Abstract

Bounds for scheduling on Grid processors
J. Boyar, F. Ellen
Space-Efficient Data Structures, Streams, and Algorithms, Lecture Notes in Computer Science 8066: 12-26, Springer, 2013.
Abstract

Relative interval analysis of paging algorithms on access graphs
J. Boyar, S. Gupta, K.S. Larsen
Algorithms and Data Structures Symposium (WADS 2013), Lecture Notes in Computer Science 8037: 195-206, Springer, 2013.
Abstract

Four measures of nonlinearity
J. Boyar, M. Find, R. Peralta
8th International Conference on Algorithms and Complexity (CIAC 2013), Lecture Notes in Computer Science 7878: 61-72, Springer, 2013.
Abstract

Access graphs results for LRU versus FIFO under relative worst order analysis
J. Boyar, S. Gupta, K.S. Larsen
13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), Lecture Notes in Computer Science 7357: 328-339, Springer, 2012.
Abstract

A small depth-16 circuit for the AES S-Box
J. Boyar, R. Peralta
Information Security and Privacy Research, 27th IFIP TC 11 Information Security and Privacy Conference (SEC 2012), IFIP Advances in Information and Communication Technology 376: 287-298, Springer, 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."

Miscellaneous

Patents

Patent No. US 8,316,338 B2, granted November 20, 2012, "Method of optimizing combinational circuits", with René Peralta.
Patent No. US 8,707,224 B2, granted April 22, 2014, "Method of optimizing combinational circuits", with René Peralta, division of application number 12/367,660, now Pat.No. 8,316,338.

Official public challenge solved

Solved the first challenge by the inventors of Keccak, the winner of the hash function competition by NIST in 2012. Solved with René Peralta on March 6, 2013.
Recognized on: Keccak Crunchy contest site
Scans of prize: signed side and back side, Turkish money signed by Guido Bertoni.

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.