Joan Boyar

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 Cryptol. ePrint Arch., 2024

Complexity Classes for Online Problems with and without Predictions.

[BibT_eX]

[DOI]

CoRR, 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

Relative Worst-order Analysis: A Survey.

[BibT_eX]

[DOI]

ACM Comput. Surv., 2022

Relaxing the Irrevocability Requirement for Online Graph Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 2022

Online Unit Profit Knapsack with Untrusted Predictions.

[BibT_eX]

[DOI]

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

2021

Online Bin Covering with Advice.

[BibT_eX]

[DOI]

Algorithmica, 2021

2020

Advice Complexity of Priority Algorithms.

[BibT_eX]

[DOI]

Theory Comput. Syst., 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 Dominating Set.

[BibT_eX]

[DOI]

Algorithmica, 2019

2018

Multiplicative complexity of vector valued Boolean functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Online-bounded analysis.

[BibT_eX]

[DOI]

J. Sched., 2018

Weighted Online Problems with Advice.

[BibT_eX]

[DOI]

Theory Comput. Syst., 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

Batch Coloring of Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2018

2017

The Advice Complexity of a Class of Hard Online Problems.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

On the list update problem with advice.

[BibT_eX]

[DOI]

Shahin Kamali

Alejandro López-Ortiz

Inf. Comput., 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

Online Bin Packing with Advice.

[BibT_eX]

[DOI]

Shahin Kamali

Alejandro López-Ortiz

Algorithmica, 2016

2015

Relative interval analysis of paging algorithms on access graphs.

[BibT_eX]

[DOI]

Sushmita Gupta

Theor. Comput. Sci., 2015

Cancellation-free circuits in unbounded and bounded depth.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

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

[BibT_eX]

[DOI]

Abyayananda Maiti

Int. J. Found. Comput. Sci., 2015

A Comparison of Performance Measures for Online Algorithms.

[BibT_eX]

[DOI]

Sandy Irani

Algorithmica, 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

A comparison of performance measures via online search.

[BibT_eX]

[DOI]

Abyayananda Maiti

Theor. Comput. Sci., 2014

Tight Bounds for an Online Bin Packing Problem.

[BibT_eX]

[DOI]

CoRR, 2014

The Relationship between Multiplicative Complexity and Nonlinearity.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

Logic Minimization Techniques with Applications to Cryptology.

[BibT_eX]

[DOI]

Philip Matthews

J. Cryptol., 2013

Four Measures of Nonlinearity.

[BibT_eX]

[DOI]

Magnus Find

IACR Cryptol. ePrint Arch., 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

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

Scheduling Jobs on Grid Processors.

[BibT_eX]

[DOI]

Algorithmica, 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

2008

Tight bounds for the multiplicative complexity of symmetric functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

The relative worst order ratio applied to seat reservation.

[BibT_eX]

[DOI]

Paul Medvedev

ACM Trans. Algorithms, 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

The relative worst-order ratio applied to paging.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2007

2006

The maximum resource bin packing problem.

[BibT_eX]

[DOI]

Morten Monrad Pedersen

Sanne Wøhlk

Theor. Comput. Sci., 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

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

2004

Priority Algorithms for Graph Optimization Problems.

[BibT_eX]

[DOI]

Allan Borodin

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

2003

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

[BibT_eX]

[DOI]

J. Sched., 2003

Extending the accommodating function.

[BibT_eX]

[DOI]

Acta Informatica, 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

2001

The Accommodating Function: A Generalization of the Competitive Ratio.

[BibT_eX]

[DOI]

Morten N. Nielsen

SIAM J. Comput., 2001

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

[BibT_eX]

[DOI]

Nord. J. Comput., 2001

Seat Reservation Allowing Seat Changes.

[BibT_eX]

[DOI]

Susan Krarup

Morten N. Nielsen

Proceedings of the Workshop on Algorithmic MeThods and Models for Optimization of RailwayS, 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

1997

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

[BibT_eX]

[DOI]

Rolf Fagerberg

J. Comput. Syst. Sci., 1997

1996

Short Discrete Proofs.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1996

1995

Subquadratic Zero-Knowledge.

[BibT_eX]

[DOI]

Gilles Brassard

J. ACM, 1995

1994

Efficient Rebalancing of Chromatic Search Trees.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 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

1991

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

[BibT_eX]

[DOI]

Katalin Friedl

Carsten Lund

J. Cryptol., 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

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]