Joan Boyar

According to our database1, Joan Boyar authored at least 85 papers between 1982 and 2022.

Collaborative distances:



In proceedings 
PhD thesis 


Online presence:



Relaxing the Irrevocability Requirement for Online Graph Algorithms.
Algorithmica, 2022

Online Unit Profit Knapsack with Untrusted Predictions.
Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

Relative Worst-order Analysis: A Survey.
ACM Comput. Surv., 2021

Online Bin Covering with Advice.
Algorithmica, 2021

Advice Complexity of Priority Algorithms.
Theory Comput. Syst., 2020

Randomized distributed online algorithms against adaptive offline adversaries.
Inf. Process. Lett., 2020

Tight Bounds for Restricted Grid Scheduling.
Int. J. Found. Comput. Sci., 2019

Scrutinizing the Tower Field Implementation of the 픽<sub>2<sup>8</sup></sub> Inverter - with Applications to AES, Camellia, and SM4.
IACR Cryptol. ePrint Arch., 2019

Advice Complexity of Adaptive Priority Algorithms.
CoRR, 2019

Small low-depth circuits for cryptographic applications.
Cryptogr. Commun., 2019

Online Dominating Set.
Algorithmica, 2019

Multiplicative complexity of vector valued Boolean functions.
Theor. Comput. Sci., 2018

Online-bounded analysis.
J. Sched., 2018

Weighted Online Problems with Advice.
Theory Comput. Syst., 2018

Adding isolated vertices makes some greedy online algorithms optimal.
Discret. Appl. Math., 2018

The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing.
CoRR, 2018

Batch Coloring of Graphs.
Algorithmica, 2018

The Advice Complexity of a Class of Hard Online Problems.
Theory Comput. Syst., 2017

On the list update problem with advice.
Inf. Comput., 2017

Online Algorithms with Advice: A Survey.
ACM Comput. Surv., 2017

On various nonlinearity measures for boolean functions.
Cryptogr. Commun., 2016

Online Bin Packing with Advice.
Algorithmica, 2016

Relative interval analysis of paging algorithms on access graphs.
Theor. Comput. Sci., 2015

Cancellation-free circuits in unbounded and bounded depth.
Theor. Comput. Sci., 2015

The Frequent Items Problem in Online Streaming Under Various Performance Measures.
Int. J. Found. Comput. Sci., 2015

A Comparison of Performance Measures for Online Algorithms.
Algorithmica, 2015

Advice Complexity for a Class of Online Problems.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Adding Isolated Vertices Makes Some Online Algorithms Optimal.
Proceedings of the Combinatorial Algorithms - 26th International Workshop, 2015

Constructive Relationships Between Algebraic Thickness and Normality.
Proceedings of the Fundamentals of Computation Theory - 20th International Symposium, 2015

A comparison of performance measures via online search.
Theor. Comput. Sci., 2014

Tight Bounds for an Online Bin Packing Problem.
CoRR, 2014

The Relationship between Multiplicative Complexity and Nonlinearity.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Logic Minimization Techniques with Applications to Cryptology.
J. Cryptol., 2013

Four Measures of Nonlinearity.
IACR Cryptol. ePrint Arch., 2013

Bounds for Scheduling Jobs on Grid Processors.
Proceedings of the Space-Efficient Data Structures, 2013

A new variable-sized bin packing problem.
J. Sched., 2012

On the absolute approximation ratio for First Fit and related results.
Discret. Appl. Math., 2012

Cancellation-free circuits: An approach for proving superlinear lower bounds for linear Boolean operators
CoRR, 2012

Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis.
Proceedings of the Algorithm Theory - SWAT 2012, 2012

A Small Depth-16 Circuit for the AES S-Box.
Proceedings of the Information Security and Privacy Research, 2012

A depth-16 circuit for the AES S-box.
IACR Cryptol. ePrint Arch., 2011

Tight results for Next Fit and Worst Fit with resource augmentation.
Theor. Comput. Sci., 2010

Priority algorithms for graph optimization problems.
Theor. Comput. Sci., 2010

