JBJoan Boyar

Joan Boyar

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Open Access

    Distributed graph algorithms with predictions

    by Joan Boyar, Faith Ellen, Kim S. Larsen

  • Open Access

    Complexity Classes for Online Problems with and without Predictions

    by Magnus Berg, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen

    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

    On the online weighted non-crossing matching problem

    by Joan Boyar, Shahin Kamali, Kim S. Larsen, Ali Mohammad Lavasani, Yaqiao Li, Denis Pankratov

  • Complexity Classes for Online Problems with and Without Predictions

    by Magnus Berg, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen


  • Open Access

    Folding Schemes with Privacy Preserving Selective Verification

    by Joan Boyar, Simon Erfurth

    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

    Online Unit Profit Knapsack with Predictions

    by Joan Boyar, Lene M. Favrholdt, Kim S. Larsen

    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}}$$ r = a a ^ where a is the actual value for this average size and $$\hat{a}$$ a ^ is the prediction. We give an algorithm which is $$\frac{e-1}{e}$$ e - 1 e -competitive, if $$r=1$$ 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$$ e - 1 e r , if $$r \le 1$$ r ≤ 1 , and $$\frac{e-r}{e}r$$ e - r e r , if $$1 \le r < e$$ 1 ≤ r < e . Any algorithm with a better competitive ratio for some $$r<1$$ r < 1 will have a worse competitive ratio for some $$r>1$$ r > 1 . To obtain a positive competitive ratio for all r, we adjust the algorithm, resulting in a competitive ratio of $$\frac{1}{2r}$$ 1 2 r for $$r\ge 1$$ r ≥ 1 and $$\frac{r}{2}$$ r 2 for $$r\le 1$$ r ≤ 1 . We show that improving the result for any $$r< 1$$ r < 1 leads to a worse result for some $$r>1$$ r > 1 .


  • Quotable Signatures for Authenticating Shared Quotes

    by Joan Boyar, Simon Erfurth, Kim S. Larsen, Ruben Niederhagen


  • Open Access

    Quotable Signatures for Authenticating Shared Quotes

    by Joan Boyar, Simon Erfurth, Kim S. Larsen, Ruben Niederhagen

    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.

  • Online Interval Scheduling with Predictions

    by Joan Boyar, Lene M. Favrholdt, Shahin Kamali, Kim S. Larsen