Joan Boyar

CoRR, January, 2025

Brief Announcement: Distributed Graph Algorithms with Predictions.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2025

Complexity Classes for Online Problems with and Without Predictions.

[BibT_eX]

[DOI]

Proceedings of the Frontiers of Algorithmics - 19th International Joint Conference, 2025

2024

Online Unit Profit Knapsack with Predictions.

[BibT_eX]

[DOI]

Algorithmica, September, 2024

Advice complexity of adaptive priority algorithms.

[BibT_eX]

[DOI]

Denis Pankratov

Theor. Comput. Sci., February, 2024

Folding Schemes with Privacy Preserving Selective Verification.

[BibT_eX]

[DOI]

Simon Erfurth

IACR Commun. Cryptol., 2024

On the Online Weighted Non-Crossing Matching Problem.

[BibT_eX]

[DOI]

Shahin Kamali

Ali Mohammad Lavasani

Yaqiao Li

Denis Pankratov

Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 2024

2023

Online Interval Scheduling with Predictions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

Online Minimum Spanning Trees with Weight Predictions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

Online Algorithms with Predictions (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Quotable Signatures for Authenticating Shared Quotes.

[BibT_eX]

[DOI]

Proceedings of the Progress in Cryptology - LATINCRYPT 2023, 2023

Paging with Succinct Predictions.

[BibT_eX]

[DOI]

Antonios Antoniadis

Marek Eliás

Lene Monrad Favrholdt

Proceedings of the International Conference on Machine Learning, 2023

2022

Online Unit Profit Knapsack with Untrusted Predictions.

[BibT_eX]

[DOI]

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

2020

Randomized distributed online algorithms against adaptive offline adversaries.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2020

2019

Tight Bounds for Restricted Grid Scheduling.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2019

Small low-depth circuits for cryptographic applications.

[BibT_eX]

[DOI]

Cryptogr. Commun., 2019

Online Bin Covering with Advice.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

2018

Multiplicative complexity of vector valued Boolean functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Adding isolated vertices makes some greedy online algorithms optimal.

[BibT_eX]

[DOI]

Christian Kudahl

Discret. Appl. Math., 2018

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

[BibT_eX]

[DOI]

CoRR, 2018

Advice Complexity of Priority Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 16th International Workshop, 2018

Relative Worst-Order Analysis: A Survey.

[BibT_eX]

[DOI]

Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017

The Advice Complexity of a Class of Hard Online Problems.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Relaxing the Irrevocability Requirement for Online Graph Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

2016

Online Algorithms with Advice: A Survey.

[BibT_eX]

[DOI]

SIGACT News, 2016

On various nonlinearity measures for boolean functions.

[BibT_eX]

[DOI]

Cryptogr. Commun., 2016

Batch Coloring of Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 14th International Workshop, 2016

Online Dominating Set.

[BibT_eX]

[DOI]

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Weighted Online Problems with Advice.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

Online Bounded Analysis.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2016

2015

Advice Complexity for a Class of Online Problems.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Adding Isolated Vertices Makes Some Online Algorithms Optimal.

[BibT_eX]

[DOI]

Christian Kudahl

Proceedings of the Combinatorial Algorithms - 26th International Workshop, 2015

Constructive Relationships Between Algebraic Thickness and Normality.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 20th International Symposium, 2015

2014

Tight Bounds for an Online Bin Packing Problem.

[BibT_eX]

[DOI]

CoRR, 2014

Online Bin Packing with Advice.

[BibT_eX]

[DOI]

Shahin Kamali

Alejandro López-Ortiz

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

The Relationship between Multiplicative Complexity and Nonlinearity.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

On the List Update Problem with Advice.

[BibT_eX]

[DOI]

Shahin Kamali

Alejandro López-Ortiz

Proceedings of the Language and Automata Theory and Applications, 2014

2013

Logic Minimization Techniques with Applications to Cryptology.

[BibT_eX]

[DOI]

Philip Matthews

J. Cryptol., 2013

Relative Interval Analysis of Paging Algorithms on Access Graphs.

[BibT_eX]

[DOI]

Sushmita Gupta

Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

The Frequent Items Problem in Online Streaming under Various Performance Measures.

[BibT_eX]

[DOI]

Abyayananda Maiti

Proceedings of the Fundamentals of Computation Theory - 19th International Symposium, 2013

Cancellation-Free Circuits in Unbounded and Bounded Depth.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 19th International Symposium, 2013

Four Measures of Nonlinearity.

[BibT_eX]

[DOI]

Magnus Find

Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

Bounds for Scheduling Jobs on Grid Processors.

[BibT_eX]

[DOI]

Proceedings of the Space-Efficient Data Structures, 2013

2012

A new variable-sized bin packing problem.

[BibT_eX]

[DOI]

J. Sched., 2012

On the absolute approximation ratio for First Fit and related results.

[BibT_eX]

[DOI]

György Dósa

Leah Epstein

Discret. Appl. Math., 2012

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

[BibT_eX]

[DOI]

Magnus Find

CoRR, 2012

Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis.

[BibT_eX]

[DOI]

Sushmita Gupta

Proceedings of the Algorithm Theory - SWAT 2012, 2012

A Small Depth-16 Circuit for the AES S-Box.

[BibT_eX]

[DOI]

Proceedings of the Information Security and Privacy Research, 2012

A Comparison of Performance Measures via Online Search.

[BibT_eX]

[DOI]

Abyayananda Maiti

Proceedings of the Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, 2012

2011

A depth-16 circuit for the AES S-box.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2011

2010

Tight results for Next Fit and Worst Fit with resource augmentation.

[BibT_eX]

[DOI]

Leah Epstein

Asaf Levin

Theor. Comput. Sci., 2010

Priority algorithms for graph optimization problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

A theoretical comparison of LRU and LRU-K.

[BibT_eX]

[DOI]

Acta Informatica, 2010

A New Combinational Logic Minimization Technique with Applications to Cryptology.

[BibT_eX]

[DOI]

Proceedings of the Experimental Algorithms, 9th International Symposium, 2010

2009

New logic minimization techniques with applications to cryptology.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2009

A Comparison of Performance Measures for Online Algorithms.

[BibT_eX]

[DOI]

Sandy Irani

Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

2008

Tight bounds for the multiplicative complexity of symmetric functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

On the Shortest Linear Straight-Line Program for Computing Linear Forms.

[BibT_eX]

[DOI]

Philip Matthews

Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

2007

The relative worst order ratio for online algorithms.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

2006

Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem.

[BibT_eX]

[DOI]

Martin R. Ehmsen

Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

Scheduling Jobs on Grid Processors.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2006

Concrete Multiplicative Complexity of Symmetric Functions.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

2005

The Exact Multiplicative Complexity of the Hamming Weight Function

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

The relative worst order ratio applied to paging.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

The Maximum Resource Bin Packing Problem.

[BibT_eX]

[DOI]

Morten Monrad Pedersen

Sanne Wøhlk

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2004

Seat reservation allowing seat changes.

[BibT_eX]

[DOI]

Susan Krarup

Morten N. Nielsen

J. Algorithms, 2004

Priority Algorithms for Graph Optimization Problems.

[BibT_eX]

[DOI]

Allan Borodin

Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

The Relative Worst Order Ratio Applied to Seat Reservation.

[BibT_eX]

[DOI]

Paul Medvedev

Proceedings of the Algorithm Theory, 2004

2003

Tight Bounds on the Competitive Ratio on Accommodating Sequences for the Seat Reservation Problem.

[BibT_eX]

[DOI]

J. Sched., 2003

The Relative Worst Order Ratio for On-Line Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2002

Fair versus Unrestricted Bin Packing.

[BibT_eX]

[DOI]

Algorithmica, 2002

Extending the Accommodating Function.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001

The Competitive Ratio for On-Line Dual Bin Packing with Restricted Input Sequences.

[BibT_eX]

[DOI]

Nord. J. Comput., 2001

2000

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

[BibT_eX]

[DOI]

Denis Pochuev

Theor. Comput. Sci., 2000

Short Non-Interactive Cryptographic Proofs.

[BibT_eX]

[DOI]

Ivan Damgård

J. Cryptol., 2000

Fair versus Unrestricted Bin Packing.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2000

Better Bounds on the Accommodating Ratio for the Seat Reservation Problem.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 6th Annual International Conference, 2000

1999

The Seat Reservation Problem.

[BibT_eX]

[DOI]

Algorithmica, 1999

The Accommodating Function - A Generalization of the Competitive Ratio.

[BibT_eX]

[DOI]

Morten N. Nielsen

Proceedings of the Algorithms and Data Structures, 6th International Workshop, 1999

1996

Short Discrete Proofs.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1996

1995

Amortization Results for Chromatic Search Trees, with an Application to Priority Queues.

[BibT_eX]

[DOI]

Rolf Fagerberg

Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

1994

Bounds on Certain Multiplications of Affine Combinations.

[BibT_eX]

[DOI]

Faith E. Fich

Discret. Appl. Math., 1994

1993

On the Communication Complexity of Zero-Knowledge Proofs.

[BibT_eX]

[DOI]

Carsten Lund

J. Cryptol., 1993

1992

An Arithmetic Model of Computation Equivalent to Threshold Circuits.

[BibT_eX]

[DOI]

Gudmund Skovbjerg Frandsen

Carl Sturtivant

Theor. Comput. Sci., 1992

Efficient Rebalancing of Chromatic Search Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1992

1991

Subquadratic Zero-Knowledge

[BibT_eX]

[DOI]

Gilles Brassard

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

A Discrete Logarithm Implementation of Perfect Zero-Knowledge Blobs.

[BibT_eX]

[DOI]

Stuart A. Kurtz

Mark W. Krentel

J. Cryptol., 1990

Convertible Undeniable Signatures.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1990

1989

Inferring Sequences Produced by a Linear Congruential Generator Missing Low-Order Bits.

[BibT_eX]

[DOI]

J. Cryptol., 1989

Inferring sequences produced by pseudo-random number generators.

[BibT_eX]

[DOI]

J. ACM, 1989

Practical Zero-Knowledge Proofs: Giving Hints and Using Deficiencies.

[BibT_eX]

[DOI]

Katalin Friedl

Carsten Lund

Proceedings of the Advances in Cryptology, 1989

On the Concrete Complexity of Zero-Knowledge Proofs.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1989

1987

Coloring Planar Graphs in Parallel.

[BibT_eX]

[DOI]