Joan Boyar
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Joan Boyar has a total of 74 co-authors. Here are the top co-authors by number of shared publications:
- Kim S. Larsen
Department of Mathematics and Computer Science, University of Southern Denmark, Odense M, Denmark
56 shared publications - Lene Monrad Favrholdt
Department of Mathematics and Computer Science, University of Southern Denmark, Odense M, Denmark
32 shared publications - René Peralta
National Institute of Standards and Technology
11 shared publications Christian Kudahl
7 shared publicationsLeah Epstein
University of Haifa
6 shared publications- Denis Pankratov
Concordia University
5 shared publications
Latest Publications
- Open Access
- 19 October 2026
- Published by Elsevier in Information and Computation
- Vol. 313
Distributed graph algorithms with predictions
- 19 October 2026
- Published by Elsevier in Information and Computation
- Vol. 313
Open AccessDistributed graph algorithms with predictions
- Open Access
- 19 August 2026
- Published by Springer Nature in Theory of Computing Systems
- Vol. 70 (3) , 45
Complexity Classes for Online Problems with and without Predictions
With the developments in machine learning, there has been a surge in interest and results focused on algorithms utilizing predictions, not least in online algorithms where most new results incorporate the prediction aspect for concrete online problems. While the structural computational hardness of problems with regards to time and space is quite well developed, not much is known about online problems where time and space resources are typically not in focus. Some information-theoretical insights were gained when researchers considered online algorithms with oracle advice, but predictions of uncertain quality is a very different matter. We initiate the development of a complexity theory for online problems with predictions, considering minimization problems and one prediction bit per request. Based on the most generic hard online problem type, string guessing, we define a family of hierarchies of complexity classes (indexed by pairs of error measures) and develop notions of reductions, class membership, hardness, and completeness. Our framework contains all the tools one expects to find when working with complexity, and we illustrate our tools by analyzing problems with different characteristics. In addition, we show that known lower bounds for paging with discard predictions apply directly to all hard problems for each class in the hierarchy based on the canonical pair of error measures. This paging problem is not complete for these classes. Our work also implies corresponding complexity classes for classic online problems without predictions, with the corresponding complete problems.
- 19 August 2026
- Published by Springer Nature in Theory of Computing Systems
- Vol. 70 (3) , 45
Open AccessComplexity Classes for Online Problems with and without Predictions
With the developments in machine learning, there has been a surge in interest and results focused on algorithms utilizing predictions, not least in online algorithms where most new results incorporate the prediction aspect for concrete online problems. While the structural computational hardness of problems with regards to time and space is quite well developed, not much is known about online problems where time and space resources are typically not in focus. Some information-theoretical insights were gained when researchers considered online algorithms with oracle advice, but predictions of uncertain quality is a very different matter. We initiate the development of a complexity theory for online problems with predictions, considering minimization problems and one prediction bit per request. Based on the most generic hard online problem type, string guessing, we define a family of hierarchies of complexity classes (indexed by pairs of error measures) and develop notions of reductions, class membership, hardness, and completeness. Our framework contains all the tools one expects to find when working with complexity, and we illustrate our tools by analyzing problems with different characteristics. In addition, we show that known lower bounds for paging with discard predictions apply directly to all hard problems for each class in the hierarchy based on the canonical pair of error measures. This paging problem is not complete for these classes. Our work also implies corresponding complexity classes for classic online problems without predictions, with the corresponding complete problems.
- Open Access
- 11 March 2026
- Published by Elsevier in Information and Computation
- Vol. 310
On the online weighted non-crossing matching problem
- 11 March 2026
- Published by Elsevier in Information and Computation
- Vol. 310
Open AccessOn the online weighted non-crossing matching problem
- 30 June 2025
- Published by Springer Nature
- p. 49-63
Complexity Classes for Online Problems with and Without Predictions
- 30 June 2025
- Published by Springer Nature
- p. 49-63
Complexity Classes for Online Problems with and Without Predictions
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 322-325
Brief Announcement: Distributed Graph Algorithms with Predictions
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 322-325
Open AccessBrief Announcement: Distributed Graph Algorithms with Predictions
- Open Access
- 13 January 2025
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (4)
Folding Schemes with Privacy Preserving Selective Verification
Folding schemes are an exciting new primitive, transforming the task of performing multiple zero-knowledge proofs of knowledge for a relation into performing just one zero-knowledge proof, for the same relation, and a number of cheap inclusion-proofs. Recently, folding schemes have been used to amortize the cost associated with proving different statements to multiple distinct verifiers, which has various applications. We observe that for these uses, leaking information about the statements folded together can be problematic, yet this happens with previous constructions. Towards resolving this issue, we give a natural definition of privacy preserving folding schemes, and what security they should offer. To construct privacy preserving folding schemes, we first define statement hiders, a primitive which might be of independent interest. In a nutshell, a statement hider hides an instance of a relation as a new instance in the same relation. The new instance is in the relation if and only if the initial instance is. With this building block, we can utilize existing folding schemes to construct a privacy preserving folding scheme, by first hiding each of the statements. Folding schemes allow verifying that a statement was folded into another statement, while statement hiders allow verifying that a statement was hidden as another statement.
- 13 January 2025
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (4)
Open AccessFolding Schemes with Privacy Preserving Selective Verification
Folding schemes are an exciting new primitive, transforming the task of performing multiple zero-knowledge proofs of knowledge for a relation into performing just one zero-knowledge proof, for the same relation, and a number of cheap inclusion-proofs. Recently, folding schemes have been used to amortize the cost associated with proving different statements to multiple distinct verifiers, which has various applications. We observe that for these uses, leaking information about the statements folded together can be problematic, yet this happens with previous constructions. Towards resolving this issue, we give a natural definition of privacy preserving folding schemes, and what security they should offer. To construct privacy preserving folding schemes, we first define statement hiders, a primitive which might be of independent interest. In a nutshell, a statement hider hides an instance of a relation as a new instance in the same relation. The new instance is in the relation if and only if the initial instance is. With this building block, we can utilize existing folding schemes to construct a privacy preserving folding scheme, by first hiding each of the statements. Folding schemes allow verifying that a statement was folded into another statement, while statement hiders allow verifying that a statement was hidden as another statement.
- Open Access
- 13 June 2024
- Published by Springer Nature in Algorithmica
- Vol. 86 (9) , 2786-2821
Online Unit Profit Knapsack with Predictions
A variant of the online knapsack problem is considered in the setting of predictions. In Unit Profit Knapsack, the items have unit profit, i.e., the goal is to pack as many items as possible. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. The prediction available to the online algorithm is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio $$r=\frac{a}{\hat{a}}$$ where a is the actual value for this average size and $$\hat{a}$$ is the prediction. We give an algorithm which is $$\frac{e-1}{e}$$ -competitive, if $$r=1$$ , and this is best possible among online algorithms knowing a and nothing else. More generally, the algorithm has a competitive ratio of $$\frac{e-1}{e}r$$ , if $$r \le 1$$ , and $$\frac{e-r}{e}r$$ , if $$1 \le r < e$$ . Any algorithm with a better competitive ratio for some $$r<1$$ will have a worse competitive ratio for some $$r>1$$ . To obtain a positive competitive ratio for all r, we adjust the algorithm, resulting in a competitive ratio of $$\frac{1}{2r}$$ for $$r\ge 1$$ and $$\frac{r}{2}$$ for $$r\le 1$$ . We show that improving the result for any $$r< 1$$ leads to a worse result for some $$r>1$$ .- 13 June 2024
- Published by Springer Nature in Algorithmica
- Vol. 86 (9) , 2786-2821
Open AccessOnline Unit Profit Knapsack with Predictions
A variant of the online knapsack problem is considered in the setting of predictions. In Unit Profit Knapsack, the items have unit profit, i.e., the goal is to pack as many items as possible. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. The prediction available to the online algorithm is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio $$r=\frac{a}{\hat{a}}$$ where a is the actual value for this average size and $$\hat{a}$$ is the prediction. We give an algorithm which is $$\frac{e-1}{e}$$ -competitive, if $$r=1$$ , and this is best possible among online algorithms knowing a and nothing else. More generally, the algorithm has a competitive ratio of $$\frac{e-1}{e}r$$ , if $$r \le 1$$ , and $$\frac{e-r}{e}r$$ , if $$1 \le r < e$$ . Any algorithm with a better competitive ratio for some $$r<1$$ will have a worse competitive ratio for some $$r>1$$ . To obtain a positive competitive ratio for all r, we adjust the algorithm, resulting in a competitive ratio of $$\frac{1}{2r}$$ for $$r\ge 1$$ and $$\frac{r}{2}$$ for $$r\le 1$$ . We show that improving the result for any $$r< 1$$ leads to a worse result for some $$r>1$$ . - 26 September 2023
- Published by Springer Nature
- p. 273-292
Quotable Signatures for Authenticating Shared Quotes
- 26 September 2023
- Published by Springer Nature
- p. 273-292
Quotable Signatures for Authenticating Shared Quotes
- Open Access
Quotable Signatures for Authenticating Shared Quotes
Quotable signature schemes are digital signature schemes with the additional property that from the signature for a message, any party can extract signatures for (allowable) quotes from the message, without knowing the secret key or interacting with the signer of the original message. Crucially, the extracted signatures are still signed with the original secret key. We define a notion of security for quotable signature schemes and construct a concrete example of a quotable signature scheme, using Merkle trees and classical digital signature schemes. The scheme is shown to be secure, with respect to the aforementioned notion of security. Additionally, we prove bounds on the complexity of the constructed scheme and provide algorithms for signing, quoting, and verifying. Finally, concrete use cases of quotable signatures are considered, using them to combat misinformation by bolstering authentic content on social media. We consider both how quotable signatures can be used, and why using them could help mitigate the effects of fake news.
Open AccessQuotable Signatures for Authenticating Shared Quotes
Quotable signature schemes are digital signature schemes with the additional property that from the signature for a message, any party can extract signatures for (allowable) quotes from the message, without knowing the secret key or interacting with the signer of the original message. Crucially, the extracted signatures are still signed with the original secret key. We define a notion of security for quotable signature schemes and construct a concrete example of a quotable signature scheme, using Merkle trees and classical digital signature schemes. The scheme is shown to be secure, with respect to the aforementioned notion of security. Additionally, we prove bounds on the complexity of the constructed scheme and provide algorithms for signing, quoting, and verifying. Finally, concrete use cases of quotable signatures are considered, using them to combat misinformation by bolstering authentic content on social media. We consider both how quotable signatures can be used, and why using them could help mitigate the effects of fake news.