Scheduling Jobs on Grid Processors.
Algorithmica, 2010

A theoretical comparison of LRU and LRU-K.
Acta Informatica, 2010

A New Combinational Logic Minimization Technique with Applications to Cryptology.
Proceedings of the Experimental Algorithms, 9th International Symposium, 2010

New logic minimization techniques with applications to cryptology.
IACR Cryptol. ePrint Arch., 2009

Tight bounds for the multiplicative complexity of symmetric functions.
Theor. Comput. Sci., 2008

The relative worst order ratio applied to seat reservation.
ACM Trans. Algorithms, 2008

On the Shortest Linear Straight-Line Program for Computing Linear Forms.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

The relative worst order ratio for online algorithms.
ACM Trans. Algorithms, 2007

The relative worst-order ratio applied to paging.
J. Comput. Syst. Sci., 2007

The maximum resource bin packing problem.
Theor. Comput. Sci., 2006

Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem.
Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

Concrete Multiplicative Complexity of Symmetric Functions.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

The Exact Multiplicative Complexity of the Hamming Weight Function
Electron. Colloquium Comput. Complex., 2005

Priority Algorithms for Graph Optimization Problems.
Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

Tight Bounds on the Competitive Ratio on Accommodating Sequences for the Seat Reservation Problem.
J. Sched., 2003

Extending the accommodating function.
Acta Informatica, 2003

The Relative Worst Order Ratio for On-Line Algorithms.
Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

Fair versus Unrestricted Bin Packing.
Algorithmica, 2002

The Accommodating Function: A Generalization of the Competitive Ratio.
SIAM J. Comput., 2001

The Competitive Ratio for On-Line Dual Bin Packing with Restricted Input Sequences.
Nord. J. Comput., 2001

Seat Reservation Allowing Seat Changes.
Electron. Notes Theor. Comput. Sci., 2001

On the multiplicative complexity of Boolean functions over the basis (cap, +, 1).
Theor. Comput. Sci., 2000

Short Non-Interactive Cryptographic Proofs.
J. Cryptol., 2000

Fair versus Unrestricted Bin Packing.
Proceedings of the Algorithm Theory, 2000

Better Bounds on the Accommodating Ratio for the Seat Reservation Problem.
Proceedings of the Computing and Combinatorics, 6th Annual International Conference, 2000

The Seat Reservation Problem.
Algorithmica, 1999

Amortization Results for Chromatic Search Trees, with an Application to Priority Queues.
J. Comput. Syst. Sci., 1997

Short Discrete Proofs.
Proceedings of the Advances in Cryptology, 1996

Subquadratic Zero-Knowledge.
J. ACM, 1995

Efficient Rebalancing of Chromatic Search Trees.
J. Comput. Syst. Sci., 1994

Bounds on Certain Multiplications of Affine Combinations.
Discret. Appl. Math., 1994

On the Communication Complexity of Zero-Knowledge Proofs.
J. Cryptol., 1993

An Arithmetic Model of Computation Equivalent to Threshold Circuits.
Theor. Comput. Sci., 1992

Practical Zero-Knowledge Proofs: Giving Hints and Using Deficiencies.
J. Cryptol., 1991

A Discrete Logarithm Implementation of Perfect Zero-Knowledge Blobs.
J. Cryptol., 1990

Convertible Undeniable Signatures.
Proceedings of the Advances in Cryptology, 1990

Inferring Sequences Produced by a Linear Congruential Generator Missing Low-Order Bits.
J. Cryptol., 1989

Inferring sequences produced by pseudo-random number generators.
J. ACM, 1989

On the Concrete Complexity of Zero-Knowledge Proofs.
Proceedings of the Advances in Cryptology, 1989

Coloring Planar Graphs in Parallel.
J. Algorithms, 1987

Inferring a Sequence Generated by a Linear Congruence
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

Inferring a Sequence Produced by a Linear Congruence.
Proceedings of the Advances in Cryptology: Proceedings of CRYPTO '82, 1982