Joan Boyar
YOU?
Author Swipe
View article: Brief Announcement: Distributed Graph Algorithms with Predictions
Brief Announcement: Distributed Graph Algorithms with Predictions Open
We initiate the study of distributed graph algorithms with predictions in synchronous message passing systems. Each node in the graph is given a prediction, which is some extra information about the problem instance that may be incorrect. …
View article: Folding Schemes with Privacy Preserving Selective Verification
Folding Schemes with Privacy Preserving Selective Verification Open
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 inclu…
View article: Distributed Graph Algorithms with Predictions
Distributed Graph Algorithms with Predictions Open
We initiate the study of deterministic distributed graph algorithms with predictions in synchronous message passing systems. The process at each node in the graph is given a prediction, which is some extra information about the problem ins…
View article: Complexity Classes for Online Problems with and without Predictions
Complexity Classes for Online Problems with and without Predictions Open
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 onl…
View article: Online Unit Profit Knapsack with Predictions
Online Unit Profit Knapsack with Predictions Open
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 competitiv…
View article: On the Online Weighted Non-Crossing Matching Problem
On the Online Weighted Non-Crossing Matching Problem Open
We introduce and study the weighted version of an online matching problem in the Euclidean plane with non-crossing constraints: 2n points with non-negative weights arrive online, and an algorithm can match an arriving point to one of the u…
View article: Online Interval Scheduling with Predictions
Online Interval Scheduling with Predictions Open
In online interval scheduling, the input is an online sequence of intervals, and the goal is to accept a maximum number of non-overlapping intervals. In the more general disjoint path allocation problem, the input is a sequence of requests…
View article: Online Minimum Spanning Trees with Weight Predictions
Online Minimum Spanning Trees with Weight Predictions Open
We consider the minimum spanning tree problem with predictions, using the weight-arrival model, i.e., the graph is given, together with predictions for the weights of all edges. Then the actual weights arrive one at a time and an irrevocab…
View article: Online Algorithms with Predictions (Invited Talk)
Online Algorithms with Predictions (Invited Talk) Open
We give an introduction to online algorithms with predictions, from an algorithms researcher’s perspective, concentrating on minimization problems.
View article: Quotable Signatures for Authenticating Shared Quotes
Quotable Signatures for Authenticating Shared Quotes Open
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 intera…
View article: Paging with Succinct Predictions
Paging with Succinct Predictions Open
Paging is a prototypical problem in the area of online algorithms. It has also played a central role in the development of learning-augmented algorithms -- a recent line of research that aims to ameliorate the shortcomings of classical wor…
View article: Online Unit Profit Knapsack with Untrusted Predictions
Online Unit Profit Knapsack with Untrusted Predictions Open
A variant of the online knapsack problem is considered in the settings of trusted and untrusted predictions. In Unit Profit Knapsack, the items have unit profit, and it is easy to find an optimal solution offline: Pack as many of the small…
View article: Online Unit Profit Knapsack with Untrusted Predictions
Online Unit Profit Knapsack with Untrusted Predictions Open
A variant of the online knapsack problem is considered in the settings of trusted and untrusted predictions. In Unit Profit Knapsack, the items have unit profit, and it is easy to find an optimal solution offline: Pack as many of the small…
View article: Advice Complexity of Adaptive Priority Algorithms
Advice Complexity of Adaptive Priority Algorithms Open
The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework…
View article: Online Bin Covering with Advice
Online Bin Covering with Advice Open
The bin covering problem asks for covering a maximum number of bins with an online sequence of $n$ items of different sizes in the range $(0,1]$; a bin is said to be covered if it receives items of total size at least 1. We study this prob…
View article: The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing
The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing Open
This work is a continuation of efforts to define and understand competitive analysis of algorithms in a distributed shared memory setting, which is surprisingly different from the classical online setting. In fact, in a distributed shared …